Codeforces Round #502 (in memory of Leopoldo Taravilse, Div. 1 + Div. 2)

Codeforces Round #502 (in memory of Leopoldo Taravilse, Div. 1 + Div. 2)

T1

加和排序就可以了。

#include<cstdio>
#include<algorithm>
using namespace std;
struct xcw{
    int x,id;
    bool operator <(const xcw b)const{return x>b.x||x==b.x&&id<b.id;}
}a[1005];
int main(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x,y,z,h;scanf("%d%d%d%d",&x,&y,&z,&h);a[i].x=x+y+z+h;a[i].id=i;
    } 
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
    if(a[i].id==1){printf("%d\n",i);return 0;}
    return 0;
} 

T2

当b[i]==0时,a[i]交换才会在第i位有变换,只要交换所以a[k(k!=i)]=a[i]^1的值就会改变,然后重复的记一下。

#include<cstdio>
#include<iostream>
using namespace std;
char a[100005],b[100005];
int Num[2],Sum[2];
long long Ans;
int main(){
    int n;
    scanf("%d%s%s",&n,a,b);
    for(int i=0;i<n;i++) Sum[a[i]!='0']++;
    for(int i=0;i<n;i++)
    if(b[i]=='0'){
        if(a[i]=='1') Ans+=Sum[0]-Num[0],Num[1]++;
        else Ans+=Sum[1]-Num[1],Num[0]++;
    }
    cout<<Ans<<endl;
    return 0;
}

T3

分成\sqrt{n}块,每块之间降序,块与块之间升序,所以最好的长度就是2 * \sqrt{n}

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[100005];
int main(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++) a[i]=i;
    int END=sqrt(n);
    for(int i=0;i<n/END;i++)
    for(int j=1;j<=END/2;j++) swap(a[i*END+j],a[(i+1)*END-j+1]);
    for(int i=1;i<=n%END/2;i++) swap(a[n-n%END+i],a[n-i+1]);
    for(int i=1;i<=n;i++) printf(i==n?"%d\n":"%d ",a[i]);
    printf("\n");
    return 0;
}

T4

我们发现(k \le 100,n \le 12)所以可以O(2^{2n} * n )预处理,然后hsh[i][j],表示数为i,分数小于等于j的个数,所以就可以O(1)回答。

#include<cstdio>
#include<cctype>
using namespace std;
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret<<3)+(ret<<1)+ch-48;
    return f?ret:ret;
}
int n,m,q,a[15],Sum[1<<13][105],hsh[1<<13];
int main(){
    n=read(),m=read();q=read();
    for(int i=0;i<n;i++) a[i]=read();
    for(int i=1;i<=m;i++){
        int Num=0;char s[15];
        scanf("%s",s);
        for(int i=0;i<n;i++) Num=Num*2+(s[i]=='1');
        hsh[Num]++;
    }
    for(int i=0,END=(1<<n);i<END;i++)
    for(int j=0;j<END;j++){
        int Now=0;
        for(int k=0;k<n;k++) if((i&(1<<k))==(j&(1<<k))) Now+=a[n-k-1];
        if(Now<=100) Sum[i][Now]+=hsh[j];
    }
    for(int i=0,END=(1<<n);i<END;i++)
    for(int j=1;j<=100;j++) Sum[i][j]+=Sum[i][j-1];
    for(int i=1;i<=q;i++){
        int Num=0,Now;char s[15];
        scanf("%s%d",s,&Now);
        for(int i=0;i<n;i++) Num=Num*2+(s[i]=='1');
        printf("%d\n",Sum[Num][Now]);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部