T1 chip change

题目描述

奶牛 Bessie 手里有 A 个 A 类筹码，以及 B 个 B 类筹码（$0\le A,B\le 10^9$）。

她可以进行如下操作任意多次：

• 如果当前 至少有 $c_B$ 个 B 类筹码，就可以用 $c_B$ 个 B 类筹码 兑换 $c_A$ 个 A 类筹码。
  其中 $1\le c_A,c_B\le 10^9$。

现在问：最小的非负整数 $x$ 是多少，使得满足下面的“保证”条件：

在 Bessie 额外收到 $x$ 个随机筹码之后（每个筹码可能是 A 类或 B 类，分配方式未知），无论这 $x$ 个筹码具体怎么分配成 A/B，Bessie 都一定能通过若干次兑换操作，使得最终拥有的 A 类筹码数量 至少为 $f_A$（$0\le f_A\le 10^9$）。

你需要对每个测试用例输出这个最小的 $x$。

输入格式

第一行是整数 $T$，表示测试用例个数（$1\le T\le 10^4$）。

接下来 $T$ 行，每行包含 5 个整数：

$$A,\ B,\ c_A,\ c_B,\ f_A$$

---

输出格式

对每个测试用例输出一行一个整数：对应的答案 $x$。

注意：数据范围很大，可能需要 64 位整数类型（例如 C/C++ 的 long long）。

样例

样例输入1:

2
2 3 1 1 6
2 3 1 1 4

样例输出1:

1
0

样例输入1:

5
0 0 2 3 5
0 1 2 3 5
1 0 2 3 5
10 10 2 3 5
0 0 1 1000000000 1000000000

样例输出2:

9
8
7
0
1000000000000000000

并解释（原文意思）：

• 第 1 组（$A=B=0,c_A=2,c_B=3,f_A=5$）：
  Bessie 一开始没有筹码。只要她额外收到任意 9 个筹码，不管这 9 个里 A/B 怎么分配，她都能通过兑换最终得到至少 5 个 A。
  比如她收到 2 个 A 和 7 个 B，可以兑换两次得到 6 个 A（$\ge 5$）。
  但如果只收到 8 个 B，则最多兑换 2 次得到 4 个 A（<5），所以 8 不够。

• 第 4 组：她一开始就已经有足够多的 A，因此答案是 0。

评分提示

• 输入 3：$c_A=c_B=1$
• 输入 4-5：所有用例的 $x\le 10$
• 输入 6-7：$c_A=2, c_B=3$
• 输入 8-12：无额外限制

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128; 

ll a, b, ca, cb, fa;


i128 cal(ll y, ll tot) {
	return (i128)tot - y + ((i128)y / cb) * ca;
}

bool chk(ll x) {
	ll tot = a + b + x;
	ll lim = b + x;
	
	i128 mn = cal(lim, tot);
	
	ll tg = cb - 1; 
	
	if (ca > cb) {
		
		ll r = b % cb;
		ll d = (tg - r + cb) % cb;
		ll y = b + d;
		if (y <= lim) mn = min(mn, cal(y, tot));
	} else {
		
		ll r = lim % cb;
		ll d = (r - tg + cb) % cb;
		ll y = lim - d;
		if (y >= b) mn = min(mn, cal(y, tot));
	}
	
	return mn >= fa;
}

void sol() {
	cin >> a >> b >> ca >> cb >> fa;
	ll l = 0, r = 2e18, ans = 2e18;
	
	while (l <= r) {
		ll md = l + (r - l) / 2;
		if (chk(md)) {
			ans = md;
			r = md - 1;
		} else {
			l = md + 1;
		}
	}
	cout << ans << "\n";
}

int main() {
	ios::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0);
	
	int t;
	cin >> t;
	while (t--) {
		sol();
	}
	return 0;
}

T2 COW

题目描述

Bessie 得到一个正整数 $N$ 和一个长度为 $3N$ 的字符串 $S$。

字符串 $S$ 的生成方式如下：把 $N$ 个长度为 3 的字符串拼接起来，而每个长度为 3 的字符串都是 "COW" 的一个循环移位（cyclic shift），也就是说每段只能是下面三种之一：

• "COW"
• "OWC"
• "WCO"

平方串（square string）

字符串 $X$ 被称为 平方串，当且仅当存在某个字符串 $Y$，使得：

$$X = Y + Y$$

其中 $+$ 表示字符串拼接。 例如：

• "COWCOW"、"CC" 是平方串（分别对应 $Y="COW"$、$Y="C"$）

• "COWO"、"OC" 不是平方串

操作

一次操作中，Bessie 可以从 $S$ 中删除任意一个子序列 $T$，要求 $T$ 是一个平方串。

子序列指：从原串中删除若干个字符（可以删除 0 个），保持剩余字符的相对顺序得到的字符串。

目标

你需要判断：是否可以通过若干次操作，把 $S$ 变成空串。

如果可以，还要输出一种删除方案。

参数 $k$ 与操作次数要求

题目还给一个参数 $k\in\{0,1\}$。

设你输出的方案使用了 $M$ 次操作。

• 若 $k=0$：必须保证 $M$ 等于最少可能操作次数（最优）。
• 若 $k=1$：允许 $M$ 最多为 最少操作次数 + 1（几乎最优，多一次也行）。

输入格式

第一行包含两个整数：

• $T$：测试组数（$1\le T\le 10^4$）
• $k$：参数（$0\le k\le 1$）

每个测试用例包含：

1. 一行整数 $N$（$1\le N\le 10^5$）
2. 一行字符串 $S$，长度为 $3N$

保证所有测试中 $N$ 的总和不超过 $10^5$。

输出格式

对每个测试用例，按如下方式输出：

• 如果无法把 $S$ 变成空串：输出一行 -1

• 否则：

  • 第一行输出 $M$：你的方案操作次数

  • 第二行输出 $3N$ 个整数，用空格分隔
    第 $i$ 个整数 $x_i$ 表示：原串 $S$ 的第 $i$ 个字符是在第 $x_i$ 次操作中被删除的（要求 $1\le x_i\le M$）

样例

样例输入1

3 1
3
COWOWCWCO
4
WCOCOWWCOCOW
6
COWCOWOWCOWCOWCOWC

样例输出1

-1
1
1 1 1 1 1 1 1 1 1 1 1 1
3
3 3 2 3 3 2 1 1 1 1 1 1 1 1 1 1 1 1

样例解释1

对于最后一个测试用例，最优（最少）操作次数是 2，因此当 $k=1$ 时，只要你的构造满足 $M=2$ 或 $M=3$ 都会被判正确（允许比最优多 1 次）。

如果取 $M=3$，下面给出一种可行方案：

1. 第一次操作：删除最后 12 个字符。此时剩下字符串为 COWCOW。

2. 第二次操作：删除子序列 WW。此时剩下字符串为 COCO。

3. 第三次操作：删除所有剩余字符。最终变成空串。

样例输入2

3 0
3
COWOWCWCO
4
WCOCOWWCOCOW
6
COWCOWOWCOWCOWCOWC

样例输出2

-1
1
1 1 1 1 1 1 1 1 1 1 1 1
2
1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2

参考代码

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

int k;

bool chk1(const string& s){
	int h = (int)s.size() / 2;
	for(int i = 0; i < h; i++){
		if(s[i] != s[i + h]) return 0;
	}
	return 1;
}

string work(const string& s, int st, char c){
	char a = 0, b = 0;
	int t = 0;
	string r;
	for(int j = 0; j < 3; j++){
		char x = s[st + j];
		if(x == c) continue;
		if(t == 0) a = x;
		else b = x;
		t++;
	}
	r += a;
	r += b;
	return r;
}

char pickc(const string& s, int x1, int x2){
	string t = "COW";
	for(char c : t){
		if(work(s, x1, c) == work(s, x2, c)) return c;
	}
	return 'C';
}

void sol(){
	int n;
	cin >> n;	
	string s;
	cin >> s;
	
	if(n & 1){
		cout << -1 << "\n";
		return;
	}
	
	int m = 3 * n;
	
	if(chk1(s)){
		cout << 1 << "\n";
		for(int i = 0; i < m; i++){
			cout << 1 << (i + 1 == m ? '\n' : ' ');
		}
		return;
	}
	
	cout << 2 << "\n";
	
	int h = n / 2;
	vector<int> ans(m, 2);
	
	for(int i = 0; i < h; i++){
		int x1 = 3 * i;
		int x2 = 3 * (i + h);
		
		char c = pickc(s, x1, x2);
		
		for(int j = 0; j < 3; j++){
			ans[x1 + j] = (s[x1 + j] == c ? 1 : 2);
			ans[x2 + j] = (s[x2 + j] == c ? 1 : 2);
		}
	}
	
	for(int i = 0; i < m; i++){
		cout << ans[i] << (i + 1 == m ? '\n' : ' ');
	}
}

int main(){
	ios::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0);
	
	int t;
	cin >> t >> k;
	while(t--) 
	{
		sol();
	}
	
	return 0;
}

T3 photo

题目描述

农夫 John 在一块“魔法草地”里看牛，想给牛群的某些子集拍照。

这块草地可以看成一个 $N \times N$ 的网格（$1 \le N \le 500$），每个格子上都有一头固定不动的牛。

农夫的相机可以拍摄草地中任意一个 $K \times K$ 的正方形区域（必须完全在草地内），其中$1 \le K \le \min(N,25)$

美丽值与吸引力

每头牛都有一个“美丽值”（beauty），范围在 $0 \sim 10^6$。

一张照片的“吸引力指数”（attractiveness index）定义为：

照片中所有牛的美丽值之和（也就是该 $K \times K$ 方块内的总和）

开始时每头牛的美丽值都是 0，所以任何照片的吸引力指数一开始都为 0。

更新操作

接下来会发生 $Q$ 次变化（$1 \le Q \le 3\times 10^4$）：

每次变化会指定一个格子 $(r,c)$，该位置的牛因为吃草，美丽值会增加到一个更大的新值（题目输入给的是新值，不是增量）：

• 输入：$r, c, v$
  表示第 $r$ 行第 $c$ 列的美丽值被更新为 $v$
• 保证：新的 $v$ 严格大于该位置之前的美丽值

在每一次更新之后，农夫想知道：

此时任意一个 $K \times K$ 照片中，吸引力指数的最大值是多少

也就是：更新后，所有可能的 $K \times K$ 方块求和，输出其中最大那个和。

输入格式

• 第一行：$N, K$
• 第二行：$Q$
• 接下来 $Q$ 行：每行 $r, c, v$ 其中 $1 \le r,c \le N$，$1 \le v \le 10^6$。

输出格式

输出 $Q$ 行：第 $i$ 行是第 $i$ 次更新后，最大吸引力指数（最大 $K \times K$ 区域和）。

样例

输入样例1:

4 2
3
2 2 11
3 4 3
3 1 100

输出样例1:

11
11
111

输入样例2:

3 1
3
2 2 3
2 2 5
2 2 7

输出样例2:

3
5
7

参考代码

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

int a[505][505];
ll sm[505][505];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n, k;
	cin >> n >> k;
	
	int q;
	cin >> q;
	
	
	int m = n - k + 1;
	
	ll mx = 0;
	
	while (q--) {
		int r, c, v;
		cin >> r >> c >> v;
		
		int od = a[r][c];
		int d = v - od;
		a[r][c] = v;
		
		int x1 = max(1, r - k + 1);
		int x2 = min(r, m);
		int y1 = max(1, c - k + 1);
		int y2 = min(c, m);
		
		for (int i = x1; i <= x2; i++) {
			for (int j = y1; j <= y2; j++) {
				sm[i][j] += d;
				if (sm[i][j] > mx) mx = sm[i][j];
			}
		}
		
		cout << mx << "\n";
	}
	
	return 0;
}