cf round 423

自用笔记算法

cf round 423

A

题目要求

一家餐厅有n张一人桌 有m张双人桌
每次来一个人或者两个人
一个人首先选择坐在单人桌 若没有优先考虑都空的双人桌 最后考虑已有一个人的双人桌 都没有的话拒绝这个人
两个人考虑是否有都空的双人桌 若没有拒绝这2个人
输出一共拒绝了多少个人

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 200050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int t[maxn];
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n,a,b;
	cin>>n>>a>>b;
	int aa=0;
	for(int i=1;i<=n;i++) cin>>t[i];
	int ans=0;
	for(int i=1;i<=n;i++){
		if(t[i]==1){
			if(a>0) a--;
			else if(b>0) b-=1,aa+=1;
			else if(aa>0) aa--;
			else ans++;
		}
		else{
			if(b>0) b--;
			else ans+=2;
		}
	}
	cout<<ans<<endl;
	return 0;
}

思路

模拟 aa表示有一个人的双人桌

B

题目要求

有一个矩形被W和B填空 问最少需要把多少个W换成B 可以满足所有的B构成一个矩形

参考AC代码

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>
#define maxn 105
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
char g[maxn][maxn];
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n,m;
	cin>>n>>m;
	int cnt=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>g[i][j];
			if(g[i][j]=='B') cnt++;
		}
	}
	int top=0,bo=0,l=0,r=0;
	for(int i=1;i<=n;i++){
		int flag=0;
		for(int j=1;j<=m;j++){
			if(g[i][j]=='B'){
				top=i,flag=1;
				break;
			}
		}
		if(flag) break;
	}
	for(int i=n;i>=1;i--){
		int flag=0;
		for(int j=1;j<=m;j++){
			if(g[i][j]=='B'){
				bo=i,flag=1;
				break;
			}
		}
		if(flag) break;
	}
	for(int j=1;j<=m;j++){
		int flag=0;
		for(int i=1;i<=n;i++){
			if(g[i][j]=='B'){
				l=j,flag=1;
				break;
			}
		}
		if(flag) break;
	}
	for(int j=m;j>=1;j--){
		int flag=0;
		for(int i=1;i<=n;i++){
			if(g[i][j]=='B'){
				r=j,flag=1;
				break;
			}
		}
		if(flag) break;
	}
//	cout<<top<<" "<<bo<<" "<<l<<" "<<r<<endl;
	int len=max(abs(top-bo)+1,abs(l-r)+1);
	if(len>min(n,m)){
		cout<<"-1"<<endl;
		return 0;
	}
	cout<<len*len-cnt<<endl;
	return 0;
}

思路

模拟
算出B的最上方 最下方 最左方 最右方 以及B的总数cnt
利用这4个数值算出矩形的面积 减去cnt即可
注意如果矩形的边长大于n和m的最小值 则无法满足矩形输出-1

C

题目要求

给出若干个字符串s 以及该字符串在总最终字符串出现的次数以及位置
用子串去填空最终字符串
输出满足条件字典序最小的最终字符串

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 2000000
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int vis[maxn<<2];
char ans[maxn];
string s;
void update(int l,int r,int rt,int L,int R){
	if(vis[rt]==(r-l+1)) return;
	if(l==r){
		vis[rt]=1;
		ans[l]=s[l-L];
		return;
	}
	int m=(l+r)>>1;
	if(m<L) update(rson,L,R);
	else if(m>=R) update(lson,L,R);
	else{
		update(lson,L,R);
		update(rson,L,R);
	}
	vis[rt]=vis[rt<<1]+vis[rt<<1|1];
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n;
	cin>>n;
	int Max=-1;
	mm(vis,0);
	for(int i=1;i<maxn;i++) ans[i]='A';
	for(int i=1;i<=n;i++){
		cin>>s;
		int len=s.length();
		int t;
		cin>>t;
		while(t--){
			int x;
			cin>>x;
			Max=max(Max,x+len-1);
			update(1,2000000,1,x,x+len-1);
		}
	}
	for(int i=1;i<=Max;i++){
		if(ans[i]=='A') cout<<"a";
		else cout<<ans[i];
	}
	cout<<endl;
	return 0;
}

思路

线段树单点更新
vis用来判断该区间是否全被修改过 若已修改则跳过该区间
ans里未更新的输出a满足字典序最小

D

题目要求

n个点 用最少的边连接 确保有k个度为1 其余n-k个点度大于1 要求最远点的距离最小
输出距离以及每条边的端点 多解输出一组即可

参考AC代码

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 maxn 200050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
vector<pii>ans;
int deep[maxn],num[maxn],out[maxn];
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n,k;
	cin>>n>>k;
	mm(deep,0),mm(num,0),mm(out,0);
	int center=n-k-1;
	for(int i=0;i<k;i++) num[i]=center;
	for(int i=0;i<center;i++){
		int pos=i%k;
		ans.pb(mp(num[pos],i));
		num[pos]=i;
		deep[pos]++;
	}
	for(int i=center+1;i<n;i++){
		int pos=(i-1)%k;
		ans.pb(mp(num[pos],i));
		num[pos]=i;
		deep[pos]++;
		out[pos]=deep[pos];
	}
	sort(out,out+k,greater<int>());
	cout<<out[0]+out[1]<<endl;
	int len=ans.size();
	for(int i=0;i<len;i++) cout<<ans[i].fi+1<<" "<<ans[i].se+1<<endl;
	return 0;
}

思路

入度为1的点越多可以确保最远点的距离越小
ans存放边的情况 num记录每条路径最远点的数值 deep记录每条路径的深度 out记录每条路径最终的深度
先连接n-k个入度大于1的点 找到中心点n-k-1(-1是因为滚动数组点要从0开始 输出的时候+1)
利用滚动数组把0->center-1与center相连接 num和deep更新维护
之后把k个入度为1的点%k算出是哪条路径加上 更新num和deep 同时维护out
out由大到小排序后out[0]+out[1]即为所求
ans输出边

本文标题:cf round 423

文章作者:Hippopmonkey

发布时间:2017-07-15, 17:35:03

最后更新:2017-07-16, 00:32:29

原始链接:http://xuboming8.github.io/2017/07/15/cf-round-423/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. cf round 423
    1. 1.1. A
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. B
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. C
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. D
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
|