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

G - GCD Permutation

给一个1~N的排列p

问有多少个有序对 (i,j), (i<=j), 满足 gcd(i,j) != 1, gcd(p[i],p[j]) != 1

范围

n 2e5

5s

1024mb

我的思路

有点想暴力 然后证明复杂度?

对于 (i,Pi), 取两个中较小的一个, 找所有包含它下标的, 用较大的去验证gcd

最多有6个不同质数因子, 最坏情况 1/2+1/3+1/5+1/7+1/11+1/13 = 1.3左右

所以最坏情况是 找n个坐标

先写个代码再说

https://atcoder.jp/contests/abc230/submissions/34500571

---

显然 有很多是2 的倍数的,它们如果每个都会去访问n/2, 那么已经就是n^2了, 肯定会超时

---

想法就是 如果 (2的倍数,3的倍数) 之类做容斥? 但是我容斥完全不会

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

G - Longest Y

一个包含字符’Y’和’.’的长n字符串S,

可以操作[0,k] 次,交换S中的两个相邻字符

问可以得到的最终S的内部最长的连续Y的长度

范围

n 2e5

k 1e12

2s

1024mb

我的思路

考虑移动

最终假设是[l..r]

那么对于初始这些y的位置的大范围是[l0..r0]

那么一定可以分成两部分

[l0..m0][m0+1..r0]

一部分向右,一部分向左

显然有个点不需要动

如果选定了第i个点p[i]和期望个数c那么,移动代价为min( 左侧k0, 右侧k1个), k0+k1+1=c

= min(sum(p[i]-k0..p[i]-1) - sum(p[i-k0]..p[i-1]) + sum(p[i+1]..p[i+k1]) - sum(p[i]+1..p[i]+k1))

---

换个角度

所有值变成p[i]-cnt1[i]

那么就是找一个值, 尽量多的数变成它, 且代价和 <= K

显然每多一个,代价的增量是非严格递增的

是个凸函数(下凹)

---

但感觉, 这样看起来, 其实左侧右侧影响不大,而是距离影响更大,

所以直接枚举中点,二分距离(选定的点的最大距离) => 去计算距离和范围,以及点数范围

这里 < 距离的必选, >距离必定不选, =距离可选可不选

似乎就没了?

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

F - Stamp Game

w乘h的矩阵初始全白色,每个有数字aij

T 可以染黑 h1 w1

A 可以染白 h2 w2

T 操作一次, S操作一次

分数= 黑色块之和

T 让尽可能大, A让T尽可能小, 求答案

范围

h,w 1000

aij [1,1e9]

2s 1024mb

我的思路

感觉就是二维常见运算

因为长度如果超了长度, 可以贪心把对应位置全覆盖,可以取min, h2=min(h2,h1), w2=min(w2,w1)

ans = max(f(i,j))

f(i,j) = sum(i,j) - max(g((range))

应该就过了吧

这场UI还有红色特效

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

D - Project Planning

长n数组a

每次选k个不同的下标, 让值减1,(保证所有值非负), 求多减的次数

范围

n 2e5

ai [1..1e12]

2s

1024mb

我的思路

感觉如果数据量小,每次最大k个下标减1

但这样每次要排序, 而且ai很大

C - Even XOR

https://atcoder.jp/contests/arc146/tasks/arc146_c

求多少个 元素值范围在[0,2^N)的集合满足

集合的任意偶数个数的非空子集合,元素xor均不为0

mod 998244353

我的思路

先是在想 线性基, 但实际上 1 2 3 4, 也是合法的, 因为, 虽然3可以由2线性表出,但是它们是3个不是偶数个

---

然后想转移 n -> n+1

显然集合合法,它的子集也是合法

如果n 合法的方案, 拆一部分 高位填,0 另一部分高位填1, 这样的方案一定是合法, 那么 ans[n][len] 乘2^len, 贡献到a[n+1][len]

如果对于n合法,必定不存在 a,a+高位,b,b+高位 同时存在的情况, 因此至多有一个 自身和自身+高位同时存在

那么考虑 合法的选定一个 做这种自身和高位都存在, 剩下的依然拆分, 这样依然是合法的, ans[n][len] * len * 2^{len-1} 贡献到a[n+1][len+1]

---

然后这样似乎能多次做路径计算+组合数可以做

但是问题是 这样算出来 n=3时答案=141, 而正确的是149

也就是漏情况了

可能存在 不合法的n的方案 但是赋予高位0,1 以后变成n+1的方案 就合法了?

那么就是任意在n中 的 xor(A)^xor(B) = 0,

在n+1中 = xor(A)^xor(B+高位) = 高位

也就是n+1 中所有低位产生xor = 0 的必然对应的高位个数是奇数

不会推了