cf&at 杂选

自用笔记算法

cf&at 杂选

atcoder_contest74_D

题目要求

有3N个数字 删除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
#include<bits/stdc++.h>
#define LL long long
#define inf 1e18 
#define maxn 100050
using namespace std;
priority_queue<int,vector<int>,greater<int> >q1;
priority_queue<int,vector<int>,less<int> >q2;
int a[maxn*3];
LL suml[maxn*3],sumr[maxn*3];
int main(){
//	freopen("input.txt","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=3*n;i++) cin>>a[i];
	LL sum=0;
	fill(suml+1,suml+1+3*n,-inf);
	fill(sumr+1,sumr+1+3*n,inf);
	for(int i=1;i<=3*n;i++){
		sum+=(LL)a[i];
		q1.push(a[i]);
		if(i>n){
			int t=q1.top();
			q1.pop();
			sum-=(LL)t;
		}
		if(i>=n) suml[i]=sum;
	}
	sum=0;
	for(int i=3*n;i>=1;i--){
		sum+=(LL)a[i];
		q2.push(a[i]);
		if(i<=2*n){
			int t=q2.top();
			q2.pop();
			sum-=(LL)t;
		}
		if(i<=2*n+1) sumr[i]=sum;
	}
	LL ans=-inf;
	for(int i=1;i<=3*n-1;i++) ans=max(ans,suml[i]-sumr[i+1]);
	cout<<ans<<endl;
	return 0;
}

思路

用优先队列模拟
预处理出suml和sumr 表示从左边(右边)开始前1-3N个数字前N个最大(最小)数字的和
遍历一遍suml[i]-sumr[i+1]即可得到最大值
优先队列每次队头出头满足里面的元素是数量为N的较大值

atcoder_contest74_E

题意

一条直线有N个矩形 每个矩形可以涂成三种颜色中的一种
给出M个要求 每个要求为l到r的矩形内满足至少有x种颜色的矩形

参考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
#include<bits/stdc++.h>
#define LL long long
const LL mod=1e9+7;
#define maxn 305
using namespace std;
struct node{
	int l,num;
	node(int l,int num):l(l),num(num){}
};
vector<node>e[maxn];
LL dp[maxn][maxn][maxn];
int n,m;
bool check(int r,int g,int b){
	int k=max(r,max(g,b));
	for(int i=0;i<e[k].size();i++){
		int cnt=0;
		int left=e[k][i].l;
		if(r>=left) cnt++;
		if(g>=left) cnt++;
		if(b>=left) cnt++;
		if(cnt!=e[k][i].num) return false;
	}
	return true;
}
int main(){
//	freopen("input.txt","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int l,r,x;
		cin>>l>>r>>x;
		e[r].push_back(node(l,x));
	}
	LL ans=0;
	dp[0][0][0]=1;
	for(int r=0;r<=n;r++){
		for(int g=0;g<=n;g++){
			for(int b=0;b<=n;b++){
				LL c=dp[r][g][b];
				if(!c) continue;
				if(!check(r,g,b)){
					dp[r][g][b]=0;
					continue;
				}
				int k=max(r,max(g,b))+1;
				if(k==n+1){
					ans+=dp[r][g][b];
					ans%=mod;
				}
				dp[k][g][b]=(dp[k][g][b]+dp[r][g][b])%mod;
				dp[r][k][b]=(dp[r][k][b]+dp[r][g][b])%mod;
				dp[r][g][k]=(dp[r][g][k]+dp[r][g][b])%mod;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

思路

dp[r][g][b]表示存储红色最后一个 绿色最后一个位置 蓝色最后一个位置的涂色方法
vector记录的是r边界里的最左边界和需要满足的颜色个数
求出最后一个位置的最大值+1 该位置枚举三种颜色
check判断最后一个某颜色的位置是否比左边界大 若大 则cnt++ 判断最后和需要满足的num是否相等

cf_Educational_round 21 D

题目要求

一个数组 可以把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
#include<bits/stdc++.h>
#define LL long long 
#define maxn 100050
using namespace std;
LL a[maxn];
LL suml[maxn],sumr[maxn];
map<LL,LL>l,r;
int main(){
//	freopen("input.txt","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	memset(suml,0,sizeof(suml));
	memset(sumr,0,sizeof(sumr));
	for(LL i=1;i<=n;i++){
		cin>>a[i];
		suml[i]=suml[i-1]+a[i];
		l[a[i]]=i;
	}
	for(LL i=n;i>=1;i--){
		sumr[i]=sumr[i+1]+a[i];
		r[a[i]]=i;
	}
	if(suml[n]&1){
		cout<<"NO"<<endl;
		return 0;
	}
	LL half=suml[n]/2;
	for(LL i=0;i<n;i++){
		if((half==suml[i])||(suml[i]<half&&l[half-suml[i]]>i&&l[half-suml[i]]<=n)){
			cout<<"YES"<<endl;
			return 0;
		}
	}
	for(LL i=n+1;i>=1;i--){
		if((half==sumr[i])||(sumr[i]<half&&r[half-sumr[i]]<i&&r[half-sumr[i]]>0)){
			cout<<"YES"<<endl;
			return 0;
		}
	}
	cout<<"NO"<<endl;
	return 0;
}

思路

suml和sumr分别从左边和右边开始的前缀和
map记录从左边和后边开始 每个数最后出现的位置
如果总和为奇数 输出NO
如果half等于suml或者sumr 直接输出YES
如果左边开始的前缀和小于half 说明需要从后面调一个元素过来 若这个元素的位置大于i小于等n 那么满足
从右边开始同理
需要注意两个地方：
（1）：for循环为0到n-1和n+1到1 边界取到0和n+1是因为可能满足half就等于某个数 直接把他移到头部或尾部
即可。若上限改成1和n可能存在永远无法取到单个half值的情况
（2）：位置的边界问题 特别注意第二个for循环从右边开始找前缀和时 需要加大于0的条件 因为可能存在某个数字
不存在在map中初始化为了0小于i 导致结果出错 第一个for的小于等于n可加可不加

cf_Educational_round 21 E

题目要求

扩大版01背包 w可取123三种情况

参考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
#include<bits/stdc++.h>
using namespace std;  
const int MAXN=300000+10;  
typedef long long  ll;  
struct{  
    ll v;  
    ll s1,s2;  
}dp[MAXN];  
ll a[4][MAXN];  //类似vector存值
ll s[4][MAXN];  //前缀和
int num[4];     //表示123三种容量的个数
int cmp(int x,int y){return x>y;}  
int main() {  
//	freopen("input.txt","r",stdin);
    int n,m;  
    scanf("%d%d",&n,&m);  
    num[1]=num[2]=num[3]=0;  
    for(int i=1;i<=n;i++){  
        ll w,c;  
        scanf("%lld%lld",&w,&c);  
        a[w][++num[w]]=c;  
    }  
    for(int i=1;i<=3;i++){  
        sort(a[i]+1,a[i]+num[i]+1,cmp);  
        for(int j=1;j<=num[i];j++){  
            s[i][j]=s[i][j-1]+a[i][j];  
        }  
    }
    dp[0].v=dp[0].s1=dp[0].s2=0;  
    for(int i=1;i<=m;i++){  
        dp[i]=dp[i-1];  
        if(dp[i-1].v+a[1][dp[i-1].s1+1]>dp[i].v){  
            dp[i].v=dp[i-1].v+a[1][dp[i-1].s1+1];  
            dp[i].s1=dp[i-1].s1+1;  
            dp[i].s2=dp[i-1].s2;  
        }  
        if(i>=2&&dp[i-2].v+a[2][dp[i-2].s2+1]>dp[i].v){  
            dp[i].v=dp[i-2].v+a[2][dp[i-2].s2+1];  
            dp[i].s1=dp[i-2].s1;  
            dp[i].s2=dp[i-2].s2+1;  
        }  
    }  
    ll res=0;  
    for(int i=0;i<=num[3];i++){  
        if(m>=i*3)  
            res=max(res,s[3][i]+dp[m-3*i].v);  
    }  
    cout<<res<<endl;
}

思路

不能像atcoder一样用vector存+贪心暴力 超时
使用dp+贪心
dp[w]里存放一个三元组 表示w容量下 取s1个第一件物品和s2件第一件物品获得的最大价值
先预处理好这部分 遍历容量为3的前缀和 剩下的1和2一共还要取m-3*i件 直接dp取值即可

atcoder_round415_C

题意

求一个数组中所有子串中最大值-最小值的和

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9+7;
ll a[300010],b[300010];
int main(){
//	freopen("input.txt","r",stdin);
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	ll sum=0;
	for(int i=1;i<=n;i++)  cin>>a[i];
	sort(a+1,a+n+1);
	b[0]=1;
	for(int i=1;i<=n;i++)  b[i]=b[i-1]*2%mod;
	for(int i=1;i<=n;i++){
		sum=(sum+a[i]*(b[i-1]-1)%mod)%mod;
		sum=(sum-a[i]*(b[n-i]-1)%mod)%mod;
	}
	cout<<(sum+mod)%mod<<'\n';
	return 0;
}

思路

归纳出公式　其实就是算每个相邻的线段一共出现了多少次　再乘以线段长度
出现次数公式为(2^(i-1)-1)-(2^(n-i)-1)

本文标题:cf&at 杂选

文章作者:Hippopmonkey

发布时间:2017-05-23, 09:48:46

最后更新:2017-05-29, 13:17:15

原始链接:http://xuboming8.github.io/2017/05/23/cf-at-杂选/

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

文章目录
  1. 1. cf&at 杂选
    1. 1.1. atcoder_contest74_D
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. atcoder_contest74_E
      1. 1.2.1. 题意
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. cf_Educational_round 21 D
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. cf_Educational_round 21 E
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. atcoder_round415_C
      1. 1.5.1. 题意
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
|