Atcoder abc236

發表於 更新於 分類於 ， Disqus： 文章字數： 2.7k 所需閱讀時間 ≈ 9 分鐘
E(DP)F(xor线性基,线性代数)G(矩阵)Ex(容斥,bitdp)

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

E - Average and Median

给你一个数列

从中选一些数,保证任意相邻的两个至少一个被选

求 平均数的最大值

求 中位数的最大值, 这里偶数个的时候, 取第 n/2 个 而不是中间两个的平均数

范围

n 1e5

ai [1,1e9]

我的思路

想dp吧, 但是如果是dp[i][0/1] 表示第i个是否选的最大平均值

那么问题是, 前面更小的平均值可能让结果更大

因为 (v0c0+a[i])/(c0+1) < (v1c1+a[i])/(c1+1), 并不意味着 v0和v1的大小关系

但如果把数量带上, 啊不就n^2空间

然后思路二, 先任意选一些合法, 然后剩下的没选的中, 从大到小,只要比当前平均值大, 则选择, 否则不选

这样最优 = 最优

问题是 如何枚举所有初步合法, 就算枚举了, 这样搞 至少还有个n倍

再就是,直接从大到小选,选到合法为止, 但是看起来样例就是反例

再就是 考虑二分答案, 答案是否小于 val, 如果小于, 则所有大于它的都必选, 因为如果不选,而答案小于val,则选了可以更大

这样对于剩下的来说, 依然和数量和和有关比如 200 100 1 100 200,

不会了

题解

考虑答案是否超过k

平均数 > k 等价 (xi-k) 有方案和大于0, 这样就不关心个数了, 而是只用关心值

中位数 > k 等价 大于k的数量 大于 小于等于k的数量, 所以大于的变成1, 小于等于的变成-1, 同样求最大的和

注意精度

代码

https://atcoder.jp/contests/abc236/submissions/34706816

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
#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 n ;
ll maximize(const ll * a) { // 相邻至少一个选,最大和
  ll c[2] = {0,0}; // 0:第i个不选, 1个选
  rep(i,0,n) tie(c[0],c[1]) = make_pair(c[1],max(c[0],c[1])+ a[i]);
  return max(c[0],c[1]);
}

// 左小于等于 右大于
template <class F> ll binary_search_lambda(ll ok, ll ng, const F& check) {
  while (abs(ok - ng) > 1) {
    ll md = (ok + ng) / 2;
    (check(md) > 0 ? ok : ng) = md;
  }
  return ok;
}

const ll t12 = 1000000000000;
const ll t9 = 1000000000;
const ll t3 = 1000;

ll a[100010];
ll b[100010];
int main() {
  n = read();;
  rep(i,0,n) a[i] = read();
  ll average = binary_search_lambda(0, t12 + 1, [&](const ll thres) {
    rep(i,0,n) b[i] = a[i] * t3 - thres;
    return maximize(b) >= 0;
  });

  ll median = binary_search_lambda(0, t9 + 1, [&](const ll thres) {
    rep(i,0,n) b[i] = a[i] >= thres ? 1 : -1;
    return maximize(b) > 0;
  });
  printf("%lld.%03lld\n", average/t3,average%t3);
  printf("%lld\n",median);
  return 0;
}

F - Spices

给你 [1,2^n) 的每个数对应的代价c[i]

求能表示[1,2^n) 的xor线性基, 的最小代价和

范围

n 16

ci [1,1e9]

2s

1024 mb

我的想法

看一个值和前面选的是否线性相关可以做, 但也是求出一组线性基

而如何保证最小呢???是否有局部性

比如

1,01,11, 可以3种选择

并没有相关知识, 也不会推

题解

先按照代价排序

然后从小到大找就行了……………………………………………

啊 我蠢了

如果 A线性无关, A & a 线性相关

那么如果A\b & a线性无关, 其实说明 A 和 A\b & a 等价

因为 A 等价 A & a = (A\b & a) & b = (A\b & a)

这人均会线性代数的吗?

求线性基

1
2
3
ll x = value;
for(int b:bases) x = min(x, x^b); // 意义是每个对应其最高位的1, 这样xor把对应最高位xor 1, 变成0
if(x) bases.push_back(x);

代码

https://atcoder.jp/contests/abc236/submissions/34714903

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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();
  vector<pair<int,int>> ci; // <cost, x>
  rep(i,1,(1<<n)) ci.push_back({read(),i});
  sort(ci.begin(), ci.end());;
  ll ans = 0;
  vector<int> bases; // 线性基的值
  for(auto[c, x]:ci){
    for(int b:bases) x = min(x, x^b);
    if(x) {
      bases.push_back(x);
      ans += c;
    }
  }
  printf("%lld\n",ans);
}

G - Good Vertices

N点,有向图

时刻0, 无边

时刻 t=1..T, 增加边ut -> vt,(可能自环)

如果一个点, 能从1开始,恰好L次移动到达, 则称为好点

对于每个点输出它首次变成好点的时刻

范围

n 100

L 1e9

t <= n^2

2s

1024mb

我的思路

看这n这么小,l这么大

第一感觉就是矩阵快速幂,但是每次需要 n^3 log(l)

一共n^5 log(l), 感觉过不了啊

优化思路, 既然是每次增加, 那么答案的点集也是非严格增加点的

那么, 可以考虑记录 初始矩阵2的幂次的矩阵幂的结果, 如果一样提前的到结果, 后面的可以减少一定计算, 但不会估计复杂度

然后因为其实只需要是否大于0, 所以可以变成 >= 0 的矩阵运算状态

题解

还是矩阵乘法

但是不要每次计算而是一起算

这样,边权变成时间, 而乘法变成a[i][j] =min(max(a[i][k],a[k][j]))

代码

https://atcoder.jp/contests/abc236/submissions/34765126

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}

const int INF = 0x3f3f3f3f;
template<class T> T f(T &A,T&B) {
  int n = A.size();
  auto C = vector(n,vector(n,INF));
  rep(i,0,n) rep(j,0,n) rep(k,0,n) C[i][j] =min(C[i][j],max(A[i][k],B[k][j]));
  return C;
}

int main() {
  int n = read();
  int t = read();
  int L = read();
  auto A = vector(n,vector(n,INF));
  A[0][0]=0;
  auto B = vector(n,vector(n,INF));
  rep(i,1,t+1) {
    int x = read()-1;
    int y = read()-1;
    B[x][y]=i;
  }
  while(L){
    if(L%2) A=f(A,B);
    B=f(B,B);
    L/=2;
  }
  for(auto v:A[0]) printf("%d ",v == INF?-1:v);
  return 0;
}

Ex - Distinct Multiples

给一个长N正整数序列D

求的长N正整数序列A,且满足要求的个数 mod 998244353

  1. $A_i \in [1,M]$
  2. $A_i\ne A_j,(i\ne j)$
  3. $A_i \equiv 0 \pmod {D_i}$

范围

N 16

M 1e18

我的思路

不妨先给D排序, 这样D从小到大

这N很小, 难道是bitdp + 容斥

2^16 = 65536

sum (-1)^cnt(bitmask) count(bitmask 全部相等)

= sum (-1)^cnt(mask) M/lcm(a[mask])

题解

N个点完全图

E为边集

S为E的子集

f(S) = 满足 范围和倍数, 且联通块中两两相等的方案数

所以答案 = sum f(S)(-1)^{|S|},

令g(T) = M / lcm(or a[T])

h(n) = n个点的图让所有点连通的边方案的$(-1)^{边数}$的和

h(1) = 1

对于n>=2,如果不考虑连通性,显然奇数条边和偶数条边方案一样, 即和=0,(每条边选和不选对应奇偶不同,所以数量一样)

令每个方案中T是包含1的连通块, |T| >= 2 不为全部1..n,

对于|T| = [1..n-2] 来说, 未连的部分又是任意连, 因此代价和也是0

对于|T| = n-1 和 |T| = n, h(n)+(n-1)h(n-1) = 0

因此h(n) = -(n-1)h(n-1)

即h(n) = (-1)^{n-1} (n-1)!

那么对于 $f(S)(-1)^|S|$ 对应的点的多个连通块 T1…Tk,的和 $= \prod g(T_k)h(|T_k|)$

因为相当于变成 指定了多个两两 不相交的 联通块, 每个连通块里的所有选边方案和的-1幂次权的和

就变成bitdp了

dp(mask) = sum (g * h)(含1的mask0) * dp(mask \ mask0)

把g,h展开一下

$dp(mask) = (-1)^{mask} sum ((n-1)! * ) dp_{mask/mask0}$

代码

https://atcoder.jp/contests/abc236/submissions/34841215

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
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
typedef long long ll;
#define MOD 998244353
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;} // read

const int N=16;
mint fac[20]={1};
mint f[1<<N]={1};
ll a[20];
ll lcm[1<<N] = {1}; // 如果过大 用 m+1表示
ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b);}
int c[1<<N] = {0};
int main(){
  int n = read();
  ll m = read();
  rep(i,0,n) a[i]=read();
  rep(i,1,n+1) fac[i]=fac[i-1]*i;
  rep(i,1,1<<n) c[i]=c[i&(i-1)]+1;
  rep(mask,1,1<<n){
    int p=__builtin_ctz(mask); // 最低位1的二的幂次
    int b=1<<p;
    ll u=lcm[mask^b];
    ll v=a[p];
    ll w=gcd(u,v);
    lcm[mask] = (u/w<=m/v)? u/w*v : (m+1); // 注意overflow 这里直接设置m+1 来避免overflow 而让结果 = 0
    // 非空子集遍历 包含最低位 dp[mask] = dp[mask0 not contain lowbit] * (g*h)(mask\mask0)
    for(int j=mask;j;j=(j-1)&mask) if(j&b) f[mask]+=f[mask^j]*fac[c[j]-1]*(m/lcm[j])*(c[j]&1?1:-1);
  }
  printf("%d\n",(f[(1<<n)-1]).val());
  return 0;
}

容斥

从零再学一次容斥

有U中元素有n种不同属性,有第i种属性的元素构成集合$S_i$

$\left|\bigcup_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{a_i < a_{i+1} }\left|\bigcap_{i=1}^mS_{a_i}\right|$

相当于 每个元素出现次数 = 1

集合的交 = 全集 - 补集的并

例子

$\sum x_i = m$

$x_i \le b_i$

求非负整数解的个数

容斥模型

  1. 全集 方程的非负整数解
  2. 元素$x_i$
  3. 属性$x_i \le b_i$

求的就是 所有对应的交 = 全集 - 补集的并

总结

E

难受啊 卡蓝题了

感觉这里的思路是变成和0比较, 因为和0比较的话, 个数就不在关心了, 这样就简单dp ! , 感觉这是干掉”个数”维度的一个思路

然后这里中位数把数量的比较,变成+1/-1,算最大和

F

还是蓝题,还是不会

不过我没怎么遇到这种 先排序代价, 再按顺序贪心的了, 算也依赖于线性基选择的局部性质选中不会被替换保证等价的局部性

G

把时间变成 权, 然后区min (max())

Ex

完全不会容斥, 问题应该是变成

  1. 确定全集
  2. 每个属性对应集合
  3. 每个元素的函数

这样做容斥

这样属性的个数才是-1的幂次, 保证容斥后并集每个的贡献为1次, 贡献为 元素的函数的结果

所以我那样的公式是不对的, 把相等点集作为属性意味着属性之间没有相互独立, 或者从中文上来讲, 两个属性对应集合的并就是两个共有的属性, 而bitmask无法表示这个意思, 011 | 101 = 111 , 但是第一个表示的是0和1相等, 第二个表示的是0和2相等,但是 后面表示的是012相等, 所以题解中的单个属性就是两个相等

而属性,一个是想每个值作为属性,

这里是建立图的关系, 每条边作为作为属性

参考

官方题解