Educational Codeforces Round 48 (Rated for Div. 2)

Educational Codeforces Round 48 (Rated for Div. 2)

T1

大水题,加上一个数,如果大于m就Ans++。

#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<<1)+(ret<<3)+ch-48;
    return f?ret:-ret;
}
int n,m;
int main(){
    n=read(),m=read();
    for(int i=1,x,lst=0;i<=n;i++) x=read(),lst+=x,printf(i==n?"%d\n":"%d ",lst/m),lst%=m;
    return 0;
}

T2

容斥一下就可以了,f[i]表示前i个字符有多少匹配,然后f[R]-f[L+Len-2]就可以了。

#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<<1)+(ret<<3)+ch-48;
    return f?ret:-ret;
}
int n,m,q,Sum[1005];
char a[1005],b[1005];
int main(){
    scanf("%d%d%d",&n,&m,&q);
    scanf("%s%s",a+1,b+1);
    for(int i=m;i<=n;i++){
        Sum[i]=Sum[i-1];bool t=1;
        for(int j=1;j<=m;j++)
        if(a[i-m+j]!=b[j]){t=0;break;}
        Sum[i]+=t;
    }
    for(int i=1;i<=q;i++){
        int x=read(),y=read();
        if(y-x<m-1) printf("0\n");
        else printf("%d\n",Sum[y]-Sum[x+m-2]);
    }
    return 0;
}

T3

两种走法,先蛇形走一段,然后绕到后面再绕回来,首先,最优解肯定是全部格子都走的情况。

先预处理,枚举中间的点,然后一加就可以了。

#include<cstdio>
#include<cctype>
#include<iostream>
#include<algorithm>
#define LL long long
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<<1)+(ret<<3)+ch-48;
    return f?ret:-ret;
}
int n,mp[2][300005];
LL Ans1,Ans2,Ans3,OUT;
LL Sum1[300005],Sum2[300005],Sum3[300005];
int main(){
    n=read();
    for(int i=1;i<=n;i++) mp[0][i]=read();
    for(int i=1;i<=n;i++) mp[1][i]=read();
    for(int i=n;i;i--) Sum1[i]=Sum1[i+1]-Ans1+(LL)mp[0][i]*(i*2-2)+(LL)mp[1][i]*(n*2-1),Ans1+=mp[1][i]+mp[0][i];
    for(int i=n;i;i--) Sum2[i]=Sum2[i+1]-Ans2+(LL)mp[1][i]*(i*2-2)+(LL)mp[0][i]*(n*2-1),Ans2+=mp[1][i]+mp[0][i];
    LL tim=0;
    for(int i=1;i<=n;i++){
        if(i&1) Sum3[i]+=Sum3[i-1]+(2ll*(LL)i-2)*mp[0][i]+(2ll*(LL)i-1)*mp[1][i];
        else Sum3[i]+=Sum3[i-1]+(2ll*(LL)i-2)*mp[1][i]+(2ll*(LL)i-1)*mp[0][i];
    }
    OUT=Sum1[1];
    for(int i=2;i<=n;i++) OUT=max(OUT,Sum3[i-1]+((i&1)?Sum1[i]:Sum2[i]));
    OUT=max(OUT,Sum3[n]);
    cout<<OUT<<endl;
    return 0;
}

T4

首先不合法情况,行异或和不等于列异或和。

然后我们构造一个这样的矩形,每行最后一列等于这一行的值,每列最后一行等于这列的值,然后其他全部放0。这样子除(n,m)不满足之外都满足。对于(n,m),我们知道行异或和等于列异或和,所以说行异或和^最后一列异或和^最后一行异或和。

#include<cstdio>
using namespace std;
int n,m,H[105],L[105],mp[105][105];
int main(){
//  freopen("D.in","r",stdin);
//  freopen("D.out","w",stdout);
    scanf("%d%d",&n,&m);
    int HXOR=0,LXOR=0;
    for(int i=1;i<=n;i++) scanf("%d",&H[i]),HXOR^=H[i];
    for(int i=1;i<=m;i++) scanf("%d",&L[i]),LXOR^=L[i];
    if(HXOR!=LXOR){printf("NO\n");return 0;}else printf("YES\n");
    for(int i=1;i<=n;i++) mp[i][m]=H[i];
    for(int i=1;i<=m;i++) mp[n][i]=L[i];
    mp[n][m]=HXOR^H[n]^L[m];
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) printf(j==m?"%d\n":"%d ",mp[i][j]);
    return 0;
}

发表评论

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

返回顶部