2018.8.16 8:00~11:06
先看t1,成功读错题。。。
以为是一个字符串的所有后缀都得在计划表里，否则权值就得是$n^2$
然后花了一个小时多一点写了一个错误的做法
然后没有分 才发现看错了题意
不过只要稍微改一改就行了
在近两个小时的时候过掉了第一题
然后看t2，显然的线性基+树剖，复杂度$O(n log n imes 60 + q log ^2 n imes 60)$
看了一下不知道能拿多少分 但是想不到更好的做法 于是就写了
获得了90分 真是不可思议
t3花了10分钟敲了一个30分暴力
总分：100+90+30
总结
感觉这一场打的没什么问题了吧
难得啊
题解
T1「SCOI2016」背单词
题面:
题解：
首先把所有字符串倒过来，把后缀变成前缀
然后建立trie树
显然的有一个性质：对于trie树上的一个结点来说，他在最终排列中的位置一定在他的所有祖先之后，所有儿子之前
因为如果不这样，出现了祖先->儿子->自己的情况，我们把儿子和自己调换位置，答案变优
然后考虑一个结点的子树
不难发现子树内部的结点一定靠在一起
因为如果不靠在一起，比如说儿子1->儿子2->儿子1的儿子1->儿子2的儿子1
我们把儿子2和儿子1的儿子1调换位置，儿子1的儿子1和儿子2的儿子1代价都减小
所以一个子树内部的结点靠在一起
最后我们确定子树之间的顺序
现在子树唯一有用的就是他的size
我们把子树设为$1~x$
最后的顺序设为$p_1~p_x$
cost就是$(1)+(1+size_{p_1})+(1+size_{p_1}+size_{p_2})+...+(1+size_{p_1}+size_{p_2}+...+size_{p_{x-1}})$
这样我们看出 应该将size按照升序排列最优
所以我们的做法就是：建立trie树，然后dfs一遍把无效结点去掉（就是那些不是终止结点的点），然后建立一个新的树（压缩之后的trie），dfs找到size，并通过size计算出每个结点的cost值（树形dp），最后dp[1]就是答案
Code：
1 #include<stdio.h> 2 #include<cstring> 3 #include<cstdlib> 4 #include<algorithm> 5 #include<vector> 6 #include<map> 7 #include<set> 8 #include<cmath> 9 #include<iostream> 10 #include<queue> 11 #include<string> 12 using namespace std; 13 typedef long long ll; 14 typedef pair<int,int> pii; 15 typedef long double ld; 16 typedef unsigned long long ull; 17 typedef pair<long long,long long> pll; 18 #define fi first 19 #define se second 20 #define pb push_back 21 #define mp make_pair 22 #define rep(i,j,k) for(register int i=(int)(j);i<=(int)(k);i++) 23 #define rrep(i,j,k) for(register int i=(int)(j);i>=(int)(k);i--) 24 25 ll read(){ 26 ll x=0,f=1;char c=getchar(); 27 while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();} 28 while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();} 29 return x*f; 30 } 31 32 int n; 33 string s[100100]; 34 35 struct TRIE{ 36 int cnt; 37 int pos[520000][26]; 38 int tag[520000]; 39 vector<int> adj[520000]; 40 ll dp[520000],sz[520000]; 41 42 TRIE(){ 43 cnt=1; 44 } 45 46 void ins(string t,int ind){ 47 int pp=1; 48 for(int i=0;i<t.size();i++){ 49 int nw=t[i]-'a'; 50 if(pos[pp][nw]) pp=pos[pp][nw]; 51 else{ 52 cnt++; 53 pos[pp][nw]=cnt; 54 pp=cnt; 55 } 56 } 57 tag[pp]=ind; 58 } 59 60 void dfs(int u,int fa=1){ 61 if(tag[u] && u!=fa) adj[fa].pb(u); 62 for(int i=0;i<26;i++){ 63 int nw=pos[u][i]; 64 if(nw==0) continue; 65 if(tag[u]) dfs(nw,u); 66 else dfs(nw,fa); 67 } 68 } 69 70 void work(int u){ 71 vector<int> nw; 72 sz[u]=1; 73 for(int i=0;i<adj[u].size();i++){ 74 int v=adj[u][i]; 75 work(v); 76 nw.pb(sz[v]); 77 sz[u]+=sz[v]; 78 dp[u]+=dp[v]; 79 } 80 sort(nw.begin(),nw.end()); 81 ll sum=1; 82 for(int i=0;i<nw.size();i++){ 83 dp[u]+=sum; 84 sum+=nw[i]; 85 // cout<<nw[i]<<' '; 86 } 87 //cout<<endl; 88 } 89 90 void calc(){ 91 work(1); 92 cout<<dp[1]<<endl; 93 } 94 } trie; 95 96 int main(){ 97 // freopen("out","w",stdout); 98 n=read(); 99 rep(i,1,n){ 100 cin>>s[i]; 101 reverse(s[i].begin(),s[i].end()); 102 trie.ins(s[i],i); 103 } 104 105 trie.dfs(1); 106 trie.calc(); 107 108 return 0; 109 }