NOI Online #3提高组题解

T1水壶

和名字一样水,双指针移动或者前缀和爆草就行。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
inline void read(LL &x)
{
	LL f=1;x=0;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
LL n,k,Max=0,sum[1000005],a;
int main()
{
	read(n),read(k);k++; 
	for (int i=1;i<=n;i++) read(a),sum[i]=sum[i-1]+a;
	for (int i=k;i<=n;i++) Max=max(Max,sum[i]-sum[i-k]);
	cout<<Max<<endl;
	return 0;
}

T2魔法值

简单矩阵乘法,设一个$[1*n]$的矩阵$A$里面$A[i]$表示为第X(初始为第0)天的数值,然后设一个$[n*n]$的矩阵$B$,$B[i][j]$表示是否相连,然后矩阵快速幂$B$,最后的$B[i][j]$如果等于$1$就代表需要最后$i$城市的值需要异或上$j$城市的初始值。但是复杂度爆表,那么考虑倍增思想,把$2^i$次变换的$B$矩阵给保存然后倍增调用即可。

#include<bits/stdc++.h>
#define LL long long 
using namespace std;
LL n,m,q,a[2][105],power[105],res[2][105],P[35][105][105];
inline void read(LL &x)
{
	LL f=1;x=0;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
inline void fac1(LL x)
{
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
		{
			for (int k=1;k<=n;k++)
			P[x][i][j]^=(P[x-1][i][k]*P[x-1][k][j]);
		}
	}
}
inline void fac2(LL x)
{
	LL tmp[2][105]; 
	memset(tmp,0,sizeof(tmp));
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
		tmp[1][i]^=(res[1][j]*P[x][j][i]);
	}
	for (int i=1;i<=n;i++) res[1][i]=tmp[1][i];
}
int main()
{
	read(n),read(m),read(q);
	for (LL i=1;i<=n;i++) read(a[1][i]);
	for (LL u,v,i=1;i<=m;i++) read(u),read(v),P[0][u][v]=P[0][v][u]=1;
	power[0]=1;
	for (int i=1;i<=32;i++) fac1(i),power[i]=power[i-1]<<1;	
	while (q--)
	{
		LL X;
		read(X);
		for (int i=1;i<=n;i++) res[1][i]=a[1][i];
		for (int i=0;i<=32;i++) if ((X>>i)&1) fac2(i);
		cout<<res[1][1]<<endl;
	}
	return 0;	
} 

T3优秀子序列

设f[i]表示为子序列总和为i时的方案数,这个可以通过满足$((i-a[i])|a[i])=i$的$i-a[i]$推来,可以满足选出来的子序列中的数两两异或为$0$的这一要求。为什么?因为$(i-a[i])|a[i]=i$这一条件如果要成立的话,必须满足$i-a[i]$的所有含$1$位置对应$a[i]$的$0$位置,而$0$的位置$a[i]$随便填$1$或$0$都行,也就满足上面那个条件。如果不满足选出来的子序列中的数两两异或为$0$的这一要求,那么某一位$1$也就被$|$了两次(两个$1$在同一位$|$成一个$1$),但由于位运算的原因,最后只加上了一个$2^i$所以会导致$((i-a[i])|a[i])<i$。那么这个问题就好解决了,我们枚举一个二进制数为$i$,把它看成整个子序列的总和,那么我们就可以再通过枚举一个子集来确定$a[i]$,最后把两者异或就可以得到该子集的补集$i-a[i]$并且一定满足$((i-a[i])|a[i])=i$,然后记录下每个$a[i]$出现的次数大力推导$DP$即可,注意枚举的时候记得判断子集与补集的大小关系,每个子集与补集只算一次,防止枚举到该子集的补集导致贡献重复计算。另外记得$0$要另外算,因为它不影响选出来的子序列中的数两两异或为$0$的这一要求,所以$0$可以有$2^{tot[0]}$种出现方式在每个无0的子序列中(全0则出现在空集中)所以最后答案要乘上$2^{tot[0]}$。(一开始 🧠 升 级把空集看作$0$和其它$0$都算一起了,后面才发现是不一样的,因为一个子序列跟了不同的$0$是不同的,但跟一个空集本质是一样的,算一种。)

#include<bits/stdc++.h>
#define LL long long
#define Mod 1000000007
using namespace std;
LL n,Max=0,phi[1000005],prime[1000005],cnt=0,f[1000005],tot[1000005],a[1000005];
bool is_prime[1000005];
inline void read(LL &x)
{
	LL f=1;x=0;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
int main()
{
	phi[1]=1;
	for (LL i=2;i<=300000;i++)
	{
		if (!is_prime[i]) prime[++cnt]=i,phi[i]=i-1;
		for (LL j=1;j<=cnt&&i*prime[j]<=300000;j++)
		{
			phi[i*prime[j]]=phi[i]*phi[prime[j]];
			is_prime[i*prime[j]]=1;
			if (i%prime[j]==0) {phi[i*prime[j]]=phi[i]*prime[j];break;}
		}
	}
//	for (LL i=1;i<=100;i++) cout<<prime[i]<<" ";
	read(n);
	for (LL i=1;i<=n;i++) read(a[i]),tot[a[i]]++,Max=max(Max,a[i]),tot[a[i]]%=1000000007;
	f[0]=1;f[0]%=1000000007; 
	LL fac=1;
	for (int i=1;i<=tot[0];i++) fac=(fac*2)%1000000007;
	LL m=(LL)log2(Max)+1;
	for (LL S=1;S<=(1<<m)-1;S++)
	{
		for (LL E=S;E>=0;E=((E-1)&S)) {if (E>(S^E)) f[S]+=f[S^E]*tot[E],f[S]%=1000000007;if (E==0) break;}
	}
	long long ans=0;
	for (LL i=0;i<=(1<<m)-1;i++) ans=(ans+phi[i+1]*f[i])%1000000007;
	cout<<(ans*fac)%1000000007<<endl;
	return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇