noip模拟测试62

考试过程:这次考试时间安排有点不合理,主要是T1影响了我的考试心态,因为我以为旁边的人切掉了T1,所以我一直在死磕这道题,花了差不多三个小时,最后也没什么思路,最后打了颗线段树拿了50分。然后就是后三个题没时间想了,只能打暴力,倒是没有挂分。
但是下次的时间安排一定要合理,不要因为周围的人影响心态。

T1 Set

思路:我在考场上刚开始一直在想之前做过的一道题,那道题有一个思路:若\(x\%n==y\%n\),则\(x-y\)为\(n\)的倍数。但是这道题好像并不能这么用,我前两个小时都在想这个,后来实在想不出,就想了一个dp,设\(f_{i,j}\)表示\(dp\)道第\(i\)位,模\(n\)余数为\(j\)的方案是否存在,转移就很暴力\(f_{i,j}|=f_{k,n-j}\),最后再加个线段树优化把复杂度变成\(n^2log(n)\),得到了50分。
正解是利用前缀和,因为前缀和的取值只有\(0\)到\(n-1\)的范围,所以一定存在两个\(i\),\(j\),满足\(i<j\)且\(s_i==s_j\)那么我们将\(i+1\)到\(j\)输出即可,这显然是对的。
代码如下:

50pts_code

#include<bits/stdc++.h>
#define int long long
#define re register int
#define ii inline int
#define iv inline void
#define mid ((l+r)>>1)
#define lc (rt<<1)
#define rc (rt<<1|1)
#define f() cout<<"fuck"<<endl
#define head headddd
#define next net
using namespace std;
const int N=1010;
vector<int> yu[N];
int n,tot,now;
int a[N],ch[N][3],ba[N][N][2];
bool vis[N],flag;
ii read()
{
	int x=0;char ch=getchar();bool f=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-') f=0;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f?x:(-x);
}
struct Segment_Tree
{
	int dp[N<<2],pos[N<<2],fr[N<<2];
	iv insert(int rt,int l,int r,int p,int my,int fa)
	{
		if(l==r)
		{
			dp[rt]=1,pos[rt]=my,fr[rt]=fa;
			return;
		}
		if(mid>=p) insert(lc,l,mid,p,my,fa);
		else insert(rc,mid+1,r,p,my,fa);
	}
	pair<int,int> query(int rt,int l,int r,int p)
	{
		if(l==r) return make_pair(dp[rt],pos[rt]);
		if(mid>=p) return query(lc,l,mid,p);
		else return query(rc,mid+1,r,p);
	}
}T;
iv get_pre(int now,int c)
{
	if(!now) return;
	vis[now]=1,++tot;
	get_pre(ba[now][c][0],ba[now][c][1]);
}
signed main()
{
	freopen("a.in","r",stdin),freopen("a.out","w",stdout);
	n=read();
	int pos=0;
	for(re i=1;i<=n;i++) a[i]=read(),yu[a[i]%n].push_back(i);
	if(yu[0].size()) {printf("1\n");printf("%lld\n",yu[0].back());return 0;}
	T.insert(1,0,n-1,a[1]%n,1,0);
	pair<int,int> P;
	for(re i=2;i<=n;i++)
	{
		for(re j=0;j<n;j++) ch[j][0]=ch[j][1]=ch[j][2]=0;
		ch[a[i]%n][0]=1;
		for(re j=0;j<n;j++)
		{
			P=T.query(1,0,n-1,j);
			if(P.first) ch[(j+a[i])%n][0]=1,ch[(j+a[i])%n][1]=P.second,ch[(j+a[i])%n][2]=j;
		}
		for(re j=0;j<n;j++) if(ch[j][0]) T.insert(1,0,n-1,j,i,ch[j][1]),ba[i][j][0]=ch[j][1],ba[i][j][1]=ch[j][2];
		P=T.query(1,0,n-1,0);
		if(P.first) {now=P.second,flag=1;break;}
	}
	if(!flag) printf("-1\n");
	else 
	{
		get_pre(now,0);
		printf("%lld\n",tot);
		for(re i=1;i<=n;i++) if(vis[i]) printf("%lld ",i);
		printf("\n");
	}
	return 0;
}


AC_code

#include<bits/stdc++.h>
#define re register int
#define ii inline int
#define iv inline void
#define mid ((l+r)>>1)
#define lc (rt<<1)
#define rc (rt<<1|1)
#define f() cout<<"fuck"<<endl
#define head headddd
#define next net
using namespace std;
const int N=2e6+10;
int sum[N],a[N],pos[N];
int n,po;
bool flag;
ii read()
{
	int x=0;char ch=getchar();bool f=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-') f=0;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f?x:(-x);
}
signed main()
{
	freopen("a.in","r",stdin),freopen("a.out","w",stdout);
	n=read();
	for(re i=1;i<=n;i++) {a[i]=read();if(a[i]%n==0) {po=i,flag=1;}}
	if(flag) {printf("1\n");printf("%d\n",po);return 0;}
	for(re i=1;i<=n;i++)
	{
		int x=(sum[i-1]+a[i])%n;
		sum[i]=(sum[i-1]+a[i])%n;
		if(pos[x])
		{
			flag=1;
			printf("%d\n",i-pos[x]);
			for(re k=pos[x]+1;k<=i;k++) printf("%d ",k);
			return 0;
		}
		pos[x]=i;
	}
	printf("-1\n");
	return 0;
}


T2 Read

这道题其实我觉得我是可做的,但是我在考场上没有时间仔细想了,同时也是理解错了题意。
1.是上次考试有一个输入是循环节的题,我以为这也是,但是它不是。仔细分析一下数据生成就显然了。
2.我以为\(A\)数组与每一天是对应的,但是他不是,在第一天可以阅读\(A_n\)的书,也就是说\(A\)只代表种类,与那一天看无关。
那么这道题思路就很显然了。
要想每天读书的种类都不同 , 就要求每一种书的数目不超过其它书的数目 +1. 所以只要看是否有一种书超过了 \((N+1)/2\). 本题空间限制很小 , 但是 N 有很大 , 所以不能用数组存下来 , 但是我们只要找到超过\((N + 1) / 2\) 的书 , 所以我们用两个变量 \(id\), \(cnt\), \(cnt\) 初始为 0. 然后生成每一个 \(A[i]\), 如果 \(cnt==0,\) 那么就令 \(id=A[i]\), \(cnt=1\), 否则如果 \(id==A[i]\), 则 \(cnt++\), 如果不等于 , \(cnt--\). 最后只要再扫一遍求出 \(id\) 的出现次数即可 .
因为如果有书超过 \((N+1)/2\), 那么就以为这它比其他所有书的和都多 , 那么 \(cnt\) 怎么减都不会小于0, 如果没有那 \(id\) 随便是哪个都没有关系了 . 最后再求这种书要减少多少个就可以了 .
代码如下:

AC_code

#include<bits/stdc++.h>
#define re register int
#define ii inline int
#define iv inline void
#define mid ((l+r)>>1)
#define lc (rt<<1)
#define rc (rt<<1|1)
#define f() cout<<"fuck"<<endl
#define head headddd
#define next net
using namespace std;
const int N=1010;
int m,k,n,s;
int now,id,cnt,maxx,ans;
int c[N],x[N],y[N],z[N];
ii read()
{
	int x=0;char ch=getchar();bool f=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-') f=0;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f?x:(-x);
}
signed main()
{
	freopen("b.in","r",stdin),freopen("b.out","w",stdout);
	m=read(),k=read();
	for(re i=1;i<=m;i++) c[i]=read();
	for(re i=1;i<=m;i++) x[i]=read();
	for(re i=1;i<=m;i++) y[i]=read();
	for(re i=1;i<=m;i++) z[i]=read();
	s=(1<<k)-1;
	for(re i=1;i<=m;i++)
	{
		n=n+1;
		now=x[i];
		if(cnt==0 or id==now) id=now,++cnt;
		else if(id!=now) --cnt;
		long long las=x[i];
		for(re j=1;j<c[i];j++)
		{
			las=(las*1ll*y[i]+z[i])&s;
			n=n+1;
			now=las;
			if(cnt==0 or id==now) id=now,++cnt;
			else if(id!=now) --cnt;
		}
	}
	cnt=0;
	for(re i=1;i<=m;i++)
	{
		now=x[i];
		if(id==now) ++cnt;
		long long las=x[i];
		for(re j=1;j<c[i];j++)
		{
			las=(las*1ll*y[i]+z[i])&s;
			now=las;
			if(id==now) ++cnt;
		}
	}
	ans=cnt-(n-cnt+1);
	printf("%d\n",max(ans,0));
	return 0;
}


T3 题目交流通道

noip模拟测试62
这里解释一下最后那个容斥的意思,显然\(f_n=g_n\)减去不合法的方案数,那么我们对于一个有\(n\)个点的图,随便划出一条线,将这个图分成左右两部分,我们钦定左边的部分是合法的,右边的部分是不合法的,那么我们再讲左右两部分进行连边,这条边的边权必须大于0,那么一共有\(f_i\times g_i\times (k)^{i\times(n-i)}\)种方案,最后就是那个组合数,为什么不是\(c^{i}_{n}\) ,因为我们在分组的时候,只是随便划了一条线,将这个集合分成了两组,那么可能会出现同一个点同时出现在两边的情况,这样就是不合法的,那么我们钦定一个点在左边,那么就不会产生这样的情况。
再正式一点的解释就是:我们利用“”围绕基准点构造一个整体的“”的思想,我们可以枚举标号为1的节点所在的联通块包含的节点个数\(k\),从剩下的\(n-1\)个节点中选出\(k-1\)个,与一号节点一起构成大小为\(k\)的联通块,显然我们有\(c^{n-1}_{k-1}\)种选法。

最后再说一下自己的调试,首先,因为压行导致我把一个变量重复定义了,调了半天。
2.我在缩点后找点\(k\)的时候直接利用了之前的\(floyd\),也就是说在没有缩点的时候我就判断了,但是我没有考虑到缩点之后可能我找到的点\(K\)就被缩到同一个集合里了。这两个问题调了两个多小时

代码如下:

AC_code

#include<bits/stdc++.h>
#define int long long
#define re register int
#define ii inline int
#define iv inline void
#define mid ((l+r)>>1)
#define lc (rt<<1)
#define rc (rt<<1|1)
#define f() cout<<"fuck"<<endl
#define head headddd
#define next net
using namespace std;
const int N=410;
const int mo=998244353;
int n,k,ans=1,ans2=1;
int d[N][N],dis[N][N][2],nd[N][N][3],c[N][N];
int be[N],size[N],f[N],g[N];
vector<int> v;
bool vis[N];
bool no;
ii read()
{
	int x=0;char ch=getchar();bool f=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-') f=0;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f?x:(-x);
}
ii gett(int x) {return x==be[x]?x:be[x]=gett(be[x]);}
ii ksm(int d,int z)
{
	int out=1;
	while(z)
	{
		if(z&1) out=out*d%mo;
		z>>=1;
		d=d*d%mo;
	}
	return out;
}
signed main()
{
	freopen("c.in","r",stdin),freopen("c.out","w",stdout);
	n=read(),k=read();
	for(re i=1;i<=n;i++)
	{
		for(re j=1;j<=n;j++)
		{
			d[i][j]=read();
			if(d[i][j]>k) no=1;	
		}
	}
	if(no) {printf("0\n");return 0;}
	for(re i=1;i<=n;i++)
	{
		for(re j=1;j<=n;j++)
		{
			dis[i][j][0]=d[i][j];
			if(d[i][j]!=d[j][i] or d[i][i]!=0) no=1;
		}
	}
	if(no) {printf("0\n");return 0;}
	for(re k=1;k<=n;k++)
	{
		for(re i=1;i<=n;i++)
		{
			for(re j=1;j<=n;j++)
			{
				if(i==k or j==k or i==j) continue;
				if(dis[i][k][0]+dis[k][j][0]<=dis[i][j][0])
				{
					dis[i][j][0]=dis[i][k][0]+dis[k][j][0];
					if(dis[i][k][0]+dis[k][j][0]==d[i][j]) dis[i][j][1]=1;
				}
			}
		}
	}
	for(re i=1;i<=n;i++)
	{
		for(re j=1;j<=n;j++)
		{
			if(i==j) continue;
			if(dis[i][j][0]<d[i][j]) {no=1;break;}
		}
		if(no) break;
	}
	if(no) {printf("0\n");return 0;}
	for(re i=1;i<=n;i++) be[i]=i;
	for(re i=1;i<=n;i++)
	{
		for(re j=i+1;j<=n;j++)
		{
			if(i==j) continue;
			if(d[i][j]==0)
			{
				int fx=gett(i),fy=gett(j);
				if(fx==fy) continue;
				be[fy]=fx;
			}
		}
	}
	for(re i=1;i<=n;i++)
	{
		for(re j=i+1;j<=n;j++)
		{
			if(i==j) continue;
			
			if(dis[i][j][1] and dis[i][j][0]==d[i][j]) nd[gett(i)][gett(j)][0]=nd[gett(j)][gett(i)][0]=1;
			nd[gett(i)][gett(j)][2]=nd[gett(j)][gett(i)][2]=d[i][j];
		}
	}
	for(re i=1;i<=n;i++)
	{
		int x=gett(i);
		size[x]++;
		if(!vis[x]) vis[x]=1,v.push_back(x);
	}
	for(re i=1;i<=n;i++)
	{
		for(re j=i+1;j<=n;j++)
		{
			if(i==j or d[i][j]==0) continue;
			int fx=gett(i),fy=gett(j);
			if(fx!=fy) nd[fx][fy][1]++,nd[fy][fx][1]++;
		}
	}
	for(re i=0;i<v.size();i++)
	{
		for(re j=i+1;j<v.size();j++)
		{
			int x=v[i],y=v[j];bool fl=0;
			for(re k=1;k<=n;k++)if(gett(k)!=x and gett(k)!=y and dis[x][k][0]+dis[k][y][0]==dis[x][y][0]) {fl=1;break;}
			if(fl) ans=ans*ksm(k-nd[x][y][2]+1,(size[x]*size[y]))%mo;
			else ans=ans*(ksm(k-nd[x][y][2]+1,(size[x]*size[y]))-ksm(k-nd[x][y][2],(size[x]*size[y]))+mo)%mo;
		}
	}
	c[0][0]=c[1][0]=c[1][1]=1;
	for(re i=2;i<=n;i++)
	{
		c[i][0]=c[i][i]=1;
		for(re j=1;j<i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mo;
	}
	f[1]=g[1]=1;
	for(int i=2;i<=n;i++)
	{
		int z=((i)*(i-1))/2;
		g[i]=ksm(k+1,z);
		int now=0;
		for(re j=1;j<i;j++) now=(now+f[j]%mo*g[i-j]%mo*c[i-1][j-1]%mo*ksm(k,j*(i-j))%mo)%mo;
		f[i]=(g[i]-now+mo)%mo;
	}
	printf("%lld\n",(ans%mo*ans2%mo+mo)%mo);
	return 0;
}

上一篇:正睿 CSP 七连测 day3


下一篇:杂项--归并排序