差别

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

--- 2020-2021:teams:legal_string:contest4 [2020/07/07 10:31]
jxm2001 创建
+++ 2020-2021:teams:legal_string:contest4 [2020/07/07 11:07] (当前版本)
jxm2001
@@ 行 7: / 行 7: @@
 ===题解===
-求一下连通块，再求一下最短路，最后一个状压 $\text{dp}$ 就好了。
+$\text{bfs}$ 求一下连通块，再 $\text{bfs}$ 求一下最短路，最后一个状压 $\text{dp}$ 就好了。
-比赛的时候把最后的 $\text{dp}$ 当成 $\text{TSP}$ 问题了，但其实可以走重复的路，不然可能无解。
+比赛的时候把最后的 $\text{dp}$ 当成 $\text{TSP}$ 问题了，但其实可以走重复的路，不然会漏解。
 于是补了个 $\text{Floyd}$ 算法，就 $\text{AC}$ 了。
+<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=55,dir[][2]={{1,0},{-1,0},{0,1},{0,-1}};
+typedef pair<int,int> pii;
+int color[MAXN][MAXN],n,m,tot_c,vis[MAXN][MAXN],dist[MAXN][MAXN],dis[MAXN][MAXN];
+vector<pii> gcc[MAXN];
+char a[MAXN][MAXN];
+bool in(int x,int y){
+    return x>=0&&x<n&&y>=0&&y<m;
+}
+void bfs(pii s,int c){
+    queue<pii> q;
+    q.push(s);
+    color[s.first][s.second]=c;
+    gcc[c].push_back(s);
+    while(!q.empty()){
+        pii u=q.front();q.pop();
+        _for(i,0,4){
+            int x=u.first+dir[i][0],y=u.second+dir[i][1];
+            if(in(x,y)&&a[x][y]=='X'&&color[x][y]==-1){
+                q.push(make_pair(x,y));
+                color[x][y]=c;
+                gcc[c].push_back(make_pair(x,y));
+            }
+        }
+    }
+}
+void bfs_2(int c){
+    queue<pii> q;
+    _for(i,0,gcc[c].size()){
+        vis[gcc[c][i].first][gcc[c][i].second]=c;
+        dist[gcc[c][i].first][gcc[c][i].second]=0;
+        q.push(gcc[c][i]);
+    }
+    while(!q.empty()){
+        pii u=q.front();q.pop();
+        _for(i,0,4){
+            int x=u.first+dir[i][0],y=u.second+dir[i][1];
+            if(in(x,y)&&a[x][y]!='.'&&vis[x][y]!=c){
+                vis[x][y]=c;
+                dist[x][y]=dist[u.first][u.second]+1;
+                if(color[x][y]!=-1)
+                dis[c][color[x][y]]=min(dis[c][color[x][y]],dist[x][y]-1);
+                else
+                q.push(make_pair(x,y));
+            }
+        }
+    }
+}
+void bf(){
+	_for(i,0,tot_c)
+	dis[i][i]=0;
+	_for(i,0,tot_c)
+	_for(j,0,tot_c)
+	_for(k,0,tot_c)
+	dis[i][j]=min(dis[i][j],dis[i][k]+dis[j][k]);
+}
+const int MAXS=1<<15;
+int dp[15][MAXS];
+int main()
+{
+    n=read_int(),m=read_int();
+    _for(i,0,n)
+    gets(a[i]);
+    mem(color,-1);mem(vis,-1);
+    _for(i,0,n)
+    _for(j,0,m){
+        if(a[i][j]=='X'&&color[i][j]==-1)
+        bfs(make_pair(i,j),tot_c++);
+    }
+    mem(dis,127/3);
+    _for(i,0,tot_c)
+    bfs_2(i);
+    int MS=(1<<tot_c)-1;
+    mem(dp,127/3);
+    _for(i,0,tot_c)
+    dp[i][MS^(1<<i)]=0;
+    for(int s=MS;s>=0;s--){
+    	_for(i,0,tot_c){
+    		if(s&(1<<i))
+    		continue;
+    		_for(j,0,tot_c){
+    			if(i!=j)
+    			dp[i][s]=min(dp[i][s],dp[j][s|(1<<i)]+dis[i][j]);
+			}
+		}
+	}
+    int ans=1e9;
+    _for(i,0,tot_c)
+    ans=min(ans,dp[i][0]);
+    enter(ans);
+    return 0;
+}
 </code>
+</hidden>
-===== B.  =====
+===== B. Cow Lineup =====
 === 题解 ===
+直接取尺法就好了，但比赛的时候写麻烦了，还写了个线段树维护答案，其实不需要。
+<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=1e5+5;
+int a[MAXN],b[MAXN],cnt[MAXN];
+struct Tree{
+	int lef[MAXN<<2],rig[MAXN<<2],w[MAXN<<2];
+	int (*merge)(int,int);
+	void Push_up(int k){w[k]=merge(w[k<<1],w[k<<1|1]);}
+	void build(int k,int L,int R){
+		lef[k]=L,rig[k]=R,w[k]=w[0];
+		if(L==R)
+		return;
+		int M=L+R>>1;
+		build(k<<1,L,M);
+		build(k<<1|1,M+1,R);
+	}
+	void build(int n,int w_0){
+		w[0]=w_0;
+		build(1,1,n);
+	}
+	void update(int k,int p,int v){
+		if(lef[k]==rig[k])
+		return w[k]=v,void();
+		int mid=lef[k]+rig[k]>>1;
+		if(p<=mid)
+		update(k<<1,p,v);
+		else
+		update(k<<1|1,p,v);
+		Push_up(k);
+	}
+	void update_2(int k,int p,int v){
+		if(lef[k]==rig[k])
+		return w[k]+=v,void();
+		int mid=lef[k]+rig[k]>>1;
+		if(p<=mid)
+		update_2(k<<1,p,v);
+		else
+		update_2(k<<1|1,p,v);
+		Push_up(k);
+	}
+	int query(int k,int L,int R){
+		if(L>R)
+		return w[0];
+		if(L<=lef[k]&&rig[k]<=R)
+		return w[k];
+		int mid=lef[k]+rig[k]>>1;
+		if(R<=mid)
+		return query(k<<1,L,R);
+		else if(L>mid)
+		return query(k<<1|1,L,R);
+		return merge(query(k<<1,L,R),query(k<<1|1,L,R));
+	}
+}tree;
+int Max(int a,int b){
+	return a>b?a:b;
+}
+int main()
+{
+	int n=read_int(),k=read_int();
+	_for(i,0,n)
+	a[i]=read_int();
+	memcpy(b,a,sizeof(a));
+	sort(b,b+n);
+	int m=unique(b,b+n)-b;
+	_for(i,0,n)
+	a[i]=lower_bound(b,b+m,a[i])-b;
+	int lef=0,rig=0,tot=0,ans=0;
+	tree.merge=Max;
+	tree.build(m,0);
+	while(lef<n){
+		while(rig<n&&(tot<=(k+1))){
+			cnt[a[rig]]++;
+			if(cnt[a[rig]]==1)
+			tot++;
+			tree.update_2(1,a[rig]+1,1);
+			rig++;
+		}
+		if(tot>(k+1)){
+			rig--;
+			cnt[a[rig]]--;
+			tot--;
+			tree.update_2(1,a[rig]+1,-1);
+		}
+		ans=max(ans,tree.query(1,1,m));
+		cnt[a[lef]]--;
+		if(cnt[a[lef]]==0)
+		tot--;
+		tree.update_2(1,a[lef]+1,-1);
+		lef++;
+	}
+	enter(ans);
+	return 0;
+}
+</code>
+</hidden>
+<hidden 正解代码>
+<code cpp>
+#include<cstdio>
+#include<map>
+int n , k ;
+std :: map < int  , int > cnt ;
+const int N = 1e5 + 10 ;
+int a[N] ;
+inline int max(int x , int y) {
+	return x > y ? x : y ;
+}
+signed main() {
+	scanf("%d %d" , & n , & k) ;
+	for(register int i = 1 ; i <= n ; i ++) scanf("%d" , & a[i]) ;
+	int l = 1 , r  = 0 ;
+	int kind = 0 ;
+	int ans = 0 ;
+	while( r <= n ) {
+		if(++ cnt [ a[++ r]] == 1) kind ++ ;
+		while( kind == k + 2 ) {
+			if(-- cnt[ a[l ++]] == 0) kind -- ;
+		}
+		ans = max (ans , cnt[a[r]]) ;
+	}
+	printf("%d\n" , ans) ;
+	return 0 ;
+}
 </code>
+</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

用户工具

站点工具

差别

页面工具