今天的比赛题目不是特别简单，但是也有3题是水题系列，另外的三题学的比较努力的同学一定都见过原题，没有3题的同学自己面壁去，比赛连接在这里点击打开链接
A：按照题目的题意去找这样的约数就行了，可以循环去找，也可以拿一个vector之类的东西去存，每一份数据花的时间是C*C*B+A，还要乘上一个数据的份数，所以最坏的情况会爆int，所以拿long long 去存
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ll n,m,k;
vector<ll>v;
while(cin>>n>>m>>k){
v.clear();
for(ll i = 1;i*i <= k;i++){
if(k%i == 0) v.push_back(i);
if(k%i == 0&&i*i!=k) v.push_back(k/i);
}
sort(v.begin(),v.end());
int minn = (v[0]*v[0]*m+n)*(k/v[0]),mi = 0;
for(ll i = 0;i < v.size();i++){
ll x = (v[i]*v[i]*m+n)*(k/v[i]);
if(minn > x) minn = x,mi = i;
}
printf("%lld\n",v[mi]);
}
return 0;
}
B：在草稿本上可以写一写，发现每个最终陷入死循环的数在某一次执行函数的时候会出现89这个东西（当然也可以是其他的数字，总之是一个会陷入死循环的数就行了），其实会出现的很快，就最多循环15次左右就会出现，具体做法见代码：
#include <bits/stdc++.h>
using namespace std;
int fun(int n){
int sum = 0;
while(n>0){
sum += (n%10)*(n%10);
n /= 10;
}
return sum;
}
int main(){
int n;
while(cin>>n){
while(1){
if(fun(n) == 1) {puts("YES");break;}
else if(fun(n) == 89) {puts("NO");break;}
n = fun(n);
}
}
return 0;
}
C：这套题里面比较难的两个题之一，但是出现在寒假训练的kuangbin带你飞专题里，题目说了要去找最少的步数，那么很容易想到用bfs来做这道题目，需要注意的是当n>k时，只能一直往后一步一步走，直接输出n-k即可
#include <bits/stdc++.h>
using namespace std;
bool vis[100005];
int step[100005];
queue <int>q;
int bfs(int n,int k){
int head,next;
q.push(n);
vis[n] = true;
while(!q.empty()){
head = q.front();
q.pop();
for(int i = 0;i < 3;i++){
if(i == 0) next = head+1;
else if(i == 1) next = head-1;
else next = head*2;
if(next < 0||next > 100000) continue;
if(!vis[next]){
q.push(next);
step[next] = step[head]+1;
vis[next] = true;
}
if(next == k) return step[next];
}
}
return -1;
}
int main(){
int n,k;
while(cin>>n>>k){
memset(vis,false,sizeof(vis));
memset(step,0,sizeof(step));
while(!q.empty()) q.pop();
if(n >= k) cout<<n-k<<endl;
else cout<<bfs(n,k)<<endl;
}
return 0;
}
D：大家是不是觉得这道题似曾相似呢？对，没有错，这道题就是新生赛决赛的那道dp题，也是我的原创题，之前大一大二的同学没有人做出来，今天把这道题又重新拿出来给大家写 ，不知道还有多少人有印象。一道很基础的动态规划，只是需要注意的是有负数，初始化dp的时候需要赋值一个1e6左右的负数，然后写出状态转移方程dp[i][j] =max(dp[i][j-1],dp[i-1][j],max(dp[i][k1],dp[i][k2],...,dp[i][kn])j%ki == 0) 就可以了
#include <bits/stdc++.h>
using namespace std;
int main(){
int t,n,m;
int num[35][105];
int dp[35][105];
while(~scanf("%d%d",&n,&m)){
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
scanf("%d",&num[i][j]);
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
if(num[i][j] < 0) num[i][j]*=2;
for(int i = 0;i <= n;i++)
for(int j = 0;j <= m;j++)
dp[i][j] = -10000000;
dp[1][1] = num[1][1];
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
for(int k = 1;k < j;k++){
if(j%k == 0){
dp[i][j] = max(dp[i][j],dp[i][k]+num[i][j]);
}
}
dp[i][j] = max(max(dp[i][j],dp[i][j-1]+num[i][j]),dp[i-1][j]+num[i][j]);
}
}
printf("%d\n",dp[n][m]);
}
return 0;
}
E：又是一道原题，就是上一次博弈论算法讲堂讲的一道尼姆博弈的例题吗，甚至都没有涉及sg函数，这都做不出来，可以去面壁了
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,a[105],ans,cot;
while(cin>>n){
ans = 0;
cot = 0;
memset(a,0,sizeof(a));
for(int i = 0;i < n;i++){
cin>>a[i];
ans^=a[i];
}
if(ans == 0) puts("0");
else{
for(int i = 0;i < n;i++){
int k = ans^a[i];
if(k < a[i]) cot++;
}
cout<<cot<<endl;
}
}
return 0;
}
F：其实这道题才是全场最水的题目，只要理解了题意就可以很快的AC掉它啦，注意一下时间最多看90分钟，循环一遍去找连续的无聊时间就可以了
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
int v[100];
int main()
{
int n;
while(~scanf("%d",&n))
{
memset(v,0,sizeof(v));
for(int i=1; i<=n; i++)
{
int x;
scanf("%d",&x);
v[x]=1;
}
int now=0,sum=0;
for(int i=1; i<=90; i++)
{
sum++;
if(v[i])now=0;
else now++;
if(now==15)
{
break;
}
}
printf("%d\n",sum);
}
return 0;
}