Atcoder abc220

發表於 更新於 分類於 ， Disqus： 文章字數： 2k 所需閱讀時間 ≈ 7 分鐘
G(计算几何,排序,自定义排序)H(FWHT,FWT,meet-in-middle,bitmask)

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;} // read

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;
}
// y = -(x1-x0)/(y1-y0) (x - (x0+x1)/2) + (y0+y1)/2
// 2(y1-y0) y = -2(x1-x0) x + (x1-x0)(x1+x0) + (y0+y1)(y1-y0)

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;} // read

ll g[50]; // g[小点] = 大点的bit mask
// f[前i个点][两端均在前i个中的未覆盖的边的奇偶][mask中的点每不选一个奇偶性变化1]=方案数
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; // 选 点0，所有点因为不选 未覆盖 的边都为0，为偶数。
  f[0][0][g[0]]++; // 不选 点0，0指向的点因为不选 未覆盖 的边+1.
  rep(i,0,n-1) rep(j,0,2) { // 枚举当前的未覆盖的边数的奇偶。
    for(auto [mask,cnt]:f[i][j]) { // 枚举上一层的所有状态，进行推磨式转移。
      ll bit = (mask >> (i+1)) & 1;// 确定 不选点i+1 未覆盖的边的 奇偶变化。
      //选 点i+1，所有点(i+1之后的点) 因为不选而未覆盖的边数的就不变。且j的状态不变。
      f[i+1][j][mask^(bit<<(i+1))]+=cnt;
      //不选 点i+1，j的状态 根据当前j 和 因为i不选要未覆盖的边数的就确定
      //并且改变之后的点因为不选而未覆盖的边的奇偶
      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; // m&1 未覆盖的奇偶和总边一样,则覆盖了的为偶数
  printf("%lld",ans);
  return 0;
}

总结

G

没啥难的

简单的计算几何,排序,自定义排序

H

一个是40的一半是20, 2^20 是可以范围内的

另一个是拆的时候,可以按点拆分,一半是有点就包含,另一半是需要两端都属于集合

参考

官方题解

csdn 逆天峰 H