题目是做梦梦到的。
先考虑什么情况下无解。
- 当 时。因为当需要操作 次时 长度至少为 。
- 当 时。因为假设 是符合构造条件，那么序列定形如 。因为 ，故 。然而 不能有重复元素，故无解。
- 当 且 。当 时显然有唯一合法构造 。对于其他情况，由于 不能有重复元素，故无解。
Subtask #1
大概就是留给选手一个暴力乱搞的部分分。
Subtask #2
输出 即可。
Subtask #3
同样是先要判掉无解。
我想到的最简单的构造是令 。
可以发现 ，即构造合法。
参考代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int p,t;
cin>>p>>t;
while(t--){
int n,k;
cin>>n>>k;
if(k>=n){
cout<<"-1\n";
continue;
}
for(int i=1;i<=n;i++){
cout<<i<<" ";
}
cout<<"\n";
for(int i=1;i<=n;i++){
if(i==1)cout<<"1 3 -1 2\n";
else if(i==2)cout<<"1 3 -1 1\n";
else cout<<"1 1 1 "<<i-1<<"\n";
}
}
return 0;
}
Subtask #4
这是我想到这档部分分最好写的构造方法。
容易联想到构造的序列和序列前缀和有关：
令 （）。
对于 ，有合法方案 。
对于 ，有合法方案 。
显然，，它在 时有最大值 。
故构造合法。
复杂度 ，瓶颈在于输出。可以通过此档部分分。
参考代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int a[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin>>T;
while(T--){
int n,k;
cin>>n>>k;
if(n==1 && k==0){
cout<<"0\n\n";
continue;
}
if(k>=n || k<=1){
cout<<"-1\n";
continue;
}
for(int i=1;i<=k;i++){
a[i]=i;
}
int pre_sum=k*(k-1)/2;
for(int i=k+1;i<=n;i++){
a[i]=pre_sum+a[i-1];
}
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
cout<<"\n";
for(int i=1;i<=k;i++){//前k个数
for(int j=1;j<=k;j++)if(i!=j){
cout<<"-1 "<<j<<" ";
}
cout<<"1 "<<k+1<<"\n";
}
for(int i=k+1;i<=n;i++){
for(int j=1;j<k;j++){
cout<<"1 "<<j<<" ";
}
cout<<"1 "<<i-1<<"\n";
}
}
return 0;
}
Subtask #5
构造方法有些劣，欢迎补充。
Subtask #4 可以得出一定的启发，然后就得到了下面的方法。
先不考虑 ，分块，块长为 。对于每个整块，区间为 ，前 个元素依次记为当前最小的未被使用过的正整数。然后 。
若有余块，那么余块在的区间是 。定义 （即余块前的最后一个整块的元素和），然后 （）。 感性理解，这样构造的序列内所有的元素都不重复。
对于每个整块，区间为 。前 个元素都有 ，第 个元素有 。对于余块也有类似如此的情况符合题目要求。当 时 有最大值 （卡的非常的死）。
故构造合法。
所以最后构造完之后把 和输出方案都按规则排序即可。
复杂度 ，常数略大。可以通过此档部分分。
参考代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=1e3+10;
int f[N];
int a[M];
int id[M][M],s[M][M];
int g[M];
int _g[M];
int cnt=1;
void init(){
memset(f,0,sizeof(f));
for(int i=1;i<M;i++)g[i]=i;
memset(a,0,sizeof(a));
f[0]=1;
cnt=1;
return;
}
int mex(){//返回mex
while(f[cnt])cnt++;
f[cnt]=1;
return cnt;
}
bool cmp(int A,int B){
return a[A]<a[B];
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int p,T;
cin>>p>>T;
while(T--){
init();
int n,k;
cin>>n>>k;
if(n<=k || k==1){
cout<<"-1\n";
continue;
}
if(k==0){
if(n!=1)cout<<"-1\n";
else cout<<"0\n";
continue;
}
//构造整块
int t=n/(k+1);
for(int i=1;i<=t;i++){
for(int j=1;j<=k;j++){
a[j+(i-1)*(k+1)]=mex();
a[i*(k+1)]+=a[j+(i-1)*(k+1)];
}
f[a[i*(k+1)]]=1;
}
//构造余块
int sum=0;
for(int i=1;i<=k+1;i++){
sum+=a[t*(k+1)-i+1];
}
for(int i=t*(k+1)+1;i<=n;i++){
a[i]=sum-a[i-k-1];
}
//处理整块
for(int i=1;i<=t;i++){
for(int j=1;j<=k;j++){//当前到的位置
id[j+(i-1)*(k+1)][1]=i*(k+1);
s[j+(i-1)*(k+1)][1]=1;
int c=1;
for(int x=1;x<=k;x++)if(x!=j){
c++;
id[j+(i-1)*(k+1)][c]=x+(i-1)*(k+1);
s[j+(i-1)*(k+1)][c]=-1;
}
}
for(int j=1;j<=k;j++){
id[i*(k+1)][j]=j+(i-1)*(k+1);
s[i*(k+1)][j]=1;
}
}
//处理余块
for(int i=t*(k+1)+1;i<=n;i++){
int c=1;
for(int j=t*(k+1);j>=(t-1)*(k+1)+1;j--)if(j!=i-k-1){
id[i][c]=j;
s[i][c]=1;
c++;
}
}
sort(g+1,g+n+1,cmp);
for(int i=1;i<=n;i++){
_g[g[i]]=i;
}
for(int i=1;i<=n;i++){
cout<<a[g[i]]<<" ";
}
cout<<"\n";
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
cout<<s[g[i]][j]<<" "<<_g[id[g[i]][j]]<<" ";
}
cout<<"\n";
}
}
return 0;
}
：余块指的是分块中最后一个长度小于 的块。
：下面是证明。
假设一共有 个整块，第 个整块的元素为 。
整块部分
显然有 ，即当构造完第 个整块时， 一定时已构造元素中严格最大的那一个。所以说 两两不相同。又因为在构造过程中已经满足了其他元素都两两不同，所以整块部分是没有重复元素的。
余块部分
显然有 ，所以根据构造方法，余块内的元素是严格递减的，所以整块部分是没有重复元素的。
整合部分
根据构造方法，余块的最后一位大于最后一块整块的最后一位，所以原序列中是没有重复元素的。
：对于每个 ，均存在一组下标 （， 个下标互不相同，且 ）以及符号系数 或 ，使得：
暂无评论