atcoder regular080

自用笔记算法

atcoder regular080

C

题目要求

有一个长度n的数组 问是否改变顺序后可以满足 任意两个相邻的元素乘积都是4的倍数

参考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
#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 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;
	int cnt1=0,cnt2=0;
	for(int i=1;i<=n;i++){
		int x; cin>>x;
		if(x%4==0) cnt1++;
		else if(x%2==0) cnt2++;
	}
	int pos=2*cnt1+1+(cnt2/2)*2;
	if(pos>=n) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

思路

记录是4的倍数的个数和剩下的数中是2倍数的个数
一个4可以解决掉他自己和左边右边各一个的位置 由于2个4会重叠一个位置 多个同理 所以cnt1和k可以解决掉2*cnt1+1个位置
一对2可以解决掉2个位置 总的位置加在一起大于等于n 满足 否则不满足

D

题目要求

一个H×W的迷宫 要求要涂n种颜色 每种颜色的所有格子必须相邻 且每种颜色要涂ai个格子 输出满足条件的任意一组解

参考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
#include<bits/stdc++.h>
#define maxn 10050
#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 a[maxn];
int g[105][105];
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int h,w;
	cin>>h>>w;
	int n; cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int pos=1;
	mm(g,0);
	for(int i=1;i<=h;i++){
		if(i&1){
			for(int j=1;j<=w;j++){
				if(a[pos]>0) g[i][j]=pos,a[pos]--;
				else pos++,g[i][j]=pos,a[pos]--;
			}
		}
		else{
			for(int j=w;j>=1;j--){
				if(a[pos]>0) g[i][j]=pos,a[pos]--;
				else pos++,g[i][j]=pos,a[pos]--;
			}
		}
	}
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			if(j==1) cout<<g[i][j];
			else cout<<" "<<g[i][j];
		}
		cout<<endl;
	}
	return 0;
}

思路

模拟
蛇形输出即可

E

题目要求

有n个元素的数组p p是一个1-n的全排列 另有一个空数组q
每次在p中挑取2个相邻的元素放到q的开头 最后要求q的序列字典序最小 输出序列

参考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
#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 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;}
struct node{
	int m,l,r;
	node(int m,int l,int r):m(m),l(l),r(r){}
	bool operator < (const node& x) const{
		return m>x.m;
	}
};
int dp[2][maxn][36]; 
int pos[maxn];
int a[2][maxn];
void makermq(int n,int f){  
    for(int i=0;i<n;i++) dp[f][i][0]=a[f][i];  
    for(int j=1;(1<<j)<=n;j++)  
        for(int i=0;i+(1<<j)-1<n;i++)  
            dp[f][i][j]=min(dp[f][i][j-1],dp[f][i+(1<<(j-1))][j-1]);  
}  
int rmq(int s,int v,int f){
    int k=(int)(log((v-s+1)*1.0)/log(2.0));  
    return min(dp[f][s][k],dp[f][v-(1<<k)+1][k]);  
}  
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;
	mm(pos,0);
	for(int i=0;i<n;i++){
		int x; cin>>x;
		pos[x]=i;
		a[i&1][i]=x;
		a[(i&1)^1][i]=inf;
	}
	makermq(n,0),makermq(n,1);
	int x1=rmq(0,n-1,0);
	priority_queue<node>q;
	q.push(node(x1,0,n-1));
	while(!q.empty()){
		node x=q.top(); q.pop();
		int v1=x.m;
		int v2=rmq(pos[v1]+1,x.r,(pos[v1]&1)^1);
		cout<<v1<<" "<<v2<<" ";
		int pos1=pos[v1],pos2=pos[v2];
		if(pos1!=x.l) q.push(node(rmq(x.l,pos1-1,x.l&1),x.l,pos1-1));
		if(pos1+1!=pos2) q.push(node(rmq(pos1+1,pos2-1,(pos1+1)&1),pos1+1,pos2-1));
		if(pos2!=x.r) q.push(node(rmq(pos2+1,x.r,(pos2+1)&1),pos2+1,x.r));
	}
	cout<<endl;
	return 0;
}

思路

把q数组的下标由1->n换成0->n-1
我们逆序 从q0开始取 思考后可以发现q0必须在p数组中下标为偶数的位置中 并且由于是字典序最小 所以选择偶数下标的最小值 记录位置为i
q1必须在大于i的位置中挑选是奇数下标位置中的最小值 记录位置j 可以i和j会把区间分成三个部分0->i-1 i->j j+1->n-1 在三个区间维护
偶数下标和奇数下标的最小值 每个区间放到优先队列中维护每个区间的偶数下标最小值 q2和q3以及后续的操作同上
每个区间奇数下标和偶数下标的最小值可以用RMQ解决 本代码中采用的是多开一维记录奇偶位置的st算法
而每个区间的偶数下标的最小值用优先队列维护 确定它后 在比它大的位置中找到奇数下标的最大值 这一循环就完成了

本文标题:atcoder regular080

文章作者:Hippopmonkey

发布时间:2017-08-07, 21:35:53

最后更新:2017-08-07, 22:06:37

原始链接:http://xuboming8.github.io/2017/08/07/atcoder-regular080/

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

文章目录
  1. 1. atcoder regular080
    1. 1.1. C
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. D
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. E
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
|