T1
直接模拟
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
int cp=0,tmp;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&tmp);
cp+=tmp;
printf("%d ",cp/m);
cp%=m;
}
return 0;
}
|
T2
本以为这题怎么也得写个 kmp，结果发现字符串长度都小于 1000，于是直接暴力匹配，记录字串从母串的哪一位开始能匹配的上，最后来个前缀和即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int NR=1005;
int n,m,q;
char mo[NR],so[NR];
int sum[NR];
int main(){
scanf("%d%d%d",&n,&m,&q);
scanf("%s%s",mo+1,so+1);
for(int i=1;i<=n-m+1;i++){
sum[i]=1;
for(int j=0;j<m;j++)
if(mo[i+j]!=so[j+1]){
sum[i]=0;
break;
}
sum[i]+=sum[i-1];
}
while(q--){
int l,r;
scanf("%d%d",&l,&r);
if(r-l+1<m)printf("0\n");
else printf("%d\n",sum[r-m+1]-sum[l-1]);
}
return 0;
}
|
T3
这道题还不太好想，首先考虑他为什么只给两行？显然不是为了方便搜索，而是方便 dp 或者分类讨论的，想了想 dp，不太好保证没有后效性，于是只能分类讨论了。
首先，既然经过了每一个单元格，这个路径就必定先走 S 形，后走 U 形状，如图所示：读者不难自证
那么我们只需要用一个数组 usum[i][j] 来记录从 0 时刻， (i,j) 号格子开始向右走 U 形状，总共能收集到的蘑菇数量。但是光靠这一个数组我们还无法转移，我们还需要一个数组 sum[i]，表示第i列右边所有格子每秒能产生的蘑菇数量，于是，usum[i][j] 可如下转移
$$
\begin{aligned}
&usum[1][i]=usum[1][i+1]+sum[i+1]+arr[2][i]\times(2(n-i)+1)\\
&usum[2][i]=usum[2][i+1]+sum[i+1]+arr[1][i]\times(2(n-i)+1);
\end{aligned}
$$最后，假设人从 (1,1) 一直走 S 形到 (i,j) ，接着开始走 U 形，则他总共能收集到的蘑菇数等于（curt 表示当前时间， curs表示走 S 形路上收集到的总磨菇数）：
$$curs+usum[i][j+1]+sum[j+1]\times curt$$于是 枚举 (i,j) 分别计算出蘑菇数，最后取个max即可。
注意：最后还需要单独考虑从(1,1)就开始走 U 形的路程
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int NR=3e5+5;
long long n;
long long arr[3][NR];
long long sum[NR],usum[3][NR];
int main(){
scanf("%lld",&n);
for(long long tmp=1;tmp<=2;tmp++)
for(long long i=1;i<=n;i++)scanf("%lld",&arr[tmp][i]);
for(long long i=n;i;i--)sum[i]=sum[i+1]+arr[1][i]+arr[2][i];
for(long long i=n;i;i--){
usum[1][i]=usum[1][i+1]+sum[i+1]+arr[2][i]*(2*(n-i)+1);
usum[2][i]=usum[2][i+1]+sum[i+1]+arr[1][i]*(2*(n-i)+1);
}
long long curt=0,curs=0;
long long ans=0;
for(long long j=1;j<=n;j++){
if(j&1)
for(long long i=1;i<=2;i++){
curs+=(curt++)*arr[i][j];
if((i+j)&1)ans=max(ans,curs+usum[i][j+1]+sum[j+1]*curt);
}
else
for(long long i=2;i;i--){
curs+=(curt++)*arr[i][j];
if((i+j)&1)ans=max(ans,curs+usum[i][j+1]+sum[j+1]*curt);
}
}
ans=max(ans,usum[1][1]);
printf("%lld",ans);
return 0;
}
|
T4
首先条件只有 2n个，不可能解出 n^2 个未知数，加上题目中说输出任意一组符合要求的表，于是猜想可以构造一个特殊的矩阵，接着想起来我做过原题，然后就a了。
最简单的一种方法就是第 i 行的最右边一项都填 b[i]，而第i列的最靠下一格都填 a[i]，？但是右下角怎么填呢？会不会有矛盾
因为异或运算具有交换律，结合律，所以一组合法的数据满足：
$$a[1] \oplus a[2] \oplus \dots a[n]=b[1] \oplus b[2] \oplus \dots b[m]$$设右下角填的数是 x，矩阵中所有数的异或和为 xorsum，则：
$$
\left\{
\begin{aligned}
x \oplus a[1] \oplus a[2] \oplus \dots a[n-1]=b[m]\\
x \oplus b[1] \oplus b[2] \oplus \dots b[m-1]=a[n]
\end{aligned}
\right.
\\化简得
\left\{
\begin{aligned}
x \oplus xorsum \oplus a[n]=b[m]\\
x \oplus xorsum \oplus b[m]=a[n]
\end{aligned}
\right.
\\
\therefore x=xorsum \oplus a[n] \oplus b[m]
$$代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int NR=105;
int n,m;
unsigned int a[NR],b[NR],test=0,tmp=0;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",a+i);
test^=a[i];
}
tmp=test;
for(int i=1;i<=m;i++){
scanf("%d",b+i);
test^=b[i];
}
if(test){
printf("NO");
return 0;
}
printf("YES\n");
for(int i=1;i<n;i++){
for(int j=1;j<m;j++)
putchar('0'),putchar(' ');
printf("%d\n",a[i]);
}
for(int i=1;i<m;i++)printf("%d ",b[i]);
printf("%d",tmp^a[n]^b[m]);
return 0;
}
|