2024.8.28 - 洛谷保存站

预计 100 + 100 + 100 + 100 = 400，实际 100 + 100 + 100 + 100 = 400

比赛复盘：

四道题看了一眼都会，然后分别写完了，由于第一题需要高精度，怕错拍了一个小时，见没拍出来就不管了。第三题需要 __int128，因为编译器太低级不能用，所以先用 long long 调试过的样例提交时再换成的 __int128

做的好的地方：AK 了

做的不好的地方：无

试题分析：

T1 dp，高精度

很显然的 dp，只不过数据范围较大，所以需要高精度

代码：

```cpp
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e6 + 10;

struct gaojing {
	int a[105], len;
	gaojing () {
	    len = 1;
	    memset(a, 0, sizeof(a));
	}
	gaojing operator + (const int b) const {
		gaojing c;
		c.a[1] += b;
		for (int i = 1; i <= len; ++ i ) {
			c.a[i] += a[i];
			if (c.a[i] > 9) {
				c.a[i] %= 10;
				++ c.a[i + 1];
			}
		} 
		if (c.a[len + 1]) c.len = len + 1;
		else c.len = len;
		return c;
	}
	gaojing operator * (const int b) const {
		gaojing c;
		for (int i = 1; i <= len; ++ i ) {
			c.a[i] += a[i] * b;
			if (c.a[i] > 9) {
				c.a[i + 1] += c.a[i] / 10;
				c.a[i] %= 10;
			}
		}
		c.len = 100;
	    while (!c.a[c.len] && c.len > 1) -- c.len;
		return c;
	}
	gaojing operator * (const gaojing b) const {
		gaojing c;
		for (int i = 1; i <= len; ++ i )
	        for (int j = 1; j <= b.len; ++ j )
	            c.a[i + j - 1] += a[i] * b.a[j];
	            
	    for (int i = 1; i <= 100; ++ i ) c.a[i + 1] += c.a[i] / 10, c.a[i] %= 10;
	    c.len = 100;
	    while (!c.a[c.len] && c.len > 1) -- c.len;
	    return c;
	}
    bool operator < (const gaojing b) const {
    	if (len != b.len) return len < b.len;
		for (int i = len; i >= 1; -- i ) {
			if (a[i] < b.a[i]) return true;
			if (a[i] > b.a[i]) return false;
		} 
		return false;
	}
	void output () {
		for (int i = len; i >= 1; -- i ) cout << a[i];
		cout << endl;
	}
};

gaojing f[45][45];

bool is[45][45];

int n, k;

char s[N];

gaojing dfs (int i, int j) { 
	if (i > n) {
		gaojing x;
		if (j == k + 1) {
			x.a[1] = 1;
		}
		return x;
	}
	if (is[i][j]) return f[i][j];
	is[i][j] = true;
	gaojing ans, sum;
	for (int t = i; t <= n; ++ t ) {
		sum = sum * 10 + (s[t] - '0');
		if (ans < sum * dfs (t + 1, j + 1)) ans = sum * dfs (t + 1, j + 1);
	}
	return f[i][j] = ans;
}

signed main() {
    scanf("%lld%lld%s", &n, &k, s + 1);
    ++ k;
    gaojing ans = dfs (1, 1);
    for (int i = ans.len; i >= 1; -- i ) printf("%lld", ans.a[i]);
	return 0;
}
```

T2 拓扑排序，数学

将给定的 DAG 拓扑排序，然后将前 m 个点加上一，然后向下传递水量，分数运算即可。

```cpp
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e5 + 10;

int n, m, d[N], b[N], cnt, dd[N];

void writen (__int128 x) {
	char tmp[44];
	int cnt = 0;
	if (!x) putchar('0');
	else {
		while (x) {
			tmp[ ++ cnt] = x % 10;
			x /= 10;
		}
		for (int i = cnt; i >= 1; -- i ) putchar(tmp[i] + '0');
	}
	return;
}

__int128 p[N], q[N];

vector <int> g[N];

signed main() {
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; ++ i ) {
    	scanf("%lld", d + i);
    	for (int j = 1; j <= d[i]; ++ j ) {
    		int v;
    		scanf("%lld", &v);
    		g[i].push_back(v);
    		++ dd[v];
		}
	}
	for (int i = 1; i <= n; ++ i ) q[i] = 1;
	queue <int> q; 
	for (int i = 1; i <= m; ++ i ) p[i] = 1, b[ ++ cnt] = i, q.push(i);
	while (q.size()) {
		int u = q.front();
		q.pop();
		for (int v : g[u]) {
			-- dd[v];
			if (!dd[v]) {
				q.push(v);
				b[ ++ cnt] = v;
			}
		}
	}
	for (int j = 1; j <= n; ++ j ) {
		int i = b[j];
		if (!d[i]) continue;
		__int128 x = p[i], y = ::q[i] * d[i];
		__int128 t = __gcd(x, y);
		x /= t;
		y /= t;
		for (int v : g[i]) {
			::q[v] *= y;
			p[v] *= y;
			p[v] += x * (::q[v] / y);
			t = __gcd(p[v], ::q[v]);
			p[v] /= t;
			::q[v] /= t;
		}
	}
	for (int i = 1; i <= n; ++ i ) {
		if (!d[i]) {
			writen(p[i]), putchar(' '), writen(::q[i]);
			putchar('\n');
		}
	}
	return 0;
}
```

T3 数学

在 $10^{18}$ 次方的数据范围下，一个正数的三次方小于 $n$，则这个数一定小于 1e6，其他更大指数的范围更小，所以特判平方数，其他的暴力计算，用 set 去重即可

```cpp
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e6 + 10;

int n, k;

__int128 ksm (__int128 a, int n) {
	__int128 ans = 1;
	while (n) {
		if (n & 1) ans = ans * a;
		a = a * a;
		n >>= 1; 
	}
	return ans;
}

signed main() {
    scanf("%lld%lld", &n, &k);
    if (k == 1) printf("%lld\n", n);
    else if (k == 2) {
    	int l = 1, r = 1e9, ans = 0;
    	while (l <= r) {
    		int mid = (l + r) >> 1;
    		if (mid * mid <= n) {
    			ans = mid;
    			l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		set <int> s;
		for (int i = 3; i <= 62; ++ i ) {
			for (int j = 1; ksm (j, i) <= n; ++ j ) {
			    int x = ksm (j, i);
			    int p = sqrt(x);
			    if (p * p == x || (p - 1) * (p - 1) == x || (p + 1) * (p + 1) == x || (p + 2) * (p + 2) == x || (p - 2) * (p - 2) == x) {
			    	continue;
				}
				s.insert(x);
			}
		}
		printf("%lld\n", (int)s.size() + ans);
	} else {
		set <int> s;
		for (int i = k; i <= 62; ++ i ) {
			for (int j = 1; ksm (j, i) <= n; ++ j ) {
			    int x = ksm (j, i);
				s.insert(x);
			}
		}
		printf("%lld\n", (int)s.size());
	}
	return 0;
}
```

T4 前缀和

维护每个点向后延伸的 0 长度和向下延伸的 0 长度，维护每个位置左上转角的个数，然后用前缀和统计即可

```cpp
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e6 + 10, mod = 998244353;

int T, id, n, m, c, f, h[1005][1005], x[1005][1005], b[1005][1005], s1[1005][1005], s2[1005][1005];

char s[1005][1005];

signed main() {
    scanf("%lld%lld", &T, &id);
    while (T -- ) {
    	scanf("%lld%lld%lld%lld", &n, &m, &c, &f);
    	for (int i = 1; i <= n; ++ i ) scanf("%s", s[i] + 1);
    	int ans1 = 0, ans2 = 0;
    	for (int i = 1; i <= n; ++ i ) {
    		int at = m + 1;
    		for (int j = m; j >= 1; -- j ) {
    			h[i][j] = at - j - 1;
    			if (s[i][j] == '1') at = j;
			}
			
		}
		for (int j = 1; j <= m; ++ j ) {
			int at = n + 1;
			for (int i = n; i >= 1; -- i ) {
				x[i][j] = at - i - 1;
				if (s[i][j] == '1') at = i;
			}
		}
		for (int j = 1; j <= m; ++ j ) {
			for (int i = 1; i <= n; ++ i ) {
				s1[i][j] = s1[i - 1][j] + h[i][j];
			}
		}
		for (int i = 1; i <= n; ++ i ) {
			for (int j = 1; j <= m; ++ j ) {
				b[i][j] = h[i][j] * x[i][j]; 
			}
		}
		for (int j = 1; j <= m; ++ j ) {
			for (int i = 1; i <= n; ++ i ) {
				s2[i][j] = s2[i - 1][j] + b[i][j];
			}
		}
		for (int i = 1; i <= n; ++ i ) {
			for (int j = 1; j <= m; ++ j ) {
				if (s[i][j] == '0' && h[i][j] >= 1 && x[i][j] >= 1) {
					ans1 = (ans1 + h[i][j] * (s1[i + x[i][j]][j] - s1[i + 1][j])) % mod;
					ans2 = (ans2 + h[i][j] * (s2[i + x[i][j]][j] - s2[i + 1][j])) % mod;	
				}
			}
		}
		ans1 = ans1 * c % mod;
		ans2 = ans2 * f % mod;
		printf("%lld %lld\n", ans1, ans2);
	}
	return 0;
}
```

正在渲染内容...