cf杂选

自用笔记算法

cf杂选

411 E

参考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 300050
using namespace std;
vector<int>e1[maxn],e2[maxn];
int color[maxn],used[maxn];
int n,m;
int ans;
void dfs(int cur,int fa){
	for(int i=0;i<e1[cur].size();i++) used[color[e1[cur][i]]]=1;
	int col=1;
	for(int i=0;i<e1[cur].size();i++){
		if(color[e1[cur][i]]==0){
			while(used[col]==1) col++;
			color[e1[cur][i]]=col;
			ans=max(ans,col);
			used[col]=1;
		}
	}
	for(int i=0;i<e1[cur].size();i++) used[color[e1[cur][i]]]=0;
	for(int i=0;i<e2[cur].size();i++) if(e2[cur][i]!=fa) dfs(e2[cur][i],cur); 
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		int x;	
		scanf("%d",&x);
		for(int j=1;j<=x;j++){
			int y;	
			scanf("%d",&y);
			e1[i].push_back(y);
		}
	}
	for(int i=1;i<n;i++){
		int x,y;	
		scanf("%d%d",&x,&y);
		e2[x].push_back(y);
		e2[y].push_back(x);
	}
	dfs(1,-1);
	if(!ans) ans=1;
	printf("%d\n",ans);
	for(int i=1;i<=m;i++) printf("%d%c",color[i]?color[i]:1,i==m?'\n':' ');
	return 0;
}

思路

连通块染色 dfs

412 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
24
25
26
27
28
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL x,y,p,q;
bool check(LL t){
   return ((p*t>=x)&&((q*t-p*t)>=(y-x)));
}
int main(){
  //  freopen("input.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%I64d%I64d%I64d%I64d",&x,&y,&p,&q);
        LL l=0,r=1e9,mid;
        LL ans=-1;
        while(l<=r){
            mid=(l+r)/2;
            if(check(mid)){
                ans=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        if(ans==-1) printf("-1\n");
        else printf("%I64d\n",ans*q-y);
    }
    return 0;
}

413 E

题意

有n件物品和它的价格 需要敲好取m件 要求a和b两个人在这m件物品里分别至少喜欢k件
给出a和b喜欢物品的编号
求出最小的cost

参考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 LL long long
#define maxn 200050
#define inf 0x3f3f3f3f
using namespace std;
vector<int>a[4];
vector<LL>sum[4];
int hasha[maxn],hashb[maxn];
int c[maxn];
int main(){
  //  freopen("input.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m,k,t;
    cin>>n>>m>>k;
    memset(hasha,0,sizeof(hasha));
    memset(hashb,0,sizeof(hashb));
    for(int i=1;i<=n;i++) cin>>c[i];
    cin>>t;
    for(int i=0;i<t;i++){
        int x;
        cin>>x;
        hasha[x]=1;
    }
    cin>>t;
    for(int i=0;i<t;i++){
        int x;
        cin>>x;
        hashb[x]=1;
    }
    for(int i=1;i<=n;i++){
        if(hasha[i] && hashb[i]) a[3].push_back(c[i]);
        else if(!hasha[i] && hashb[i]) a[2].push_back(c[i]);
        else if(hasha[i] && !hashb[i]) a[1].push_back(c[i]);
        else a[0].push_back(c[i]);
    }
    for(int i=0;i<4;i++) sort(a[i].begin(),a[i].end());
    for(int i=0;i<4;i++) sum[i].push_back(0);
    for(int i=0;i<4;i++){
        for(int j=0;j<a[i].size();j++) sum[i].push_back(sum[i].back()+a[i][j]);
    }
    LL ans=1e18+1;
    for(int i=0;i<=a[3].size();i++){
        LL cost=sum[3][i];
        int need=max(0,k-i);
        if(need>a[1].size()||need>a[2].size()||i+need*2>m) continue;
        cost+=sum[1][need],cost+=sum[2][need];
        int left=m-i-2*need;
        if(a[1].size()-need+a[2].size()-need+a[0].size()<left) continue;
        if(left>0){
            int l=0,r=1e9;
            while(l<r){
                int mid=(l+r)/2;
                int cnt=0;
                int h=upper_bound(a[0].begin(),a[0].end(),mid)-a[0].begin();
                cnt+=max(0,h);
                h=upper_bound(a[1].begin(),a[1].end(),mid)-a[1].begin();
                cnt+=max(0,h-need);
                h=upper_bound(a[2].begin(),a[2].end(),mid)-a[2].begin();
                cnt+=max(0,h-need);
                if(cnt>=left) r=mid;
                else l=mid+1;
            }
            int mid=l,cnt=0;
            int h=upper_bound(a[0].begin(),a[0].end(),mid)-a[0].begin();
            cnt+=max(0,h);
            cost+=sum[0][h];
            h=upper_bound(a[1].begin(),a[1].end(),mid)-a[1].begin();
            cnt+=max(0,h-need);
            if(h>need) cost+=sum[1][h]-sum[1][need];
            h=upper_bound(a[2].begin(),a[2].end(),mid)-a[2].begin();
            cnt+=max(0,h-need);
            if(h>need) cost+=sum[2][h]-sum[2][need];
            if(cnt>left) cost-=mid*(cnt-left);
        }
        ans=min(ans,cost);
    }
    if(ans>1e17) ans=-1;
    cout<<ans<<endl;
    return 0;
}

思路

物品只有四种状态：a和b都不喜欢 a喜欢b不喜欢 b喜欢a不喜欢 a和b都喜欢
分别用0 1 2 3四种状态表示他们 vector a和sum的编号与他们对应 sum求的是前i项和
用hash的思想把四种状态存好
首先从a和b都喜欢的状态可以遍历sum 接下来a和b分别还要取出喜欢的k-i件 若还有left剩余 在a或者b或者ab都不喜欢里面挑选
最后一个状态使用二分答案 二分的是找出012三种状态大于他们的最小的数 二分出的数字为l
接下来看012三种状态的剩余 若有剩余把前i项和都加上
这里存在一个问题 就是三个状态相加后可能大于left 这时要把多余的部分去掉
还需注意这里的最大值为1e18 因为1e9相乘的前n项和已经超过了int的范围

cf 414 C

题目要求

a和b分别有一个长度为n的字母集合 要填充到一个长度也为n的字符串中 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
#include<bits/stdc++.h>
 using namespace std;
 int main(){
  //   freopen("input.txt","r",stdin);
     ios::sync_with_stdio(false);
     cin.tie(0);
     string s1,s2;
     cin>>s1>>s2;
     int n=s1.length();
     sort(s1.begin(),s1.end());
     sort(s2.begin(),s2.end());
     reverse(s2.begin(),s2.end());
     string s;
     for(int i=0;i<n;i++) s+="?";
     int l=0,r=n-1;
     int a_l=0,b_l=0;
     int a_r=n-(n/2)-1,b_r=(n/2)-1;
     for(int i=0;i<n;i++){
        if(i%2==0){
            if(s1[a_l]<s2[b_l]){
                s[l]=s1[a_l];
                l++,a_l++;
            }
            else{
                s[r]=s1[a_r];
                r--,a_r--;
            }
        }
        else{
            if(s1[a_l]<s2[b_l]){
                s[l]=s2[b_l];
                l++,b_l++;
            }
            else{
                s[r]=s2[b_r];
                r--,b_r--;
            }
        }
     }
     cout<<s<<endl;
     return 0;
 }

思路

贪心
把a按照升序排列 b按照降序排列 那么最后实际用到的分别就是n/2上取整的数字
贪心策略为：
首先按照奇偶性判断谁动
若a比b小 那么自然a把最小的放在最左边
若a比b大 那么两人都希望对方把该数放在第一个 所以此时不能考虑首位而要考虑末尾
此时a需要把最大的数字放到末尾确保字典序最小
b移动与a的策略同理
这里需要注意的是a的数量是n-(n/2)-1 因为如果n为奇数 那么最后a需要多取一个 这样确保a的数量是正确的

cf 414 F

题意

线段树
每次可以有2种询问方式
1是把l和r中所有数字某位的u变成v
2是求出l和r中的和

参考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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000;
int a[N+1][10];
struct node
{
	int nxt[10];
	ll sum[10];
};
node st[N*4+1];
void push_down(int rt){
	for(int i = 0; i < 10; i++) st[rt].sum[i]=st[rt*2].sum[i]+st[rt*2+1].sum[i];
}
void build(int rt, int l, int r)
{
	if(r-l<2){
		for(int i = 0; i < 10; i++) st[rt].sum[i]=a[l][i];
		for(int i = 0; i < 10; i++) st[rt].nxt[i] = i;
		return ;
	}
	for(int i = 0; i < 10; i++) st[rt].nxt[i] = i;
	int mid=(l+r)>>1;
	build(rt*2,l,mid);
	build(rt*2+1,mid,r);
	push_down(rt);
}
ll sum[10];
void push_up(int rt, int l, int r){
	memset(sum,0,sizeof(sum));
	if(r-l>=2){
		for(int i=0;i<10;i++){
			st[rt*2].nxt[i]=st[rt].nxt[st[rt*2].nxt[i]];
			st[rt*2+1].nxt[i]=st[rt].nxt[st[rt*2+1].nxt[i]];
		}
	}
	for(int i=0;i<10;i++) sum[st[rt].nxt[i]]+=st[rt].sum[i];
	for(int i=0;i<10;i++){
		st[rt].sum[i]=sum[i];
		st[rt].nxt[i]=i;
	}
}
void update(int rt, int l, int r, int ql, int qr, int u, int v){
	push_up(rt,l,r);
	if(ql>=r||l>=qr) return ;
	if(ql<=l&&r<=qr){
		st[rt].nxt[u]=v;
		push_up(rt,l,r);
		return ;
	}
	int mid=(l+r)>>1;
	update(rt*2,l,mid,ql,qr,u,v);
	update(rt*2+1,mid,r,ql,qr,u,v);
	push_down(rt);
}
ll query(int rt, int l, int r, int ql, int qr){
	push_up(rt,l,r);
	if(ql>=r||l>=qr) return 0;
	if(ql<=l&&r<=qr){
		ll sum=0;
		for(int i=1;i<10;i++) sum+=ll(i)*st[rt].sum[i];
		return sum;
	}
	int mid=(l+r)>>1;
	return (query(rt*2,l,mid,ql,qr)+query(rt*2+1,mid,r,ql,qr));
}
int main(){
   // freopen("input.txt","r",stdin);
	ios_base::sync_with_stdio(0);
    cin.tie(0);
	int n, q;
    cin>>n>>q;
	for(int i = 0; i < n; i++){
		int x;
		cin>>x;
		int cur=1;
		for(int j = 0; j < 9; j++){
			a[i][x%10] += cur;
			x/=10;
			cur*=10;
			if(x==0) break;
		}
	}
	build(1,0,n);
	for(int i = 0; i < q; i++){
		int type;
		cin>>type;
		if(type==1){
			int l,r,u,v;
			cin>>l>>r>>u>>v;
			l--; r--;
			update(1,0,n,l,r+1,u,v);
		}
		else{
			int l,r; cin>>l>>r;
			l--; r--;
			ll sum = query(1,0,n,l,r+1);
			cout<<sum<<'\n';
		}
	}
}

思路

用hash的思想来存储线段树
0-9每个数位上存放的数字表示该数字乘存放的大小(10^x)表示该位的大小
例如 0 0 0 10 100 0 0 0 0 表示430
线段树上存放每个数字0-9的状态 sum表示该位存放的所有10的阶乘 next为指向下一个0-9数字的指针

本文标题:cf杂选

文章作者:Hippopmonkey

发布时间:2017-05-19, 08:02:06

最后更新:2017-05-19, 10:03:17

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

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

文章目录
  1. 1. cf杂选
    1. 1.1. 411 E
      1. 1.1.1. 参考AC代码
      2. 1.1.2. 思路
    2. 1.2. 412 c
      1. 1.2.1. 题意
      2. 1.2.2. 参考AC代码
    3. 1.3. 413 E
      1. 1.3.1. 题意
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. cf 414 C
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. cf 414 F
      1. 1.5.1. 题意
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
|