题目链接：
https://cn.vjudge.net/contest/229761
A题：
n个数字，两个人轮流去数字，直到剩下最后一个数字为止，第一个人希望剩下的数字最小，第二个人希望数字最大，最终数字是多少？
思路：
贪心，第一个人每次取最大的，第二个人取最小的，最后就是中间值，直接排序即可。
代码：
#include<bits/stdc++.h>
using namespace std;
int a[];
int main()
{
int n;
cin >> n;
for(int i = ; i <= n; i++)cin >> a[i];
sort(a + , a + + n);
cout<<a[(n + ) / ]<<endl;
return ;
}
B题：给出扫雷图，判断是否正确，其中 '.' 表示空的地方 *表示地雷
直接模拟即可，对每个地雷8个方向加1，最后判断一下数字和空格是否都正确
代码：
#include<bits/stdc++.h>
using namespace std;
char a[][];
int Map[][];
int dir[][] = {,,,,-,,,-,,,,-,-,,-,-};
int main()
{
int n, m;
cin >> n >> m;
for(int i = ; i < n; i++)
{
cin >> a[i];
for(int j = ; j < m; j++)
{
if(a[i][j] == '*')
{
for(int k = ; k < ; k++)
{
int x = i + dir[k][];
int y = j + dir[k][];
if(x >= && x < n && y >= && y < m)
Map[x][y]++;
}
}
}
}/*
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)cout<<Map[i][j]<<" ";
cout<<endl;
}*/
bool flag = ;
for(int i = ; i < n; i++)
{
for(int j = ; j < m; j++)
{
if(a[i][j] != '*')
{
if(a[i][j] == '.' && Map[i][j] != )
flag = ;
if(isdigit(a[i][j]) && Map[i][j] != a[i][j] - '')
flag = ;
}
}
}
if(flag)cout<<"YES\n";
else cout<<"NO\n"; return ;
}
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的情况
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b)
{
return b == ? a : gcd(b, a % b);
}
int main()
{
int T;
cin >> T;
while(T--)
{
ll p, q, b;
scanf("%lld%lld%lld", &p, &q, &b);
ll g = gcd(p, q);
p /= g;
q /= g;
bool flag = ;
while(q != )
{
g = gcd(q, b);
if(g == )
{
flag = ;//循环小数
break;
}
while(q % g == )q /= g;//需要不断的把g除掉，不然会超时
}
if(flag)printf("Finite\n");
else printf("Infinite\n");
}
return ;
}
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的写法去更新
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = + ;
int a[maxn], dp[maxn][maxn];
int main()
{
int n, q, l, r;
cin >> n;
for(int i = ; i <= n; i++)scanf("%d", &a[i]);
for(int i = ; i <= n; i++)dp[i][i] = a[i];
for(int len = ; len < n; len++)
{
for(int l = ; l + len <= n; l++)
{
int r = l + len;
dp[l][r] = dp[l][r - ] ^ dp[l + ][r];
}
}
for(int len = ; len < n; len++)
{
for(int l = ; l + len <= n; l++)
{
int r = l + len;
dp[l][r] = max(dp[l][r], max(dp[l][r - ] , dp[l + ][r]));
}
}
cin >> q;
while(q--)
{
scanf("%d%d", &l, &r);
printf("%d\n", dp[l][r]);
}
return ;
}
E留坑待补