又是一道题意杀………… 首先可以发现1号操作显然不能出现。 然后我们把所有单词倒着建一棵trie，去掉一些没有用的节点。比如说abbbb和bb这两个单词，abbbb的前两个b是多余的。所以最后留下来的树，每个节点（根节点除外）都代表了一个单词。所以题目就变成了给每个节点编号。 首先为了不出现1号操作，每个父亲节点的编号都必须比孩子编号小。然后显然就是一个dfs序（别告诉我为什么显然我也不知道TAT） 然后就要考虑优先访问那个孩子。其实这也是比较（不）显然的，一定优先访问size较小的子树。感性的想一想，如果有5个孩子1、2、3、4、5，当前访问1的子树的时候，每次访问到1的新孩子，2、3、4、5的编号就要统统向后移一位。 如果这都不够感性，那就想想打cf的时候，为什么从简单的做起分数高？一开始每道题目每分钟扣4分，一旦做出一道题，那么这道题的时间分就不会动了。放到这道题也是一个道理。（感觉写完这段自己就成了个傻逼） 然后。。。不要问我空间为什么顶着上限。。我已经分不清1e5和5e5了。
#include<cmath>#include<cstdio>#include<vector>#include <queue>#include<cstring>#include<iomanip>#include<stdlib.h>#include<iostream>#include<algorithm>#define ll long long#define inf 1000000000#define mod 1000000007#define N 500050#define fo(i,a,b) for(i=a;i<=b;i++)#define fd(i,a,b) for(i=a;i>=b;i--)using namespace std;char s[N];int rt,n,i,tot;ll res;int son[N][30],tag[N],id[N],siz[N],num[N];vector<int> sn[N/5];void ins(){ int len = strlen(s+1); int p = rt; int i; fd(i,len,1) { if (!son[p][s[i]-'a']) son[p][s[i]-'a'] = ++tot; p = son[p][s[i]-'a']; } tag[p] = 1;}void dfs(int x){ int i; if (tag[x]) {sn[id[x]].push_back(++tot); id[x] = tot;} fo(i,0,25) if (son[x][i]) { id[son[x][i]] = id[x]; dfs(son[x][i]); }}void dfs2(int x){ siz[x] = 1; for (int i = 0;i < sn[x].size(); i++) { int t = sn[x][i]; dfs2(t); siz[x] += siz[t]; }}bool cmp(int x,int y) {return siz[x] < siz[y];}void calc(int x){ sort(sn[x].begin(),sn[x].end(),cmp); for (int i = 0;i < sn[x].size(); i++) { int t = sn[x][i]; num[t] = ++tot; res += num[t] - num[x]; calc(t); }}int main(){ scanf("%d",&n); tot = rt = 1; fo(i,1,n) {scanf("%s",s+1); ins();} id[1] = tot = 1; dfs(1); dfs2(1); tot = 0; calc(1); PRintf("%lld/n",res); return 0; }新闻热点
疑难解答
