A

模拟

两个序列每次可以选一个位置，如果$a_i>b_i$则给$a_i$减一。问最多进行多少次操作

计算$\sum max(a_i-b_i,0)$即可

void solve(void){
	int n;
	cin>>n;
	vi a(n+1),b(n+1);
	rep(i,1,n){
		cin>>a[i];
	}
	rep(i,1,n){
		cin>>b[i];
	}
	int ans=0;
	rep(i,1,n){
		if(a[i]>b[i]){
			ans+=a[i]-b[i];
		}
	}
	cout<<ans+1<<'\n';
	
}

B

构造 贪心

构造一个序列，满足任意一个长度大于一的子区间元素和都大于0，且相邻元素乘起来小于0。要求这个序列取绝对值后的字典序尽量小

考虑所有长度为2的子数组，想要乘起来负的，需要一正一负，想要绝对值后字典序尽量小，显然最小的方式就是第一个是-1，第二个是2。

再考虑长度3子数组，一个正数两边会有两个-1，想要和大于0，还要字典序尽量小，中间那个应该用3。

所以方案就是$-1,3,-1,\mathrm{3...}$这样，注意如果是个3结尾，这个3只有左边有一个-1，可以用2，字典序更小

void solve(void){
	int n;
	cin>>n;
	if(n==2){
		cout<<-1<<' '<<2<<'\n';
	}
	else{
		vi ans(n+1);
		rep(i,1,n){
			if(i%2){
				ans[i]=-1;
			}
			else{
				ans[i]=3;
			}
		}
		if(n%2==0){
			ans[n]=2;
		}
		rep(i,1,n){
			cout<<ans[i]<<' ';
		}
		cout<<'\n';
	}
	
}
	
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int test=1;	
	
    cin>>test;
    while(test--){
    	solve();	
    }
    
}

C

数论

给一个集合s，每次可以对一个元素$x$，变成$x+k$或$|x-k|$。问能否任意操作后变成另一个集合t？

注意到这个操作不看绝对值的话就是就是加减k，显然这样可以变成所有模k同余的其它正数，考虑绝对值，特殊情况只有在减完会变成负的的时候，原本是模k余r的话，会变成模k余k-r，然后接下来又可以变成所有模k同余的正数。

所以，s里的任何一个元素，假设x模k等于r,都可以变成模k余r或k-r的任意数字。

我们可以把s,t每个数都对k取模，并且余数取r,k-r里较小的，然后比较这两个余数集合是否相等即可，相等就可以变成一样的

void solve(void){
	int n,k;
	cin>>n>>k;
	map<int,int>s,t;
	rep(i,1,n){
		int x;
		cin>>x;
		x%=k;
		s[min(x,k-x)]++;
	}
	rep(i,1,n){
		int x;
		cin>>x;
		x%=k;
		t[min(x,k-x)]++;
	}
	if(s==t){
		cout<<"yes\n";
	}
	else{
		cout<<"no\n";
	}
}

D

树论

每次可以做一个并差集路径压缩操作，把一条链上所有点，都变成一个端点的直接儿子，问最少操作多少次可以变成一个菊花？

根是不确定的，考虑枚举根，对于一个根，需要的操作次数就是不相交的链的个数，也就是深度大于1的叶子个数。可以先统计所有叶子的个数，然后每次确定一个根，实际上只会把根节点直接相邻的叶子变成深度等于1的，也就是这个根的答案可以在$O(d_i)$复杂度算出，$d_i$是$i$点的度

那么直接枚举所有根，枚举每个根的相邻点计算答案，取min即可，复杂度为$O(\sum d_i)=O(n)$

void solve(void){
	int n;
	cin>>n;
	vvi g(n+1);
	vi in(n+1);
	rep(i,1,n-1){
		int u,v;
		cin>>u>>v;
		in[u]++,in[v]++;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	int cnt=0;
	rep(i,1,n){
		if(in[i]==1){
			cnt++;
		}
	}
	int ans=1e18;
	rep(i,1,n){
		int cur=cnt;
		for(int v:g[i]){
			if(in[v]==1){
				cur--;
			}
		}
		if(in[i]==1)cur--;
		ans=min(ans,cur);
	}
	cout<<ans<<'\n';
}

E

归纳法 从一侧开始贪心

每个位置$i(i<n)$可以执行至多一次$a_i=a_i\oplus a_{i+1}$，问能否使得序列a与b相等

直接想不好想，先找有哪些是确定的。对于一个序列上的问题，两端一般是确定的，因为两端元素只有一边需要考虑，另一边啥也没有。在这里就是$a_n$是无法进行任何操作的，那么想让$a=b$，一定有$a_n=b_n$

$a_n$确定了，$a_{n-1}$也变成只用考虑一边了，我们来看看$a_{n-1}$需要什么条件，显然要么$a_{n-1}=b_{n-1}$，要么$a_{n-1}\oplus a_n=b_{n-1}$，由于$a_n=b_n$，显然也可以是$a_{n-1}\oplus b_n=b_{n-1}$

那么大胆猜测这三个等式就是对于每个位置的条件，也就是对于其他所有位置，三个等式至少要成立一个，否则无解

有了假设了，可以从最后面开始，往前递推，也就是一个类似归纳法的东西，假设$a[+1i,n]=b[i+1,n]$已经都相等了，现在我们需a_i=b_i$可以达到当且仅当上面的三个等式至少有一个成立

那其实前两个等式显然是对的，第三个等式，由于保证了后缀都可以相等，也就是有$a_{i+1}=b_{i+1}$，把这个带入第二个等式，就能得到第三个等式。所以我们相当于证明了，若$[i+1,n]$成立，$[i,n]$也成立，并且我们又证明了初始条件：$[n,n]$处显然是成立的，那么整个序列上我们这个命题就都是对的

oid solve(void){
	int n;
	cin>>n;
	vi a(n+1),b(n+1);
	rep(i,1,n)cin>>a[i];
	rep(i,1,n)cin>>b[i];
	if(a[n]!=b[n]){
		cout<<"no\n";
		return;
	}
	rep(i,1,n-1){
		int x=a[i]^a[i+1];
		int y=a[i]^b[i+1];
		if(a[i]==b[i]||x==b[i]||y==b[i]);
		else{
			cout<<"no\n";
			return;
		}
	}
	cout<<"yes\n";
}

F

转化 推式子 双指针计数

很有意思的一个题。

给两个01序列a,b，生成一个网格图，其中$c_{ij}=a_i\oplus b_j$

每次操作可以反转a或b的某一个元素，网格图上只有全0路径才可以走，设从$(1,1)$出发，走到$(x,y)$的最小操作次数为$f(x,y)$，问$\sum f(x,y)$，也就是到达所有点的操作次数和，对于每个终点都是独立计算的

先不说求和，来看看对于一个终点怎么算？想从$(x,y)$移动到$(x+1,y)$的话，需要这俩点都是0，也就是$a_x\oplus b_y=a_{x+1}\oplus b_y$，也就是$a_x=a_{x+1}$

所以想走到$(x,y)$要求$a[1,x]$全部相同，且$b[1,y]$全部相同，且a和b全都相同（异或要是0），代价就是$min(pre{a}_i+pre{b}_j,i-pre{a}_i+j-pre{b}_j)$，其中$prea,preb$是$a,b里1$的个数的前缀和，也就是要么吧两个前缀全变成1，要么把两个前缀全变成0

如果只求一个，我们前缀和查询即可，但现在要求和，这个min的形式显然不方便求和，考虑把他转化一下，$min(x,y)=(x+y)/2-|x-y|/2$，所以

$min(pre{a}_i+pre{b}_j,i-pre{a}_i+j-pre{b}_j)$
$=\frac{1}{2}(i+j-|2pre{a}_i-i+j-pre{b}_j|)$

$i+j$对所有$(i,j)$求和是简单的，可以对$i,j$分别求和然后加起来

${\sum }_{i=1}^n{\sum }_{j=1}^{n}j={\sum }_{i=1}^n\frac{n(1+n)}{2}=\frac{n^2(1+n)}{2}$

这是对$j$求和，对$i$也是类似的

问题是后面这个绝对值，加法绝对值不好做，考虑转成减法，设$a{a}_i=2pre{a}_i-i,b{b}_i=2pre{b}_i-i$，则有

$|2pre{a}_i-i+j-2pre{b}_j|$
$=|a{a}_i-b{b}_j|$

到这里，就比较显然了，做差的绝对值，我们考虑把绝对值打开，对于所有比$a{a}_i$大的$b{b}_j$，就是$b{b}_j-a{a}_i$，对于比$a{a}_i$小的$b{b}_j$就是$a{a}_i-b{b}_j$

那么可以先把$aa,bb$排序，扫描$aa$的同时，双指针维护比$a{a}_i$大的元素个数，元素和，比它小的元素和，元素个数，答案就是$su{m}_1-cn{t}_1\ast a{a}_i+cn{t}_2\ast a{a}_i-su{m}_2$，当然也可以二分。

void solve(void){
	int n;
	cin>>n;
	
	vi a(n+1),b(n+1);
	rep(i,1,n){
		char c;
		cin>>c;
		a[i]=c-'0';
	}	
	rep(i,1,n){
		char c;
		cin>>c;
		b[i]=c-'0';
	}
	int ans=n*n*(n+1);
	int pre=0;
	vi aa,bb;
	rep(i,1,n){
		pre+=a[i];
		aa.push_back(i-2*pre);
	}
	pre=0;
	rep(i,1,n){
		pre+=b[i];
		bb.push_back(2*pre-i);
	}
	sort(aa.begin(),aa.end());
	sort(bb.begin(),bb.end());
	
	int sum1=0,sum2=0;
	for(int x:bb){
		sum2+=x;
	}
	for(int i=0,j=0;i<n;i++){
		while(j<n&&bb[j]<=aa[i]){
			sum1+=bb[j];
			sum2-=bb[j];
			j++;
		}
		ans-=j*aa[i]-sum1;
		ans-=sum2-(n-j)*aa[i];
	}
	cout<<ans/2<<'\n';
}

G

思维 倍增思想 找规律

一次操作删掉集合最小值$x$，分数乘上$x$，给集合加入$1,..x-1$这些元素。现在初始集合有一些元素，问操作$k$后得分多少？

先不说得分，$k=1e9$，我们的肯定不能模拟，需要快速算出来完全删掉一个元素（也就是删掉这个元素和衍生元素）的操作次数。

考虑打表或者推式子，推式子的话，设删掉$x的代价是f_x$，删掉他自己需要一次，然后还需要删掉他的所有衍生元素，故$f_x=1+{\sum }_{i=1}^{x-1}{f}_i$

这个式子还不是很显然，考虑根据这个式子打表，可以发现$f_x=2^{x-1}$

接下来来考虑得分，也是类似的式子，只是删掉$x$得分$x$，并且是乘法，式子变成$g_x=x{\prod }_{i=1}^{x-1}{g}_i$

注意到$x$超过$30$，需要的操作次数就大于$1e9$了，所以我们只用预处理出来删掉不超过$30$的元素的得分。

最后处理时对元素排序，先处理小的。如果一个元素需要的操作次数，不超过剩余次数，直接把他的贡献加进来。如果超过剩余次数了说明这个元素不能全删完，写个函数$cal(i,j)表示删i，剩余次数j的总得分$，函数内部考虑枚举$p\in [1,x-1]$看能删到哪里，枚举过程中可能在某个$p$处，操作次数又不够了，可以发现这是个和$cal(i,j)$结构相同，规模更小的子问题，直接递归。

注意如果某个元素大于$30$,不用计算它需要多少次完全删完了，操作次数肯定不够，直接调用$cal()$即可，否则计算$2^{a_i-1}$可能溢出

int f[40];
int cal(int x,int k){
	int res=x%M1;
	k--;
	if(!k){
		return res;
	}
	rep(i,1,x-1){
		if((1ll<<(i-1))>=k){
			res*=cal(i,k);
			res%=M1;
			break;
		}
		else{
			k-=(1ll<<(i-1));
			res*=f[i];
			res%=M1;
		}
	}
	return res;
}
void solve()
{
	int n,k;
	cin>>n>>k;
	vi a(n+1);
	rep(i,1,n){
		cin>>a[i];
	}
	
	sort(a.begin()+1,a.end());
	int ans=1;
	rep(i,1,n){
		if(a[i]>35||(1ll<<(a[i]-1))>=k){
			ans*=cal(a[i],k);
			ans%=M1;
			break;
		}
		else{
			k-=(1ll<<(a[i]-1));
			ans*=f[a[i]];
			ans%=M1;
		}
	}
	cout<<ans<<'\n';
//	int n;
//	cin>>n;
//	int sum=1;
//	rep(i,1,n){
//		int cur=i*sum;
//		cout<<i<<' '<<cur<<'\n';
//		sum*=cur;
//	}
}
	
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int test=1;	
	
    cin>>test;
    int pre=1;
    rep(i,1,35){
		f[i]=i*pre%M1;
		pre=pre*f[i]%M1;
	}
    while(test--){
    	solve();	
    }
}