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

發表於 更新於 分類於 Disqus： 文章字數： 934 所需閱讀時間 ≈ 3 分鐘

好久不登洛谷了, 最近翻了一下之前的一个帖子, 当时应该有其他事 没后续跟进了

题目

https://www.luogu.com.cn/problem/P1036

n个数

选k个出来和是质数的方案数

范围

n<=20

ai<=5e6

1s

128MB

题解

数筛TLE

https://www.luogu.com.cn/record/25067342

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 ten5 100000+10
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define iif(c,t,f) ((c)?(t):(f))
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
const double pi = acos(-1.0);

bool p[100000010];
int ans = 0;
int a[30];
int n,k;

void dfs(int idx,int picked,int cnt){
  if(picked == k){
    ans+=!p[cnt];
    return ;
  }
  if(n - idx < k-picked)return ;
  dfs(idx+1,picked+1,cnt+a[idx]);
  dfs(idx+1,picked,cnt);
}

int main(){
  cin>>n>>k;
  rep(i,0,n){
    scanf("%d",a+i);
  }
  p[1] = 1;
  rep(i,2,10001){
    if(p[i] == 1)continue;
    for(int j=i*i;j<100000001;j+=i){
      p[j] = 1;
    }
  }
  dfs(0,0,0);
  cout<<ans<<endl;
  return 0;
}

循环到根号n判质数竟然过了?而且搜到的一堆题解都是这样做

https://www.luogu.com.cn/record/25067748

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

typedef long long ll;
#define ten5 100000+10
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define iif(c,t,f) ((c)?(t):(f))
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
const double pi = acos(-1.0);

//bool p[100000010];
int ans = 0;
int a[30];
int n,k;

bool pp(int v){
  if(v==1)return 1;
  int maxv = int(sqrt(v))+2;
  rep(i,2,maxv){
    if(v%i==0 && v!=i){
      return 1;
    }
  }
  return 0;
}

void dfs(int idx,int picked,int cnt){
  if(picked == k){
    // ans+=!p[cnt];
    ans+=!pp(cnt);
    return ;
  }
  if(n - idx < k-picked)return ;
  dfs(idx+1,picked+1,cnt+a[idx]);
  dfs(idx+1,picked,cnt);
}

int main(){
  cin>>n>>k;
  rep(i,0,n){
    scanf("%d",a+i);
  }
  // p[1] = 1;
  // rep(i,2,10001){
  //   if(p[i] == 1)continue;
  //   for(int j=i*i;j<100000001;j+=i){
  //     p[j] = 1;
  //   }
  // }
  dfs(0,0,0);
  cout<<ans<<endl;
  return 0;
}

问题

虽然当时发了帖子, 但是里面都在喷我表达不规范 XD, 没人给我说是数据其实很小的问题

https://www.luogu.com.cn/discuss/153208

数筛 是$O(sum + 2^n)$

而上面AC的代码是$O(max(2^n, sqrt(sum) \cdot 2^k))$

如果真如题目所说的数据范围, 其实数筛更有可能过大数据, 然而实际数筛TLE了

也有老哥说n实测出来最大是7,(7的话那的确第二种没啥问题), 那题目说你妈n<=20呢?

https://www.luogu.com.cn/discuss/347995

造数据

通过简单的尝试,生成了以下数列

1
2
for i in range(20):
  print(5000000-1-6*i)
1
2
20 11
4999999 4999993 4999987 4999981 4999975 4999969 4999963 4999957 4999951 4999945 4999939 4999933 4999927 4999921 4999915 4999909 4999903 4999897 4999891 4999885

这数据下

数筛0.88s

后面方法1.022s

电脑配置i7-7700HQ

编译命令clang++ -o Main Main.cpp -std=gnu++17 -O2 -g -Wall -Wcomma -Wextra -fsanitize=integer,undefined,null,alignment

真题解 Miller robin + 特殊判定序列, 这个可以极快判定64位以内的质数

https://www.luogu.com.cn/record/73708925

关于质数判别之前做PE时也写过

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

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

ll quick_p(ll b, ll p,const ll mod){
  ll r = 1;
  while(p){
    if(p%2)(r*=b)%=mod;
    (b*=b)%=mod;
    p/=2;
  }
  return r%mod;
}

ll mr(ll base,ll v){
  if(base > v)return true;
  ll startp = v-1;
  while(startp%2 == 0)startp>>=1;
  ll p = startp;
  ll r = quick_p(base,p,v);
  while(p != v-1){
    if(r == v-1)return true;
    if(r == 1)return p == startp;
    p*=2;
    // overflow
    (r*=r)%=v;
  }
  return false;
}

bool is_prime_64(ll v){
  if(v < 2)return false;
  if(v < 4)return true;
  // %6 = 1 or 5
  if((v % 6) % 4 != 1)return false;
  ll test_g[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
  rep(i,0,7){
    if(!(mr(test_g[i],v)))return false;
  }
  return true;
}

int ans = 0;
int a[30];
int n,k;

void dfs(int idx,int picked,int cnt){
  if(picked == k){
    ans+=is_prime_64(cnt);
    return ;
  }
  if(n - idx < k-picked)return ;
  dfs(idx+1,picked+1,cnt+a[idx]);
  dfs(idx+1,picked,cnt);
}

int main(){
  cin>>n>>k;
  rep(i,0,n){
    scanf("%d",a+i);
  }
  dfs(0,0,0);
  cout<<ans<<endl;
  return 0;
}

發表於 更新於 分類於 ， Disqus： 文章字數： 396 所需閱讀時間 ≈ 1 分鐘
F(Math only)

题目

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

长度n的0/1串

找多个不重叠子串满足

  1. 0/1比例和原串一致
  2. 长度和为m

范围

m <= n <= 2e5

1s

256MB

题解

Math

https://t.bilibili.com/646605883381383189

  1. 字符串拼成环
  2. 长度为m的1的个数,在相邻统计中变化最多为1, 所有的1个数和=m乘总的1的个数, 因此对于长度为m的1的个数 不会都大于目标也不会都小于目标,至少一个等于目标

长度为m的在原数组内则一个, 跨了原数组边界则两个

很明显不满足的我想到了,一个的很好做滑动窗口入门

但是我一直在想怎么证明 两个一定可以, 想了 单测大于小于, 全局不满足,但始终没想到 拼成环就容易搞了, 哎

代码

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

#define rep(i,a,n) for (int i=a;i<n;i++)
#define pb push_back

char s[200010];
int n,m;

void work(){
  scanf("%d %d",&n,&m);
  scanf("%s",s);
  int cnt1 = 0;
  rep(i,0,n){
    cnt1+=s[i] == '1';
  }
  if((cnt1 * m ) % n != 0){
    printf("-1\n");
    return ;
  }
  int x = (cnt1*m)/n;
  int c = 0;
  rep(i,0,m){
    c += s[i]=='1';
  }
  rep(i,0,n){
    if(c == x){
      if(i <= n-m){
        printf("1\n");
        printf("%d %d\n",i+1,i+m);
      }else{
        printf("2\n");
        printf("%d %d\n",1,m-(n-i));
        printf("%d %d\n",i+1,n);
      }
      return ;
    }
    c += s[(i+m)%n]=='1';
    c -= s[i]=='1';
  }
}

int main(){
  int t;
  cin>>t;
  while(t--)work();
  return 0;
}

总结

Math啊 Math, 我怎么就想不出呢

看jiangly老哥的视频,他只想了15min

参考

官方题解

發表於 更新於 分類於 ， Disqus： 文章字數： 1.6k 所需閱讀時間 ≈ 5 分鐘
F(2-SAT,tarjan,scc)

题目

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

一个树上,每个点有小写字母

q个描述(<=4e5)

ai,bi 的简单路径得到字符串si , 注意方向可能a到b,也可能b到a

求一种满足上述所有描述的一种方案,或输出无法满足

范围

点数不超过4e5

字符串长度和不超过4e5

9s

1GB

题解

2-SAT

对于被字符串覆盖到的点, 如果正反字符相等,那么必定是这个字符

如果不等那么它也只有两种可能

于是问题变成了每个点有两种可能,并且选中其中一个时会决定它被覆盖的字符串上其它点的选择

这就是2-sat问题(每个点0/1 , 选定情况会决定其它的点情况,找一种可行方案)

2-sat问题的解法就是 建立有向图(注意这里是全部双向关系) ,求最大联通分量缩点,看是否有矛盾(一个点同时选了两个不同字符)

注意这里字符串在转化成图之前, 额外操作就是多个字符串覆盖到同一个点时, 有时能直接确定哪个字符是有效的,无效字符可以在转化前确定一部分

处理也很直白,同字符唯一确定,不同字符两个可能,多个字符串覆盖, 需要一个字符出现次数刚好是多个字符出现总次数一半

最大联通分量scc

上述处理以后就是scc的求解,这直接上tarjan

tarjan 主要就是

dfn 深度搜索访问记号

low 最小可达的前向点记号

stk 当前访问栈

res 结果数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
tarjan(u){
    DFN[u] = Low[u] = ++Index//为节点u设定次序编号和Low初值
    Stack.push(u) //将节点u压入栈中
    for each(u,v) in E //枚举每一条边
        if (v not visited) //如果节点v未被访问过
            tarjan(v) //继续向下找
            Low[u]=min(Low[u],Low[v])
        else if (v in S) //如果节点v还在栈内
                Low[u]=min(Low[u], DFN[v])
    if ( DFN[u] == Low[u] ){ //如果节点u是强连通分量的根
        component = {}
        repeat{
            v = S.pop//将v退栈，为该强连通分量中一个顶点
            component.append(v)
            until( u == v)
        }
        print component
    }
}

代码

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
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(n);i++)
#define per(i,a,n) for (ll i=(ll)n-1;i>=a;i--)
#define pb push_back

const int N = 400000;
vector<int> p2[N+10];
int dep[N+10];
int fa[N+10];
char s[N+10];
map<char,vector<int> > p2charid[N+10];
vector<pair<int,char> > id2pchar;
vector<int> id2scc;
vector<vector<int> > scc2ids ;
vector<bool> vis ;
char ans[N+10];

class Tarjan{
  vector<int> low;
  vector<int> dfn;
  stack<int> stk;
  vector<int> res;
  vector<vector<int> > p;
  int n;
  void scc(int v) {
    static int id = 0;
    low[v] = dfn[v] = ++id;
    stk.push(v);
    for(auto w:p[v]){
      if(!dfn[w]){ // 未访问过
        scc(w);
        low[v] = min(low[v],low[w]);
      } else if(!res[w]){ // 访问过但没有结果(在栈中)
        low[v] = min(low[v],dfn[w]);
      }
    }
    int u;
    if(low[v] == dfn[v])  {
      do{
        res[u = stk.top()] = v;
        stk.pop();
      }while(u != v);
    }
  }
public:
  Tarjan(int SZ):n(SZ){
    low = vector<int>(n+1);
    dfn = vector<int>(n+1);
    stk = {};
    res = vector<int> (n+1);
    p = vector<vector<int> >(n+1);
  }
  vector<int> calc(){
    rep(i,1,n+1){
      if(!res[i]){
        scc(i);
      }
    }
    return res;
  }
  void p2(int i,int j){
    p[i].pb(j);
  }
};

void build(int idx,int father){
  fa[idx] = father;
  dep[idx] = dep[father]+1;
  for(auto x:p2[idx]) {
    if(x == father)continue;
    build(x, idx);
  }
}

// 因为要具体路径, LCA帮不上忙,直接暴力找
vector<int> getpath(int u,int v){
  if(dep[u] > dep[v])swap(u,v);
  vector<int> r1 = {};
  vector<int> r2 = {};
  while(dep[v] > dep[u]){
    r1.push_back(v);
    v = fa[v];
  }
  while(u != v){
    r1.push_back(v);
    v = fa[v];
    r2.push_back(u);
    u = fa[u];
  }
  r1.push_back(u);
  per(i,0,r2.size()){
    r1.push_back(r2[i]);
  }
  return r1;
}

bool add(int u,int v, Tarjan &t){
  vector<int> path = getpath(u, v);
  // 只记录不确定的
  vector<int>inc;
  vector<int>dec;
  rep(i,0,(int)path.size()){
    int p = path[i];
    char ch1 = s[i];
    char ch2 = s[path.size() - 1 -i];
    if(ch1 == ch2){ // 直接确定
      if(ans[p] != 0 && ans[p] != ch1){
        return false;
      }
      ans[p] = ch1; // 一个的改值, 两个的是 增加统计
    }else{ // 先建立关系 不关心冲突
      int id = id2pchar.size();
      id2pchar.push_back({p,ch1});
      p2charid[p][ch1].push_back(id);
      inc.pb(id);

      id = id2pchar.size();
      id2pchar.push_back({p,ch2});
      p2charid[p][ch2].push_back(id);
      dec.pb(id);
    }
  }
  assert(dec.size() == inc.size());
  rep(i,0,(int)inc.size()){
    t.p2(inc[i],inc[(i+1)%inc.size()]);
    t.p2(dec[i],dec[(i+1)%dec.size()]);
  }
  return true;
}

bool checkscc(int scc){
  vector<pair<int,char>> pch;
  for(auto id:scc2ids[scc]){
    auto [p, ch] = id2pchar[id];
    if(ans[p] == ch || ans[p] == 0){
      pch.push_back({p,ch});
    }else{
      return false;
    }
  }
  sort(pch.begin(),pch.end());
  rep(i,1,(int)pch.size()){
    if(pch[i-1].first != pch[i].first) continue; // 同一个点
    if(pch[i-1].second != pch[i].second) return false; // 不同字符
  }
  return true;
}

bool applyscc(int scc){
  vis[scc] = true;
  for(auto id:scc2ids[scc]){
    auto [p, ch] = id2pchar[id];
    if(ans[p] == ch)continue;
    if(ans[p] == 0){
      ans[p] = ch;
    }else{
      return false;
    }
  }
  return true;
}

bool rmscc(int scc){
  vis[scc] = true;
  for(auto id:scc2ids[scc]){
    if(id == 1)continue;
    auto [p, ch] = id2pchar[id];
    if(ans[p] == ch) return false; // 失效和已经填入的冲突
    if(p2charid[p].count(ch)){
      p2charid[p].erase(ch);
      if(ans[p] == 0 && p2charid[p].size() == 0)return false; //
      if(p2charid[p].size() == 1){
        auto [ch,ids] = *p2charid[p].begin();
        if(ans[p] != 0 && ans[p] != ch)return false;
        ans[p] = ch;
        for(auto id:ids){
          if(!vis[id2scc[id]]){
            int r = applyscc(id2scc[id]);
            if(!r)return r;
          }
        }
      }
    }
  }
  return true;
}

int main(){
  id2pchar.push_back({-1,'X'}); // 占位0
  id2pchar.push_back({-1,'X'}); // 建立特殊失效节点, 下标为1
  int n,q;
  cin>>n>>q;
  rep(i,0,n-1){
    int u,v;
    scanf("%d %d",&u,&v);
    p2[u].push_back(v);
    p2[v].push_back(u);
  }
  build(1,0); // 父节点和深度
  Tarjan t(2*N+2);
  rep(i,0,q){
    int u,v;
    scanf("%d %d",&u,&v);
    scanf("%s",s);
    bool r = add(u,v,t);
    if(!r){
      printf("NO\n");
      return 0;
    }
  }
  // 处理每个点明确不可能的情况
  rep(i,1,n+1) {
    if(ans[i]){ // 已确定的
      for(auto [ch,ids]:p2charid[i]){
        if(ch == ans[i])continue;
        for(auto id: ids){
          t.p2(1,id); // 失效的
          t.p2(id,1); // 失效的
        }
      }
    }else{ // 未确定的
      if(p2charid[i].size() == 0){
        ans [i] = 'a'; // 没有限制
      }else { // 每次贡献两个不同的,那么答案要占恰好一半出现
        int total = 0;
        for(auto [ch,ids]:p2charid[i]){
          total+=ids.size();
        }
        for(auto [ch,ids]:p2charid[i]){
          if((int)ids.size()*2 != total){
            for(auto id: ids){
              t.p2(1,id); // 建立不可能
              t.p2(id,1);
            }
          }
        }
      }
    }
  }
  id2scc = t.calc();
  scc2ids = vector<vector<int>>(id2pchar.size());
  vis = vector<bool>(id2pchar.size());
  rep(i,1,(int)id2pchar.size()){
    scc2ids[id2scc[i]].pb(i);
  }
  // 处理掉直接不可能
  bool r = rmscc(1);
  if(!r){
    printf("NO\n");
    return 0;
  }
  rep(scc,2,(int)id2pchar.size()){
    if(!scc2ids[scc].size())continue;
    if(vis[scc])continue;
    if(!checkscc(scc)){
      bool r = rmscc(scc);
      if(!r){
        printf("NO\n");
        return 0;
      }
    }else{
      bool r = applyscc(scc);
      if(!r){
        printf("NO\n");
        return 0;
      }
    }
  }
  rep(i,1,n+1){
    if(!ans[i]){
      printf("NO\n");
      return 0;
    }
  }
  printf("YES\n");
  rep(i,1,n+1){
    printf("%c",ans[i]);
  }
  printf("\n");
  return 0;
}

总结

还是知识点不够, 一个是太久没写tarjan scc,一个是没搞过2-sat

参考

官方题解

發表於 更新於 分類於 ， Disqus： 文章字數： 2k 所需閱讀時間 ≈ 7 分鐘
E(按类别分治),F(神奇的逐位排序, 基数排序, 后缀数组)

E

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

给一数列,修改尽量少的值让整个数列等差

范围

n <= 1e5

1<= ai <= 1e5

5s

1GB

题解

实际上是二维点(i,ai),找直线经过最多的点

考虑增量 小于 sqrtn,那么选中斜率, 计算每个点沿着斜率与y轴交点 出现的最多次即可, 不要用map,用数组和清理数组实现

考虑增量 大于 sqrtn,以每个点作为起点,那么最多尝试这个点向后n/sqrt(n) 个点, 把这些点计算出现最多次数的斜率, 数量不多,可以用map

代码

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
#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-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);

const int N = 100000;
int a[N+10];

int used[32000010];
int n;

int work(){
  int SQRT = 316;
  int ans = 0;
  // 增量 <= SQRT;
  rep(i,0,SQRT+1){
    vector<int> rm;
    rep(j,0,n){
      // 非负便宜量
      int v = a[j] + SQRT*N- j*i; // max = 31600000+100000
      if(!used[v])rm.push_back(v);
      ans = max(ans,++used[v]);
    }
    // clear
    for(auto v:rm){
      used[v] = 0;
    }
  }
  // 增量 大于 SQRT
  rep(j,0,n){ // 下标
    map<int,int> kcnt;
    rep(i,j+1,n){ // 增量
      if(a[j] + (i-j) * SQRT > N) break;
      if( (a[i] - a[j]) % (i-j) == 0){
        kcnt[(a[i] - a[j]) / (i-j)]++;
      }
    }
    for(auto [k,cnt]:kcnt){
      // printf("a[%lld] = %d : k=%d cnt = %d\n",j,a[j],k,cnt+1);
      ans = max(ans, cnt+1);
    }
  }
  return ans;
}

int main(){
  cin>>n;
  rep(i,0,n){
    scanf("%d",a+i);
  }
  int ans = work();
  // 翻转
  rep(i,0,n/2){
    swap(a[i],a[n-1-i]);
  }
  printf("%d\n",n - max(ans,work()));
  return 0;
}

总结

按照一个值,分段处理,每一段都是性能满足的

参考

官方题解

F

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

给一个字符串,长度$2^n$

找一个$j <= 2^n$, 让s[i^j] 字典序最小

范围

n <= 18

3s

512MB

题解

我的尝试

我想到,j的位是0或1实际上意味着 原字符串 的长度2^k 区间是否交换

而判断是否交换,可以局部贪心

问题是,存在字符相等的情况, 不知道怎么记录, 试了一下random 并不能骗分哈哈

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
#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-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);
 
// n => 2^n length lowercase letters
//
// t[i] = s[i ^ j]
//
// find j => minimal string
// n <= 18
// 2^n <= 262144
// bit1 ,一个一组,相邻交换
// bit2 ,2个一组,相邻交换
// bit3 ,3个一组,相邻交换
// bit4 ,4个一组,相邻交换
 
// ans(0..x)
// => min(ans(0..x/2),ans(x/2+1...x)) 最小的作为前缀
// 3**18 => 387420489
 
int n;
char s[270010];
int ans[270010][20];
 
int cmp(int p,int pwr,int l,int r){
  // 自己所在的那一节
  rep(i,0,(1<<pwr)){
    if(s[(p + i) ^ l] < s[(p + (1<<pwr) + i) ^ r]) return -1;
    if(s[(p + i) ^ l] > s[(p + (1<<pwr) + i) ^ r]) return 1;
  }
  // 对手那一行
  rep(i,0,(1<<pwr)){
    if(s[(p + (1<<pwr) + i) ^ l] < s[(p + i) ^ r]) return -1;
    if(s[(p + (1<<pwr) + i) ^ l] > s[(p + i) ^ r]) return 1;
  }
  return 0;
}
 
ll tryRand(){
  rep(i,1,n+1){
    for(int p = 0;p < (1<<n); p += (1<<i)){
      int lans = ans[p][i-1];
      int rans = ans[p+(1<<(i-1))][i-1];
      int res = cmp(p,i-1,lans,rans);
      // TODO 相等的情况??????
      if(res == 0){
        // printf("fuck?\n");
        if(rand()%2){
          ans[p][i] = lans;
        }else{
          ans[p][i] = (rans | (1<<(i-1)));
        }
      } else if(res == -1){
        ans[p][i] = lans;
      }else{
        ans[p][i] = (rans | (1<<(i-1)));
      }
    }
  }
  return ans[0][n];
}
 
int main(){
  srand(time(NULL));
  cin>>n;
  scanf("%s",s);
  int j = tryRand();
  rep(t,0,180){
    int k = tryRand();
    rep(i,0,(1<<n)){
      if(s[i ^ j] < s[i ^ k])break;
      if(s[i ^ j] == s[i ^ k])continue;
      j = k;
      break;
    }
  }
  rep(i,0,(1<<n)){
    printf("%c", s[i ^ j]);
  }
  printf("\n");
  return 0;
}

正解

实际上可以看成, 把 0~n-1排序

而排序是按照f(s,i)的字典序来比较大小的

这里的问题是 如果两两比较 依然复杂度完成不了, 如何减少比较和处理相等

考虑样例1: acba

1
2
3
4
0: acba
1: caab
2: baac
3: abca

最终期望得到

1
2
3
4
3: abca
0: acba
2: baac
1: caab

然而注意到,

首位的比较 就是 s[i]

第2位的比较 就是 s[i ^ (1<<0)]

第3位的比较 就是 s[i ^ (1<<1)]

第4位的比较 就是 s[i ^ (1<<2)]

而 一旦首位有非相等的大小关系了,之后也就不会改变相对顺序, 不想等时 才考虑后续排序

于是, 按首位排序

1
2
3
4
0: a
1: c
2: b
3: a

变为

1
2
3
4
0: a
3: a
2: b
1: c

记录大小顺序

1
2
3
4
0: a(0)
3: a(0)
2: b(1)
1: c(2)

按照第二位排序

1
2
3
4
0: ?c
1: ?a
2: ?a
3: ?b

得到

1
2
3
4
1: ?a
2: ?a
3: ?b
0: ?c

整体变为(注意首位不相等的要保持顺序)

1
2
3
4
3: ab
0: ac
2: ba
1: ca

记录大小顺序

1
2
3
4
3: ab(0)
0: ac(1)
2: ba(2)
1: ca(3)

这样所有位排序, 更新顺序即可

换句话说就是类似基数排序, 每次是对前缀相等的一系列值的下一位 进行排序

这里注意到看上去字符串长度,有1 << n, 但是实际上,上述排序只需要考虑2的幂次的

因为,[2..3] 的排序 实际是 ([0..1]^2)得到的排序

因为,[4..7] 的排序 实际是 ([0..3]^4)得到的排序

所以 虽然是基数排序,但是 能通过幂次 和记录大小的排序值 优化比较次数

代码

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
#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-1;i>=a;i--)
#define pb push_back

const int N = 1 << 18;
int n, a[N], val[N], tmp[N], now;
char s[N];

// x 在 y 前面
bool cmp(int x, int y) {
  return (val[x] == val[y]) ?
    val[x ^ now] < val[y ^ now] :
    val[x] < val[y];
}

int main() {
  cin>>n;
  scanf("%s", s);
  rep(i,0,1<<n){
    val[i] = s[i] - 'a'; // [0,26), 实际表示的是以 (1<<pwr) 跨度排序 的 顺序下标,
    a[i] = i; // 相当于 0 ~ 2^n-1 中 让s字典序最小的
  }
  rep(pwr,0,n) {
    now = 1 << pwr; // 比较区间长度
    sort(a, a + (1 << n), cmp);
    int num = 0; // 离散化顺序值
    rep(j,0,1<<n){
      if (j > 0 && cmp(a[j - 1], a[j])) num ++; // f(a[j-1]) < f(a[j]) => num++; 明确j比前一个大
      tmp[a[j]] = num;
    }
    rep(j,0,1<<n){
      val[j] = tmp[j]; // 记录的是 now*2 长度 的 排序 序号
    }
  }

  rep(i,0,1<<n){
    putchar(s[i ^ a[0]]);
  }

  return 0;
}

pwr = 0, now = 1

如果字符 更小,则排在前面

如果字符 相等,则它^1位置的更小就排在前面, 如果依然相等,则认为当前论次比较它们两相等

修改val[i] = 表示选定异或值i, 让 s在i 的转换下, 前两位 在所有i 中的 顺序

pwr = 1, now = 2

注意到上面val意义已经变化

val[i] 表示的是 i 引起的转换 的前两位的排序值

如果排序值更小,则排在前面

如果排序值相等,则它^2位置的更小就排在前面, 如果依然相等,则认为当前论次比较它们两相等

修改val[i] = 表示选定异或值i, 让 s在i 的转换下, 前4位 在所有i 中的 顺序

pwr = 2, now = 4

val[i] 表示的是 i 引起的转换 的前4位的排序值

如果排序值更小,则排在前面

如果排序值相等,则它^4位置的更小就排在前面, 如果依然相等,则认为当前论次比较它们两相等

修改val[i] = 表示选定异或值i, 让 s在i 的转换下, 前8位 在所有i 中的 顺序

pwr = n, now = 2**n

val[i] 表示的是 i 引起的转换 的前now位的排序值

如果排序值更小,则排在前面

如果排序值相等,则它xor now 位置的更小就排在前面, 如果依然相等,则认为当前论次比较它们两相等

修改val[i] = 表示选定异或值i, 让 s在i 的转换下, 前now*2位 在所有i 中的 顺序

总结

每次排序,再记录顺序, 方便后续比较,而不仅仅排序就完了, 这个记录顺序很重要

参考

官方题解

發表於 更新於 分類於 ， Disqus： 文章字數： 1.5k 所需閱讀時間 ≈ 5 分鐘
D(二分，单调队列，前缀和，线段树，区间覆盖，动态规划)

D

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

3xn 左上角 走到 右下角，只能右和下两个方向的走，价值= 经过块的值的和

第一行，第三行直接可走，第二行需要额外代价v,开启[l,r]一段

问总获得价值最大值

范围

n <= 5e5

块上值 -1e9 ~ 1e9

可选扩展 5e5 个，扩展代价 1~1e9

题解

行走代价简化

走过的样子无非是

1
2
3
xxxxxx
     xxxxxxx
           xxxxxxxxx

拆分一下,

第一段： 第一行+，第二行-

第二段： 第二行+，第三行+

1
2
3
4
5
6
     i
++++++
-----
            j
+++++++++++++
            +++++++++

那么行走代价为s[i]+t[j]

剩下就是开放(i,j)的最小代价

状态与转移与范围最值

考虑从(1,1)走到(2,i), 其中当前使用的最右侧的开放端点是i

1
2
3
4
5
6
     ?
xxxxxx      i
     xxxxxxxx
        [   ]
      [  ]
    [  ]

dp[i] = (1,1) -> (2,i) 且i 是当前最右侧开放的点, 上述条件下 , 最大的 s[?] - cost(?,i)

这里两点

  1. i 是某个区间右侧端点, 且走到了这个位置
  2. dp表示的是这样范围中最大的, 包含s 和 cost , 这里很神奇，没有t意味着，下面转移时并不用考虑第二行所选位置对dp的影响

也就是一个准确，一个范围最值

状态转移，

要么是通过第一行直接进入所选区间走到i,

要么就是先走到(2,j), 再在一个区间内走到i, 所以 j 在 [l-1,r] 内

1
2
3
4
5
6
     ?
xxxxxx       j
     xxxxxxxxx
           [      ]
xxxxxx            i
     xxxxxxxxxxxxxx

dp[i] = max(dp[j] - cost(i,j).value)

剩下的就是最终的答案, 因为可能走到不是某个区间的终点，就去第三行了

1
2
3
4
5
     ?
xxxxxx         i  j
     xxxxxxxxxxxxxx
                  xxxxxxx
              [      ]

ans = max(dp[i] - cost(i,j).value + t[j])， i,j 在某个区间内，i < j, 对于相等的情况 上面直接+t[i]就更新

换个角度，先固定一个区间,cost确定,再在这个区间里找 max(dp[i]+t[j])

其中i 在[l-1,r]内

注意到上面的方案，一定经过了某个开放区间的终点，开放区间为 >= 1 个 ，所以还有一种情况，只开放了一个区间，i和j都在区间之中

上面最重要的是控制成了一个区间,但不一定是唯一一个区间

而上面的操作和只开放一个区间十分的像，都是开放一个区间，左dp[i],右t[j] 和(i < j) 左s[i],右t[j] (i <= j)

注意到对于左dp,右t的情况，i==j只会产生比最优更小的答案，所以可以考虑在最值处理时合并left[i] = min(dp[i],dp[i-1],s[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
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
#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 pb push_back
#define SEG_ROOT 1,0,n-1
#define SEG_L o<<1,l,m
#define SEG_R o<<1|1,m+1,r
const double pi = acos(-1.0);
 
const int N = 500'000;
ll s[N + 10];
ll t[N + 10];
ll dp[N + 10];
ll a[3][N + 10];
vector<tuple<int, int, ll> > rlv;
 
ll seg[2][N * 4 + 10];
ll segans[N * 4 + 10];
const ll INF = 0x3f3f3f3f3f3f3f3f;
 
ll query(int o, int l, int r, int ql, int qr) {
  if (l == ql && r == qr)
    return seg[0][o];
  int m = (l + r) / 2;
  if (qr <= m) {
    return query(SEG_L, ql, qr);
  } else if (ql > m) {
    return query(SEG_R, ql, qr);
  } else {
    return max(query(SEG_L, ql, m),
               query(SEG_R, m + 1, qr));
  }
}
 
void update(int o, int l, int r, int pos) {
  if (l == r) {
    seg[0][o] = dp[l];
    return;
  }
  int m = (l + r) / 2;
  if (pos <= m)
    update(SEG_L, pos);
  else
    update(SEG_R, pos);
  seg[0][o] = max(seg[0][o << 1], seg[0][o << 1 | 1]);
}
 
void build(int o, int l, int r) {
  if (l == r) {
    seg[0][o] = dp[l];
    return;
  }
  int m = (l + r) / 2;
  build(SEG_L);
  build(SEG_R);
  seg[0][o] = max(seg[0][o << 1], seg[0][o << 1 | 1]);
}
 
// [l,r]为开放段
void buildans(int o, int l, int r) {
  if (l == r) {
    // 可以dp到[l-1] 或[l]
    seg[0][o] = max(max(dp[l], s[l]), l > 0 ? dp[l-1] : -INF);
    seg[1][o] = t[l];
    segans[o] = seg[0][o] + t[l];
    return;
  }
  int m = (l + r) / 2;
  buildans(SEG_L);
  buildans(SEG_R);
 
  seg[0][o] = max(seg[0][o << 1], seg[0][o << 1 | 1]);
  seg[1][o] = max(seg[1][o << 1], seg[1][o << 1 | 1]);
  segans[o] = max(seg[0][o << 1] + seg[1][o << 1 | 1],
                  max(segans[o << 1], segans[o << 1 | 1]));
};
 
// {最大值, 最大dp, 最大t}
vector<ll> qans(int o, int l, int r, int ql, int qr) {
  if (ql == l && qr == r) {
    return {segans[o], seg[0][o], seg[1][o]};
  }
  int m = (l + r) / 2;
  if (qr <= m) {
    return qans(SEG_L, ql, qr);
  } else if (ql > m) {
    return qans(SEG_R, ql, qr);
  }
  auto lres = qans(SEG_L, ql, m);
  auto rres = qans(SEG_R, m + 1, qr);
  return {max(max(lres[0], rres[0]), lres[1] + rres[2]), max(lres[1], rres[1]),
          max(lres[2], rres[2])};
}
 
int main() {
  int n, q;
  scanf("%d %d", &n, &q);
  ll a2 = 0;
  rep(i, 0, 3) {
    rep(j, 0, n) { scanf("%lld", &a[i][j]); }
  }
  rep(i, 0, n) a2 += a[2][i];
  s[0] = a[0][0];
  rep(i, 1, n) { s[i] = s[i - 1] + a[0][i] - a[1][i - 1]; }
  t[0] = a2 + a[1][0];
  rep(i, 1, n) { t[i] = t[i - 1] + a[1][i] - a[2][i - 1]; }
 
  rep(i, 0, q) {
    int r, l;
    ll v;
    scanf("%d %d %lld", &l, &r, &v);
    rlv.pb({r - 1, l - 1, v});
  }
  ll ans = -INF;
  // 按右端点排序
  sort(rlv.begin(), rlv.end());
  // 处理 使用一次区间直接进入的
  vector<int> pos;  // 单调队列
  unsigned long itr = 0;
  rep(i, 0, n){
    dp[i] = -INF;
  }
  rep(i, 0, n) {  // 下标
    while (pos.size() && s[pos.back()] <= s[i]) {
      pos.pop_back();
    }
    pos.pb(i);
    while (itr < rlv.size() && get<0>(rlv[itr]) == i) {
      // 区间内最大值
      dp[i] = max(
          dp[i],
          s[*lower_bound(pos.begin(), pos.end(), get<1>(rlv[itr]))] -
              get<2>(rlv[itr]));  // cost > 0选自己没影响
      if (dp[i] != -INF) {
        ans = max(ans, dp[i] + t[i]);
        // printf("dp[%lld] => %lld\n", i, dp[i]);
      }
      itr++;
    }
  }
  build(SEG_ROOT);
  itr = 0;
  for(auto [r,l,v]:rlv){
    // 注意可以上一个结束的位置[?..l-1] 和当前 [l..r] 是相邻而不是重叠
    // dp[i] = max(dp[<i] - cost);
    ll newdpi = query(SEG_ROOT, max(0,l-1), max(0,r-1)) - v;
    if (newdpi > dp[r]) {
      dp[r] = newdpi;
      ans = max(ans, dp[r] + t[r]);
      // printf("update: dp[%lld] => %lld\n", i, dp[i]);
      update(SEG_ROOT, r);
    }
  }
  buildans(SEG_ROOT);
  // [l...r] => [l..m] [m+1,r]
  for (auto [r, l, v] : rlv) {
    auto qres = qans(SEG_ROOT, l, r);
    if (qres[0] <= -INF)
      continue;
    ans = max(ans, qres[0] - v);
  }
  printf("%lld\n", ans);
 
  return 0;
}

总结

一个核心的点就是区间覆盖，转换成刚好走到以某个区间结束的动规，感觉要是一个纯的动规还可能想到，合在一起竟然卡住了

参考

官方题解

C202044zxy

cggghh

Sstee1XD

某岛

0%