CF tracker

Edu List

https://codeforces.com/contest/1651

F. Tower Defense

塔防游戏, i位置上 塔 能量上限c[i] 每秒充能r[i], 初始满能量

一关卡 生成 q 个怪, 第j个怪, 在point 1位置, tj时刻, 生成, 血量hj, 移动速度1格子/s

当怪经过 塔时, 塔对它 造成 min(怪血量,塔能量) 的伤害, 并且消耗同样多能量

但是还是会有的怪 活着经过所有塔

求 或者的怪的血量和

范围

n 2e5

ci,ri [1,1e9]

q 2e5

tj [0,2e5] 保证严格单调递增

hj [1,1e12]

我的思路

假设 每个怪都不死, 而且每个塔充能无上限

那么除了第一个怪, 第i个怪 受到的伤害 = (i与i-1的时间差) * (sum r)

但似乎没有什么帮助

再看 既然 伤害唯一来源是塔, 那么 伤害 + 剩余血量 = 总血量

如果能计算出塔实际造成的伤害, 那么 剩余血量也可以算出

第一个塔

min(c[1],h[1]): c[1] -> c[1] - min(c[1],h[1]) = p[1]

min(c[1],p[1]+r[1](t[2]-t[1]),h[2])

.. 感觉就是关联很紧, 如何消除这种 强关联

第一个 假设在 塔i倒下 或 塔j倒下, 有啥不同

i倒下, 说明i-1都是完全能量, j 倒下,说明j-1塔都是完全能量, min(i,j) -1 都是完全能量

所以看起来需要一个前缀能量和

而第二个 如果 在 p2 倒下, 第一个在p1 倒下

那么 如果哦 p2 < p1 对于 前 p2-1 对 第二个造成的伤害 就是 = sum min((t[2]-t[1])r[i],c[i])

一个与t,i 相关的 函数, 对于给定t, 随i严格单调递增, 但是问题是 难以?快速求点值, 不然可以二分

另一个问题, 如果 p2 > p1, 那么超出的部分还要和 更前面的相关

想拆一个单独x, 或者调整血量, 似乎都没啥能和原题方案一致的办法

感觉很卡在一个 无法快速计算一轮的结果

换个视角, 不按怪来看, 按塔来看

第一个塔接受的是 (t0,h0) (t1,h1) …

输出的内容被第塔接受, 而可以通过时间偏移让时间不变 (t0,h0_1) (t1,h1_1) (t2,h2_1)...

那么问题变成

有一堆点 (t0,h0) (t1, h1)

依次 n个操作 (ri,ci), 对每个点的高度进行修改, 问最后的高度和

看起来 每个h变化在允许小于0时, 下降要么是 ci, 要么是间隔 * ri ?

但实际上并不是, 可能是击倒了上一个 有残余

但是每个单位最多被击倒一次!

n次 残余情况, 剩下的都是 ci, 间隔 * ri

如果 h > ci 一定不被击倒, 如果 h < min(间隔 * ri, ci), 一定被击倒

还剩 间隔 * ri < h < ci 的情况

感觉上需要 实现一定的区间操作, 而且可能需要先排序什么的?

CF tracker

Edu List

https://codeforces.com/contest/1701

F. Points

如果 i < j < k 且 k-i <= d 则 称作美丽

初始没有点, q次操作, 每次操作3种可能

1. 增加一个点
2. 删除一个点

保证 集合中不会有相同点

每次操作后 计算 美丽的三元组个数

范围

q 2e5

d 2e5

a[i] 点坐标 [1,2e5]

6.5 s

512 mb

我的思路

简单讲, 就是 选两个距离小于d的点作为首尾, 然后问它们之间其它点的个数 作为贡献, 的贡献和

维护

其实增加一个点, 和删除一个点, 并不会影响其它点的组合,

影响的 三元组一定和操作的这个点有关

如果它是 最小的

= sum_{l=2~d} count(i,i+l) * c[l]

如果暴力算, 需要 O(d)

如果它在中间

= sum_{l=1~d-1} count(i,i-l) * c[i+d-l]

也是O(d)

感觉 似乎可能按照sqrt(max{a}) 分块

分块 对于不在中间的情况还好, 因为 相当于计算 (i,i+d] 之间 的不同值的点对个数, 在一个块里 预计算了, 在不同块里, 通过前缀和 可以算掉,

问题是 当加入的/删除的 为中间点时, 那么要找的就是 i < point < k, 且 k-i <= d

不知道有啥办法搞

CF tracker

Edu List

https://codeforces.com/contest/1716

E. Swap and Maximum Block

给一个长度 2^n 的数组a, 值范围是[1~2^n]

q个询问,

每个询问, 给k, for i = [1..2^n-2^k], 如果该轮询问没有交换过a[i],则交换swap(a[i],a[i+2^k])

操作后, 输出最大的连续区间的和

范围

n 18

a[i] \in [-1e9,1e9]

q 2e5

4s

512mb

我的思路

很显然 就是一个满完全二叉树

而操作k 就是从下向上第k层左右交换,(第k-1层每个点交换左右儿子)

问题是如何维护最大值, 或者如何算最大值

考虑直接算,

f(l..r) = max(f(l..mid),f(mid+1..r),maxr(l..mid) + maxl(mid+1..r))

maxr(l…r) = max(suffix(l…r))

maxl(l…r) = max(prefix(l…r))

但问题是 交换会让比 n-k层更低的 都会影响

感觉可能的方向, 就是 暴力从下向上, 枚举所有

似乎 就 层数的个数 和层数的方案数的乘积都是2^n, 这样就是n 2^n???

CF tracker

Edu List

https://codeforces.com/contest/1721

F. Matching Reduction

给2分图, 左侧n1个点, 右侧n2个点, m条边

2种询问

第一种, 删除最少的点, 让最大匹配的值 正好少1, 输出具体选点方案, 剩余的匹配边的index和

第二种, (只会紧跟着第一种, 输出实际的匹配方案)

注意的是,在输出询问的结果前是无法读下一个的, 你需要fflush 输出后才能读下一个询问

范围

n1,n2 [1,2e5]

m 2e5

q 2e5

8s

512mb

强制在线

我的思路

极端一点, 不妨设每次都有1和2的询问, 就变成了如何维护二分图的匹配了

有点想到 abc215 的霍尔定理(左侧n点,右侧m点, 最大匹配为n的充分必要条件, 左侧的任意k个点集子集,连右侧点的个数都>=k)

所以如果 当前的匹配 刚好一侧点=匹配个数, 那么这一侧就随便删除一个点就行, 并且还满足这一侧的点=匹配数

问题来到 当匹配数 < 左侧点, 右侧点 时如何处理

1
2
3
4

1 -> 4
2 -> 4
3 -> 5
3 -> 6

比如这个就是两侧都是3个点,但是最大匹配只是2, 看上去, 删除3或者4都能让个数-1

再变化

1
2
3
4
5
6

1 -> 4
2 -> 4
3 -> 5
3 -> 6
7 -> 8
7 -> 9

不论删除3还是7 都可以让匹配数-1, 但是 都不会让匹配数 = 一侧点数

主要感觉霍尔定理还是和完美匹配挂钩

考虑直接匹配, 得到一个方案, 如果删除的点不在匹配中, 那么一定对个数无影响

所以至少需要删除一个匹配中的点

虽然匹配过程有顺序, 但是因为点是可以乱序, 所以考虑如果让最后一个失配 会怎么样

1. 删除左侧点,

那么 左侧且在它前面的未匹配点不会影响,因为没匹配它时也未找到方案(在匈牙利算法中一个匹配成功的点会一直在匹配中)

左侧未匹配在它之后的可能会有影响, 设它是 u0 -> v0, 而后面的是u1 能通过某条路径(不一定直接,可能和前面的点走反边)和v0 匹配, 而u0 可以匹配某个当前右侧未匹配的 v, 那么这种情况 会有更大匹配, 而当前就是最大匹配矛盾,

所以如果有u1有路径和v0 匹配则 u0 一定没有额外可匹配的点,(这种情况删除v0即可, 空出来的u0不会被任何匹配)

否则所有u1都没有路径到v0, (这种情况删除u0即可,空出来的v0不会被任何匹配,其实左右交换是有对称性的)

综上得到, 每次只需要删除一个点(左右中一个和另一侧 未配点没有匹配关系的)

how 找

好处是上面的方案 所有匹配都没有变化, 只是减少, 而不会交换匹配的点

那么不如先跑一遍最大匹配, 然后枚举点和边, 计算每个点和未匹配的点有边的个数(O(E+V))

丢进set< pair<个数,点id>>维护

然后删除时更新一下set, 每条边更新一次, O(E log E)

然后随便set维护一下匹配方案

似乎就没了?

但是想了个反例

1
2
3
4

1-1
2-1
2-2
3-2

然后当前是1-1和2-2, 注意到右侧2没有未匹配点和它相连, 所以如果删除它匹配的左侧1, 并不能让个数下降

所以需要 找到的是一侧匹配的点 有, 一侧没有的这种去删除, 否则 所有的点都没有额外连接点了(就可以任意一个)

CF tracker

Edu List

https://codeforces.com/contest/1728

F. Fishermen

n个钓鱼人

第i个获得大小a[i]的鱼

他们选一个报告的顺序, 报告鱼的大小b[i], 但是可能虚报

第一个报告的 诚实报告

其它人报告的 是最小的b[i]=a[p[i]]的倍数 且 大于 前一个报告值

1
2
3

1 2 3 2 2 8 3
按顺序报 变成
1 2 3 4 4 8 9

对于所有报告顺序, 让所有报告的 sum b[i] 最小

输出sum b[i]的最小值即可

范围

n 1000

ai [1,1e6]

6s

512mb

我的思路

如果两两不同, 那么从小到大就好了, 因为b[i] >= a[i], 这是所有都取a[i] 是最小值

如果 两个相同, 那么至少一个要虚报, 那么至少 2a[i]

如果 三个相同, 那么=> a[i], 2a[i], 3a[i]

但不只是让它们不同就完了, 因为翻倍后依然可能相同

1

2 2 2 3 3

1

2 4 6 3 6

这两个6还要处理

但是一个6是变8, 一个是变9

显然 如果a 有重复n次, 那么 a,2a,…,na 一定都有的,不会中间空着, 否则把更大的来填补可以让它更小

感觉上 当倍增的时候遇到相同的, 那就让小的去增加,

但实际上

1
2
3
4

2 2 2 2 3 3
变成
2 4 6 8
3 6

如果是 2的6去变化, 那么要变成16, 不如3的6变成9

而变化, 因为上面说了不会中间空着, 那就是每次找 最大的倍数去变

这样靠差值最小来变化的贪心, 似乎是对的吗???? 但我证明不了

然后 如果这样搞, 运算量

1

600 个1, 300个2 这样大量重叠

似乎也就O(2n)?

写了下, 不出所料 样例都没过

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

#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
int main(){
  int n=read();
  map<ll,vector<pair<ll,int> > > v2tv; // {倍数, 原值}
  rep(i,0,n){
    int a=read();
    v2tv[a].push_back({1,a});
  }
  map<ll,ll> v2mxt; // v 到最大倍数
  ll ans=0;
  while(v2tv.size()){
    auto [k,arr]=*v2tv.begin();
    v2tv.erase(v2tv.begin());
    auto keep=arr[0];
    rep(i,1,size(arr)){
      auto [kt,kv] = keep; // keep {t,v}
      auto [nt,nv] = arr[i]; // new {t,v}
      if(!v2mxt.count(kv)) v2mxt[kv]=1; // kt 一定是1
      if(!v2mxt.count(nv)) v2mxt[nv]=1; // nt 一定是1

      ll nkt=v2mxt[kv]+1;
      ll nnt=v2mxt[nv]+1;
      if(nkt*kv < nnt*nv){ // 用keep
        v2mxt[kv]=nkt;
        v2tv[nkt*kv].push_back({nkt,kv});
        keep=arr[i];
      }else{ // 用 arr[i]
        v2mxt[nv]=nnt;
        v2tv[nnt*nv].push_back({nnt,nv});
      }
    }
    printf("%d -> %lld\n",keep.second,keep.first*keep.second);
    ans+=k;
  }
  printf("%lld\n",ans);
  return 0;
}

1
2
3
4
5
6
7
8

1 -> 1
2 -> 2
3 -> 3
2 -> 4
3 -> 6
8 -> 8
2 -> 10
34

问题就在6的地方是动2还是动3, 动2是先到8再到10, 这个8 能预判吗??

并不会