众所周知，codeforce div2AB两题以思维题为主，极少涉及算法知识。对于新手来说，能够快速并准确地解决B题是上分的关键。当AB题的写题量达到一定程度时，可以发现所谓思维题也有套路可循。据此，笔者将套路归纳为几大块，并收纳了一些具有一定代表性的题目。
本题单持续更新。
模拟
这里放上一些对模拟码力要求较高而解题性质较明显的题目。
732(div2) A.AquaMoon and Two Arrays
题意：虽然是A题，但还是有点码力要求的 给两个序列，可以对第一个序列进行任意次操作，每次操作可选取两个数，使其中一个数加一，另一个数减一，问能否进行小于等于100次的操作，使第一个序列变成第二个序列，并将操作过程输出。
思路：纯模拟+贪心。将所有数分为两部分，要加的和要减的，把要加的差减去要减的，可以发现最后两差分数组所有数必为零，不为零输出-1。
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
struct Node{
int x,y;
};
bool cmp(Node x,Node y){
return x.y < y.y;
}
signed main(){
IOS
int t;cin>>t;
while (t--){
int n;cin>>n;
int a[n+1],b[n+1];
for (int i=1;i<=n;i++) cin>>a[i];
for (int i=1;i<=n;i++) cin>>b[i];
Node d1[n+1],d2[n+1];
//d1存要加的，d2存要减的
//处理d1 d2数组 y存差值 x存下标
int cnt = 0,snt = 0;
for (int i=1;i<=n;i++){
int d = a[i] - b[i];
if (d<0){
cnt++;
d1[cnt].y = -d;
d1[cnt].x = i;
}
else if (d>0){
snt++;
d2[snt].y = d;
d2[snt].x = i;
}
}
//贪心 根据值排序
sort(d1+1,d1+cnt+1,cmp);
sort(d2+1,d2+snt+1,cmp);
vector<pair<int,int>>op;
//op存操作过程
bool flag = 0;
//flag判断能否成功变成
//模拟部分
for (int i=1;i<=cnt;i++){
int dd = d1[i].y;
//取出一个d1 然后暴力遍历d2
for (int j=1;j<=snt;j++){
if (d2[j].y>=dd){
//d2 比 dd大 直接减
d2[j].y -= dd;//d2减去dd贡献
for (int k=1;k<=dd;k++){
op.push_back({
d2[j].x,d1[i].x});
}//存操作数
dd = 0;//dd清零
break;
}
else {
for (int k=1;k<=d2[j].y;k++){
op.push_back({
d2[j].x,d1[i].x});
}
dd -= d2[j].y;//dd减去贡献
d2[j].y = 0;//d2变为0
}
}
if (dd){
//d1经过遍历d2后都不能变成0 说明无法变成
flag = 1;
break;
}
}
//如果可以变成第二个序列，d2数组在操作后必为零
for (int i=1;i<=snt;i++){
if (d2[i].y){
flag = 1;//不为零就说明变成不了
break;
}
}
//输出部分
if (flag) cout<<-1<<endl;
else {
cout<<op.size()<<endl;
for (auto it:op){
cout<<it.first<<" "<<it.second<<endl;
}
}
}
}
751(div2) B. Divine Array
题意：给一串数，进行无数次操作，每次操作让每个数变成它出现的次数。进行q次询问，询问第x下标第k***作的值
思路：模拟+思维。对于无数次操作的题目，显然是去找一个“不动结点”，即发现哪次操作后数组值不会改变。手模一遍后发现，当每个数的数值等于它出现次数时，它就不变了。故用桶模拟出这个过程即可。
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
signed main(){
IOS
int t;cin>>t;
while (t--){
int n;cin>>n;
int a[n+1];
map<int,int>mp;
int m[n+1][n+1];
//m[i][k]第k次操作第i个数的值
//mp记录每个数出现次数
for (int i=1;i<=n;i++){
cin>>a[i];
m[i][0] = a[i];
mp[a[i]]++;
}
int cnt = 0;
while (1){
bool flag = 0;
cnt++;
//cout<<"cnt = "<<cnt<<endl;
for (int i=1;i<=n;i++){
m[i][cnt] = mp[m[i][cnt-1]];
//cout<<m[i][cnt]<<" ";
//mp[mmp[a[i]]]++;
}
mp.clear();
for (int i=1;i<=n;i++){
mp[m[i][cnt]]++;
}
for (int i=1;i<=n;i++){
if (mp[m[i][cnt]]!=m[i][cnt]) flag = 1;
}
//cout<<endl;
if (flag) continue;
else break;//当所有数等于出现次数时 不会再改变 跳出循环
}
int q;cin>>q;
while (q--){
int x,k;cin>>x>>k;
if (k>cnt) k = cnt;
cout<<m[x][k]<<endl;
}
//cout<<"......."<<endl;
}
}
705(div2) B. Planet Lapituletti
题意：自定义小时进制h,分钟进制m,给出当前时间，求最近的在镜子里合法的未来时间。
思路：模拟+简单规律。可以发现镜子里的合法时间仅包括0，1，2，5，8五个数字，故暴力枚举所有合法时间和其镜子里的映射时间，判断两者是否均符合进制，记录离当前时间最近的时间即可。
#include <bits/stdc++.h>
#define INF 0x7f7f7f7f
using namespace std;
char s[] = {
'0','1','2','5','8'};
string s1[30];
int cnt;
int at(string s){
//计算现实时间
int ans = 0;
for (int i=0;i<s.size();i++)
ans = ans * 10 + s[i] - '0';
return ans;
}
int bt(string s){
//映射为镜子里的时间
int ans = 0;
for (int i=s.size()-1;i>=0;i--)
if (s[i]=='2') ans = ans * 10 + '5' - '0';
else if (s[i]=='5') ans = ans * 10 + '2' - '0';
//注意2和5需要转换
else ans = ans * 10 + s[i] - '0';
return ans;
}
int main(){
for (int i=0;i<5;i++){
for (int j=0;j<5;j++){
string ss;ss += s[i];
ss += s[j];
s1[cnt++] = ss,ss.clear();
}
}//预处理所有合法时间
int t;cin>>t;
while (t--){
int h,m;cin>>h>>m;
int a,b;
scanf("%d:%d",&a,&b);
int mini = INF;
string ans_h,ans_m;
for (int i=0;i<cnt;i++){
//暴力枚举所有合法时间
for (int j=0;j<cnt;j++){
int hi = at(s1[i]),mi = at(s1[j]);
int hh = bt(s1[j]),mm = bt(s1[i]);
//hi,mi存现实时间
//hh,mm存镜子时间 注意小时和分钟互换
if ((hi>=h)||(mi>=m)||(mm>=m)||(hh>=h)) continue;
//判断是否符合要求的进制
int ti = (hi * m + mi) - (a * m + b);
//ti计算同一天的时间差
if (ti<mini&&ti>=0){
mini = ti;
ans_h = s1[i],ans_m = s1[j];
}
int si = hi * m + mi + h * m - (a * m + b);
//si计算不同天的时间差
if (abs(si)<mini){
mini = abs(si);
ans_h = s1[i],ans_m= s1[j];
}
}
}
cout<<ans_h<<":"<<ans_m<<endl;
}
}
748(div3) B. Make it Divisible by 25
题意：给一串数，去掉任意数后使其变为25的倍数，求最少去掉几个数
做法：数学规律+暴力枚举。发现规律25的倍数末尾必为00，25，50，75，故暴力枚举、用双指针往后找越接近末尾的子序列，去掉的数=右指针到末尾的数+左右指针中间的数，再取最小值即可
#include <bits/stdc++.h>
#define INF 0x7f7f7f7f
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
string s[] = {
"00","25","50","75"};
signed main(){
IOS
//for (int i=25;i<=100000;i+=25) cout<<i<<endl;
int t;cin>>t;
while (t--){
string ss;cin>>ss;
int len = ss.length();
int ans = INF;
for (int i=0;i<4;i++){
int l = -1,r = -1;
for (int k=0;k<ss.size();k++){
if (ss[k]==s[i][1]){
r = k;
}
}//右指针先找末尾数的位置
if (r!=-1){
for (int k=0;k<ss.size()&&k<r;k++){
if (ss[k]==s[i][0]){
l = k;
}
}
}
//cout<<"l = "<<l<<" r = "<<r<<endl;
if (l!=-1&&r!=-1) {
ans = min(len-r-1+r-l-1,ans);
}
}
cout<<ans<<endl;
}
}
753(div3) B. Odd Grasshopper
题意：给一个原坐标x0,可以向左或向右跳t格（t为时间点，如果第一次跳就跳1格，第二次跳就跳2格，以此类推），如果在奇数坐标向右跳，在偶数就向左跳，问跳了n次后的坐标位置。
思路：思维+模拟。很有趣的题目。纸上画一下可发现跳4次是一个循环节，也可打表找规律，再分类讨论一下原坐标x0的奇偶。
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int t;cin>>t;
while (t--){
int x,n;cin>>x>>n;
int ans = x;
if (x%2==0){
if (n%4==0) ans = x;
else if (n%4==1) ans -= n;
else if (n%4==2) ans += 1;
else if (n%4==3) ans += n + 1;
}
else {
if (n%4==0) ans = x;
else if (n%4==1) ans += n;
else if (n%4==2) ans -= 1;
else if (n%4==3) ans -= n + 1;
}
cout<<ans<<endl;
}
}
贪心
常见套路是排序+堆
711(div2) B. Box Fitting
题意：一辆宽度为w的二维货车，有n个物品，每个物品有一定宽度，问物品最少能垒成几行
思路：动态贪心。易知先放大物品可使决策更优，故先将物品从大到小排序；每放一个物品，挑选剩下长度最长的行，故用大顶堆维护每行剩余长度。
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;cin>>t;
while (t--){
int n,w;cin>>n>>w;
int a[n+1];
for (int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n,greater<int>());
priority_queue<int>q;
for (int i=1;i<=n;i++){
if (q.empty()) q.push(w-a[i]);
else {
if (q.top()<a[i]) q.push(w-a[i]);
else {
int t = q.top();q.pop();
t -= a[i];
q.push(t);
}
}
}
cout<<q.size()<<endl;
}
}
707(div2) B. Napoleon Cake
题意：一块蛋糕有n层，每层有a[i]奶油，奶油会往下渗，有多少奶油就向下渗几层，被渗透的层数用1表示，没被渗透的用0表示。
思路：贪心+模拟。因为蛋糕一定是从上往下渗透，故从后往前遍历，用cnt记录最多可以渗透几层。
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;cin>>t;
while (t--){
int n;cin>>n;
int a[n+1],b[n+1];
for (int i=1;i<=n;i++) cin>>a[i];
int cnt = a[n];
for (int i=n;i>=1;i--){
if (a[i]){
//如果当前层数有奶油 考虑更新cnt
if (cnt<a[i]){
cnt = a[i] - 1;
b[i] = 1;
}
else {
cnt--;
b[i] = 1;
}
}
else {
//如果没有奶油 直接看cnt状态
if (cnt) b[i] = 1,cnt--;
else b[i] = 0;
}
}
for (int i=1;i<=n;i++) cout<<b[i]<<" ";
cout<<endl;
}
}
673(div2) B. Two Arrays
题意：把序列分成两部分，使这两部分加起来等于k的数对最小
思路：贪心+思维。把小于k一半的数放在一起，把大于k一半的放一起，如果等于k的一半则对半标记
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
struct Node{
int x,c;
};
int main(){
int t;cin>>t;
while (t--){
int n,k;cin>>n>>k;
int flag = 0;
Node a[n+1];
for (int i=1;i<=n;i++){
cin>>a[i].x;
if (a[i].x*2<k) a[i].c = 1;
else if (a[i].x*2>k) a[i].c = 0;
else if (a[i].x*2==k){
if (flag) a[i].c = 1;
else a[i].c = 0;
flag = 1 - flag;
}
}
for (int i=1;i<=n;i++) cout<<a[i].c<<" ";
cout<<endl;
}
}
Global Round 11 B. Chess Cheater
题意：給一串LW的字符串，若W前面也有W则它的贡献为2，没有则贡献为2。现在可以进行k次操作，将L变为W，问操作后的最大贡献。
思路：贪心。若有区间1WLW，将这个L填满带来3贡献；若有区间2WLLW，填满带来5贡献，平均每个L带来2.5贡献，小于区间2每个L带来的贡献。故贪心先填满小区间贡献最大，将每个区间放进容器排序，再计算剩下的操作即可。
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;cin>>t;
while (t--){
int n,k;cin>>n>>k;
string s;cin>>s;
if (n==1&&k>=1){
cout<<1<<endl;
continue;
}
s = '0' + s;
int flag = 0,ans = 0,cnt = 0;
vector<int>v;
for (int i=1;i<=n;i++){
if (s[i]=='W'){
if (!flag) flag = i;
else v.push_back(i-flag-1),flag = i;
ans++;
cnt++;
}
}
sort(v.begin(),v.end());
for (int i=0;i<v.size();i++){
if (v[i]<=k){
k -= v[i];
ans += v[i] * 2 + 1;
cnt += v[i];
}
}
if (!cnt&&k) ans += (k - 1) * 2 + 1;
else if (k){
cnt = n - cnt;
ans += min(cnt,k) * 2;
}
cout<<ans<<endl;
}
}
位运算题
包括&，^,|等各种操作题
717(div2) B. AGAGA XOOORRR
题意：给一串序列，对其进行任意次操作，每次操作选取相邻的两个数进行异或，使其变成长度不小于2的每个数相等的序列。
思路：数学+思维。1.若长度为偶数的相等序列，它们的异或值必为0；2.若长度为奇数的相等序列，它们的异或值必为这些相等数。
于是可以倒推思考。异或值为0→一定可以变成相等序列；最后异或值不为0→若有异或值等于这个值的区间数大于等于2，则可以变成相等序列
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int t;cin>>t;
while (t--){
int n;cin>>n;
int a[n+1];
int ans = 0;
for (int i=1;i<=n;i++){
cin>>a[i];
ans ^= a[i];
}
//cout<<"ans = "<<ans<<endl;
if (!ans) puts("YES");
else {
int sum = 0,cnt = 0;
for (int i=1;i<n;i++){
sum ^= a[i];
if (ans==sum){
cnt++;
sum = 0;
}
}
if (cnt>=2) puts("YES");
else puts("NO");
}
}
}
Round 714(div2)B. AND Sequences
题意：给一串序列，问对任意i<=n-1满足a1&a2&…&ai=ai+1&ai+2&…&an 有多少种排列方式
思路：数学+思维。通过观察，可以发现a1和an是永远都在等式两边的，假若a1和an不相等，则等式无法成立。
简单证明：
以样例为例,当n = 5时，有：
s1=s2&s3&s4&s5
s1&s2&s3&s4=s5
两式联立有：
s1=s2&s3&s4&s1&s2&s3&s4=s2&s3&s4&s1=s5
（&运算符合交换律和结合律，两个相等的数&后是本身）
同时其值要等于所有数的&值，有：
s1=s2&s3&s4&s5 = 0
s1 = s1&s1=s2&s3&s4&s5&s1=0
s5同理
故挑选相同和等于所有数&值的数在两边，其余数任意排即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
const int N = 2e5 + 7;
int f[N];
signed main(){
int t;cin>>t;
f[0] = 1,f[1] = 1;
for (int i=2;i<=2e5;i++){
f[i] = i * f[i-1] % mod;
}//预处理阶乘
while (t--){
int n;cin>>n;
int a[n+1];
int ans = 0,snt;
map<int,int>mp;
for (int i=1;i<=n;i++){
cin>>a[i];
if (i==1) snt = a[i];
else snt &= a[i];
mp[a[i]]++;
}
if (mp[snt]>1){
int c = mp[snt] * (mp[snt]-1) % mod;
int d = n - 2;
ans = (ans + c*f[d]%mod) % mod;
}
cout<<ans<<endl;
}
}
752(div2) B. XOR Specia-LIS-t
题意：将一个序列分为任意段，判断能否使每一段最长上升子序列的长度异或为0
思路：思维+数学。最长上升子序列和异或的关系看上去好像很难联系在一起。这里我们把问题简单化。
绝大多数异或题必分奇偶。如果序列为偶数长度，直接全分为长度为1的小段，它们的异或和肯定为0；如果序列为奇数长度，只需找到相邻一段a[i]>=a[i+1]的区间，使它和其他长度为1的小段凑成偶数个数，如果找不到，那就无法实现。
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;cin>>t;
while (t--){
int n;cin>>n;
int a[n+1];cin>>a[1];
bool flag = 0;
for (int i=2;i<=n;i++){
cin>>a[i];
if(a[i]<=a[i-1]){
flag = 1;
}
}
if (flag||n%2==0) puts("YES");
else puts("NO");
}
}
672(div. 2) B. Rock and Lever
题意：问一个序列中有多少对异或值等于与值 ai & aj≥ai⊕aj
思路：思维。可以发现二进制同位数的与值必大于异或值，不同位则异或大于与值。故用桶统计每位有多少个数即可
#include <bits/stdc++.h>
#define int long long
using namespace std;
int bit_sum(int x){
int sum = 0;
while (x){
x >>= 1;
sum++;
}
return sum;
}
signed main(){
int t;cin>>t;
while (t--){
int n;cin>>n;
int cnt = 0;
unordered_map<int,int>mp;
set<int>s;
for (int i=1;i<=n;i++){
int x;cin>>x;
mp[bit_sum(x)]++;
s.insert(bit_sum(x));
}
for (auto it=s.begin();it!=s.end();it++){
if (mp[*it]>=2){
cnt += (mp[*it]-1) * (mp[*it]) / 2;
}
}
cout<<cnt<<endl;
}
}
构造
通常是构造出一个特殊结构使之满足题目要求。
720(div2) B. Nastia and a Good Array
题意：有一串正数序列，进行不大于n次操作，每次操作任选两个数x,y满足min(a[i],a[j]) = min(x,y)，将a[i]替换为x，a[j]替换为y，使这个序列相邻两个数的gcd都等于1
思路：构造+思维。找到最小数，将它两边的数都替换为以它为起点的等差为1的递增序列即可
#include <bits/stdc++.h>
#define INF 0x7f7f7f7f
#define int long long
#define x first
#define y second
using namespace std;
signed main(){
int t;cin>>t;
while (t--){
int n;cin>>n;
int a[n+1];
int mini = INF,mint = 0;
for (int i=1;i<=n;i++){
cin>>a[i];
if (a[i]<mini){
mini = min(a[i],mini);
mint = i;
}
}
cout<<n-1<<endl;
int cnt = mini;
for (int i=mint-1;i>=1;i--){
cout<<mint<<" "<<i<<" "<<mini<<" "<<++cnt<<endl;
}
cnt = mini;
for (int i=mint+1;i<=n;i++){
cout<<mint<<" "<<i<<" "<<mini<<" "<<++cnt<<endl;
}
}
}
Round 106(div2) B. Binary Removals
题意：将一串二进制序列删除几个不相邻的数使之变为有序的
思路：思维。可以发现序列中只要有1100的结构，必不可能有序，即判断有连续的1时，判断后面是否有连续的0即可（注意连续0不和连续1相邻同样不能有序）
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;cin>>t;
while (t--){
string s;cin>>s;
bool flag = 0;
for (int i=0;i<s.size()-1;i++){
if (s[i]=='1'&&s[i+1]=='1'){
for (int j=i+2;j<s.size()-1;j++){
if (s[j]=='0'&&s[j+1]=='0'){
flag = 1;
break;
}
}
if (flag) break;
}
}
if (flag) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
}
Round 109(div2) B. Permutation Sort
题意：对一个n全排列进行任意次操作，每次操作能选择一段连续但不能等于n的区间，让区间的数任意排序，问最少能进行几次操作使全排列变成递增序列
思路：思维+构造。观察样例发现 如果最小值在最左边或最大值在最右边，那么只要选择其余一段的序列进行一次操作；如果最小值和最大值的位置互换，则必须进行3次操作；除此之外需进行2次
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;cin>>t;
while (t--){
int n;cin>>n;
int a[n+1];
bool flag = 0;
for (int i=1;i<=n;i++){
cin>>a[i];
if (i!=a[i]) flag = 1;
}
if (!flag) cout<<0<<endl;
else {
if (1==a[n]&&n==a[1]) cout<<3<<endl;
else if (n==a[n]||1==a[1]) cout<<1<<endl;
else cout<<2<<endl;
}
}
}
数学
涉及gcd，mex，max，整除，取模，奇偶，几何等知识
706(div2) B. Max and Mex
题意：对一个集合进行k次操作，每次操作加入(mex+max)/2向上取整的值，问去重后的集合大小
mex:没有出现在序列中的最小非负整数
思路：思维+数学。可以发现mex在操作过程中是一定不会出现在集合里的，即mex是定值。故进行分类讨论找到mex即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int t;cin>>t;
while (t--){
int n,k;cin>>n>>k;
vector<int>v;
unordered_map<int,int>mp;
for (int i=1;i<=n;i++){
int x;cin>>x;
v.push_back(x);
mp[x]++;
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
int si = v.size();
if (mp[0]){
int mexi = -1;
int maxi = v[si-1];
for (int i=1;i<si;i++){
if (v[i]-v[i-1]>=2){
mexi = v[i] + 1;
break;
}
}
if (mexi==-1) cout<<si+k<<endl;
else {
if (mp[(maxi+mexi+1)/2]) cout<<si<<endl;
else {
if (k) cout<<si+1<<endl;
else cout<<si<<endl;
}
}
}
else {
if (mp[(v[si-1]+1)/2]) cout<<si<<endl;
else if (k) cout<<si+1<<endl;
else cout<<si<<endl;
}
}
}
708(div2) B. M-arrays
题意：问序列能被分成几个子序列，使每个子序列相邻两个数的和能被m整除
思路：思维+数学。若两个数取模后相加等于m,则两数和能被k整除。故用桶记录取模数，把相加等于m的两个桶进行匹配。
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;cin>>t;
while (t--){
int n,m;cin>>n>>m;
map<int,int>mp;
for (int i=1;i<=n;i++){
int x;cin>>x;
mp[x%m]++;//对取模数进行桶计数
}
int cnt = 0;
if (mp[0]) cnt++;
for (int i=1;i<=m/2;i++){
if (mp[i]&&!mp[m-i]) cnt += mp[i];
else if (!mp[i]&&mp[m-i]) cnt += mp[m-i];
//若匹配不了 直接加个数
else if (mp[i]&&mp[m-i]){
//若可以匹配 进行分类讨论
if (abs(mp[i]-mp[m-i])>=2) cnt += abs(mp[i]-mp[m-i]);
//若绝对值差大于等于2 那么他们子序列的个数即绝对值差
else cnt++;
//若小于2 那么只有一个子序列
}
}
cout<<cnt<<endl;
}
}
Global round 14 B. Phoenix and Puzzle
题意：给n个等腰直角三角形，问能否组成一个正方形
思路：数学。每个大正方形的最小正方形只能由两块三角形或四块三角形拼成，故n必被2或4整除；将n/=2或n/=4，得出n能组成几个小正方形，而这些小正方形只有个数等于平方数时才能变成大正方形。
注：判断平方数时，不能写sqrt(m)*sqrt(m)==m cf编译器会误判。但我自己的dev编译器却是正确的
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;cin>>t;
while (t--){
int n;cin>>n;
if (n==2||n==4)cout<<"YES"<<endl;
else if (n%2==0){
int m = n / 2;
double c = sqrt(m);
if (c==(int)c) cout<<"YES"<<endl;
else if (n%4==0){
m = n / 4;
double c = sqrt(m);
if (c==(int)c) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
else cout<<"NO"<<endl;
}
else if (n%4==0){
int m = n / 4;
double c = sqrt(m);
if (c==(int)c) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
else cout<<"NO"<<endl;
}
}
Round 116(div2) B. Update Files
题意：有n个结点，每两个结点每次连一条边，每次最多连k条边，问变成连通图需要几次。
思路：思维+数学。发现能连的边以2的指数倍增长，当k比2的指数倍小时，把剩下没连的结点数除以k即可
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
signed main(){
IOS
int t;cin>>t;
while (t--){
int n,k;cin>>n>>k;
int p = 1;
int sum = 0;
n -= 1;//结点1不需要连
while (p<k){
//枚举2的指数倍
n -= p;
p <<= 1;
sum ++;
}
if (n<=0) cout<<sum<<endl;
else {
//剩下的结点数直接除以k
sum += (n+k-1) / k;//向上取整
cout<<sum<<endl;
}
}
}
京公网安备 11010502036488号