第十届蓝桥杯决赛

c++b组国二，cai是原罪。

第一题：计算一个数列数列包含三个数：2019的平方，x^2，y^2 求x+y

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int x = 2019 * 2019;
 6     for(int i = 2010; ; ++i)
 7     {
 8         for(int j = i + 1;j <= 10000; ++j)
 9         {
10             if(i * i - x == j * j - i * i)
11             {
12                 printf("%d
",i+j);
13                 return 0;
14             }
15         }
16     }
17 }

答案：7020

第二题：计算多个小于2019质数能组成2019的方法

当时看错题了以为是两个质数就写了个1

正解就是01背包

第三题：切割一个7*7正方形看能组成多少种直角

不会

第四题：计算有100的约数的数

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int cnt;
 6     for(int i = 2; ;++i)
 7     {
 8         cnt = 0;
 9         int j;
10         for(j = 1;j <= i;++j)
11         {
12             if(i % j == 0)
13                  cnt ++;
14         }
15         if(cnt == 100)
16         {
17             cout << i << endl;
18             return 0;
19         }
20     }
21 }

答案：45360

第五题：计算小于12步回到起点，有多少种做法。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int ans;
 4 int vis[6][6];
 5 int d[4][2] = {{-1,0},{0,-1},{1,0},{0,1}};
 6 bool check(int x,int y)
 7 {
 8     return x >= 0 && x < 6 && y >= 0 && y < 6;
 9 }
10 void dfs(int step ,int x,int y)
11 {
12     if(step <= 12 && step != 0 && x == 0 && y == 0)
13     {
14         ans ++;
15         return ;
16     }
17     for(int i = 0; i < 4; ++i)
18     {
19         int dx = x + d[i][0];
20         int dy = y + d[i][1];
21         if(step == 1 && !dx && !dy)
22             continue;
23         if(check(dx,dy) && vis[dx][dy] == 0)
24         {
25             vis[dx][dy] = 1;
26             dfs(step + 1, dx , dy);
27             vis[dx][dy] = 0;
28         }
29     }
30 }
31 int main()
32 {
33     dfs(0,0,0);
34     cout << ans << endl;
35     return 0;
36 }

答案：206

第六题：给你两个字符串，看第二个字符串最少修改几次能成为第一个字符串的子串。

我一开始以为是kmp，结果写了半个小时kmp，写完结果是暴力，出了考场是dp，呵呵。

 1 #include<cstring>
 2 #include<iostream>
 3 #include<cstdio>
 4 using namespace std;
 5 char a[2007];
 6 char b[2007];
 7 int main()
 8 {
 9     cin >> a + 1;
10     cin >> b + 1;
11     int ans = -1;
12     int n = strlen(a+1);
13     int m = strlen(b+1);
14     for(int i = 1;i <= n - m + 1;++i)
15     {
16         int cnt = 0;
17         for(int j = i,k = 1; k <= m && j <= n ; ++j,++k)
18         {
19             if(a[j] == b[k])
20             {
21                 cnt ++;
22             }
23         }
24         ans = max(cnt,ans);
25     }
26     cout << m - ans << endl;
27 
28 }

第七题：

给定一些坐标上数，连接起来，看有几个拐点

1 4 2 3 就是两个拐点 n就是最大数

n = 4 就是1 2 3 4 四个数 n = 3就是 1 2 3 三个数

k就是线段数

k-1就是拐点数

我只能暴力骗分了

 1 #include<cstring>
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<vector>
 5 #include<cmath>
 6 #include<algorithm>
 7 using namespace std;
 8 int main()
 9 {
10     int n,k;
11     cin >> n >> k;
12     vector<int> v;
13     for(int i = 0;i < n;++i)
14     {
15         v.push_back(i+1);
16     }
17     int ans = 0;
18     do
19     {
20         int cnt = 0;
21         for(int i = 1;i < v.size() - 1;++i)
22         {
23             if(v[i] > v[i-1] && v[i] > v[i+1] || v[i] < v[i-1] && v[i] < v[i+1])
24             {
25                 cnt ++;
26             }
27         }
28         if(cnt == k-1)
29         {
30             ans ++;
31         }
32     }while(next_permutation(v.begin(),v.end()));
33     cout << ans << endl;
34 
35 }

第八题：给你三个环，外环12个，中环8个，内环4个，看是否能让外环都是G，中环都是R，内环都是Y。

呵呵，这个题，我bfs算了1个小时，最后交了一个玄学答案。如果队列内的元素超过一百万个，那就no，那么就是yes。（错误答案，估计能过25%）

代码就不写了，写了200多行。。。

第九题：为什么我没想到用线段树，就是看区间第八大是多少，呵呵，写暴力写多了，上来就暴力。

第十题：应该是概率dp，我直接把案例交了。

大三拿了个国二，学了这么久acm，却是这么个结果，我对不起实验室学长，对不起老师，更对不起自己。