Anticube
给定 \(n\) 个数 \(s_i\)，要求从中选出最多的数，满足任意两个数之积都不是完全立方数
对于一个数 \(x\) 进行唯一分解，把每个质因子的指数对 \(3\) 取模构造出数 \(a\)，再把 \(a\) 的每个质因子指数相反数对 \(3\) 取模得到 \(b\)，我们发现 \(a\) 和 \(b\) 是一一对应的，贪心取较大的那一个即可，特判 \(x\) 是完全平方数的情况
进行质因数分解时，可以筛到 \(10^{\frac{10}{3}}\)
以内的质数，对于分解后剩下的数，要么是一个质数的完全平方数，要么是质数，判断一下即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
using namespace std;
typedef long long int64;
inline int64 read(int f = 1, int64 x = 0, char ch = ' ')
{
while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
return f*x;
}
const int p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}, S = 127;
const int N = 1e5+5;
int64 qpow(int64 a, int64 b, int64 n)
{
int64 ret = 1;
for( ; b; b >>= 1, a = a*a%n) if(b&1) ret = a*ret%n;
return ret;
}
int64 gcd(int64 a, int64 b) { return b?gcd(b, a%b):a; }
bool miller_rabin(int64 n)
{
if(n == 1) return false;
for(int i = 0; i < 12; ++i) if(n%p[i] == 0) return n == p[i];
int64 r; int t;
for(r = n-1, t = 0; ~r&1; r >>= 1, ++t);
for(int i = 0; i < 12; ++i)
{
int64 x = qpow(p[i], r, n), xs;
for(int j = 1; j <= t; ++j)
{
xs = x*x%n;
if(xs == 1&&x != 1&&x != n-1) return false;
x = xs;
}
if(x != 1) return false;
}
return true;
}
vector<int64> pd;
int n, c[N], ans;
int64 a[N], b[N];
map<int64, int> h, vis;
int main()
{
n = read();
for(int i = 1; i <= 2200; ++i) if(miller_rabin(i)) pd.push_back(i);
for(int i = 1; i <= n; ++i)
{
int64 x = read(), t; a[i] = b[i] = 1;
for(int k = 0; k < pd.size(); ++k)
{
c[k] = 0; while(x%pd[k] == 0) ++c[k], x /= pd[k]; c[k] %= 3;
if(c[k] == 2) a[i] *= pd[k]*pd[k], b[i] *= pd[k];
else if(c[k] == 1) a[i] *= pd[k], b[i] *= pd[k]*pd[k];
}
t = sqrt(x);
if(t*t == x) a[i] *= t*t, b[i] *= t;
else a[i] *= x, b[i] *= x*x;
++h[a[i]];
}
for(int i = 1; i <= n; ++i)
{
if(vis[a[i]]||vis[b[i]]||a[i] == 1) continue;
vis[a[i]] = 1; ans += max(h[a[i]], h[b[i]]);
}
printf("%d\n", ans+(h[1] != 0));
return 0;
}
Sequential operations on Sequence
初始为 \(1\) 到 \(n\) 的数列，每次操作把数组长度变为\(m\)，新增的数为上一个操作后的数组的重复，问最终数出现的次数
首先，对最终答案有贡献的一定是单调递增的操作序列，用单调栈维护，其次这个问题的实质是要维护出每个操作对应的序列在最终答案的出现次数，便于处理每次操作后对于的那些部分，那么需要从最后一个序列倒推，中间递归维护即可，最后中间涉及的区间加的操作差分就好了
1 |
|
Fraction of Fractal
给定一个\(n\times m\)的黑白网格，保证黑格四连通且至少有一个黑格，求 \(k\) 级分形的四联通数量
首先，我们定义对于一个图形定义上下联通为上下对应的位置都为黑色，左右联通同理
那么若 \(1\) 级分形若左右联通和上下联通同时存在，答案一定为 \(1\)，若不是，我们只需要考虑一方面即可，以上下为例
当我们把 \(1\) 级分形当作节点，节点与节点之间若联通则有边，则建出的图是若干条链组成的森林，那么 \(k\) 级分形的联通块的个数即可用 \(v_k-e_k\) 快速计算，\(v_k\) 是点数，\(e_k\) 是边数，此外还有几个变量 \(f_k\) 为 \(k\) 级分形上下联通节点个数，\(c\) 为 \(1\) 级分形黑色方块个数，\(a\) 为 \(1\) 级分形上下都为黑色的分界线个数，\(b\) 为 \(1\) 级分形上下联通方块个数
所以我们有
\[ f_k\ =\ f_{k-1}\times b，\ v_k\ =\ v_{k-1}\times c\\\\ e_k\ =\ e_{k-1}\times c\ +\ f_{k-1}\times a \]
边界条件 \(f_1=1,\ v_1=1,\ e_1=0\)
通过手模样例即可理解
构造出矩阵转移即可
1 |
|