cf-edu-round-48解题记录

有点难

Posted by ethan-zhou on July 10, 2020

T1

直接模拟

代码:

#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,于是直接暴力匹配,记录字串从母串的哪一位开始能匹配的上,最后来个前缀和即可。

#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 形状,如图所示:读者不难自证 T3配图 那么我们只需要用一个数组 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 形的路程

代码:

#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]\]

代码:

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


作者:@ethan-enhe
本文为作者原创,转载请注明出处:本文链接