差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:contest4 [2020/07/07 10:38]
jxm2001
+++ 2020-2021:teams:legal_string:contest4 [2020/07/07 11:07] (当前版本)
jxm2001
@@ 行 336: / 行 336: @@
 </hidden>
+===== I. Running Away From the Barn =====
+=== 题解 ===
+这题思路还挺多的。有跑树上差分 $+$ 倍增的；还有按 $\text{depth}$ 降序询问，然后权值线段树/树状数组维护答案的；还有左偏树的。
+比赛时没想到调整询问顺序，直接写了个主席树 $+$ 权值线段树，感觉又写麻烦了。
+<hidden 比赛代码>
+<code cpp>
+#include <iostream>
+#include <cstdio>
+#include <cstdlib>
+#include <algorithm>
+#include <string>
+#include <sstream>
+#include <cstring>
+#include <cctype>
+#include <cmath>
+#include <vector>
+#include <set>
+#include <map>
+#include <stack>
+#include <queue>
+#include <ctime>
+#include <cassert>
+#define _for(i,a,b) for(int i=(a);i<(b);++i)
+#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
+#define mem(a,b) memset(a,b,sizeof(a))
+using namespace std;
+typedef long long LL;
+inline int read_int(){
+	int t=0;bool sign=false;char c=getchar();
+	while(!isdigit(c)){sign|=c=='-';c=getchar();}
+	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
+	return sign?-t:t;
+}
+inline LL read_LL(){
+	LL t=0;bool sign=false;char c=getchar();
+	while(!isdigit(c)){sign|=c=='-';c=getchar();}
+	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
+	return sign?-t:t;
+}
+inline char get_char(){
+	char c=getchar();
+	while(c==' '||c=='\n'||c=='\r')c=getchar();
+	return c;
+}
+inline void write(LL x){
+	register char c[21],len=0;
+	if(!x)return putchar('0'),void();
+	if(x<0)x=-x,putchar('-');
+	while(x)c[++len]=x%10,x/=10;
+	while(len)putchar(c[len--]+48);
+}
+inline void space(LL x){write(x),putchar(' ');}
+inline void enter(LL x){write(x),putchar('\n');}
+const int MAXN=2e5+5;
+struct Node{
+	int lef,rig,val;
+};
+Node node[MAXN*40];
+int cnt,root[MAXN];
+int nodecopy(int k){
+	node[++cnt]=node[k];
+	return cnt;
+}
+void build(int &k,int lef,int rig){
+	k=++cnt;
+	int mid=lef+rig>>1;
+	if(lef==rig)
+	return;
+	build(node[k].lef,lef,mid);
+	build(node[k].rig,mid+1,rig);
+}
+void update(int &k,int p,int lef,int rig,int pos){
+	k=nodecopy(p);
+	node[k].val++;
+	if(lef==rig)
+	return;
+	int mid=lef+rig>>1;
+	if(mid<pos)
+	update(node[k].rig,node[p].rig,mid+1,rig,pos);
+	else
+	update(node[k].lef,node[p].lef,lef,mid,pos);
+}
+int query(int k1,int k2,int lef,int rig,int L,int R){
+	if(L<=lef&&rig<=R)
+	return node[k1].val-node[k2].val;
+	int mid=lef+rig>>1;
+	if(mid>=R)
+	return query(node[k1].lef,node[k2].lef,lef,mid,L,R);
+	else if(mid<L)
+	return query(node[k1].rig,node[k2].rig,mid+1,rig,L,R);
+	else
+	return query(node[k1].lef,node[k2].lef,lef,mid,L,R)+query(node[k1].rig,node[k2].rig,mid+1,rig,L,R);
+}
+int head[MAXN],edge_cnt;
+struct Edge{
+	int to,next;
+	LL w;
+}edge[MAXN];
+void Insert(int u,int v,LL w){
+	edge[++edge_cnt].next=head[u];
+	edge[edge_cnt].to=v;
+	edge[edge_cnt].w=w;
+	head[u]=edge_cnt;
+}
+LL dep[MAXN],dw[MAXN],b[MAXN];
+int dfs_t,lf[MAXN],rf[MAXN];
+void dfs(int u,LL d){
+	lf[u]=++dfs_t;dep[u]=d;dw[dfs_t]=d;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		dfs(v,d+edge[i].w);
+	}
+	rf[u]=dfs_t;
+}
+int main()
+{
+	int n=read_int(),u;
+	LL L=read_LL(),w;
+	_rep(i,2,n){
+		u=read_int(),w=read_LL();
+		Insert(u,i,w);
+	}
+	dfs(1,0);
+	memcpy(b,dep,sizeof(dep));
+	sort(b+1,b+n+1);
+	int m=unique(b+1,b+n+1)-b;
+	build(root[0],1,m);
+	_rep(i,1,n)
+	update(root[i],root[i-1],1,m,lower_bound(b+1,b+m,dw[i])-b);
+	_rep(i,1,n)
+	enter(query(root[rf[i]],root[lf[i]-1],1,m,1,upper_bound(b+1,b+m,dep[i]+L)-b-1));
+	return 0;
+}
+</code>
+</hidden>
+<hidden 正解代码>
+<code cpp>
+#include<bits/stdc++.h>
+using namespace std;
+const int N=200005;
+int n,id[N],r[N],now,ans[N];
+pair<long long,int> a[N];
+struct BIT
+{
+    int tree[N];
+    void modify(int x,int val)
+    {
+        for(;x<=n;x+=x&-x)
+            tree[x]+=val;
+    }
+    int query(int x)
+    {
+        int ans=0;
+        for(;x;x-=x&-x)
+            ans+=tree[x];
+        return ans;
+    }
+}T;
+//树状数组模板
+vector<pair<int,long long>> mat[N];
+void dfs(int k)
+{
+    id[k]=++now;
+  //dfs序
+    for(auto e:mat[k])
+    {
+        a[e.first]=make_pair(a[k].first+e.second,e.first);
+        dfs(e.first);
+    }
+    r[k]=now;
+  //结束时间戳
+}
+int main()
+{
+    long long l;
+    cin>>n>>l;
+    for(int i=2;i<=n;i++)
+    {
+        int p;
+        long long w;
+        cin>>p>>w;
+        mat[p].push_back(make_pair(i,w));
+    }
+    a[1]=make_pair(0ll,1);
+    dfs(1);
+    sort(a+1,a+n+1);
+    int j=n;
+    for(int i=n;i;i--)
+    {
+        for(;a[j].first-a[i].first>l;j--)
+            T.modify(id[a[j].second],-1);
+      //删除超过距离超过L的点
+        T.modify(id[a[i].second],1);
+      //插入当前点
+        ans[a[i].second]=T.query(r[a[i].second])-T.query(id[a[i].second]-1);
+      //统计子树答案
+    }
+    for(int i=1;i<=n;i++)
+        cout<<ans[i]<<endl;
+    return 0;
+}
+</code>
+</hidden>
+===== J. First! =====
+=== 题解 ===
+$\text{Trie}$ 建树，然后询问每个单词结点，如果他是某个单词结点的子结点，一定不合法。
+沿路把 $\text{Trie}$  的其他分支代表的字母向该路径代表字母连单向边，最后跑一下 $26$ 个字母的拓扑，看看合不合法。
+<hidden 赛后代码>
+<code cpp>
+#include <iostream>
+#include <cstdio>
+#include <cstdlib>
+#include <algorithm>
+#include <string>
+#include <sstream>
+#include <cstring>
+#include <cctype>
+#include <cmath>
+#include <vector>
+#include <set>
+#include <map>
+#include <stack>
+#include <queue>
+#include <ctime>
+#include <cassert>
+#define _for(i,a,b) for(int i=(a);i<(b);++i)
+#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
+#define mem(a,b) memset(a,b,sizeof(a))
+using namespace std;
+typedef long long LL;
+inline int read_int(){
+	int t=0;bool sign=false;char c=getchar();
+	while(!isdigit(c)){sign|=c=='-';c=getchar();}
+	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
+	return sign?-t:t;
+}
+inline LL read_LL(){
+	LL t=0;bool sign=false;char c=getchar();
+	while(!isdigit(c)){sign|=c=='-';c=getchar();}
+	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
+	return sign?-t:t;
+}
+inline char get_char(){
+	char c=getchar();
+	while(c==' '||c=='\n'||c=='\r')c=getchar();
+	return c;
+}
+inline void write(LL x){
+	register char c[21],len=0;
+	if(!x)return putchar('0'),void();
+	if(x<0)x=-x,putchar('-');
+	while(x)c[++len]=x%10,x/=10;
+	while(len)putchar(c[len--]+48);
+}
+inline void space(LL x){write(x),putchar(' ');}
+inline void enter(LL x){write(x),putchar('\n');}
+const int MAXS=3e5+5,MAXN=3e5+5;
+int ch[MAXS][26],val[MAXS],cnt;
+char temp[MAXN],*buf[MAXN];
+void Insert(char *s){
+	int len=strlen(s),pos=0;
+	_for(i,0,len){
+		int c=s[i]-'a';
+		if(!ch[pos][c])
+		ch[pos][c]=++cnt;
+		pos=ch[pos][c];
+	}
+	val[pos]++;
+}
+int a[26][26],in[26],vis[26];
+bool topu(){
+	mem(in,0);
+	_for(i,0,26)
+	_for(j,0,26){
+		if(a[i][j])
+		in[j]++;
+	}
+	queue<int> q;
+	_for(i,0,26){
+		if(!in[i])
+		q.push(i);
+	}
+	while(!q.empty()){
+		int u=q.front();q.pop();
+		_for(i,0,26){
+			if(a[u][i]){
+				in[i]--;
+				if(!in[i])
+				q.push(i);
+			}
+		}
+	}
+	_for(i,0,26)
+	if(in[i])
+	return false;
+	return true;
+}
+bool query(char *s){
+	mem(a,0);
+	int len=strlen(s),pos=0;
+	_for(i,0,len){
+		if(val[pos])
+		return false;
+		int c=s[i]-'a';
+		_for(j,0,26){
+			if(j==c||ch[pos][j]==0)
+			continue;
+			a[j][c]=1;
+		}
+		pos=ch[pos][c];
+	}
+	return topu();
+}
+bool ok[MAXN];
+int main()
+{
+	int n=read_int();
+	_for(i,0,n){
+		gets(temp);
+		buf[i]=(char*)malloc(strlen(temp)+1);
+		strcpy(buf[i],temp);
+	}
+	_for(i,0,n)
+	Insert(buf[i]);
+	int tot=0;
+	_for(i,0,n)
+	ok[i]=query(buf[i]),tot+=ok[i];
+	enter(tot);
+	_for(i,0,n)
+	if(ok[i])
+	puts(buf[i]);
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具