G - Isosceles Trapezium
二维平面, N个点,坐标Xi,Yi, 权重Ci
选4个点, 形成 等腰梯形, 问选的4个点最大权重和
限制
N 1000
Xi,Yi [-1e9,1e9]
Ci [1,1e9]
无重点
3s
1024
我的思路
有点计算几何
N的样子,像是N^2的做法
如果是暴力找三个点, 确定平行边,那么剩下一个点就自然确定了, 这样的话是 N^3 log(N)
换个想法, 按对称轴来找
如果是垂于对称轴的一点,则找对称轴最远的两个点
这样 N^2 的对称轴, 其中相等的里面 按照垂点相同的最大的,找不同的两组就行了??
代码
https://atcoder.jp/contests/abc220/submissions/33799130
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
74
75
76
77
78
79
80
81
82
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
ll read(){ll r;scanf("%lld",&r);return r;}
ll gcd(ll a,ll b){
a = abs(a);
b = abs(b);
while(b!= 0) tie(a,b) = make_pair(b,a%b);
return a;
}
const ll INF = 0x3f3f3f3f3f3f3f3f;
array<ll,3> xyv[1010];
map<tuple<ll,ll,ll>, vector<pair<int,int> > > cx;
void addp(int i,int j){
auto [x0,y0,v0] = xyv[i];
auto [x1,y1,v1] = xyv[j];
ll ky = 2*(y1-y0);
ll kx = -2*(x1-x0);
ll k = (x1-x0)*(x1+x0) + (y1-y0)*(y1+y0);
ll g = gcd(k,gcd(ky,kx));
ky /= g;
kx /= g;
k /= g;
if(ky < 0){
ky = -ky;
kx = -kx;
k = -k;
}else if(ky == 0 && kx < 0){
kx = -kx;
k = -k;
}
cx[{ky,kx,k}].push_back({i,j});
}
int main(){
int n = read();
rep(i,0,n){
int x = read();
int y = read();
int v = read();
xyv[i] = {x,y,v};
}
rep(i,0,n) rep(j,i+1,n) addp(i,j);
ll ans = -1;
for(auto [_,vec]:cx){
auto center = [=](const pair<int,int>&ij){
auto [i0,j0] = ij;
auto [x0,y0,v0] = xyv[i0];
auto [x1,y1,v1] = xyv[j0];
return make_pair(x0+x1,y0+y1);
};
sort(vec.begin(),vec.end(), [=](const auto &ij0,const auto &ij1){
return center(ij0) < center(ij1);
});
ll lastmax = -INF;
ll cur = -INF;
rep(i,0,vec.size()){
if(i == 0 || center(vec[i]) != center(vec[i-1])){
lastmax = max(lastmax,cur);
cur = 0;
}
auto [i0,j0] = vec[i];
cur = max(cur, xyv[i0][2] + xyv[j0][2]);
if(lastmax != -INF){
ans = max(ans, lastmax + cur);
}
}
}
printf("%lld\n",ans);
return 0;
}
|
H - Security Camera
N 点, M 边
选定一些点, 让边(至少一个点上有被选定的)的数量是偶数个
求合法方案数
限制
N 40
无重边,自环
2s
1024mb
我的思路
感觉题面就是个朴素的图论
40 呢, 对应边就是780
估计是个边平方~ 3次方 左右的算法, 或者点的5次方?
思路正向就是考虑局部可行方案加上插头状态
逆向就是 所有减去存在未选择的 做容斥
点数量40, 2^40 = 1099511627776
如果, 是一个一个安装的, 那么考虑对于个数的影响
增量是 相邻未安装的和
而对于这个连接出的点,相邻未安装的奇偶性发生颠倒
题解
2^20 = 1048576
折半
把拆成两个点集合S,T
L1[S,s] = 点集S的子集s 被选了, 覆盖的边数的奇偶性
L2[S,T,s] = 点集T中, 连向S\s的数量是奇数的点集? (因为偶数的话,首先不被s选,其次不论在T中是否被选不影响奇偶性
R[T,t] = 点集T的子集t被选了,覆盖的两端属于T的边的奇偶性
因为对于每个选中状态, 可以枚举剩下所有点, 所以 可以$O(|S|2^{|S|})$ 暴力算完
那么对于答案有贡献的
$L_1[s] \oplus ((\text{popcount} (L_2[s] & t) ) &1) \oplus R[t] = 0$
意义 s得到的奇数偶,t内部奇偶,和t向S\s的奇偶 = 最终奇偶
中间这玩意怪怪的,虽然很长意义也就是L2[s] & t 的1的个数的奇偶性
像个办法把右侧合并一下
$F[S,T,s] = \sum_{t \subset T} ((\text{popcount} (L_2[s] \& t) ) \& 1) \oplus R[t] $
注意到 求和部分,奇数贡献1, 偶数贡献0, 所以这里是对于给定s,在T的子集中, 让上述表达式贡献1的个数
那么贡献0的个数就是 $2^{|T|} - F[S,T,s]$
如果能求出来, 那么对于每个$s$, 有$L1[s]$ 的奇偶性, 直接加上对应贡献即可
问题变成是如何求出F[S,T,s]
这里记$t’ = L2[s]$, 这样一个s唯一对应一个t', 但t'可能有多个s 映射过来
记作$G[T,t’] = \sum_{t \subset T} ((\text{popcount} (t’ \& t) ) \&1) \oplus R[t] $
这样有个好处是,不再关心S和s, 只用管T中的即可
注意到 $FWHT$的变换公式是
$fwht[a]_ i = \sum_{(\text{popcount}(i \& j) \bmod 2 = 0}a_j - \sum_{(\text{popcount}(i\& j) \bmod 2 = 1}a_j$
对于给定 i
一个具体的j
左侧为0时, 原式子贡献是 R[j], 而fwht贡献是 a[j]
左侧为1时, 原式子贡献是 R[j]^1, 而fwht贡献是 -a[j]
如果让a[j] = R[j], 那么
左侧为0时, 原式子贡献是 0 , 而fwht贡献是 0
左侧为0时, 原式子贡献是 1 , 而fwht贡献是 1
左侧为1时, 原式子贡献是 0^1, 而fwht贡献是 -0
左侧为1时, 原式子贡献是 1^1, 而fwht贡献是 -1
左侧为0和为1各占一半, 总贡献会少掉$2^{|T|-1}$
加上即可?
另一个做法
所有边变成”有向”, 小点连出到大点
f[i][j][k] = 前i个点, 未覆盖的边的两端都在前i的边数为j(奇1/偶0), 一些未来不选的会影响未覆盖边的奇偶性的点的方案数
i+1选 f[i][j][k] 贡献 f[i+1][j][k高(i+2)位]
i+1不选 f[i][j][k] 贡献 f[i+1][j^(i+1是否在k中)][(k高(i+2)位) ^ (i+1 连出的边) ]
很神奇的是, 这样每个点对于每个上个状态最多分支出两个状态
那么前一半最多2^20个状态
而状态低i位都是0, 所以后面的一半也是最多2^20个状态
所以复杂度也是
n 2^{n/2}
从一定程度上也有meet-in-middle 的感觉,而没有了fwt的需要
代码
https://atcoder.jp/contests/abc220/submissions/33847519
1.7s 快超时了, 为什么有人6ms 啊
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}
ll g[50];
unordered_map<ll,ll>f[50][2];
int main() {
int n = read();
int m = read();
rep(i,0,m){
int x = read() - 1;
int y = read() - 1;
if(x > y) swap(x,y);
g[x] |= 1ll<<y;
}
f[0][0][0]=1;
f[0][0][g[0]]++;
rep(i,0,n-1) rep(j,0,2) {
for(auto [mask,cnt]:f[i][j]) {
ll bit = (mask >> (i+1)) & 1;
f[i+1][j][mask^(bit<<(i+1))]+=cnt;
f[i+1][j^bit][mask^(bit<<(i+1))^g[i+1]] += cnt;
}
}
ll ans=0;
for(auto [_,cnt]:f[n-1][m&1]) ans += cnt;
printf("%lld",ans);
return 0;
}
|
总结
G
没啥难的
简单的计算几何,排序,自定义排序
H
一个是40的一半是20, 2^20 是可以范围内的
另一个是拆的时候,可以按点拆分,一半是有点就包含,另一半是需要两端都属于集合
参考
官方题解
csdn 逆天峰 H