atcoder beginner 281 DEFG 题解

比赛链接：https://atcoder.jp/contests/abc281

题解：
D
\(dp[i][j][k]\) 表示考虑到第 i 个数，集合加入了 \(k\) 个数，余数为 \(j\) 的答案
转移即可

// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long LL;
#define int LL

const int inf = 1e9, INF = 0x3f3f3f3f;

int dp[105][105][105];	// dp[i][j][q] 模 k = j，选了 q 个的最大值 
int a[205],n,k,d;
int cmp(int a,int b){return a>b;}
void ck(int &a,int b){a = max(a, b);}
signed main(){
	memset(dp, -1, sizeof dp);
	scanf("%lld%lld%lld",&n,&k,&d);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	sort(a+1,a+n+1,cmp);
	dp[1][a[1] % d][1] = a[1];
	dp[1][0][0] = 0;
	for(int i=2;i<=n;i++){
		for(int j=0;j<d;j++){
			for(int m=1;m<=k;m++){
				if(~dp[i-1][j][m-1])
					ck(dp[i][(j+a[i])%d][m], dp[i-1][j][m-1] + a[i]);
				ck(dp[i][j][m], dp[i-1][j][m]);
			}
			ck(dp[i][j][0], dp[i-1][j][0]);
		}
	}
	printf("%lld\n",dp[n][0][k]);
	
	return 0;
}

E
滑动窗口升级版，用对顶堆维护。每次去掉开头元素的时候可以打一个懒标记，然后加入结尾元素的时候先扔到辅助堆里面，然后用辅助堆的top和答案堆的top比较
细节挺多

// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#include <queue>
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 2e5+5;

struct node{
	int id;
	LL val;
	node(){}
	node(int id,LL val):id(id),val(val){}
};
struct node2{
	int id;
	LL val;
	node2(){}
	node2(int id,LL val):id(id),val(val){}
};
bool operator < (node a,node b){return a.val < b.val;}
bool operator < (node2 a,node2 b){return a.val > b.val;}
struct node a[maxn];
struct node2 b[maxn];
priority_queue<node>pq;		// val 大到小（答案pq） 
priority_queue<node2>pq2;	// val 小到大 

int n,m,k;
int st[maxn];
int dead[maxn];

signed main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i].val);a[i].id = i;
		if(i <= m)b[i] = node2(a[i].id,a[i].val);
	}
	sort(b+1,b+m+1);reverse(b+1,b+m+1);
	
	LL sum = 0;
	for(int i=1;i<=k;i++)
		pq.push(node(b[i].id,b[i].val)),
		sum += b[i].val,
		st[b[i].id] = 1;
		
	for(int i=k+1;i<=m;i++){
		pq2.push(b[i]);
		st[b[i].id] = 2; 
	}
	printf("%lld ",sum);
	
	int capa = k;
	for(int i=m+1;i<=n;i++){
		// pop a[i]
		pq2.push(node2(a[i].id, a[i].val));
		st[a[i].id] = 2;
		dead[a[i-m].id] = 1;
		if(st[a[i-m].id] == 1)sum -= a[i-m].val, -- capa;
		
		while(!pq.empty()){
			node cur = pq.top();
			if(dead[cur.id]){
				pq.pop();
			}else break;
		}
		while(!pq2.empty()){
			node2 cur = pq2.top();
			if(dead[cur.id]){
				pq2.pop();
			}else break;
		}
		if(capa < k){
			node2 n2 = pq2.top();pq2.pop();
			pq.push(node(n2.id,n2.val));
			sum += n2.val;
			st[n2.id] = 1;
			++ capa;
		}else{
			if(pq.top().val > pq2.top().val){
				node n1 = pq.top();node2 n2 = pq2.top();
				pq.pop();pq2.pop();
				pq.push(node(n2.id,n2.val));pq2.push(node2(n1.id,n1.val));
				sum = sum - n1.val + n2.val;
				st[n2.id] = 1; st[n1.id] = 2;
			}
		}
			
		printf("%lld ",sum);
	}

	return 0;
}
//10 6 3
//12 2 17 11 19 8 4 3 6 20

F
从高到低枚举二进制位。如果当前位均为 1 或均为 0，那么显然都取反就可以了，否则，如果这一位取反就对应了当前位为 0 的哪些数，否则对应了为 1 的。
递归维护这个过程即可

// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f;

int n,a[200005];
int dfs(int x,vector<int>v){
	if(x == -1)return 0;
	vector<int>S,T;
	for(int u : v){
		if(u & (1<<x))S.push_back(u);
		else T.push_back(u);
	}
	if(S.size() == 0)return dfs(x-1, T);
	else if(T.size() == 0)return dfs(x-1, S);
	else return min(dfs(x-1, S), dfs(x-1, T)) | (1<<x);
}

signed main(){
	vector<int>v;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),v.push_back(a[i]);
	int ans = dfs(29, v);
	printf("%d\n",ans);

	return 0;
}

G
这个题挺有意思。考虑什么样的图符合条件
设 \(d_u\) 表示 1 到 \(u\) 的最短距离，\(u = 1 .. n-1\) 那么显然 \(d_1=1\)
如果该图符合条件，那么必然有：

• 如果存在 \((u,v) \in E\) ，那么 \(|d_u-d_v| \leq 1\) ，否则 \(|d_u-d_v| \geq 2\)

考虑构造这么个图

• 先把 \(d_u = \inf, u=2..n-1, m=1\)
• 选任意多 \(d_u = \inf\)，再选任意多 \(d_v=m-1\)，将\(u\)集合中的所有点和\(v\)中的点连边
• \(u\)中的所有点任意连边（可以不连）
• \(m\)加一
• 最后，选任意多 \(d_v=m-1\) 和 \(n\) 连边
  显然这就包含了所有的合法情况

考虑dp这个过程，注意到两个图不同当且仅当有一条边在一个图中有另一个图中没有，因此可以对边进行计数，这样我们就把图的问题转化为了序列问题

设 \(dp[i][j]\) 表示已经加入了 \(i\) 个点，\(m=j\) 时的方案数
考虑 \(dp[i][j] \rightarrow dp[i+k][k]\)
从 \(n-i-1\) 个点中挑 \(k\) 个 \(u\) ，\(C(n-i-1,k)\) ，挑 \(v\) 显然是 \(2^{j}-1\) 注意这些 \(v\) 都要和 \(u\) 连边，因此如果有 \(k\) 个 \(u\) 需要 \(k\)次方，然后 \(u\) 内部随意连是 \(2^{\frac{k(k-1)}{2}}\)

最后统计答案

// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f;

int n,mod;
int dp[505][505],C[505][505], p2[505], p22[505];

int pw(int x,int y){
	if(!y)return 1;
	if(y==1)return x;
	int mid=pw(x,y>>1);
	if(y&1)return 1ll*mid*mid%mod*x%mod;
	return 1ll*mid*mid%mod;
}

signed main(){
	scanf("%d%d",&n,&mod);
	C[0][0] = 1;
	for(int i=1;i<=500;i++){
		C[i][0] = 1;
		for(int j=1;j<=500;j++)
			C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;
	}
	
	p2[0] = 1;
	for(int i=1;i<=500;i++)p2[i] = 2ll*p2[i-1]%mod;
	for(int i=1;i<=500;i++)p22[i] = pw(2, i*(i-1)/2);
	
	dp[1][1] = 1;
	for(int i=1;i<=n-2;i++){
		for(int j=1;j<=i;j++)if(dp[i][j]){
			int coef = 1;
			for(int k=1;i+k<=n-1;k++){
				coef = 1ll*coef*(p2[j]-1)%mod;
				(dp[i+k][k] += 1ll*dp[i][j]*C[n-1-i][k]%mod*p22[k]%mod*coef%mod) %= mod;
			}
		}
	}
	
	int ans = 0;
	for(int i=1;i<=n-1;i++)
		(ans += 1ll*dp[n-1][i]*(p2[i]-1)%mod) %= mod;
	printf("%d\n",ans);

	return 0;
}