Codeforces Round #760 (Div. 3)

比赛的时候做了 $\mathrm{A,B,C,D,G}$.     

A. Polycarp and Sums of Subsequences

标签：模拟  

仔细观察发现 $\mathrm{b[1], b[2]}$ 恰好对应 $\mathrm{a[1], a[2]}$, 然后 $\mathrm{a[3]}$ 就是第 3 项或第 4 项.  

由于问题保证有解，所以只需判断一下是否是第三项即可.   

#include  
#define ll long long
#define pb push_back  
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std; 
int a[10], b[10]; 
vectorg; 
int check(int x, int y, int z) {
	g.clear();  
	g.pb(x); 
	g.pb(y); 
	g.pb(z); 
	g.pb(x + y); 
	g.pb(x + z); 
	g.pb(y + z); 
	g.pb(x + y + z); 
	sort(g.begin(), g.end()); 
	for(int i = 1; i <= 7; ++ i) {
		if(a[i] != g[i - 1]) return 0; 
	}
	return 1;  
}
void solve() {
	int n = 7; 
	for(int i = 1; i <= n ; ++ i) {
		scanf("%d", &a[i]); 
	}
	//b[1] = a[1], b[2] = a[2];  
	if(check(a[1], a[2], a[3])) {
		printf("%d %d %d\n", a[1], a[2], a[3]); 
	}
	else {
		printf("%d %d %d\n", a[1], a[2], a[4]); 
	}

}
int main() {
	// setIO("input"); 
	int T; 
	scanf("%d", &T); 
	while(T-- ) solve(); 
	return 0; 
}

B. Missing Bigram

标签：模拟  

如果可以直接输出的话就在末尾随便加一个字符.  

否则可以在不合法的位置选择输出两个字符，其余位置输出一个即可. 

#include  
#define ll long long 
#define N  2009 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std; 
char str[N][2]; 
void solve() {
	int n ; 
	scanf("%d", &n); 
	for(int i = 1; i <= n - 2; ++ i) {
		scanf("%s", str[i]); 
	}
	printf("%c%c", str[1][0], str[1][1]); 
	int flag = 0; 
	for(int i = 2; i <= n - 2; ++ i) {
		if(str[i - 1][1] != str[i][0]) {
			flag = 1; 
			printf("%c%c", str[i][0], str[i][1]); 
		}
		else {
			printf("%c", str[i][1]); 
		}
	}
	if(!flag) printf("%c", 'a');  
	printf("\n"); 
}
int main() {
	// setIO("input");
	int T; 
	scanf("%d", &T); 
	while(T -- ) solve();  
	return 0;
}

C. Paint the Array

标签：$\mathrm{gcd}$ 相关.  

可以枚举是奇数下标还是偶数下标可以被钦定的 $\mathrm{d}$ 整除.  

那么显然这个 $\mathrm{d}$ 必须是所有数字的 $\mathrm{gcd}$.   

然后显然对于不能被 $\mathrm{d}$ 整除的位置条件应该苛刻，所以直接取 $\mathrm{d}$ 作为答案即可. 

#include 
#define N  104
#define ll long long  
#define pb push_back 
#define setIO(s) freopen(s".in","r",stdin)  
using namespace std;
ll a[N]; 
int n ;
vectorg[2];
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y ) : x;  
}   
ll lcm(ll x, ll y) {
	return x / gcd(x, y) * y;   
}
ll sol(int o) {
	if(!g[o].size()) return 0;   
	ll gc = g[o][0];  
	for(int i = 0 ; i < g[o].size() ; ++ i) {
		gc = gcd(gc, g[o][i]);
	}  
	for(int i = 0; i < g[o ^ 1].size() ; ++ i) {
		if(g[o ^ 1][i] % gc == 0) return 0; 
	}
	return gc;  
}
void solve() {
	scanf("%d", &n); 
	g[0].clear(); 
	g[1].clear(); 
	for(int i = 1; i <= n ; ++ i) {
		scanf("%lld", &a[i]);
		g[i % 2].pb(a[i]); 
	}
	// d comes from g[0]  
	ll p = max(sol(0), sol(1));
	printf("%lld\n", p);   
}
int main() {
	//setIO("input");
	int T; 
	scanf("%d", &T); 
	while(T -- ) solve(); 
	return 0; 
}

D.  Array and Operations

标签：贪心，众数

贪心选择将最大的 $\mathrm{2K}$ 个数字操作掉.  

那么操作这些数字的时候贡献要么是 $\mathrm{0}$ 要么是 $1$.  

只需把众数的个数拿出来，然后讨论一下是否会出现 $1$ 的情况即可. 

#include 
#define N  1004 
#define setIO(s) freopen(s".in","r",stdin)  
using namespace std; 
int n , a[N], bu[200009], K; 
bool cmp(int i, int j) { return i > j; }
void solve() {
	scanf("%d%d", &n, &K);   
	for(int i = 1; i <= n ;++ i) {
		scanf("%d", &a[i]); 
		//bu[a[i]] ++ ;  
	}  
	sort(a + 1, a + 1 + n, cmp); 
	for(int i = 1; i <= 2 * K ; ++ i) {
		bu[a[i]] ++ ; 
	}
	int sum = 0; 
	for(int i = 2 * K + 1; i <= n ; ++ i) sum += a[i]; 
	int mx = 0; 
	for(int i = 1; i <= 2 * K ; ++ i) mx = max(mx, bu[a[i]]); 
	if(mx > K) {
		int c1 = mx, c2 = 2 * K - mx;   
		sum += (c1 - c2) / 2;    
	} 
	for(int i = 1; i <= n ; ++ i) bu[a[i]] = 0; 
	printf("%d\n", sum); 
}
int main() {
	// setIO("input"); 
	int T; 
	scanf("%d", &T); 
	while(T--) solve(); 
	return 0; 
}

E. Singers' Tour 

标签：模拟，性质分析 

显然可以直接确定 $\mathrm{a[i]}$ 之和.  

然后可以考虑相邻的 $\mathrm{b[i]}$ 之间的不同，发现这个不同是 $\mathrm{\sum a + n \times a[i]}$.  

然后就能将 $\mathrm{a[i]}$ 解出来了，答案其实是唯一的. 

#include  
#define N  100009 
#define ll long long 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std; 
int n; 
ll b[N], a[N]; 
void solve() {
	scanf("%d", &n); 
	ll sum = 0; 
	for(int i = 1; i <= n ; ++ i) {
		scanf("%lld", &b[i]); 
		sum += b[i]; 
	}
	ll tot = 1ll * (n + 1) * n / 2; 
	if(sum % tot) {
		printf("NO\n"); 
		return ; 
	}
	// 
	// b[i] = b[i - 1] + sum(a[i]) - (n - 1)  * a[i];      
	ll pa = sum / tot;   
	// printf("%lld\n", pa); 
	for(int i = 1; i <= n ; ++ i) {
		int prev = (i - 2 + n) % n + 1;    
		ll det = (b[prev] - b[i] + pa);    
		// printf("%lld %lld %lld %lld\n",b[prev], b[i], det, pa);   
		if(det <= 0) {
			printf("NO\n"); 
			return ; 
		}
		if(det % n) {
			printf("NO\n"); 
			return ; 
		}
 
		a[i] = det / n; 
	}
	printf("YES\n"); 
	for(int i = 1; i <= n; ++ i) {
		printf("%lld ", a[i]); 
	}
	printf("\n"); 
	// exit(0); 
}
int main() {
	// setIO("input"); 
	int T; 
	scanf("%d", &T); 
	while(T -- ) solve(); 
	return 0; 
}

F. Reverse

标签：二进制，模拟 

不难发现加 0 的操作就是将二进制序列翻转，然后 + 1 的操作是 + 1 后翻转.  

由于每个数字最多会有 2 个分叉，所以直接暴力搜索用 $\mathrm{map}$ 记录一下即可. 

#include  
#define ll long long 
#define pb push_back 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std; 
int bu[103];      
mapvs;     
ll bin[103], X, Y;    
void init() {
	for(int i = 0; i < 64 ; ++ i) bin[i] = 1ll << i; 
}
ll rev(ll x) {
	int le = 0; 
	while(x) {
		bu[++ le] = x & 1;
		x >>= 1; 
	}
	ll tp = 0; 
	for(int i = 1; i <= le; ++ i) {
		tp += 1ll * bu[i] * bin[le - i];   
	}
	// printf("%lld qaq\n", tp); 
	// exit(0); 
	return tp;   
}
int get_len(ll x) {
	int le = 0; 
	while(x) {
		++ le;
		x >>= 1; 
	}
	return le;  
}

void dfs(ll x) {    
	// printf("%lld\n", x); 
	vs[x] = 1;  
	if(x == Y) {
		printf("YES\n"); 
		exit(0); 
	}
	ll tmp = rev(x);     
	ll t1 = rev(x * 2 + 1);  
	// printf("%lld %lld\n", tmp, t1);
	// printf("%d %d\n", get_len(t1), get_len(tmp));  
	if(!vs[t1] && get_len(t1) <= get_len(Y)) {
		dfs(t1);    
		// +1 后翻转.            
	}    
	if(!vs[tmp] && get_len(tmp) <= get_len(Y)) {
		dfs(tmp);  
	}
}
int main() {
	// setIO("input"); 
	init();    
	scanf("%lld%lld", &X, &Y);
	dfs(X);  
	printf("NO\n"); 
	return 0; 
}

G. Trader Problem

标签：并查集   

可以把所有数字放到一起排序，那么如果一个数字可以达到第一个比他大的数字就连边.   

然后数字序列就构成了若干个连通块，每一个连通块的贡献就是前 $\mathrm{num[i]}$ 大的数字和.  

这里 $\mathrm{num[i]}$ 代表这个连通块中包含初始数字的个数.   

这个模型可以将询问离线从小到大排序，然后挨个合并并查集即可. 

#include  
#define N  400009 
#define ll long long
#define pb push_back  
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;
int n, m, Q;  
struct Query  {
	int K, id;  
	Query(int K = 0, int id = 0):K(K), id(id) {}
}q[N]; 
bool cq(Query i, Query j) {
	return i.K < j.K; 
}
int num[N]; 
ll ans[N], sum[N], fin[N];  
struct Node {
	int x, id; 
	Node(int x = 0, int id = 0):x(x),id(id){}  
}A[N]; 
bool cmp(Node i, Node j) {
	return i.x < j.x; 
}     
struct DET {
	int pos, det;  
	DET(int pos = 0, int det = 0):pos(pos), det(det){}  
}arr[N];   
int fa[N]; 
int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]); 
}
bool DE(DET i, DET j)  { return i.det < j.det;   }   
ll ou[N]; 
int main() {
	// setIO("input"); 
	scanf("%d%d%d", &n, &m, &Q); 
	for(int i = 1; i <= n ; ++ i) {
		scanf("%d", &A[i].x); 
		A[i].id = 1; 
	}
	for(int i = 1; i <= m ; ++ i) {
		scanf("%d", &A[i + n].x); 
		A[i + n].id = 0; 
	}  
	int tot = n + m; 
	ll ans = 0; 
	sort(A + 1, A + 1 + tot, cmp); 
	for(int i = 1; i <= tot; ++ i) {
		sum[i] = sum[i - 1] + A[i].x;  
		if(A[i].id) ans += A[i].x; 
	} 
	// printf("%lld\n", ans); 
	for(int i = 1; i <= tot; ++ i) {
		fa[i] = i;  
		if(A[i].id == 1) num[i] = 1, fin[i] = A[i].x;   
	}
	for(int i = 1; i < tot; ++ i) {
		int de = A[i + 1].x - A[i].x;                 
		arr[i] = DET(i, de);    
	}
	sort(arr + 1, arr + tot, DE);   
	for(int i = 1; i <= Q; ++ i) {
		int kth; 
		scanf("%d", &kth); 
		q[i] = Query(kth, i); 
	}
	sort(q + 1, q + 1 + Q, cq); 
	for(int i = 1, j = 1; i <= Q; ++ i) {
		for(; j <= (tot - 1) && arr[j].det <= q[i].K; ++ j) {
			int p = arr[j].pos;     
			int ori = sum[p];  
			fa[p] = p + 1;  
			int now = find(fa[p]);  
			num[now] += num[p];  
			ans -= fin[p]; 
			ans -= fin[now]; 
			fin[now] = sum[now] - sum[now - num[now]];  
			ans += fin[now];    
		}
		ou[q[i].id] = ans; 
	}
	for(int i = 1; i <= Q; ++ i) {
		printf("%lld\n", ou[i]); 
	}
	return 0; 
}