20zr提高组十连测day8

qwq重新整理啦

A. [2020提高组十连测day8]割韭菜

http://www.zhengruioi.com/contest/748/problem/1622

经典的技巧叫做行列无关

就是说我们每一行选多少每一列选多少本质上只有在拼起来的时候才会有影响

就是说我们能先选行再选列喽

那我们直接作出选前k次行的最大收益,前k次列的最大收益

然后计算一下因为行列重复覆盖而导致的收益减损即可

应该行数*列数个格子要少算


//你要意识到一个最基本的事情是:行列单独无关
//那么我们可以处理行操作某些次数最大收益
//列操作某些次数最大收益
//然后组合一下下qwq
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,int>
#define mkp(x,y) (make_pair(x,y))
#define se second
#define fi first
using namespace std;
const int MAXN = 1e3 + 7;
const int MAXK = 1e6 + 7;
priority_queue<pii> heap;
int n, m, k, v0;
int a[MAXN][MAXN];
ll f[MAXK], g[MAXK];

namespace fastIO {
#define BUF_SIZE (1<<20)
	static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x = 0;
		int f = 1;
		char s = nc();
		for(; !isdigit(s); s = nc())if(s == '-')f = -1;
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x * f;
	}
}
using namespace fastIO;

int main() {
	// freopen("test.in", "r", stdin);
	// freopen("test1.out", "w", stdout);
	n = read();
	m = read();
	k = read();
	v0 = read();
	if(k == 0) {
		return puts("0"), 0;
	}
	for(int i = 1; i <= n; ++i) {//一行二列
		for(int j = 1; j <= m; ++j) {
			a[i][j] = read();
		}
	}
	//行init
	for(int i = 1; i <= n; ++i) {
		ll S = 0;
		for(int j = 1; j <= m; ++j) {
			S += a[i][j];
		}
		heap.push(mkp(S, i));
	}
	//行k
	for(int i = 1; i <= k; ++i) {
		int u = heap.top().se;
		ll v = heap.top().fi;
		heap.pop();
		f[i] = f[i - 1] + v;
		heap.push(mkp(v - 1ll * v0 * m, u)); //会每一列都减少QAQ
	}
	while(!heap.empty())heap.pop();
	for(int i = 1; i <= m; ++i) {
		ll S = 0;
		for(int j = 1; j <= n; ++j) {
			S += a[j][i];
		}
		heap.push(mkp(S, i));
	}
	for(int i = 1; i <= k; ++i) {
		int u = heap.top().se;
		ll v = heap.top().fi;
		heap.pop();
		g[i] = g[i - 1] + v;
		heap.push(mkp(v - 1ll * v0 * n, u)); //每一列decQAQ
	}
	ll ans = -1e18;
	for(int i = 0; i <= k; ++i) {
		ans = max(ans, f[i] + g[k - i] + 1ll * i * (i - k) * v0);//可能爆llQAQ
	}
	printf("%lld\n", ans);
	return 0;
}

B. [2020提高组十连测day8]智勇大闯关

http://www.zhengruioi.com/contest/748/problem/1623

咱不知道为啥要把这个题放在B....

发现最优一定是每个人都停在一个位置上,因为x能到y(结果更优),那我们z也可以按照同样的方式从
x到y

这样就很简单了,可以二分人数...也可以发现随着人数的增多这个公共停下来的位置只能单调后移,所以说直接记录一下即可

这类结论题特容易fst,所以一定要拍拍拍


//你考虑尺取推进...
//就是说人数越多,我们只可能单调向前冲啊
//然后你会发现,一个人能否到达某个点之和这个人的位置到某点位置之间的前缀最小值有关...
//也就是说,A能到x点,那么B也一定能到达,因为过程和A到达一样,而结果一定是更优了/....
//所以说我们可以考虑每次多出一个人QAQ
//然后我们会发现这个推进过程可以直接做....
//好像就线性了........我直接服了啊
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 7;
int T, n;
char s[MAXN];

inline void solve() {
	int cnt = 0;
	int pos = 0;
	for(int i = 1; i <= n; ++i) {
		if(s[i] == '1')cnt++;
		else cnt--;
		pos = min(pos, cnt);
	}
	pos = -pos;
	int ans = 0;
	int ret = 0;
	int premax = 0;
	//先可怜一个人冲,然后挨个加人
	cnt = 0;
	for(int i = 1; i <= n; ++i) {
		if(s[i] == '1')cnt++;
		else cnt--;
		while(cnt + ret < 0) {
			ans++;
			ret += premax;
			if(ans > n) {
				printf("-1\n");
				return ;
			}
		}
		if(ret >= pos) {
			printf("%d\n", ans);
			return;
		}
		//转折...
		premax = max(premax, cnt);
		ret = max(ret, premax * ans);
	}
	return ;
}

int main() {
	scanf("%d", &T);
	while(T-- > 0) {
		scanf("%s", s + 1);
		n = strlen(s + 1);
		solve();
	}
	return 0;
}

C. [2020提高组十连测day8]剪刀石头布

http://www.zhengruioi.com/contest/748/problem/1624

其实也不难/xk

首先我们有暴力跳区间的做法,因为能统计出每个人最后成为胜者的方案数即可

而你会发现他成为左/右区间的方案数是一样的.....也就是说其实本质不同的只有这些人向上爬时哪些时候成为左边,哪些时候成为右边

所以说我们暴力这样做,正解也一样肯定能O(n)推出一下每个手势作为左右胜者概率...1/3(右边)或者2/3(左边)

然后这个次数好像等价于转换为2进制数后0的个数,一个0就是一个右边...证明,其实可以通过观察每个数的每个二进制位发现(线段树本质)

那么假如有k个我们就是 $w_i=3^{-n}2^k$

答案就是求解 $\sum_{l=1}^r 2^{k_i}$ , $(3^n)^{r-l+1}$ 直接提出

然后这个可以数位dp,直接记录卡没卡上界就好

最后的问题在于高精度十进制转二进制,这个可以转换成1e9进制再转换为 $2^32$ 进制

相当于 $n^2/9*32$ !




#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<assert.h>
using namespace std;
#define G getchar()
int read() {
	int x = 0; char ch = G;
	for (; !isdigit(ch); ch = G);
	for (; isdigit(ch); ch = G) x = (x << 3) + (x << 1) + (ch ^ 48);
	return x;
}
#undef G
typedef long long ll;
const int INF = 1e9, mod = 998244353, inv3 = (mod + 1) / 3;
inline int upd(int x) {
	return x + (x >> 31 & mod);
}
inline void add(int &x, int y) {
	x = upd(x + y - mod);
}
inline void iadd(int &x, int y) {
	x = upd(x - y);
}

int n;

int a[1 << 15], b[1 << 15];
int atot, btot;
int work() {
	int res = 0;
	for (int i = atot; i; i--) {
		ll t = (1LL * res * INF + a[i]);
		a[i] = t >> 30, res = t & 1073741823;
	}
	while (atot && !a[atot]) --atot;
	return res;
}
void bigint_minus() {
	int pos = 1;
	while (pos <= btot && !b[pos]) pos++;
	assert(pos <= btot);
	--b[pos];
	for (int i = 1; i < pos; i++) b[i] = 1073741823;
	while (btot && !b[btot]) --btot;
}
int f[100010];
int g[100010];
int solve() {
	f[0] = 3;
	for (int i = 1; i <= n; i++) f[i] = 1LL * f[i - 1] * f[i - 1] % mod;
	g[0] = 3;
	for (int i = 0, k = 1; i < n; i += 30, k++) {
		for (int j = 0; j < 30 && i + j < n; j++) {
			int id = i + j, v = b[k] >> j & 1;
			if (!v) g[id + 1] = g[id] * 2LL * inv3 % mod * f[id] % mod;
			else g[id + 1] = (2LL * inv3 * f[id] % mod * f[id] + 1LL * inv3 * f[id] % mod * g[id]) % mod;
		}
	}
	return g[n];
}


char s[1 << 15]; int len;
int ans;
int main() {
	n = read();

	scanf("%s", s); len = strlen(s);
	reverse(s, s + len);
	if (!(len == 1 && s[0] == '1')) {
		for (int i = 0; i < len; i += 9) {
			int x = 0;
			for (int j = min(len, i + 9) - 1; j >= i; j--) {
				int v = s[j] ^ 48;
				x = x * 10 + v;
			}
			a[++atot] = x;
		}
		while (atot) b[++btot] = work();
		bigint_minus(); bigint_minus();
		iadd(ans, solve());
	}
	memset(a, 0, sizeof a);
	memset(b, 0, sizeof b);

	scanf("%s", s); len = strlen(s);
	reverse(s, s + len);
	atot = 0;
	for (int i = 0; i < len; i += 9) {
		int x = 0;
		for (int j = min(len, i + 9) - 1; j >= i; j--) {
			int v = s[j] ^ 48;
			x = x * 10 + v;
		}
		a[++atot] = x;
	}
	btot = 0;
	while (atot) b[++btot] = work();
	bigint_minus();
	add(ans, solve());

	printf("%d\n", ans);
	return 0;
}

夏晓光(loveJY)的博客

ARC杂题选讲P2