🌏博客主页:PH_modest的博客主页
🚩当前专栏:cf闯关练习
💌其他专栏:
🔴每日一题
🟡 C++跬步积累
🟢 C语言跬步积累
🌈座右铭:广积粮,缓称王!
一.关卡1(D. Epic Transformation)
👉传送门👈
1.Tutorial
- 统计每个数出现的次数,然后找到出现的最大次数maxx
- 然后通过模拟得出以下结论:(
真的就是慢慢模拟找的)
- 如果maxx大于n/2,那么就说明这个数(x)可以和其他数全部消去,最后剩下的数一定是x,通过观察可以得出最后剩余的值满足以下结论:n-2*(n-maxx);
-如果maxx小于等于n/2,那么就需要分奇偶讨论,因为如果是偶数,最后剩余的两个相异的数能够抵消,如果是奇数就不可以;
(1)偶数情况:只要我们优先将次数多的先结合,最后一定不会剩余数字,所以直接输出0,至于为什么大家可以下去模拟一下;(我也不会证明)
(2)奇数情况:奇数情况和偶数差不多,只不过最后一个数没办法消除,所以直接输出1。
2.Solution
//https://codeforces.com/problemset/problem/1506/D
//结果和数量最多的那个数有关
//
#include<bits/stdc++.h>
#define int long long
using namespace std;void solve()
{int n;cin>>n;map<int,int>mp;int maxx=0;for(int i=0;i<n;i++){int a;cin>>a;mp[a]++;maxx=max(maxx,mp[a]);}if(maxx==n-maxx) cout<<"0\n";else if(maxx>n-maxx) cout<<maxx-(n-maxx)<<"\n";else{if(n%2==0) cout<<"0\n";else cout<<"1\n";}
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){solve();}return 0;
}
3.Conclusion
二.关卡2
👉传送门👈
1.Tutorial
第一行从2开始递增,这样可以保证第一行的最大公约数是1,然后每一列的最大公约数就可以设置成第一行的数,之后的每行是由第一行乘上当前行数的最大公约数得到的,需要特别判断一下只有一列或者行和列都为1的情况,看起来比较抽象可以看下面的图;
2.Solution
//https://codeforces.com/problemset/problem/1266/C
//第一行从2开始递增,这样可以保证第一行的最大公约数是1,然后每一列的最大公约数就可以设置成第一行的数,之后的每行是由第一行乘上当前行数的最大公约数得到的,需要特别判断一下只有一列或者行和列都为1的情况
//
#include<bits/stdc++.h>
#define int long long
using namespace std;int s[505][505];void solve()
{int r,c;cin>>r>>c;if(r==1&&c==1){cout<<"0\n";return;}if(c==1){int tmp=2;for(int i=0;i<r;i++){cout<<tmp<<"\n";tmp++;}cout<<"\n";return;}int flag=2;for(int i=0;i<c;i++){s[0][i]=flag++;}for(int i=1;i<r;i++){for(int j=0;j<c;j++){s[i][j]=s[0][j]*flag;}flag++;}for(int i=0;i<r;i++){for(int j=0;j<c;j++){cout<<s[i][j]<<" ";}cout<<"\n";}
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);solve();return 0;
}
3.Conclusion
最后:
闯关系列旨在养成刷题的习惯,所以对代码的解释并不会特别详细,但足够引导大家写出来,选的题目都不会特别难,但也不是特别简单,比较考验大家的基础和应用能力,我希望能够将这个系列一直写下去,也希望大家能够和我一起坚持每天写代码。
之后每个星期都会不定期更新codeforces和atcoder上的题目,想要学习算法的友友们千万别错过了,有什么疑问欢迎大家在评论区留言或者私信博主!
最近在全力突破瓶颈,更新的会比较慢,请见谅!
在这里送大家一句话:广积粮,缓称王!