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

G - 012 Inversion

长n序列A, 元素只有0,1,2

q个询问

类型1, 输出A[l..r] 中逆序对个数

类型2, 同时 让A[l..r] 中 0->S,1->T,U->2

范围

n 1e5

q 1e5

5s

1024mb

我的思路

看起来, 就是 线段树 + 记录0,1,2个数 和逆需对个数

但是问题是, 虽然很容易计算 左侧选点 与右侧选点构成的逆需对个数

所以跨区间的容易计算

但是内部的 0,1,2 翻转 并不能只靠0,1,2个数就能得到

但如果记录 (0,1) (1,0) (0,2) (2,0) (1,2) (2,1) 个数

那么翻转就好计算了

甚至不需要记录逆对个数了, 直接统计(1,0) (2,0) (2,1) 个数即可

就过了..

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

F - Monochromatic Path

给定 h行 w列 黑/白 格子

可以 支付R[i] 翻转第i行

可以 支付C[j] 翻转第j列

求最小代价,让从(1,1)到(h,w) 有一条同色只向下/右走的路径

范围

h,w 2000

ri,ci 1e9

2s

1024mb

我的思路

然后 记走到 dp[i][j][i行是否翻转 0/1][j列是否翻转0/1]的最小代价

dp[i][j][计算出是否翻转][sj] = dp[i-1][j][0/1][sj] 因为知道[i-1][j]的颜色和j的翻转状态

dp[i][j][si][计算出是否翻转] = dp[i][j-1][si][0/1] 因为知道[i][j-1]的颜色和i的翻转状态

那么 就没了?

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

E - Sugoroku 3

n个格子,初始在1

1到n-1上面都有个骰子, 上面 [0..Ai] 等概率

在到N之前 每次移动 扔出的步数

求期望扔的次数

答案mod 998244353

范围

n 2e5

ai n-i 也就是不会超过n

2s

1024mb

我的思路

记 f(i) = 首次到i的期望次数

i -> j 的期望步数 = 1/(ai+1) + 2/(ai+1)^2 + 3/(ai+1)^3…

s = sum t/(ai+1)^t, t=1…

s/x = sum t/(x)^{t+1}, t=1…

s/x = -(sum 1/(x)^t)’, t=1…

s/x = -((1/x) 1/(1-1/x))’

s/x = -(1/(x-1))’

s/x = 1/(x-1)^2

s = x/(x-1)^2

s = x/(x-1)^2

s = (ai+1)/ai^2

f(i) = sum(f[j=0….i-1]+s[j], 若 j 能到i)

注意到 f[j]+s[j] 的贡献值与i无关, 只有是否贡献有关, 而是否贡献 还是连续的一段

所以用遍历记录贡献和 和失效处来算?

然而并不对, 样例都过不了

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

#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
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;}

mint ans[200010];
mint rm[200010];

int main(){
  int n = read();
  mint c=0;
  rep(i,0,n-1){
    int ai=read();
    ans[i] = c;
    c-=rm[i];
    mint s = ans[i] + mint(ai+1)/(mint(ai)*ai);
    rm[i+ai] += s;
    c+=s;
  }
  printf("%d\n",c.val());
  return 0;
}

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

F - Erase and Rotate

给一个长n排列A

问不超过k次操作后能得到的最小字典序列

每次操作 可以删除一个数, 或循环右移1个单位

范围

n 2e5

k [0,n-1]

2s

1024mb

我的思路

考虑两种一个是不移动, 从左删除, 那么就是前 k个中取最小, 然后 后面塞入一个, minPQ维护

右侧移动, 也可以确定 首个数字是啥

问题是 当右侧移动时, 可能和删除是同一个, 这个感觉没啥简单的想法去记录

比如样例数据三

如果看成先移动,再删除, 其实会删除移动过的数字

不知道能不能移动+标记+贪心局部?

然后因为k可能比较大,可以从左侧删除和右侧移动 来得到, 所以考虑两个方向来算, 算完了比较?

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

Ex - I like Query Problem

长n序列A

q个操作

类型1, a[l..r] 整除 x

类型2, a[l..r] = x

类型3, 求 sum a[l..r]

范围

8s

1024mb

n 5e5

q 1e5

ai [1,1e5]

x [2,1e5]

我的思路

感觉就线段树啊

(a/x) = (a/(x * y)) 吧

所以记录一下区间 的操作,

问题是求和的话??

另一个思路就是, 记录连续一样的段, 这样每次操作到连续一样的段上, 如果本来就是一致的就直接除就行了, 而不一致的,每个位置的值在重新赋值前最多除log(2,a[i]) 次

似乎就被均摊了?

然后向上搜集的时候, 注意把原来不一样但除了以后一样的也做合并

似乎就没了?