CVBB ACM Team

用户工具

站点工具

您在这里: front_page » 2020-2021 » teams » legal_string » contest4
2020-2021:teams:legal_string:contest4

目录

比赛链接

题解

A. Island Travels

题解

$\text{bfs}$ 求一下连通块，再 $\text{bfs}$ 求一下最短路，最后一个状压 $\text{dp}$ 就好了。

比赛的时候把最后的 $\text{dp}$ 当成 $\text{TSP}$ 问题了，但其实可以走重复的路，不然会漏解。

于是补了个 $\text{Floyd}$ 算法，就 $\text{AC}$ 了。

赛后代码

赛后代码 

#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;
}

B. Cow Lineup

题解

直接取尺法就好了，但比赛的时候写麻烦了，还写了个线段树维护答案，其实不需要。

比赛代码

比赛代码 

#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;
}

正解代码

正解代码 

#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 ;
}

I. Running Away From the Barn

题解

这题思路还挺多的。有跑树上差分 $+$ 倍增的；还有按 $\text{depth}$ 降序询问，然后权值线段树/树状数组维护答案的；还有左偏树的。

比赛时没想到调整询问顺序，直接写了个主席树 $+$ 权值线段树，感觉又写麻烦了。

比赛代码

比赛代码 

#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;
}

正解代码

正解代码 

#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;
}

J. First!

题解

$\text{Trie}$ 建树，然后询问每个单词结点，如果他是某个单词结点的子结点，一定不合法。

沿路把 $\text{Trie}$ 的其他分支代表的字母向该路径代表字母连单向边，最后跑一下 $26$ 个字母的拓扑，看看合不合法。

赛后代码

赛后代码 

#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;
}
2020-2021/teams/legal_string/contest4.txt · 最后更改: 2020/07/07 11:07 由 jxm2001

页面工具

除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki
京ICP备20018844号-3