\(Atcoder-Beginner-Contest-312\)

AB过于简单，在此略去。

\(C-Invisible\) \(Hand\)

题意：给定长为 \(n\) 的数组 \(a\)，长为 \(m\) 的数组 \(b\)，找到最小的非负整数 \(x\)，使得 \(\sum_{i=1}^n[a_i\le x]\ge \sum_{i=1}^m[b_i\ge x]\)

题解：

容易发现，随着 \(x\) 的增大，右式单调不升，左式单调不降，故答案具有单调性。

将两数组排序，二分答案。可以使用 lower_bound 和 upper_bound 快速统计出左右两式。

sort(a+1,a+n+1);sort(b+1,b+m+1);
	int l=0,r=0x3f3f3f3f;
	while(l<r){
		int mid=l+r>>1;
		int x=upper_bound(a+1,a+n+1,mid)-a-1;
		int y=lower_bound(b+1,b+m+1,mid)-b;
		y=m+1-y;
		if(x>=y)r=mid;
		else l=mid+1;
	}
	cout<<l<<"\n";

\(D-Count\) \(Bracket\) \(Sequences\)

题意：给定一个残缺的由 \(\text{(,?,)}\) 构成的括号序列 \(s\)，有若干位置不确定，要求将其补全为完整的括号序列，求方案数，\(n\le 3000\)。

合法括号序列的充要条件是在任意前缀中左括号数量不小于右括号数量，且左括号总数量等于右括号总数量。

复杂度要求 \(O(n^2)\)，显然是动态规划。

考虑设 \(f_{i,j}\) 表示前 \(i\) 个符号里，左括号数量减去右括号数量为 \(j\) 的方案数。

初始化：\(f_{0,0}=1\)

目标：\(f_{n,0}\)

转移：

注意边界。

    f[0][0]=1;
	for(int i=1;i<=n;i++){
		if(a[i]=='(') for(int j=1;j<=n;j++)f[i][j]=f[i-1][j-1];
		else if(a[i]==')') for(int j=0;j<n;j++)f[i][j]=f[i-1][j+1];
		else for(int j=1;j<=n;j++)f[i][j]=(f[i-1][j+1]+f[i-1][j-1])%p;
	}
	cout<<f[n][0]<<"\n";

\(E-Tangency\) \(of\) \(Cuboids\)

题意:给定若干不相交的长方体，坐标范围在 \([0,100]\) 且为整数，求出对于每个长方体，有多少个其他长方体和它共用至少一个面

考虑弱化条件为对于每个长方体而言，有多少个长方体与它共用 \(1\times 1\) 的小矩形。由于坐标很小，我们可以考虑对于该空间每一块都标记属于哪一个长方体。

需要注意的是，对于右上顶点坐标需要都减去1，这很容易理解，避免长方体交。

等下，我们要求的就是交一个平面。那么，什么样的情况下才能共用一个 \(1\times 1\) 的长方形的？注意到我们每一个坐标 \((x,y,z)\) 表示的是 \((x,y,z,x+1,y+1,z+1)\) 这个立方。那么若 \((x,y,x+1,y+1)\) 与另一个交，则另一个的坐标应该是 \((x,y,z+1)\)。

那么其实与 \((x,y,z)\) 交一个面的的坐标只有 \((x+1,y,z),(x,y+1,z),(x,y,z+1),(x-1,y,z),(x,y-1,z),(x,y,z-1)\) 六个，且由于对称性只需考虑前三个。

那么我们枚举这个坐标就可以解决问题了 \(O(m^3)\) 。现在问题变成了怎么统计答案数量，因为长方体交可能会统计很多次。很简单，用一个 \(set\) 维护去重即可。

#include<iostream>
#include<algorithm>
#include<set>
using namespace std; 
#define N 505050
#define M 105
set<int>ans[N];
int n,a[M][M][M];
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int p=1;p<=n;p++){
		int x1,y1,z1,x2,y2,z2;
		cin>>x1>>y1>>z1>>x2>>y2>>z2;
		for(int i=x1;i<x2;i++)for(int j=y1;j<y2;j++)for(int k=z1;k<z2;k++)a[i][j][k]=p;
	}
	for(int i=0;i<=100;i++)for(int j=0;j<=100;j++)for(int k=0;k<=100;k++){
		if(!a[i][j][k])continue;
		if(a[i+1][j][k]&&a[i+1][j][k]!=a[i][j][k])ans[a[i][j][k]].insert(a[i+1][j][k]),ans[a[i+1][j][k]].insert(a[i][j][k]);
		if(a[i][j+1][k]&&a[i][j+1][k]!=a[i][j][k])ans[a[i][j][k]].insert(a[i][j+1][k]),ans[a[i][j+1][k]].insert(a[i][j][k]);
		if(a[i][j][k+1]&&a[i][j][k+1]!=a[i][j][k])ans[a[i][j][k]].insert(a[i][j][k+1]),ans[a[i][j][k+1]].insert(a[i][j][k]);
	}
	for(int i=1;i<=n;i++)cout<<ans[i].size()<<"\n";
	 
}

\(F-Cans\) \(and\) \(Openers\)

题意：给定 \(n\) 个物品，分为三类：

1. 第一类罐子，不需要开罐器，收益为 \(x_i\)
2. 第二类罐子，需要开罐器，收益为 \(x_i\)
3. 开罐器，可以用 \(x_i\) 次。

求从 \(n\) 个物品里选出 \(m\) 个的最大收益。

我们现将3类物品分开，分别记为 \(a,b,c\) ，并按权值从大到小排序。

设 \(f_i\) 为选择 \(i\) 个23类物品的最大收益，\(g_i\) 为选择 \(i\) 个第一类物品的最大收益，则答案为 \(\max_{0\le i\le m}\lbrace f_i+g_{m-i}\rbrace\)

\(g_i\) 是容易的，对 \(a\) 做前缀和即可解决。而 \(f_i\)？注意到我们肯定是贪心地选能开罐子多的开罐器，并且选收益最大的罐子，所以我们记录两个指针 \(j,k\) 分别表示当前选到了第 \(j\) 个罐子和第 \(k\) 个开罐器，然后记录 \(sur\) 表示剩余的开罐次数，一路平推就可以计算 \(f\) 了，显然必须要开罐次数用完后才选择开罐器。

#define int long long
#define N 505050
void read(int &x){
	x=0;char ch=getchar();int w=1;
	while(ch>'9'||ch<'0'){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	x*=w;
}
int n,ans,m,f[N],a[N],b[N],c[N],n1,n2,n3;
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int t;cin>>t;if(t==0)cin>>a[++n1];
		else if(t==1)cin>>b[++n2];
		else cin>>c[++n3];
	}
	sort(a+1,a+n1+1);sort(b+1,b+n2+1);sort(c+1,c+n3+1);
	reverse(a+1,a+n1+1);reverse(b+1,b+n2+1);reverse(c+1,c+n3+1);
	for(int i=1;i<=m;i++)a[i]+=a[i-1];
	int j=0,sur=0,k=0;
	for(int i=1;i<=m;i++){
		if(!sur)f[i]=f[i-1],sur=c[++j];
		else f[i]=f[i-1]+b[++k],--sur;
	}
	for(int i=0;i<=m;i++)ans=max(ans,f[i]+a[m-i]); 
	cout<<ans<<"\n";
}

\(G-Avoid-Straight-Line\)

题意：给定一颗树，求满足 \(i,j,k\) 不在一条简单路径上的点对 \((i,j,k)(i<j<k)\) 的个数。

简单的树形DP问题，不知为什么题解那么复杂。

发现不在同一简单路径比较复杂，考虑容斥。则显然总的点对数是容易求出的，为 \({n\choose 3}\)。然后我们再考虑计算在同一简单路径上的点对数。

考虑固定路径中点 \(u\)，然后就需要在 \(u\) 的某棵子树以及树外部分里选出第一个点，接着在再其他集合里选出另一个点。

形式地说，设 \(u\) 的儿子为 \(v_1,v_2\sim v_m\)，则方案数为：

每一个乘积式的左边是在当前子树里选，后半部分表示在其他部分选，然后除以二是因为重复统计了。

所以代码很简单了。

#define int long long
#define N 505050
void read(int &x){
	x=0;char ch=getchar();int w=1;
	while(ch>'9'||ch<'0'){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	x*=w;
}
int head[N],ver[N],nxt[N],tot,siz[N];
void add(int u,int v){
	nxt[++tot]=head[u],ver[head[u]=tot]=v;
}
int n,ans;
void dfs(int u,int fa){
	siz[u]=1;
	int k=0;
	for(int i=head[u];i;i=nxt[i]){
		int v=ver[i];if(v!=fa){
			dfs(v,u);siz[u]+=siz[v];
			k+=siz[v]*(n-siz[v]-1);
		}
	}
	k+=(n-siz[u])*(siz[u]-1);
	ans-=k/2;
}
signed main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;cin>>u>>v;add(u,v);add(v,u);
	}ans=n*(n-1)*(n-2)/2/3; 
	dfs(1,0);
	cout<<ans<<"\n";
}

\(Ex-snukesnuke\)

题意：

有 \(n\) 个人，每个人有一个想要的名字 \(s_i\)，是一个字符串，可能会重复。我们从 \(1\) 到 \(n\) 取名字，若第 \(i\) 个人喜欢的名字被占用了，则把 \(s_i\) 复制一倍再检查，若仍然被占用了，就再接一倍 \(s_i\)，直到没有重复为止。

对于每个 \(i\)，求出最后第 \(i\) 个人的名字是由多少个 \(s_i\) 构成的。

题解：

我们考虑什么情况下前面的人可能会占用后面的人的名字——前面的人和后面的人有共同的最小循环元。

用 Z函数处理出每个人名字的最小循环元，然后按照最小循环元，以编号顺序分组，依次解决每一组。

对于每一组，我们只需记录原 \(s_i\) 的长度，并且除以循环元长度（防太长爆了），然后仔细观察，发现问题化为了：

维护一个含有若干整数的集合 \(S\)，有 \(a_1\sim a_m\) 个数依次插入 \(S\)，插入规则如下：

对于每个 \(a_i\)，找到最小的满足 \(xa_i\notin S(x>0)\) 的\(x\)，将 \(xa_i\) 插入集合中。

这个 \(x\) 就是 \(i\) 的答案。

这是一个经典的问题。倍数法的时间复杂度是 \(O(n\log n)\)，我们也尝试做到这个复杂度。

注意到对 \(a_i\) 去重后，我们枚举每一个数的倍数暴力插入的复杂度也只有 \(O(n\log n)\) （倍数法推论）。所以我们考虑优化掉重复的 \(a_i\)。

这是容易的，记录一个 \(lst_i\)，表示数 \(i\) 的倍数上一次已经枚举到了 \(lst_i\)，下一次直接从 \(i+lst_i\) 开始枚举。

注意到倍数可能会很大，存不下，并且判断相同的循环元等我们需要用到STL容器比如map等，而且枚举倍数法时候，标记数组 \(vis\) 也有可能很大，开不下，需要用 map。则设 \(L\) 为字符总长，时间复杂度为 \(O(L\log^2 L)\)

#define N 505050
#define pr pair<int,int>
#define x first
#define id second
#define mk make_pair
char a[N];
int cnt[N],z[N],n,ans[N],t,num,lst[N];
map<int,int>vis;
map<string,int>h;
vector<pr >c[N]; 
void init_str(int id){ 
	int n=strlen(a+1);
	for(int i=1;i<=n+1;i++)z[i]=0;
	if(n==1){
		string x;x+=a[1];
		if(!h[x])h[x]=++num;
		c[h[x]].push_back(mk(1,id));return ;
	}
	z[1]=n;int l=0,r=0;
	for(int i=2;i<=n;i++){
		if(i<=r)z[i]=min(z[i-l+1],r-i+1);
		while(i+z[i]<=n&&a[z[i]+1]==a[i+z[i]])++z[i];
		if(i+z[i]-1>r)r=i+z[i]-1,l=i;
	}z[n+1]=0;
	for(int i=2;i<=n+1;i++){
		if(i+z[i]-1==n&&n%(i-1)==0){
			string x;
			for(int j=1;j<i;j++)x+=a[j];
			if(!h[x])h[x]=++num;
			c[h[x]].push_back(mk(n/(i-1),id));
			return ;
		}
	}
}
void solve(int id){
	for(auto x:c[id]){
		int i=x.x;
		if(lst[x.x]!=0)i=lst[x.x]+x.x;
		for(;i;i+=x.x){
			if(vis[i]!=id){
				lst[x.x]=i;vis[i]=id;ans[x.id]=i/x.x;
				break;
			}
		} 
	}
	for(auto x:c[id])lst[x.x]=0;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n;for(int i=1;i<=n;i++){
		cin>>a+1;
		init_str(i);
	}
	for(int i=1;i<=num;i++)solve(i);
	for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
}

\(Trick\) 总结

很简单，没什么好说的。

1. 利用体积空间较小性质解题
2. 容斥原理
3. Z函数，KMP以及倍数法时间渐进 \(O(n\log n)\) 的结论。