比赛链接:https://vjudge.csgrandeur.cn/contest/538238#overview
这次比赛做出了六道题。需要手动计算的题有点多,有点恶心,计算题就做了一个G题,主要是规律已经发现了做不出来有点可惜,BC目测应该也需要手动算一下。
BC感觉自己不会,没有做(其实就是自己不会)。
E题没看,应该是不难。H题没看,div2的C应该不简单,但不是不可做。
中间开小摊+刷抖音,应该是有大约两个半小时在做题(或许是做完atcoder打的太累了,emm~一定是这样的)。G题有点卡,D题题目太长了不想读题就一直在玩样例导致罚时较长。
A题:分类讨论。大意是给出一个数,根据性质分类,比较简单,直接代码吧。
code:
int main() { //cin.ignore(numeric_limits<streamsize>::max(),'\n'); ios_base::sync_with_stdio(0); cin.tie(0); //cout.tie(0); int n; cin>>n; bool flag1=false,flag2=false; if(n%2==0) flag1=true; if(n>4&&n<=12) flag2=true; if(flag1&&flag2) cout<<1<<' '; else cout<<0<<' '; if(flag1||flag2) cout<<1<<' '; else cout<<0<<' '; if((flag1||flag2)&&!(flag1&&flag2)) cout<<1<<' '; else cout<<0<<' '; if(!flag1&&!flag2) cout<<1<<' '; else cout<<0<<' '; }
D题:大意是给出密文和原文的对照,求一组密文解密后的原文,不能存在题目中说的冲突情况。
因为没有好好读题,所以这种密文和原文的冲突情况可能存在很多。怎么算冲突,一对多还是多对一,还是双向冲突算冲突?根据最后AC应该是只能一对一且不满足26个字母的解密也不符合条件。
解决方法:map存字符映射,sign标记一下对一情况。
code:
int main() { //cin.ignore(numeric_limits<streamsize>::max(),'\n'); ios_base::sync_with_stdio(0); cin.tie(0); //cout.tie(0); string s1,s2,s3; cin>>s1>>s2>>s3; for(int i=0;i<s1.size();i++){ if(!mp[s1[i]]&&!sign[s2[i]]||mp[s1[i]]==s2[i]) mp[s1[i]] = s2[i],sign[s2[i]]=true; else{ cout<<"Failed"<<endl; return 0; } } if(mp.size()<26){ cout<<"Failed"<<endl; return 0; } vector<char> ve; for(int i=0;i<s3.size();i++){ if(mp[s3[i]]){ ve.push_back(mp[s3[i]]); }else{ cout<<i<<endl; cout<<"Failed"<<endl; return 0; } } for(int i=0;i<ve.size();i++){ cout<<ve[i]; } }
F题:大意是给出一个数组。我们可以选择其中两个数a,b。对于a*b = x*y.可以将x和y替换到a和b。最后求得到的最大钱数。最大钱数等于所有数的和。
思路:很明显可以贪,直接分成1*(a*b)即可。所以最后答案等于所有数相乘再加去(n-1)。因为通过贪心操作存在n-1个1.
code:
void solve() { int n; cin>>n; ll ans = 1; for(int i=1;i<=n;i++){ cin>>a[i]; ans*=a[i]; } ans+=(n-1); cout<<ans*2022<<endl; }
G题:大意是存在n*n的格子,对于下标i、j。每个格子的敌人数量是i*j。求从(1,1)走到(n,n)遇到的敌人数量。只能向右或向下走。
思路:最开始想的是走到最右边在一直向下走。答案不对。通过分析发现应该是先右在下一直循环往复。
但是数据量很大,很明显暴力不行。那么就需要在纸上去解方程。
向右的为(1*2)+(2*3)+(3*4)...((n-1)*n),往下的就是(1*1)+(2*2)+(3*3)。
然后就是这两个公式化简之后。有个坑就是化简之后会有一个/6的操作。因为存在模除情况,所以强行除以6必须要乘以6的逆元,且6为合数,这样必须扩展欧几里得算法来求逆元。但是存在*2022操作,而2022又正好整除6,所以最后答案可以直接*(2022/6)
code:
void solve() { ll n; cin>>n;; ll ans = 0; // 1 2 3 4 5 6 // 1²+2²+3²+.+n²=n(n+1)(2n+1)/6 n*(n+1)*(n-1); // n*(n+1)*(2*n+1) + 3*(n+1) // n*(n+1)*(2*n+4) // n*(n+1)*(n+2)/3 // n*(n+1)*(4*n-1)/3/2 ans = n*(n+1)%mod7*(4*n-1)%mod7; ans = ans*(2022/6)%mod7; cout<<ans%mod7<<endl; }
I题:常见位运算套路题。大意就是给出一个数组。你可以选择两个数,去交换他们的二进制的某一位,可以进行无限次操作。最后求数组最大的数减最小的数的最大的情况值。
思路:很明显,我们可以构造最大的数为所有数的存在的二进制1.这里直接或运算所有的数。
最小的数应该怎么构造。最小的数肯定是把身上的1都舍去。那么我们考虑无法舍去的数。怎么才能无法舍去?我们考虑如果在交换中,无法换到0,那么无法舍去。也就是某一位不存在任何数的二进制位为0.直接与运算起来就好了。
code:
void solve() { int n; cin>>n; int maxt = 0; int mint = 0; int x; for(int i=1;i<=n;i++){ cin>>a[i]; maxt|=a[i]; } mint = a[1]; for(int i=2;i<=n;i++){ mint&=a[i]; } cout<<maxt-mint<<endl; }
J题:大意是给出一些怪物,这些怪物存在两个值,血量和能力。你拿着武器去消灭他们。武器威力值为k。每次令所有敌人减少k血量。每次攻击后,k的威力值减少,减少量为还存活的怪物的能力值最低的量。求能否消灭所有敌人。
思路:优先队列去维护所有怪物的数据,自定义排序规则以能力排序作小顶堆。然后直接模拟一遍。
code:
const int nn = 1e5+10; int h[nn]; int p[nn]; struct tdata{ ll x; ll nl; }; struct cmp { bool operator() (tdata& a, tdata& b) { return a.nl>b.nl; } }; void solve() { priority_queue<tdata,vector<tdata>,cmp> pr; ll n,k; cin>>n>>k; ll sum = 0; for(int i=1;i<=n;i++) cin>>h[i]; for(int i=1;i<=n;i++) cin>>p[i]; for(int i=1;i<=n;i++){ pr.push({h[i],p[i]}); } while(!pr.empty()&&k>0){ sum+=k; while(!pr.empty()&&pr.top().x<=sum) pr.pop(); if(!pr.empty()) k-=pr.top().nl; } if(pr.empty()) cyes; else cno; }