cf round 424

自用笔记算法

cf round 424

A

题目要求

问一组序列是否满足前半部分严格递增 中间连续 末尾严格递减

参考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
#include<bits/stdc++.h>
#define maxn 150
#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)
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 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);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int flag1=1,flag2=1;
	for(int i=2;i<=n;i++){
		if(flag1==1){
			if(a[i]==a[i-1]){
				flag1=2;
				continue;
			}
			if(a[i]<a[i-1]){
				flag1=3;
				continue;
			}
		}
		if(flag1==2){
			if(a[i]<a[i-1]){
				flag1=3;
				continue;
			}
			if(a[i]>a[i-1]){
				flag2=0;
				break;
			}
		}
		if(flag1==3){
			if(a[i]==a[i-1] || a[i]>a[i-1]){
				flag2=0;
				break;
			}
		}
	}
	if(flag2) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	return 0;
}

思路

模拟
题面较坑 注意可以跳过连续的部分直接进入下降部分

B

题目要求

给出两组26个字母的排列顺序
给出一组字符串由大小写字母和数字组成 是对应第一组字母排序输入 要求输出对应按照第二组字母的次序

参考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
#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)
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 s1,s2,s3;
	cin>>s1>>s2>>s3;
	mm(hashh,0);
	for(int i=0;i<s1.length();i++) hashh[s1[i]-'a'+1]=i+1;
//	for(int i=1;i<=26;i++) cout<<hashh[i]<<endl;
	for(int i=0;i<s3.length();i++){
		if(s3[i]>='0' && s3[i]<='9') cout<<s3[i];
		if(s3[i]>='A' && s3[i]<='Z'){
			char ch=(char)(s3[i]-'0'+32+'0');
			int pos=hashh[ch-'a'+1];
			cout<<char(s2[pos-1]-'0'-32+'0');
		}
		if(s3[i]>='a' && s3[i]<='z'){
			int pos=hashh[s3[i]-'a'+1];
			cout<<s2[pos-1];
		}
	}  
	return 0;
}

思路

模拟 hash位置

C

题目要求

主角看电视，电视里有k个评委给参赛者打分，每个评委打了ai分，即参赛者的初始分加上这些评委打分，等于一个结果
但是主角不是很记得所有结果，只记得n个结果，即bj（加上若干个ai的结果），现问你他的初始分有多少种可能（注意a按时间顺序给出，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
#include<bits/stdc++.h>
#define maxn 2050
#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)
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 a[maxn],b[maxn];
LL sum[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(sum,0);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	for(int i=1;i<=k;i++) cin>>b[i];
	sort(sum+1,sum+1+n);
	int len=unique(sum+1,sum+1+n)-(sum+1);
	int ans=len;
	for(int i=1;i<=len;i++){
		int st=b[1]-sum[i];
		for(int j=1;j<=k;j++){
			if(!binary_search(sum+1,sum+1+n,b[j]-st)){
				ans--;
				break;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

思路

前缀和去重排序用于二分搜索
最大长度等于去重后的前缀和长度
遍历前缀和与b[1]相减用于找到起始位置st
从该位置开始每个bi都可以用st+sum找到 查找方式为二分 若找不到 ans减1 继续下一种情况

D

题目要求

一条直线上给出n个人和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
40
41
42
43
44
#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)
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<LL>people,key;
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,p;
	cin>>n>>k>>p;
	for(int i=1;i<=n;i++){
		LL x;
		cin>>x;
		people.pb(x);
	}
	for(int i=1;i<=k;i++){
		LL x;
		cin>>x;
		key.pb(x);
	}
	sort(people.begin(),people.end());
	sort(key.begin(),key.end());
	LL ans=INF;
	for(int i=0;i<=k-n;i++){
		LL c=-1;
		for(int j=0;j<n;j++) c=max(c,abs(people[j]-key[i+j])+abs(key[i+j]-p));
		ans=min(ans,c);
	}
	cout<<ans<<endl;
	return 0;
}

思路

人和钥匙坐标排序
外层i遍历人拿钥匙的间隔 对于每种间隔遍历所有人拿钥匙去警察局的情况 找到最大值 同时更新最小值
1 2 3
1 2 3 4 5
如下图可以为:
1->1 2->2 3->3
1->2 2->3 3->4
1->3 2->4 3->5
三种情况 间隔分别为0 1 2

E

题目要求

n张卡片 每张卡片上有一个数字 可以重复
每次拿走最上面的一张 如果这张的数字是剩下卡片的最小值 删去 否则放到卡片的最下面
问一共要重复多少步骤才能全部拿走

参考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
#include<bits/stdc++.h>
#define maxn 100050
#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;}
LL n;
LL a[maxn],tree[maxn];
vector<int>s[maxn];
void change(int x,LL val){
    while(x<=n) {
        tree[x]+=val;
        x+=x&(-x);
    }
}
LL sum(int x){
    LL res=0;
    while (x){
        res+=tree[x];
        x-=x&(-x);
    }
    return res;
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	mm(tree,0);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[a[i]].pb(i);
		change(i,1LL);
	}
	sort(a+1,a+1+n);
	LL ans=0;
	int pre=0;
	vector<int>::iterator cur;
	for(int i=1;i<=n;i++){
		cur=upper_bound(s[a[i]].begin(),s[a[i]].end(),pre);
		if(cur==s[a[i]].end()) cur=s[a[i]].begin();
		if(*cur>=pre) ans+=sum(*cur)-sum(pre);
		else ans+=sum(n)-sum(pre)+sum(*cur);
		change(*cur,-1LL);
		pre=*cur;
	}
	cout<<ans<<endl;
	return 0;
}

思路

树状数组维护区间内是否还存在该点 存在为1 不存在为0 每一轮累加的结果就是该轮的操作次数
vector存放每个卡片上数字出现的位置
a排序后从最小的数字开始
cur有2种情况：若该数字有多个位置 upper_bound可以确保下一轮从上一轮的末尾出发 若已经进入下一个数字 cur置为首地址
同时更新pre代表上一轮拿走卡片的位置 拿走的位置树状数组置0
更新ans注意如果cur比pre大 直接累加中间部分 否则循环累加pre-n以及0-cur的部分

本文标题:cf round 424

文章作者:Hippopmonkey

发布时间:2017-07-14, 14:11:39

最后更新:2017-07-15, 12:47:37

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

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

文章目录
  1. 1. cf round 424
    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. 思路
    5. 1.5. E
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
|