反正都是原题，不设密码没什么大不了的

T1

黑白棋游戏

描述

一个 4 × 4 的 0/1 矩阵

每次可以交换相邻两个元素

求从初始状态到目标状态的最小交换次数

输入

前四行,每行一个长为 4 的 0/1 字符串,描述初始状态

后四行,每行一个长为 4 的 0/1 字符串,描述目标状态

输出

一行一个数,表示最小交换次数

样例

.in 1111 0000 1110 0010 1010 0101 1010 0101 1.5 .out 4

好像见过这题的强化版

https://www.luogu.org/problem/show?pid=1225 .
可以用状压哈希+搜索（就16个格子可以蛤希成int）

搜索的局面最多12870个，不怕超时

最好用位运算优化一下废话

代码蒯上

#include<iostream> #include<iomanip> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; inline int gotcha() { register int _a=0;bool _b=1;register char _c=getchar(); while(_c<'0' || _c>'9'){if(_c=='-')_b=0;_c=getchar();} while(_c>='0' && _c<='9')_a=_a*10+_c-48,_c=getchar(); return _b?_a:-_a; } using namespace std; int bit[16],h[2][65537],step[2][65537],he[2]={0},ta[2],st,tar,s; bool ed[2][65537]={0}; void BFS(int x) { register int i,num=h[x][++he[x]],n; for(i=15;i>=0;i--) { if(i%4!=0) { int a=num&bit[i],b=num&bit[i-1]; n=num+(a>>1)-a+(b<<1)-b; if(ed[x][n]==0) { h[x][++ta[x]]=n; ed[x][n]=1; step[x][n]=step[x][num]+1; } } if(ed[0][n] && ed[1][n])printf("%d",step[0][n]+step[1][n]),exit(0); if(i>=4) { int a=num&bit[i],b=num&bit[i-4]; n=num+(a>>4)-a+(b<<4)-b; if(ed[x][n]==0) { h[x][++ta[x]]=n; ed[x][n]=1; step[x][n]=step[x][num]+1; } } if(ed[0][n] && ed[1][n])printf("%d",step[0][n]+step[1][n]),exit(0); } } int main() { register int i;bit[0]=1; for(i=1;i<=15;i++)bit[i]=bit[i-1]<<1; for(i=15;i>=0;i--)scanf("%1d",&s),st+=s<<i; for(i=15;i>=0;i--)scanf("%1d",&s),tar+=s<<i; ta[0]=ta[1]=1; h[0][1]=st,h[1][1]=tar,ed[0][st]=1,ed[1][tar]=1; while(he[0]<ta[0] && he[1]<ta[1])BFS(0),BFS(1); return 0; }

T2

王八棋

描述

n 个格子,每个格子上有个分数

m 张牌,每张牌上面一个 1 到 4 的整数

王八初始时在 1 号格子,每次你可以使用一张牌,使王八前进这张牌上的数字这么多个格子

一张牌只能用一次

总得分为王八到达的所有格子的分数和

求最大化总得分

n ≤ 350, m ≤ 120 ,每种牌的数目不超过 40 ,保证所有的牌用完后,王八停在 n 号格子

输入

输入文件的每行中两个数之间用一个空格隔开

第 1 行 2 个正整数 n 和 M ,分别表示棋盘格子数和爬行卡片数

第 2 行 n 个非负整数,a_1, a_2, ..., a_n,其中 a i 表示棋盘第 i 个格子上的分数

第 3 行 m 个整数,b_1, b_2, ..., b_m,表示 m 张爬行卡片上的数字

输入数据保证到达终点时刚好用光 m 张爬行卡片,即$ n-1=∑ mi=1 b i $

输出

输出只有 1 行,1 个整数,表示最多能得到的分数

样例

.in 9 5 6 10 14 2 8 8 18 5 17 1 3 1 2 1 2.5 .out 73

这特么不是一DP题么

怎么跑这里来了

就4种牌，开个4维数组DP水过

不过要注意转移时可能会溢出

代码蒯上

#include<iostream> #include<iomanip> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; inline int gotcha() { register int _a=0;bool _b=1;register char _c=getchar(); while(_c<'0' || _c>'9'){if(_c=='-')_b=0;_c=getchar();} while(_c>='0' && _c<='9')_a=_a*10+_c-48,_c=getchar(); return _b?_a:-_a; } const int _ = 50; int DP[_][_][_][_]={0},m,n,card[5]={0},maps[_*8]={0}; int main() { memset(DP,0,sizeof(DP)); register int i,j,k,l; n=gotcha(),m=gotcha(); for(i=1;i<=n;i++)maps[i]=gotcha(); for(i=1;i<=m;i++)card[gotcha()]++; for(i=0;i<=card[1];i++) for(j=0;j<=card[2];j++) for(k=0;k<=card[3];k++) for(l=0;l<=card[4];l++) if(i+j*2+k*3+l*4+1<=n) DP[i+5][j+5][k+5][l+5]=max(max(DP[i+4][j+5][k+5][l+5],DP[i+5][j+4][k+5][l+5]),max(DP[i+5][j+5][k+4][l+5],DP[i+5][j+5][k+5][l+4]))+maps[i+j*2+k*3+l*4+1]; printf("%d",DP[card[1]+5][card[2]+5][card[3]+5][card[4]+5]); return 0; }

T3

CF-177-A

描述

满足以下条件的字符串:

1. 包含恰好 k 个不同字符
2. 长度为 n
3. 相邻两个字符不同

   如果存在多个,请输出字典序最小的

   不存在的话输出-1

   n ≤ 10 6 , k ≤ 26

输入

一行两个数 n, k

输出格式

一个长度为 n 的字符串

样例输入

.in 7 4 .out ababacd

这是一道贪心题

加粗部分是出题人蒯题目没有蒯完的地方

考试时并没有看到，所以代码就变成了这样……

#include<iostream> #include<iomanip> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; inline int gotcha() { register int _a=0;bool _b=1;register char _c=getchar(); while(_c<'0' || _c>'9'){if(_c=='-')_b=0;_c=getchar();} while(_c>='0' && _c<='9')_a=_a*10+_c-48,_c=getchar(); return _b?_a:-_a; } int n,lim; int main() { register int i,j; n=gotcha(),lim=gotcha(); if(lim>n){puts("Fuck you");return 0;} if(lim==1){puts(n==1?"a":"Fuck you");return 0;} else if(lim==2)for(i=1;i<=n;i++)putchar(i%2?'a':'b'); else { for(i=1;i<=n-lim+2;i++)putchar(i%2?'a':'b');j='c'; for(i=n-lim+3;i<=n;i++)putchar(char(j)),j++; } return 0; }

T4

虫食算

描述

给定一个用字母代替的加法等式

AB+BA=CC → 12+21=33

保证唯一解,求之。所有数字为 n 进制数,且加法为 n 进制下的加法

n ≤ 26

输入

包含 4 行. 第一行有一个正整数 n ≤ 26

后面的 3 行每行有一个由大写字母组成的字符串,分别代表两个加数以及和。这 3 个字符串 左右两端都没有空格,从高位到低位,并且恰好有 n 位

输出

包含一行。在这一行中,应当包含唯一的那组解。解是这样表示的:输出 n 个数字,分别表示A,B,C......所代表的数字,相邻的两个数字用一个空格隔开,不能有多余的空格

样例

.in 4 BADC CBDA DCCC .out 0 1 2 3

这就是真的一道原题了

要注意，这是K进制加法

并且要从后（右）往前（左）搜，可以使触发剪枝的概率变高

代码蒯上

#include<iostream> #include<iomanip> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; const int _ = 28; int n,l[_],r[_],sum[_],ans[_]; bool ed[_]={0}; void DFS(int x,int y,int up) { int i,a,b,c,all; if(!x){for(i=0;i<n;i++)printf("%d ",ans[i]);exit(0);} for(i=1;i<=x;i++) { a=ans[l[i]],b=ans[r[i]],c=ans[sum[i]]; if(a!=-1 && b!=-1 && c!=-1 && ((a+b+1)%n!=c && (a+b)%n!=c))return; } if(y==1) { if(ans[l[x]]>-1){DFS(x,2,up);return;} for(i=0;i<n;i++) if(!ed[i])ans[l[x]]=i,ed[i]=1,DFS(x,2,up),ans[l[x]]=-1,ed[i]=0; return; } a=ans[l[x]],b=ans[r[x]],c=ans[sum[x]]; if(b>-1) { all=a+b+up; if(c==-1) { ans[sum[x]]=all%n,ed[ans[sum[x]]]=1;DFS(x-1,1,all/n); ans[sum[x]]=-1,ed[all%n]=0; return; } if(all%n==c)DFS(x-1,1,all/n); return; } for(i=n-1;i>=0;i--) if(!ed[i]) { all=a+i+up; if((all%n!=c&&c>-1)||(c==-1&&ed[all%n]))continue; if(c==-1)ed[all%n]=1,ans[sum[x]]=all%n; ans[r[x]]=i,ed[i]=1,DFS(x-1,1,all/n),ans[r[x]]=-1,ed[i]=0; if(c==-1)ed[all%n]=0,ans[sum[x]]=-1; } } char s[_]; int main() { memset(ans,-1,sizeof(ans)); register int i; scanf("%d",&n); scanf("%s",s);for(i=1;i<=n;i++)l[i]=s[i-1]-'A'; scanf("%s",s);for(i=1;i<=n;i++)r[i]=s[i-1]-'A'; scanf("%s",s);for(i=1;i<=n;i++)sum[i]=s[i-1]-'A'; DFS(n,1,0); return 0; }

T5

单词矩阵

描述

把 A 到 Y 的排列从上到下从左至右依次填入一个 5 × 5 的矩阵

如果每行每列都递增,则称这个排列是优美的

任务 1 :给定一个优美的排列,求这个排列是第几个优美的排列

任务 2 :给定 k ,求第 k 个优美排列

输入

第一行一个字母,W 表示任务 1,N 表示任务 2

若是任务 1,第二行是一个优美的排列,否则第二行是一个正整数,表示某个优美的排列的编 号,保证该数不超过优美的排列的总数

输出

一行,若是任务 1,输出对应编号,否则输出对应的优美的排列

样例

.in W ABCDEFGHIJKLMNOPQRSUTVWXY .out 2

全场爆零之殇

这一题竟然也是搜索

按字典序搜索排列

位运算优化:S&(-(1<<t)) :删去集合 S 中小于 t 的所有元素

剪枝:

1. (i, j) 右下角的字符一定都比 (i, j) 的大
2. 如果大于当前字符的数目填不满右下角这个区域,无解

想象这是题目的所有解。

▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉ 

我们可以预处理打表，把一些特定的地方的解求出来。

比如像这样

▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉ ________________________________________________________________________

(我暂时找不到向上箭头，先用这个代替一下)

然后就可以在一个比原来小的多的区域求解了

没有可用的较好的代码

T6

CF-54-E

题目描述

给定一个(可能)不成立的等式:a+b=c ,要求插入尽量少的数字使得这个等式成立

2+4=5 ⇒ 21+4=25

1+1=3 ⇒ 1+31=32

保证 a, b, c 不存在前导零,要求插入后的等式中的三个数不允许存在前导零

a,b,c < 10^6

输入

仅一行 a+b=c

输出格式

一行表示成立的等式

样例

.in 1+1=3 .out 1+31=32

为方便处理进位,从低位往高位搜

答案上界:12 位

结论:

1. 如果当前搜素的最低位是合法的,就不需添加
2. 如果不合法,则 只添加一个数位
3. 枚举在哪里添加

   还可以加上一些最优化剪枝

不是标程：这个代码的得分是90。

错误原因是：没有SPJ。

// This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=100001; const int INF=1e9; const int K=13; lol a,b,c,sa,sb,d[K]; int gl=K; void dfs(lol a,lol b,lol c,lol ga,lol gb,lol gc,int l,int p){ if(l>=gl)return; if(!a&&!b&&!c&&!gc){sa=ga;sb=gb;gl=l;return;} if(!c){ int k=0; for(lol tmp=a+b+gc;tmp;tmp/=10)k++; dfs(0,0,0,a*d[p]+ga,b*d[p]+gb,0,l+k,p); return; } if((a+b+gc)%10==c%10)dfs(a/10,b/10,c/10,d[p]*(a%10)+ga,d[p]*(b%10)+gb,(a%10+b%10+gc)/10,l,p+1); else{ dfs(a*10+(c+10-b%10-gc)%10,b,c,ga,gb,gc,l+1,p); dfs(a,b*10+(c+10-a%10-gc)%10,c,ga,gb,gc,l+1,p); dfs(a,b,c*10+(a+b+gc)%10,ga,gb,gc,l+1,p); } } int main(){ scanf("%lld+%lld=%lld",&a,&b,&c); d[0]=1;for(int i=1;i<K;i++)d[i]=d[i-1]*10; dfs(a,b,c,0,0,0,0,0); printf("%lld+%lld=%lld",sa,sb,sa+sb); return 0; }

T7

最大团

描述

给定一个图 tt = (V, E)

求一个点集 S ,使得对于任意 x ≠ y ∈ S ,x 和 y 都有一条边

|V | ≤ 50

输入

第一行两个数,n, m 分别表示图的点数、边数。 接下来 m 行,每行两个整数 x, y 表示一条边 x ↔ y

输出格式

输出最大团的大小以及最大团的数目

样例

.in 4 5 1 2 2 3 3 1 1 4 2 4 .out 3 2

还是一道搜索……

1. 位运算优化

2.倒着搜:

令 f i 表示后 i 个点所组成的图的最大团

从 f n 开始倒着求 f 1

在求解 f i 时,当前最优解是 best ,搜到了点 x ,且 i 到 x − 1 中选择了 k个点

若 k + f x ≤ best ,则继续搜下去不可能更新答案,剪枝

// This file is created by GuTingFeng. #include<iostream> #include<cstdlib> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<queue> #include<ctime> #include<vector> #include<stack> #include<set> #include<map> #ifdef WIN32 #define LLD "%I64d" #else #define LLD "%lld" #endif using namespace std; typedef long long LL; const int INF=2147483647; LL getint() { LL res=0,p=1; char ch=getchar(); while ((ch<'0'||ch>'9') && ch!='-') ch = getchar(); if (ch=='-') p=-1,ch=getchar(); while (ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar(); return res*p; } bool g[55][55]; int n,m,mx[55],w[55][55],ans,cnt; bool dfs(int now, int sum) { if(now==0) { if (sum==ans) { cnt++; } if (sum>ans) { ans=sum; cnt=1; return 1; } return 0; } for(int i=0;i<now;i++) { int u=w[sum][i]; if(mx[u]+sum<ans) return 0; //后面的最大团+当前最大团比ans小 int nxt=0; for(int j=i+1; j<now; j++) if(g[u][w[sum][j]]) w[sum+1][nxt++]=w[sum][j]; dfs(nxt,sum+1); } return 0; } int mxc() { ans=0; memset(mx,0,sizeof(mx)); for(int i=n-1;i>=0;i--) { int now=0; for(int j=i+1;j<n;j++) if(g[i][j]) w[1][now++]=j; dfs(now,1); mx[i]=ans; } return ans; } int main() { n=getint(); m=getint(); int i,u,v; for (i=1;i<=m;i++) { u=getint()-1; v=getint()-1; g[u][v]=g[v][u]=1; } mxc(); printf("%d %d\n",ans,cnt); return 0; }

T8

TC-572-D1L2

描述

有一个神秘的常数 K ,s 位

现在有 n 个 s 位数,告诉你每个数与 K 有多少位是相同的

判断 K 的无解、多解、唯一解,并求出唯一解(如果存在的话)

所有出现的数都允许前导零

s ≤ 9, n ≤ 50

输入

第一行两个数 n, s

接下来 n 行,每行两个数 a, b 表示 s 位数 a 与 K 有 b 位是相同的

输出

无解输出 Liar , 多解输出 Ambiguity ,唯一解则输出唯一解

样例

.in 5 4 1234 2 4321 1 1111 1 3333 2 7777 1 .out 1337

一般的搜索肯定是超时的

这里要用到双向搜索

先枚举最后 \(t=floor(s/2)\) 位,求出所有可能的后 t 位与 K 的相同位数

搜索前 s − t 位,利用 hash 判断是否存在一个“后 t 位”

没有可用的较好的代码

T9

方程的解数

描述

已知一个n元高次方程：
$ k_1x_1^{p_1} + k_2x_2^{p_2} + \cdots + k_nx_n^{p_n} = 0 $

其中：x1, x2, …,xn是未知数，k1,k2,…,kn是系数，p1,p2,…pn是指数。且方程中的所有数均为整数

求有多少组整数解

输入

文件的第 1 行包含一个整数 n

第 2 行包含一个整数 m 。第 3 行到第 n + 2 行,每行包含两个整数,分别表示 k i 和 p i 。两 个整数之间用一个空格隔开。第 3 行的数据对应 i = 1 ,第 n + 2 行的数据对应 i = n

输出

文件仅一行,包含一个整数,表示方程的整数解的个数

样例

.in 3 150 1 2 -1 2 1 2 9.5 .out 178

也是双向搜索

枚举前 3 个 x 的值,存入 Hash 表

再枚举后 3 个 x 的值,可以算出前三个的和,在 Hash 中查询这个和出现的次数

不是标程：这个代码的得分是90。

错误原因是：TLE。

// This file is created by ZouKeShen. #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAXN 3500000 //150^3 int n, m, ans; int p[20], k[20]; int res1[MAXN], rk1; int res2[MAXN], rk2; int p1[5], k1[5]; int ksm(int d,int z)//快速幂，稍微加快一点 { int res=1; for (;z>0;d*=d,z>>=1) if (z&1) res=res*d; return res; } int lv; void dfs(int i, int res, int*a, int&rk) //最后两个参数的设置可以让两组DFS共享一个函数 { if (i>lv) { a[++rk]=res; return; } for (int x=1; x<=m;++x) dfs(i+1,res+k1[i]*ksm(x,p1[i]),a,rk); } void work() { int i, j=rk2; int cnt1, cnt2; sort(res1+1, res1+rk1+1); sort(res2+1, res2+rk2+1); //这个循环中根据单调性，i不降，j不增，所以总的时间复杂度为O(n) for(i = 1; i<=rk1; ++i) { while (res1[i]+res2[j]>0&&j>0) --j; //当i, j越小，res1[i]+res2[j]越小。i增加后，j的取值应单调减小。 if(j<=0) break; if(res1[i]+res2[j] != 0)continue; cnt1=cnt2 =1; while(res1[i+1]==res1[i]&&i<rk1) ++i,++cnt1; while(res2[j-1]==res2[j]&&j>1) --j,++cnt2; ans = ans + cnt1 * cnt2; // 乘法原理 } } int main() { scanf("%d%d", &n, &m); int i; int part1=n/2, part2=(n+1)/2; //分别为下取整，上取整。 for (i=1;i<=n;++i) scanf("%d%d",k+i,p+i); for (i=1;i<=part1;++i) p1[i]=p[i],k1[i]=k[i]; lv=part1; dfs(1,0,res1,rk1); for (i=1;i<=part2;++i) p1[i]=p[i+part1],k1[i]=k[i+part1]; lv=part2; dfs(1,0,res2,rk2); work(); printf("%d\n",ans); return 0; }

转载于:https://www.cnblogs.com/finder-iot/p/7631231.html

原文链接：https://blog.csdn.net/weixin_30342827/article/details/99488470

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。