比赛链接:https://codeforc.es/contest/1711
感觉题比较难,幸亏没参赛,不然掉老多分了。感觉一个也做不出来,补题只打算补A和B了
A题:大意是给出一个n,制作一个p1 - pn长度的序列,内容为1-n,对于每一个pi,如果pi%i==0则为一个权重,最后使得权重最小。
一个很明显的数学构造题,我们从1开始考虑,这个元素权重至少为1,对于剩下的每个pi,都有pi-1%pi !=0,所以可以把n放在最前面,剩下的作为顺序排列。
code:
#include<bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin>>t; while(t--) { int n; cin>>n; cout<<n<<' '; for(int i=1;i<n;i++) { cout<<i<<' '; } cout<<endl; } }
B题:大意是要开一个party,有n个人,如果不邀请其中的一个人就会获得一个不快乐值,给出n个人的预计不快乐值。
party开始后,朋友之间会分享蛋糕,有m对朋友,每个人吃的蛋糕数量=他被邀请的次数,蛋糕机一次只能做两个,所以要求求出一种邀请方式,使得获得的不快乐值最少,且吃的蛋糕数量为偶数。
思路:这个题很有意思,因为吃的蛋糕必须是偶数,所以有可能存在一种情况,所有的人我都邀请了,然而却消费了奇数个蛋糕,这个时候我就需要不邀请一些朋友。首先我们考虑一下有没有可能存在一种情况,使得我们吃的蛋糕是偶数呢,肯定是存在的,当m为偶数时,度为0的成员一定是个偶数的,所以不用删除朋友。
当m为奇数时,我们可以删除一个奇数度的朋友,使得吃的蛋糕数量为偶数。也可以删除一对相邻的偶数度朋友,这里也可以理解成删除一组朋友一定能形成一个合法状态,上面说到了。特别注意的一种情况,就是当m为奇数时,我们既可以删除一个奇数度朋友,也可以删除两个成一对的偶数度朋友。
经过举一反三的测试,我们总可以通过删除一对朋友获得一个合法状态,也总可以通过删除一个奇数度朋友获得一个合法状态。
code:
#include<bits/stdc++.h> using namespace std; const int nn = 1e5+10; int unhappy[nn]; int degree[nn]; int x[nn],y[nn]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin>>t; while(t--) { memset(unhappy,0,sizeof unhappy); memset(degree,0,sizeof degree); memset(x,0,sizeof x); memset(y,0,sizeof y); int n,m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>unhappy[i]; for(int i=1;i<=m;i++) { cin>>x[i]>>y[i]; degree[x[i]]++; degree[y[i]]++; } /* for(int i=1;i<=n;i++) cout<<degree[i]<<' '; cout<<endl;*/ int ans = 9999999; if(m%2==0) ans = 0; for(int i=1;i<=n;i++)//删除一个奇数点 if(degree[i]%2==1) ans = min(ans,unhappy[i]); for(int i=1;i<=m;i++)//删除一对偶数点 // if(degree[x[i]]%2==0&°ree[y[i]]%2==0) ans = min(ans,unhappy[x[i]]+unhappy[y[i]]); cout<<ans<<endl; } }