2020CS杯热身赛(网络赛)

发表于 更新于 分类于 本文字数： 737 阅读时长 ≈ 3 分钟

数据太弱，错误判断都能过。。

1
2
if(cnt[0]+cnt[1]==0)
        break;
A:

先考虑是一道数学题，对于某一位上出现的次数，我们可由数学知识推出为，而求出该组合数与Codeforces Round #745 (Div. 2)的D题一致。

注意oj数据后带无效空格？回车，单纯getchar判断会报WA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
LL n, k, c[N][N], mark = 2;
LL quikpower(int b)
{
    LL ans = 1, base = 2;
    while (b > 0)
    {
        if (b & 1)
        {
            ans *= base;
            ans %= p;
        }
        base *= base;
        base %= p;
        b >>= 1;
    }
    if (ans == 0)
        return p - 1;
    else
        return ans - 1;
}

int main()
{
    //IN;OUT;
    ios::sync_with_stdio(false);
    cin.tie(0);
    c[0][0] = c[1][1] = c[1][0] = 1;
    while (scanf("%lld%lld", &n, &k) == 2)
    {
        f(i, mark, n)
        {
            c[i][i] = c[i][0] = 1;
            for (int j = 1; j < i; j++)
            {
                c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % p;
            }
        }
        mark = mark < n ? n : mark;
        cout << quikpower(n) * c[n - 1][k - 1] % p << '\n';
    }
    return 0;
}

B:

考虑异或的性质，我们先求出两个数组每一位上和的个数
求出每一位上的异或值再乘以基数，即：
最后累加即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
const LL N = 1e5 + 86,p=1e9+7;
LL n, m, a[N], b[N], cnt[2],ans,base=1;
int main()
{
    //IN;OUT;
    n = io.xint();
    m = io.xint();
    f(i, 1, n) a[i] = io.xint();
    f(i, 1, m) b[i] = io.xint();
    f(k, 1, 31)
    {
        cnt[0]=cnt[1]=0;
        f(i, 1, n)
        {
            if (a[i] & 1)
            cnt[0]+=1;
            a[i]>>=1;
        }
        f(i,1,m){
            if(b[i]&1)
            cnt[1]+=1;
            b[i]>>=1;
        }
      /*if(cnt[0]+cnt[1]==0)
        break;*/
        ans+=base*((cnt[0]*(m-cnt[1])+cnt[1]*(n-cnt[0]))%p)%p;
        ans%=p;
        base<<=1;
        base%=p;
    }
    io.wll(ans);
    return 0;
}

C:

列几个情况贪心即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LL n,x,y,res=0,lx,ly;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>lx>>ly;
    f(sb,2,n){
        cin>>x>>y;
        res+=abs(x-lx)<abs(y-ly)?abs(y-ly):abs(x-lx);
        lx=x,ly=y;
    }
    cout<<res;
    return 0;
}

D:

先预处理出结果用bitset储存，然后直接判断，辣鸡1也是YES

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
bitset<100009> vis;

int main()
{
    //IN;OUT;
    ios::sync_with_stdio(false);
    cin.tie(0);
    vis.reset();
    vis[1]=1;
    for (int k = 2; k <= 100000; k++)
    {
        LL temp =k;
        while(temp*k<=100000){
            temp*=k;
            vis[temp]=1;
        }
    }
    while (1)
    {
        LL n;
        cin >> n;
        if(n==0)break;
        if (vis[n])
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    return 0;
}

E不会，老是WA

F:

二维前缀和模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const LL N = 1e3 + 86;
LL n, m, s[N][N],temp;

inline LL getsum(int x1, int y1, int x2, int y2)
{
    return s[x2][y2] + s[x1 - 1][y1 - 1] - s[x1 - 1][y2] - s[x2][y1 - 1];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    f(k, 1, n)
    {
        f(j, 1, m)
        {
            cin>>temp;
            s[k][j] = s[k - 1][j] + s[k][j - 1] - s[k - 1][j - 1] + temp;
        }
    }
    f(i,1,n){
        f(j,1,m){
            cout<<getsum(1,1,i,j)<<(j==m?"":" ");
        }
        cout<<(i==n?"":"\n");
    }
    return 0;
}

G:

按题意搞即可，可采用位操作优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
LL cnt=0;
char c;

int main()
{
    //IN;OUT;
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(~(c=getchar())){
        while(c>0){
            if(c&1)
            cnt+=1;
            c>>=1;
        }
    }
    cout<<(cnt&1);
    return 0;
}