懒起来了，整个合集还是爽啊。

突然就进了 BUPT 的 ACM 队，最近说是要磨合来着，每隔一天搞一套题。

看着大佬写了啥，把大佬切的题跟着写了写，很多东西都要重新学习。

每次比赛都应该会挑几道写一下。

A. Change number

题意

给定两序列 ai,bia_i , b_i，定义操作 (x,y)(x,y) 为将两序列所有的 xx 换成 yy。
问最少操作数使两序列相同，并求出多少操作的排列方式。

分析

我们可以利用映射的思想，把每一个不一样的位置两个数拎出来（设为 A,BA,B）。
这两个数互相转成哪个都无所谓，可理解为呈互相映射关系。

这样我们把所有位置处理完，便可能出现一堆数互相映射，立刻联想到这是个并查集。

我们用并查集处理这种映射关系，假设一棵树内部有 kk 个数，要想全部变成一个数便需要 k−1k-1 次操作，累加即可。

关键是 排列方式 杀我。

既然转换关系不重要，就是说明并查集中一棵树转换顺序不重要，只需要最后转成一个就行了。
那我们直接 A(n,n)A(n,n) 便可解决内部顺序的问题。

之后对于并查集不同树的组合方式，我们不妨考虑最后统计答案的时候每多找到一颗树，就把里面所有的排序插板。
假设此时已经有了 mm 次操作，又多出来 k−1k-1 个，若插板时顺便考虑顺序，就是 A(m+k−1,k−1)A(m+k-1,k-1) ，加起来就行了。

#include<stdio.h>

typedef long long ll;

const int N=100005,P=1e9+7;

int test,n,m,k,ret,a[N],b[N],fa[N],sz[N],fac[N],ifac[N],inv[N];
int find(int u){return fa[u]==u?u:fa[u]=find(fa[u]);}
int fpow(int a,int t){
	static int r;
	for(r=1;t;t>>=1,a=(ll)a*a%P)if(t&1)r=(ll)r*a%P;
	return r;
}

int main(){
	int i,u,v;
	fac[0]=fac[1]=ifac[0]=ifac[1]=inv[1]=1;
	for(i=2;i<N;i++){
		fac[i]=(ll)fac[i-1]*i%P;
		inv[i]=P-(ll)(P/i)*inv[P%i]%P;
		ifac[i]=(ll)ifac[i-1]*inv[i]%P;
	}
	auto binom=[&](int n,int m){return n<m?0:(ll)fac[n]*ifac[m]%P*ifac[n-m]%P;};
	scanf("%d",&test);
	for(;test;--test){
		scanf("%d%d",&n,&k);
		for(i=1;i<=n;i++)fa[i]=i,sz[i]=1;
		for(i=1;i<=n;i++)scanf("%d",a+i);
		for(i=1;i<=n;i++)scanf("%d",b+i);
		for(i=1;i<=n;i++){
			u=find(a[i]),v=find(b[i]);
			if(u!=v)fa[u]=v,sz[v]+=sz[u];
		}
		m=0,ret=1;
		for(i=1;i<=n;i++)if(fa[i]==i&&sz[i]>1){
			m+=sz[i]-1;
			ret=(ll)ret*binom(m,sz[i]-1)%P;
			ret=(ll)ret*fac[sz[i]]%P*fac[sz[i]-1]%P;
		}
		printf("%d",m);
		if(k==2)printf(" %d",ret);
		puts("");
	}
}

F. ForbiddenSum

题意

一个可重复数字集合 SS 的神秘数定义为最小的不能被 SS 的子集的和表示的正整数。
给出任意子序列 [l,r][l,r] 中的神秘数。

分析

题意很简单，但无从下手，真就菜的彻底。

这种时候应该搞几组小数据猜猜结论。若这个序列没有 1，那答案就是 1 ；若有个 1 有个 3 ，答案就是 2 ；

那就猜一手如果我们先找出所有 1 ，再找出所有 2 …最后找到了 mxmx，致使子序列中某些数已经可以从 11 一直表示到 kk，
那么如果这个自序列还有 xx，对其分类讨论：

  • 若 x∈[1,mx]x \in [1,mx]，好像不存在这种情况，我们的前提就是 xx 已经找过了
  • 若 x∈[mx+1,k+1]x \in [mx+1,k+1]，好像可以有贡献，对于任意一个可以表示出的数 k0∈[1,k]k_0 \in [1,k]，都可以加上这个 xx从而扩大范围，最大可以到 k+xk+x
  • 若 x⩾k+1x \geqslant k+1 ，好像就没啥贡献，可以理解为在 k+1k+1 断档，那神秘数就是 k+1k+1。

我们按照这种想法，搞一个权值线段树，把所有在 [mx+1,k+1][mx+1,k+1] 区间内的数找出来，这些数都是有贡献的，全加上去就完事了。

但是我们限制了子区间，上主席树！！

#include <iostream>
#include <cstring>
#define inf 1e9
#define ll long long
#define maxn (ll)(1e6+1)
#define mid (l+r)/2
using namespace std;

struct tr{
	ll sum,ls,rs;
}t[25*maxn];
ll n,st,m,a[maxn],rt[maxn];

void update(ll &rt,ll l,ll r,ll k)
{
	t[++st]=t[rt]; rt=st; t[rt].sum+=k;
	if (l==r) return;
	if (k<=mid) update(t[rt].ls,l,mid,k); else update(t[rt].rs,mid+1,r,k);
}

ll query(ll i,ll j,ll l,ll r,ll x,ll y)  //x,y--check bound; l,r--now bound
{
	if ( (t[j].sum-t[i].sum)<=0 || y<l || x>r ) return 0;
	if ( x<=l && r<=y ) return (t[j].sum-t[i].sum);
	return query(t[i].ls,t[j].ls,l,mid,x,y)+query(t[i].rs,t[j].rs,mid+1,r,x,y);
}

int main()
{
	cin>>n;
	for (ll i=1;i<=n;i++) cin>>a[i],rt[i]=rt[i-1],update(rt[i],1,inf,a[i]);
	cin>>m;
	for (ll i=1,l,r;i<=m;i++)
	{
		cin>>l>>r;  ll Max=0,sm=0;
		while ("CRN TQL")
		{
			ll sum=query(rt[l-1],rt[r],1,inf,sm+1,Max+1);
			if (!sum) break;
			sm=Max+1;  Max+=sum;
		}
		cout<<Max+1<<endl;
	}
}


I. Perfect Security

题意

上下各 nn 个数,求一种排列 p ,使上面的数 ai(ai⩽230)a_i (a_i \leqslant 2^{30}) 异或 bib_i 成为新的数 kik_i ,求方案使 kik_i 字典序最小

分析

又是一个短小精悍的题。

先考虑个 O(n2)O(n^2) 的暴力：每个 aia_i 都和 bjb_j 匹配一下，挑个最小的搭上去，就完成了。

若想加速每个 aia_i 的匹配过程，我们需要明确两数异或后变更小的实质，那就是每个数位都能最好是 0，那铁定最小。

又注意到 ai⩽230a_i \leqslant 2^{30}，那就可以二进制拆分，套上我们无敌的 01Trie 树 ！

将 bib_i 每个数的二进制插入 01Trie 树，但注意是从高位插入，因为我们需要使最高位优先最小。

关于 01Trie01Trie 树的故事我们还需要更加深刻的了解。。。

#include <iostream>
#include <cstring>
#include <vector>
#define maxn 300001
#define inf 2147483647
using namespace std;

struct tree{
	int cnt,s[2];
}t[maxn*20];

int n,st=1,a[maxn],b[maxn];

void insert(int k)
{
	int now=1;  t[now].cnt++;
	for (int i=30;i>=0;i--)
	{
		int nex=(k>>i) & 1;
		if ( !t[now].s[nex] ) t[now].s[nex]=++st;
		now=t[now].s[nex]; t[now].cnt++;
	}
}

int query(int k)
{
	int now=1,ans=0;
	for (int i=30;i>=0;i--)
	{
		int nex=(k>>i) & 1;
		if ( !t[ t[now].s[nex] ].cnt ) nex=(!nex);
		ans=(ans<<1)+nex;  now=t[now].s[nex]; t[now].cnt--;
	}
	return ans ^ k;
}

int main()
{
	cin>>n; 
	for (int i=1;i<=n;i++) cin>>a[i];
	for (int i=1;i<=n;i++) cin>>b[i],insert(b[i]);
	for (int i=1;i<=n;i++) cout<<query(a[i])<<" ";
}

这次比赛堡羚了，这很好，时刻都能警醒自己有多菜。

A. Array Partition

题意：

给定一个数组将其分为两组 P,QP,Q，若使得 GCD(∏Pi,∏Qi)=1GCD(\prod P_i , \prod Q_i) = 1，问有多少分组方式？

分析：

拿到手以为是数论就弃了，后来 xd 同学为我耐心地讲解我才明白自己多sb。。

已知任意两个有公因数的元素都应该在一侧，按这个构建并查集求连通块的个数 cntcnt。每个连通块有 P,QP,Q 两种摆放方法。
因此答案便是 2cnt−22^{cnt}-2，减 2 排除了空集的可能性。

关于构建并查集，我们可以把所有质因数也当做节点考虑：对于一个数 xx，我们将其所有的质因子都指向他认作祖先；这样如果枚举到 yy 时若有同样的质因子，我们就可以查出该质因子的祖先并直接将其加入同一棵树下；
换句话说，我们可以用质因数作为桥梁，连接两个有公因数的元素，相当于空间换时间了。

#include <iostream>
#include <cstring>
#define inf 2147483647
#define maxn 100010
#define N 1000100
using namespace std;

const int mod=1e9+7; 
int t,n,a[maxn],A[N],p[N/2],f[N];  bool v[N];

int find(int x){return (x==f[x])?x:f[x]=find(f[x]);}

void merge(int x,int y)
{	int f1=find(x),f2=find(y); f[f1]=f2;}

int main()
{
cin>>t; v[1]=1;
for (int i=2;i<=1000000;i++) {
	if ( !v[i] ) p[++p[0]]=i;
	for (int j=1;j<=p[0] && p[j]*i<=1000000 ;j++) {
		v[p[j]*i]=1; if ( i%p[j]==0 ) break;
	} 
}

while (t--)
{
	cin>>n; int t=n,ans=1;
	for (int i=1;i<=n;i++) cin>>a[i],f[i]=i;
	for (int i=1;i<=p[0];i++) f[++t]=t,A[p[i]]=t;
	for (int k=1;k<=n;k++) {
		int x=a[k];
		for (int i=1;i<=p[0] && p[i]*p[i]<=x ;i++) {
			if ( x%p[i]==0 ) merge(A[p[i]],k);
			while ( x%p[i]==0 ) x/=p[i];
		}
		if ( x!=1 ) merge(A[x],k);  //小优化，大于开跟的质数不用枚举 
	}
	for (int i=1;i<=n;i++) {
		if (i==f[i]) ans=(ans*2)%mod;
	}
	ans=(ans-2+mod)%mod; cout<<ans<<endl;
}
}

C. Chef and Chocolates

题意：

每个糖果有权值与数量，对于每次询问 k 会消耗所有比k小的糖果一个，问每次操作后有几个糖果变为0，并输出它们的权值。

分析：

这种题就是你看一眼就会写，但细细一想发现一堆细节不知道怎么实现的那种。。

核心就是将糖果按权值排序后插入线段树，每次询问用二分查找修改区间并区间减一，
我们同样可以利用一次询问查找出所有变为 0 的数：只需要每当查出一个就修改为 inf 并上传，继续找就行了。相当于搞了一个查询和修改操作的缝合怪。
由于每个糖果至多被查询一次，所以时间复杂度 O(n⋅logn)O(n·logn)。

#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
#define inf 2147483647
#define maxn 100010
#define pushup(o) tr[o].mn=min(tr[o*2].mn,tr[o*2+1].mn)
#define mid (l+r)/2
using namespace std;

struct tr{
	int mn,tg;
}tr[maxn*4];
struct choco{
	int sm,nb;
	bool operator <(const choco &a) const {return nb<a.nb;}
	bool operator <(const int &a) const {return nb<a;}
}a[maxn];
int n,q;  vector<int> ans;  

void pd(int o)
{
	tr[o*2].tg+=tr[o].tg; tr[o*2+1].tg+=tr[o].tg;
	tr[o*2].mn-=tr[o].tg; tr[o*2+1].mn-=tr[o].tg;
	tr[o].tg=0;
}

void build(int o,int l,int r)
{
	if (l==r) tr[o]={a[l].sm,0};
else {
	build(o*2,l,mid); build(o*2+1,mid+1,r);
	pushup(o); 
}}

void del(int o,int l,int r,int x,int y)
{
	if (x<=l && r<=y) {tr[o].mn--,tr[o].tg++; return;}
	if (r<x || l>y) return; if (tr[o].tg) pd(o);
	del(o*2,l,mid,x,y); del(o*2+1,mid+1,r,x,y);
	pushup(o);
}

void find(int o,int l,int r)
{
	if ( l==r && tr[o].mn==0 ){
		ans.push_back(l);  tr[o].mn=inf; return;
	}
	if (tr[o].tg) pd(o);
	if ( tr[o*2].mn==0 ) find(o*2,l,mid);
	if ( tr[o*2+1].mn==0 ) find(o*2+1,mid+1,r);
	pushup(o);
}

int main()
{
	ifstream cin("1.in");
	ofstream cout("out.txt");
	cin>>n; build(1,1,n);
	for (int i=1;i<=n;i++) cin>>a[i].nb;
	for (int i=1;i<=n;i++) cin>>a[i].sm; 
	sort(a+1,a+n+1);  build(1,1,n);  cin>>q; 
	for (int i=1,x;i<=q;i++) {
		ans.clear(); cin>>x; cout<<i;  
		int l=lower_bound(a+1,a+n+1,x)-(a+1);  
		del(1,1,n,1,l);  find(1,1,n);
		for (int i=0;i<ans.size();i++) cout<<" "<<a[ans[i]].nb; cout<<endl;
	}
}

E. Permutation Composition Queries

题意：

定义新运算 X∗Y=Z,Z=YXiX*Y=Z,Z=Y_{X_i}，其中 X,YX,Y 是两个 1 M1~M 的排列。

对于给定 每个元素都是1 M1~M排列的数组 PP，每次询问给定 L,RL,R，问 PL∗PL+1∗...∗PRP_L*P_{L+1}*...*P_{R} 的结果。

分析：

我比赛结束那天晚上拿着题解翻来覆去看不懂，最后才发现整个网页上都写满了两个大字：脑瘫。

但讨论组里有个大佬给出了一个思路；既然你给定了新运算，那我们类比加法：对于 [l,r][l,r] 区间和，我们有什么 O(1)O(1) 解决的方法呢？
对，就是前缀和，我们假设 ss 是 [1,r][1,r] 的前缀和数组，那么对于 [l,r][l,r] 的答案就是 s[r]−s[l]s[r]-s[l] ，这个大家都知道。

那我们将其应用于本题，发现我们同样可以在 O(n)O(n) 时间内搞出任意一个元素经 rr 次操作的位置，也就是该运算的前缀和数组 S[i][j]S[i][j] ，表示第 i 次操作后 j 的位置。
显然，初始化 S[0][i]=iS[0][i]=i。

那我们的问题就转化为求 S[r]−S[l]S[r]-S[l] 的大小，那就纳闷了，我们该用什么东西来类比减法呢？
答案是没必要类比，我们可以将其看作 S[r]+(−S[l])S[r]+ (-S[l])，这就很有意思了，等价于求出 S[l]S[l] 该排列的”逆元“。

据那个大佬说这里的逆元指的就是 inverse of permutation，直译就是逆排序但我没在百度搜到。大概意思就是将第 i 位置上的数 j调换为 第 j 位置上的数 i。
不是很懂有什么应用，但能做出来，那不管了（

#include <iostream>
#include <cstring>
#include <map>
#define inf 2147483647
#define ll long long
#define mp make_pair 
#define pr pair<int,int> 
using namespace std;

int t,n,m,q,l,r;

int main()
{
cin>>t;
while (t--)
{
	cin>>n>>m;  int p[n+1][m+1];
	for (int i=1;i<=n;i++) 
	for (int j=1;j<=m;j++) cin>>p[i][j];
	int pre[n+1][m+1],inv[n+1][m+1];
	for (int i=1;i<=m;i++) pre[0][i]=inv[0][i]=i;
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++) 
		pre[i][j]=p[i][pre[i-1][j]],inv[i][pre[i][j]]=j;
	cin>>q; map<pr,ll> hash;
	while (q--)	{
		cin>>l>>r; ll ans=0;
		if ( hash.count(mp(l,r)) ) ans=hash[mp(l,r)];
		else {
			for (ll i=1;i<=m;i++) ans+=(ll)pre[r][inv[l-1][i]]*i; 
			hash[mp(l,r)]=ans;
		}
		cout<<ans<<endl;
	}
}
}

J. Course Selection

题意：

对于 mm 个学期共学习 nn 门课，第 ii 学期修第 jj 门课的得分是 x[i][j]x[i][j] ，且存在前置课程，问最终的最高得分？

分析：

一开始还以为是啥背包，但细细一想发现前置课程与每个学期相同课程得分不同两个限制同时存在，应该限制了背包物品的构造。。。
搞这种规划问题除了 DP 就是跑网络流了，但我又把网络流给忘了，就摸了。

稍微复习了一下，这种带限制条件的图我们称它为 最大权闭合子图，我们只需要将得分改成丢分，跑最小割就行了。。。

#include <iostream>
#include <cstring>
#include <queue>
#include <cmath>
#include <iomanip>
#define inf 2147483647
#define ll long long
#define maxn 100000
using namespace std;

struct ed{
	int u,nex,w;
}e[2*maxn];
int n,m,k,s,t,x[101][101],st=1,c[maxn],fir[maxn];
int d[maxn]; bool v[maxn];
queue<int> q;
//x[n][m] -> n classes with m terms

void add(int u,int v,int w)
{
	e[++st].u=v; e[st].nex=fir[u]; e[fir[u]=st].w=w;
	e[++st].u=u; e[st].nex=fir[v]; e[fir[v]=st].w=0;	
}

bool bfs()
{
	memset(v,0,sizeof(v)); memset(d,0x3f,sizeof(d));
	memcpy(c,fir,sizeof(c)); q.push(s); v[s]=1; d[s]=0;
	while (!q.empty())
	{
		int k=q.front(); q.pop();
		for (int i=fir[k];i;i=e[i].nex)
		{
			int u=e[i].u,w=e[i].w;
			if ( d[u]>d[k]+1 && w){
				d[u]=d[k]+1; if (!v[u]) v[u]=1,q.push(u); 
			} 
		}
	}
	return (d[t]<1e9);
}

int dfs(int v,ll f)
{
	if (v==t) return f;
	ll mw=0,used=0;
	for (int i=c[v];i;i=e[i].nex)
	{
		c[v]=i; int u=e[i].u,w=e[i].w;
		if (w && d[u]==d[v]+1){
			if ( mw=dfs(u,min((ll)w,f-used)) ) {
				e[i].w-=mw; e[i^1].w+=mw; used+=mw;
				if ( used==f ) break;
			}
		}
	}
	return used;
}

ll dinic()
{
	ll ans=0;
	while (bfs()) ans+=dfs(s,inf);
	return ans;
}

int main()
{
	cin>>n>>m>>k; s=0; t=n*(m+1)+1;
	for (int i=1;i<=n;i++) 
		for (int j=1;j<=m;j++) cin>>x[i][j]; 
	for (int i=1;i<=m;i++) 
	for (int j=1;j<=n;j++) add( (i-1)*n+j, i*n+j , (x[j][i]==-1)? inf/2 :100-x[j][i]);
	for (int i=1;i<=n;i++) add(s,i,inf/2),add(n*m+i,t,inf/2);
	while (k--) {	
		int u,v; cin>>u>>v;
		for (int j=1;j<=m;j++) add( (j-1)*n+u, j*n+v ,inf/2);
	}
	ll ans=dinic(); 
	cout<<fixed<<setprecision(2)<<(double)(n*100-ans)/(double)n<<endl;
}

去朋友家登dua郎就翘了这次比赛，回来一看一万个DP，我一个不会写，幸好没来否则又要堡羚了。

A.Bear and Tree jumps

题意：

给定一棵大小为 nn 的树以及单次行动最大位移 kk，求出所有点对间的行动步数 ∑f(s,t)\sum f(s,t)

分析：

基本思路是搞出每一个点于其他所有点的行动步数，累加起来除以 2 就是点对间的步数和了。
而“每一个点相对于其余所有点”可以想到先搞出以 1 为根相对于所有点的答案，再考虑换根转移，从而求得其他点的答案。

我们设 jpijp_i 为以 i 为根，到达其子树内所有点的总步数，则以 1 为根时，jp1jp_1 便是 1 号节点的贡献；
再令 JpiJp_i 为以 i 为根，到达其他所有点的总步数，这也便是我们最终的答案。

考虑由 uu 转移到子节点 vv 的贡献变化：

  • 若 uu 跳了 pk+1pk+1 步到达 vv 子树中的 v1v_1 节点，那么对于 vv 而言就省了一步，贡献减一；
  • 若 uu 跳了 qkqk 步到达 vv 子树外的 u1u_1 节点，那么对于 vv 要多走一步，贡献加一；
  • 其余不影响

也就是说我们还需要维护一个信息 s[u][i]s[u][i]，方便我们查询 从节点 uu 出发到距离膜 k 后余 ii 的节点数量，
同理，小写 ss 数组维护的是以 u 为根，其子树内所有点的贡献；而大写 SS 数组维护与其他所有点的贡献

对于 jpujp_u，我们不难得到转移方程 jpu=∑v∈ujpv+s[v][0]jp_u = \sum_{v \in u} jp_v +s[v][0]

对于大写 SS 数组，我们可以感性理解一下转移过程：

  • 对于 ∀u,i\forall u,i，S[u][k]=S[fa][k−1]S[u][k] = S[fa][k-1] 相当于我们将所有点的距离都相对父节点拉远了一格；这只能适用于非 uu 子树内的节点。
  • 考虑对 uu 子树内节点进行修正： S[u][k]=S[u][k]+s[u][k−2]+s[u][k]S[u][k] = S[u][k] + s[u][k-2] +s[u][k]，这里有点容斥的思想，画个图就能理解。

有了以上条件，我们就能搞出 JpiJp_i ：

  • Jpu=jpuJp_u = jp_u
  • 对于非 1 节点，Jpu+=(S[fa][0]−s[u][k−1])Jp_u += (S[fa][0]-s[u][k-1])，对于父节点恰好到的节点 uu要多走一步，贡献加一，同样利用容斥的思想。
  • 对于非 1 节点，Jpu−=s[u][0]Jp_u -= s[u][0]，再修正子树u内部信息，父节点跳了 qk+1qk+1 步的节点对于 uu少走一步，贡献减一；
#include <iostream>
#include <cstring>
#define inf 2147483647
#define maxn 200010
#define ll long long
using namespace std;

struct ed{
	int u,nex;
}e[maxn*2];
ll n,k0,fir[maxn],st;
ll ans,jp[maxn],s[maxn][5],Jp[maxn],S[maxn][5];

void add(ll u,ll v)
{
	e[++st].u=v; e[st].nex=fir[u]; fir[u]=st;
	e[++st].u=u; e[st].nex=fir[v]; fir[v]=st;
}

void dfs1(ll u,ll fa)
{
	s[u][0]=1; jp[u]=0;
	for (ll i=fir[u];i;i=e[i].nex) {
		ll v=e[i].u; if (v==fa) continue;
		dfs1(v,u);  jp[u]+=jp[v];
		for (ll k=0;k<k0;k++) 
			s[u][k]+=s[v][(k-1+k0)%k0];
		jp[u]+=s[v][0];  //到v距离为k，到u就要增一。 
	}
}

void dfs2(ll u,ll fa)
{
	if (u!=1){
		for (ll k=0;k<k0;k++) {
			S[u][k]=S[fa][(k-1+k0)%k0];  
			S[u][k]=S[u][k]-s[u][(k-2+k0)%k0]+s[u][k]; //再修正子树u内部信息 
		}
		Jp[u]=Jp[fa];
		Jp[u]+=(S[fa][0]-s[u][k0-1]); //先更新子树u以外的信息 
		Jp[u]-=s[u][0]; //再修正子树u内部信息 
	}
	ans+=Jp[u];
	for (ll i=fir[u];i;i=e[i].nex)
	{
		ll v=e[i].u; if (v==fa) continue;
		dfs2(v,u);
	}
}

int main()
{
	cin>>n>>k0;
	for (int i=1,u,v;i<n;i++) cin>>u>>v,add(u,v);
	dfs1(1,0); 
	memcpy(S,s,sizeof(s)); Jp[1]=jp[1];
	dfs2(1,0);
	cout<<ans/2<<endl;
}

B.The least round way

题意：

在 n∗nn*n 矩阵内找一条路径，使各点相乘的 0 后缀最少。

分析：

这题细节巨多。

易想到质因数分解，把每个数中 2,5 的贡献单独表示，最后看最少的2,5有多少个，就有多少 0 后缀。
但是 2 和 5 应该是分开转移的，设为f[i][j][0]→f[i][j][0] \rightarrow 至 (i,j)(i,j) 路径中 2 的最小数量,f[i][j][1]→f[i][j][1] \rightarrow 至 (i,j)(i,j) 路径中 5 的最小数量。。
而不能将两个信息合并为 f[i][j]→f[i][j] \rightarrow 至 (i,j)(i,j) 路径中 2,5 的最小数量。

若路径上有 0 ，标记后将其改为 10 ，便可避免无 0 后缀但经过 0 的尴尬情况。
当正常求得的答案大于 1，我们就输出 1 （0的0后缀便是1），随便打印一条经过 0 的路径即可。

输出路径可以和 dp 一其顺手维护了，也可以求完答案后递归求解。

#include <cstdio>
#include <cstring>
#include <vector>
#define inf 2147483647
using namespace std;

int f[1001][1001][2];
int a[1001][1001][3],n,x,y,t;
vector<char> c;

void Print(int i,int j,int k) {
    if(i==1&&j==1) {                //递归输出函数
        putchar(k? 'D':'R');
        return ;            
    }
    if(i==1)
        Print(i,j-1,0);
    else if(j==1)
        Print(i-1,j,1);
    else if(f[i][j][t]==f[i][j-1][t]+a[i][j][t+1])
        Print(i,j-1,0);
    else
        Print(i-1,j,1);
    if(i!=n||j!=n)
        putchar(k? 'D':'R');    //在(n,n)处不输出
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;f[i][0][0]=f[i][0][1]=inf/2,f[0][i][0]=f[0][i][1]=inf/2,i++) 
	for (int j=1;j<=n;j++) {
		scanf("%d",&a[i][j][0]);  if ( !a[i][j][0] ) x=i,y=j,a[i][j][0]=10;
		int t=a[i][j][0];
		while ( t%2==0 ) a[i][j][1]++,t/=2; t=a[i][j][0];
		while ( t%5==0 ) a[i][j][2]++,t/=5;
	}
	f[1][0][0]=f[1][0][1]=0,f[0][1][0]=f[0][1][1]=0;
	for (int i=1;i<=n;i++)
	for (int j=1;j<=n;j++) {
		int x1=f[i-1][j][0],x2=f[i][j-1][0],y1=f[i-1][j][1],y2=f[i][j-1][1];
		f[i][j][0]=min(x1,x2)+a[i][j][1]; f[i][j][1]=min(y1,y2)+a[i][j][2];
	}
	int ans=min(f[n][n][0],f[n][n][1]);
	if (ans>1 && x!=0) {
		printf("1\n");
		for (int i=1;i<x;i++) putchar('D'); 
		for (int i=1;i<n;i++) putchar('R');
		for (int i=x;i<n;i++) putchar('D');
	}
	else {
		if (f[n][n][0]<f[n][n][1]) t=1; else t=0;
		printf("%d\n",ans); Print(n,n,t);
	}
}

E.Array

题意：

对于长度为 nn 的数组A，只包含从1到n的整数（可重复）。
如果A单调不上升或单调不下降，A就可称为美丽的，问美丽A的数量。

分析：

答案是 2∗C(2∗n−1,n)−n2*C(2*n-1,n)-n，我也想听数论证明。

A.Lizard lounge

题意：

给定一系列肥宅的坐标（有高度）以及电视的坐标，肥宅可以看到电视当且仅当面朝电视前方所有人的高度小于该肥宅高度。假设可踢掉任意肥宅，问最多可看到电视的肥宅人数。

分析：

大概就是按照角度把所有肥宅分类，一条线上跑LIS就行了。。
每次跑LIS清空数组，如果用 memset 会炸成 O(NM)O(NM)（ M 是最大高度），我为了这个交了 5 发；
xd 同学用了撤销操作的想法，保证时间复杂度控制在 O(N⋅logN)O(N \cdot logN)，简单且巧妙但我就是没想到。

B.Tree Requests

题意：

给定一个以 1 为根的 nn 个结点的树，每个点上有一个字母（ a-z ），每个点的深度定义为该节点到 1 号结点路径上的点数。
每次询问 a,ba,b 查询以 a 为根的子树内深度为 b 的结点上的字母重新排列之后是否能构成回文串。

分析：

看完题我只会把树建好然后 O(n2)O(n^2) 暴力搞，比赛后才知道有树上启发式合并这种东西，要学的东西还有很多。

考虑将询问全部离线，对于每个点求出其对应询问的所有答案。
首先将这棵树重链剖分，在深搜的过程中我们可以优先处理轻儿子并在关于轻儿子的询问结束后清空答案数组，最后再处理重儿子，但此时我们不必清空答案数组，这样我们能够在处理其父亲的询问时只需要把所有轻儿子的贡献重新统计即可。
由于轻儿子修改次数不会超过logn，所以大胆删去并不会影响时间复杂度。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define inf 2147483647
#define ll long long
#define maxn 500010
using namespace std;

struct e{int id,d;};  vector<e> ask[maxn];
int n,m,cnt[maxn][27],d[maxn],f[maxn],s[maxn],son[maxn];
int dfn[maxn],st,id[maxn],ans[maxn];
vector<int> g[maxn];  
char str[maxn]; 

void dfs(int u,int fa)
{
	s[u]=1; d[u]=d[fa]+1; dfn[u]=++st; id[st]=u;
	for (int v: g[u]) {
		if (v==fa) continue; dfs(v,u);
		s[u]+=s[v]; if (s[v]>s[son[u]]) son[u]=v;
	}
}

void chg(int u,int k) { cnt[d[u]][str[u]-'a'+1]+=k; }
bool check(int d){
	int ans=0;
	for (int i=1;i<=26;i++) ans+=(cnt[d][i] & 1);
	return (ans<=1); 
}

void DFS(int u,bool kp)
{
	for (int v: g[u]) {
		if (v==f[u] || v==son[u]) continue; DFS(v,0);
	}
	//先处理全部的轻儿子 
	if ( son[u] ) DFS(son[u],1); // 最后处理重儿子，此时cnt函数只存了重儿子 
	for (int v:g[u]){
		if (v==f[u] || v==son[u]) continue;
		for (int i=dfn[v];i<=dfn[v]+s[v]-1;i++) chg(id[i],1); 
	}	chg(u,1);  //重新加上轻儿子和自己 
	for (int i=0;i<ask[u].size();i++) 
		ans[ask[u][i].id]=check(ask[u][i].d);  //离线查询
	if (!kp) for (int i=dfn[u];i<=dfn[u]+s[u]-1;i++) chg(id[i],-1); //由于轻儿子修改次数不会超过logn，所以大胆删去 
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=2,x;i<=n;i++) {
		scanf("%d",&x); f[i]=x;
		g[i].push_back(x); g[x].push_back(i);
	}
	scanf("%s",str+1);
	for (int i=1,u,k;i<=m;i++) {
		scanf("%d%d",&u,&k); ask[u].push_back({i,k});
	}
	dfs(1,1);  DFS(1,1);
	for (int i=1;i<=m;i++) printf("%s\n",ans[i]?"Yes":"No");
	return 0;
}

C. Range Increments

题意：

给定一个序列，对于其任意子区间进行减一操作，直至全部变为 0 ，问最小操作数。

分析：

这题一看就是典型的数据结构题，然后我就被差分曹翻了。

我的想法是线段树维护区间最大 / 最小值，如果 [1,n][1,n] 的最大值为 0 ，标志查询结束。
为了找出当前所有连续的非 0 区间，对于 [1,i][1,i] 区间其最大值必然是递增的，可以利用二分找出最小的 ii 使其区间最大值非 0 ，这就确定了最靠左的非 0 子区间的左端点。
我们继续在 [i,n][i,n] 范围内找出第一个 jj 使得 [i,j][i,j] 区间的最小值为 0 ，则 j−1j-1 便是该非 0 子区间的右端点。

然后就没了，思路挺直白的但是时间就白白浪费了。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <vector>
#define inf 2147483647
#define ll long long
#define mid (l+r)/2
#define mp make_pair
using namespace std;

const int maxn=1e5+1;
struct tree{
	int mx,mn;
}tr[maxn*4];
int tg[maxn*4],a[maxn],n; vector< pair<int,int> > ans;


/*segment treee*/
void pushup(int o){tr[o] = {max(tr[o*2].mx,tr[o*2+1].mx) , min(tr[o*2].mn,tr[o*2+1].mn)};}
void pd(int o){
	int k=tg[o]; tg[o]=0;
	tr[o*2].mx+=k; tr[o*2].mn+=k;
	tr[o*2+1].mx+=k; tr[o*2+1].mn+=k;
	tg[o*2]+=k; tg[o*2+1]+=k;
}

void build(int o,int l,int r)
{
	if (l==r) {tr[o] = {a[l],a[l]}; return;}
	build(o*2,l,mid); build(o*2+1,mid+1,r);
	pushup(o);
}

int query_mn(int o,int l,int r,int x,int y)
{
	if (x<=l && r<=y) return tr[o].mn;
	if (l>y || r<x) return inf/2;
	if (tg[o]) pd(o);
	return min(query_mn(o*2,l,mid,x,y),query_mn(o*2+1,mid+1,r,x,y));
}

int query_mx(int o,int l,int r,int x,int y)
{
	if (x<=l && r<=y) return tr[o].mx;
	if (l>y || r<x) return -inf/2;
	if ( tg[o]!=0 ) pd(o);
	return max(query_mx(o*2,l,mid,x,y),query_mx(o*2+1,mid+1,r,x,y));
}

void update(int o,int l,int r,int x,int y)
{
	if (x<=l && r<=y) { tr[o].mn--,tr[o].mx--; tg[o]--; return;}
	if (l>y || r<x) return; if ( tg[o]!=0 ) pd(o);
	update(o*2,l,mid,x,y); update(o*2+1,mid+1,r,x,y);
	pushup(o);
}

/* binary search*/
int head()
{
	int l=1,r=n,ans=-1;
	while (l<=r) {
		if ( query_mx(1,1,n,1,mid)>0 ) ans=mid,r=mid-1;
		else l=mid+1;
	}
	return ans;
}

int back(int x)
{
	int l=x,r=n,ans=-1;
	while (l<=r) {
		if ( query_mn(1,1,n,x,mid)>0 ) ans=mid,l=mid+1;
		else r=mid-1;
	}
	return ans;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n;
	for (int i=1;i<=n;i++) cin>>a[i]; build(1,1,n);
	while (query_mx(1,1,n,1,n) != 0) {
		int fro = head(); int to = back(fro);
		ans.push_back( mp(fro,to) );
		update(1,1,n,fro,to);
	}
	cout<<ans.size()<<endl;
	for (auto i=0;i<ans.size();i++) cout<<ans[i].first<<" "<<ans[i].second<<endl;
	return 0;
}

D. Zagreb Sorts Machines

题解：

有N台机器重量各不相等，现在要求把这些机器按照重量排序，重量从左到右依次递增。
移动机器只能做交换操作，但交换机器要花费一定的费用，费用的大小就是交换机器重量的和，求将所有机器变为有序的最小代价。

分析：

将 aia_i 排序后可确定每个元素最终的位置 kk，我们将 ii 向 kk 连有向边，可以证明最后所有元素会形成好几个环。
且我们始终能在任意环内找到一个最优的处理方案：每个对应元素和环内最小值位置交换，最终一定会使环内元素有序。
设 mnimn_i 为第 i 个环的最小元素， smism_i 为第 i 个环的总和， nminm_i 为第 i 个环的元素数量。不难得到上述处理方案的贡献为：

mni∗(nmi−2)+smimn_i*(nm_i-2)+sm_i

但是 WA 了，想到可能这个环本身的最小值就很大，那样还是不能使答案更优。于是我们有个贪心的想法，先把整个序列最小的值换过来，进行上述操作之后在换回去，这样的贡献为:

(Min∗nmi)+smi+(Min+mni)(Min*nm_i)+sm_i+(Min+mn_i) 

#include <iostream>
#include <algorithm>
#include <cstring>
#define inf 2147483647
#define ll long long
using namespace std;

const int maxn=50005;
int f[maxn],a[maxn],b[maxn],bel[maxn],cnt,n; bool v[maxn];
ll mn[maxn],nm[maxn],sm[maxn],ans;

int get(int x){return (x==f[x])?x:f[x]=get(f[x]);}
void merge(int a,int b){
	int f1=get(a),f2=get(b); if (f1!=f2) f[f1]=f2;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	memset(mn,0x3f,sizeof(mn));
	cin>>n; for (int i=1;i<=n;i++) cin>>b[i],a[i]=b[i],f[i]=i;
	sort(b+1,b+n+1);  mn[0]=b[1];
	for (int i=1,k;i<=n;i++) k=lower_bound(b+1,b+n+1,a[i])-b,merge(i,k);
	for (int i=1;i<=n;i++) if (i==f[i]) bel[i]=++cnt; 
	for (int i=1;i<=n;i++) {
		int bl=bel[get(i)];  
		mn[bl]=min(mn[bl],(ll)a[i]); sm[bl]+=a[i]; nm[bl]++;
	}
	for (int i=1;i<=cnt;i++) 
	ans+=min(mn[i]*(nm[i]-2)+sm[i],mn[0]*nm[i]+sm[i]+mn[0]+mn[i]);
	cout<<ans<<endl;
	return 0;
}

CF1548C. The Three Little Pigs

题意：

有一个最初为空箱子，一共有 n 天，每天开始时箱子里会多出 3 个球，所有球互不相同。
有一个参数 x。我们认为一次行动为在某天球数增加后从箱子里选出 x 个球拿走。注意如果箱子里的球数少于 x，那么当天无法进行行动。
给定 n 和 q，有 q 次询问，每次询问给定 x，你需要求出有多少种行动方案，对 109+710^9+7 取模。

两种行动不同当且仅当进行行动的天数不同，或者拿走的球的集合不同。
注意行动并没有真正执行，只需要计算出方案数。

分析：

一开始没注意到最后一句话，还在想这个既像是数论又不像数论的是啥玩意。
赛后去翻题解，发现居然是生成函数入门题。。

设要求拿 t 个球，根据题意我们很容易构造出 F(x)=∑i=1n(3it)F(x)=\sum_{i=1}^n \binom{3i}{t}，
其生成函数即是：F(x)=xt⋅∑i=1n(1+x)3iF(x)=x^t\cdot \sum_{i=1}^n (1+x)^{3i}

分离系数，由等比数列公式：F(x)=(1+x)3−(1+x)3n+31−(1+x)3F(x) = \frac{(1+x)^3-(1+x)^{3n+3}}{1-(1+x)^3}

利用二项式定理，再与前面一项拧巴拧巴，可以搞出分子的各项；而要想计算出最终答案，我们需要对分母进行多项式除法操作。
这玩意列一个竖式模拟模拟就出来了。

BUPT Autumn Training #12

B. 攻防演练

题意：

给定字符串及一系列询问区间 Sl,rS_{l,r} 求最小的 k ，使不存在长度为 k 的字符串成为其 子序列。用来构造的字符只能在 Sl,rS_{l,r} 中出现。

分析：

从构造角度看，我们定义一个 循环块[i,j] 为包涵所有字符集元素的区间。则对于询问区间 [l,r]，我们只需要找出区间内能包涵所有循环块，答案即为块数加一。

简单的证明，对于连续的 l 个循环块，你可以在每个块内取到长度为 l 的所有子序列。此时长度 l+1 便肯定能构造出非子序列的串 — — 只需选择最后一段未出现的字符做末尾即可。

我们的任务转移到：对于每一个点，如何找到 [l,r] 间所有循环块。我们定义： nxt[i][j] 为从第 i 个元素开始，下一个 j 字符的位置；dp[i][j] 为从第 i 个字符后 2j2^j 个循环块结束的位置。转移方程：

nxt[i][j]=(s[i]==j)?i:nxt[i+1][j]nxt[i][j] = (s[i]==j)?i:nxt[i+1][j]

dp[i][0]=maxi(nxt[i][si]), dp[i][j]=dp[dp[i][j−1]][j−1]dp[i][0] = max_i(nxt[i][s_i]),~dp[i][j]=dp[dp[i][j-1]][j-1]

其中，两者可以通过 倒序处理 减少代码复杂度。对于每一个循环区间跳表即可。

代码：