Codeforces Round 48 Div2
A题 Death Note
题意 ：给一个本子，在上面写名字，每页最多写m个人的名字，有n天，每天给你一些名字，然后需要判断，每天需要翻多少页。
思路：就是模拟每天的情况就行了，然后需要将每天最后一页剩余名字记录下来，与下一天的进行下判断就OK了
#include <cstdio> #include <iostream> using namespace std; int main() { int n,m; int num[200005]; cin>>n>>m; for(int i=0;i<n;i++) cin>>num[i]; int name=m; for(int i=0;i<n;i++){ int t=0; if(num[i]>=name){ num[i]-=name; t++; } else { cout<<0<<' '; name-=num[i]; continue; } t+=num[i]/m; name=m*t-num[i]; cout<<t<<' '; } return 0; }
B题 Segment Occurrences
题意：给a，b两个字符串，然后给a中的一段长度，询问在这段长度中存在多少个b字符串。
思路：一开始以为要用kmp算法去匹配字符串的位置，然后存起来，然后查询的时候遍历数组就行了，但是后面发现不用kmp也不会超时。。暴力找符合的位置就行了
#include <cstdio> #include <iostream> #include <string> using namespace std; int main() { int n,m,s; string a,b; int num[200005]; int t=0; cin>>n>>m>>s; cin>>a>>b; for(int i=0;i<n;i++){ int flag=0; for(int j=0;j<m;j++){ if(a[i+j]!=b[j]){ flag=1; break; } } if(flag==0) num[t++]=i; } int q,w; for(int i=0;i<s;i++){ int sum=0; cin>>q>>w; for(int j=0;j<t;j++){ if(q<=num[j]+1&&w>=num[j]+m) sum++; } cout<<sum<<endl; } return 0; }
D题 Vasya And The Matrix
题意 ：求一个n*m的矩阵，给矩阵每行的异或，以及每列的异或，先判断是否存在这个矩阵，然后写出这个矩阵。
思路：一开始看到这个题的时候一脸懵逼，看了好久，判断挺好判断的，只需要将每行的异或给异或了再与每列的异或异或进行判断，如果相等就存在，否则就不存在。
然后就是求这样一个矩阵，其实只需要关注最后一行和最后一列就行了，其他的元素设置为0，因为0^x=x，然后最后一行和最后一列设置为这行（列）的异或就OK了，重点是最后一个元素，只需要将每行（列）的异或的异或再异或最后一行和最后一列的异或就行了，然后就是注意用long long 存，wa了几次
#include <cstdio> #include <iostream> using namespace std; int main(){ int n,m; long long num[105][105]; long long a[105],b[105]; long long sum1=0,sum2=0; cin>>n>>m; for(int i=0;i<n;i++){ cin>>a[i]; sum1^=a[i]; } for(int i=0;i<m;i++){ cin>>b[i]; sum2^=b[i]; } if(sum1!=sum2) cout<<"NO"<<endl; else { cout<<"YES"<<endl; for(int i=0;i<n;i++) num[i][m-1]=a[i]; for(int j=0;j<m;j++) num[n-1][j]=b[j]; num[n-1][m-1]=sum1^a[n-1]^b[m-1]; for(int i=0;i<n;i++){ for(int j=0;j<m;j++) cout<<num[i][j]<<' '; cout<<endl; } } return 0; }
查看11道真题和解析