APIO2014练习记录

发表于 | 分类于


所有题目都是在uoj上提交完成的。
【APIO2014】Palindromes - 题目 - Universal Online Judge
【APIO2014】Split the sequence - 题目 - Universal Online Judge
【APIO2014】Beads and wires - 题目 - Universal Online Judge

Palindromes uoj 103

这题做的时候无限犯二。。。
1.第一眼看题，看成“存在值之和”，然后浪费半小时。
2.意识到可能需要用马拉车这种东西的时候…突然忘记怎么打。。。
3.上午才学完的SAM，居然不知道用。。。

步入正题：
题目要求的是串中回文子串的长度与出现次数。
首先，一个串的回文子串数量是$O(n)$级的，这点我们使用manacher时，能拓展R数组的即为本质不同的回文子串，长度此时也是确定的。
然后，出现次数…子串的出现次数…我上午才学完的SAM，怎么就忘了呢。。。
看到hzwer标签上的“后缀自动机”的时候，顿时感觉自己智商不在线。
这样，扔到一个后缀自动机里面去，对自动机每个节点x维护一个$size_x$，然后我们从r对应的节点出发，在parent树上倍增到[l,r]对应的节点，用它的$size*(r-l+1)$更新答案。
代码十分丑陋，hzw打的维护size好神奇…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#include <complex>
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long LL;
int n,m;
int in[600010][26],fa[600010][25],mx[600010],sz[600010];char ch[300010],a[600010];
int pl[300010],deep[600010];
int last,nn;
vector<int>g[600010];
void Insert(int x,int Pl){
	int p=last,np=++nn;sz[np]=1;
	last=np;mx[np]=mx[p]+1;pl[Pl]=np;
	while(~p&&!in[p][x])in[p][x]=np,p=fa[p][0];
	if(p==-1)return;
	int q=in[p][x];
	if(mx[q]==mx[p]+1)fa[np][0]=q;
	else{
		int nq=++nn;mx[nq]=mx[p]+1;
		for(int i=0;i<26;i++)in[nq][i]=in[q][i];
		fa[nq][0]=fa[q][0];
		fa[np][0]=fa[q][0]=nq;
		while(~p&&in[p][x]==q)in[p][x]=nq,p=fa[p][0];
	}
}

void dfs(int x){
	for(int i=1;(1<<i)<=deep[x];i++){
		fa[x][i]=fa[fa[x][i-1]][i-1];
	}
	for(int i=0,siz=g[x].size();i<siz;i++){
		fa[g[x][i]][0]=x;
		deep[g[x][i]]=deep[x]+1;
		dfs(g[x][i]);
		sz[x]+=sz[g[x][i]];
	}
}
LL ans=0,R[600010],pos,MR;
LL query(int l,int r){
	int j=pl[r];
	for(int i=20;i>=0;i--){
		int t=fa[j][i];
		if(mx[t]>=(r-l+1))j=t;
	}
	return (LL)sz[j]*(r-l+1);
}
void manacher(){
	for(int i=0;i<n;i++){
		a[i*2]=ch[i];
		a[i*2+1]='#';
	}
	pos=0,MR=-1;
	for(int i=0;i<2*n-1;i++){
		if(i<MR)R[i]=min(R[2*pos-i],MR-i);
		else R[i]=1;
		while(i-R[i]+1>=0&&i+R[i]-1<=2*n-2&&a[i+R[i]-1]==a[i-R[i]+1]){
			if(a[i+R[i]-1]!='#'){
				ans=max(ans,query(i-R[i]+1>>1,i+R[i]-1>>1));
			}R[i]++;
		}R[i]--;
		if(R[i]+i-1>MR){
			pos=i;MR=i+R[i]-1;
		}
	}
}
int main(){
#ifdef WK
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    scanf("%s",ch);n=strlen(ch);fa[0][0]=-1;
    for(int i=0;i<n;i++)Insert(ch[i]-'a',i);
	for(int i=1;i<=nn;i++)g[fa[i][0]].push_back(i);
    dfs(0);
    manacher();
    printf("%lld\n",ans);
	return 0;
}

Split the sequence uoj 104

调这个题疯了。。。
直观看上去，就是个DP。
$f_{i,j}$表示第j刀剁在i后面的最大收益。
容易看出，顺序一定是从左往右（或者从右往左）剁是最优的。
记$sum_i$为$\sum_{j=1}^{i}a_j$
那么

首先打了个simple的$O(n^2m)$确保公式无误。
假设j>k,且取j的决策比取k优秀，那么(以下省略第二维）：

然后它就可以变形为一个可斜率优化的式子：

此外额外维护一个数组pre，$pre_{i,j}$表示$f_{i,j}$是由决策$f_{pre_{i,j},j-1}$取到
接下来的情节，应该就是直接上斜率优化愉快AC。
然而，并不。
1.f数组和pre数组如果都开$10^5*200$的话直接MLE，so，f数组要改为滚动数组。（也许是因为我后来发现我SB把pre开成LL了。。。）
2.被各种卡常数（我代码一直就常数大QAQ），各种优化才过。。。
惨啊。。。

代码各位大佬轻喷。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#include <complex>
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long LL;
typedef complex<double>E;
LL f[100010][2];int pre[100010][210];
int n,m;
int sum[100010];int st[100010];
inline int read() {
	char ch=getchar();
	int rtn=0,f=1;
	for (;ch>'9'||ch<'0';ch=getchar())if(ch=='-')f=-1;
	for (;ch<='9'&&ch>='0';ch=getchar())rtn=rtn*10+ch-'0';
	return rtn*f;
}
inline double K(int x,int y,int t){
	if (sum[x]==sum[y]) return 1e9;
	return (double)(f[x][t]-f[y][t])/(sum[x]-sum[y]);
}
int q[100010],l,r;
int main(){
#ifdef WK
    freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+read();
    for(int i=1;i<=n;i++)f[i][1]=(LL)(sum[n]-sum[i])*(sum[i]);
    int last=1;
    for(int j=2;j<=m;j++){
    	r=0;l=1;q[++r]=j-1;
    	for(int i=j;i<=n;i++){
    		while(r-l&&K(q[l+1],q[l],last)>=sum[n]-sum[i])l++;
    		f[i][last^1]=(LL)(sum[i]-sum[q[l]])*(sum[n]-sum[i])+f[q[l]][last];
    		pre[i][j]=q[l];
    		while(r-l&&K(i,q[r],last)>=K(q[r],q[r-1],last))r--;
    		q[++r]=i;
		}last^=1;
	}
	LL ans=-1e9;int mf;
	for(int i=1;i<=n;i++){
		if(ans<f[i][last]&&(m==1||~pre[i][m])){
			ans=f[i][last];
			mf=i;
		}
	}
	printf("%lld\n",ans);
	if(!ans){
		for(int i=1;i<=m;i++)printf("%d ",i);
		return 0;
	}
	for(int i=mf,j=m;;){
		st[++st[0]]=i;
		i=pre[i][j];j--;
		if(!j)break;
	}
	for(int i=st[0];i;i--)printf("%d ",st[i]);
	return 0;
}

Beads and wires uoj 105

这个题挺有趣啊。。。
我不停地开脑洞，发现只要给每个节点，要么不匹配，要么匹配父亲与它和它与一个儿子链接的两条蓝边即可符合题意。
然后我只会枚举根，$(O(n^2))$滚粗。。。
正解…什么鬼…换根DP？
学习一下，再做更新QAQ

总结

一句话
我要是到了APIO2017的考场上怎么办啊QAQ