写在前面：本次比赛共12题，比赛总体难度相比第一次比赛略有提高，但是整体难度依旧不难，本次比赛打乱了题目，题目难度随机，导致了简单题出题人数减少。本次比赛的题目难度跨度不是特别大，但是题目类型增多，由于每个人擅长的领域不同，可能对结果有一定影响。

比赛地址：https://vjudge.net/contest/284308

下面就对比赛的题目做一下简单的解答（题目方法不唯一，给出的解法仅供参考）：

神秘连接

A题     B题     C题     D题      E题      F题     G题     H题     I题     J题     K题     L题

A题

题意：

给你一个打乱的序列，求原序列。

已知原序列是从x不断操作得来的。

操作有两个一个是对前一个x/3，另外一个是×2。

也就是说每一个数就是前一个数的1/3或者两倍。

分析：

因为知道序列里面的所以数字，所以我们可以全排列所有的序列，看一下这种序列成不成立，但是这样子实在是太慢了。我们可以用dfs来减少一些判断。我们枚举每一个数字作为起始的x，对这个x进行bfs看看能不能产生符合条件的序列。我这里一开始把这个序列存入Map中，相当于普通bfs中的vis数组，来进行标记。

参考代码：

#include <cstdio>
#include <iostream>
#include <map>
typedef long long ll;
using namespace std;int n,flag=0;
ll a[105];
ll ans[105];
map<ll,int> M;void dfs(ll num,int step)
{// 出口，dfs产生序列中的数字个数到达n个if (step>=n){flag=1;for (int i=1;i<=n;i++)cout << ans[i] << " ";return;}// 如果当前x除以3的数字在剩下序列中if (num%3==0 && M.count(num/3) && M[num/3]>0){M[num/3]--; ans[step+1]=num/3;dfs(num/3,step+1);M[num/3]++;}// 如果当前x乘以2的数字在剩下序列中if (M.count(num*2) && M[num*2]>0){M[num*2]--; ans[step+1]=num*2;dfs(num*2,step+1); if (flag) return;M[num*2]++;}
}int main()
{cin >> n;for (int i=1;i<=n;i++){// 把所有数字加入Mapcin >> a[i];if (M.count(a[i]))M[a[i]]++;elseM[a[i]]=1;}// 枚举所有的起始xfor (int i=1;i<=n;i++){ans[1]=a[i];dfs(a[i],1);if (flag)break;}return 0;
}

B题

题意：

根据编码后的单词，求编码前的单词。

编码方式为不断取出一个单词的中间单词，放在新单词后面。

其中偶数长度单词的中间单词为中间偏左的那个。

分析：

需要分成两种情况。

1.长度为奇数

编码后单词的第一个字母就是原单词最中间的，然后依次是左边，右边，左边，右边的...

1.长度为偶数

编码后单词的依次是原单词左边，右边，左边，右边的...

参考代码：

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;int n;
string s,s1;int main()
{cin >> n >> s;// 长度为奇数if (n%2){// 开始的s[0]在原单词中在最中间s1=s[0];for (int i=1;i<n;i++)// 加在左边if (i%2) s1=s[i]+s1;// 加在右边else s1=s1+s[i];}// 长度为偶数，同理else{s1="";for (int i=0;i<n;i++)if (i%2==0) s1=s[i]+s1;else s1=s1+s[i];}cout << s1 << endl;return 0;
}

C题

题意：

题意很简单，注意蛋糕每块大小可以不一样。

分析：

这是道数学题，其实从数学方面考虑还是不简单的，如果换一个方面考虑可能就会好理解一点。p个人我们就把每块蛋糕切成1/p，q个人就切成1/q。然后这些是必须要切得刀数，我们可以让这些刀数尽可能的重合，那么最多的重合刀数就是gcd(p,q)

，gcd是最大公约数，于是最少刀就是p+q-gcd(p,q)。

还有一个神坑的地方！！！！，自细看题，发现他说输入是每行，所以要用多组输入。

参考代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;int p,q;int main()
{while(cin >> p >> q)cout << p+q-__gcd(p,q) << endl;return 0;
}

D题

题意：

求和1-n，如果是2的倍数不加，反而减。

分析：

先把2的倍数存到数组里，然后先求和1-n，高斯求和一下，然后把2的倍数减掉（注意一开始加了，要减两倍）。

可能会超，用long long。

参考代码：

#include <cstdio>
#include <iostream>
typedef long long ll;
using namespace std;ll n,t,ans,de[105];int main()
{// de为存2的倍数的数组de[0]=1LL;for (int i=1;i<=35;i++)de[i]=de[i-1]*2;cin >> t;while(t--){cin >> n;// 求1-n的和ans=(1+n)*n/2;for (int i=0;i<=35;i++)// 减掉2的倍数if (de[i]<=n)ans-=(2LL*de[i]);cout << ans << endl;}return 0;
}

E题

题意：

问从左上角走到右下角的最短路径，并输出。

分析：

求最短路径就用bfs，问题是怎么存路径，我这里解决的办法是用一个pre数组，pre[x][y]表示(x,y)位置的前一个位置是什么，最后倒着推回去就可以知道路径了。

参考代码：

#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;struct node
{int x,y;
}st;int maze[5][5];
node pre[5][5];
int vis[5][5];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};// 判断是否在地图内，而且能走
int judge(int x,int y)
{if (0<=x&&x<5&&0<=y&&y<5&&maze[x][y]==0)return 1;return 0;
}void bfs()
{memset(vis,0,sizeof(vis));st.x=0,st.y=0; vis[0][0]=1;queue<node> Q;Q.push(st);while(!Q.empty()){node Now=Q.front();if (Now.x==4&&Now.y==4)return;Q.pop();for (int i=0;i<4;i++){int nx=Now.x+dx[i],ny=Now.y+dy[i];if (judge(nx,ny) && !vis[nx][ny]){vis[nx][ny]=1;// 注意这里要标记当前位置的前驱位置，用于输出路径pre[nx][ny]=Now;node New;New.x=nx; New.y=ny;Q.push(New);}}}}// 利用递归打印路径
void print(int x,int y)
{// 找到起点，打印起点if (x==0 && y==0)printf("(0, 0)\n");else{print(pre[x][y].x,pre[x][y].y);printf("(%d, %d)\n",x,y);}
}int main()
{for (int i=0;i<5;i++)for (int j=0;j<5;j++)scanf("%d",&maze[i][j]);bfs();print(4,4);return 0;
}

F题

题意：

我的队友真的是改题鬼才，改的我都看不懂。

吐血了，我的队友改题的时候把数据范围改错了，还好比赛的时候没多少人做。

注意：这里n的范围是<=2*10^5，题面有误，我们对造成的RE表示抱歉。

简单的来说就是有一堆咖啡，然后每杯咖啡有对应咖啡因，一天的第一杯咖啡咖啡因-0，第二杯-1以此类推直到0。

然后1咖啡因对应1作业，问最快多少天能做完作业。

分析：

这其实是一道二分的题目，二分需要的天数。

然后判断当前天数是否符合条件，如果符合那就二分小的那部分，否则就二分大的那部分。

关键是怎么判断是否符合条件呢？

这边有一个贪心的思想：我们每次肯定是在每一天先喝咖啡因多的咖啡，因为这个不会减少咖啡因，而咖啡因少的就放在后面喝。于是我们就可以先把咖啡因从大到小排序，然后进行总的咖啡因的计算。

假设x为天数，这里有一个小技巧，我们前1-x个咖啡因-0，想x+1-2x个咖啡因-1。

于是我们可以写成for (i=0;i<n;i++) sum+=a[i]-i/x;

参考代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
typedef long long ll;
using namespace std;int n,m,k;
int a[200005];int cmp(int a1,int a2)
{return a1>a2;
}// 判断函数
int judge(int x)
{// sum用来计算总的咖啡因ll sum=0;for (int i=0;i<n;i++)// 注意不能加负的sum+=max(0,a[i]-i/x);// 说明当前天数足够if (sum>=k) return 1;return 0;
}int main()
{cin >> n >> k;for (int i=0;i<n;i++)scanf("%d",&a[i]);// 降序排列sort(a,a+n,cmp);// 二分答案int l=1,r=n;while(l<r){int mid=(l+r)>>1;if (judge(mid))r=mid;elsel=mid+1;}if (judge(l))cout << l << endl;else cout << -1 << endl;return 0;
}

G题

题意：

已知数位和的根就是对一个数字求数位和直到这个数字为1-9，记做S(x)。

给你x和k，求第k大的数位和的根为x的数字。

分析：

这个题目乍看很难，其实很简单。我们先来计算一下S(1)-S(100)，我们会发现S的值是从1-9不断循环的。

于是就很简单了，第k大的根为x的数就是(k-1)*9+x。

参考代码：

#include <cstdio>
#include <iostream>
typedef long long ll;
using namespace std;ll n,k,x;int main()
{cin >> n;while(n--){cin >> k >> x;cout << (k-1LL)*9+x << endl;}return 0;
}

H题

题意：

闲人们都分配好了工作，但是要让所有工作都有人做，已知说服闲人要花费的口舌，要说服闲人做其他工作，然后求浪费最少口舌。

分析：

至少一个闲人的工作留下那个花费口舌最大的闲人，剩下的闲人加到优先队列里面，取出浪费口舌最少的闲人分配到其他工作。

参考代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
typedef long long ll;
using namespace std;ll n,k,temp=0;
ll a[100005],b[100005],worker[100005],cost[100005];
ll ans=0;
priority_queue<ll,vector<ll>,greater<ll> > Q;int main()
{memset(worker,0,sizeof(worker));memset(cost,0,sizeof(cost));cin >> n >> k;for (int i=1;i<=n;i++)cin >> a[i];// 读入口舌，worker[i]为工作i有的闲人个数，cost[i]为花费最高的闲人for (int i=1;i<=n;i++){cin >> b[i];worker[a[i]]++;cost[a[i]]=max(cost[a[i]],b[i]);}// 把除了花费最高闲人加入优先队列，temp为已经有闲人的工作for (int i=1;i<=n;i++){if (worker[a[i]]>1){if (cost[a[i]]==b[i])cost[a[i]]++;elseQ.push(b[i]);}if (worker[i]>=1)temp++;}// 把能用的闲人取出k-temp个分配到没有人的工作for (int i=1;i<=k-temp;i++){ans+=Q.top();Q.pop();}cout << ans << endl;return 0;
}

I题

题意：

有一系列题目按顺序出的，如果出完一道题1-n难度的题目都有了就可以出场比赛了，然后删掉这些题目。问出完哪些题目可以出比赛，出比赛的时候输出1，其他时候输出0。

分析：

用一个map来映射每个难度题目的数量，当map元素的个数有n个的时候就说明可以出比赛了，然后对应map中的每个元素都删掉一个。

参考代码：

#include <cstdio>
#include <iostream>
#include <map>
using namespace std;int n,m,x;
map<int,int> M;int main()
{cin >> n >> m;for (int i=1;i<=m;i++){cin >> x;// x难度的题之前存在，就加一if (M.count(x))M[x]++;// 不存在，标记为1elseM[x]=1;// 出的1-n的题目都有了if (M.size()==n){printf("1");// 1-n难度的题目都减一for (int j=1;j<=n;j++){M[j]--;// 减没了，就删掉if (M[j]==0)M.erase(j);}}elseprintf("0");}return 0;
}

J题

题意：

又是数学题，n!转化成b进制尾导0有几个。

分析：

又是队友出的，数学题对我来说实在是太难了，我感觉是整个比赛最难的（我是个蒟蒻）。

水平有限我就不班门弄斧了，。

这里引用的是别的大佬的解析：https://blog.csdn.net/qq_42217376/article/details/87791186

参考代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map> 
using namespace std;typedef long long ll;
const ll Max_n=10000005;
vector<ll>prime;
map<ll,ll>cnt;void get_count(ll b)
{for(int i=2;i<=sqrt(b);++i){if(b%i==0){prime.push_back(i);while(b%i==0) cnt[i]++,b/=i; }}if(b>1){prime.push_back(b);cnt[b]++;}
}ll solve(ll n,ll p)
{ll res=0;while(n) res+=n/p,n/=p;return res;
}int main()
{ll n,b;scanf("%lld%lld",&n,&b);get_count(b);ll len=prime.size();ll ans=1e18+5;for(int i=0;i<len;++i)ans=min(ans,solve(n,prime[i])/cnt[prime[i]]);printf("%lld\n",ans); return 0;
}

K题

题意：

炒鸡无敌大模拟。

分析：

简单的来说就是先还原诗句，然后在输成要求那样。类似蛇形填数，可以参考。

我的代码是自己比赛时写的，写的可能有点挫，将就着看下吧，这是2017年ACM-ICPC北京区域赛的一道原题，如果有问题可以网上找一下其他题解看一下问题所在。

参考代码：

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;int n;
char p[100005];
char M[105][105];
char ans[105][105];int main()
{while(scanf("%d",&n)!=EOF){memset(ans,0,sizeof(ans));for (int i=1;i<=n;i++)scanf("%s",M[i] + 1);	p[1]=M[1][1];int x=1,y=1,op=1,t=2,op1=1;while(!(x==n && y==n)){if (op==1){if (y!=n){y++;p[t++]=M[x][y];op=0;}else{x++;p[t++]=M[x][y];}}else{if (x!=n){x++;p[t++]=M[x][y];op=1;}else{y++;p[t++]=M[x][y];}				}if (x==n && y==n)break;if (op1==0){while(1){if (x-1<1 || y+1>n)break;elsex--,y++;p[t++]=M[x][y];}op1=1;}else{while(1){if (x+1>n || y-1<1)break;elsex++,y--;p[t++]=M[x][y];}op1=0;}			}x=1,y=1; ans[1][1]=p[1];int temp=2;while(temp<=n*n){while(1){if (y+1>n || ans[x][y+1])break;elsey++;ans[x][y]=p[temp++];}while(1){if (x+1>n || ans[x+1][y])break;elsex++;ans[x][y]=p[temp++];}while(1){if (y-1<1 || ans[x][y-1])break;elsey--;ans[x][y]=p[temp++];}while(1){if (x-1<1 || ans[x-1][y])break;elsex--;ans[x][y]=p[temp++];}}for (int i=1;i<=n;i++){for (int j=1;j<=n;j++)printf("%c",ans[i][j]);printf("\n");}}return 0;
}

L题

题意：

改一个大数的每位数，问最少改几个能让和不小于k。

分析：

算是贪心吧，直接都改成9就完事了，小的数字优先改成9。

参考代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;int k,sum=0;
string s;int main()
{cin >> k >> s;// 从小到大排序sort(s.begin(),s.end());for (int i=0;i<s.length();i++)// 计算总和sum+=s[i]-'0';int ans=0;// 如果sum<k就继续改成9while(sum<k)// 改成9后修改当前的sumsum+='9'-s[ans++];cout << ans << endl;return 0;
}