cf杂选2

自用笔记算法

cf杂选2

817 A

题目要求

给出初始坐标和目标坐标
并给出(x,y)每次可以在初始坐标上执行(x,y),(x,-y),(-x,y),(-x,-y)

参考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
#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;
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int x1,x2,y1,y2;
	int x,y;
	cin>>x1>>y1>>x2>>y2>>x>>y;
	if((abs(x1-x2)%x!=0)||(abs(y1-y2)%y!=0)){
		cout<<"NO"<<endl;
		return 0;
	}
	int t1=abs(x1-x2)/x;
	int t2=abs(y1-y2)/y;
	int ans=max(t1,t2)-min(t1,t2);
	if(ans&1) cout<<"NO"<<endl;
	else cout<<"YES"<<endl;
	return 0;
}

思路

若x1-x2不能被x整除或y1-y2不能被y整除 均NO
整除做减法后奇数输出NO 偶数输出YES
偶数可以开会”跳”到结果

817 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
#include<bits/stdc++.h>
#define maxn 100050
#define inf 0x3f3f3f3f
#define LL long long
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
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;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+1+n);
	LL cnt=0;
	for(int i=1;i<=n;i++) if(a[i]==a[3]) cnt++;
	if(a[1]==a[2] && a[2]==a[3]) cout<<cnt*(cnt-1)*(cnt-2)/6<<endl;
	else if(a[1]==a[2] && a[2]<a[3]) cout<<cnt<<endl;
	else if(a[1]<a[2] && a[2]==a[3]) cout<<cnt*(cnt-1)/2<<endl;
	else if(a[1]<a[2] && a[2]<a[3]) cout<<cnt<<endl;
	return 0;
}

思路

计算出a[3]的个数 组合数

817 C

题目要求

求出满足该数x-sum(各位相加只和)>=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
#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)
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL n,s;
bool check(LL x){
	LL sum=0;
	LL temp=x;
	while(x){
		sum+=x%10;
		x/=10;
	}
	return temp-sum>=s;
}
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>>s;
	LL l=1,r=1LL*1e18,mid,ans=0;
	LL res;
	while(l<=r){
		mid=(l+r)>>1;
		if(check(mid)){
			ans=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	if(ans==0) res=0;
	else res=n-ans+1<0?0:n-ans+1;
	cout<<res<<endl;
	return 0;
}

思路

由于随着数字每增加10 x-sum会增加9 满足递增有序 所以二分答案即可
找到最小的满足条件的数字 n-ans+1就是答案
注意边界即可 可能ans比n大 此时res=0
并且可能ans=0表示没有找到 此时res=0

817 D

题目要求

求出一个数组内所有子序列的最大值-最小值的和

参考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
#include<bits/stdc++.h>
#define maxn 1000050
#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 ans;
int n;
int a[maxn],l[maxn],r[maxn];
void solve(){
	for(int i=0;i<n;i++) l[i]=r[i]=i;
	for(int i=0;i<n;i++){
		int temp=i;
		while(temp && a[i]>=a[temp-1]) temp=l[temp-1];
		l[i]=temp;
	}
	for(int i=n-1;i>=0;i--){
		int temp=i;
		while(temp<n-1 && a[i]>a[temp+1]) temp=r[temp+1];
		r[i]=temp;
	}
	for(int i=0;i<n;i++) ans+=(LL)(r[i]-i+1)*(i-l[i]+1)*a[i];
}
int main(){
//	freopen("input.txt","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	mm(l,0),mm(r,0); ans=0;
	solve();
	for(int i=0;i<n;i++) a[i]*=-1;
	solve();
	cout<<ans<<endl;
	return 0;
}

思路

首先更新出每个作为最大值向左和向右最多能走多远 记为l和r
接着把每个数字取反再带入solve函数求出的就是作为最小值左右能走多远
枚举每个区间长度相加就是答案 相当于最大值的和减去最小值的和

round419_B

题目要求

先给出区间的覆盖情况
每次询问区间内至少被覆盖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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#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)
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
int a[maxn+50];
int sum[maxn+50];
int c[maxn];
int lowbit(int x){
	return x&(-x);
}
void create(int n){
	for(int i=1;i<=n;i++){
		int s=lowbit(i);
		for(int j=0;j<s;j++)
			c[i]+=sum[i-j];
	}
}
int Sum(int idx){
	int sum=0;
	while(idx>0){
		int s=lowbit(idx);
		sum+=c[idx];
		idx-=s;
	}
	return sum;
}
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,q;
	cin>>n>>k>>q;
	mm(a,0),mm(sum,0);
	for(int i=1;i<=n;i++){
		int l,r;
		cin>>l>>r;
		a[l]++,a[r+1]--;
	}
	sum[0]=a[0];
	for(int i=1;i<maxn;i++) sum[i]=sum[i-1]+a[i];
	for(int i=0;i<maxn;i++){
		if(sum[i]>=k) sum[i]=1;
		else sum[i]=0;
	}
	create(maxn);
	for(int i=1;i<=q;i++){
		int count=0;
		int l,r;
		cin>>l>>r;
		cout<<Sum(r)-Sum(l-1)<<endl;
	}
	return 0;
}

思路

预处理presum+树状数组
跟处理覆盖k次区间的总长度略有不同
并不能只预处理所有的端点 因为本题的询问会针对区间内的所有整数
所以正解为：对于每次区间a[l]++ a[r+1]–(加1解决端点重叠问题)
预处理sum前缀和后即可求出每个数字被覆盖的次数 hash思想
遍历一遍 对于大于等于k的数字置为1 其余置为0 接着带入树状数组求出区间和即可
就是本题要求的满足的覆盖点数

round419_C

题目要求

初始矩阵为0 给出目标矩阵 每次可以对每一列或每一行+1 问最少需要多少次操作可以变成目标矩阵
达不到输出-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
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
#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;
int g[maxn][maxn];
int minr[maxn],minc[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,m;
	cin>>n>>m;
	mm(minr,inf),mm(minc,inf);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) cin>>g[i][j];
	}
	int sum=0;
	if(n<=m){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++) minr[i]=min(minr[i],g[i][j]);
			sum+=minr[i];
			for(int j=1;j<=m;j++) g[i][j]-=minr[i];
		}
		for(int j=1;j<=m;j++){
			for(int i=1;i<=n;i++) minc[j]=min(minc[j],g[i][j]);
			sum+=minc[j];
			for(int i=1;i<=n;i++) g[i][j]-=minc[j];
		}
	}
	else{
		for(int j=1;j<=m;j++){
			for(int i=1;i<=n;i++) minc[j]=min(minc[j],g[i][j]);
			sum+=minc[j];
			for(int i=1;i<=n;i++) g[i][j]-=minc[j];
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++) minr[i]=min(minr[i],g[i][j]);
			sum+=minr[i];
			for(int j=1;j<=m;j++) g[i][j]-=minr[i];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) if(g[i][j]){
			cout<<"-1"<<endl;
			return 0;
		}
	}
	cout<<sum<<endl;
	for(int i=1;i<=n;i++) if(minr[i]){
		for(int k=1;k<=minr[i];k++) cout<<"row "<<i<<endl;
	} 
	for(int i=1;i<=m;i++) if(minc[i]){
		for(int k=1;k<=minc[i];k++) cout<<"col "<<i<<endl;
	}
	return 0;
}

思路

预处理出每行和每列的最小值 求出最小值的同时 对这一行或这一列的元素全部减去最小值
sum加上最小值 就是最后需要操作的次数
由于需要最小的操作次数 所以先处理行和列中的较小者 即可满足要求
如果预处理完的矩阵还有元素不为0 输出-1
否则for输出row和col即可

815 C

题目要求

超市里有n种商品，第i件物品价格为ci，除了第一件物品以外，每个物品都有优惠劵，可以优惠di，但是第i件物品能使用优惠劵的前提是第xi (1 <= xi < i) 件物品已经用优惠券买过。每件物品只能买一次，问在不超过预算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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
#define maxn 5050
#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 dp[maxn][maxn][2];
LL n,b,c[maxn],d[maxn];
LL sz[maxn];
vector<int>e[maxn<<1];
void dfs(int u){
	sz[u]=1;
	dp[u][0][0]=0;
	dp[u][1][0]=c[u];
	dp[u][1][1]=c[u]-d[u];
	for(int i=0;i<e[u].size();i++){
		int v=e[u][i];
		dfs(v);
		for(int j=sz[u];j>=0;j--){
			for(int k=0;k<=sz[v];k++){
				dp[u][j+k][0]=min(dp[u][j+k][0],dp[u][j][0]+dp[v][k][0]);
				dp[u][j+k][1]=min(dp[u][j+k][1],dp[u][j][1]+dp[v][k][1]);
				dp[u][j+k][1]=min(dp[u][j+k][1],dp[u][j][1]+dp[v][k][0]);
			}
		}
		sz[u]+=sz[v];
	}
}
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>>b;
	mm(dp,inf);
	for(int i=0;i<=n;i++) e[i].clear();
	cin>>c[1]>>d[1];
	for(int i=2;i<=n;i++){
		int x;
		cin>>c[i]>>d[i]>>x;
		e[x].pb(i);
	}
	dfs(1);
	LL ans=0;
	for(int i=n;i>=0;i--){
		if(dp[1][i][0]<=b || dp[1][i][1]<=b){
			ans=i;
			break;
		}
	}
	cout<<ans<<endl;
	return 0;
}

思路

依赖型01背包问题
可以转换成树形dp
dp[now][x][1]表示，在now节点，买x个，并且now可以使用优惠券的最小花费
dp[now][x][0]表示，在now节点，买x个，并且now不可以使用优惠券的最小花费
背包逆序
最后逆序遍历n到1求出第一个满足小于b的的数量就是最大解

817 E

题目要求

每次添加或者删除一个人 权值为p
每次询问一个人 权值为p和l 对于前面所有的人若p和该人的p xor后小于l count++ 输出最后的count值

参考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
#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)
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
int trie[maxn*40][2],cnt[maxn*40],sz;
void init(){
	sz=1;
	mm(trie,0),mm(cnt,0);
}
void insert(int pos,int num,int bit){
//	cout<<pos<<endl;
	cnt[pos]++;
	if(bit<0) return;
	if((num&(1<<bit))==0){
		if(trie[pos][0]==0){
			trie[pos][0]=sz;
			sz++;
		}
		insert(trie[pos][0], num, bit-1);
	}
	else{
		if(trie[pos][1]==0){
			trie[pos][1]=sz;
			sz++;
		}
		insert(trie[pos][1], num, bit-1);
	};
	
}
void delet(int pos,int num,int bit){
	cnt[pos]--;
	if(bit<0) return;
	if((num&(1<<bit))==0) delet(trie[pos][0], num, bit-1);
	else delet(trie[pos][1], num, bit-1);
}
int query(int pos,int p,int l,int bit){
	if(bit<0) return 0;
	int lbit=(l&(1<<bit));
	int pbit=(p&(1<<bit));
	if(lbit) lbit=1;
	if(pbit) pbit=1;
	if(lbit==0){
		if(trie[pos][pbit]==0) return 0;
		return query(trie[pos][pbit], p, l, bit-1);
	}
	else{
		int ans=0;
		if(trie[pos][pbit]!=0) ans+=cnt[trie[pos][pbit]];
		if(trie[pos][1-pbit]!=0) ans+=query(trie[pos][1-pbit], p, l, bit-1);
		return ans;
	}
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	init();
	int t;
	cin>>t;
	while(t--){
//		for(int i=0;i<=40;i++) cout<<cnt[i]; cout<<" "; cout<<sz<<endl;
		int op; cin>>op;
		if(op==1){
			int x; cin>>x;
			insert(0,x,30);
		}
		if(op==2){
			int x; cin>>x;
			delet(0,x,30);
		}
		if(op==3){
			int x,y; cin>>x>>y;
			cout<<query(0,x,y,30)<<endl;
		}
	}
	return 0;
}

思路

xor相关 可以想到二叉字典树 即01字典树

本文标题:cf杂选2

文章作者:Hippopmonkey

发布时间:2017-06-16, 18:48:50

最后更新:2017-06-22, 18:16:58

原始链接:http://xuboming8.github.io/2017/06/16/cf杂选-1/

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

文章目录
  1. 1. cf杂选2
    1. 1.1. 817 A
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. 817 B
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. 817 C
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. 817 D
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. round419_B
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
    6. 1.6. round419_C
      1. 1.6.1. 题目要求
      2. 1.6.2. 参考AC代码
      3. 1.6.3. 思路
    7. 1.7. 815 C
      1. 1.7.1. 题目要求
      2. 1.7.2. 参考AC代码
      3. 1.7.3. 思路
    8. 1.8. 817 E
      1. 1.8.1. 题目要求
      2. 1.8.2. 参考AC代码
      3. 1.8.3. 思路
|