[数据结构与算法]Codeforces Round #760 (Div. 3)

E. Singers’ Tour
F. Reverse
G. Trader Problem

?推推式子就行了。

int a[N];
int main() 
{
	int t;
	scanf("%d", &t);
	while(t --)
	{
		int n;
		LL sum = 0;
		scanf("%d", &n);
		for(int i = 1;i <= n;i ++) scanf("%d", a+i), sum += a[i];
		a[0] = a[n];
		if(sum%(n*(n+1)/2))
		{
			puts("NO");
			continue;
		}
		sum /= n*(n+1)/2;
		for(int i = n;i >=1;i --)
		{
			if((sum-a[i]+a[i-1])%n || sum-a[i]+a[i-1]<=0)
			{
				puts("NO");a[1] = 0;break;
			}
			a[i] = (sum-a[i]+a[i-1])/n;
		} 
		if(a[1])
		{
			puts("YES");
			for(int i = 1;i <= n;i ++)cout<<a[i]<<' ';
			cout<<endl;
		}
	}
	return 0;
}

?爆搜， 写的很烦。

LL x, y;
string a, b;
map<string, bool>ma;
bool flag  = 0;
string fan(string c) // 取反 
{
	string a = c;
	while(a.back() == '0') a.pop_back();
	reverse(a.begin(), a.end());
	return a;
}
 
void inverse(LL x, string &a)  // 转换成二进制字符串 
{
	while(x)a += (char)('0'+(x&1)), x>>=1;
	reverse(a.begin(), a.end());
	return ;
}

void dfs(string a)
{
	if((a.size() > b.size() && a.back() == '1') || ma[a]) return ; 
	if(a.size() == b.size())  flag |= a == b|fan(a) == b;
	ma[a] = 1;    
	if(a.back() == '0')
		dfs(fan(a+'1')), dfs(fan(a));
	else 
	{
		ma[fan(a)] = 1;
		dfs('1'+a); dfs(a+'1');
	}
	return ; 
}
 
int main()
{	
	scanf("%lld%lld", &x, &y);
	inverse(x, a); inverse(y, b);
	dfs(a);
	puts(flag ? "YES" : "NO");
    return 0;
}

?首先肯定要离线,然后还得把n+m个数排个序，那么就可以看作是一系列的连通块，连通块可以合并的条件是左边的最大值+k >= 右边的最小值，那么这就说明假设两个连通块内原本有a个数是n个数中的(a < n), 那么就可以从这两个连通块的范围内取最大的a个数。
?写起来也有点绕，原本想直接set，但是太难写了，然后就改成了优先队列，但发现优先队列不能删除，如果要标记的话就要每个连通块的范围，但这样又想到了可以直接模拟，就直接模拟了，代码有注释

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#define mid (l+r>>1)
#define lowbit(x) (x&-x)
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 2e6+10, mod = 998244353;
void mull(int &a, LL b){a = a*b%mod;return ;}
void add(int &a, LL b){a = (a+b)%mod;return ;}

pair<int,bool> a[N];  // a 存的是n+m个数 ，second代表的是 是否属于n个数中。 
PII Q[N], b[N];       // q 是离线化的询问，答案存在an[]中，b是每个连通块和右边相邻的连通块的差值。 
LL x[N], an[N];       // x[]和y[]是方便计算区间答案的前缀和，x[]是a[].first的前缀和，y[]是a[].second的前缀和。 
int y[N], l[N], r[N], idx = 1;  // l[],r[] 是连通块的做右端点. 

LL quary(int l, int r){return x[r]-x[r-y[r]+y[l-1]];}  // 计算l,r 的答案 y[r] - y[l-1] 是可以选择的数量
 
int main() 
{	
	int n, m, q;
	LL ans = 0;
	scanf("%d%d%d", &n, &m, &q);
	m += n;
	for(int i = 1;i <= m;i ++)
	{
		scanf("%d", &a[i].first);
		a[i].second = i <= n;
	}
	for(int i = 1;i <= q;i ++)
	{
		scanf("%d", &Q[i].first);
		Q[i].second = i;
	}
	sort(a+1, a+m+1); a[m+1] = {2e9+1, 0}; // 加个数方便最后不用判断是否变成了一个整体. 
	sort(Q+1, Q+q+1);
	for(int i = 1;i <= m;i ++)
	{
		x[i] = a[i].first + x[i-1];    // 前缀和 
		y[i] = a[i].second + y[i-1];   // 前缀和 
		b[i] = {a[i+1].first-a[i].first, i}; // 连通块的差值， 
		l[i] = r[i] = i;                     // 初始每个数都是一个连通块 
		ans += a[i].second ? a[i].first : 0 ;// 初始ans 
	}
	sort(b+1, b+m+1);    // 按照差值排序 

	for(int i = 1;i <= q;i ++)
	{
		int k = Q[i].first, id = Q[i].second;   
		while(b[idx].first <= k)
		{
			int R = b[idx].second, L = l[R], t = r[R+1];  // L,R是可合并的左边的连通块的左右端点，R+1,t 是可合并的右边连通块的左右端点。 
			ans -= quary(L, R) + quary(R+1, t) - quary(L, t);  
			l[t] = L;  // 把这两个区间和并. 
			r[L] = t;
			++ idx;
		}
		an[id] = ans;
	}
//  不至于吧，差了500多ms。
	for(int i = 1;i <= q;i ++) cout<<an[i]<<endl; 
    for(int i = 1;i <= q;i ++) printf("%lld\n", an[i]);
	return 0;
}