【Codeforces】Rand#416解题报告

  • 本文为博主原创，未经许可不得转载

Vladik and Courtesy

题目大意：给你两个数A、B，和一个计数器cnt，cnt初始值为1，A、B轮流减去cnt，且cnt每减一次后加1，问A、B谁先为负

分析：直接模拟即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
#define FILE "read"
using namespace std;
int main(){
	//freopen(FILE".in","r",stdin);
	//freopen(FILE".out","w",stdout);
	int A,B;  cin>>A>>B;
	for(int i=1;;++i){
		if(i&1)  A-=i;
		else     B-=i;
		if(A<0) {puts("Vladik"); break;}
		if(B<0) {puts("Valera"); break;}
	}
	return 0;
}

　　

　　

Vladik and Complicated Book

题目大意：给你一个序列，每次讲[l,r]排序，问第x个数是否发生变化

分析：每次统计[l,r]内比a[x]小的数的个数，然后判断一下就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
#define FILE "read"
using namespace std;
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
int n,m,a[10010];
int main(){
	//freopen(FILE".in","r",stdin);
	//freopen(FILE".out","w",stdout);
	n=read();  m=read();
	for(int i=1;i<=n;++i) a[i]=read();
	for(int i=1;i<=m;++i){
		int l=read(),r=read(),x=read();
		int temp=a[x],cnt=0;
		for(int j=l;j<=r;++j) if(a[j]<=temp) ++cnt;
		if(cnt==x-l+1) puts("Yes");
		else puts("No");
	}
	return 0;
}

　　

　　

Vladik and Memorable Trip

题目大意：给你一个序列，要求你用满足以下条件的子序列去覆盖它：

1、子序列不能相交

2、所有相同的数必须在同一个子序列中，或者不选他们

3、所有子序列的异或之和最大（一个子序列中，相同的数只异或一次）

求最大的子序列的和

分析：先预处理出每个数的开头位置和结束位置，然后dp解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 5010
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
using namespace std;
int n,a[MAXN],L[MAXN],R[MAXN],vis[MAXN],f[MAXN];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
int main(){
	//freopen(FILE".in","r",stdin);
	//freopen(FILE".out","w",stdout);
	n=read();
	for(int i=1;i<=n;++i) a[i]=read();
	for(int i=1;i<=n;++i){
		if(!L[a[i]])  L[a[i]]=i;
		cmax(R[a[i]],i);
	}
	for(int i=1;i<=n;++i){
		f[i]=f[i-1];  int temp=0;
		int l=i,r=i;  memset(vis,0,sizeof(vis));
		for(int j=i;j;--j){
			cmin(l,L[a[j]]);
			cmax(r,R[a[j]]);
			if(!vis[a[j]])  temp^=a[j],vis[a[j]]=1;
			if(l>=j&&r<=i) cmax(f[i],f[j-1]+temp);
		}
	}
	printf("%d\n",f[n]);
	return 0;
}

　　

　　

Vladik and Favorite Game

题目大意：给你一张地图，你需要找到一条从(1,1)到终点的路径并输出

分析：此题为交互题，按钮的功能可能改变，你需要去试出按钮的功能，然后决定路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
#define FILE "read"
using namespace std;
typedef pair<int,int> pii;
const int dx[5]={0,1,0,-1};
const int dy[5]={1,0,-1,0};
char D[5]={'R','D','L','U'};
int n,m,dis[105][105];
char ch[105][105];
queue<pii>q;
void bfs(){
	while(!q.empty()){
		int x=q.front().first,y=q.front().second; q.pop();
		for(int k=0;k<4;++k){
			int xx=x+dx[k],yy=y+dy[k];
			if(xx<=0||yy<=0||xx>n||yy>m||ch[xx][yy]=='*'||dis[xx][yy]) continue;
			dis[xx][yy]=dis[x][y]+1;  q.push(make_pair(xx,yy));
		}
	}
}
void dfs(int x,int y){
	int temp;
	if(ch[x][y]=='F') exit(0);
	for(int k=0;k<4;++k){
		int xx=x+dx[k],yy=y+dy[k];
		if(dis[xx][yy]+1==dis[x][y]) {temp=k; break;}
	}
	printf("%c\n",D[temp]);
	fflush(stdout);
	int a,b;  scanf("%d%d",&a,&b);
	if(a==x+dx[temp]&&b==y+dy[temp]) dfs(a,b);
	else{
		if(temp==0||temp==2) swap(D[0],D[2]);
		if(temp==1||temp==3) swap(D[1],D[3]);
		dfs(a,b);
	}
}
int main(){
	//freopen(FILE".in","r",stdin);
	//freopen(FILE".out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%s",ch[i]+1);
	for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)if(ch[i][j]=='F'){
		q.push(make_pair(i,j)); dis[i][j]=1; bfs();
	}
	dfs(1,1);
	return 0;
}

　　

　　

Vladik and Entertaining Flags

题目大意：看样例解释就能看懂

分析：直接上线段树就行了，但是不太好写的样子

注意区间合并时用并查集维护连通性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 100100
using namespace std;
int n,m,Q,cnt,f[MAXN*20],A[15][MAXN];
struct node{
	int sum,L,R,l[15],r[15];
	node(){sum=0;}
}tr[MAXN<<2];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
inline node operator +(node a,node b){
	if(!a.sum) return b;
	if(!b.sum) return a;
	node c;  c.sum=a.sum+b.sum;  
	c.L=a.L;  c.R=b.R;
	for(int i=1;i<=n;++i){
		f[a.l[i]]=a.l[i];
		f[a.r[i]]=a.r[i];
		f[b.l[i]]=b.l[i];
		f[b.r[i]]=b.r[i];
	}
	for(int i=1;i<=n;++i)if(A[i][a.R]==A[i][b.L]){
		int p=find(a.r[i]),q=find(b.l[i]);
		if(p==q) continue;
		c.sum--;  f[p]=q;
	}
	for(int i=1;i<=n;++i){
		c.l[i]=find(a.l[i]);
		c.r[i]=find(b.r[i]);
	}
	return c;
}
void build(int p,int l,int r){
	if(l==r){
		for(int i=1;i<=n;++i){
			if(A[i][l]==A[i-1][l]) tr[p].l[i]=tr[p].r[i]=tr[p].l[i-1];
			else tr[p].l[i]=tr[p].r[i]=++cnt,tr[p].sum++;
		}
		tr[p].L=l;  tr[p].R=r;
		return;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid); build(p<<1|1,mid+1,r);
	tr[p]=tr[p<<1]+tr[p<<1|1];
}
node query(int p,int l,int r,int x,int y){
	if(x<=l&&y>=r)  return tr[p];
	int mid=(l+r)>>1;  node ret;
	if(x<=mid) ret=ret+query(p<<1,l,mid,x,y);
	if(y>mid)  ret=ret+query(p<<1|1,mid+1,r,x,y);
	return ret;
}
int main(){
	//freopen(FILE".in","r",stdin);
	//freopen(FILE".out","w",stdout);
	n=read(); m=read(); Q=read();
	for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)A[i][j]=read();
	build(1,1,m);
	for(int i=1;i<=Q;++i){
		int l=read(),r=read();
		printf("%d\n",query(1,1,m,l,r).sum);
	}
	return 0;
}

本文标题:【Codeforces】Rand#416解题报告

文章作者:chty

发布时间:2017年05月28日 - 11时37分

最后更新:2017年05月28日 - 21时09分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
  1. 1. Vladik and Courtesy
  2. 2. Vladik and Complicated Book
  3. 3. Vladik and Memorable Trip
  4. 4. Vladik and Favorite Game
  5. 5. Vladik and Entertaining Flags
,