YeXiaoRain Blog(hexo的搜索高亮会破坏latex)

發表於 更新於 分類於 ， Disqus： 文章字數： 1.7k 所需閱讀時間 ≈ 6 分鐘
C (trie树, bit flip)

C

https://atcoder.jp/contests/agc057/tasks/agc057_c

0~ 2^N - 1的排列

问能否通过多次任选操作(每次操作独立,在上一次操作结果基础上), 让数列单调递增, 给出方案

操作1: a[i] = (a[i]+1)%(2^n) , 所有值循环+1

操作2: a[i] = a[i] xor x , 选定一个值,所有值异或它

限制

n<=18

我的思路

显然连续的异或没意义,甚至题目可以改成不是+1,+任意

所以问题变成 穿插的正数个+1和xor能否让数列单调递增, 若能给出方案

考虑所有+1/xor 末尾是1, 都是让所有末尾翻转, 因此结论是 末位前两个互为0/1,后面循环这两个

同理考察第二位,发现(0和2)(1和3)两对,互为0/1,后面的同样按照4个一组循环

同理考察第三位,发现(0和4)(1和5)(2和6)(3和7)四对,互为0/1,后面的同样按照8个一组循环

换句话说, 最低位1个自由元,其它由它决定,第2低位两个自由元,剩余的也是由它决定,第低3位4个自由元,低4位8个自由元…

我想先弄好一部分位再弄剩下的,从高位到低位或从低位到高位,但是 没想到实际怎么操作

题解

设计结构

trie tree

先不看方框, 看树上的边, 从根向叶子的方向, 对应值的从低到高的位

然后关注叶子方框,例如上面的6,二进制下是110,和它的路径是一样的

再看带有n的方框,意思是如果从树上截取某个点作为根来看,如果根表示的是n,那么一条边权是0子节点是2n+0,边权是1的子节点是2n+1, 注意的是这里并不是左右节点,而是由边权决定的

树的结构建好以后, 那么把叶子中再填入初始每个值所在的位置,完成初始化

接下来看+1和xor操作对树进行怎样的修改

+1

+1

因为我们的树是越接近根,对应的位越低,所以+1带来的进位效果也是从根向叶子前进的

如果我们以改变树上边的权值,而不是改变左右指向的视角来看,

那么对于根

0变成1

1变成0且它的子树受到和根一样的处理

这样发现改动的实际上只有log级别个

xor

xor

xor 比 +1 其实好观察,

对于xor二进制对应位为1的层级的0变成1,1变成0

实现

现在我们再回头看目标呢, 也就是位置上和它对应的值是一样的

这里可以思考为啥,是按边上的值来描述而不是左右描述的, 考虑不按照涂上那样初始摆,而是按照叶子直接放初始的值,比如这里0 4 2 6 1 5 3 7位置上对应的值, 在放值时就能明确的知道冲突的情况,排除一些不可能

问题变成了,如何让二叉树边上的0/1 变回 完全二叉树的位置对应的值

考虑把叶子变成 0,1 序列.

如果叶子是反着的1,0, 那么只需要把上面的路径变成 从根到它都是1,这样+1 就能完成修正

修正了所有叶子以后, 问题来了, 还可以通过+1/xor的组合修正非叶子吗

1
2
3
   1       0
 1   0   0   1 ( 其它位还有 不是xor 能解决的情况
0 1 0 1 0 1 0 1 ( 高位全部0,1顺序了

证明不可能, 首先 这种情况, 如果能修正,必定是奇数次操作到该层, 因为 xor不改相对一致性,+每次操作到这两个中的一个就会改,所以这两个操作次数总和必为奇数,考虑它们所覆盖的叶子节点,总操作次数也为奇数

因此要么 xor翻转能得到,要么就是不可能

从逻辑上, 已经完成了,还有个实现问题,如果通过枚举导数第二层,再模拟xor和+1, 虽然+1代价小,但是xor的代价可能达到O(n)的级别, 总的会变成n方

简单的增加一个翻转标识记录行的翻转状态, 因为+1是对单个点翻转,xor是行翻转,翻转两次等于未翻转,都是翻转,所以+1直接让对应位置的节点翻转, 而xor 通过行标识记录,

代码

https://atcoder.jp/contests/agc057/submissions/31596691

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

const int N = 262144;

vector<int> lr(N*4+10,-1); // -1 unset 0:01, 1:10

int a[N+10];

int n;
bool build(int pos,int val,int idx = 1,int pwr = 0){
  if(pwr == n)return true;
  int direction = pos%2;
  int v = direction != val%2;
  if(lr[idx] != -1 && lr[idx] != v){
    return false;
  }
  lr[idx] = v;
  return build(pos/2,val/2,idx*2+direction,pwr+1);
}

int xorcache[20] = {0}; // 不要实际的xor, 修改代价大

vector<int>ans;

void fix(int val){
  // printf("Fix %d\n",val);
  int x = 0;
  {
    int pwr = n-1;
    int v = val;
    while(pwr--){
      if(v%2 == (lr[v/2] ^ xorcache[pwr])){
        x |= (1<<(pwr));
      }
      v/=2;
    }
  }
  // printf("xor %d\n",x);
  if(x){
    ans.push_back(x);
    rep(pwr,0,n){
      if((1<<pwr) & x)xorcache[pwr]^=1; // 标记
    }
  }
  // printf("+1\n");
  {
    int idx = 1;
    rep(pwr,0,n){
      if(lr[idx]^xorcache[pwr]){
        idx=idx*2;
      }else{
        idx=idx*2+1;
      }
      lr[idx/2] ^= 1;
    }
  }
  ans.push_back(-1);
}


int main(){
  cin>>n;
  rep(i,0,(1<<n)){
    scanf("%d",a+i);
  }
  rep(i,0,(1<<n)){
    int r = build(i,a[i]);
    if(!r){
      printf("No\n");
      return 0;
    }
  }
  // rep(i,1,8){
  //   printf("lr[%lld]= %d\n",i,lr[i]);
  // }
  rep(i,(1<<(n-1)),(1<<n)){
    if(lr[i] == 0)continue;
    fix(i);
  }
  int x = 0;
  rep(pwr,0,n){
    if(lr[1<<pwr] ^ xorcache[pwr]){
      x |= 1<<pwr;
      xorcache[pwr] ^= 1;
    }
  }
  if(x){
    ans.push_back(x);
  }
  rep(pwr,0,n){
    rep(i,(1<<pwr),(1<<(pwr+1))){
      if(lr[i]^xorcache[pwr]){
        printf("No\n");
        return 0;
      }
    }
  }
  printf("Yes\n");
  printf("%d\n",(int)ans.size());
  rep(i,0,(int)ans.size()){
    printf("%d ",ans[i]);
  }
  printf("\n");
  return 0;
}

总结

其实我的思路和题解中trie树的结论是一致的,但是我的思路不是trie树形状的,所以再往后推导的阻力更大

一个经验就是对于这种2的幂次的 xor 或 加减操作,可以放在trie树中批量操作, 比如稍微变一变, 就可以变成给你+1/-1/xor操作序列,和询问第idx位置是什么,这样多个操作询问交替的题目

参考

官方题解 https://atcoder.jp/contests/agc057/editorial/3925

發表於 更新於 分類於 ， Disqus： 文章字數： 3.1k 所需閱讀時間 ≈ 10 分鐘
D(冒泡排序, 排列),E(线段树,倍数,贡献,单调栈,离线)

D

https://codeforces.com/contest/1677/problem/D

1到n的排列,进行k次冒泡排序(for i = 0..n-1{if a[i] > a[i+1]: swap(a[i],a[i+1])})以后

每一位与它前面的逆序对个数为v[i]

v[i] = count(a[j] > a[i] && j < i)

现在给定数组v,其中-1表示任意值, 求有多少个原始序列 能k次冒泡排序后,逆序对满足v

答案mod 998244353

保证-1<= vi <=i

范围

t <= 1000

k < n <= 1e6

2s

256MB

题解

观察冒泡排序过程中 逆对的变化

如果a[i]前面有比它大的, 那么一次冒泡排序后,至多有一个移动到它后面, 且a[i]移动到了a[i-1]

因此对于逆序对 v[0] v[1] v[2] ... v[n] 的变化是

如果v[i] > 0 , 那么一次排序后 v[i-1] = v[i]-1

对于v[i] == 0, 0 v[i+1] v[i+2] v[i+3] ... v[j-2] v[j-1] 0, 两个0之间其它非零

注意到上面 非0的结论, (v[i+1]-1) (v[i+2]-1) (v[i+3]-1) ... (v[j-2]-1) (v[j-1]-1) 0 (v[?j+1]-1),

即是这个0会移动到下一个0的前一个位置,a[j-1] = a[i]

所以0-index

最终v[i] == 0 操作前 v[i+k] <= k(反证法) , <= min(k,i)

最终v[i] > 0 操作前 v[i+k] = k

最终v[i] == -1 操作前 v[i+k] 任意(<=i)

最后k位一定是0

综上, 我们可以求得初始的v数组

其中 [0..k-1] 任意

其中 [k..n] 由按上述 平移确定具体情况

接下来讨论排列方案计算方式

如果完全自由就是n!,

考虑从后向前选, 如果位置i不受限制, 那么它有i+1种选法, 相当于每个位置的方案数和下标同增 w[i] = i+1(0-index)

如果它明确知道前面有几个比它小的, 那么只有唯一选法

如果它前面比它小的允许<=k, 那么它有k+1种选法, 相当于[0..k]每个一种

题目保证了v[i] 的范围,所以最多判断一下后k位是否为0即可

代码

https://codeforces.com/contest/1677/submission/156367090

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

typedef long long ll;
#define MOD 998244353
#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;)

int n,k;
int v[1000010];

int main(){
  int t;
  cin>>t;
  while(t--){
    scanf("%d %d",&n,&k);
    rep(i,0,n){
      scanf("%d",v+i);
    }
    ll ans = 1;
    rep(i,0,n){
      if(i < k){ // 前k个自由
        (ans*=i+1)%=MOD;
      }else if(v[i-k] == -1){ // -1 自由
        (ans*=i+1)%=MOD;
      }else if(v[i-k] == 0){ // <=k 即 [0..k] , k+1种
        (ans*=k+1)%=MOD;
      } // v[i-k] != 0 , 唯一选择(从后向前)
    }
    // 最后k个一定是0(也可以-1表示0)
    rep(i,0,k){
      if(v[n-1-i] > 0)ans = 0;
    }
    printf("%lld\n",ans);
  }
  return 0;
}

总结

感觉还是考察 冒泡排序及其性质

参考

https://www.bilibili.com/video/BV1GS4y1b7SD

E

https://codeforces.com/contest/1677/problem/E

给定1到n的排列

q个询问

每次问[l..r] 中有多少子区间, 满足 子区间存在不同的两个数的乘积 等于 子区间最大值

范围

n <= 2e5

q <= 1e6

4s

1024MB

题解

a[1..n]为给的排列

离线, 把所有查询[l..r] 按r升序

for(i = 1..n) 在i == r 时,回答查询[l..r]

线段树, 叶子节点记录[l..j], (j<=r) 有多少个是满足的, 答案就是线段树的区间求和query(o,1,n,l,r)

问题: 遍历过程中i=>i+1时,也就是以i==r作为区间结束时,合法的区间起始l需要+1,但合法的l是散的,不是一个连续的区间, 这样更新复杂度高

考虑加入r时, 左侧比它大的端点的贡献, 首先用单调栈记录(坐标增加,值减少)

vector<pair<value,position>> stk, 其中(stk[i].value = a[stk[i].position])

那么加入{a[r],r} 后会移除值比它小的, 变成

stk[0] ... stk[i-1] stk[i] ... stk[j] {a[r],r}

讨论3部分贡献

  1. 以a[r] 为区间最大值, 那么必然 $(stk[j].position, r]$ 中找最右侧的位置k让a[k..r]中能有两个乘起来等于a[r], 这样, 就有$k-stk[j].position$ 个合法方案

  2. 以stk[i].value为区间最大值, 且stk[i].value 不是a[r]的倍数, $max(k) ,k \in (stk[i-1].position,stk[i].position]$, 贡献为$k-stk[i-1].position$, 因为不是倍数, 显然并不会因为多了a[r] 影响以这个值为最大值的左侧选取的$k$, 所以换个说法就是, 它以原来的贡献又贡献了一轮

  3. 以stk[i].value为区间最大值, 且stk[i].value 是a[r]的倍数, $max(k) ,k \in (stk[i-1].position,stk[i].position]$, 贡献为$k-stk[i-1].position$, 是倍数, 所以需要看stk[i].value/a[r]这个值所在的位置是否会更新k

这样去统计, 单调队列中

考虑变化

如果我们每个线段树节点记录了 (对右侧贡献的左端点数量x, 总贡献数c)

(x0,c0) => (x1,c1) 是怎么变化的呢

x1 = x0 + 那些a[r]倍数中超出来的长度

c1 = c0 + x1

注意的是, 可以lazytag记录有多少轮没有向下, 每次修改log级别个节点就行了

(这个方法感觉有实现问题, 我尝试做了一下,发现每次需要 c += x, 但是因为lazytag 的关系, 你一个节点上只能保存常数个x 和 常数个次数记录, 对于在 dep 层 的变化, lazytag down到dep+1层会覆盖x, 换句话说 lazy 的部分和历史每个节点内的x相关

官方的代码, 记录的是(x0,y0)

y0 = c0 - x0 * 轮次, y1 = c1 - x1*(轮次+1) = (x1+c0) - x1*(轮次+1) = y0 - (x1-x0) * 轮次

比记录和好的是,在不更新时(x,y)不会变,而c会变, 每次更新后所有节点都是正确的值, 因为lazy的部分只和当前轮次相关, 而这些轮次加和以后, 就是y的变化量

注意到 lazy的部分 (x1-x0) 要么是len要么是-len, 所以把符号给到轮次上, lazy轮次的和即可

而不是全覆盖的部分, 直接去更新到准确的(x,y)

代码

官方代码+注释

https://codeforces.com/contest/1677/submission/156392477

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
const int N=2e5;
#define SEG_ROOT 1,1,n
#define SEG_L (o<<1)
#define SEG_R (o<<1|1)
#define mid (l+r)/2
#define SEG_L_CHILD SEG_L,l,mid
#define SEG_R_CHILD SEG_R,mid+1,r
#define SEG_L_CHILD_Q SEG_L,l,mid,ql,qr
#define SEG_R_CHILD_Q SEG_R,mid+1,r,ql,qr
int n; // 数组长度
int a[N+10]; // 原始排列 1-index
int a2i[N+10]; // 值到下标 a2i[value] = index
int di; // 单调栈的尾部下标
int d[N+10]; // 单调栈,存的原数组的下标 1-index, d[stack-index] = a-index
int i2di[N+10]; // [a中下标] = 栈中下标 映射  i2di[a-index] = stack-index , 0(表示不在栈中)
int ti; // 当前遍历的个数 = i-1 or i
int p[N+10]; // p[stack-index] = 左侧最大合法a-index
ll ans[1000005]; // 询问的答案数组
vector<pair<int,int> >q[1000005]; // 询问 q[right] = vector<pair<left,query index> >
vector<int> w[N + 10]; // 因数分解 w[value]= vector<value的因数>
struct seg {
  // 答案 = x * ti + y
  ll x; // 合法的左端点位置数
  ll y; // (真实答案 与 x*ti 之间补充的差), 辅助变量, 因为直接记录答案无法维护x, 同理也可以记录(真实答案,x), y = 该段贡献 - x*ti, (x0,y0)=>(x1,y1) : (y0+x0*ti) + x1 = (y1+x1*(ti+1)), y1 = y0 - (x1-x0)*ti
  ll tg; // 未向下传递的ti的和, y += (+/- ti) * len
  ll len; // 对应区间长度 简化书写
} tr[N*4 + 10];
// 初始化 线段树, 只有设置len = 区间长度,其它x,y,tg全为0
void make(int o,int l,int r){
  tr[o].len=r-l+1;
  if (l==r) return;
  make(SEG_L_CHILD);
  make(SEG_R_CHILD);
}
// lazy tag 下降
void down(int o) {
  // x
  if (tr[o].x == tr[o].len) {
    tr[SEG_L].x = tr[SEG_L].len;
    tr[SEG_R].x = tr[SEG_R].len;
  }
  if (tr[o].x==0) {
    tr[SEG_L].x=0;
    tr[SEG_R].x=0;
  }
  // 能向下的tag一定是区间全覆盖的
  if(tr[o].tg != 0){
    assert(tr[o].x == tr[o].len || tr[o].x == 0);
    // y, 如下clear和add 同样的 y += tg * len
    tr[SEG_L].y+=tr[o].tg*tr[SEG_L].len;
    tr[SEG_R].y+=tr[o].tg*tr[SEG_R].len;
    // tg
    tr[SEG_L].tg+=tr[o].tg;
    tr[SEG_R].tg+=tr[o].tg;
    tr[o].tg=0;
  }
}
// 更新 o
void up(int o) {
  tr[o].x=tr[SEG_L].x+tr[SEG_R].x; // 贡献数
  tr[o].y=tr[SEG_L].y+tr[SEG_R].y; // 修正值
}
// 保证 tr[o].x == tr[o].len
void clear(int o,int l,int r,int ql,int qr) {
  if (ql <= l && r <= qr) {
    // 贡献变化 tr[o].x * ti + tr[o].y => 0 * ti (当前轮) + (tr[o].y + ti * tr[o].len)
    // (tr[o].y + ti * tr[o].len) - (tr[o].x * ti + tr[o].y)
    // = ti * (tr[o].len - tr[o].x)
    // = 0
    assert(tr[o].x == tr[o].len);
    tr[o].tg+=ti; // 选中 -> 未选 未向下传递的, 对于下一级来说,也是 y+=ti*(len-x), 所以+ti传下去
    tr[o].y += ti*tr[o].len;// y += ti * x => y += ti * len
    tr[o].x=0;
    return;
  }
  down(o);
  if (ql<=mid) clear(SEG_L_CHILD_Q);
  if (qr>mid) clear(SEG_R_CHILD_Q);
  up(o);
}
// [ql..qr] 现在合法
// 保证了 tr[o].x == 0
void add(int o,int l,int r,int ql,int qr) {
  if (ql <= l && r <= qr) {
    // 贡献变化 tr[o].x * ti + tr[o].y => tr[o].len * (ti+1) 下一轮 + (tr[o].y - ti * tr[o].len)
    // (tr[o].len * (ti+1) + tr[o].y - ti * tr[o].len) - (tr[o].x * ti + tr[o].y)
    // = tr[o].len - (tr[o].x * ti)
    // = tr[o].len
    assert(tr[o].x == 0);
    tr[o].tg += -ti; // 未选 -> 选中 未向下传递的
    tr[o].y += -ti*tr[o].len; // y += -ti*(len - x) => y+= -ti * len
    tr[o].x=tr[o].len;
    return;
  }
  down(o);
  if (ql<=mid) add(SEG_L_CHILD_Q);
  if (qr>mid) add(SEG_R_CHILD_Q);
  up(o);
}
ll find(int o,int l,int r,int ql,int qr) {
  if (ql <= l && r <= qr) return tr[o].y+ti*tr[o].x; // 如segtree的设计定义
  down(o);
  ll ret = 0;
  if (ql<=mid) ret+=find(SEG_L_CHILD_Q);
  if (qr>mid) ret+=find(SEG_R_CHILD_Q);
  return ret;
}
int main() {
  int m; // 询问次数
  scanf("%d%d",&n,&m);
  // 读入排列
  rep(i,1,n+1){
    scanf("%d",&a[i]);
    a2i[a[i]]=i;
  }
  // 读入询问
  rep(i,1,m+1) {
    int l,r;
    scanf("%d%d",&l,&r);
    q[r].emplace_back(l,i);
  }
  // 因数
  rep(i,1,n+1)
    for (int j=i;j<=n;j+=i)
      w[j].emplace_back(i);
  // 初始化 线段树, 只有设置len = 区间长度,其它x,y,tg全为0
  make(SEG_ROOT);
  rep(i,1,n+1) { // a[i]
    while (di && a[d[di]]<a[i]) { // 新加入的值, 比单调栈中的最小的小, 移除操作
      if (p[di]>d[di-1]) clear(SEG_ROOT,d[di-1]+1,p[di]); // 从贡献标记为不贡献, 但是对于总的贡献不变
      // 出栈
      i2di[d[di]]=0;
      di--;
    }
    for (int j=a[i];j<=n;j+=a[i]) { // j = a[i] 的倍数, j 作为最大值时
      int k=i2di[a2i[j]]; // j在栈中下标
      if (!k) continue; // 不在栈中
      int l=d[k-1]+1,r=d[k]; // 左端点在范围 a[l..r] 中
      int e=a2i[j/a[i]]; // 乘起来等于j的另一个因数在a中的下标
      if (e<l || e>=i) continue; // e 在范围 a[l..i) 中, 不能选同一个ie平方
      e=min(e,r); // 左端点范围的最大值 a[l..e]
      if (e<=p[k]) continue; // p[k] 最大值不更新
      // a[l..p[k]] 合法 => a[l..e] 合法
      add(SEG_ROOT,p[k]+1,e); // 把[p[k]+1,e] 从不贡献变成贡献, 更新到本轮结束时该有的(x,y)
      p[k]=e;
    }
    // 入栈
    d[++di]=i;
    i2di[i]=di;
    p[di]=d[di-1]; // 初始化p[di]表示以a[i]作为峰, 左侧端点不贡献
    for (auto j:w[a[i]]) { // 枚举 因子对 (j,a[i]/j)
      int l=d[di-1]+1;
      // int r=i;
      int e1=a2i[j];
      int e2=a2i[a[i]/j];
      if (e2<=e1) continue; // 减少重复计算,主要是不等于
      if (e1<l || e2>i) continue; // [l-1..e1..e2..i+1]
      if (e1<=p[di]) continue; // 不会更新可行值 [p[di] .. e1 .. i]
      add(SEG_ROOT,p[di]+1,e1); // 从不贡献记为贡献, 更新到本轮结束时该有的(x,y)
      p[di]=e1; // 更新
    }
    ti++;
    for (auto t:q[i]) ans[t.second] = find(SEG_ROOT,t.first,i); // 查询[l = t.first,r = i]
  }
  rep(i,1,m+1) printf("%lld\n",ans[i]);
  return 0;
}

总结

学会了一下新的线段树写法,以前我在左右拆点的时候, 会根据覆盖决定是

(ql,qr) => (ql,qr) 还是(ql,qr) => (ql,mid) 还是 (ql,qr) => (mid+1,qr) 终止条件是l == ql && r == qr

这里学到了把终止条件改成ql <= l && r <= qr, 这样的话, 传参就不用拆了(ql,qr) => (ql,qr)

参考

https://codeforces.com/contest/1678/attachments/download/16086/Codeforces%20Round%20789%20Editorial%20in%20Chinese.pdf

https://codeforces.com/blog/entry/102631

https://www.bilibili.com/video/BV1GS4y1b7SD

發表於 更新於 分類於 ， Disqus： 文章字數： 2.1k 所需閱讀時間 ≈ 7 分鐘
C(构造),D(频率频次, 贡献统计, 二项式分布)

C

https://atcoder.jp/contests/arc139/tasks/arc139_c

nxm格子选尽可能多的点

让每个点(x,y)的(x+3y)互不相等

且每个点(x,y)的(3x+y)互不相等

n,m <= 1e5

题解

我的思路是, 这相当于做的线性变换

每个点变成 (x,y) => (3x+y,x+3y)

要结果的点 的横纵坐标互不相等

那么原来是矩形的点, 映射后变成了斜着平行四边形的点

然后想办法尽可能多的找点, 但是我可能点画得不算多, 没有找到规律

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import matplotlib.pyplot as plt

x = []
y = []

for i in range(1, 10):
    for j in range(1, 10):
        x.append(3*i+j)
        y.append(i+3*j)

plt.plot(x, y, 'ro')
ax = plt.gca()
ax.set_xlim(0)
ax.set_ylim(0)
ax.xaxis.set_minor_locator(plt.MultipleLocator(1))
ax.yaxis.set_minor_locator(plt.MultipleLocator(1))
plt.grid(which='minor')
plt.show()

1

先考虑特殊情况足够大

那么对于 3x+y 有没有可能尽量排满

两种办法让3x+y 的增量为1

(x,y) => (x,y+1)

(x,y) => (x+1,y-2)

比较神奇的是

如果你考虑x+3y每次增加1的方案,是对称的

(x,y) => (x+1,y)

(x,y) => (x-2,y+1)

那么如图, 两个方法选的点(蓝色路线 和 绿色路线) 是一样的

2

因此, 如果刚好 N=M, 且N是奇数, 就按照这个方法去选即可, 这样相当于把所有可能的(x+3y),(3x+y)的值都取到了

非一般情况, 首先N,M 是可以轮换

所以不妨设 N<=M

注意最大的个数,会被min(3n+m,n+3m) 限制, 也就是点的上界

但是如果短的边也是奇数的话

可以这样操作

3

这样即满足题意, 又达到了上界

两边不等,但是短边是 偶数长度

5

这样即满足题意, 又达到了上界

还有一个情况

两边相等,但是 是偶数长度

4

如图, 距离上界还差4个, 但是看起来按现有的选法最多再选3个

下面证明 就是差一个

首先如果 N=2 , 那么M=2 最多选取 NM = 3N+M-4个

对于 N >= 4,且为偶数

S = 从(3,1)开始, 通过多次 (+1,-3) / (+3,-1) 到达的所有点

注意到 这个集合中 其实就是 转换坐标轴后以 (3,1) 开始,同纵坐标,和同横坐标,反复关联的点

6

而这些点,在x上的可选值 为 N/2-1, y上的可选值为N/2, 也就是S中的点本身是互相影响的点,而这些点占了N/2个位置,最多却只能选N/2-1, 因此 总的上界也是比范围小一

所以 不论N=2还是N>=4 的偶数情况, 上述少选一个的方案 既能达到 又是上界

代码

(无)

参考

官方题解 https://atcoder.jp/contests/arc139/editorial/3863

Youtube官方 https://www.youtube.com/watch?v=tIdPBN2x6KU

D

https://atcoder.jp/contests/arc139/tasks/arc139_d

长度为n的有序数组a

每次操作, 选择[1~m]中的一个插入并保持有序, 删除下标为X的数(1-index)

进行k次操作的所有结果的剩余数组元素的和, 模 998244353

范围

n,m,k <= 2000

$X \in [1,n]$

$a_i \in [1,m]$

2s

1024MB

我的思路

如果知道 最后结果数组中, 位置i 为v 的出现次数,那么 最后只需要求和即可

cnt(a[i] == v)

注意到 a一直是有序的,也就是 cnt(a[i] == v) 也意味着 a[i..n] >= v

cnt(a[i] == v) = cnt(a[i..n] >= v) - cnt(a[i..n] >= v-1)

把指定位置等于 转化成 指定范围大于等于, 就能更容易进行状态转移了

dp[0..k][1..n][1..m]

dp[itr][idx][v] = 第itr次操作后, 从idx到n 都大于等于v的方案数

注意到 转移的系数和 itr 无关,所以可能可以矩阵快速幂

但是我没推出来

官方题解翻译

如果 对于$\forall v \in [1..m]$ 我们能找到结果中 $\leq v$ 的数出现的次数 的期望(频次 = 总次数 * 频率), 那么就能计算答案了(和上面我思路同理 都是 等于转化成 大于等于/小于等于)

题意转换:

对于一个指定的$v$

给定 $x \in [0,N]$

$x$的意义是初始数组中 $\leq v$的个数

操作: 概率$p = \frac{v}{m}$ 让x=x+1, 如果 $x\ge X$ , 让x=x-1

意义是 有概率$p$ 选择不超过$v$的数, 那么个数加一

如果 总个数 大于 删除下标, 那么 必定被删除一个, 那么个数减一

找到执行了$K$次操作后, $x$的期望值

也就是 剩下 $\leq v$ 的个数

注意到$|x - (X-1)|$ 会单调递减

换句话说, 如果 $初始x > (X-1)$ 那么$初始x \ge 最终x \ge (X-1)$

如果 $初始x < (X-1)$ 那么$初始x \leq 最终x \leq (X-1)$

$初始x$ 是从输入的a中统计的

如果我们指定了最终的x, 那么得到这个x的 概率可以用二项式系数和幂次得到

设 初始值为$x_0$, 最终为$x_1$

若 $x_0 \leq x_1 < X-1$

也就是$k$次 操作中 $x_1 - x_0$ 次增加了1, 其它时候全未增加

概率为 $C(k, x_1-x_0) \cdot p^{x_1-x_0}(1-p)^{k-(x_1-x_0)}$

若 $x_0 < x_1 = X-1$ (如果 都是$X-1$那概率就是1)

也就是$k$次 操作中 至少$x_1 - x_0$ 次增加了1, 其它时候任意

概率为 $\sum_{i=0}^{k-(x_1-x_0)} C(k, x_1-x_0 + i) \cdot p^{x_1-x_0 + i}(1-p)^{k-(x_1-x_0 + i)}$

看起来难算, 但是因为 上面的$x_1 \neq X-1$的和$x_1 = X-1$构成了所有情况, 所以实际上直接 1减去上面概率和就是剩下概率

对于$初始x_0$大于$X-1$的同理

其中组合数可以预处理,幂次可以快速幂

综上 可算

代码

https://atcoder.jp/contests/arc139/submissions/31271889

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 998244353
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

ll a[2010];
ll pro[2010][2010]; // [v][cnt] 结果 <= v 的有cnt个的概率
ll c[2010][2010];

ll mypow(ll v,ll pwr){
  v=(v+MOD)%MOD;
  ll r = 1;
  while(pwr){
    if(pwr%2)(r*=v)%=MOD;
    (v*=v)%=MOD;
    pwr/=2;
  }
  return r;
}

// C(m,n) = m!/(n!(m-n)!)
ll C(ll m,ll n){
  if(n > m)return 0;
  return c[m][n];
}

int main(){
  rep(i,1,2005){
    c[i][0] = c[i][i] = 1;
    rep(j,1,i){
      c[i][j] = (c[i-1][j-1] + c[i-1][j])%MOD;
    }
  }

  ll n,m,k,x;
  cin>>n>>m>>k>>x;
  ll invm = mypow(m,MOD-2);
  x--; // 先减1
  rep(i,0,n){
    scanf("%lld",a+i);
  }
  sort(a,a+n);
  rep(v,1,m+1){
    int stx = 0;
    rep(i,0,n){
      if(a[i] <= v)stx++;
      else break;
    }
    if(stx == x){ // 结果必定 x
      pro[v][x] = 1;
      continue;
    }
    // p = v/m
    ll p = v * invm %MOD;
    rep(endx,0,n+1){
      if(stx < x){ // stx <= endx <= x
        if(stx <= endx && endx < x){
          // C(k,endx-stx) * p^(endx-stx) * (1-p)^(k-(endx-stx))
          pro[v][endx] = C(k,endx-stx) * mypow(p,endx-stx) %MOD * mypow(1-p,k-(endx-stx)) % MOD;
        }
      }else { // stx > x => stx >= endx >= x
        if(stx >= endx && endx > x){
          // C(k,stx-endx) * (1-p)^(stx-endx) * p^(k-(stx-endx))
          pro[v][endx] = C(k,stx-endx) * mypow(1-p,stx-endx) %MOD * mypow(p,k-(stx-endx)) % MOD;
        }
      }
    }
    // 最后处理 (endx == x) , 等于 1-其它概率和
    pro[v][x] = 1;
    rep(endx,0,n+1){
      if(endx == x)continue;
      (pro[v][x] -= pro[v][endx])%=MOD;
    }
  }
  ll leqv[2010] = {0};
  ll ans = 0;
  rep(v,1,m+1){
    rep(cnt,0,n+1){
      (leqv[v] += cnt*pro[v][cnt]%MOD)%=MOD; // 期望长度 = sum{期望*长度}
    }
    (ans += v*(leqv[v] - leqv[v-1]) %MOD)%=MOD; // count( == v) = count(<= v) - count(<= v-1)
  }
  printf("%lld\n", ((ans * mypow(m,k)%MOD)+MOD)%MOD); // 频次 = 总次数 * 频率
  return 0;
}

总结

相对于以前不会 count(x = v) = count(x >= v) - count(x >= v+1) = count(x <= v) - count(x <= v-1) , 已经算是有进步,能想到转换了

  1. 但是 对于上面 转换成概率 和 小于统计的想法还是不够, 一个是 想用坐标表示而不是明确的值的分界线表示, 题解就没有坐标作为键,只是把坐标作为值

  2. 虽然从频次上也能算,但是上到概率,推概率公式,算出概率再转换成频次都会容易进入思路, 需要增加 频次和概率之间的转换意识

参考

官方题解 https://atcoder.jp/contests/arc139/editorial/3860

Youtube官方 https://www.youtube.com/watch?v=tIdPBN2x6KU

發表於 更新於 分類於 ， Disqus： 文章字數： 232 所需閱讀時間 ≈ 1 分鐘
F(暴力 组合数)

F. Permutation Counting

https://codeforces.com/contest/1671/problem/F

t 组测试

问 [1~n]的所有排列中

x个相邻逆序对, k个逆序对 有多少个, 答案取mod 998244353

范围

t <= 3e4 组测试

n <= 998244353 - 1

k <= 11

x <= 11

4s

512MB

题解

k和x很小, 所以不在它原本位置的数字少, 且离原来位置也近

直接暴力算出 12! 的所有排列,记录 其中 (k,x) 和长度

那么答案相当于 把这些排列 插入到有序数字中

所以 再计算一个组合数

需要注意的是, [1~10] 的排列 可能是由 [1-4][1-6] 的排列组成的, 所以 要注意不可分割的排列统计, 或者插入的时候 不支持相邻

代码

无

总结

暴力和关联性的思路对了, 但为啥我在想矩阵乘法而不是组合数,让我自己卡住了

参考

官方

發表於 更新於 分類於 ， Disqus： 文章字數： 1.2k 所需閱讀時間 ≈ 4 分鐘
F(你真的会二分吗)

题目

https://codeforces.com/contest/1661/problem/F

给你n个线段

问最少切多少次,让切割后所有线段长度平方和不大于m

范围

n<=1e5

线段长度和 <= 1e9

m <= 1e18

7s

512MB

题解

尝试

对于最外层的答案, 显然二分答案

那么问题变成了 如果指定切割k次, 能否满足条件

贪心: 从小到大, 判断剩余期望与已切割, 显然如果 当前 乘上段数 不大于剩余值, 那么不需要切割, 否则任意不合法必定存在比当前段更大的值, 要切也是切更大的

一定不切割的状态 能证明了, 但是不是这种状态时,可能切割也可能不切割, 即使切割, 怎么计算次数也不知道

https://codeforces.com/contest/1661/submission/153691360

例如两个线段 3,4, 要结果小于17, 最好的办法是均分4, 而这种没有对应的贪心规则, 上述方法不能判断

另一个正确但是会超时的思路是

我们如果知道一个具体的段,要切割成多少份, 那么显然可以数学O(1)就算出这一段切割的最小值,(切割出来的尽量相等)

那么一个段 从 k次变成k+1次 它带来的变化量也是 上述计算相减,也是O(1)的

那么 我们直接维护优先队列 (多切割一次代价,线段编号,当前切割次数), 这样每次取最大的切一下,放回去

复杂度就是 O(线段长度和), 也能直接计算出k次最优

问题是O(线段长度和)的计算代价, 甚至说这就是枚举答案了,外层的二分都没意义了

题解

注意到 一个线段 随着切割次数变多, 每次贡献的代价也是单调递减的!!!!!!

再结合上面的 优先队列思路, 其实就是选取了k次最大值, 那么也就是 被选的 >=x, 未被选的 <= x

也就变成了找x, 满足如果被选的都是 大于x 则不满足题意,且如果被选的都是 大于等于 x 则满足题意

那么个数也就自然 是 大于x的个数,加上 与目标差距 除以 x 向上取整了

代码

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n;i-->a;)
#define pb push_back
const double pi = acos(-1.0);

// 0 < a1 < a2 < a3..an 传送点
// 传送消耗 (ai-aj)**2 能量
// + 一些整数点 => a0 -> an 能量消耗 <= m
// 最小整数点个数

ll a[200010];
vector<ll> segs ;
int n;
ll m;

ll f(ll len, ll part){
  if(part > len)return len;
  ll minv = len/part;
  ll maxcnt = len%part;
  // printf("f(%lld %lld) => %lld %lld => %lld\n",len,part,minv,maxcnt,minv*minv*(part - maxcnt) + (minv+1)*(minv+1) * maxcnt);
  return minv*minv*(part - maxcnt) + (minv+1)*(minv+1) * maxcnt;
}

// 大于等于x的贡献都选
pair<ll,ll> calc(ll x){ // 切割次数, 消耗平方值
  assert(x > 0);
  ll cnt = 0; // 个数
  ll sum = 0; // 消耗
  rep(i,0,n){
    if(x <= 2){
      sum += f(segs[i],1) - f(segs[i],segs[i]); // 1*1*segs[i];
      cnt += segs[i] - 1;
      continue;
    }
    // 最大的都不满足
    if(f(segs[i],1) - f(segs[i],2) < x){
      continue;
    }
    // 二分切割的段
    int l = 1, r = segs[i]; // l 满足 r 不满足
    while(l+1<r){
      int mid = (l+r)/2;
      if(f(segs[i],mid) - f(segs[i],mid+1)>= x){
        l = mid;
      }else{
        r = mid;
      }
    }
    sum += f(segs[i],1) - f(segs[i],r);
    cnt += l;
  }
  return {cnt,sum};
}

int main(){
  ll cost = 0;
  scanf("%d",&n);
  rep(i,1,n+1){
    scanf("%lld",a+i);
    segs.push_back(a[i]-a[i-1]);
    cost += (a[i] - a[i-1])*(a[i] - a[i-1]);
  }
  scanf("%lld",&m);
  if(cost <= m){
    printf("0\n");
    return 0;
  }
  // 找的是 x 不是答案
  // l 满足 r 不满足
  ll l = 0, r = 1'000'000'000'000'000'000;
  while(l+1<r){
    // printf("[%lld %lld]\n",l,r);
    ll mid = (l+r)/2;
    if(calc(mid).second >= cost - m){
      l = mid;
    }else{
      r = mid;
    }
  }
  assert(l != 0);
  auto [c,s] = calc(r); // x+1 的所有
  printf("%lld\n",c + (cost - m - s)/l + !!((cost - m - s)%l));
  return 0;
}

总结

里面这个 二分好像很有用, 感觉之前做PE应该遇到过类似的,但是没想到二分,唉 我好蠢啊

数学证明

其实这里有一个东西 没有严格证明

就是 f(x,k) - f(x,k+1) 随着k增大而减小

难就难在它是整数划分, 如果是实数的话, 直接分析导数即可

dreamoon

jiangly

简单的说, 把 (x,k-1)的方案 和 (x,k+1)的方案拼在一起, 那么它一定是 2x 分割2k块的一个方案

那么 显然 (x,k)的方案的两倍 恰好是(2x,2k)的最优解

因此 2f(x,k) <= f(x,k-1) + f(x,k+1) 即

f(x,k-1) - f(x,k) >= f(x,k) - f(x,k+1) 得证

参考

https://blog.csdn.net/Code92007/article/details/124089868

0%