YeXiaoRain Blog

發表於 更新於 分類於 ， 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

發表於 更新於 分類於 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 中的 顺序

总结

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

参考

官方题解

0%