写在前面:本次比赛共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;
}