Codeforces Global Round 2_codeforce global round 2题解

Codeforces Global Round 2
B - Alyona and a Narrow Fridge(贪心)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void)
{
	cin.tie(0);
	// freopen(“in.txt”,“r”,stdin);
	// freopen(“out.txt”,“w”,stdout);
	int n , h; cin >> n >> h;
	vector <int> a(n);
	for(int i = 0; i < n; i++)
		cin >> a[i];
	priority_queue <int> q;
	int res = h, i;
	for(i = 0; i < n; i++)
	{
		priority_queue <int> p;
		q.push(a[i]);
		res = h;
		while(!q.empty()){
			res -= q.top();
			p.push(q.top());
			q.pop();
			if(!q.empty()) {
				p.push(q.top());
				q.pop();
			}
		}
		q = p;
		if(res < 0) break;
	}
	cout << i << endl;
	return 0;
}

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

C - Ramesses and Corner Inversion（规律）

#include<bits/stdc++.h>
using namespace std;
int main(void)
{
	cin.tie(0);
	int n,m; cin >> n>> m;
	std::vector<std::vector<int> > a(n,std::vector<int> (m));
	std::vector<std::vector<int> > b(n,std::vector<int> (m));
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			cin >> a[i][j];
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
				cin >> b[i][j];
	for(int i = 0; i < n; i++)
	{
		int sum = 0;
		for(int j = 0; j < m; j++)
				if(a[i][j]^b[i][j]) sum++;
		if(sum&1) { cout << "No" << endl; return 0;}
	}
	for(int i = 0; i < m; i++)
	{
		int sum = 0;
		for(int j = 0; j < n; j++)
			if(a[j][i]^b[j][i]) sum++;
		if(sum&1) { cout << "No" << endl; return 0;}		
	}
	cout << "Yes" << endl;
	return 0;
}
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

D题TLE代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void)
{
	cin.tie(0);
	int n; cin >> n;
	std::vector<ll> a(n+1);
	a[0] = - (1e18);	
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a.begin(),a.end());  
	int m = unique(a.begin(),a.end()) - a.begin();  
//	for(int i = 0; i < m; i++) cout << a[i] << endl;
	std::vector<ll> v(m+1); 
	for(int i = 1; i < m; i++)
		v[i] = a[i] - a[i-1];
	int q; cin >> q;
	while(q--)
	{
		ll l,r; cin >> l >> r;
		r = r - l + 1; 
		ll ans = r;
		for(int i = 2; i < m; i++)
			ans += min(r,v[i]);  
		cout << ans << endl; 
	}
	return 0;
	
}
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

D题前缀维护AC

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void)
{
	std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
	int n;cin >> n;
	std::vector<ll> a(n+1);
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a.begin(),a.end());  
	//int m = unique(a.begin(),a.end()) - a.begin();  
	//for(int i = 0; i < m; i++) cout << a[i] << endl;
	std::vector<ll> v(n+1); 
	for(int i = 2; i <= n; i++)
		v[i] = a[i] - a[i-1];
	sort(v.begin()+2,v.begin()+n+1);  
	std::vector<ll> sum(n+1);  //前缀和维护
	for(int i = 2; i <= n; i++)
		sum[i] = sum[i-1] + v[i];
	int q; cin >> q;
	while(q--)
	{
		ll l,r; 
		cin >> l >> r;
		r = r - l + 1;  
		int prefix = lower_bound(v.begin(),v.begin()+n+1,r) - v.begin();
		ll ans = r + sum[prefix - 1] + (n - prefix + 1)*r;
		// for(int i = 2; i < m; i++)
		// 	ans += min(r,v[i]);  
		cout << ans << endl;
	}
	return 0;
	
}
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

E. Pavel and Triangles（思维） ※※

/*
* @Author: Achan
* @Date:   2019-04-11 09:52:14
* @Last Modified by:   Achan
* @Last Modified time: 2019-04-11 10:09:32
*/
#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<iomanip>
#include<vector> 
#include<queue>
#include<cmath> 
using namespace std;

#define X 			first
#define Y 			second
#define eps  		1e-2
#define gcd 		__gcd
#define pb 			push_back
#define PI 			acos(-1.0)
#define lowbit(x) 	(x)&(-x)
#define fin         freopen("in.txt","r",stdin);
#define fout        freopen("out.txt","w",stdout);
#define Debug(format, ...) printf(format, ##__VA_ARGS__)
#define bug 		printf("!!!!!\n");
#define mem(x,y)	memset(x,y,sizeof(x))
#define rep(i,j,k)  for(int i=j;i<(int)k;i++)
#define per(i,j,k)  for(int i=j;i<=(int)k;i++)
#define pset(x)     setiosflags(ios::fixed)<<setprecision(x)
#define io std::ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);

typedef long long ll;
typedef long double LD; 
typedef pair<int,int> pii;
typedef unsigned long long ull; 

const int inf  = 1<<30;
const ll  INF  = 1e18 ;
const int mod  = 1e9+7;
const int maxn = 1e5+2;
const int mov[4][2] = {-1,0,1,0,0,1,0,-1};
const int Mov[8][2] = {-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1};
 
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

void read(int &x)
{
    x=0;int f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    x*=f;return;
}




int main(void)
{
	int n = read();
	std::vector<int> a(n);
	for(int i = 0; i < n; i++) read(a[i]);
	ll ans = 0, pairs = 0;
	for(int i = n-1; ~i; i--)
	{
		pairs +=  a[i]/2;
		(a[i]&1)&&pairs? ans++, pairs-- : ans; 
	}
	printf("%lld\n", ans + pairs*2/3);




 	return 0;
 #ifdef LOCAL
    Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
 #endif   
}
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