刘润达的模拟题

随便做？真的随便做。。。

难度是逆序的。。。最后一道题贪心总是GG，wyy的code轻松AC，看来我还是太naive了。。贪心的确不行。

随(rand)

好题，太难了。。。。

【题目描述】

给出n 个正整数a1,a2…an 和一个质数mod.一个变量x 初始为1.进行m 次操作. 每次在n 个数中随机选一个ai,然后x=xai%mod.问m 次操作之后x 的取值的期 望. 答案一定可以表示成a/b 的精确分数形式.a 和b 可能很大,所以只需要输出 a(b^(10^9+5))模10^9+7 的结果.

【输入格式】

第一行三个整数n,m,mod. 接下来一行n 个空格隔开的正整数a1,a2…an

【输出格式】

一行一个整数表示答案

【样例输入】

2 1 3 1 2

【样例输出】

3

【数据范围】

第1 个测试点:mod=2 第2 个测试点:n=1 第3,4,5 个测试点:m<=1000,1<=mod<=300. 第6,7,8 个测试点:1<=mod<=300 对于全部测试点: 1<=ai<mod,mod 为质数1<=mod<=1000, 对于全部测试点:1<=n<=10^5,1<=m<=10^9

【孙金宁教你学数学】

质数P 的原根g 满足1<=rt<P,且rt 的1 次方,2 次方…(P-1)次方在模P 意义下可 以取遍1 到(P-1)的所有整数. 欧拉定理:对于质数P,1<=x<P 的任意x 的P-1 次方在模P 意义下都为1. 显然,原根的1 次方,2 次方…（P-2）次方在模P 意义下都不为1,只有(P-1)次方在 模P 意义下为1.这也是一个数成为原根的充分必要条件.

code

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int MOD=1000000007;
const int N=100100,MD=1100;
int n,m,mod,r,modt,w[N],num[MD],dm[MD],vis[MD],flag;
long long dp[MD][MD],f[MD]={1},mtr[MD][MD],g,ans,tmp;
template<class T>inline void read(T &res){
	static char ch;T flag=1;
	while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;res=ch-48;
	while((ch=getchar())>='0'&&ch<='9')res=res*10+ch-48;res*=flag;
}
long long pow_mod(long long a,int b,int mo){
  	long long ret=1;
	while(b){
    	if(b&1)ret=(ret*a)%mo;
    	a=(a*a)%mo;b>>=1;
	}
  	return ret;
}
int root(){
	for(register int i=1;i<mod;++i){
    	flag=0,tmp=1;
    	memset(vis,0,sizeof(vis));
    	for(register int j=1;j<mod;++j){
      		tmp=tmp*i%mod;
			if(vis[tmp]){
				flag=1;break;
			}
      		vis[tmp]=1;
    	}
    	if(!flag)return i;
  	}
  	return -1;
}
int main(){
	//freopen("rand.in","r",stdin);
	//freopen("rand.out","w",stdout);
	read(n),read(m),read(mod);
	for(register int i=1;i<=n;++i)read(w[i]);
	g=pow_mod(n,MOD-2,MOD),r=root();tmp=1;
	for(register int i=1;i<mod;++i)tmp=tmp*r%mod,dm[tmp]=i;
	for(register int i=1;i<=n;++i)++num[dm[w[i]]];
    for(register int i=0;i<mod;++i)
	    for(register int j=1;j<mod;++j)
	    	(dp[i][(i+j)%(mod-1)]=dp[i][(i+j)%(mod-1)]+g*num[j]%MOD)%=MOD;
	for(;m;m>>=1){
		/*
		cout<<"DP:"<<endl;
		for(register int i=0;i<=mod;++i){
			for(register int j=0;j<=mod;++j)
				printf("%010d ",dp[i][j]);
			cout<<endl;
		}cout<<endl;
		*/
	    if(m&1){
			for(register int i=0;i<=mod;++i){
				mtr[0][i]=0;
				for(register int k=0;k<=mod;++k)
					(mtr[0][i]=mtr[0][i]+f[k]*dp[k][i]%MOD)%=MOD;
			}
			for(register int i=0;i<=mod;++i)f[i]=mtr[0][i];
	    }
	    for(register int i=0;i<=mod;++i){
	    	mtr[0][i]=0;
	    	for(register int k=0;k<=mod;++k)
	        	(mtr[0][i]=mtr[0][i]+dp[0][k]*dp[k][i]%MOD)%=MOD;
		}
	    for(register int i=0;i<=mod;++i)dp[0][i]=mtr[0][i];
	    for(register int i=1;i<=mod;++i){
	    	dp[i][0]=dp[i-1][mod-2];
	    	for(register int j=1;j<mod-1;++j)dp[i][j]=dp[i-1][j-1];
	    }
		
	}
	/*
	cout<<"ED:"<<endl;
    cout<<"DP:"<<endl;
	for(register int i=0;i<=mod;++i){
		for(register int j=0;j<=mod;++j)
			printf("%010d ",dp[i][j]);
		cout<<endl;
	}cout<<endl;
	*/
	ans=0,tmp=1;
	for(register int i=0;i<=mod;++i){
		ans+=tmp*f[i]%MOD,ans%=MOD;
		tmp=tmp*r%mod;
	}
	cout<<ans<<endl;
	return 0;
}

题解

考察概率和期望的求解,矩阵乘法,原根的性质,循环矩阵的性质,倍增优化DP. 首先需要注意到虽然n可以达到\(10^5\),但相同数字可以合并考虑,只需要考虑mod个不同的数字及选择它们的概率. 第1个测试点:mod=2,则n个数字都是1,直接输出1即可. 第2个测试点:每次乘上去的数字只有一种选择,快速幂即可. 第3,4,5个测试点:定义\(f[i][j]\)表示i次操作后x的数值为j的概率.直接转移,复杂度O\((mmod^2)\) 第6,7,8个测试点:第3,4,5个测试点中的DP转移可以转化为矩阵乘法形式,利用矩阵快速幂进行优化,复杂度\(O(mod^3logm)\) 第9,10个测试点(标算):利用原根进行转化,则乘法转化为加法,\(f[i][j]\)表示i次操作后x取模后等于原根的j次方的概率.指数需要对\((mod-1)\)取模.这样转化一下我们发现转移还是矩阵的形式,而且是循环矩阵的形式.循环矩阵快速幂,复杂度\(O(mod^2logm)\) 另一种标算:定义\(f[i][j]\)表示i次操作后变成原根的j次方的概率.求出\(g[i][j]\)表示2^i次操作后变成原根的j次方的概率.倍增的思想求出\(f[m][]\)这个数组.也是O\((mod^2logm)\) 更加优越的算法:本质上我们要做的是循环卷积,可以使用fft.但本题的模数使得fft较为不方便..

便 then

便(then)

【题目描述】

给出一个RC的棋盘.共有R行C列,RC个格子.现要在每个格子都填一个非负整数.使得任意一个22的正方形区域都满足这样的性质:左上角的数字+右下角的数字=左下角的数字+右上角的数字.有些格子已经确定,你不能更改其中的数字.其他格子的数字由你决定. 这是一个符合要求的33的棋盘: 1 2 3 2 3 4 4 5 6 不难验证每个2*2的区域都是符合要求的. Orbitingflea想要知道一个可行的填充棋盘的方案.但是这个方案可能很大.所以你只需对给定的棋盘判定是否存在至少一种可行的填充棋盘的方案.

【输入格式】

第一行输入一个T，表示数据组数。接下来T组数据。 每组数据的第1行2个整数R,C表示棋盘的大小. 第2行1个整数n表示已经被填好数字的格子的数目. 接下来n行每行3个整数ri,ci,ai,表示第ri行ci列的格子被填上了数字ai.

【输出格式】

T行.第i行是第i组数据的答案.有合法方案时输出一行Yes,没有时输出一行No.

【样例输入】

6 2 2 3 1 1 0 1 2 10 2 1 20 2 3 5 1 1 0 1 2 10 1 3 20 2 1 30 2 3 40 2 2 3 1 1 20 1 2 10 2 1 0 3 3 4 1 1 0 1 3 10 3 1 10 3 3 20 2 2 4 1 1 0 1 2 10 2 1 30 2 2 20 1 1 1 1 1 -1

【样例输出】

Yes No No Yes No No

【数据范围】

第1个测试点,R=1 第2,3个测试点,R*C<=12,如果有解,保证存在一个解使得所有数字大小不超过2 第4,5个测试点,R=2 第6,7个测试点,R=3 第8个测试点,1<=R,C<=20 第9个测试点,1<=R,C<=100 对于全部测试点,1<=T<=6,1<=R,C,n<=100000,1<=ri<=R,1<=ci<=C,同一个格子不会多次被填上数字.ai是整数且绝对值不超过10^9.

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 100005
using namespace std;
template<class T>inline void read(T &res){
	static char ch;T flag=1;
	while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;res=ch-48;
	while((ch=getchar())>='0'&&ch<='9')res=res*10+ch-48;res*=flag;
}
int R,C,n,flag,T;
long long fa[N][2],w[N][2],val[N][2];
struct data{
    int x,y;
	long long val;
	data(){}
	data(int _x,int _y,long long _val):x(_x),y(_y),val(_val){}
}a[N];
bool cmpf(data a,data b){
	return a.x<b.x;
}
bool cmps(data a,data b){
	return a.y<b.y;
}
int find(int x,bool d){
    if(fa[x][d]==x)return fa[x][d];
    int tmp=find(fa[x][d],d);
    w[x][d]+=w[fa[x][d]][d];
    return fa[x][d]=tmp;
}
int cntval(int x,int y,long long l,bool d){
    int xt=find(x,d),yt=find(y,d);
    if(xt==yt)return w[x][d]==l+w[y][d];
    fa[xt][d]=yt;
    w[xt][d]=l-w[x][d]+w[y][d];
    return 1;
}
int main(){
	freopen("then.in","r",stdin);
	freopen("then.out","w",stdout);
    read(T);
    while(T--){
    	for(register int i=0;i<=N-2;i++)fa[i][0]=fa[i][1]=i;
	    memset(w,0,sizeof(w)),memset(val,127/2,sizeof(val));
	    read(R),read(C),read(n),flag=1;
	    for(register int x,y,z,i=1;i<=n;i++){
	        read(x),read(y),read(z);
	        a[i]=data(x,y,z);
	        if(z<0)flag=0;
	        if((R*C)<=12&&R!=1&&z>=3)flag=0;// 过了数据过不了样例
	    }
	    if(!flag){
	    	printf("No\n");
	    	continue;
	    }
	    sort(a+1,a+n+1,cmpf);
	    for(register int i=1;i<n;i++)
			if(a[i].x==a[i+1].x&&!cntval(a[i].y,a[i+1].y,a[i+1].val-a[i].val,1)){
				printf("No\n");flag=0;break;
			}
		if(!flag)continue;
	    sort(a+1,a+n+1,cmps);
	    for(register int i=1;i<n;i++)
			if(a[i].y==a[i+1].y&&!cntval(a[i].x,a[i+1].x,a[i+1].val-a[i].val,0)){
				printf("No\n");flag=0;break;
			}
		if(!flag)continue;
	    for(register int i=1;i<=n;i++)
	        val[find(a[i].x,0)][0]=min(val[find(a[i].x,0)][0],a[i].val+w[a[i].x][0]);
	    for(register int i=1;i<=R;i++)
	        val[find(i,0)][1]=min(val[find(i,0)][1],-w[i][0]);
	    for(register int i=1;i<=R;i++)
	        if(fa[i][0]==i&&val[i][1]+val[i][0]<0){
	        	printf("No\n");flag=0;break;
	        }
	    if(!flag)continue;
	    printf("Yes\n");
    }
    return 0;
}
/*
6
2 2 3
1 1 0
1 2 10
2 1 20
2 3 5
1 1 0
1 2 10
1 3 20
2 1 30
2 3 40
2 2 3
1 1 20
1 2 10
2 1 0
3 3 4
1 1 0
1 3 10
3 1 10
3 3 20
2 2 4
1 1 0
1 2 10
2 1 30
2 2 20
1 1 1
1 1 -1 
*/

题解

考察并查集的应用. 第1个测试点:只有1行,无法形成2*2的区域,只要输入的数字中没有负数就一定有解.接下来我们默认已经排除了输入的数字有负数的情况. 第2,3个测试点:3^12枚举所有可能的情况. 第4,5个测试点:仔细观察一下性质.(1,1)+(2,2)=(1,2)+(2,1),实际上是(1,1)-(2,1)=(1,2)-(2,2). 也就是说:对于任意一列,两行之间的差相等. 如果不存在填满了数字的一列:这个差我们可以随便确定,比如说让两行之间的差为0.这样一定有解. 如果存在填满了数字的一列,我们就可以确定这个差.然后去填充可以填充的数字,只要没有矛盾,不会推导出负数,就一定有解. 如果有两列都填满但是得到的两行的差不相等,则无解. 第6,7个测试点:3行的情况比2行的情况复杂,如果手动讨论不同行之间的情况,似乎是比较麻烦的,可能会有同学写出来. 第8,9个测试点:坐标范围较小,但我没有想到对应的方法,可能会有选手想到针对性的算法. 第10个测试点(标算): “对于任意一列,两行之间的差相等”是一个很重要的性质.这告诉我们:每一列差分后得到的结果相同.每一行差分后的结果也相同.于是我们对行列分别用带权并查集维护行之间,列之间的差分关系.如果差分关系出现矛盾(两行之间的差值可以推导出两种可能)则无解.如果差分关系没有矛盾,则需要求出整个矩阵中能推导出的最小值判断是否小于0.这里的推导方法是:维护差分关系的并查集必然分成了多个连通块.一种直观的方法是,枚举一个关于行的连通块,再枚举一个关于列的连通块,这两个连通块相交产生的格子中的最小值位于列和行的最小值的交点.这样的时间复杂度是很高的.实际上我们只需考虑每个关于列的连通块.对于一个关于列的连通块,我们求出这个连通块中数值最小的一列.考虑这个连通块中所有的已知数字,每个已知数字都可以求出数值最小的一列中某一个数值.在这些数值中取最小值即可,实现的时候,只需用每个已知数字求出这个连通块中某一列的最小值,再从这一列的最小值转换到最小的一列的最小值.

做(do)

【题目描述】 你是一个位于无限大二维平面上没有近战能力的膜法师,无限大二维平面上还有一个只有近战能力的香港记者. 你们都在整点上.每个回合你先行动,香港记者后行动. 香港记者的目标是使你被续.你的目标是让香港记者被续. 香港记者有一个属性是森破值,当他的森破值小于等于零他将立刻被续. 因为香港记者的近战能力比你高到不知道哪里去了,如果任意时刻你和香港记者位于同一个整点,你将立即被续. 人物(膜法师或香港记者)被续之后就被得罪了一下,从二维平面上消失了. 香港记者只有一种行动模式:移动,香港记者因为跑得比谁都快,一个回合可以移动两次.每次可以在上下左右四个方向中选一个移动一步.当然也可以选择不动.也就是说,一个回合内香港记者可以到达曼哈顿距离小于等于2的任意位置. 你在回合中可以在3种操作中选一种: 1.移动,你一个回合只能移动1次. 也就是说,一个回合内你可以到达曼哈顿距离小于等于1的任意位置. 2.膜.大呼”蛤蛤蛤”,消耗a点膜法值.对香港记者造成伤害.香港记者的森破值会减小,减小的量等于你与香港记者之间的欧几里得距离的平方.即,若你在(x1,y1),香港记者在(x2,y2),香港记者的森破值将减少(x1-x2)^2+(y1-y2)^2.膜法值不足a则不能膜. 3.念诗.大呼”苟利国家生死以,竹外桃花三两枝”,回复b点膜法值. 一开始你有c点膜法值.之后你的膜法值可以超过c. 香港记者有一个好,脑子转得比谁都快,会选择最优策略. 如果你会被续,输出”SIMPLE”,如果香港记者会被续,输出“NAIVE” 多组数据.

【输入格式】

第一行一个正整数T表示数据组数 第二行两个空格隔开的整数a,b,含义见【题目描述】. 接下来T行,每行描述一组数据.这T行每行为6个空格隔开的整数 X1,Y1,X2,Y2,c,d. 表示你的初始坐标是(X1,Y1),香港记者的初始坐标是(X2,Y2).你一开始有c点膜法值,香港记者一开始有d点森破值.

【输出格式】

T行,一行一个字符串”SIMPLE”或者“NAIVE”.

【样例输入】

2 2 1 0 0 10 10 0 10000 0 0 10 10 0 10

【样例输出】

SIMPLE NAIVE

【数据范围】

第1个测试点,1<=|X1-X2|+|Y1-Y2|<=6 第2个测试点,1<=|X1-X2|+|Y1-Y2|<=7 第3个测试点,1<=|X1-X2|+|Y1-Y2|<=8 第4,5个测试点,a=0 第6,7个测试点,b=0 100%的数据,T=10^5.1<=X1,X2,Y1,Y2<=10^9 |X1-X2|<=300,|Y1-Y2|<=300 0<=a,b,c<=100

code

暴力踩标程。。。。。

#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
int t,a,b,c,d,elderx,eldery,reporterx,reportery;
template<class T>inline void read(T &res){
	static char ch;T flag=1;
	while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;res=ch-48;
	while((ch=getchar())>='0'&&ch<='9')res=res*10+ch-48;res*=flag;
}
int main() {
	freopen("do.in","r",stdin);
	freopen("do.out","w",stdout);
	read(t),read(a),read(b);
	while(t--){
		read(elderx),read(eldery),read(reporterx),read(reportery),read(c),read(d);
		int x=abs(elderx-reporterx),y=abs(eldery-reportery);
		for(;;){
			if(c<a)c+=b;
			else d-=x*x+y*y,c-=a;
			if(d>0)if(x >= y+2)x-=2;
				else if(y>=x+2)y-=2;
				else x--,y--;
			else{printf("NAIVE\n");break;}
			if(x<=0&&y<=0){printf("SIMPLE\n");break;}
		}
	}
	return 0;
}

题解

考察简单的搜索和动态规划,以及分析题目性质的能力 首先香港记者必然朝着靠近膜法师的方向移动,那么有3种走法: （横1纵1)（横2）（纵2） 前3个测试点:数据范围较小,容易想到搜索.不同的数据范围对应优化程度不同的搜索,对性质的不同程度的分析. 这里介绍较为优秀的算法: 实际上膜法师如果移动的话,必然不是最优解.在膜法师移动一步之后,香港记者可以移动两步,这时两人的膜法值,森破值都没有变,膜法师白白把自己和香港记者之间的距离缩小了一格(显然两人距离越远对膜法师越有利). 因此最优解中膜法师必然停留在原地攻击香港记者.在没有足够的膜法值时就念诗.我们搜索香港记者的最优行走方式即可. 同时也发现最终答案和具体坐标无关,只和横纵坐标之差的绝对值有关.而坐标之差,初始膜法值确定时,膜法师在被香港记者续掉之前能够给香港记者造成的伤害也是确定的.预处理一下即可, 第4,5,6,7个测试点:思路和标算相同,但因为补充膜法值的操作没有意义,可以简化实现. 标算:f[i][j][k]表示两人坐标之差为(i,j),膜法师还有k的膜法值,在香港记者走到膜法师的位置之前,最多能对香港记者造成多少伤害.决策时香港记者需要选择接下来受到伤害最小的走法. 预处理f数组后每组询问可以O(1)回答.