CodeVs天梯黄金Gold题解

网友投稿 544 2022-05-28

title: CodeVs天梯之Gold

date: 2017-12-28

tags:

天梯

CodesVs

categories: OI

CodeVs天梯之Gold

2018.01.04 By gwj233

均分纸牌

#include using namespace std; const int maxn = 110; int a[maxn], sum, ans; int main(){ int n; cin>>n; for(int i = 1; i <= n; i++){ cin>>a[i]; sum += a[i]; } sum /= n; for(int i = 1; i <= n; i++){ if(a[i] != sum){ ans++; a[i+1] -= sum-a[i]; } } cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

线段覆盖

#include #include using namespace std; const int maxn = 110; int a[maxn], b[maxn], c[maxn]; bool cmp(int x, int y){ return b[x]==b[y] ? a[x]>n; for(int i = 1; i <= n; i++){ int x, y; cin>>x>>y; //输入有坑,可能先大再小 a[i]=min(x,y); b[i]=max(x,y); c[i]=i; } sort(c+1,c+n+1,cmp); int t = -999, ans = 0; for(int i = 1; i <= n; i++){ if(t <= a[c[i]]){ t = b[c[i]]; ans++; } } cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

高精度练习之减法

#include #include #include using namespace std; const int maxn = 510; int a[maxn], b[maxn], c[maxn]; int main(){ string s1, s2; cin>>s1>>s2; if(s1.size()1 && c[c[0]]==0)c[0]--; for(int i = c[0]; i >= 1; i--)cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

高精度练习之加法

#include #include #include using namespace std; const int maxn = 510; int a[maxn], b[maxn], c[maxn]; int main(){ string s1, s2; cin>>s1>>s2; a[0] = s1.size(); b[0] = s2.size(); for(int i = 1; i <= a[0]; i++)a[i] = s1[a[0]-i]-'0'; for(int i = 1; i <= b[0]; i++)b[i] = s2[b[0]-i]-'0'; c[0] = max(a[0], b[0])+1; for(int i = 1; i <= c[0]; i++){ c[i] += a[i]+b[i]; if(c[i]>=10){ c[i+1]++; c[i]%=10; } } while(c[0]>1 && c[c[0]]==0)c[0]--; for(int i = c[0]; i >= 1; i--)cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

高精度练习之乘法

#include #include #include using namespace std; const int maxn = 510; int a[maxn], b[maxn], c[maxn]; int main(){ string s1, s2; cin>>s1>>s2; a[0] = s1.size(); b[0] = s2.size(); for(int i = 1; i <= a[0]; i++)a[i] = s1[a[0]-i]-'0'; for(int i = 1; i <= b[0]; i++)b[i] = s2[b[0]-i]-'0'; c[0] = a[0]+b[0]; for(int i = 1; i <= a[0]; i++){ for(int j =1; j <= b[0]; j++){ c[i+j-1] += a[i]*b[j]; if(c[i+j-1]>=10){ c[i+j] += c[i+j-1]/10; c[i+j-1] %= 10; } } } while(c[0]>1 && c[c[0]]==0)c[0]--; for(int i = c[0]; i >= 1; i--)cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

装箱问题

//数据太水,搜索就好 #include #include using namespace std; int n, m, a[110]; int search(int i, int r){ if(i == n)return r; if(r < a[i])return search(i+1, r); return min(search(i+1,r), search(i+1,r-a[i])); } int main(){ cin>>m>>n; for(int i = 0; i < n; i++)cin>>a[i]; cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

//f[i][j],表示在选第i个物品时, 大小为j的体积能否取到 #include using namespace std; const int maxn = 20010; int n, m, a[35], f[35][maxn]; int main(){ cin>>m>>n; for(int i = 1; i <= n; i++)cin>>a[i]; f[0][0] = 1; for(int i = 1; i <= n; i++) for(int j = 0; j <= m; j++) if(f[i-1][j]){ f[i][j] = f[i-1][j]; if(j+a[i]<=m)f[i][j+a[i]] = 1; } for(int i = m; i >= 0; i--) if(f[n][i]){ cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

//f[i]表示大小为i的体积能否取到 #include using namespace std; const int maxn = 20010; int n, m, a[maxn], f[maxn]; int main(){ cin>>m>>n; for(int i = 1; i <= n; i++)cin>>a[i]; f[0] = 1; for(int i = 1; i <= n; i++) for(int j = m; j >= 0; j--) if(f[j] && j+a[i]<=m) f[j+a[i]] = 1; for(int i = m; i >= 0; i--) if(f[i]){ cout<

1

2

3

4

5

CodeVs天梯黄金Gold题解

6

7

8

9

10

11

12

13

14

15

16

17

//01背包, f[i]表示体积为i时得到的最大价值 #include using namespace std; const int maxn = 20010; int n, m, w[35], v[35], f[maxn]; int main(){ cin>>m>>n; for(int i = 1; i <= n; i++){ cin>>w[i]; v[i] = w[i]; } for(int i = 1; i <= n; i++) for(int j = m; j >= w[i]; j--) f[j] = max(f[j],f[j-w[i]]+v[i]); cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

乌龟棋

#include #include using namespace std; int n, m, a[350], num[5], f[50][50][50][50]; int main(){ cin>>n>>m; for(int i = 1; i <= n; i++)cin>>a[i]; for(int i = 1; i <= m; i++){ int x; cin>>x; num[x]++; } for(int i = 0; i <= num[1]; i++){ for(int j = 0; j <= num[2]; j++){ for(int k = 0; k <= num[3]; k++){ for(int l = 0; l <= num[4]; l++){ int t = 0; if(i)t = max(t, f[i-1][j][k][l]); if(j)t = max(t, f[i][j-1][k][l]); if(k)t = max(t, f[i][j][k-1][l]); if(l)t = max(t, f[i][j][k][l-1]); f[i][j][k][l] = t+a[i+j*2+k*3+l*4+1]; } } } } cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

拦截导弹

//LDS的个数等于LIS的长度 #include #include using namespace std; int n, a[30], f[30], ans; int main(){ while(cin>>a[n])n++; for(int i = 0; i < n; i++)f[i] = 1; for(int i = 0; i < n; i++) for(int j = 0; j < i; j++) if(a[j]>=a[i])f[i] = max(f[i], f[j]+1); for(int i = 0; i < n; i++)ans = max(ans, f[i]); cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

最长严格上升子序列

//f[i]:到i为止的LIS的长度。 //f[i]=max{1,f[j]+1|j #include using namespace std; int n, a[510], f[510], ans; int main(){ cin>>n; for(int i = 1; i <= n; i++)cin>>a[i]; for(int i = 1; i <= n; i++){ int t = 0; for(int j = 1; j < i; j++) if(a[j]

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

线段覆盖 2

//f[i]:到第i条线段为止能获得的最大价值 //f[i]=max{s[i].c,f[j]+s[i].c|j #include using namespace std; const int maxn = 1010; struct seg{ int a, b, c; }s[maxn]; bool cmp(seg a, seg b){ return a.a>n; for(int i = 1; i <= n; i++) cin>>s[i].a>>s[i].b>>s[i].c; sort(s+1,s+n+1,cmp); for(int i = 1; i <= n; i++){ f[i] = s[i].c; for(int j = 1; j < i; j++) if(s[j].b<=s[i].a)f[i] = max(f[i], f[j]+s[i].c); ans = max(ans, f[i]); } cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

石子归并

#include #include using namespace std; const int maxn = 1010, inf=0xffffff; int w[maxn], f[maxn][maxn]; int main(){ int n; cin>>n; for(int i = 1; i <= n; i++)cin>>w[i]; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) f[i][j] = i==j ? 0 : inf; for(int i = 1; i <= n; i++)w[i] += w[i-1]; //转移顺序长度从小到大覆盖即可 for(int i = n; i >= 1; i--)//枚举起点 for(int j = i; j <= n; j++)//枚举终点 for(int k = i; k <= j; k++)//枚举断点 f[i][j] = min(f[i][j],f[i][k]+f[k+1][j]+w[j]-w[i-1]); cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

//解释一下, DP题写几个版本主要看心情。。。 #include #include using namespace std; const int maxn = 1010, inf=0xffffff; int w[maxn], f[maxn][maxn]; int dp(int i, int j){ if(f[i][j] != inf)return f[i][j]; for(int k = i; k <= j; k++) f[i][j] = min(f[i][j], dp(i,k)+dp(k+1,j)+w[j]-w[i-1]); return f[i][j]; } int main(){ int n; cin>>n; for(int i = 1; i <= n; i++)cin>>w[i]; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) f[i][j] = i==j ? 0 : inf; for(int i = 1; i <= n; i++)w[i] += w[i-1]; cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

能量项链

//环形DP, 复制一份, 拆环成链,然后做区间DP(即对每条链做一遍区间DP,取最大值。) //解释一下, 注释详细度主要看心情。。。 #include #include using namespace std; const int maxn = 1010; int w[maxn], f[maxn][maxn]; int dp(int i, int j){ if(f[i][j])return f[i][j]; //注意边界, [i~i,i+1~j] and [i~j-1,j~j]; for(int k = i; k <= j-1; k++) //通过k合并后, 两颗珠子分别为[i,k],[k+1,j]其中计算能量时headi*taili*headj; f[i][j] = max(f[i][j], dp(i,k)+dp(k+1,j)+w[i]*w[k+1]*w[j+1]); return f[i][j]; } int main(){ int n; cin>>n; for(int i = 1; i <= n; i++){ cin>>w[i]; w[i+n]=w[i]; } dp(1, 2*n); int ans = 0; for(int i = 1; i <= n; i++)//扫描每条长度为n的链, 最大值为答案。 ans = max(ans, f[i][i+n-1]); cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

矩阵取数游戏

//每行独立区间DP, 贪心反例->某行像这样,4 1 1 1 1 1 233 3 3 //2^80数据, 所以记得高精. #include #include #include #include #include using namespace std; typedef long long LL; typedef __int128 LLL; const int maxn = 110; int n, m, a[maxn]; LLL t[maxn], f[maxn][maxn], _max, ans; void print(LLL ans){ if(ans == 0)return ; else print(ans/10); putchar(ans%10+'0'); } int main(){ cin>>n>>m; t[0] = 1; for(int i = 1; i <= m; i++)t[i] = t[i-1]*2; while(n--){ for(int i = 1; i <= m; i++)cin>>a[i]; memset(f, 0, sizeof f); //f[i][j]:这行还剩下[i,j]时能得到的最高分 //转移加上分别取了左边的和右边的数的时候的得分 //转移顺序,区间从大到小。 for(int i = 1; i <= m; i++) for(int j = m; j >= i; j--) f[i][j]=max(f[i-1][j]+t[m-(j-i+1)]*a[i-1], f[i][j+1]+t[m-(j-i+1)]*a[j+1]); //枚举最后一个取的是哪个数,得到这一行的最高分 _max = 0; for(int i = 1; i <= m; i++)_max = max(_max, f[i][i]+t[m]*a[i]); ans += _max; } if(ans == 0)cout<<"0\n"; else print(ans); return 0; }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

过河卒

//填表法 #include using namespace std; int n, m, x, y, a[20][20], f[20][20]; int main(){ cin>>n>>m>>x>>y; x++;y++;n++;m++;//+1方便赋初始值 //9 points could'n be find a[x][y] = 1; a[x-1][y-2] = a[x-1][y+2] = a[x+1][y-2] = a[x+1][y+2] = 1; a[x-2][y-1] = a[x-2][y+1] = a[x+2][y-1] = a[x+2][y+1] = 1; f[0][1] = 1; //边界 for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(!a[i][j])f[i][j] = f[i-1][j]+f[i][j-1]; cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

//刷表法 #include using namespace std; int n, m, x, y, a[20][20], f[20][20]; int main(){ cin>>n>>m>>x>>y; a[x][y] = 1; a[x-1][y-2] = a[x-1][y+2] = a[x+1][y-2] = a[x+1][y+2] = 1; a[x-2][y-1] = a[x-2][y+1] = a[x+2][y-1] = a[x+2][y+1] = 1; f[0][0] = 1;//初始值, 刷表时不会覆盖所以可以直接放 for(int i = 0; i <= n; i++){ for(int j = 0; j <= m; j++){ if(!a[i+1][j])f[i+1][j] += f[i][j]; if(!a[i][j+1])f[i][j+1] += f[i][j]; } } cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

传纸条

//考虑题设,找到两条不重复的路径,所以从上到下直接DP,状态四维(上往下,下往上分别DP,没办法考虑路径重叠) //f[i][j][k][l]表示分别到(i,j),(k,l)时候的最大好心值 #include #include using namespace std; int n, m, a[55][55], f[55][55][55][55]; int main(){ cin>>n>>m; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin>>a[i][j]; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) for(int k = 1; k <= n; k++) for(int l = 1; l <= m; l++) if(!(i==k&&j==l) || (i==n&&j==m&&k==n&&l==m)) f[i][j][k][l] = max(max(f[i-1][j][k-1][l], f[i][j-1][k-1][l]), max(f[i-1][j][k][l-1],f[i][j-1][k][l-1]))+a[i][j]+a[k][l]; cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

骑士游历

//bugs:行列弄反(x,y是坐标轴...)+longlong #include using namespace std; typedef long long LL; LL n, m, x1, y1, x2, y2, f[55][55]; int main(){ cin>>n>>m>>x1>>y1>>x2>>y2; f[x1][y1] = 1; for(int i = x1+1; i <= x2; i++)//避免覆盖掉x1,y1时候的1种方案 for(int j = 1; j <= n; j++)//因为日字,所以要全 f[i][j] = f[i-1][j-2]+f[i-1][j+2]+f[i-2][j-1]+f[i-2][j+1]; cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

//行列式反的,,, #include using namespace std; typedef long long LL; LL n, m, x1, y1, x2, y2, f[55][55]; int main(){ cin>>n>>m>>x1>>y1>>x2>>y2; f[y1][x1] = 1; //转移的时候按照列每层去取(因为只能往右走) for(int i = x1; i <= x2; i++){//枚举y for(int j = 1; j <= m; j++){//枚举x //之前的状态无法到达那么当前状态也无法到达 if(!f[j][i])continue; //刷表状态转移 f[j+1][i+2] += f[j][i]; f[j-1][i+2] += f[j][i]; f[j+2][i+1] += f[j][i]; f[j-2][i+1] += f[j][i]; } } cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

数字三角形

//f[i][j]:从(i,j)出发能获得的最大值 _裸DFS #include #include using namespace std; int n, a[110][110], f[110][110]; int dfs(int i, int j){ if(f[i][j])return f[i][j]; if(i>n || j>n)return 0; return f[i][j] = max(dfs(i+1,j),dfs(i+1,j+1))+a[i][j]; } int main(){ cin>>n; for(int i = 1; i <= n; i++) for(int j = 1; j <= i; j++) cin>>a[i][j]; cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

//f[i][j]:从(i,j)出发能获得的最大值 _裸递推 #include #include using namespace std; int n, a[110][110], f[110][110]; int main(){ cin>>n; for(int i = 1; i <= n; i++) for(int j = 1; j <= i; j++) cin>>a[i][j]; for(int i = n; i >= 1; i--) for(int j = 1; j <= i; j++) f[i][j] = max(f[i+1][j], f[i+1][j+1])+a[i][j]; cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

//f[i][j]:从(1,1)到(i,j)能获得的最大值 _裸递推 #include #include using namespace std; int n, a[110][110], f[110][110]; int main(){ cin>>n; for(int i = 1; i <= n; i++) for(int j = 1; j <= i; j++) cin>>a[i][j]; for(int i = 1; i <= n; i++) for(int j = 1; j <= i; j++) f[i][j] = max(f[i-1][j], f[i-1][j-1])+a[i][j]; int ans = -0xffffff; for(int i = 1; i <= n; i++)ans = max(ans, f[n][i]); cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

//f[i][j]:从(i,j)出发能获得的最大值 _滚动数组 #include #include using namespace std; int n, a[110][110], f[2][110]; int main(){ cin>>n; for(int i = 1; i <= n; i++) for(int j = 1; j <= i; j++) cin>>a[i][j]; for(int i = n; i >= 1; i--) for(int j = 1; j <= i; j++) f[i%2][j] = max(f[(i+1)%2][j], f[(i+1)%2][j+1])+a[i][j]; cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

//f[i][j]:从(1,1)到(i,j)能获得的最大值 _滚动数组2 #include #include using namespace std; int n, a, f[2][110]; int main(){ cin>>n; for(int i = 1; i <= n; i++){ for(int j = 1; j <= i; j++){ cin>>a; f[i%2][j] = max(f[(i-1)%2][j], f[(i-1)%2][j-1])+a; } } int ans = -0xffffff; for(int i = 1; i <= n; i++)ans = max(ans, f[n%2][i]); cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

乘积最大

//f[i][j]:前i位数包含j个乘号时能获得的最大值 //转移,枚举每个乘号的位置即可,O(n^3)可过。 #include #include #include using namespace std; typedef long long LL; int n, m; LL f[110][110]; string s; LL mid(int l, int r){ LL t = 0; for(int i = l; i <= r; i++) t = t*10+s[i-1]-'0';//第i位在s[i-1]; return t; } int main(){ cin>>n>>m>>s; for(int i = 1; i <= n; i++)f[i][0] = mid(1,i);//边界条件,没有乘号 for(int i = 1; i <= n; i++) //枚举前i位数 for(int j = 1; j <= min(m,i-1); j++)//枚举每个乘号(即子状态) for(int k = j; k < i; k++)//枚举该乘号的位置,乘号放后面(保证第j个乘号时, 前j-1个乘号的最优状态已经算出来了) f[i][j] = max(f[i][j], f[k][j-1]*mid(k+1,i)); cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

数的划分

//step1:把n个苹果放到m个盘子里,不允许有空盘。等价于每个盘子放一个苹果先允许有空盘 //step2:f[i][j]表示i个苹果j个盘子的放法数目 //step3:转移,j>i时,去掉空盘不影响结果; j<=i时,对盘子是否空着分类讨论; #include using namespace std; int n, m, f[210][10]; int main(){ cin>>n>>m; n-=m;//每个盘子先放一个苹果就不会有空盘了。。。 for(int i = 0; i <= n; i++)f[0][i]=f[i][1]=1; for(int i = 1; i <= n; i++) for(int j = 2; j <= m; j++) f[i][j] = j>i?f[i][i]:f[i][j-1]+f[i-j][j];//所有盘子有苹果时每个盘子都去掉一个苹果不影响结果 cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

//Step1:f[i][j]:将i这个整数划分成j份且不重复的方法数 //Step2:因为划分成的每一份至少为1,所以我们把它每份减去1 //Step3:将i这个数划分成j份等价于将i-j这个数划分成1份、2份、3份。。。j份的和 //Step4:f[i-1][j-1]=f[(i-1)-(j-1)][1]+...+f[(i-1)-(j-1)][j-1]; 代入化简 #include #include using namespace std; int n, k, f[210][10]; int main(){ cin>>n>>k; f[0][0] = 1; for(int i = 1; i <= n; i++) for(int j = 1; j <= min(i,k); j++) f[i][j] = f[i-j][j]+f[i-1][j-1]; cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

统计单词个数

//just for test4 #include #include #include #include using namespace std; int n, m, x, d[210], f[210][50];//c[210][210]; string s, w[20]; void pre(){ memset(d, 0x3f, sizeof d); for(int i = 1; i <= s.size(); i++){//枚举每个字母 for(int j = 1; j <= x; j++){//枚举每个单词 if(s.substr(i).find(w[j])==0){//如果存在i字母开头的单词 d[i] = min(d[i], i+(int)w[j].size()-1); } } } } int main(){ int T; cin>>T; while(T--){ //input cin>>n>>m; s = " "; for(int i = 1; i <= n; i++){ string t; cin>>t; s += t; } n *= 20; cin>>x; for(int i = 1; i <= x; i++)cin>>w[i]; //预处理1:得到c[i][j]为[i,j]中的最大单词数 //预处理2:得到d[i]为字母i开头的最短单词的结束位置(小贪心,每个字母只能按照第一个字母取一次) pre(); //dp:f[i][j]为前i个字母划分成j段能得到的最大单词数 //转移:f[i][j] = max{ f[k][j-1]+c[k+1][i] | k>=j&&k= j; k--){ //逆序覆盖 if(d[k]<=i)w++; //w=[k,i] f[i][j] = max(f[i][j],f[k-1][j-1]+w); //f[i][j] = max(f[i][j], f[k][j-1]+w); //if(d[k]<=i)w++; //w=[k+1,i] } } } cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

四子连棋

//思路:把空白当棋,交替黑白走。 //实现:BFS, 打表判断是否成立 #include #include #include #include using namespace std; string s; struct node{ string ma; int step; char next; node(string x, int y, char ch):ma(x),step(y),next(ch){} }; queueq; int dz[] = {4,-4,1,-1}; char change(char ch){ if(ch == 'B')return 'W'; if(ch == 'W')return 'B'; } int check(string s){ //check diagonal 1 if(s[0]==s[5] && s[5]==s[10] && s[10]==s[15])return 1; //check diagonal 2 if(s[3]==s[6] && s[6]==s[9] && s[9]==s[12])return 1; //check row for(int i = 0; i < 4; i++){ int ok = 1, t = 4*i; for(int j = 0; j < 4; j++) if(s[t] != s[t+j])ok = 0; if(ok)return 1; } //check col for(int i = 0; i < 4; i++){ int ok = 1, t = i; for(int j = 0; j < 4; j++) if(s[t] != s[t+j*4])ok = 0; if(ok)return 1; } return 0; } int bfs(){ while(q.size()){ string t = q.front().ma; int st = q.front().step; char ch = q.front().next; q.pop(); //check if(check(t))return st; //find O int o1=-1, o2; for(int i = 0; i < 16; i++){ if(t[i]=='O'){ if(o1==-1)o1 = i; else o2 = i; } } //o1go for(int i = 0; i < 4; i++){ if(dz[i]==1 && o1%4==3)continue; if(dz[i]==-1 && o1%4==0)continue; int nz = o1+dz[i]; if(nz>=0 && nz<16 && t[nz]==ch){ string nt = t; swap(nt[o1],nt[nz]); q.push(node(nt,st+1,change(ch))); } } //o2go for(int i = 0; i < 4; i++){ if(dz[i]==1 && o2%4==3)continue; if(dz[i]==-1 && o2%4==0)continue; int nz = o2+dz[i]; if(nz>=0 && nz<16 && t[nz]==ch){ string nt = t; swap(nt[o2],nt[nz]); q.push(node(nt,st+1,change(ch))); } } } } int main(){ ios::sync_with_stdio(false); for(int i = 0; i < 4; i++){ string t; cin>>t; s += t; } if(check(s)){ cout<<"0"; return 0;} int ans = 0xffffff; q.push(node(s,0,'W')); ans = min(ans, bfs()); while(q.size())q.pop(); q.push(node(s,0,'B')); ans = min(ans, bfs()); cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

逃跑的拉尔夫

#include #include #include//set判重防MLE using namespace std; const int dx[4] = {-1, 0, 1, 0}; const int dy[4] = {0, 1, 0, -1}; int r, c, c1, r1, n, go[1010]; char a[55][55]; struct node{ int x, y, step; node(int x, int y, int step):x(x),y(y),step(step){} }; queueq; sets; bool inside(int x, int y){ return (x=0 && y=0 && a[x][y]!='X'); } int togo(char ch){ if(ch == 'N')return 0; if(ch == 'E')return 1; if(ch == 'S')return 2; if(ch == 'W')return 3; } void bfs(){ q.push(node(r1, c1, 0)); while(q.size()){ node t = q.front(); q.pop(); if(t.step == n)a[t.x][t.y] = '*'; int tt=go[t.step], nx=t.x+dx[tt], ny=t.y+dy[tt]; while(inside(nx,ny)){ int ok = nx*1000000+ny*10000+t.step+1; if(!s.count(ok)){ q.push(node(nx,ny,t.step+1)); s.insert(ok); } nx += dx[tt], ny += dy[tt]; } } return ; } int main(){ scanf("%d%d", &r, &c); for(int i = 0; i < r; i++)scanf("%s", a[i]); for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) if(a[i][j] == '*'){ r1 = i; c1 = j; break;} a[r1][c1] = '.'; scanf("%d",&n); for(int i= 0; i < n; i++){ char t[10]; scanf("%s", t); go[i] = togo(t[0]); } bfs(); for(int i = 0; i < r; i++)printf("%s\n", a[i]); return 0; }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

字串变换

//思路就是对于每个状态下的字符串,枚举可以替换的部分替换作为下一个新的状态。 #include #include #include #include using namespace std; int n = 1, flag; string a, b, ai[1010], bi[1010]; queueq; mapma;//map判重防MLE int main(){ cin>>a>>b; while(cin>>ai[n]>>bi[n])n++; q.push(a); ma[a] = 0; while(q.size()){ string t = q.front(); q.pop(); if(t == b){ flag = 1; break; } if(ma[t]>10)break; //如果没有这层循环的话,就只能找到第一个子串,后面的会被忽略,如abaaaba abcdaba for(int j = 0; j < t.size(); j++){ string nt = t.substr(j); for(int i = 1; i < n; i++){ int tt = nt.find(ai[i]); if(tt == string::npos)continue; tt += j; //边界条件调起来很麻烦,以及最后直接+j就好了 string ttt = t.substr(0,tt)+bi[i]+t.substr(tt+ai[i].size()); if(!ma.count(ttt)){ ma[ttt] = ma[t]+1; q.push(ttt); } } } } if(flag)cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

#include #include #include #include //set判重 #define maxn 1010 using namespace std; string ai[maxn],bi[maxn]; struct node{ string str; int st; node(string a, int b):str(a),st(b){} }; sets; int ans; int main(){ string a, b; cin>>a>>b; int n = 1; while(cin>>ai[n]>>bi[n])n++; queueq; q.push(node(a,0)); while(q.size()){ node t = q.front(); q.pop(); if(t.str == b){ ans = t.st; break;} if(t.st > 10){ ans = 20; break; } for(int j = 0; j < t.str.size(); j++){ string nt = t.str.substr(j); for(int i = 1; i < n; i++){ int tt = nt.find(ai[i]); if(tt==string::npos)continue; tt += j; string ttt = t.str.substr(0,tt)+bi[i]+t.str.substr(tt+ai[i].size()); if(!s.count(ttt)){ q.push(node(ttt,t.st+1)); s.insert(ttt); } } } } //如果<10就因为找不到出来也是不成立的, 即ans没有被赋过值的话 if(ans == 20 || ans == 0)cout<<"NO ANSWER!\n"; else cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

单词接龙

//直接搜索就好啦,几乎没什么技巧,就是状态建模会有点难想到(应该有多种) //包含的情况可以证明是不需要考虑的,因为包含后一定不会比不包含要来的长 #include #include #include using namespace std; const int maxn = 30; int n, ans, used[maxn]; string w[maxn]; //找到a的末尾与b的前端重复的子串并返回其长度 int find(string a, string b){ int mm = min(a.size(), b.size()); for(int i = 1; i <= mm; i++) if(a.substr(a.size()-i)==b.substr(0,i)) return i; return 0; } //深度优先搜索寻找解, 状态:s为当前字符串 void dfs(string s){ ans = max(ans, (int)s.size()); for(int i = 1; i <= n; i++)if(used[i]<2){ int t = find(s, w[i]); if(t == s.size() && s!=w[0])continue;//包含关系 if(t){ used[i]++; dfs(s.substr(0,s.size()-t)+w[i]); used[i]--; } } } int main(){ cin>>n; for(int i = 1; i <= n; i++)cin>>w[i]; cin>>w[0]; dfs(w[0]); cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

四色问题

//尝试填每个点每种颜色填过去就好啦 #include using namespace std; int n, e[10][10]; int c[10], ans; void dfs(int cur){ if(cur == n)ans++; else for(int i = 0; i < 4; i++){ c[cur] = i; bool ok = true; for(int j = 0; j < cur; j++)//判断和前面的点有没有冲突 if(e[j][cur] && c[j]==c[cur])//如果联通且同色那就翻车 { ok = false; break; } if(ok){ dfs(cur+1); } } } int main(){ cin>>n; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) cin>>e[i][j]; dfs(0); cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

全排列

#include using namespace std; int n, c[20]; void dfs(int cur){ if(cur == n){ for(int i = 0; i < n; i++)cout<>n; dfs(0); return 0; }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

N皇后问题

//c[i]:第i行的皇后放在第几列 #include using namespace std; int n, c[20], ans; void dfs(int cur){ if(cur > n)ans++; else for(int i = 1; i <= n; i++){ int ok = 1; for(int j = 1; j < cur; j++) if(c[j]==i || c[j]-j==i-cur || c[j]+j==i+cur) { ok = 0; break; } if(ok){ c[cur] = i; dfs(cur+1); } } } int main(){ cin>>n; dfs(1); cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

AI 云硬盘 EVS

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:原来类加载器这么简单,手把手教你用纯java代码实现热部署
下一篇:windows宿主机ssh连接vmware ubuntu虚拟机
相关文章