Codeforces Round #704 (Div. 2) C1C2D_codeforces #704

题外话：由于一些原因，拿小号打的，然后就发现拿小号打大概是真的没压力吧，乱交，哈哈qaq，and 比赛很随意，后来困了现场泡咖啡，晚上直接失眠，我生物钟乱了cf要负一半责任thx（不是

但是总体来说每题都要卡还是我的问题，and C2直接想不明白（也不是太没思路，这次看数据一猜就二分，也猜到大概怎么搞但是就是想不清楚（好的很，下次晚上同时段要多练练脑子）, 还剩20+min开的D，我一看直接贪了个长度就是K然后改了个平衡树板子往上交，wa7，后来发现长度不一定为k，（）当时时间太紧了，但是也改不太出来，等手题解
upd：D已补，在后面

好的官方题解出的好快竟然已经有了（*…

---

A

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
	int T;
	cin >> T;
	while(T--) {
		ll n;
		cin >> n;
		ll x, sum = 0;
		bool f = 0;
		for(int i = 0; i < n; ++ i) {
			cin >> x;
			if(x >= i) {
				sum += x - i;
			}
			else {
				if(x + sum >= i) {
					sum = x + sum - i;
				}
				else {
					f = 1;
				}
			}
		}
		if(!f) cout <<"YES\n";
		else cout << "NO\n";
	}
} 
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

B

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

typedef long long ll;

struct node {
	ll x, y;
}mp[N];

vector<ll> xs, ys;


int main() {
//	freopen("in.txt","r",stdin);
	int T;
	cin >> T;
	while(T--) {
		int n;
		cin >> n;
		xs.clear(); ys.clear();
		for(int i = 1; i <= n; ++ i) {
			cin >> mp[i].x >> mp[i].y;
			xs.push_back(mp[i].x);
			ys.push_back(mp[i].y);
		}
		
		sort(xs.begin(), xs.end());
		sort(ys.begin(), ys.end());
		
		if(n & 1) {
			cout << 1 << endl;
			continue;
		}
		else {
			ll ans =  (xs[n / 2] - xs[n / 2 - 1] + 1) * (ys[n / 2] - ys[n / 2 - 1] + 1);
			cout << ans << endl;
		}
			
	}
} 
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

---

C1

40次，两倍log，随便造作就完事了，也是二分…

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n;
	cin >> n;
	int l = 1, r = n;
	int pos;
	cout << "? " << l << " " << r << endl; fflush(stdout);
	cin >> pos;
	while(r - l >= 2) {
		int mid = l + r >> 1;
		int p1;
		if(mid > pos) {
			cout << "? " << l << " " << mid << endl; fflush(stdout);
			cin >> p1;
			if(p1 == pos) {
				r = mid;
			}
			else {
				l = mid;
				cout << "? " << l << " " << r << endl; fflush(stdout);
				cin >> pos;
			}
		}else {
			cout << "? " << mid << " " << r << endl; fflush(stdout);
			cin >> p1;
			if(p1 == pos) {
				l = mid;
			}
			else {
				r = mid;
				cout << "? " << l << " " << r << endl; fflush(stdout);
				cin >> pos;
			}
		}
	}
	
	if(l == r) {
		cout << "! " << l << endl;
		return 0; 
	}
	int res;
	cout << "? " << l << " " << r << endl;
	fflush(stdout);
	cin >> res;
	if(res == l) {
		cout << "! " << r << endl;
		fflush(stdout);
	}
	else {
		cout << "! " << l << endl;
		fflush(stdout);
	}
	
	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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

C2 - Guessing the Greatest (hard version)

题意： 有一个数列，你有20次询问的机会，每次可以询问一个区间$[l,r]$，会告诉你区间中第二大的元素的下标，你需要在至多20次询问后得出$[1,n]$中的最大值，

$n\le 2e5$， 20次询问，一看就很二分（

我总觉得整体第二大在某些情况要改掉，所以一直是最坏27次询问，进不了20，（

后来睡不着然后想到：我为什么不能一直带着整体第二大一起玩呢（…

思路： 先求出整体第二大$pos$，然后询问$[1,pos]$或者$[pos,r]$， 把$pos$弄到边上去，之后缩小范围$[l,r],mid$的时候每次把pos所在位置一起问进去就好

注意判断，不能询问长度小于2的区间…

#include <bits/stdc++.h>
using namespace std;

void ques(int l, int r){
	cout << "? " << l << " " << r << endl; fflush(stdout);
} 

int main() {
	int n;
	cin >> n;
	
	int l = 1, r = n;
	int pos, p1;
	ques(l, r);
	cin >> pos;
	if(pos != l && pos != r) {
		ques(pos, r);
		cin >> p1;
		if(p1 == pos) {
			l = pos;
		}
		else {
			r = pos;
		}	
	}
	
	
	while(r - l >= 2) {
		int mid = l + r >> 1;
		if(mid > pos) {
			ques(pos, mid);
			cin >> p1;
			if(p1 == pos) {
				r = mid;
			}
			else {
				l = mid;
			}
		}else {
			ques(mid, pos);
			cin >> p1;
			if(p1 == pos) {
				l = mid;
			}
			else {
				r = mid;
			}
		}
	}
	
	
	if(l == r) {
		cout << "! " << l << endl;
		return 0; 
	}
	
	ques(l, r);
	cin >> p1;
	if(p1 == l) {
		cout << "! " << r << endl;
		fflush(stdout);
	}
	else {
		cout << "! " << l << endl;
		fflush(stdout);
	}
	
	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
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

D - Max Median

题意： 有一个长度为n的数列，现在要求你在所有长度$\ge k$的子数列中找能取到的最大的中位数，

刚开始乱猜贪长度就是k，然后我：有没有什么能logn左右实现插入删除找排位的数据结构，哦好耶，平衡树，直接找个板子往上套，喜提wa7，（后来发现不一定

找最大的xx，这不二分，（

就是判断条件确实有点难想：当判断是否能取到$\ge x$ 的中位数作为答案时，把所有$\ge x$ 的数变成1，$\le x$的数变成-1， 然后看是否能有一段长度大于k的区间的和为正

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int a[N], sum[N], n, k;

bool judge(int x) {
	int mn = 1e9;
	int mx = 0;
	for(int i = 1; i <= n; ++ i) {
		if(a[i] >= x) {
			sum[i] = 1;
		}
		else {
			sum[i] = -1;
		} 
		sum[i] += sum[i - 1];
	}
	
	for(int i = k; i <= n; ++ i) {
		mn = min(mn, sum[i - k]);
		mx = max(mx, sum[i] - mn);
	}
	
	if(mx > 0) return 1;
	return 0;

}

int main() {
//	int n;
	cin >> n >> k;
	for(int i = 1; i <= n; ++ i) {
		cin >> a[i]; 
	}
	int l = 1, r = n, ans = -1;
	while(l <= r) {
		int mid = l + r >> 1;
		if(judge(mid)){
			ans = mid;
			l = mid + 1;
		}
		else {
			r = mid - 1;
		} 
	}
	
	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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51