Codeforces Round #502(Div. 1 + Div. 2)

A.

签到

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct mark{
    int id,sum;
    bool operator<(const mark&v)const{
        if(sum==v.sum)
            return id<v.id;
        return sum>v.sum;
    }
}G[1005];
int main()
{
    int n,i,j,k,a,b,c,d;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>a>>b>>c>>d;G[i].sum+=a+b+c+d;G[i].id=i;
    }
    sort(G+1,G+1+n);
    for(i=1;i<=n;i++){
        if(G[i].id==1){
            cout<<i<<endl;return 0;
        }
    }
}

B.

首先,可以发现一个事实:第二个串的某个位置如果是1,那么第一个串是什么是不重要的,因为换完还是1.否则,第一个串如果是0,我们就研究有多少个1可以换。但是这样就会带来一个重复的问题,对此,我们可以做一个预处理,对于每个1,相当于要换0,而相应前面的0的位置必然要换1,那么我们就可以统计一下这个重复的问题。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string str1,str2;int n,i,j,k,cnt[2]={0},cnt1[2]={0};
    cin>>n>>str1>>str2;
    for(auto a:str1)cnt[a-'0']++;
    long long ans=0;
    for(i=0;i<n;i++){
        if(str2[i]=='0'){
            if(str1[i]=='1'){
                ans+=cnt[0];ans-=cnt1[1];cnt1[0]++;
            }
            else{
                ans+=cnt[1];ans-=cnt1[0];cnt1[1]++;
            }
        }
    }
    cout<<ans<<endl;

    return 0;
}

C.

不太会证明…利用了一点类似分块的思想,反正平方分割肯定是对的…

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,j,k,pos;
    cin>>n;pos=n;
    int len=sqrt(n);
    while(pos>=len){
        for(i=pos-len+1;i<=pos;i++)
            cout<<i<<' ';
        pos-=len;
    }
    for(i=1;i<=pos;i++)
        cout<<i<<' ';

    return 0;
}

D.

比赛的时候总觉得是建树,然后就t得怀疑人生了…

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
struct node{
    int son[2];
    int cnt=0;
    bool tag;
}ch[1<<14];//数组大小由所要插入字符的总长度决定
void insert(char*str,int n)
{
    int now=0; ch[now].tag=true;
    for(int i=0;i<n;i++){
        int c=str[i]-'0';
        now=ch[now].son[c];
        ch[now].tag=true;
    }
    ch[now].cnt++; ch[now].tag=true;
}
int w[15],k;int cnt,n;
void query(string str,int id,int quan,int ceng)
{
    if(!ch[id].tag)return;
    if(ceng) {
        if ((id & 1) != str[ceng - 1] - '0')
            quan += w[ceng];
        if (quan > k)return;
        if (ceng == n) {
            cnt += ch[id].cnt;
            return;
        }
    }
        query(str,id<<1|1,quan,ceng+1);
        query(str,(id<<1)+2,quan,ceng+1);

}
int main()
{
    int i,j;
    for(i=0;i<(1<<12);i++){
        //ch[i].cnt++;
        ch[i].son[0]=i<<1|1;ch[i].son[1]=(i<<1)+2;
    }
    int m,q;
    cin>>n>>m>>q;
    for(i=1;i<=n;i++)scanf("%d",&w[i]);
    for(i=1;i<=m;i++){
        char str[15];scanf("%s",str);
        insert(str,n);
    }
    while(q--){
        string str;cin>>str>>k;
        cnt=0;
        query(str,0,0,0);
        printf("%d\n",cnt);
    }

    return 0;
}

正解是利用类似bitset的思想,因为两串相与只可能是0~2^12,所以我们可以预处理所有的情况,把他们转10进制表示,然后查询的时候就是$O(1)$的了. 有一点要注意的就是因为两个串都是0或者都是1 的时候权值都是有效的,为了方便统计,我们可以把set里面的串全部取反,然后查询的时候两个串异或一下,是1的位置就是权值有效的位置了。ans[i][j]代表模式串为i的时候两串相与为j的情况数。 以及,string会tle

#include<bits/stdc++.h>
using namespace std;
int w[5000],s[5000],ans[5000][105],f[5000];//s是将字符串转化为数字串,ans存答案,f预处理
int main() {
    int n,m,q;
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++)scanf("%d", &w[n - i]);//注意这里层级要倒着来,不然没法从前往后匹配
    for (int i = 0; i < (1 << n); i++)
        for (int j = 0; j < n; j++)
            if (i & (1 << j))//f[i]代表两个数相与等于i时的权值
                f[i] += w[j];
    for (int i = 1; i <= m; i++) {
        char ss[15];scanf("%s",ss);
        int a = 0;
        for (int j = 0; j < n; j++)
            a = a * 2 + 1 - (ss[j] - '0');//注意这里是与原数取反的!!!
            //a=a*2+(ss[j]-'0');
        s[a]++;//统计串个数
    }
    for (int i = 0; i < (1 << n); i++)
        for (int j = 0; j < (1 << n); j++)
            if (f[i ^ j] <= 100)//题意:k<=100才有效
                ans[i][f[i ^ j]] += s[j];//ans[i][j]统计模式串为i时相与答案为j的个数
                //ans[i][f[i&j]]+=s[j];
    for (int i = 0; i < (1 << n); i++)
        for (int j = 1; j <= 100; j++)
            ans[i][j] += ans[i][j - 1];//因为<=j都可以,所以,要加成前缀和
    for (int i = 1; i <= q; i++) {
        char ss[15];scanf("%s",ss);int k;scanf("%d",&k);
        int a = 0;
        for (int j = 0; j < n; j++)
            a = a * 2 + (ss[j] - '0');
        printf("%d\n", ans[a][k]);
    }

    return 0;
}