cf edu25

自用笔记算法

cf edu25

A

题目要求

转换
num是几输出几个1 每个数字之间以0间隔

参考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
#include<bits/stdc++.h>
#define maxn 100000
#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 double eps = 1e-6;
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 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;
	string s;
	cin>>s;
	int cnt=0;
	for(int i=0;i<n;i++){
		if(s[i]=='0'){
			cout<<cnt;
			cnt=0;
		}
		if(s[i]=='1') cnt++;
	}
	cout<<cnt<<endl;
	return 0;
}

思路

模拟

B

题目要求

X代表己方 O代表对方 .代表该位置可以下
模拟五子棋 问走一步后己方是否能取得胜利

参考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
#include<bits/stdc++.h>
#define maxn 100000
#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 double eps = 1e-6;
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[15][15];
bool check(){
	for(int i=1;i<=10;i++){
		for(int j=1;j<=6;j++){
			int flag=0;
			for(int k=0;k<=4;k++){
				if(g[i][j+k]!='X') flag=1;
			}
			if(!flag) return true;
		}
	}
	for(int i=1;i<=10;i++){
		for(int j=1;j<=6;j++){
			int flag=0;
			for(int k=0;k<=4;k++){
				if(g[j+k][i]!='X') flag=1;
			}
			if(!flag) return true;
		}
	}
	for(int i=1;i<=6;i++){
		for(int j=1;j<=6;j++){
			int flag=0;
			for(int k=0;k<=4;k++){
				if(g[i+k][j+k]!='X') flag=1; 
			}
			if(!flag) return true;
		}
	}
	for(int i=1;i<=6;i++){
		for(int j=10;j>=4;j--){
			int flag=0;
			for(int k=0;k<=4;k++){
				if(g[i+k][j-k]!='X') flag=1;
			}
			if(!flag) return true;
		}
	}
	return false;
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	for(int i=1;i<=10;i++){
		for(int j=1;j<=10;j++) cin>>g[i][j];
	}
	for(int i=1;i<=10;i++){
		for(int j=1;j<=10;j++){
			if(g[i][j]=='.'){
				g[i][j]='X';
				if(check()){
					cout<<"YES"<<endl;
					return 0;
				}
				g[i][j]='.';
			}
		}
	}
	cout<<"NO"<<endl;
	return 0;
}

思路

把所有.的位置模拟成X后判断是否满足五子棋的规则
check判断规则的时候 遍历起点和长度为小于等于4的窗
四种情况均考虑到即可

C

题目要求

有n个难度值为ai的题目 k代表起始难度
每次能解决题目的难度必须小于2k
如果不能解决需要去别的oj找题目更新k
问最少需要找多少题目

参考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
#include<bits/stdc++.h>
#define maxn 1050
#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 double eps = 1e-6;
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;}
LL a[maxn];
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	LL n,k;
	cin>>n>>k;
	for(LL i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+1+n);
	LL ans=0,limit=2*k;
	for(LL i=1;i<=n;i++){
		while(limit<a[i]){
			ans++;
			limit*=2;
		}
		limit=max(limit,2*a[i]);
	}
	cout<<ans<<endl;
	return 0;
}

思路

limit为当前可以解决的题目的最大难度
如果小于a[i] 根据最优策略 必须找到难度为limit的题目最大程度扩大limit
同时做出题目后同时更新limit上限

D

题目要求

字符串s里可能存在一些?可以用任意字符替代
同时定义舒适度为:交换s里任意2个位置 该操作可以不相交的重复多次 有子串t的最大个数
输出填充好的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
#include<bits/stdc++.h>
#define maxn 100000
#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 double eps = 1e-6;
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 hashh[30];
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	string s,t;
	cin>>s>>t;
	queue<int>q;
	int num=0;
	mm(hashh,0);
	for(int i=0;i<s.length();i++){
		if(s[i]=='?'){
			q.push(i);
			num++;
		}
		else hashh[s[i]-'a']++;
	}
	while(t.length()<s.length()) t+=t;
	for(int i=0;i<t.length();i++){
		int id=t[i]-'a';
		if(!num && !hashh[id]) break;
		else if(hashh[id]) hashh[id]--;
		else{
			num--;
			s[q.front()]=t[i];
			q.pop();
		}
	}
	cout<<s<<endl;
	return 0;
}

思路

queue存放?的位置 num记录?的个数 同时hash每个字母出现的次数
扩充t满足长度大于s 遍历t
如果没有?并且s里不存在这个字母 break掉
否则把queue里第一个位置存放该字母 出队列 num–

本文标题:cf edu25

文章作者:Hippopmonkey

发布时间:2017-07-17, 18:48:37

最后更新:2017-07-17, 19:08:06

原始链接:http://xuboming8.github.io/2017/07/17/cf-edu25/

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

文章目录
  1. 1. cf edu25
    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. 思路
|