Reku
0%

Codeforces Round #416 (Div. 2)

Posted on Edited on In Views: Valine:

A. Vladik and Courtesy 二分查找一下次数就行 

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
#include<bits/stdc++.h>
using namespace std;
long long a,b;
long long ff1(long long x)
{
	long long l=0;
	long long r=27483600;
	while(l<r)
	{
		long long mid=(l+r)/2+1;
		if(mid*mid>x) r=mid-1;
		else l=mid;
	}
	return l;
}
long long ff2(long long x)
{
	long long l=0;
	long long r=27483600;
	while(l<r)
	{
		long long mid=(l+r)/2+1;
		if((mid+1)*mid>x) r=mid-1;
		else l=mid;
	}
	return l;
}
int main() 
{
	cin>>a>>b;
	long long k1=ff1(a);
	long long k2=ff2(b);
	if(k1>k2)
	{
		cout<<"Valera"<<endl;
	}
	else cout<<"Vladik"<<endl;
	return 0;
}

B. Vladik and Complicated Book 暴力\(N^2\)计数就行，很傻

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int p[10010];
int n,m;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&p[i]);
	for(int i=1;i<=m;i++)
	{
		int l,r,x;
		scanf("%d%d%d",&l,&r,&x);
		int num=0;
		for(int j=l;j<=r;j++) if(p[j]<=p[x]) num++;
		if(num==(x-l+1)) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

C. Vladik and Memorable Trip 计算出要覆盖每个值的最小块的大小，然后标记一下。以为是最小块，所以两个块要么互相独立，要么包含，这样直接树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
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
71
72
73
74
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
using namespace std;
int n;
int a[5010];
int ma[5010];
int mi[5010];
int pp[5010];
vector<int> e[5010];
bool b[5010];
int t[5010];
int ff(int x)
{
	int ans=t[x];
	int ans1=0;
	for(auto &i:e[x])
	{
		ans1+=ff(i);
	}
	ans=max(ans,ans1);
	return ans;
}
int main()
{
	memset(pp,-1,sizeof(pp));
	cin>>n;
	for(int i=1;i<=5000;i++) mi[i]=2147483600,ma[i]=-1;
	for(int i=1;i<=n;i++) cin>>a[i],mi[a[i]]=min(i,mi[a[i]]),ma[a[i]]=max(ma[a[i]],i);
	for(int i=1;i<=5000;i++)
	{
		memset(b,0,sizeof(b));
		if(ma[i]==-1) continue;
		int zz=mi[i];
		int yy=ma[i];
		for(int j=mi[i];j<=ma[i];j++)
		{
			zz=min(zz,mi[a[j]]);
			yy=max(yy,ma[a[j]]);
		}
		int l=mi[i];
		int r=ma[i];
		while(l!=zz||r!=yy)
		{
			if(l!=zz)
			{
				l--;
				zz=min(zz,mi[a[l]]);
				yy=max(yy,ma[a[l]]);
			}
			if(r!=yy)
			{
				r++;
				zz=min(zz,mi[a[r]]);
				yy=max(yy,ma[a[r]]);
			}
		}
		pp[yy]=-1;
		pp[zz]=yy-zz;
		int ans=0;
		for(int j=l;j<=r;j++)
		{
			if(b[a[j]]==0)
			{
				b[a[j]]=1;
				ans^=a[j];
			}
		}
		t[l]=ans;
	}
	for(int i=1;i<=n;i++)
	{
		//cout<<i<<" "<<pp[i]<<endl;
		if(pp[i]==-1) continue;
		int l=i-1;
		while(l!=0&&pp[l]+l<pp[i]+i)
		{
			l--;
		}
		e[l].push_back(i);
	}
	cout<<ff(0)<<endl;
	return 0;
}

D. Vladik and Favorite Game 这是一道交互题。 交互题其实就是你输出一些东西，然后cf的程序会输入回一些东西，然后你通过这些，来搞一下你的下一步策略。 这个题其实很傻，就是先广搜出一条合理的路径，然后因为一定是先沿边走，所以瞎判断一下就行了。

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<bits/stdc++.h>
using namespace std;
int n,m;
char c[110][110];
bool v[110][110];
int d[110][110];
pair<int,int> la[110][110];
int xx[4]={1,-1,0,0};
int yy[4]={0,0,1,-1};
vector<char> ans;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>c[i][j];
			d[i][j]=2*n*m;
		}
	}
	queue<pair<int,int> > q;
	q.push(make_pair(1,1));
	v[1][1]=1;
	d[1][1]=0;
	while(!q.empty())
	{
		int a=q.front().first;
		int b=q.front().second;
		q.pop();
		v[a][b]=0;
		for(int i=0;i<4;i++)
		{
			int x=a+xx[i];
			int y=b+yy[i];
			if(x<=0||x>n) continue;
			if(y<=0||y>m) continue;
			if(c[x][y]=='*') continue;
			if(d[a][b]+1<d[x][y])
			{
				d[x][y]=d[a][b]+1;
				la[x][y]=make_pair(a,b);
				if(v[x][y]==0)
				{
					v[x][y]=1;
					q.push(make_pair(x,y));
				}
			}
		}
	}
	int a,b;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(c[i][j]=='F')
			{
				a=i;
				b=j;
			}
	while(a!=1||b!=1)
	{
		int x,y;
		x=la[a][b].first;
		y=la[a][b].second;
		if(x<a) ans.push_back('D');
		if(x>a) ans.push_back('U');
		if(y<b) ans.push_back('R');
		if(y>b) ans.push_back('L');
		a=x;
		b=y;
	}
	int bj1=-1;
	int bj2=-1;
	a=1; b=1;
	for(int i=ans.size()-1;i>=0;i--)
	{
		if(bj1==-1&&c[a+1][b]!='*')
		{
			int pa=a;
			cout<<'D'<<endl;
			fflush(stdout);
			cin>>a>>b;
			if(a!=pa)
			{
				bj1=0;
				cout<<'U'<<endl;
				fflush(stdout);
				cin>>a>>b;
			}
			else bj1=1;
		}
		if(bj2==-1&&c[a][b+1]!='*')
		{
			int pb=b;;
			cout<<'R'<<endl;
			fflush(stdout);
			cin>>a>>b;
			if(b!=pb)
			{
				bj2=0;
				cout<<'L'<<endl;
				fflush(stdout);
				cin>>a>>b;
			}
			else bj2=1;
		}
		if(ans[i]=='U'&&bj1==1) ans[i]='D';
		else if(ans[i]=='D'&&bj1==1) ans[i]='U';
		else if(ans[i]=='L'&&bj2==1) ans[i]='R';
		else if(ans[i]=='R'&&bj2==1) ans[i]='L';
		cout<<ans[i]<<endl;
		fflush(stdout);
		cin>>a>>b;
	}
	return 0;
}

E. Vladik and Entertaining Flags 不错的一道题。 用线段树维护一下左边界和右边界总共2*n个点的并查集，然后做一下并查集的合并。 说起来蛮简单的，但是合并的细节有点多，写起来也有点烦。（可能我的写法比较糟糕）

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
int c[15][100010];
struct seg
{
	int u[22];
	int l,r;
	int num;
};
seg e[400040];
int init(int (&f)[22])
{
	for(int i=1;i<=2*n;i++) f[i]=i;
}
int ff(int (&f)[22],int x)
{
	if(x==f[x]) return x;
	f[x]=ff(f,f[x]);
	return f[x];
}
void merge(int (&f)[22],int x,int y)
{
	f[ff(f,x)]=ff(f,y);
}
int t[42];
int w[44];
int p[22];
int ff1(int x)
{
	if(t[x]==x) return x;
	t[x]=ff1(t[x]);
	return t[x];
}
void mergedsu(seg &a,seg &b,seg &e)
{
	init(a.u);
	for(int i=1;i<=4*n;i++) t[i]=i;
	a.num=b.num+e.num;
	for(int i=1;i<=n;i++)
	{
		if(c[i][b.r]==c[i][e.l]&&(ff1(ff(b.u,i+n))!=ff1(ff(e.u,i)+2*n)))
		{
			t[ff1(ff(b.u,i+n))]=ff1(ff(e.u,i)+2*n);
			a.num--;
		}
	}
	a.l=b.l; a.r=e.r;
	memset(p,-1,sizeof(p));
	for(int i=1;i<=n;i++)
	{
		int tt=ff(b.u,i);
		if(p[tt]==-1) p[tt]=i;
		else merge(a.u,p[tt],i);
	}
	memset(p,-1,sizeof(p));
	for(int i=1;i<=n;i++)
	{
		int tt=ff(e.u,i+n);
		if(p[tt]==-1) p[tt]=i+n;
		else merge(a.u,p[tt],i+n);
	}
	memset(w,-1,sizeof(w));
	for(int i=1;i<=n;i++)
	{
		int tt=ff1(ff(e.u,i+n)+2*n);
		w[tt]=i+n;
	}
	for(int i=1;i<=n;i++)
	{
		int tt=ff1(ff(b.u,i));
		if(w[tt]!=-1) merge(a.u,i,w[tt]);
	}
	memset(w,-1,sizeof(w));
	for(int i=1;i<=n;i++)
	{
		int tt=ff1(ff(b.u,i));
		w[tt]=i;
	}
	for(int i=1;i<=n;i++)
	{
		int tt=ff1(ff(e.u,i+n)+2*n);
		if(w[tt]!=-1) merge(a.u,i+n,w[tt]);
	}
	memset(w,-1,sizeof(w));
	for(int i=1;i<=n;i++)
	{
		int tt=ff1(ff(b.u,i));
		w[tt]=i;
	}
	for(int i=1;i<=n;i++)
	{
		int tt=ff1(ff(b.u,i));
		if(w[tt]!=-1) merge(a.u,i,w[tt]);
	}
	memset(w,-1,sizeof(w));
	for(int i=1;i<=n;i++)
	{
		int tt=ff1(ff(e.u,i+n)+2*n);
		w[tt]=i+n;
	}
	for(int i=1;i<=n;i++)
	{
		int tt=ff1(ff(e.u,i+n)+2*n);
		if(w[tt]!=-1) merge(a.u,i+n,w[tt]);
	}
}
void build(int x,int l,int r)
{
	if(l==r)
	{
		init(e[x].u);
		e[x].l=l; e[x].r=r;
		e[x].num=0;
		for(int i=1;i<=n;i++)
		{
			if(c[i][l]==c[i-1][l]) merge(e[x].u,i,i-1);
			else e[x].num++;
			merge(e[x].u,i,i+n);
		}
		return;
	}
	int mid=(l+r)/2;
	build(x*2,l,mid);
	build(x*2+1,mid+1,r);
	mergedsu(e[x],e[x*2],e[x*2+1]);
	return;
}
seg ans;
void query(int x,int l,int r,int z,int y)
{
	if(z<=l&&y>=r)
	{
		if(z==l) ans=e[x];
		else
		{
			seg u;
			mergedsu(u,ans,e[x]);
			ans=u;
		}
		return;
	}
	int mid=(l+r)/2;
	if(z<=mid) query(x*2,l,mid,z,y);
	if(y>mid) query(x*2+1,mid+1,r,z,y);
}
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&c[i][j]);
		}
	}
	build(1,1,m);
	int l,r;
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&l,&r);
		query(1,1,m,l,r);
		printf("%d\n",ans.num);
	}
	return 0;
}