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; }