ural 1275. Knights of the Round Table

有 \(n\) 个围着圆桌，其中第 \(i\) 个人有 \(a_i\) 个盘子，服务员每个可以给相邻为 \(k\) 的两个人各自带来/带走一个盘子 , 需要求出最少的方案数使得最后每个人都有 \(F\) 个盘子 .

\(1\leq n\leq 1000,1\leq k\leq n-1,0\leq a_i,F\leq1000\)

考虑操作 \((i-k,i)\) 的操作数量为 \(x_i\) .

\(x_0+x_k=F-a_0\)

\(x_1+x_{k+1}=F-a_1\)

\(\cdots\)

\(x_{n-1}+x_{n-1+k}=F-x_{n-1}\)

这里的下标都是模 \(n\) 后的 .

此时有 \(n\) 个方程，有 \(n\) 个未知量，但是还是需要分成几种情况讨论 .

第一种特殊情况是 \(2k=n\)，此时需要 \(a_i=a_{i+k}\) . 操作很好构造 .

第二种操作是有 \(m\) 个方程，\(m\) 个未知量，可以设其中一个量为 \(x\) 其他的所有的位置量都可以用 \(x\) 表示，最后绕了一圈后可以得到一个表示 \(b+x\) 或者 \(b-x\) .

如果 \(b-x=x\) ，那么 \(b\) 是偶数，其他的值可以直接求出 .

如果 \(b+x=x\) ，那么 \(b=0\) ，对于每个 \(x_i=x+b_i\ /\ x_i=-x+b_i\) . 其中 \(b_i\) 或者 \(-b_i\) 就是临界点，可以 \(O(n)\) 处理出最小值 .

时间复杂度 : \(O(n+ans)\) .

空间复杂度 : \(O(n)\)

首先要先输出 + 再输出 - ，其次，输出操作的时候不能用 \(\rm{vector}\) 保存，会超出空间限制 .

code

#include
using namespace std;
char in[100005];
int iiter=0,llen=0;
inline char get(){
	if(iiter==llen)llen=fread(in,1,100000,stdin),iiter=0;
	if(llen==0)return EOF;
	return in[iiter++];
}
inline long long rd(){
	char ch=get();while(ch<'0'||ch>'9')ch=get();
	long long res=0;while(ch>='0'&&ch<='9')res=(res<<3)+(res<<1)+ch-'0',ch=get();
	return res;
}
inline void pr(long long res){
	if(res==0){putchar('0');return;}
	static int out[20];int len=0;
	while(res)out[len++]=res%10,res/=10;
	for(int i=len-1;i>=0;i--)putchar(out[i]+'0');
}
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int N=1e3+10;
int n,k,F;
int a[N];
class node{public:int k,b;}eq[N];
vectorv;
bool ok[N];
int ans[N];
inline void print(){
	int res=0;
	for(int i=0;i=0)continue;
		for(int j=0;j<-ans[i];j++){
			pr((i-k+n)%n+1);putchar(' ');
			pr(i+1);putchar(' ');
			putchar('-');putchar('\n');
		} 
	}
}
void work_special(){
	for(int i=0;iv){
	vectortmp;
	for(int i=0;i<(int)v.size();i++)tmp.pb((node){eq[v[i]].k,eq[v[i]].b});
	sort(tmp.begin(),tmp.end(),cmp);
	int sk=0,sb=0;
	for(int i=0;i<(int)tmp.size();i++){
		if(tmp[i].k<0)sk+=tmp[i].k,sb+=tmp[i].b;
		else sk-=tmp[i].k,sb-=tmp[i].b;
	}
	int mn=tmp[0].k<0?tmp[0].b:-tmp[0].b,res=sk*mn+sb;
	for(int i=0;i+1<(int)tmp.size();i++){
		sk+=2;sb+=tmp[i].k<0?-2*tmp[i].b:2*tmp[i].b;
		int l=(tmp[i].k<0?tmp[i].b:-tmp[i].b),r=(tmp[i+1].k<0?tmp[i+1].b:-tmp[i+1].b);
		if(sk<0&&sk*r+sb0&&sk*l+sbv,int x){
	for(int i=0;i<(int)v.size();i++)ans[v[i]]=eq[v[i]].k*x+eq[v[i]].b;
}
bool work(vectorv){
	node tmp=(node){-eq[v.back()].k,F-a[v.back()]-eq[v.back()].b};
	if(tmp.k==eq[v[0]].k){
		if(tmp.b!=0){
			puts("-1");
			return false;
		}
		solv1(v);
		return true;
	}else{
		if(tmp.b&1){
			puts("-1");
			return false;
		}
		solv2(v,tmp.b/2);
		return true;
	}
}
int main(){
	n=rd();k=rd();F=rd();
	for(int i=0;i