有哪些做问卷调查的网站好,南京市住房与城乡建设局网站,php mysql 网站开发实例教程,网站多久C. Code a Trie
大佬题解#xff0c;代码基本就是抄的
对于每一个值计算所有串的LCA#xff0c;也就是最长公共前缀#xff0c;将该节点#xff08;Trie树的节点#xff09;标记#xff0c;对于这些字符串在LCA下面的点一定不存在#xff08;如果存在他们不会返回相同…C. Code a Trie
大佬题解代码基本就是抄的
对于每一个值计算所有串的LCA也就是最长公共前缀将该节点Trie树的节点标记对于这些字符串在LCA下面的点一定不存在如果存在他们不会返回相同的值
每个Trie树中的节点只能被标记一次并且从跟到LCA路径上的变必须存在
dfs贪心计算每个子树中最少的节点 插入时统计cnt[u]表示它的子树中被标记为LCA的点的数量
如果cnt[u]1这个点必选如果说该节点没被标记为LCA那么它可以替代它一个儿子称为那个值的LCA如果被标记为LCA它的儿子被标记那就必须选。如果cnt[u]1贪心选择该点儿子不选如果cnt[u]0贪心不选
#include bits/stdc.h
using namespace std;
using ll long long;
const int N500010;int n,a[N],b[N],cnt[N],ans;
string s[N];
vectorstring g[N];
int t[N][27],idx;
bool lca[N];
void init()
{cinn;int m0;for(int i1;in;i) {cins[i]a[i];ms[i].size();}idx0;for(int i1;in;i) g[i].clear();for(int i0;im;i) memset(t[i],0,sizeof t[i]);for(int i0;im;i) lca[i]0,cnt[i]0;
}bool check(vectorstring v) {//暴力寻找LCAsort(v.begin(),v.end(),[](string a, string b) {return a.size()b.size();});int len0;for(int i0;iv[0].size();i) {int ok1;for(int j0;jv.size()ok;j)if(v[j][i]!v[0][i]) ok0;if(ok) len;else break;}// Trie树插入int p0;for(int i0;ilen;i) {cnt[p];//子树中的lcaint cv[0][i]-a;if(t[p][c]-1) return 0; //节点不存在if(!t[p][c]) t[p][c]idx;pt[p][c];} if(lca[p]) return 0;lca[p]1;cnt[p];// lca 后面的一定不存在 打上标记for(int i0;iv.size();i) {if(v[i].size()len) continue; int cv[i][len]-a;if(t[p][c]0) return 0;// 不存在的点存在了t[p][c]-1;}return 1;
}
void dfs(int u) {if(cnt[u]1) ans;bool fllca[u]0;for(int i0;i26;i) {int vt[u][i];if(!v||v-1) continue;if(cnt[v]1) {if(!fl) ans;else fl0;}else dfs(v);}
}
void co(int cid, int x) {cout Case # cid : x\n;
}
void work(int cid) {int m0;for(int i1;in;i)b[m]a[i];// 离散化sort(b1,b1m);munique(b1,b1m)-b-1;for(int i1;in;i) a[i]lower_bound(b1,b1m,a[i])-b;// 统计相同值的字符串for(int i1;in;i) g[a[i]].push_back(s[i]);// 判断进行插入for(int i1;im;i)if(!check(g[i])) {co(cid, -1);return;}ans0;cnt[0]; //根节点必须选dfs(0);co(cid, ans);
}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T1;cinT;for(int i1;iT;i) {init();work(i);}return 0;
}
