2026-08-24~25 hetao1733837 的刷题记录CF1368G Shifting Dominoes原题链接G. Shifting Dominoes分析我竟然还记得/ll就是一个空格可以向其横向多米诺的另外一个去连边。我们会得到一个森林为什么不会有环呢我们发现环的出现是中间有奇数个空格的情况根本不可能输入进来这题不如叫华容道……。那么我们发现初始扔掉一个骨牌会出现两个空格也就是两棵树我们进行d f s dfsdfs序即可确定一个区间那么我们发现这是两个区间那么我们把l ll和r rr整成两个轴就是矩形面积并我们只需要扫描线做一下就可以了。正解#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN400005;intn,m;intget_id(intx,inty){return(x-1)*my;}structnode{intx,y;intval;};vectornodee[N];structsegtree{structtree{intl,r,tag,len;}tr[N2];voidpushup(intp){if(tr[p].tag){tr[p].lentr[p].r-tr[p].l1;}else{tr[p].lentr[p1].lentr[p1|1].len;}}voidbuild(intp,intl,intr){tr[p].ll;tr[p].rr;tr[p].tagtr[p].len0;if(lr)return;intmid(lr)1;build(p1,l,mid);build(p1|1,mid1,r);pushup(p);}voidmodify(intp,intl,intr,ints,intt,intval){if(slrt){tr[p].tagval;pushup(p);return;}intmid(lr)1;if(smid)modify(p1,l,mid,s,t,val);if(tmid)modify(p1|1,mid1,r,s,t,val);pushup(p);}intquery(){returntr[1].len;}}T;string s;intfa[N];vectorintg[N];intdfn[N],tot,low[N];voiddfs(intu){dfn[u]tot;for(autov:g[u]){dfs(v);}low[u]tot;}vectorintc[N];intdx[]{0,-1,0,1};intdy[]{-1,0,1,0};signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnm;for(inti1;in;i){cins;c[i].push_back(0);for(intj0;jm;j){if(s[j]R){c[i].push_back(0);}elseif(s[j]D){c[i].push_back(1);}elseif(s[j]L){c[i].push_back(2);}elseif(s[j]U){c[i].push_back(3);}}}for(inti1;in;i){for(intj1;jm;j){for(intk0;k4;k){intniidx[k]*2,njjdy[k]*2;if(ni0||nin||nj0||njm)continue;if(c[ni][nj]!(k2)%4)continue;g[get_id(i,j)].push_back(get_id(ni,nj));fa[get_id(ni,nj)]get_id(i,j);}}}for(inti1;in;i){for(intj1;jm;j){if(!dfn[get_id(i,j)]){intuget_id(i,j);while(fa[u])ufa[u];dfs(u);}}}for(inti1;in;i){for(intj1;jm;j){if((ij)%21){intnxidx[c[i][j]],nyjdy[c[i][j]];intmnxdfn[get_id(i,j)],mxxlow[get_id(i,j)];intmnydfn[get_id(nx,ny)],mxylow[get_id(nx,ny)];e[mnx].push_back({mny,mxy,1});e[mxx1].push_back({mny,mxy,-1});}}}intans0;T.build(1,1,tot);for(inti1;itot;i){for(autotmp:e[i]){T.modify(1,1,tot,tmp.x,tmp.y,tmp.val);}ansT.query();}coutans;}LGP3065 [USACO12DEC] First! G原题链接[USACO12DEC] First! G分析我们发现一个字符串是另一个的前缀那么另外一个就“倒闭”了渐渐aoao化了。剩下的话……我们直接做就是说我们……每次选择一颗子树这个节点是关键的我们会出现一些偏序关系……我们再建一个图吗感觉一个并查集就可以满足吧……维护一下大小关系似乎树状数组也可以并查集好理解一点吧……然后就做完了我几乎做出来了/ll我们发现不合法当且仅当图建出来以后出现环……那非常容易了拿一个拓扑排序就解决了……怎么办啊/ll正解#includebits/stdc.husingnamespacestd;constintN30005,M300005;intn;intch[M][26],tot;string s[N];boolpos[M];voidinsert(intx){intu0;for(inti0;i(int)s[x].length();i){if(!ch[u][s[x][i]-a]){ch[u][s[x][i]-a]tot;}uch[u][s[x][i]-a];}pos[u]true;}intdeg[26];inttopo[N];queueintq;boole[26][26];voidtoposort(){while(!q.empty())q.pop();for(inti0;i26;i){if(!deg[i]){q.push(i);}}while(!q.empty()){intuq.front();q.pop();for(intv0;v26;v){if(e[u][v]){deg[v]--;if(!deg[v])q.push(v);}}}}boolcheck(intx){intu0;memset(e,false,sizeof(e));memset(deg,0,sizeof(deg));for(inti0;i(int)s[x].length();i){if(pos[u])returnfalse;for(intj0;j26;j){if(s[x][i]-a!jch[u][j]!e[s[x][i]-a][j]){e[s[x][i]-a][j]true;deg[j];}}uch[u][s[x][i]-a];}toposort();for(inti0;i26;i){if(deg[i])returnfalse;}returntrue;}boolvis[N];intans;signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;for(inti1;in;i){cins[i];insert(i);}for(inti1;in;i){if(check(i)){ans;vis[i]true;}}coutans\n;for(inti1;in;i){if(vis[i]){couts[i]\n;}}}LGP4407 [JSOI2009] 电子字典原题链接[JSOI2009] 电子字典分析难道说建立两棵字典树一颗正着一颗倒着对于删除和添加操作我思考一下……那似乎也很自然也不用那么麻烦对于增加和替换我们查的时候多遍历一下对于删除直接继续搜就行。记录两个都查到哪了也没什么吧……正解#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN10005*20;intn,m;string w[N];string q[N];intch1[N][26],tot1;boolpos1[N];mapstring,boolbuc;boolvis[N];intncnt;voidinsert(intx){buc[w[x]]true;intu0;for(inti0;i(int)w[x].length();i){if(!ch1[u][w[x][i]-a]){ch1[u][w[x][i]-a]tot1;}uch1[u][w[x][i]-a];}pos1[u]true;}voiddfs(intu,intx,inti,boolflag){if(i(int)q[x].length()pos1[u]flag){if(!vis[u]){ncnt;vis[u]true;}return;}if(!flag){if(i(int)q[x].length()){dfs(u,x,i1,true);}for(intj0;j26;j){if(ch1[u][j]){dfs(ch1[u][j],x,i,true);if(i(int)q[x].length()j!q[x][i]-a){dfs(ch1[u][j],x,i1,true);}}}}if(i(int)q[x].length())return;if(ch1[u][q[x][i]-a])dfs(ch1[u][q[x][i]-a],x,i1,flag);}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnm;for(inti1;in;i){cinw[i];insert(i);}for(intcs1;csm;cs){cinq[cs];if(buc[q[cs]]){cout-1\n;continue;}dfs(0,cs,0,false);coutncnt\n;memset(vis,false,sizeof(vis));ncnt0;}} 2026-08-24~25 hetao1733837 的刷题记录CF1368G Shifting Dominoes原题链接G. Shifting Dominoes分析我竟然还记得/ll就是一个空格可以向其横向多米诺的另外一个去连边。我们会得到一个森林为什么不会有环呢我们发现环的出现是中间有奇数个空格的情况根本不可能输入进来这题不如叫华容道……。那么我们发现初始扔掉一个骨牌会出现两个空格也就是两棵树我们进行d f s dfsdfs序即可确定一个区间那么我们发现这是两个区间那么我们把l ll和r rr整成两个轴就是矩形面积并我们只需要扫描线做一下就可以了。正解#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN400005;intn,m;intget_id(intx,inty){return(x-1)*my;}structnode{intx,y;intval;};vectornodee[N];structsegtree{structtree{intl,r,tag,len;}tr[N2];voidpushup(intp){if(tr[p].tag){tr[p].lentr[p].r-tr[p].l1;}else{tr[p].lentr[p1].lentr[p1|1].len;}}voidbuild(intp,intl,intr){tr[p].ll;tr[p].rr;tr[p].tagtr[p].len0;if(lr)return;intmid(lr)1;build(p1,l,mid);build(p1|1,mid1,r);pushup(p);}voidmodify(intp,intl,intr,ints,intt,intval){if(slrt){tr[p].tagval;pushup(p);return;}intmid(lr)1;if(smid)modify(p1,l,mid,s,t,val);if(tmid)modify(p1|1,mid1,r,s,t,val);pushup(p);}intquery(){returntr[1].len;}}T;string s;intfa[N];vectorintg[N];intdfn[N],tot,low[N];voiddfs(intu){dfn[u]tot;for(autov:g[u]){dfs(v);}low[u]tot;}vectorintc[N];intdx[]{0,-1,0,1};intdy[]{-1,0,1,0};signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnm;for(inti1;in;i){cins;c[i].push_back(0);for(intj0;jm;j){if(s[j]R){c[i].push_back(0);}elseif(s[j]D){c[i].push_back(1);}elseif(s[j]L){c[i].push_back(2);}elseif(s[j]U){c[i].push_back(3);}}}for(inti1;in;i){for(intj1;jm;j){for(intk0;k4;k){intniidx[k]*2,njjdy[k]*2;if(ni0||nin||nj0||njm)continue;if(c[ni][nj]!(k2)%4)continue;g[get_id(i,j)].push_back(get_id(ni,nj));fa[get_id(ni,nj)]get_id(i,j);}}}for(inti1;in;i){for(intj1;jm;j){if(!dfn[get_id(i,j)]){intuget_id(i,j);while(fa[u])ufa[u];dfs(u);}}}for(inti1;in;i){for(intj1;jm;j){if((ij)%21){intnxidx[c[i][j]],nyjdy[c[i][j]];intmnxdfn[get_id(i,j)],mxxlow[get_id(i,j)];intmnydfn[get_id(nx,ny)],mxylow[get_id(nx,ny)];e[mnx].push_back({mny,mxy,1});e[mxx1].push_back({mny,mxy,-1});}}}intans0;T.build(1,1,tot);for(inti1;itot;i){for(autotmp:e[i]){T.modify(1,1,tot,tmp.x,tmp.y,tmp.val);}ansT.query();}coutans;}LGP3065 [USACO12DEC] First! G原题链接[USACO12DEC] First! G分析我们发现一个字符串是另一个的前缀那么另外一个就“倒闭”了渐渐aoao化了。剩下的话……我们直接做就是说我们……每次选择一颗子树这个节点是关键的我们会出现一些偏序关系……我们再建一个图吗感觉一个并查集就可以满足吧……维护一下大小关系似乎树状数组也可以并查集好理解一点吧……然后就做完了我几乎做出来了/ll我们发现不合法当且仅当图建出来以后出现环……那非常容易了拿一个拓扑排序就解决了……怎么办啊/ll正解#includebits/stdc.husingnamespacestd;constintN30005,M300005;intn;intch[M][26],tot;string s[N];boolpos[M];voidinsert(intx){intu0;for(inti0;i(int)s[x].length();i){if(!ch[u][s[x][i]-a]){ch[u][s[x][i]-a]tot;}uch[u][s[x][i]-a];}pos[u]true;}intdeg[26];inttopo[N];queueintq;boole[26][26];voidtoposort(){while(!q.empty())q.pop();for(inti0;i26;i){if(!deg[i]){q.push(i);}}while(!q.empty()){intuq.front();q.pop();for(intv0;v26;v){if(e[u][v]){deg[v]--;if(!deg[v])q.push(v);}}}}boolcheck(intx){intu0;memset(e,false,sizeof(e));memset(deg,0,sizeof(deg));for(inti0;i(int)s[x].length();i){if(pos[u])returnfalse;for(intj0;j26;j){if(s[x][i]-a!jch[u][j]!e[s[x][i]-a][j]){e[s[x][i]-a][j]true;deg[j];}}uch[u][s[x][i]-a];}toposort();for(inti0;i26;i){if(deg[i])returnfalse;}returntrue;}boolvis[N];intans;signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;for(inti1;in;i){cins[i];insert(i);}for(inti1;in;i){if(check(i)){ans;vis[i]true;}}coutans\n;for(inti1;in;i){if(vis[i]){couts[i]\n;}}}LGP4407 [JSOI2009] 电子字典原题链接[JSOI2009] 电子字典分析难道说建立两棵字典树一颗正着一颗倒着对于删除和添加操作我思考一下……那似乎也很自然也不用那么麻烦对于增加和替换我们查的时候多遍历一下对于删除直接继续搜就行。记录两个都查到哪了也没什么吧……正解#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN10005*20;intn,m;string w[N];string q[N];intch1[N][26],tot1;boolpos1[N];mapstring,boolbuc;boolvis[N];intncnt;voidinsert(intx){buc[w[x]]true;intu0;for(inti0;i(int)w[x].length();i){if(!ch1[u][w[x][i]-a]){ch1[u][w[x][i]-a]tot1;}uch1[u][w[x][i]-a];}pos1[u]true;}voiddfs(intu,intx,inti,boolflag){if(i(int)q[x].length()pos1[u]flag){if(!vis[u]){ncnt;vis[u]true;}return;}if(!flag){if(i(int)q[x].length()){dfs(u,x,i1,true);}for(intj0;j26;j){if(ch1[u][j]){dfs(ch1[u][j],x,i,true);if(i(int)q[x].length()j!q[x][i]-a){dfs(ch1[u][j],x,i1,true);}}}}if(i(int)q[x].length())return;if(ch1[u][q[x][i]-a])dfs(ch1[u][q[x][i]-a],x,i1,flag);}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnm;for(inti1;in;i){cinw[i];insert(i);}for(intcs1;csm;cs){cinq[cs];if(buc[q[cs]]){cout-1\n;continue;}dfs(0,cs,0,false);coutncnt\n;memset(vis,false,sizeof(vis));ncnt0;}} 
)
算法精解与面试技巧)
