Atcoder abc290

發表於 更新於 分類於 ， Disqus： 文章字數： 2.2k 所需閱讀時間 ≈ 7 分鐘
G(贪心)Ex(数学)

https://atcoder.jp/contests/abc290/tasks

G - Edge Elimination

perfect k(>=2)叉树,深度D(根深度=0)

问最少剪掉多少边，存在一个点数为X的连通分量

数据足数 t <= 100

原树点树 <= 1e18

2s

1024mb

我的思路

如果 选定连通分量 再剪断边

那么 显然连通分量的所有点有唯一lca，那么如果这个lca不是根的化，只需要在lca的父向边剪断

而对于指定了根以后，剩余的全是从指定根向叶子向的连通路径

因此每次剪断边相当于减去 1+k+k2+… = (k^?-1)/(k-1)

注意到 点<=1e18

log2(1e18) = 59.794705707972525, 即 D <= 60

所以对于指定根来说 可以枚举根在哪一层

x = (k^{d+1}-1)/(k-1) - a1(k1-1)/(k-1) - a2(k2-1)/(k-1) - a3(k3-1)/(k-1) -…

min(a1+a2+a3+..)

然后注意到 不同层的点的剪断次数之间还有限制关系，所以 这像是一线性规划?

一个方向是考虑 k = 2时，就是二叉树

每次都是减去 2^d-1

1
2
3
4
5
6
7
8
9
10
11
1110101011011110
1111111111111111
    111111111111
    111111111111
      1111111111
      1111111111
        11111111
        11111111
           11111
           11111
               1

想要从高到低 贪心（数位dp?）但证明不了??

但这样至少是可行解不一定是最优解

题解

想法方向是正确的，就是贪心正确性的

在指定X的根以后

如果当前剩余的为Y, 最大的子树u <= Y-X

v为其儿子

要证明的是直接减去u不会更差

換句话说，就是 (u + …) 的方案的选边 <= (比u小深)的选边

而对于 u的个数的拆分 (1+k个v)

而这多出来的1,并不会让 (…) 中的个数下降 > k 个???

不妨给这个1在新的方案中标上颜色，首先是如果1是新的某个子树的根，那么和没加之前是一样的

如果这个1在新的方案中不是根，那么把它換作根个数不变

如果比原方案个数下降 > k, 那么在換作根以后去掉 会是一个更优的方案，所以原方案不是最优解

这样证明了，选u不会是比最优解更差的解

代码

https://atcoder.jp/contests/abc290/submissions/41805891

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#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 a[60+10]={1};

void w(){
  int D=read();
  ll K=read();
  ll X=read();
  rep(i,1,D+1) a[i] = a[i-1]*K+1;
  ll ans = 1'000'000'000'000'000'000;
  rep(k,0,D+1) if(a[k]>=X){
    ll cnt = !(k==D); // 是否为原来的根
    ll x = a[k]-X;
    per(j,0,k){
      cnt += x/a[j];
      x %= a[j];
    }
    ans = min(ans,cnt);
  }
  printf("%lld\n",ans);
}

int main(){
  int t = read();
  while(t--) w();
  return 0;
}

Ex - Bow Meow Optimization

n个狗，m个猫, 需要排列成一条线, 排列会造成动物沮丧

狗i的沮丧值 = Ai |x-y|, x和y分别是它左右侧的猫的个数

猫i的沮丧值 = Bi |x-y|, x和y分别是它左右侧的狗的个数

问所有排列方案中，最小的(沮丧值的和)

n,m 300

ai,bi [1,1e9]

2s

1024mb

我的思路

这n,m 只有300, 似乎是 O(n m) 以上的?

如果我们指定了猫狗的不分内部ai/bi的排列

那么，对于狗内部的交换，不影响猫的贡献。同样对猫的内部交换，不影响狗的贡献

那么 ai * |xi-yi| + aj * |xj-yj| 交换后是 aj * |xi-yi| + ai * |xj-yj|

ai * |xi-yi| + aj * |xj-yj| <= aj * |xi-yi| + ai * |xj-yj|

ai * ti + aj * tj <= aj * ti + ai * tj

ai * (ti-tj) <= aj * (ti-tj)

(ai-aj) * (ti-tj) <= 0, 说明 a的大小关系 和|x-y|的大小关系 相反

也就是 位置的 猫贡献|x-y| 小的地方，ai就要放大的，而位置|x-y|贡献大的地方ai要放小的

一个极端，如果狗为偶数个，那么把猫全部放在狗中间

则贡献 = (sum 狗) * (cnt 猫),

对于 指定 猫狗排列，其最小值根据上面的方法可以很快算出

那么 如果改变 排列，对于相邻的 [狗,猫] 改为 [猫,狗]

对于这两个位置以外的|x-y|贡献不变

而这两个 位置在绝对值的的变化是 -2 和 +2

所以 对于加绝对值后的变化是 +2/-2/+0

看起来没有太大帮助，因为 如果左侧狗 > 右侧狗，右侧猫 > 左侧猫，那交换的确都-2，而这都-2在保持ai/bi不变时必定减小，

但是这只感受到局部性，如果有-2,+2同时发生时，可能-2的ai/bi更大，而+2的ai/bi更小，得到更优

另外一个思路就是从一侧开始，如果是狗,则一定是最大的ai,因为|x-y|是最大的，但问题是

这样向中间推进时，新的决策位置|x-y|不再知道是“最大”或者是第几大的了，由此不不知道选哪个ai/bi

这样想从两侧向中间推进? [len left][len right][left dog][right dog]

还是无法保证新的决策位置|x-y|的最大性

题解

模拟退火 Simulated Annealing ?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

根据上面的推理，其实知道 |x-y|是先减后增，所以赋值是先增后减

性质1: 当有奇数个数时抛开正中的猫狗，或者偶数个数时， 左右侧的猫狗都是一半一半

即 [half 狗 half猫][中间 猫%2 狗%2 ][half狗 half猫]

证明: 不妨设左侧狗 > half狗, 可以通过相邻逐个交换向中间交换，交换到中间左侧，这样贡献显然单调递减，同时因为左侧狗 > half狗，则右侧一定猫 > half猫，同理右侧猫可以相邻逐个交换到中间右侧

因此有 [>=half 狗 < half猫] 狗 [中间 猫%2 狗%2] 猫 [< half 狗 >= half 猫]

对于中间易证:

狗[狗猫]猫 >= 狗[猫狗]猫 >= 猫[狗猫]狗

狗[狗]猫 >= 狗[猫]狗 >= 猫[狗]狗

狗[猫]猫 >= 猫[狗]猫 >= 猫[猫]狗

狗[]猫 >= 猫[]狗

而这带来了一个极好的性质, 那么对于左边中的，如果相邻 狗猫交换成猫狗， 那么贡献变化一定是 +2狗-2猫, 因为它们都是右侧更多, 同样对于右侧中的来说 也是这样

这就完成了 去绝对值,

而不只是去绝对值，也完成猫狗之间的联系，因为这里发现交换则意味着 猫和狗的直接大小关系

所以从两边向中间放

dp[i][j][k] = 放了前i小的动物，左侧中放了j个狗，k只猫 的最小贡献

而这里因为前i小的动物，所以

右侧的狗个数 = 前i小中的狗的个数-j

右侧的猫个数 = 前i小中的猫的个数-k

这里也是因为a/b有序性才让 4维变成3维

代码

https://atcoder.jp/contests/abc290/submissions/41817376

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#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);)
ll read(){ll r;scanf("%lld",&r);return r;}
void chmin(ll &a, ll b) {a=min(a, b);}
int a[310];
int b[310];
int main() {
  int n=read();
  int m=read();
  rep(i,0,n) a[i]=read();
  rep(i,0,m) b[i]=read();
  sort(a,a+n);
  sort(b,b+m);
  ll ans = 0;
  if (n & 1) rep(i,0,m) ans+=b[i]; // 奇狗
  if (m & 1) rep(i,0,n) ans+=a[i]; // 奇猫
  if (n & 1) n--; // 奇狗
  if (m & 1) m--; // 奇猫
  vector<pair<int, int> > ab; // a or b,0 or 1
  rep(i,0,n) ab.push_back({a[i], 0});
  rep(i,0,m) ab.push_back({b[i], 1});
  sort(ab.begin(), ab.end());
  const ll INF=0x3f3f3f3f'3f3f3f3f;

  vector dp(n + m + 1, vector(n + 1, vector<ll>(m + 1, INF)));

  dp[0][0][0] = 0;
  int dog = 0;
  int cat = 0;
  rep(i,0,n+m){ // i 总数
    auto [now,cate]=ab[i];
    if (cate == 0) { // 狗
      rep(j,0,dog+1) rep(k,0,cat+1) if(dp[i][j][k]!=INF){
        chmin(dp[i+1][j+1][k], dp[i][j][k] + now * (m - k * 2));        // 放左侧
        chmin(dp[i+1][j  ][k], dp[i][j][k] + now * (m - (cat - k) * 2));// 放右侧
      }
      ++dog;
    } else { // 猫
      rep(j,0,dog+1) rep(k,0,cat+1) if(dp[i][j][k]!=INF){
        chmin(dp[i+1][j][k+1], dp[i][j][k] + now * (n - j * 2));        // 放左侧
        chmin(dp[i+1][j][k  ], dp[i][j][k] + now * (n - (dog - j) * 2));// 放右侧
      }
      ++cat;
    }
  }
  printf("%lld\n",ans + dp[n + m][n / 2][m / 2]);
}

总结

F

虽然 连 $\sum_i \binom{a}{i}\binom{n}{i}$ 可以化简都没发现，但是用NTT强行过了, 用了一下289 Ex Trio的技巧

G

敢贪也要敢证

H

还是不喜欢 工程概率类的方法 比如模拟退火, 比如字符串hash

这个一半 回过头来看，应该算很“自然”不怪，又不太难证的想法，没去向这个方向想真的不应该

过往有绝对值的题目，去绝对值都是一个关键步骤，这里就是靠上面这个证明一半的性质来达到去绝对值

不过在3维和从两头放的方向是有想到

参考

官方题解