CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!)

构造一个长度为n的数组a
满足循环右移数组中恰好有k个是升序的

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int n,k;
void solve() {cin>>n>>k;if(k==1){for(int i=1;i<=n;i++) cout<<i<<' ';cout<<endl;}else if(n==k){for(int i=1;i<=n;i++) cout<<1<<' ';cout<<endl;}else{cout<<-1<<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,n]）

构造一个长度为n的排列p，使得ai=mex(p1,p2,…pi)-pi
一定有解

首先，如果a1为负数x的话，那么p1为-x
如果a1为1的话，那么p1为0

维护mex，也就是缺mex这个数
如果令pi为mex的话，那么结果是mex+1-mex=1
否则，令pi为x，则mex-x=a[i]==>x=mex-a[i]
不对

应该倒着推，mex(p1,p2,p3,…pn)=n，所以n-p[n]=a[n]>p[n]=n-a[n]
然后求出倒数第二个mex，以此类推，mex-p[i]=a[i]>p[i]=mex-a[i]

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=2e5+10;
int a[N];
int p[N];
int n;
void solve() {cin>>n;set<int>s;for(int i=1;i<=n;i++) cin>>a[i];p[n]=n-a[n];s.insert(p[n]);for(int i=n-1;i>=1;i--){p[i]=*s.begin()-a[i];s.insert(p[i]);}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;
}

边长为n的正多边形，顶点按照顺时针方向从1到n

贝西选择了x个顶点，以及还可以选择其它顶点最多y个（easy版本y为0）
然后切出不相交的对角线，问最多切成几个三角形

问分成几块问题，往往是通过数线产生的交点个数或者有效点的个数
问切成几个三角形，答案为有效的个数-2
如果两个有效点之间恰好有1个点，那么中间的那个点也是有效点

1 2 3 4 5 >2个
1 2 3>1个
1 2 3 4 5 6==>3个

trick：

问分成几块问题，往往是通过数线产生的交点个数或者有效点的个数

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int n,x,y;
void solve() {cin>>n>>x>>y;vector<int>res;for(int i=0;i<x;i++){int d;cin>>d;res.push_back(d);}int ans=x;sort(res.begin(),res.end());for(int i=1;i<(int)res.size();i++){if(res[i]==res[i-1]+2) ans++;}int len=res.size();int a=res[len-1]+2;if(a>n) a-=n;if(a==res[0]) ans++;cout<<ans-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;
}

如果两个有效的点之间的个数为奇数，记为cnt，那么只需要(cnt-1)/2个点就可以产生cnt个有效点，如果为偶数的话，那么需要cnt/2个点产生cnt个有效点

所以优先奇数

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int n,x,y;
void solve() {cin>>n>>x>>y;vector<int>res;for(int i=0;i<x;i++){int d;cin>>d;res.push_back(d);}int ans=x;int len=res.size();sort(res.begin(),res.end());vector<int>ji,ou;int l=res[0]+n-res[len-1]-1;if(l%2&&l) ji.push_back(l);else ou.push_back(l);for(int i=1;i<len;i++){int l=res[i]-res[i-1]-1;if(l%2) ji.push_back(l);else ou.push_back(l);}sort(ji.begin(),ji.end());sort(ou.begin(),ou.end());for(int i=0;i<(int)ji.size();i++){if(ji[i]/2<=y){ans+=ji[i];y-=ji[i]/2;}else {ans+=y*2;y=0;break;}}for(int i=0;i<(int)ou.size();i++){if(ou[i]/2<=y){ans+=ou[i];y-=ou[i]/2;}else{ans+=y*2;y=0;break;}}cout<<ans-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;
}