CodeVs天梯黄金Gold题解

网友投稿 527 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

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

CodeVs天梯黄金Gold题解

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虚拟机
相关文章