题目链接：

https://cn.vjudge.net/contest/229761

A题：

n个数字，两个人轮流去数字，直到剩下最后一个数字为止，第一个人希望剩下的数字最小，第二个人希望数字最大，最终数字是多少？

思路：

贪心，第一个人每次取最大的，第二个人取最小的，最后就是中间值，直接排序即可。

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int a[1005];
 4 int main()
 5 {
 6     int n;
 7     cin >> n;
 8     for(int i = 1; i <= n; i++)cin >> a[i];
 9     sort(a + 1, a + 1 + n);
10     cout<<a[(n + 1) / 2]<<endl;
11     return 0;
12 }

B题：给出扫雷图，判断是否正确，其中 ‘.’ 表示空的地方　*表示地雷

直接模拟即可，对每个地雷8个方向加1，最后判断一下数字和空格是否都正确

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 char a[105][105];
 4 int Map[105][105];
 5 int dir[8][2] = {1,0,0,1,-1,0,0,-1,1,1,1,-1,-1,1,-1,-1};
 6 int main()
 7 {
 8     int n, m;
 9     cin >> n >> m;
10     for(int i = 0; i < n; i++)
11     {
12         cin >> a[i];
13         for(int j = 0; j < m; j++)
14         {
15             if(a[i][j] == '*')
16             {
17                 for(int k = 0; k < 8; k++)
18                 {
19                     int x = i + dir[k][0];
20                     int y = j + dir[k][1];
21                     if(x >= 0 && x < n && y >= 0 && y < m)
22                         Map[x][y]++;
23                 }
24             }
25         }
26     }/*
27     for(int i = 0; i < n; i++)
28     {
29         for(int j = 0; j < m; j++)cout<<Map[i][j]<<" ";
30         cout<<endl;
31     }*/
32     bool flag = 1;
33     for(int i = 0; i < n; i++)
34     {
35         for(int j = 0; j < m; j++)
36         {
37             if(a[i][j] != '*')
38             {
39                 if(a[i][j] == '.' && Map[i][j] != 0)
40                     flag = 0;
41                 if(isdigit(a[i][j]) && Map[i][j] != a[i][j] - '0')
42                     flag = 0;
43             }
44         }
45     }
46     if(flag)cout<<"YES\n";
47     else cout<<"NO\n";
48 
49     return 0;
50 }

C题：给出p，q，b，询问分数p / q在b进制下是不是循环小数

思路：

先对p和q进行约分，判断是不是循环小数的话，只要q的素因子是b的素因子。

比如在10进制中，如果最简分数p / q不是循环小数，那么q的素因子只能是2和5

所以可以对q和b求出最大公因数g，如果g为1，说明没有相同因子，说明肯定是循环小数

如果g不为1，q一直除以g，不断减小，在重复上述过程，知道q等于1为止，如果不是循环小数，不会出现gcd为1的情况

 代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll gcd(ll a, ll b)
 5 {
 6     return b == 0 ? a : gcd(b, a % b);
 7 }
 8 int main()
 9 {
10     int T;
11     cin >> T;
12     while(T--)
13     {
14         ll p, q, b;
15         scanf("%lld%lld%lld", &p, &q, &b);
16         ll g = gcd(p, q);
17         p /= g;
18         q /= g;
19         bool flag = 1;
20         while(q != 1)
21         {
22             g = gcd(q, b);
23             if(g == 1)
24             {
25                 flag = 0;//循环小数
26                 break;
27             }
28             while(q % g == 0)q /= g;//需要不断的把g除掉，不然会超时
29         }
30         if(flag)printf("Finite\n");
31         else printf("Infinite\n");
32     }
33     return 0;
34 }

 

D题：

给出q个询问，每个询问有l到r，求l-r的子序列中最大的f值

思路：做题时没想出，后来找题解发现其实很简单，就是一个规律

对于f（l , r） = f（l, r – 1）^ f（l + 1, r）

根据这个规律，就可以打表出所有的f(l, r)

dp[l][r] = max(f[l][r], f[l][r – 1], f[l +1][r])

注意更新f和dp的时候采用区间DP的写法去更新

 代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 5000 + 10;
 5 int a[maxn], dp[maxn][maxn];
 6 int main()
 7 {
 8     int n, q, l, r;
 9     cin >> n;
10     for(int i = 1; i <= n; i++)scanf("%d", &a[i]);
11     for(int i = 1; i <= n; i++)dp[i][i] = a[i];
12     for(int len = 1; len < n; len++)
13     {
14         for(int l = 1; l + len <= n; l++)
15         {
16             int r = l + len;
17             dp[l][r] = dp[l][r - 1] ^ dp[l + 1][r];
18         }
19     }
20     for(int len = 1; len < n; len++)
21     {
22         for(int l = 1; l + len <= n; l++)
23         {
24             int r = l + len;
25             dp[l][r] = max(dp[l][r], max(dp[l][r - 1] , dp[l + 1][r]));
26         }
27     }
28     cin >> q;
29     while(q--)
30     {
31         scanf("%d%d", &l, &r);
32         printf("%d\n", dp[l][r]);
33     }
34     return 0;
35 }

 

E留坑待补

 

版权声明：本文为fzl194原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/fzl194/p/9053581.html