赞
踩
构造相邻元素差的绝对值在[2,4]的排列(1到n各出现一次)
无解输出-1
n小于4无解
n等于4时,可以3 1 4 2
当n大于4时,可以依次将5到n一个放最前面一个放最后面
trick:
差的绝对值在[2,4]均可以,可以考虑最特殊的2,只要依次前面放一个后面放一个就行
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; int n; void solve() { cin>>n; if(n<4){ cout<<-1<<endl; return; } deque<int>q; q.push_back(3); q.push_back(1); q.push_back(4); q.push_back(2); int flag=1; for(int i=5;i<=n;i++){ if(flag) q.push_front(i); else q.push_back(i); flag^=1; } for(int i=0;i<(int)q.size();i++) cout<<q[i]<<' '; cout<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--) { solve(); } return 0; }
初始有n个0
共n次操作
第i次操作:选择连续为0的一段长度最长的[l,r](如果有好几个,选最左边的),让[l,r]最中间的那个值变为i
问最终序列是什么,一定有解,且唯一
trick:
1.优先可以考虑优先队列,可以按照题目中的优先自定义优先队列
2.自定义优先队列:
//结构体 struct node{ int l,r,len; bool operator<(const node &W)const{ if(len==W.len) return l>W.l;//反着来,优先l小的话,那么用大于号 return len<W.len;//反着来,优先len大的话,那么用小于号 } }; priority_queue<node>q;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int N=2e5+10; int a[N]; int n; struct node{ int l,r,len; bool operator<(const node &W)const{ if(len==W.len) return l>W.l; return len<W.len; } }; void solve() { cin>>n; for(int i=1;i<=n;i++) a[i]=0; priority_queue<node>q; q.push({1,n,n}); for(int i=1;i<=n;i++){ auto t=q.top(); q.pop(); int pos; if(t.len%2) pos=(t.l+t.r)/2; else pos=(t.l+t.r-1)/2; a[pos]=i; q.push({t.l,pos-1,pos-1-t.l+1}); q.push({pos+1,t.r,t.r-pos}); } for(int i=1;i<=n;i++) cout<<a[i]<<' '; cout<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--) { solve(); } return 0; }
将正整数n分解为k个正整数,k个正整数的最小公倍数小于等于n/2,一定有解
先考虑特殊的,k为3的情况,因为题目中明确表示k大于等于3,那么k为3一定是特殊的,所以先考虑k为3,发现k为3只要三个数就行了,那么我们可以再补k-3个1就可以凑出k个数了,所以先让n减k-3,分解为3个数,然后再加上k-3个1即可
trick:
1.对于k大于等于3这一条件,我们可以认为k等于3是特殊的,先考虑这一情况
2.构造若干个数,要求它们的最小公倍数满足某个要求,其中1是最特殊的,我们可以先构造好几个数,满足要求,然后添加1就行了,想添几个1就添几个1
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; int n,k; void solve() { cin>>n>>k; n-=k-3; //先考虑k为3的情况 if(n%2==0){//如果n为偶数 if(n/2%2==0) cout<<n/2<<' '<<n/4<<' '<<n/4<<' ';//n/2是偶数 else if((n/2-1)%2==0) cout<<n/2-1<<' '<<n/2-1<<' '<<2<<' ';//n/2是奇数 } else cout<<n/2<<' '<<n/2<<' '<<1<<' ';//n是奇数 for(int i=0;i<k-3;i++) cout<<1<<' '; cout<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--) { solve(); } return 0; }
共n只怪兽围成一个圈,ai为第i只怪兽的生命值,我们每次发射一颗子弹,使其中一只怪兽扣除一个生命,如果一个怪兽死亡,会发生爆炸,对下一只怪兽造成bi伤害,可以连锁反应
问最少发射几颗子弹,杀死所有怪兽
前一个造成的爆炸伤害只能对后一个,要想这个怪兽被杀死,要么直接杀死,要么通过上一个怪兽的爆炸伤害杀死,方向是单向的,所以只要起点确定了,整个链的最小次数通过依次顺序来就行,于是需要考虑以每个点为起点,长度为n的链需要发射子弹数量,用前缀和
trick:
1.方向是单向的,考虑前缀和,如果成环了也一样,只不过长度乘个2而已
2.memset造成的惨案,超时,以后如果初始化的话用for循环
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int N=3e5+10; int a[2*N],b[2*N]; int sum[2*N]; int n; void solve() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]>>b[i]; for(int i=n+1;i<=2*n;i++) a[i]=a[i-n],b[i]=b[i-n]; for(int i=1;i<=2*n;i++) sum[i]=sum[i-1]+max(0ll,a[i]-b[i-1]); int ans=1e18; for(int i=1;i<=n;i++){ ans=min(ans,a[i]+sum[i+n-1]-sum[i]); } cout<<ans<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--) { solve(); } return 0; }
长度为n的数组a(数[-1e9,1e9])
操作:选择一段,可以向其中的数加上该段长度的倍数,每个数可以加的不同
操作刚好三次,使得所有元素为0
一定有解
第一次操作:1,1
第二次操作:1,n加上(-n)* a i a_i ai
第三次操作:2,n加上- a i a_i ai
trick:
操作某个数时,可以用上它本身的数值,乘,加,减混合使用
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int N=1e5+10; int a[N]; int n; void solve() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; if(n==1){ cout<<1<<' '<<1<<endl; cout<<a[1]<<endl; a[1]+=a[1]; cout<<1<<' '<<1<<endl; cout<<a[1]<<endl; a[1]+=a[1]; cout<<1<<' '<<1<<endl; cout<<(-1)*a[1]<<endl; return; } cout<<1<<' '<<1<<endl; cout<<(-1)*a[1]<<endl; a[1]=0; cout<<1<<' '<<n<<endl; for(int i=1;i<=n;i++) cout<<(-1)*n*a[i]<<' '; cout<<endl; for(int i=1;i<=n;i++) a[i]=a[i]-n*a[i]; cout<<2<<' '<<n<<endl; for(int i=2;i<=n;i++) cout<<(-1)*a[i]<<' '; cout<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
将字符串s的所有字符分配到k个集合中,分配完后集合不能为空
使得k个集合字典序最大的那个最小
顺序可以随便排
肯定要平均分
先将字符串s从小到大排个序,然后按从小到大顺序平均分到k个集合中
这样错了,比如aabbc分配到两个集合中,平均分配的话,最大的是abc,但是答案为abbc
首先,由于集合不能为空,所以都至少有一个字符,对字符串s从小到大排序,如果前k个字符不全一样,那么第k个集合就放s[k],然后就不放了,答案为s[k],如果前k个字符全一样,后面的字符也全部相等,那么就平均分配,如果后面的字符有不一样的,那么后面的字符全部放在第一个集合中
trick:
看到字典序,优先考虑第一位,再考虑第二位,一位一位看,因为前一位已经比较出来了,后面不管怎么样都没用
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int N=1e5+10; string s; int n,k; void solve() { cin>>n>>k; cin>>s; sort(s.begin(),s.end()); s=' '+s; if(s[k]!=s[1]) cout<<s[k]<<endl; else if(s[n]==s[k+1]){ cout<<s[1]; for(int i=0;i<(n-k)/k+((n-k)%k!=0);i++) cout<<s[k+1]; cout<<endl; } else{ cout<<s[1]; for(int i=k+1;i<=n;i++) cout<<s[i]; cout<<endl; } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--) { solve(); } return 0; }
样例中没有-1,大概是没有无解的情况
可以先将所有芯片移到角落,然后,再走遍所有的格子
注意要特判n为1以及m为1
trick:
矩阵要特判n为1以及m为1
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; int n,m,k; void solve() { cin>>n>>m>>k; if(n==1&&m==1){ cout<<0<<endl; return; } if(n==1){ cout<<2*m<<endl; for(int i=0;i<m;i++) cout<<'L'; for(int i=0;i<m;i++) cout<<'R'; return; } if(m==1){ cout<<2*n<<endl; for(int i=0;i<n;i++) cout<<'U'; for(int i=0;i<n;i++) cout<<'D'; return; } for(int i=0;i<k;i++){ int x,y; cin>>x>>y; } for(int i=0;i<k;i++){ int x,y; cin>>x>>y; } cout<<n-1+m-1+n*m+n-1<<endl; for(int i=0;i<m-1;i++) cout<<'L'; for(int i=0;i<n-1;i++) cout<<'U'; int flag=1; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(flag) cout<<'R'; else cout<<'L'; } if(i<n-1) cout<<'D'; flag^=1; } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
两个偶数x,y
找出一个整数n,满足n % x = y % n,一定有解
n=k1x+b
y=k2n+b
n-y=k1x-k2n
(k2+1)n=k1x+y
k1,k2均为整数,所以k3n=(k1x+y)
所以n是k1*x+y的因数
当x=y时,取n为x
当x>y时,取n为x+y
当x<y时,根据%前后大小关系分类得知,n肯定在(x,y),,取n为y-y%x/2
trick:
1.遇到x % y = a % b,转化为 x=k1 * y + c,a=k2 * b + c
2.遇到x % y,要注意前后的大小关系,讨论x<y,x=y,x>y
3.遇到%,数形结合,画数轴,用距离来理解
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; int x,y; void solve() { cin>>x>>y; if(x==y){ cout<<x<<endl; return; } if(x>y){ cout<<x+y<<endl; return; } cout<<y-(y%x)/2<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--) { solve(); } return 0; }
长度为n的01串,n为偶数
构造两个平衡序列a和b,使得si为1时ai=bi,否则ai!=bi
无解输出No
首先先看s[i]为1的,肯定是对称的,另外s[i]为0的,也肯定是对称的
对于 s[i]=1 的, 如果这个 1 是在所有 1中的前半部分, 那就用左括号, 否则就用右括号。
对于 s[i]=0 的, 则如果是第奇数个0 的情况, 就用左括号, 否则就右括号。
比较难总结,作为构造括号序列的一个案例
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; int n; string s; void solve() { cin>>n; cin>>s; map<char,int>mp; for(int i=0;i<n;i++) mp[s[i]]++; int cnt_0=0,cnt_1=0; string a,b; for(int i=0;i<n;i++){ if(s[i]=='1'){ cnt_1++; if(cnt_1<=mp['1']/2) a+='('; else a+=')'; } else{ cnt_0++; if(cnt_0%2) a+='('; else a+=')'; } } for(int i=0;i<n;i++){ if(s[i]=='1') b+=a[i]; else{ if(a[i]=='(') b+=')'; else b+='('; } } //验证 int sum=0; bool ok1=true; for(int i=0;i<n;i++){ if(a[i]=='(') sum++; else sum--; if(sum<0) ok1=false; } if(sum) ok1=false; sum=0; bool ok2=true; for(int i=0;i<n;i++){ if(b[i]=='(') sum++; else sum--; if(sum<0) ok2=false; } if(sum) ok2=false; // cout<<sum<<endl; if(!ok1||!ok2) cout<<"No"<<endl; else { cout<<"Yes"<<endl; cout<<a<<endl; cout<<b<<endl; } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--) { solve(); } return 0; }
长度为n的数组a,非降序
ai<=i
构造数组b
对于任意i,ai=mex(b1,b2,…bi)
无解输出-1
如果mex已经等于ai了,那么就需要添加大于mex的且后缀没出现过的数,为后续产生更大的mex创造机会,,否则就添加mex
trick:
mex常用的技巧之前总结过了,
一个是看后缀是否出现,一个是
while(s.count(mex)) mex++;
- 1
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int N=1e5+10; int a[N]; int n; void solve() { cin>>n; map<int,int>mp,mmp; for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]]++; set<int>s; int mex=0; int x=0; vector<int>ans; for(int i=1;i<=n;i++){ if(mex==a[i]){ while(mmp[x]!=mp[x]) x++; ans.push_back(x); s.insert(x); x++; } else{ ans.push_back(mex); s.insert(mex); while(s.count(mex)) mex++; x=max(x,mex+1); } mmp[a[i]]++; } s.clear(); mex=0; for(int i=0;i<(int)ans.size();i++){ s.insert(ans[i]); while(s.count(mex)) mex++; if(mex!=a[i+1]){ cout<<-1<<endl; return; } } for(int i=0;i<(int)ans.size();i++) cout<<ans[i]<<' '; cout<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
共n场竞赛,第i场难度为ai
Doremy初始智商为q,如果当前智商小于ai,那么可以参加这场比赛并且智商不变,否则可以参加但是智商减1或者选择不参加,智商不变
当智商减为0时,不能参加比赛
问最多参加多少场比赛
贪心
从前往后,首先,智商大于ai肯定参加,智商x如果小于ai,那么看后面小于等于x-1的个数cnt1和后面小于等于x的个数cnt2,如果cnt2>=cnt1+1,那么就不参加当前比赛,否则参加当前按比赛
用树状数组+离散化
这个策略的本质就是如果选的话不影响后面的选取就选,否则就不选,这样不是最优的,这样只能算保守,这样的问题在于虽然选这个会影响后面的选取,但是完全可以通过消耗q来将后面的全部选掉
所以,想到拐点
如果对于某个q,如果有不止一个大于q的,那么晚消耗q肯定比先消耗q优,所以将所有比赛分为两部分,每个点作为一个拐点,前半部分不消耗q,后半部分一直消耗q,然后取最优的,但可以继续优化思路,肯定让q最终刚好全部消耗完是最优的,所以从后往前,令qq为0,从后往前推,直到qq等于q
trick:
1.贪心,有可能想到的并不是最优策策略,可能想到了一个保守策略,觉得最优了,比如说有q值,通过消耗q值来执行操作,那么可能q值消耗刚好为0是最优的
2.贪心之拐点法,作为一个参考方向
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int N=1e5+10; int a[N]; int ans[N]; int n,q; void solve() { cin>>n>>q; for(int i=1;i<=n;i++) cin>>a[i],ans[i]=0; int qq=0; int idx=1; for(int i=n;i>=1;i--){ if(a[i]>qq) qq++; if(qq==q) { idx=i; break; } } // cout<<idx<<endl; for(int i=1;i<=idx-1;i++){ if(a[i]<=q) ans[i]=1; } for(int i=idx;i<=n;i++) ans[i]=1; for(int i=1;i<=n;i++) cout<<ans[i]; cout<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--) { solve(); } return 0; }
构造一个n * n的01矩阵,使得1的个数刚好等于k
记01矩阵为A,使得f(A)最小
f:(最大的行-最小的行)2+(最大的列-最小的列)2
行最大:行中所有数相加最大
一定有解
肯定要平均,行平均,列平均
平均分配问题,同时保证行分配平均,列分配平均,斜着填
按照离散数学那样,照对角线填
比如n=4
(1,1)->(2,2)->(3,3)->(4,4)
(1,4)->(2,1)->(3,2)->(4,3)
(1,3)->(2,4)->(3,1)->(4,2)
(1,2)->(2,3)->(3,4)->(4,1)
可以发现,让行为1,2,…n,让列循环右移
trick:
1.矩阵填数问题,先想好怎么填,然后在草稿纸中将填数顺序记录下来,根据横纵坐标变化规律写代码
2.矩阵循环右移写法(本质是+1取模,借助循环里其中一维++来实现)
for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ int x=(i+j)%n; } }
- 1
- 2
- 3
- 4
- 5
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; int n,k; void solve() { cin>>n>>k; vector<vector<int>>a(n,vector<int>(n)); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ a[i][j]=0; } } if(k%n) cout<<2<<endl; else cout<<0<<endl; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(k>0) a[j][(i+j)%n]=1; k--; } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cout<<a[i][j]; } cout<<endl; } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--) { solve(); } return 0; }
长度为n的字符串
beautiful:不包含一个长度大于等于2的回文子串
操作:将任意一个字符变为a,b,c中的一个
cost:将字符串边beauticul的最小操作次数
对于m次询问,回答子串[l,r]的cost
要想区间[l,r]beautiful,必须是前三个为abc的全排列,然后后面一直循环,abc的全排列一共就6种,所以就6种情况,只要前3个定死,那么后面就定死,不一样的都得修改
但是求前缀和的话,考虑abc这种排列,比如说第一个区间[1,n]那么前三个为abc然后一直循环,不一样的就计数++,然后如果后面询问[5,10],然后考虑abc这种排列,那么[5,10]为abcabc,但是再往前反推,[1,10]为cabcabcabc,并不是一开始预处理的abc这种情况,妙就妙在这里,这样并没有关系,因为我们是6种情况取最优,不管怎样,都包含了所有情况
这题很妙,当作前缀和题的一个案例
trick:
多次询问不同的区间[l,r],考虑预处理前缀和
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int N=2e5+10; int n,m; int f[N][6]; string s; string t[6]={"abc","acb","bac","bca","cab","cba"}; void solve() { memset(f,0,sizeof f); cin>>n>>m; cin>>s; s=' '+s; for(int i=1;i<=n;i++){ int k=(i-1)%3; for(int j=0;j<6;j++){ f[i][j]+=f[i-1][j]+(s[i]!=t[j][k]); } } while(m--){ int l,r; cin>>l>>r; int ans=2e9; for(int j=0;j<6;j++) ans=min(ans,f[r][j]-f[l-1][j]); cout<<ans<<endl; } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
交互题
通过问问题,来猜测长度为n的全排列
最多问2 * n 次
利用%前后大小关系,小的%大的=小的
所以先找到最大的n,然后其它模n都等于自身,似乎不好找
可以一个数模另一个数,然后再反过来一次,这样肯定可以确定一个数
trick:
1.%前后大小关系,小的%大的=小的
2.一个数模另一个数,然后再反过来一次,这样肯定可以确定一个数
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int N=1e4+10; int a[N]; int n; void solve() { cin>>n; int tmp=1; for(int i=2;i<=n;i++){ cout<<'?'<<' '<<tmp<<' '<<i<<endl; cout.flush(); int x; cin>>x; cout<<'?'<<' '<<i<<' '<<tmp<<endl; cout.flush(); int y; cin>>y; if(x>y) a[tmp]=x,tmp=i; else a[i]=y; } a[tmp]=n; cout<<'!'<<endl; for(int i=1;i<=n;i++) cout<<a[i]<<' '; cout<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
构造一个长度为n的字符串,只包括前k个小写字母
代价:si=sj&&si+1=sj+1的数目
要求代价最小
这题就是排列组合,使得相邻两个一起出现的次数越少越好
长度长了肯定会花费代价,所以造一个极长的一个周期,没填完才循环
比如k为4
a ab ac ad b bc bd c cd d 这样为一循环
trick:
如何把一个周期循环放入n个数中:
先将一个周期放入vector中,然后利用循环右移取周期里的数
for(int i=0;i<n;i++){ cout<<(char)(ans[i%(int)ans.size()]+'a'); }
- 1
- 2
- 3
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; int n,k; void solve() { cin>>n>>k; vector<int>ans; for(int i=0;i<k;i++){ ans.push_back(i); for(int j=i+1;j<k;j++){ ans.push_back(i); ans.push_back(j); } } for(int i=0;i<n;i++){ cout<<(char)(ans[i%(int)ans.size()]+'a'); } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
n * m的矩阵
每一行选择一个数,使得n个数异或起来大于0,如果无解输出NIE
否则TAK,输出n行,每行选第几列的数
这题很妙,先将每行第一个数异或起来,如果不为0,那么只要其中一行找一个和改行第一个数不一样就行了
异或:x ^ x = 0,只要改掉其中一个数,结果必不为0
当案例
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int N=510; int a[N][N]; int n,m; void solve() { cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; } } int tmp=0; for(int i=1;i<=n;i++){ tmp^=a[i][1]; } if(tmp){ cout<<"TAK"<<endl; for(int i=1;i<=n;i++) cout<<1<<' '; cout<<endl; return; } for(int i=1;i<=n;i++){ for(int j=2;j<=m;j++){ if(a[i][j]!=a[i][1]){ cout<<"TAK"<<endl; for(int k=1;k<=i-1;k++) cout<<1<<' '; cout<<j<<' '; for(int k=i+1;k<=n;k++) cout<<1<<' '; cout<<endl; return; } } } cout<<"NIE"<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
构造一个数组b,不包含数字0,使得所有ai * bi 加起来等于0,一定有解
两两抵消为0
trick:
构造题,可以先构造一个循环节(类似),然后再按照此法一直填写
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int N=1e5+10; int a[N]; int b[N]; int n; void solve() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; if(n%2==0){ for(int i=1;i<=n;i+=2){ b[i]=-a[i+1]; b[i+1]=a[i]; } } else{ if((a[1]>0&&a[2]>0&&a[3]>0)||(a[1]<0&&a[2]<0&&a[3]<0)){ b[1]=a[2]+a[3]; b[2]=b[3]=-a[1]; } else if(a[1]*a[2]>0){ b[3]=a[1]+a[2]; b[1]=b[2]=-a[3]; } else if(a[1]*a[3]>0){ b[2]=a[1]+a[3]; b[1]=b[3]=-a[2]; } else if(a[2]*a[3]>0){ b[1]=a[2]+a[3]; b[2]=b[3]=-a[1]; } for(int i=4;i<=n;i+=2){ b[i]=-a[i+1]; b[i+1]=a[i]; } } for(int i=1;i<=n;i++) cout<<b[i]<<' '; cout<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--) { solve(); } return 0; }
给定一个字符串s,问最多能删除几个字符
操作:如果相邻字符中ASCII码小1,那么可以删掉该字符
a删不掉,b只能靠a删,c只能靠b删
数据小,直接暴力,字符从大到小删
trick:
a删不掉,b只能靠a删,c只能靠b删,像这种话往往是解题的关键,类似的分析可以写下来,又比如求字典序最小,先看第一位,然后再看第二位,一位一位看
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; int n; string s; void solve() { cin>>n; cin>>s; int ans=0; for(int i=26;i>=1;i--){ char ch=(char)('a'+i-1); bool ok=true; while(ok){ ok=false; string tmp; for(int i=0;i<(int)s.size();i++){ if(s[i]==ch){ if((i-1>=0&&s[i-1]==(char)(ch-1))||(i+1<(int)s.size()&&s[i+1]==(char)(ch-1))){ ans++; ok=true; continue; } else{ tmp+=s[i]; } } else{ tmp+=s[i]; } } s=tmp; } } cout<<ans<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
玩m天游戏,每天在n个人中选择一个人作为队友,每个人被选择不能超过m/2次
每天选当天可选择中使用次数最少的那个
m/2比较特殊,只要不是当天只能选择一个人导致超过m/2次,其它都YES
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; typedef pair<int,int>PII; const int N=2e5+10; int ans[N]; int n,m; void solve() { cin>>n>>m; vector<vector<int>>e(m); map<int,int>mp; bool ok=true; for(int i=0;i<m;i++){ int k; cin>>k; for(int j=0;j<k;j++){ int x; cin>>x; e[i].push_back(x); } if(k==1){ mp[e[i][0]]++; if(mp[e[i][0]]>(m+1)/2){ ok=false; } } } if(!ok){ cout<<"NO"<<endl; return; } for(int i=0;i<m;i++){ if(e[i].size()==1){ ans[i]=e[i][0]; continue; } int mini=e[i][0]; for(int j=1;j<(int)e[i].size();j++){ if(mp[mini]>mp[e[i][j]]){ mini=e[i][j]; } } ans[i]=mini; mp[mini]++; } cout<<"YES"<<endl; for(int i=0;i<m;i++) cout<<ans[i]<<' '; cout<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--) { solve(); } return 0; }
找到字典序比s大,比t小的字符串
基本上是两种情况,要么是s+1,要么是t-1,要么特判一下
azzz
caaa
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; string s,t; void solve() { cin>>s>>t; int len=s.size(); string tmp1; for(int i=0;i<len-1;i++) tmp1+=t[i]; tmp1+=(char)(t[len-1]-1); string tmp2; for(int i=0;i<len-1;i++) tmp2+=s[i]; tmp2+=(char)(s[len-1]+1); bool ok=true; for(int i=0;i<len;i++){ if(tmp1[i]<'a'||tmp1[i]>'z'){ ok=false; break; } } if(tmp1>s&&tmp2<t&&ok){ cout<<tmp1<<endl; return; } ok=true; for(int i=0;i<len;i++){ if(tmp2[i]<'a'||tmp2[i]>'z'){ ok=false; break; } } if(tmp2>s&&tmp2<t&&ok){ cout<<tmp2<<endl; return; } string tmp; for(int i=0;i<len;i++){ if(t[i]-s[i]>1) tmp+=(char)(t[i]-1); else tmp+=t[i]; } if(tmp>s&&tmp<t){ cout<<tmp<<endl; return; } cout<<"No such string"<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
一共有n个员工
ai表示第i个员工想为ai准备礼物
构造一个序列b,bi表示第i个员工为bi准备礼物,使得越多人满足越好
bi所有数都必须不同
先把可以匹配的匹配了,那些第一次出现过的数字都可以直接确定
然后对于那些没有确定的,我们只需要保证pi!=i即可,可以先随便填入,然后对于pi=i的,进行移位即可,如果有多个pi=i,可以进行移位,但如果只有一个pi=i,那么只需要和匹配对象为a[i]的换
trick:
先确定能够确定的位置填数,然后其它位置可以先随便填入,然后再调整,进行移位或交换操作
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int N=2e5+10; int a[N],b[N]; int n; void solve() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; map<int,int>mp,pos; int cnt=0; for(int i=1;i<=n;i++){ if(!mp[a[i]]) b[i]=a[i],mp[a[i]]=1,cnt++; else pos[i]=1;//没有确定的位置 } set<int>s; for(int i=1;i<=n;i++){ if(!mp[i]) s.insert(i); } for(auto v:pos){ b[v.first]=*s.begin(); s.erase(s.begin()); } vector<int>ans; for(auto v:mp){ if(b[v.first]==v.first) ans.push_back(v.first); } // for(int i=1;i<=n;i++) cout<<b[i]<<' '; // cout<<endl; // cout<<ans.size()<<endl; // for(auto v:ans) cout<<v<<' '; // cout<<endl; if(ans.size()==0){ cout<<cnt<<endl; for(int i=1;i<=n;i++) cout<<b[i]<<' '; cout<<endl; return; } if(ans.size()==1){ for(int i=1;i<=n;i++){ if(i==ans[0]) continue; if(b[i]==a[ans[0]]){ swap(b[i],b[ans[0]]); } } } else{ int tmp=b[ans[0]]; for(int i=0;i<(int)ans.size()-1;i++){ b[ans[i]]=b[ans[i+1]]; } b[ans[(int)ans.size()-1]]=tmp; } cout<<cnt<<endl; for(int i=1;i<=n;i++) cout<<b[i]<<' '; cout<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--) { solve(); } return 0; }
长度为n的字符串(由小写字母和句号组成)
操作:将两个连续句号变成一个句号
使得没有没有连续的句号
共m次询问,每次修改一个字符(每次修改会保留),问操作的最小次数
一开始先记录连续句号的区间,并求出最开始操作的最小次数
然后,每次操作进行修改区间,并记录操作次数的变化
一开始写的,细节很多,特别是二分的边界,最后还是没调对,吃力不讨好
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int N=3e5+10; int rr[N];//区间右端点 int n,m; string s; void solve() { cin>>n>>m; cin>>s; set<int>ans;//记录区间左端点 bool ok=false; int l; for(int i=0;i<n;i++){ if(!ok&&s[i]=='.'){ l=i; ans.insert(l); ok=true; } else if(ok&&s[i]!='.'){ rr[l]=i-1; ok=false; } } if(ok) rr[l]=n-1; int sum=0; for(auto v:ans){//计算最开始的操作次数 int l=v,r=rr[l]; int len=r-l+1; sum+=len-1; } // cout<<sum<<endl; while(m--){ int x; char c; cin>>x>>c; x--; auto it=ans.upper_bound(x);//找到大于x的第一个左端点 if(it==ans.end()){//找不到大于x的第一个左端点,即x后面没有句号 if(s[x]=='.'){ if(c=='.'){ cout<<sum<<endl; continue; } else{ it--; int l=*it,r=rr[l]; if(l==r){ ans.erase(it); cout<<sum<<endl; continue; } else{ rr[l]=r-1; sum--; } } } else{ if(c!='.'){ cout<<sum<<endl; continue; } else{ if(s[x-1]=='.'){ sum++; it--; int l=*it; rr[l]=x; } else{ ans.insert(x); } } } cout<<sum<<endl; continue; } if(it!=ans.begin()) { it--;//找到小于等于x的第一个左端点 int l=*it,r=rr[l];//区间 if(x>r){//不在区间中 if(c!='.'){ cout<<sum<<endl; continue; } else{ s[x]='.'; if(s[x-1]=='.'&&s[x+1]=='.'&&it!=(--ans.end())){ sum+=2; it++; rr[l]=rr[*it]; ans.erase(it); } else if(s[x-1]=='.'){ sum++; rr[l]=x; } else if(s[x+1]=='.'&&it!=(--ans.end())){ sum++; it++; rr[x]=rr[*it]; ans.erase(it); ans.insert(x); } } } else {//在区间中,x位置原本为句号 if(c=='.'){ cout<<sum<<endl; continue; } else{ if(l==r){ ans.erase(l); cout<<sum<<endl; continue; } else{ if(x==l||x==r){ sum--; if(x==l){ ans.erase(l); if(l+1<=r) { ans.insert(l+1); rr[l+1]=r; } } else { if(l<=r-1){ rr[l]=r-1; } } } else{ sum-=2; rr[x+1]=rr[l]; rr[l]=x-1; ans.insert(x+1); } } } } } else{//在第一个句号的前面 if(c!='.'){ cout<<sum<<endl; continue; } else{ s[x]='.'; if(s[x+1]=='.'){ rr[x]=rr[x+1]; ans.erase(x+1); ans.insert(x); } else{ ans.insert(x); rr[x]=x; } } } cout<<sum<<endl; } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
参考Codeforces Round #316 (Div. 2) - NotNight - 博客园 (cnblogs.com)
trick:
如果连续的两个点产生一个贡献,那么可以转化为点的个数减去段数,只要一直维护点的个数和段数即可
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int N=3e5+10; char s[N]; int n,m; void solve() { cin>>n>>m; cin>>(s+1); int cnt=0,num=0;//cnt表示一共有几段,num表示一共有几个点 for(int i=1;i<=n;i++){ if(s[i-1]!='.'&&s[i]=='.') cnt++; if(s[i]=='.') num++; } while(m--){ int x; char c; cin>>x>>c; if(c=='.'){ if(s[x]!='.'){ num++;//点的个数+1 if(s[x-1]=='.'&&s[x+1]=='.') cnt--; else if(s[x-1]!='.'&&s[x+1]!='.') cnt++; } s[x]=c; } else{ if(s[x]=='.'){ num--; if(s[x-1]=='.'&&s[x+1]=='.') cnt++; else if(s[x-1]!='.'&&s[x+1]!='.') cnt--; } s[x]=c; } cout<<num-cnt<<endl; } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
参考【CF1798D】Shocking Arrangement - 洛谷专栏 (luogu.com.cn)
长度为n的数组a,所有数的和为0
记最大值为max,最小值为min,均是确定的
重新排列数组a,使得最大的sum[r]-sum[l-1]小于max-min
无解输出No
最大最小,次大次小交替
这样不对,对于一个很小的负数,应该用很多正数去抵消
维护前缀和,如果为正数,那么填入负数,如果为负数,那么填入正数,因为这样任意前缀和超不过肯定在[min,max]之间,那么前缀和减前缀和肯定超不过max-min
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int N=3e5+10; int dp1[N],dp2[N]; int n; void solve() { cin>>n; deque<int>q1,q2; int ma=-2e9,mi=2e9; for(int i=1;i<=n;i++){ int x; cin>>x; ma=max(ma,x); mi=min(mi,x); if(x>=0) q1.push_back(x); else q2.push_back(x); } vector<int>ans; int sum=0; while(q1.size()&&q2.size()){ if(sum>=0){ sum+=q2.front(); ans.push_back(q2.front()); q2.pop_front(); } else{ sum+=q1.front(); ans.push_back(q1.front()); q1.pop_front(); } } while(q1.size()){ ans.push_back(q1.front()); q1.pop_front(); } while(q2.size()){ ans.push_back(q2.front()); q2.pop_front(); } if(ma==mi) cout<<"No"<<endl; else{ cout<<"Yes"<<endl; for(int i=0;i<(int)ans.size();i++) cout<<ans[i]<<' '; cout<<endl; } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--) { solve(); } return 0; }
长度为n的数组a(n为奇数)
一开始按照1,2,3,…n的顺序排列
评委选择了(n-1)/2对元素进行交换,剩下一个元素没有交换,目标是找到这个元素
最多问15次,每次问区间[l,r]是哪些元素,只能得到有哪些,顺序无法得知
参考CF1698D Fixed Point Guessing - 洛谷专栏 (luogu.com.cn)
当所问区间中原本就在该区间的个数为奇数时,说明答案在该qu’j
trick:
交互题可有根据询问次数猜测做法,比如这题最多问15次,由于 2 15 2^{15} 215大概1e4的级别,所以猜测二分
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; int n; void solve() { cin>>n; int l=1,r=n; while(l<r){ int mid=(l+r)/2; cout<<"? "<<l<<' '<<mid<<endl; cout.flush(); int cnt=0; for(int i=l;i<=mid;i++){ int x; cin>>x; if(x>=l&&x<=mid) cnt++; } if(cnt%2) r=mid; else l=mid+1; } cout<<"! "<<l<<endl; cout.flush(); } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--) { solve(); } return 0; }
参考题解 CF1099D 【Sum in the tree】 - 洛谷专栏 (luogu.com.cn)
n个顶点的树
直接让那些被删除的节点的a值为0就好,不是最优的,因为如果在交叉口,那么可以赋值,为多个分支作出前缀和的贡献,解决办法就是让被删除的节点的s值等于它的子树中最小的s
不能用子树,而是从上往下仅仅取和儿子节点的小的s值
无解的情况就是节点x的儿子子节点y到根节点的距离比x到根节点的距离小
trick:
1.熟悉对于dfs遍历的写法2.如果在交叉口会对多个分支作出前缀和的贡献,要使得所有节点权值之和最小,解决办法是让该节点等于它的儿子节点中小的那个
不用看子树,每个都是父子之间的联系,要判无解的话,只要有父子不满足即可
#include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int N = 1e5 + 10; int p[N], s[N]; int a[N]; int n; map<int,vector<int>>e; int ans; void dfs1(int u,int fa){ s[fa]=min(s[fa],s[u]); for(auto v:e[u]){ if(v==fa) continue; dfs1(v,u); } } void dfs2(int u,int fa){ if(s[u]<s[fa]){ cout<<-1<<endl; exit(0); } if(s[u]!=2e9){ ans+=s[u]-s[fa]; } for(auto v:e[u]){ if(v==fa) continue; dfs2(v,u); } } void solve() { cin >> n; for (int i = 2; i <= n; i++){ cin>>p[i]; e[p[i]].push_back(i); } for (int i = 1; i <= n; i++){ cin>>s[i]; if(s[i]==-1) s[i]=2e9; } dfs1(1,-1); ans=0; dfs2(1,-1); cout<<ans<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; // cin>>t; while (t--) { solve(); } return 0; }
构造一个n * m的矩阵,非负整数
使得对于任意一个4 * 4的子矩阵,左上角的2 * 2矩阵的异或和等于右下角的2 * 2矩阵的异或和,左下角的2 * 2矩阵的异或和等于右上角的2*2矩阵的异或和
同时不同数字最多
一定有解
异或有一个性质:0和1异或为1,2和3异或为1…
但是这样的话,第一列和第二列可以这样异或为1,但是第二列和第三列就不行了,不可行
参考The Very Beautiful Blanket 题解 - 洛谷专栏 (luogu.com.cn)
可以让任意的2 * 2的异或和都为0
trick:
1.关于异或和相等,可以让异或和均为0,通过相同抵消,若要让每个数尽量不同,可以乘或异或上一个2的幂次(很大的数)
2.构造矩阵,可以让a[i] [j]和i,j联系在一起
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int N=210; int a[N][N]; int n,m; void solve() { cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ a[i][j]=(i*(1ll<<9))^j; } } cout<<n*m<<endl; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cout<<a[i][j]<<' '; } cout<<endl; } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--) { solve(); } return 0; }
一共有n间房子,编号为1到n
一开始位于1
一共走k次,一共要走s个单位,每次到的房子都要与当前房子不同
YES,NO
用总距离s / 次数 得到平均每次走多少距离,记为cnt,如果大于n-1或者小于1,那么无解,如果等于n-1,但是cnt * k小于s,无解
否则,平均分
主要运用了平均分的技巧
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; int n,k,s; void solve() { cin>>n>>k>>s; int cnt=s/k; if(cnt>n-1||cnt<1){ cout<<"NO"<<endl; return; } if(cnt==n-1){ if(cnt*k<s){ cout<<"NO"<<endl; return; } } //平均分 int res=s%k;//res个cnt+1,k-res个cnt vector<int>ans; int flag=1; int path=1; for(int i=0;i<res;i++){ if(flag==1) path+=cnt+1; else path-=cnt+1; ans.push_back(path); flag^=1; } for(int i=0;i<k-res;i++){ if(flag==1) path+=cnt; else path-=cnt; ans.push_back(path); flag^=1; } cout<<"YES"<<endl; for(int i=0;i<(int)ans.size();i++) cout<<ans[i]<<' '; cout<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
一共有n名参赛选手
两两对局,输了立即淘汰,两个对局的人要求是对局数不能超过1
问比赛获胜者最多能参加多少场比赛
n达1e18,肯定是找规律了
发现n从2开始,数一个,答案为1,然后往下数两个,答案为2,再往下数三个,答案为3,…
二分找到小于等于n的第一个(1+2+3+…+k)+1=(1+k)* k / 2 +1
如果n刚好到(1+2+3+…+k)+ 1,那么为k个,如果n大一些的话,那么答案为k+1
可惜找错规律了,样本太少了,就手玩了小的数
要想参加n场比赛,最少需要至少参加n-1场的人数+至少参加n-2场的人数
其中参加n-1场的和参加n-2场的互不干扰,因为双方都是独立各自产出一个胜者,再pk
所以就是斐波那契数列,阶乘级别的
trick:
递归的思想,它的子问题的答案是固定的,且分解成的两个子问题互不干扰
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; int n; void solve() { cin>>n; int x=1,y=2,z=3; int ans=1; while(z<=n){ x=y; y=z; z=x+y; ans++; } cout<<ans<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
n * m的01矩阵
操作:选择两行,交换对应的两个元素
问最少几次使得每行1的个数相等
模拟题
统计1的总个数,除以n,就是每行1的个数,记为ave,如果不能整除,则无解
然后分别记录1的个数大于ave的行和小于ave的行,放入set1和set2中
然后大于ave的行去和小于ave的行交换,当大于ave的行刚好等于ave,那么就从set1中去除,同理,小于ave的行刚好等于ave时,就从set2中去除
但是这样超时了,反复的从第一列开始遍历
//超时 #include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; typedef pair<int,int>PII; int n, m; struct node{ int x,y,z; }; void solve() { cin >> n >> m; int sum = 0; vector<vector<int>>a(n + 1, vector<int>(m + 1)); set<PII>s1, s2; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; if (a[i][j] == 1) sum++; } } if (sum % n) { cout << -1 << endl; return; } int ave=sum/n; for (int i = 1; i <= n; i++) { int cnt = 0; for (int j = 1; j <= m; j++) { if(a[i][j]==1) cnt++; } if(cnt>ave) s1.insert({i,cnt}); else if(cnt<ave) s2.insert({i,cnt}); } vector<node>ans; while(s1.size()&&s2.size()){ auto t1=*s1.begin(),t2=*s2.begin(); int line1=t1.first,cnt1=t2.second,line2=t2.first,cnt2=t2.second; for(int j=1;j<=m;j++){ if(a[line1][j]==1&&a[line2][j]==0){ swap(a[line1][j],a[line2][j]); ans.push_back({line1,line2,j}); cnt1--,cnt2++; if(cnt1==ave&&cnt2==ave){ s1.erase(s1.begin()); s2.erase(s2.begin()); break; } else if(cnt1==ave){ s1.erase(s1.begin()); s2.erase(s2.begin()); s2.insert({line2,cnt2}); break; } else if(cnt2==ave){ s1.erase(s1.begin()); s2.erase(s2.begin()); s1.insert({line1,cnt1}); break; } } } } cout<<ans.size()<<endl; for(auto v:ans) cout<<v.x<<' '<<v.y<<' '<<v.z<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; cin >> t; while (t--) { solve(); } return 0; }
可以改进一下,对于每一列,记录大于ave且a值为1的行以及小于ave且a值为0的行,分为两个集合,以长度短的为标准,两两交换
参考CF1774D 题解 - 洛谷专栏 (luogu.com.cn)
trick:
1.一开始先想一个思路,出现问题,对症下药,比如超时了,反复的从第一列开始遍历,那么就对此改进,枚举列,对于某一列进行行上的操作
2.如果操作是对某一列的两行进行交换,那么就枚举列,让列不动
有很多题目都用固定d,比如固定长度,固定最小值,固定答案然后check
#include <bits/stdc++.h> #define endl '\n' #define int long long using namespace std; typedef pair<int,int>PII; int n, m; struct node{ int x,y,z; }; void solve() { cin >> n >> m; int sum = 0; vector<vector<int>>a(n + 1, vector<int>(m + 1)); map<int,int>mp;//mp[i]表示第i行有几个1 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; if (a[i][j] == 1) sum++,mp[i]++; } } if (sum % n) { cout << -1 << endl; return; } int ave=sum/n; vector<node>ans; for(int j=1;j<=m;j++){ vector<int>s1,s2; for(int i=1;i<=n;i++){ if(mp[i]>ave&&a[i][j]==1) s1.push_back(i); else if(mp[i]<ave&&a[i][j]==0) s2.push_back(i); } int len=min(s1.size(),s2.size()); for(int i=0;i<len;i++){ mp[s1[i]]--; mp[s2[i]]++; ans.push_back({s1[i],s2[i],j}); } } cout<<ans.size()<<endl; for(auto v:ans) cout<<v.x<<' '<<v.y<<' '<<v.z<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; cin >> t; while (t--) { solve(); } return 0; }
长度为n的序列
将1到x共x个数插入到序列中
得分:相邻元素差的绝对值之和
问最少得分
对于两个数,比如是说
2和10
它们的差值为8
如果在它们之间插入一个1,那么差值变为1+9=10,变大
如果在它们之间插入一个11,那么差值变为9+1=10,变大
所以应该插入数值在它们之间的数,比如说7,差值仍为8,同时按升序的顺序插入,当然如果是10 和 2,那么就按降序的顺序插入
所以最终就是大于序列中最大值的先不放进去,小于最小值的先放进去(其实就一个最大值x和一个最小值1就可,原因在于1 2 3 4和1 4差值是一样的)
其它全部放进去和最开始的差值没变化
然后想办法把1放在序列的最小值旁边,多的差值是2*(min-1)或者min-1,把x放在序列的最大值旁边,多的差值是2*(x-max)或者x-max
至于是否乘2,取决于最小值是否在边上,最大值是否在边上
当然,不一定非要放在最值旁边,因为有可能要乘2,直接放在边上就不用乘2,两者取min就可
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int N=2e5+10; int a[N]; int n,x; void solve() { cin>>n>>x; int maxn=0,minn=2e9; for(int i=1;i<=n;i++){ cin>>a[i]; maxn=max(maxn,a[i]); minn=min(minn,a[i]); } int ans=0; for(int i=2;i<=n;i++) ans+=abs(a[i]-a[i-1]); if(1<minn) ans+=min({2*(minn-1),abs(a[1]-1),abs(a[n]-1)}); if(x>maxn) ans+=min({2*(x-maxn),abs(a[1]-x),abs(a[n]-x)}); cout<<ans<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--) { solve(); } return 0; }
交互题
n*m的棋盘,有一个王放在棋盘的某个位置
目标猜出王的位置
最多问3次
问 (x,y),得到王到(x,y)的最小步数
做过类似的题,这个更简单些
第一次问(1,1)得到王所在的对角线(左下右上方向的对角线)
第二次问(1,n)得到左上右下方向的对角线
然后两条对角线交于一点
所以问两次就够了
问题在于如何计算交点
可以先求出第一条对角线右上的顶点坐标,然后求出它对应第二条对角线的第几条,然后再x++,y–找到交点,注意每次x++,y–是经过两条对角线
然后写下了如下错误代码
原来又读错题了,国王还可以斜着走,以为只能上下左右
题目一定要慢慢读,不然一个小时做一个假题
问(1,1)和(n,m),得到两个正方形,得到两个交点,然后问一个确定另一个
参考CF1797C Li Hua and Chess - 洛谷专栏 (luogu.com.cn)
trick:
1.题目一定要慢慢读,一个字一个字读,不可图快
2.三种距离:
欧式距离、曼哈顿距离、切比雪夫距离
欧式距离:我们平常所用的,对于某个顶点,与它欧式距离相同的轨迹是一个圆
曼哈顿距离:就是只能上下左右一格一格移动,对于某个定点,与它曼哈顿距离相同的轨迹是一条对角线
切比雪夫距离:就是不仅可以上下左右一格一格移动,还可以斜着一格一格移动,对于某个定点,与它切比雪夫距离相同的轨迹是一个正方形
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; int n,m; void ask(int x,int y){ cout<<"? "<<x<<' '<<y<<endl; cout.flush(); } void answer(int x,int y){ cout<<"! "<<x<<' '<<y<<endl; cout.flush(); } void solve() { cin>>n>>m; ask(1,1); int ans; cin>>ans; if(ans==0) { answer(1,1); return; } int line1=min(n,1+ans),col1=min(m,1+ans); ask(n,m); cin>>ans; if(ans==0) { answer(n,m); return; } int line2=max(1ll,n-ans),col2=max(1ll,m-ans); //得到两个交点 int x1=line1,y1=col2; int x2=line2,y2=col1; if(x1==x2&&y1==y2) answer(x1,y1); else if(x1!=x2&&y1!=y2){ if(x1>=1&&x1<=n&&y1>=1&&y1<=m){ ask(x1,y1); cin>>ans; if(ans==0) answer(x1,y1); else answer(x2,y2); } else answer(x2,y2); } else{ if(x1==x2){ if(y1>y2) swap(y1,y2); if(x1>=1&&x1<=n&&y1>=1&&y1<=m){ ask(x1,y1); cin>>ans; if(ans==0) answer(x1,y1); else answer(x1,y1+ans); } else{ ask(x2,y2); cin>>ans; if(ans==0) answer(x2,y2); else answer(x2,y2-ans); } } else if(y1==y2){ if(x1>x2) swap(x1,x2); if(x1>=1&&x1<=n&&y1>=1&&y1<=m){ ask(x1,y1); cin>>ans; if(ans==0) answer(x1,y1); else answer(x1+ans,y1); } else{ ask(x2,y2); cin>>ans; if(ans==0) answer(x2,y2); else answer(x2-ans,y2); } } } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--) { solve(); } return 0; }
一共有n行记录
操作:
1.将给定数字放入堆中
2.获取堆中最小元素的值
3.取出堆中最小元素
记录的顺序混乱了,导致有些操作不合法
要求插入一些记录(可以插入在任何位置),使得所有操作合法
问最少几条记录,并按顺序输出所有记录
数据结构:小根堆
模拟,当遇到不合法操作时,在它前面插入一些记录使得当前操作合法
trick:
1.需要注意的是这些stl自身操作的合法性,要注意判断是否为空
2.将数字(不止一位)转化为字符串
string s=to_string(x);
- 1
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; int n; void solve() { cin>>n; priority_queue<int,vector<int>,greater<int>>q; vector<string>ans; for(int i=0;i<n;i++){ string s; cin>>s; if(s=="insert"){ int x; cin>>x; q.push(x); string tmp="insert "; string t=to_string(x); tmp+=t; ans.push_back(tmp); } else if(s=="removeMin"){ if(q.empty()){ string tmp="insert 1"; q.push(1); ans.push_back(tmp); } string tmp="removeMin"; q.pop(); ans.push_back(tmp); } else if(s=="getMin"){ int x; cin>>x; if(q.empty()){ string tmp="insert "; string t=to_string(x); tmp+=t; ans.push_back(tmp); q.push(x); } while(q.top()<x&&q.size()){ string tmp="removeMin"; ans.push_back(tmp); q.pop(); } if(q.empty()||q.top()!=x){ string tmp="insert "; string t=to_string(x); tmp+=t; ans.push_back(tmp); q.push(x); } string tmp="getMin "; string t=to_string(x); tmp+=t; ans.push_back(tmp); } } cout<<ans.size()<<endl; for(auto v:ans) cout<<v<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
给定一个长度为2*n的序列q
求与序列q最接近的好的序列p,只需输出p和q的距离即可
好的:任意一半元素的乘积等于另一半元素的和
根据样例,
可以发现n为1时,将两个数变得一样即可
n为2时,可以全为2
然后第三个样例,发现不知道怎么构造,只能慢慢试,可以发现-1 -1 -1 2,然后进行推广,当n为偶数时,一种构造方式就是-1 -1 -1…n,对于为奇数不适用
另外还有一种万能的构造方法就是全0
检验这几种构造方式,取距离最小的即可
trick:
对于两个序列,要使得它们的距离最小,那么同时让它们升序
2.如果不理解样例,那么理解样例就是解题的关键
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int N=2e5+10; int a[2*N]; int n; void solve() { cin>>n; for(int i=1;i<=2*n;i++) cin>>a[i]; sort(a+1,a+1+2*n); if(n==1) cout<<abs(a[1]-a[2])<<endl; else if(n==2){ int ans1=0; for(int i=1;i<=2*n;i++) ans1+=abs(a[i]-2); int ans2=0; for(int i=1;i<=2*n-1;i++) ans2+=abs(a[i]+1); ans2+=abs(a[2*n]-n); int ans3=0; for(int i=1;i<=2*n;i++) ans3+=abs(a[i]); cout<<min({ans1,ans2,ans3})<<endl; } else if(n%2){ int ans=0; for(int i=1;i<=2*n;i++) ans+=abs(a[i]); cout<<ans<<endl; } else{ int ans1=0; for(int i=1;i<=2*n-1;i++) ans1+=abs(a[i]+1); ans1+=abs(a[2*n]-n); int ans2=0; for(int i=1;i<=2*n;i++) ans2+=abs(a[i]); cout<<min(ans1,ans2)<<endl; } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--) { solve(); } return 0; }
一共有n节车厢,编号为1到n,每节车厢编号不同
但是车厢并不是按照编号从小到大顺序排列,而是打乱顺序
操作:将一节车厢放到头或者尾
问最少几次操作,可以使得车厢按照编号从小到大顺序排列
最后的结果肯定是1,2,3,…n
如果一个数和比它小1的数逆序,那么可以把它放到最后面,按照从小到大的顺序
或者
如果一个数和比它大1的数逆序,那么就把它放在最前面,按照从大到小的顺序
预处理每个数的位置
然后错了,难道不止这两种
发现其实只要找到最长上升子序列,然后这些数不动,其它数动就行
但是最长上升子序列为O(n^2)
再次进行优化,可以求挨个最长上升子序列
证明见CF605A - 洛谷专栏 (luogu.com.cn)
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int N=1e5+10; int a[N]; int dp[N]; int n; void solve() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) dp[a[i]]=dp[a[i]-1]+1; int ans=0; for(int i=1;i<=n;i++) ans=max(ans,dp[i]); cout<<n-ans<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
初始1到n共n个整数
操作:将剩余所有数的最大公约数放到答案中,并删除任意一个元素
操作n次
问最终字典序最大是多少
当n小于等于3时,特判
相差为1的数,最大公约数肯定是1
如果不把所有奇数删掉,那么肯定最大公约数为1,所以先把所有奇数删掉,然后,只剩下偶数,最大公约数始终为2,然后最后是最大的偶数
有一点问题
先把除了2的幂次的偶数删掉,然后再从小到大把2的幂次删掉
另外,如果最大的偶数和最大的2的幂次的最大公因数等于最大的2的幂次和次小的2的幂次的最大公因数
又改成先保留2的幂次和最大的2的幂次一直加gcd(最大的2的幂次,次大的2的幂次)
还是错了
类似的题真的很难调,一直wa,可以wa到test 16
很难这种题,关于2的次幂,偶数
参考CodeForces 1059 C.Sequence Transformation (思维)_gcd的最大字典序 codeforces-CSDN博客
tirck:
类似的,关于2的次幂,偶数的,真的很难调
这题每次都可以变成原问题的子问题,就可以利用递归的思想,不一定非得用递归,可以用while循环
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; int n; void solve() { cin>>n; int t=1; while(n>3){ for(int i=1;i<=n-n/2;i++) cout<<t<<' '; n/=2; t*=2; } if(n==1) cout<<t<<endl; else if(n==2) cout<<t<<' '<<2*t<<endl; if(n==3) cout<<t<<' '<<t<<' '<<3*t<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
n*n的01矩阵
操作4运算:
1.循环上移所有行
2.循环下移所有行
3.循环左移所有列
4.循环右移所有列
操作次数不限
然后选择任意元素,任意数量,进行01反转,但是一次操作耗费1布尔值
问成为单元矩阵需要的最少布尔值
操作太复杂了,没啥思路
参考CF1660E Matrix and Shifts 题解 - 洛谷专栏 (luogu.com.cn)
trick:
一维数组:
循环右移->将数组在右边再复制一份
矩阵:
循环上移所有行->将矩阵在上面再复制一份
循环下移所有行->将矩阵在下面再复制一份
循环左移所有列->将矩阵在左边再复制一份
循环右移所有列->将矩阵在右边再复制一份2.对于sum [x] [y],可以写一个函数
int Sum(int x,int y){ return sum[x][y]; }
- 1
- 2
- 3
这样有什么用呢?比如需要前缀和,然后用到sum [-1] [-1],这样在数组是越界的,但是我们可以这样写
int Sum(int x,int y){ if(x<0||y<0) return 0; return sum[x][y]; }
- 1
- 2
- 3
- 4
然后直接用Sum(x,y)代替sum [x] [y]
3.对于01矩阵,想要快速求出对角线上1的个数,那么预处理sum [i] [j]=Sum(i-1,j-1)+a [i] [j];
#include<bits/stdc++.h> #include<cstdio> #define endl '\n' #define int long long using namespace std; const int N=2010; int a[2*N][2*N]; int sum[2*N][2*N]; int n; int Sum(int x,int y){ if(x>2*n||y>2*n) return 0; if(x<0||y<0) return 0; return sum[x][y]; } void solve() { cin>>n; int cnt=0;//总共1的个数 for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ scanf("%1lld",&a[i][j]); cnt+=a[i][j]; } } for(int i=0;i<2*n;i++){ for(int j=0;j<2*n;j++){ a[i][j]=a[i%n][j%n]; } } for(int i=0;i<2*n;i++){ for(int j=0;j<2*n;j++){ sum[i][j]=Sum(i-1,j-1)+a[i][j]; } } int ans=2e9; for(int i=0;i<n+1;i++){ for(int j=0;j<n+1;j++){ ans=min(ans,n+cnt-2*(Sum(i+n-1,j+n-1)-Sum(i-1,j-1))); } } cout<<ans<<endl; } signed main() { // ios::sync_with_stdio(false); // cin.tie(0); // cout.tie(0); int t=1; cin>>t; while(t--) { solve(); } return 0; }
f[i]为斐波那契数列的第i项
阶数为n的斐波那契矩形:高为f[n],宽为f[n+1]
给s[x][y]单元格着色
能否将矩形分解成刚好n+1个正方形,使得着色单元格位于边长为1的正方形,最多有一对边长相等的正方形,每个正方形的边长都是斐波那契数
YES,NO
参考CF 863 (Div. 3) D. Umka and a Long Flight(补题)-CSDN博客
trick:
1.出现数学式子,就列式子,推导
2.每次都可以变成原问题的子问题,递归的思想,可以用递归或者while循环
对于从矩形中切割最大正方形的问题就是递归的思想
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int N=50; int f[N]; int n,x,y; bool dfs(int n,int x,int y){ if(x==1&&y==1) return true; if(y>f[n-1]&&y<=f[n]) return false; if(y>f[n]) y-=f[n]; return dfs(n-1,y,x); } void solve() { cin>>n>>x>>y; if(dfs(n,x,y)) cout<<"YES"<<endl; else cout<<"NO"<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; f[0]=f[1]=1; for(int i=2;i<=50;i++) f[i]=f[i-1]+f[i-2]; cin>>t; while(t--) { solve(); } return 0; }
长度为n的字符串s,由小写字母组成
平衡字符串:每个字符出现的次数一样
构造一个平衡字符串t,尽量接近字符串s,一定有解
参考Codeforces Round #844 (Div.1 + Div.2) CF 1782 A~F 题解 - LegendStane - 博客园 (cnblogs.com)
trick:
1.结果已知,倒推,结果未知,但接近给定串,那么假定结果已知,自己构造不同的结果,然后倒推
如果有很多很多情况,然后在这些情况里取最值,那么就去枚举这些情况,分类需精炼,直接去枚举结果,然后倒推
2.如果想要以某种方式排序,直接自定义sort函数,写个cmp,自定义排序优先级
3.令ci表示字母i在s中的出现次数。对于字母i,如果它是选出的cnt个之一,且cnt≤ci,就把这cnt个i都放到s中字母i出现的对应位置;如果被选了但cnt>ci,就先放ci个,剩下的先不放写法(就看左半部分):
int use=min(ave,(int)e[ord[j]].size()); for(int k=0;k<use;k++) tmp[e[ord[j]][k]]=ord[j]+'a'; for(int k=0;k<ave-use;k++) left.push_back(ord[j]+'a');
- 1
- 2
- 3
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; int n; string s; map<int,vector<int>>e; bool cmp(int x,int y){ return e[x].size()>e[y].size(); } void solve() { cin>>n; cin>>s; e.clear(); for(int i=0;i<n;i++) e[s[i]-'a'].push_back(i); vector<int>ord; for(int i=0;i<26;i++) ord.push_back(i); sort(ord.begin(),ord.end(),cmp); int ans=2e9; string t; for(int i=1;i<=26;i++){//枚举字母种类 if(n%i) continue; int ave=n/i; string tmp(n,'-'); string left; for(int j=0;j<i;j++){//选数量最多的i种字母 int use=min(ave,(int)e[ord[j]].size()); for(int k=0;k<use;k++) tmp[e[ord[j]][k]]=ord[j]+'a'; for(int k=0;k<ave-use;k++) left.push_back(ord[j]+'a'); } int res=left.size(); for(int j=0;j<(int)tmp.size();j++){ if(tmp[j]=='-'){ tmp[j]=left.back(); left.pop_back(); } } if(res<ans){ ans=res; t=tmp; } } cout<<ans<<endl; cout<<t<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--) { solve(); } return 0; }
1*n的棋盘
棋盘上分布若干坦克,数量和位置均未知
我们在上空投掷炸弹,坦克第一次收到伤害会移到相邻的一格,第二次受到伤害直接摧毁
问最少投掷几个炸弹,摧毁所有坦克
只要在第i格单元格投掷炸弹,那么下一轮该单元格一定没有坦克
因为坦克会乱跑,为了保证摧毁坦克,得按照某种顺序,就是2,1,3,2,4,3…一共2*(n-1)
当n为2和3时,特判
然后错了,样例是2,4,6,…1,3,5,…,2,4,6…
确实是切实可行的
然后就过了
因为坦克只有 2条命,所以炸 3次必炸死。
以下为轰炸方法:
先炸偶数格的坦克,这时坦克会到奇数格;
然后炸奇数格的坦克,原本在奇数格的坦克就会到偶数格去,这时从偶数格移动过来的坦克就会被摧毁;
最后再炸一次偶数格内的坦克即可。
trick:
相邻一个,想到奇偶
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; int n; void solve() { cin>>n; if(n==2){ cout<<3<<endl; cout<<2<<' '<<1<<' '<<2<<endl; return; } if(n==3){ cout<<4<<endl; cout<<2<<' '<<1<<' '<<3<<' '<<2<<endl; return; } vector<int>ans; for(int i=2;i<=n;i+=2) ans.push_back(i); for(int i=1;i<=n;i+=2) ans.push_back(i); for(int i=2;i<=n;i+=2) ans.push_back(i); cout<<ans.size()<<endl; for(auto v:ans) cout<<v<<' '; cout<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
博弈
在a*b的长方形里面放半径为r的圆,不能重叠,谁不能放置谁输
问先手赢还是后手赢
先手如果可以放置在正中间,如果后手可以放置,那么始终对称放置
所以先手第一次可以放就赢 ,不能放就输
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; int a,b,r; void solve() { cin>>a>>b>>r; if(a>=2*r&&b>=2*r) cout<<"First"<<endl; else cout<<"Second"<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
最初序列只包含0
操作:
1.将xi添加到前 ai个元素(加法)
2.在序列末尾添加k
3.删除序列的最后一个元素(当元素个数大于等于2时)
共n次操作
问每次操作后所有数字的平均值
维护总和以及总个数比较简单,但是元素的更新比较难,当删除末尾元素时我们得知道末尾元素是什么
也可以维护,维护以x为右端点,1为左端点的区间加了多少,由于每次只需要末尾元素,所以我们当删除末尾元素时,就将此信息更新到它的前一个
注意,当删除末尾元素时,记得将它所记录的以它为右端点的区间加多少的信息清0
trick:
当出现某个问题时,就聚焦于这个问题进行改进,对症下药
#include <bits/stdc++.h> #include <cstdio> #define endl '\n' //#define int long long using namespace std; int n; void solve() { cin >> n; double sum = 0; map<int, int>mp; deque<int>q; q.push_back(0); while (n--) { int op; cin >> op; if (op == 1) { int a, x; cin >> a >> x; mp[a-1] += x; sum += a * x; } else if (op == 2) { int k; cin >> k; q.push_back(k); sum += k; } else if (op == 3) { int idx = q.size()-1; sum -= q[idx] + mp[idx]; mp[idx - 1] += mp[idx]; mp[idx]=0; q.pop_back(); } printf("%.10f\n", sum / (int)q.size()); } } signed main() { // ios::sync_with_stdio(false); // cin.tie(0); // cout.tie(0); int t = 1; // cin>>t; while (t--) { solve(); } return 0; }
长度为n的全排列p(1到n)
然后每连续3个元素作为一个三元组,一共n-2组
将三元组内部乱序,以及将不同的三元组整体乱序
还原出全排列p(一定 有解,不止一个解)
结果已知,根据结果倒推
如果个数为1的话,那么肯定在最两端
如果个数为2的话,那么在第二个位置或者倒数第二个位置
其它数个数均为3
然后就可以一个一个推了
trick:
三个元素组成一个三元组,如何进行标记:map<PII,vector<int>>e; e[{a,b}].push_back(c); e[{b,a}].push_back(c); //可以通过两个元素快速知道第三个元素
- 1
- 2
- 3
- 4
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int N=1e5+10; typedef pair<int,int>PII; struct node{ int x,y,z; }q[N]; int p[N]; bool vis[N]; int n; void solve() { cin>>n; map<int,int>mp; map<PII,vector<int>>e; for(int i=0;i<n-2;i++){ int a,b,c; cin>>a>>b>>c; mp[a]++,mp[b]++,mp[c]++; e[{a,b}].push_back(c); e[{b,a}].push_back(c); e[{a,c}].push_back(b); e[{c,a}].push_back(b); e[{b,c}].push_back(a); e[{c,b}].push_back(a); } vector<int>res1,res2; for(auto v:mp){ if(v.second==1) res1.push_back(v.first); else if(v.second==2) res2.push_back(v.first); } p[1]=res1[0]; if(e[{p[1],res2[0]}].size()) p[2]=res2[0]; else p[2]=res2[1]; memset(vis,false,sizeof vis); vis[p[1]]=true; vis[p[2]]=true; for(int i=3;i<=n;i++){ for(auto v:e[{p[i-1],p[i-2]}]){ if(!vis[v]){ p[i]=v; vis[v]=true; break; } } } for(int i=1;i<=n;i++) cout<<p[i]<<' '; cout<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
一棵树
有三个条件:
1.有n个顶点
2.直径为d
3.顶点1和其他顶点之间的最大距离为h
问是否有这样一棵树
如果d+1小于n,则无解
一个条件一个条件满足,先使得高度满足,直接1,2,3,…h+1
然后满足直径,直径d的范围必须在[h,2*h],否则无解
如果d大于h:
只需从根节点1再开一个分支,节点个数为d-h
最后只需要补足n个节点即可,继续开分支就行,剩下的节点都和1相连
如果d等于h:只需要补足n个节点即可,剩下的节点都和2相连
特判d为1的情况
trick:
如果要构造,满足多个条件 ,一个条件一个条件考虑
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; int n,d,h; void solve() { cin>>n>>d>>h; if(d+1>n){ cout<<-1<<endl; return; } if(d>2*h){ cout<<-1<<endl; return; } if(d==1){ if(n>=3){ cout<<-1<<endl; return; } } for(int i=2;i<=h+1;i++) cout<<i-1<<' '<<i<<endl; if(d>h){ d--; cout<<1<<' '<<h+2<<endl; for(int i=h+3;i<h+3+d-h;i++) cout<<i-1<<' '<<i<<endl; for(int i=h+3+d-h;i<=n;i++) cout<<1<<' '<<i<<endl; } else{ for(int i=h+2;i<=n;i++) cout<<2<<' '<<i<<endl; } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
初始列表只有一个元素n
操作:删除一个大于1的元素,然后在同样的位置插入x/2(下取整),x%2,x/2(下取整)
直到所有元素只有0和1
输出最终列表[l,r]中1的个数
参考「水」CF768B Code For 1 - 洛谷专栏 (luogu.com.cn)
trick:
递归层数过多,自己模拟小数据,来找一下规律
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int N=2e5+10; int res[N]; int n,l,r; void solve() { cin>>n>>l>>r; if(n==1){ cout<<1<<endl; return; } int cnt=0; res[++cnt]=n%2; while(n/2>1){ n/=2; res[++cnt]=n%2; } n/=2; reverse(res+1,res+1+cnt); int ans=0; for(int i=l;i<=r;i++){ if(i%2==1) ans+=n; else{ for(int j=cnt;j>0;j--){ if(i%(1ll<<j)==0){ ans+=res[j]; break; } } } } cout<<ans<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
一共有n个应用程序,每个屏幕分布k个应用程序,可能最后一个屏幕不足k个应用程序
需要按顺序启动m个应用程序,bi表示第i个应用程序的ID
模拟
利用map
记录并维护ID所在的屏幕
以及记录并维护ID是第几个应用程序
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int N=1e5+10; int a[N],b[N]; int n,m,k; void solve() { cin>>n>>m>>k; map<int,int>mp,mmp; int cnt=1; int sum=0; for(int i=1;i<=n;i++) cin>>a[i],mmp[a[i]]=i; for(int i=1;i<=n;i++){ mp[a[i]]=cnt; sum++; if(sum==k){ cnt++; sum=0; } } int ans=0; while(m--){ int id; cin>>id; ans+=mp[id]-1; ans++; if(mmp[id]==1) continue; //更新维护 int now=mmp[id];//现在的位置 int pre=now-1;//前一个的位置 int pre_id=a[pre];//先前的id swap(mmp[id],mmp[pre_id]); swap(a[now],a[pre]); swap(mp[id],mp[pre_id]); } cout<<ans<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
构造一个长度为n的全排列(1到n)
使得最长递增子序列的长度和最长递减子序列长度之和最小
试了一下小数据,感觉就是1到n升序,但是错了
看到最长的最小,可以想到平均分,平均分成cnt组,每组n/cnt个每组内部升序,然后组和组之间降序,那么答案为n/cnt+cnt
要使得答案最小,那么就要让cnt为sqrt(n)
或者用小数据打表找规律
void solve() { for(n=1;n<=10;n++){ int ans=2e9; vector<int>f; for(int i=1;i<=n;i++) a[i]=i; do{ int res1=0,res2=0; for(int i=1;i<=n;i++){ dp1[i]=1; for(int j=1;j<=i-1;j++){ if(a[j]<a[i]) dp1[i]=max(dp1[i],dp1[j]+1); } } for(int i=1;i<=n;i++){ dp2[i]=1; for(int j=1;j<=i-1;j++){ if(a[j]>a[i]) dp2[i]=max(dp2[i],dp2[j]+1); } } for(int i=1;i<=n;i++) res1=max(res1,dp1[i]); for(int i=1;i<=n;i++) res2=max(res2,dp2[i]); if(ans>res1+res2){ ans=res1+res2; f.clear(); for(int i=1;i<=n;i++) f.push_back(a[i]); } }while(next_permutation(a,a+n)); cout<<n<<endl; cout<<ans<<endl; for(auto v:f) cout<<v<<' '; cout<<endl; cout<<"--------------------"<<endl; } }
可以发现确实是这样的规律
trick:
1.最长递增子序列和最长递减子序列,长度最短也是1,单个元素都是满足递增子序列或者递减子序列的
2.最长的最小==>平均分
3.全排列函数next_permutation
int a[]={3,1,2}; sort(a,a+3); do{ for(int i=0;i<3;i++) cout<<a[i]<<' '; cout<<endl; }while(next_permutaton(a,a+3));
- 1
- 2
- 3
- 4
- 5
- 6
4.可以用小数据打表找规律
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; int n; void solve() { cin>>n; int cnt=sqrt(n); while(n>0){ for(int i=n-cnt+1;i<=n;i++){ if(i>0) cout<<i<<' '; } n-=cnt; } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
一个字符串s(仅由b和w组成)
操作:选择一个分界线,将字符串分成左右两半,然后将左边翻转,将右边翻转
操作次数不限
斑马的长度:b和w交替连续的长度
问能制作的斑马的最大长度
abc | def==>cba | fed
发现逆时针成了一个环,那么就是在这个环上找交替最长的长度,当然长度不能超过n
要想构造一个环,只需将字符串(数组)变成两倍
trick:
1.操作性题目,如果觉得毫无章法,无迹可寻,那么最好的一个方法是自己具象化一个对象,然后按照操作操作一次(就一次),然后看和之前有什么变化联系
2.要想构造一个环,只需将字符串(数组)变成两倍
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; string s; void solve() { cin>>s; int n=s.size(); s+=s; int ans=0; int cnt=1; for(int i=1;i<2*n;i++){ if(s[i]!=s[i-1]) cnt++; else { ans=max(ans,cnt); cnt=1; } } ans=max(ans,cnt); ans=min(ans,n); cout<<ans<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
一共有n本书,wi表示编号为i的书的重量
一共读m天,bi表示第i天要读的书的编号
每次读书,比如读x,需要把它上面的书都抬起来(有重量)
每次读了书x,就把它放在最上面
问最少需要抬多少重量的书,我们可以自定最开始书的放置顺序
既然读了x肯定要把x放在最上面,增加后续拿别的书的总重量,那么我们就要让x上面的总重量越小越好
所以,按照拿书的顺序从上到下放置书,初始顺序确定了
关键是如何计算书x上面的总重量
数据比较小,考虑暴力
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int N=1010; int w[N],b[N]; int n,m; void solve() { cin>>n>>m; deque<int>q; map<int,int>mp; for(int i=1;i<=n;i++) cin>>w[i]; for(int i=1;i<=m;i++){ int x; cin>>x; b[i]=x; if(!mp[x]){ q.push_back(x); mp[x]=1; } } int ans=0; for(int i=1;i<=m;i++){ int sum=0; int t; for(int j=0;j<(int)q.size();j++){ if(q[j]==b[i]){ ans+=sum; t=j; break; } sum+=w[q[j]]; } q.erase(q.begin()+t); q.push_front(b[i]); } cout<<ans<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
n个节点的树
1为根节点
在每个叶子节点上放置一个灯泡,颜色可以不同
快乐节点:该节点的子树的所有灯泡颜色不同
问快乐节点数大于等于1所需的最少颜色,大于等于2,3,…n
参考codeforces1056D_ Decorate Apple Tree_牛客博客 (nowcoder.net)
反过来想,先考虑n的情况,要n个happy节点,那就是所有叶子都染不同颜色,然后考虑n-1的情况,就去掉一个根节点,那么就变成两棵独立的子树,那只要保证那个叶子节点多的那个子树的叶子染不同的颜色即可,另外的兄弟子树的叶子不管染什么色肯定不会超过这一棵的颜色数,所以其实就是第二大的叶子数的子树,所以答案就是dfs一遍预处理出每个节点对应的子树的叶子节点数,排序输出即可
只要求出每个节点子树的叶子节点个数即可,存入数组,从小到大排序,第i个就表示i个快乐节点所需的最少颜色数
trick:
1.节点的子树:包含该节点以及往下的所有节点
2.图论一定要特判n为1和m为1
3.求编号为id的子树的叶子节点数:
map<int,vector<int>>e; void dfs(int u,int fa){ if(e[u].size()==1&&u!=1){ num[u]=1; return; } for(auto v:e[u]){ if(v==fa) continue; dfs(v,u); num[u]+=num[v]; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
4.对于从 1到 n 的每个 k ,要使快乐结点的数量大于或等于 k ,至少需要多少种不同颜色的灯泡?
像这种问法 ,1到n的情况都要回答,它们之间往往是有联系的
可以先考虑1的情况,然后一个一个往后推
也可以先考虑n的情况,然后一个一个往前推
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int N=1e5+10; int num[N]; int n; map<int,vector<int>>e; void dfs(int u,int fa){ if(e[u].size()==1&&u!=1){ num[u]=1; return; } for(auto v:e[u]){ if(v==fa) continue; dfs(v,u); num[u]+=num[v]; } } void solve() { cin>>n; if(n==1){ cout<<1<<endl; return; } for(int i=2;i<=n;i++){ int x; cin>>x; e[i].push_back(x); e[x].push_back(i); } dfs(1,-1); sort(num+1,num+1+n); for(int i=1;i<=n;i++) cout<<num[i]<<' '; cout<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--) { solve(); } return 0; }
n个顶点的树
操作:找两个相连的点u,v,然后删去它们之间的边,将u和x相连(u和x本来不相连)
在q天里
如果第i天没有两个叶子节点距离正好为di,是不允许的,因此需要进行以上操作最多一次,如果不需要执行操作,那么输出-1
注意,只要有两片距离为di的叶子就行 ,注意,只要有就行
一开始自己先构造一棵树,直接构造1到n的一条链
然后每次移动节点n,将n和节点d相连
trick:
构造题都是往简单特殊的方向想,主打一个妙字,不要想复杂
#include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; int n,q; void solve() { cin>>n>>q; int p=n-1; for(int i=2;i<=n;i++) cout<<i-1<<' '<<i<<endl; for(int i=0;i<q;i++){ int d; cin>>d; if(d==p) cout<<-1<<' '<<-1<<' '<<-1<<endl; else{ cout<<n<<' '<<p<<' '<<d<<endl; p=d; } } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--) { solve(); } return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。