比赛链接：Contests

A.put

原题链接：Problems

简单的贪心，直接切了。10点58分榜上的rank1大佬写了个dp，但我研究了一下，那个dp也只是把贪心的过程记录在了dp数组中。

那么直接上代码吧！

正解：

#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
long long n;
struct node{
	long long p, h;
}a[N];
bool cmp(node x, node y){
	return x.p < y.p;
}
int read(){
	char c = getchar();
	long long x = 0, f = 1;
	while (c < '0' || c > '9'){
		if (c == '-')
			f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9'){
		x = x * 10 + (c - '0');
		c = getchar();
	}
	return x * f;
}
int main(){
	n = read();
	for (int i = 1; i <= n; i++){
        a[i].p = read();
        a[i].h = read();
	}
	sort(a + 1, a + n + 1, cmp);
	long long ans = 2;
	for (int i = 2; i < n; i++){
		int lst = a[i - 1].p;
		int nxt = a[i + 1].p;
		if (a[i].p - a[i].h > lst){
			ans++;
			continue;
		}
		if (a[i].p + a[i].h < nxt){
			ans++;
			a[i].p += a[i].h;
		}
	}
	printf("%d", ans);
}

常数很大吗？机房普遍都在100ms以内，我跑了131ms/(ㄒoㄒ)/~~

B.match

原题链接：Problems

错误分析：乱打暴力，写了,其实思考一下就可以优化到

思路分析：相当于把A数组进行滑动，而前面的是已经存在的，只改变一个位置就可以了。

正解：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 2e5 + 10;
ll n, m, q, p;
ll a[N], o[N], mx[N], ans[N];
struct node{
	ll num, w;
}b[N];
bool cmp(node q, node p){
	return q.num < p.num;
}
long long read(){
	char c = getchar();
	long long x = 0, f = 1;
	while (c < '0' || c > '9'){
		if (c == '-')
			f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9'){
		x = x * 10 + (c - '0');
		c = getchar();
	}
	return x * f;
}
int main(){    
	n = read();
	n++;
	for (ll i = 1; i <= n; i++){
		b[i].num = read();
		b[i].w = i;
	}
	for (ll i = 1; i < n; i++){
		a[i] = read();
	}
	sort(a + 1, a + n);
	sort(b + 1, b + 1 + n, cmp);
	for (ll i = n; i >= 2; i--){
		o[i] = max(o[i + 1], b[i].num - a[i - 1]);
	}
	ans[b[1].w] = o[2];
	for (ll i = 2; i <= n; i++){
		mx[i] = max(b[i - 1].num - a[i - 1], mx[i - 1]);
		ans[b[i].w] = max(mx[i], o[i + 1]);
	}
	for (ll i = 1; i <= n; i++){
		printf("%lld ", ans[i]);
	}
	return 0;
}

膜拜呱呱！

C.div

显然我只会，但要求.

传言是根号分治的板子，机房AeeE5x这么强吗？

那么，直接上正解吧！！！

#include<bits/stdc++.h>
#define int long long
using namespace std;
int prexor(int n){
	if(n == 2) 
		return 3;
	if(n % 2 == 1) 
		return ((n + 1) >> 1) % 2;
	else 
		return n + ((n >> 1) % 2);
}
void solve(int n){
	int ans = 0;
	int nowfactor = 1;
	for ( ; nowfactor <= n; nowfactor++){
		if ((n / nowfactor) % 2 == 1) 
			ans ^= nowfactor;
		else
			ans ^= 0;
		if (nowfactor > sqrt(n) && (n / nowfactor != n / (nowfactor + 1))) 
			break; 
	}
	nowfactor++;
	int maxdiv = n / nowfactor;
	for (int nowdiv = 1; nowdiv <= maxdiv; nowdiv += 2){
		int minfac = (n / (nowdiv + 1)) + 1;
		int maxfac = (n / nowdiv);
		ans ^= prexor(maxfac) ^ prexor(minfac - 1);
	}
	cout << ans << "\n";
}
int n;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	freopen("div.in", "r", stdin);
	freopen("div.out", "w", stdout);
	cin >> n;
	solve(n);
	return 0;
}

严肃学习根号分治……