TCO19 SRM 751 Div1 解题记录

### Easy Hyperbox
题意：二维立方体的边界是一维的，可以计算长度。三维立方体的边界时两维的，可以计算表面积。四维立方体时三维的，可以计算表体积。给定四维立方体的表体积$V$，问有多少个边长都是正整数的，表体积为$V$的四维立方体。

题解：为什么$Div1$的画风就这样变了，变得扑朔迷离了$QAQ$……
好难过，$Easy$想了好久……
我们类比三维情况。
$S=2(ab+ac+bc)$
那么四维下有$8$个面，自然是：
$V=2(abc+abd+acd+bcd)$
等价于：
$$a(bc+bd+cd)=\frac{v}{2}-bcd$$
然后就不会做了
发现居然直接暴力枚举$b/c/d$的值就可以了？
设$(b,c,d,a)$是满足$b\le c\le d\le a$的四元组
我们粗略估计一下复杂度，大概是$O(n^{\frac{1}{4}}n^{\frac{1}{3}}n^{\frac{1}{2}})=O(n^{\frac{13}{12}})$的。怎么想也觉得过不了。但是就是过了，$2\times 10^8$的时候还跑的飞快。
服了
```
#include<cstdio>
using namespace std;
int S(int a, int b, int c, int d) {
	return 2 * (a * b * c + a * b * d + a * c * d + b * c * d);
}
class Hyperbox {
	public:
	int n, a, b, ans, tot;
	int count(int n) {
		if(n & 1) return 0;
		for(register int i = 1; S(i, i, i, i) <= n; ++i) {
			for(register int j = i; S(i, j, j, j) <= n; ++j) {
				for(register int k = j; S(i, j, k, k) <= n; ++k) {
					a = n / 2 - i * j * k;
					b = i * j + j * k + i * k;
					if(a % b == 0 && a / b >= k) ++ans;
				}
			}
		}
		return ans;
	}
};
```

### Medium WrongBase
题意：给你一个数列，在$(mod\ 998244353)$下是等差数列$a_i$，已知$g$，$g^{x_i}=a_i$
现在求$h^{x_i}$的和。$|a_i|\le 10^6$

题解：傻了，这种签到题都智障一般在分析性质……
实际上设$g^c=h$，那么把原来的等差数列每一项都变成$c$次幂就完了……$c$直接$BSGS$。
等差数列一点性质都没有，只是给你读入的……

### Hard AllInclusiveString
题意：求最短的满足字符集为$'a'$~$'p'$的字符串$s$，同时满足$n$个条件，形如：$t$在$s$中作为子序列出现。其中$|t|=2$。$n\le 256$

题解：考虑满足"xy"作为子序列存在的条件。显然是"x"第一次出现的位置在"y"最后一次出现的位置之前。
不妨大胆猜想，要满足长度最小，每个字母最多出现两次，总长最多$O(\alpha)$。
考虑三进制状压，对$16$个字母压$0/1/2$表示没放/放了第一个/放了第二个。$f(i,mask)$表示到第$i$个位置，$16$个字母的状态分别为$mask$，最多满足多少个条件。为了满足正确性，我们规定一个条件被满足一定是'y'放置了最后一个时前面有第一个'x'才算满足。注意，字母'x'只放一个的转移我们定为第一次/最后一次重在一起，转移为$0\to 2$。这样就可以了。加上预处理复杂度：$O(\alpha^2 3^n)$

~~做起了一个没那么水的$Hard$，高兴坏了$qwq$~~

Rockdu's Blog

导航

最近发表

大佬们的友链