12.1

树树

solution

观察发现首先染一个连向叶子结点的点是最优的。

考虑一下这个点,如果它连向了两个叶子,那么这个点选完先手必赢。

如果它只连向一个叶子,后手一定会选这个叶子,那么就相当于在原图中删掉了这 两个点。

那么我们的做法就出来了。 先染色度数为1的点,把相邻的点删掉。 如果在这一步删掉了已经删掉的点(注意不是标记的点),那么先手赢。

如果最后也没有找到这样的条件,后手赢。

这样的做法可以通过dfs来实现。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
const int N=100005;
inline int read() {
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return f*x;
}
int n;
int hd[N],to[N<<1],nxt[N<<1],tot;
inline void add(int x,int y) {
	to[++tot]=y;nxt[tot]=hd[x];hd[x]=tot;
}

bool flag;
bool dfs(int x,int fa) {
	if(flag) return 0;
	int res=0;
	for(int i=hd[x];i;i=nxt[i]) {
		int y=to[i];
		if(y==fa) continue;
		res+=dfs(y,x);
	}
	if(res>1) flag=1;//因为多于1个叶子结点肯定有解了
	if(res==1) return 0;//相当于删点
	else return 1;//无论是个死胡同还是个散开的树杈先手都能赢
}
int main() {
	int T=read();
	while(T--)  {
		n=read();
		for(int i=1;i<n;i++) {
			int x=read(),y=read();
			add(x,y);add(y,x);
		}
		if(dfs(1,0)) flag=1;
		puts(flag?"Illyasviel":"Miyu"); 
		memset(hd,0,sizeof(hd));
		tot=0;flag=0;
	}
	return 0;
}

网格

solution

垃圾构造题

无解的情况:

(1)\(n=1\)且\(1<t<m\);

(2)\(m=1\)且\(1<s<n\);

(3)\(n,m,s+t\)均为奇数。

构造如下:

(1)\(s=t=1\):

![image-20201202195459370](2020.12.1 题解.assets/image-20201202195459370.png)

(2)\(s\)和\(t\)均为奇数且\(t>1,s<n\):

![image-20201202195512307](2020.12.1 题解.assets/image-20201202195512307.png)

(3)\(n-s+1,t\)均为偶数,\(t<m\):

![image-20201202195529167](2020.12.1 题解.assets/image-20201202195529167.png)

通过旋转和翻转可以处理其他情况。

代码咕咕咕了

我考场水了个20分暴力——输出调试还眼瞎没看到错,然后成功爆零(改好的暴力在下面登不上大雅博客

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cstdlib>

using namespace std;

inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int N=105;
int n,m,s,t;
void baoli() {
	if(n==1&&m==1){
		printf("1\n");return;
	} 
	else if(n==1&&m==2) {
 		if(t==1) printf("1\n2\n");
		else printf("2\n1\n");
		return;
	}
	else if(n==1&&m==3) {
		if(t==1) printf("1\n2\n3\n");
		else if(t==3) printf("3\n2\n1\n");
		return;
	}
	else if(n==2&&m==1) {
		if(s==1) printf("1 2\n");
		else printf("2 1\n");
		return;
	} 
	else if(n==2&&m==2) {
		if(s==1&&t==1) printf("1 2\n4 3\n");
		else if(s==1&&t==2) printf("2 1\n3 4\n");
		else if(s==2&&t==1) printf("2 3\n1 4\n");
		else printf("3 4\n2 1\n");
		return;
	}
	else if(n==2&&m==3) {
		if(s==1&&t==1) printf("1 2 3\n6 5 4\n");
		else if(s==1&&t==2) printf("2 1 6\n3 4 5\n");
		else if(s==1&&t==3) printf("3 2 1\n4 5 6\n");
		else if(s==2&&t==1) printf("6 5 4\n1 2 3\n");
		else if(s==2&&t==2) printf("5 4 3\n6 1 2\n");
		else if(s==2&&t==3) printf("4 5 6\n3 2 1\n");
		return;		
	}
	else if(n==3&&m==1) {
		if(s==1) printf("1 2 3\n");
		else printf("3 2 1\n");
		return;
	}
	else if(n==3&&m==2) {
		if(s==1&&t==1) printf("1 2\n4 3\n5 6\n");
		else if(s==1&&t==2) printf("2 1\n3 4\n6 5\n");
		else if(s==2&&t==1) printf("2 3\n1 4\n6 5\n");
		else if(s==2&&t==2) printf("3 2\n4 1\n5 6\n");
		else if(s==3&&t==1) printf("3 4\n2 5\n1 6\n");
		else if(s==3&&t==2) printf("4 3\n5 2\n6 1\n");
		return;			
	}
	else if(n==3&&m==3) {
		if(s==1&&t==1) printf("1 2 9\n4 3 8\n5 6 7\n");
		else if(s==1&&t==3) printf("3 2 1\n4 5 6\n9 8 7\n");
		else if(s==2&&t==2) printf("3 4 5\n2 1 6\n9 8 7\n");
		else if(s==3&&t==1) printf("7 8 9\n6 5 4\n1 2 3\n");
		else if(s==3&&t==3) printf("9 8 7\n4 5 6\n3 2 1\n");
		return;			
	}	
}

int main(){
	// freopen("grid1.in","r",stdin);
	// freopen("my.out","w",stdout);
	int T=read();
	while(T--) {
		n=read();m=read();s=read();t=read();
		if((n&1)&&(m&1)&&((s+t)&1)) {
			puts("-1");continue;
		}
		if(n<=3&&m<=3) baoli();	
		else {
			puts("-1");
		}
	}
	return 0;
}

有手就行

观察发现只需要把每个游戏拆成一个体积为\(1\),价值为\(a_i\)和一个体积为\(2\),价值为\(a_i+b_i\)的物品即可覆盖题目中给的条件,做贪心01背包即可。

神仙拆法:这样达到了所有组合

单纯暴力

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
#define ull unsigned long long
const int threshold=10000000;
const int N=2005;
inline ull read(){
	ull x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x;
}
int a[N],b[N],n,m;
ull k1,k2;
ull Rand(){
	ull k3=k1,k4=k2;
	k1=k4;
	k3^=(k3<<23);
	k2=k3^k4^(k3>>17)^(k4>>26);
	return k2+k4;
}
void gen(int n,ull _k1,ull _k2){
	k1=_k1,k2=_k2;
	for(int i=1;i<=n;i++){
		a[i]=Rand()%threshold+1;
		b[i]=Rand()%threshold+1;
	}
}
ull f[N][N*3][4],ans;
inline void Max(ull &x,ull y){if(x<y)x=y;}
int main(){
	n=read();m=read();k1=read();k2=read();
	gen(n,k1,k2);
	for(int i=1;i<=n;i++)
		for(int j=0;j<=3*i;j++)
			for(int k=0;k<=3;k++){//上次选了k个 
				Max(f[i][j][0],f[i-1][j][k]);
				if(j>=1) Max(f[i][j][1],f[i-1][j-1][k]+a[i]);
				if(j>=2) Max(f[i][j][2],f[i-1][j-2][k]+a[i]+b[i]);
				if(j>=3) Max(f[i][j][3],f[i-1][j-3][k]+a[i]+a[i]+b[i]);
			}
	for(int i=1;i<=m;i++) 
		ans^=max(f[n][i][0],max(f[n][i][1],max(f[n][i][2],f[n][i][3])));
	cout<<ans;
	return 0;
}

正解:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
#define ull unsigned long long
const int threshold=10000000;
const int N=15000010;
inline ull read(){
	ull x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x;
}
int a[N],b[N],n,m;
ull k1,k2;
ull Rand(){
	ull k3=k1,k4=k2;
	k1=k4;
	k3^=(k3<<23);
	k2=k3^k4^(k3>>17)^(k4>>26);
	return k2+k4;
}
void gen(int n,ull _k1,ull _k2){
	k1=_k1,k2=_k2;
	for(int i=1;i<=n;i++){
		a[i]=Rand()%threshold+1;
		b[i]=Rand()%threshold+1;
	}
}
int g[3][N];//表示代价为i的取得了f_i贡献时价值为1/2的取了多少个 
ull f[N*3],ans,val[3][N];
bool cmp(ull a,ull b){return a>b;}
int main(){
	n=read();m=read();k1=read();k2=read();
	gen(n,k1,k2);
	
	for(int i=1;i<=n;i++) 
		val[1][i]=a[i],val[2][i]=a[i]+b[i];
	sort(val[1]+1,val[1]+1+n,cmp);
	sort(val[2]+1,val[2]+1+n,cmp);
	g[1][0]=1;g[2][0]=1;
	for(int i=1;i<=m;i++) {
		f[i]=f[i-1];
		g[1][i]=g[1][i-1];g[2][i]=g[2][i-1];
		if(i-1>=0&&f[i]<=f[i-1]+val[1][g[1][i-1]]) {
			f[i]=f[i-1]+val[1][g[1][i-1]];
			g[1][i]=g[1][i-1];g[2][1]=g[2][i-1];
			g[1][i]=g[1][i-1]+1;
		}
		if(i-2>=0&&f[i]<=f[i-2]+val[2][g[2][i-2]]) {
			f[i]=f[i-2]+val[2][g[2][i-2]];
			g[1][i]=g[1][i-2];g[2][1]=g[2][i-2];
			g[2][i]=g[2][i-2]+1;		
		}
	}
	for(int i=1;i<=m;i++) ans^=f[i];
	cout<<ans;
	return 0;
}

求余数

代码先粘一份std

#include <cstdio>
#include <algorithm>
#include <cstring>
 
#define R register
#define maxm 110
#define maxn 1000010
int pr[maxm], prcnt, mp[maxm], r[maxm];
int f[26][16], g[2][26][16], aans[maxm][26];
int pw[maxn], inp[maxn];
bool vis[maxm], visans[maxn];
const int mod = 1e9 + 7;
inline bool cmp(R int a, R int b) {return mp[a] < mp[b];}
inline int qpow(R int base, R int power)
{
	R int ret = 1;
	for (; power; power >>= 1, base = 1ll * base * base % mod)
		power & 1 ? ret = 1ll * ret * base % mod : 0;
	return ret;
}
struct Q {int n, m;} qq[510];
int main()
{
	R int T; scanf("%d", &T);
	for (R int i = 2; i <= 100; ++i)
	{
		if (!vis[i]) pr[++prcnt] = mp[i] = i;
		for (R int j = 1; j <= prcnt && i * pr[j] <= 100; ++j)
		{
			vis[i * pr[j]] = 1;
			mp[i * pr[j]] = mp[i];
			if (i % pr[j] == 0) break;
		}
	}
	R int maa = 0;
	for (R int i = 1; i <= T; ++i) scanf("%d%d", &qq[i].n, &qq[i].m), maa < qq[i].n ? maa = qq[i].n : 0;
	pw[0] = 1;
	for (R int i = 1; i <= maa; ++i) pw[i] = 1ll * pw[i - 1] * i % mod;
	inp[maa] = qpow(pw[maa], mod - 2);
	for (R int i = maa; i; --i) inp[i - 1] = 1ll * inp[i] * i % mod;
 
	for (R int TT = 1; TT <= T; ++TT)
	{
		R int n = qq[TT].n, m = qq[TT].m, tot = 0;
		R int lim = m < 25 ? m : 25;
		if (!visans[m])
		{
		visans[m] = 1;
		for (R int i = 2; i <= m; ++i) r[i] = i;
		std::sort(r + 2, r + m + 1, cmp);
 
		memset(f, 0, sizeof (f));
		memset(g, 0, sizeof (g));
		g[0][0][0] = 1;
		for (R int i = 2; i <= m; ++i)
		{
			if (mp[r[i]] < 10 || (mp[r[i]] != mp[r[i - 1]]))
			{
				tot ^= 1;
				memset(f, 0, sizeof (f));
				memset(g[tot], 0, sizeof (g[tot]));
			}
 
			R int tmp = r[i], tS = 0;
			if (tmp % 2 == 0) tS |= 1;
			if (tmp % 3 == 0) tS |= 2;
			if (tmp % 5 == 0) tS |= 4;
			if (tmp % 7 == 0) tS |= 8;
			
			R int pS = ~tS & 15;

			for (R int j = lim; j; --j)
			{
				R int *fij = f[j], *gij = g[tot ^ 1][j - 1];
				for (R int S = pS; S; S = (S - 1) & pS)
					(fij[S | tS] += gij[S]) %= mod;
				(fij[tS] += gij[0]) %= mod;
			}
 
			if (i == m || mp[r[i + 1]] < 10 || mp[r[i + 1]] != mp[r[i]])
			{
				for (R int j = 0; j <= lim; ++j)
				{
					R int *gij = g[tot][j], *gij1 = g[tot ^ 1][j], *fij = f[j];
					for (R int S = 0; S < 16; ++S)
						gij[S] = (gij1[S] + fij[S]) % mod;
				}
			}
		}
		for (R int i = 0; i <= lim; ++i) for (R int S = 0; S < 16; ++S) (aans[m][i] += g[tot][i][S]) %= mod;
		}
		R int ans = 0;
		for (R int i = 0; i <= lim && i <= n; ++i)
		{
			R int Cp = 1ll * pw[n] * inp[n - i] % mod;
			ans = (ans + 1ll * aans[m][i] * Cp) % mod;
		}
		printf("%d\n", ans);
	}
	return 0;
}
上一篇:2020-10-18


下一篇:hash-白兔的字符串