又是一道題意殺………… 首先可以發(fā)現(xiàn)1號操作顯然不能出現(xiàn)。 然后我們把所有單詞倒著建一棵trie，去掉一些沒有用的節(jié)點(diǎn)。比如說abbbb和bb這兩個單詞，abbbb的前兩個b是多余的。所以最后留下來的樹，每個節(jié)點(diǎn)（根節(jié)點(diǎn)除外）都代表了一個單詞。所以題目就變成了給每個節(jié)點(diǎn)編號。 首先為了不出現(xiàn)1號操作，每個父親節(jié)點(diǎn)的編號都必須比孩子編號小。然后顯然就是一個dfs序（別告訴我為什么顯然我也不知道TAT） 然后就要考慮優(yōu)先訪問那個孩子。其實(shí)這也是比較（不）顯然的，一定優(yōu)先訪問size較小的子樹。感性的想一想，如果有5個孩子1、2、3、4、5，當(dāng)前訪問1的子樹的時候，每次訪問到1的新孩子，2、3、4、5的編號就要統(tǒng)統(tǒng)向后移一位。 如果這都不夠感性，那就想想打cf的時候，為什么從簡單的做起分?jǐn)?shù)高？一開始每道題目每分鐘扣4分，一旦做出一道題，那么這道題的時間分就不會動了。放到這道題也是一個道理。（感覺寫完這段自己就成了個傻逼） 然后。。。不要問我空間為什么頂著上限。。我已經(jīng)分不清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);新聞熱點(diǎn)
疑難解答
