专栏首页Code思维奇妙屋Codeforces Round #360 div2

Codeforces Round #360 div2

Problem_A(CodeForces 688A):

题意:

  有d天, n个人。如果这n个人同时出现, 那么你就赢不了他们所有的人, 除此之外, 你可以赢他们所有到场的人。

  到场人数为0也算赢。

  现给出这n个人d天的到勤情况, 求最大连胜天数。

思路:

  暴力找下去, 维护最大天数即可。

代码:

#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define eps 1e-6
#define MAXN 110
#define MAXM 100
#define dd {cout<<"debug"<<endl;}
#define pa {system("pause");}
#define p(x) {printf("%d\n", x);}
#define pd(x) {printf("%.7lf\n", x);}
#define k(x) {printf("Case %d: ", ++x);}
#define s(x) {scanf("%d", &x);}
#define sd(x) {scanf("%lf", &x);}
#define mes(x, d) {memset(x, d, sizeof(x));}
#define do(i, x) for(i = 0; i < x; i ++)
#define dod(i, x, l) for(i = x; i >= l; i --)
#define doe(i, x) for(i = 1; i <= x; i ++)
int n, d;

int main()
{
    char str[MAXN];
    int ans = 0, max_day = 0;
    scanf("%d %d", &n, &d);
    for(int i = 0; i < d; i ++)
    {
        scanf("%s", str);
        bool flag = false;
        for(int j = 0; j < n; j ++)
            if(str[j] == '0')
                flag = true;
        if(!flag)
        {
            ans = 0;
        }
        else 
            ans = ans + 1;
        max_day = max(ans, max_day);
    }
    printf("%d\n", max_day);
    return 0;
}

Problem_B(CodeForces 688B):

题意:

  给你一个n, 给出第n个偶数长度回文串。

思路:

  显而易见, 第n个回文串就是n+n的反转, 反向再输出一次即可。

代码:

#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define eps 1e-6
#define MAXN 1000010
#define MAXM 100
#define dd {cout<<"debug"<<endl;}
#define pa {system("pause");}
#define p(x) {printf("%d\n", x);}
#define pd(x) {printf("%.7lf\n", x);}
#define k(x) {printf("Case %d: ", ++x);}
#define s(x) {scanf("%d", &x);}
#define sd(x) {scanf("%lf", &x);}
#define mes(x, d) {memset(x, d, sizeof(x));}
#define do(i, x) for(i = 0; i < x; i ++)
#define dod(i, x, l) for(i = x; i >= l; i --)
#define doe(i, x) for(i = 1; i <= x; i ++)
int len;
char str[MAXN];

int main()
{
    scanf("%s", str);
    printf("%s", str);
    for(int i = strlen(str) - 1; i >= 0; i --)
        printf("%c", str[i]);
    printf("\n");
    return 0;
}

Problem_C(CodeForces 688C):

题意:

  给一个图, n个点,m条边。

  要求你找到这样的两个集合 A, B。

  每个集合都满足如下条件:

    任意一条边至少有一个端点在这个集合中。   并且A, B无交集。

思路:

  种类并查集, 先将其分成两个类。

  然后对于每条边, 看它们是否在同一个类里, 如果在同一个类里, 那么就不可能找到这样的两个集合(因为A, B都要满足上述条件)。

  不在同一个集合便分别加入两个类里。

代码:

#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define eps 1e-6
#define MAXN 400010
#define MAXM 100
int n, m;

int fa[2 * MAXN];
bool has[MAXN];
int A[MAXN], B[MAXN];
int cnt_a, cnt_b;

int find_(int x)
{
    return fa[x] = x == fa[x] ? fa[x] : find_(fa[x]);
}

void union_(int x, int y)
{   
    x = find_(x);
    y = find_(y);
    if(x != y) fa[y] = x;
}

bool same(int x, int y)
{
    return find_(x) == find_(y);
}

int main()
{
    memset(has, false, sizeof(has));
    cnt_a = 0, cnt_b = 0;
    scanf("%d %d", &n, &m);

    for(int i = 0; i < 2 * MAXN; i ++)
        fa[i] = i;

    int u, v;
    scanf("%d %d", &u, &v);
    union_(u, v + n);
    union_(u + n, v);
    has[u] = has[v] = true;
    bool flag = false;

    for(int i = 1; i < m; i ++)
    {
        scanf("%d %d", &u, &v);
        if(flag) continue;
        if(same(u, v)) flag = true;
        else 
        {
            union_(u, v + n);
            union_(u + n, v);
            has[u] = has[v] = true;
        }
    }

    if(flag) printf("-1\n");
    else 
    {
        for(int i = 1; i <= n; i ++)
        {
            if(has[i] && find_(i) <= n)
                A[cnt_a ++] = i;
            if(has[i] && find_(i) > n)
                B[cnt_b ++] = i;
        }

        printf("%d\n", cnt_a);
        for(int i = 0; i < cnt_a; i ++)
            printf("%d ", A[i]);
        printf("\n%d\n", cnt_b);
        for(int i = 0; i < cnt_b; i ++)
            printf("%d ", B[i]);
        printf("\n");
    }
    return 0;
}

Problem_D(CodeForces 688D):

题意:

  给n个ci, 可以假设已知 x % ci = ai。

  现给一个k, 问能否由这n个式子确定x % k的值。

思路:

\(由题意可知,如果存在这样的x_1\space x_2\) \(使得\forall _{i\in [1,n]} 有 x_1\equiv a_i(mod\space c_i) 且x_2\equiv a_i(mod \space c_i)\)

$\because $ \(\left\{ \begin{array}{c} x_1\equiv a_i(mod \space c_i)\\ x_2\equiv a_i(mod \space c_i)\\ \end{array} \right.\)

得如下式子: \(\left\{ \begin{array}{c} x_1 \%c_i=a_i\%c_i\\ x_2 \%c_i=a_i\%c_i\\ \end{array} 令b=a_i\%c_i得\longrightarrow \{ \begin{array}{c} x_1\%c_i=b\\ x_2\%c_i=b\\ \end{array} \right.\)

\(\therefore (x_1 -x_2) \equiv 0(mod \space c_i)\) \(由此可得, (x_1-x_2)=yc_i \longrightarrow c_i \mid (x_1-x_2)\) \(\because \forall _{i\in [1, n]} 都有c_i \mid (x_1-x_2) \longrightarrow lcm(c_1,c_2,\cdots,c_n)\mid(x_1-x_2)\)

\(如果有\) \(x_1\equiv b(mod \space k)\) \(x_2\equiv c(mod \space k)\) \(b\neq c时,即由这n个c_i不能确定x\%k的值\) \(即(x_1-x_2) \neq0(mod \space k) \longrightarrow lcm(c_1,c_2,\cdots, c_n)\nmid k\) \(b=c时,表示可以确定x\%k的值\) \(即lcm(c_1, c_2,\cdots, c_n)\mid k \longrightarrow lcm(c_i) \mid k = 0\) 数比较大, 所以需要边除边算 代码:

#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define eps 1e-6
#define MAXN 1000000
#define MAXM 100
#define dd {cout<<"debug"<<endl;}
#define pa {system("pause");}
#define p(x) {printf("%d\n", x);}
#define pd(x) {printf("%.7lf\n", x);}
#define k(x) {printf("Case %d: ", ++x);}
#define s(x) {scanf("%d", &x);}
#define sd(x) {scanf("%lf", &x);}
#define mes(x, d) {memset(x, d, sizeof(x));}
#define do(i, x) for(i = 0; i < x; i ++)
#define dod(i, x, l) for(i = x; i >= l; i --)
#define doe(i, x) for(i = 1; i <= x; i ++)
int n, k;
LL gcd(LL a, LL b)
{
    return b == 0? a : gcd(b, a % b);
}

LL lcm(LL a, LL b)
{
    return a / gcd(a, b) * b;
}

int main()
{
    scanf("%d %d", &n, &k);

    int ans = 1;
    int c;
    for(int i = 0; i < n; i ++)
    {
        scanf("%d", &c);
        ans = gcd(k, lcm(ans, c));
    }
    printf(ans == k? "Yes\n" : "No\n");
    return 0;
}

Problem_E(CodeForces 688E): 题意: 给n个硬币,让你用这n个硬币组合出k。 并且对于每个能组合出k的组合, 计算出它能够组合出来的所有数。

思路: 设dp[i][j][y]为从前1~i个硬币, 和为sum时, 能否组合出y。 那么dp[i][j][y]就由三个状态转移过来。 1、不选第i个硬币(dp[i-1][j][y]) 2、选择第i个硬币,但是集合中已经有c[i]了(dp[i-1][j-c[i]][y]) 3、选择第i个硬币,集合中不存在ci

代码:

#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define eps 1e-6
#define MAXN 510
#define MAXM 100
#define dd {cout<<"debug"<<endl;}
#define pa {system("pause");}
#define p(x) {printf("%d\n", x);}
#define pd(x) {printf("%.7lf\n", x);}
#define k(x) {printf("Case %d: ", ++x);}
#define s(x) {scanf("%d", &x);}
#define sd(x) {scanf("%lf", &x);}
#define mes(x, d) {memset(x, d, sizeof(x));}
#define do(i, x) for(i = 0; i < x; i ++)
#define dod(i, x, l) for(i = x; i >= l; i --)
#define doe(i, x) for(i = 1; i <= x; i ++)
int n, k;
bool dp[2][MAXN][MAXN];

int main()
{
    scanf("%d %d", &n, &k);

    int c;
    
    dp[0][0][0] = 1;

    for(int i = 1; i <= n; i ++)
    {
        int cnt = i % 2;
        int pre = 1 - cnt;
        scanf("%d", &c);
        for(int j = 0; j <= k; j ++)
            for(int y = 0; y <= j; y ++)
            {
                dp[cnt][j][y] = dp[pre][j][y];
                if(j >= c)
                    dp[cnt][j][y] = (dp[cnt][j][y] | dp[pre][j - c][y]) | (y >= c? dp[pre][j - c][y - c] : 0);
            }
    }

    vector <int> V;
    for(int i = 0; i <= k; i ++)
        if(dp[n % 2][k][i]) V.push_back(i);

    printf("%d\n", V.size());
    for(int i = 0; i < V.size(); i ++)
        printf("%d ", V[i]);
    printf("\n");
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Codeforces Round #359 div2

    Problem_A(CodeForces 686A): 题意: \[ 有n个输入, +\space d_i代表冰淇淋数目增加d_i个, -\space...

    若羽
  • Codeforces Round #326 div2

      Duff 很喜欢吃肉, 每天都要吃,然而她又懒得下楼。 可以买很多放在家里慢慢吃。然而肉价每天都在变化,现给定一个n, 表示有多少天,然后第i天吃ai kg...

    若羽
  • LightOj_1317 Throwing Balls into the Baskets

      每个人进球数的期望为:E = sigma (i * C(K, i) * p ^ i * (1 - p) ^ (k - i));

    若羽
  • Codeforces Round #359 div2

    Problem_A(CodeForces 686A): 题意: \[ 有n个输入, +\space d_i代表冰淇淋数目增加d_i个, -\space...

    若羽
  • Codeforces Round #326 div2

      Duff 很喜欢吃肉, 每天都要吃,然而她又懒得下楼。 可以买很多放在家里慢慢吃。然而肉价每天都在变化,现给定一个n, 表示有多少天,然后第i天吃ai kg...

    若羽
  • Codeforces Round #315 (Div. 2)

    这次可以说是最糟糕的一次比赛了吧, 心没有静下来好好的去思考, 导致没有做好能做的题。

    若羽
  • 四则运算、幸福来敲门、求一次方程解ax+b=0

    /* 功能:四则运算 日期:2013-03-16 */ #include<stdio.h> #include<stdlib.h>

    汐楓
  • cf540D. Bad Luck Island(概率dp)

    还是想复杂了啊,我列的状态时$f[i][j], g[i][j],t[i][j]$分别表示第$i$天,$j$个$s, r, p$活着的概率

    attack
  • Python的内置函数(四十八)、setattr()函数

    setattr() 函数对应函数 getattr(),用于设置属性值,该属性不一定是存在的。

    于小勇
  • 数据哪里找?奉上社会发展类公开数据清单:6千万条数据

    公开数据能帮助记者找到好故事、验证信息。来自34个国家的24万数据如何一搜可得?有哪些关于社会发展议题的权威门户可以将数据一网打尽?遇到海量数据,想批量转换格式...

    华章科技

扫码关注云+社区

领取腾讯云代金券