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

發表於 更新於 分類於 ， Disqus： 文章字數： 1.7k 所需閱讀時間 ≈ 6 分鐘
D(dp)E(双指针,部分更新,线性筛1/2+1/3+1/4+...)

这次Div2的D,E都不会了

D

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

长度n数组A

每次操作可以删除相邻且不同的两个值, 剩下的拼在一起, 多次操作

要让最终的数组值全部相同,求最大长度

范围

n 5000

2s

256MB

题解

我的思路

如果我们指定哪个值留下来

假设是v

那么 考虑两个v之间的其它值 v …. v

如果其中有值x出现次数超过一半, 那么剩下的必然是x - 非x

否则,如果是奇数个剩下任意一个, 偶数个则全部清除

最后可以得到一个 v 非v v 非v v …

的多段结果

然后我并没有什么办法 处理这个

如果有办法就是n^2 的总复杂度了

题解

首先如果一个数出现次数超过一半,那最终剩下的一定是它,所以这种情况不用猜留哪个

如果整个长度是偶, 且没有数出现次数超过一半,那么可以被完全删除

然后通过O(n^2) 计算所有区间 最多出现的数字,或者全部可消除

啊 我知道啊

dp[i] 表示a[0…i]删除以后 结果包含a[i] 的最大长度

初始化 如果[0..i-1] 能完全删除 dp[i] = 1, 否则 dp[i] = -INF

如果j < i, a[i] == a[j] 且 [j+1..i-1] 能完全删除

dp[i] = max(dp[j]+1)

所以最后就是求所有中的最大的且后缀可删除rm[j..end] == true, 相当于找结果的末尾位置

代码

https://codeforces.com/contest/1699/submission/162852461

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

typedef long long ll;
#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;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

int n;

int a[5010];  // 5000 n^2
bool rm[5010][5010]; // rm[i][j] = [i..j] 完全删除
int dp[5010]; // 前[0..i] 删完剩下 a[i] 的个数

const int INF = 0x3f3f3f3f;

void w(){
  n = read();
  rep(i,0,n) a[i] = read();
  rep(i,0,n){
    fill(rm[i],rm[i]+n,false);
    vector<int>cnt(n+1,0); // 次数统计
    int maxc = -1; // 出现最多的
    rep(j,i,n){
      cnt[a[j]]++;
      if(maxc == -1 || cnt[maxc] < cnt[a[j]]) maxc = a[j];
      if((j-i)%2 == 0)continue;
      if(cnt[maxc] <= (j-i+1)/2) rm[i][j] = true;
    }
  }
  rep(i,0,n) dp[i] = (i == 0 || rm[0][i-1]) ? 1: -INF; // 初始化
  int ans = 0;
  rep(i,0,n){
    rep(j,0,i){
      if((i-j)%2==0)continue;
      if(a[i] != a[j]) continue;
      if(j == i-1 || rm[j+1][i-1]) dp[i] = max(dp[i], dp[j]+1);
    }
    if(i == n-1 || rm[i+1][n-1]) ans = max(ans,dp[i]); // 后续可删
  }
  printf("%d\n",ans);
}
 
int main(){
  int t = read();
  while(t--) w();
  return 0;
}

E

给你长度n数组a

每次你可以把任意一个值v=a乘b,拆成a,b,

求 min(max(数组) - min(数组))

范围

n 1e6

ai [1..5e6]

4s

256MB

题解

我的思路

直接想 有点像是说, 能否把每个数拆分进[l..r] 之间

变个方向就是 给定l,求最小的r

那么考虑l的变化

因为任意两个ai,aj的拆分方案互不影响, 考虑单个 v 拆成最小>=l时,最大r的最小值的

显然l增大时,r 非严格单增, 且l <= min(ai)的

而问题是让区间尽量小

区间长度并没有单调性或凹凸性, 想法方向GG

第二个想法是

我直接拆每个数, 去计算每个数的map[间隔] = vector< pair<最小,最大> >

比如 4: [0] = { { 2 , 2 } , { 4 , 4 } }

但不知道怎么拆, dfs暴力?

以及拆分后怎么在不同ai之间组合

题解

和我第一个想法类似但是倒着for最小的因子

因为不同v的拆法互不影响,考虑一个具体的原数组中出现过的 v

若当前最小因子恰好为i, 那么

如果 v不是i的倍数, 则,之前v怎么拆分就怎么拆分

如果 v < i^2, 显然不能拆,如果拆了 另一个因子就会小于i

v >= i^2 且v = ik , 那么会拆成i 和 k, 而对于k可能也有拆的方案

我们直接记录dp[k] = 当前拆分方案中, 最大的因子

有dp[ik] = min(old dp[ik], dp[k]), 其中k >= i

这里要注意的是当一个数v=ik是i的倍数,它按i拆开仅是可能让最大因子更小,而不是一定, 所以要和之前的dp[v] 比较

而最大值, 显然是非严格单调递减, 我们只需要 统计每个值拆分后的最大因子(也是非严格单调递减)出现次数, 就能知道最大值

代码

https://codeforces.com/contest/1699/submission/162860620

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 rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
 
ll read(){ll r;scanf("%lld",&r);return r;} // read
const int N = 5000000;
bool appear[N+10]; // 在数列中出现过
int mxval[N+10]; // [v] = v当前被拆分出来的更大的因子 , 运算过程中每个值的变化是非严格单调递减
int cnt[N+10]; // 遍历过程中 每个ai拆分后对应最大因子 的 次数统计
int n;
int m;
 
void w(){
  // clear
  fill(appear,appear+m+1,false);
  fill(cnt,cnt+m+1,0);
  fill(mxval,mxval+m+1,0);
 
  n = read();
  m = read();
 
  int mn = m; // 最小
  int mx = 0; // 最大
  rep(i,0,n){
    int x = read();
    appear[x] = true;
    cnt[x] = 1;
    mn = min(mn, x);
    mx = max(mx, x);
  }
  iota(mxval,mxval+mx+1,0); // mxval[i] = i; 默认都未被拆分
  int ptr = mx; // 最大值
  ll ans = mx - mn;
  per(i,1,mx+1){
    for (ll j = i * i; j <= mx; j += i) { // j = i * (k>=i) , j 拆分成 i 和 k, k可能继续能拆
      // 移除原有拆分方案
      if (appear[j]) cnt[mxval[j]]--; // 从真的统计上讲 应该是 [i]--, [mxval[j]]--, 但i <= mxval[j] 所以 这里 中间一段不影响结果
      // 计算新的最优方案
      mxval[j] = min(mxval[j], mxval[j / i]); // i 不一定是最小的, 所以吆喝之前的比较
      // 加入新的拆分方案
      if (appear[j]) cnt[mxval[j]]++;
    }
    while (cnt[ptr] == 0) ptr--;
    if (i <= mn) ans = min(ans, ptr - i); // 最小值为i, 最大值为ptr
  }
  printf("%lld\n",ans);
}
 
int main() {
  int t = read();
  while (t--) w();
}

总结

D

核心其实还是dpi可以和ai挂钩,因为其它什么区间可删除都想到了, 感觉应该还很常见的

E

倒着处理

只更新会影响的部分内容

因为遍历的i就是最小, 所以拆分统计, 不需要统计非最大因子以外的内容, 优化统计

参考

官方

發表於 更新於 分類於 ， Disqus： 文章字數： 1.1k 所需閱讀時間 ≈ 4 分鐘
F(暴力)G(bitset)H/Ex(dp,矩阵快速幂)

F

题目

https://atcoder.jp/contests/abc258/tasks/abc258_f

网格,4临移动

如果 x=Bn的线上移动或者y=Bn的线上移动,(B的倍数), 单位距离代价1

其它情况单位距离代价k

求(sx,sy) -> (gx,gy) 的最小代价

范围

t 2e5 测试点

b,k [1,1e9]

sx,sy,gx,gy [0,1e9]

3s

1024mb

题解

我的思路

显然是个数学处理一下, 就做的题

两个点分开考虑

一个点计算它本身, 四个方向到x=bn or y=bn , 的点,再到四个角的点

点类型 (普通0,边点1,十字交点2)

(0-任何) 直接距离乘k

(边点 - 边/十字) = 在方向上同bn, 则x1, 否则直接距离乘k

(十字-十字) = 距离x1

写了二十多分钟

代码

https://atcoder.jp/contests/abc258/submissions/32973579

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<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

ll b;
ll k;

const int T_NORMAL = 0; // 普通
const int T_SIDE = 1; // 边
const int T_CROSS = 2; // 角

int calctype(ll i,ll j){
  return (int)(i%b == 0) + (int)(j%b == 0);
}

vector<array<ll,3> > calc(ll i,ll j){  // i , j , dis
  vector<ll> ai = {i};
  vector<ll> aj = {j};
  if(i%b) {
    ai.pb((i/b)*b);
    ai.pb((i/b+1)*b);
  }
  if(j%b) {
    aj.pb((j/b)*b);
    aj.pb((j/b+1)*b);
  }
  vector<array<ll,3> > res;
  for(auto ni:ai){
    for(auto nj:aj){
      if(ni != i && nj != j){
        res.pb({ni,nj, (abs(ni-i) + abs(nj-j) - max(abs(ni-i), abs(nj-j)))*k + max(abs(ni-i), abs(nj-j)) });
      }else{
        if(i % b != 0 && j%b != 0){
          res.pb({ni,nj, (abs(ni-i) + abs(nj-j))*k});
        }else{
          res.pb({ni,nj, (abs(ni-i) + abs(nj-j))});
        }
      }
    }
  }
  return res;
}

void w(){
  b = read();
  k = read();
  ll si = read();
  ll sj = read();
  ll gi = read();
  ll gj = read();
  auto ijds = calc(si,sj);
  auto ijdg = calc(gi,gj);
  ll ans = 0x3f3f3f3f3f3f3f3f;

  for(auto [i0,j0,d0]:ijds){
    int t0 = calctype(i0,j0);
    for(auto [i1,j1,d1]:ijdg){
      int t1 = calctype(i1,j1);
      if(t0 == T_NORMAL || t1 == T_NORMAL){
        ans = min(ans,d0+d1+ (abs(i1-i0) + abs(j1-j0))*k);
      }else if(t0 == T_SIDE || t1 == T_SIDE){
        if(i0 == i1 && i0 % b == 0){
          ans = min(ans,d0+d1+abs(j1-j0));
        }else if(j0 == j1 && j0 % b == 0){
          ans = min(ans,d0+d1+abs(i1-i0));
        }else{
          ans = min(ans,d0+d1+(abs(i1-i0)+abs(j1-j0))*k);
        }
      }else{ // == CROSS
        ans = min(ans,d0+d1+abs(i1-i0)+abs(j1-j0));
      }
    }
  }
  printf("%lld\n",ans);
}

int main(){
  int t = read();
  while(t--) w();
  return 0;
}

H/Ex

https://atcoder.jp/contests/abc258/tasks/abc258_h

序列X满足

  1. 所有元素正奇数
  2. 和为s
  3. X前缀和的值不在集合A中, 集合A大小为N

求满足的要求的序列X的个数

范围

n 1e5

ai [1,1e18]

s [1,1e18]

题解

我的思路

果然读错题, 读成了需要序列X长度也是N

实际上对序列长度无要求

不考虑X而是直接考虑X的前缀和

dp[v] = 构成v的方案数

dp[Aj] = 0

dp[0] = 1

递推关系

dp[v] = sum{dp[v-1]+dp[v-3]+ dp[v-5]+...}

令f[i] = dp[i] + dp[i-2] + dp[i-4]

有dp[v] = f[v-1] f[v] = dp[v] + f[v-2] = (v in A ? 0 :f[v-1]) + f[v-2]

所以可以直接算f 矩阵快速幂

然后问题是要处理掉v 在 A中的情况, 并且注意到v在A中是dp[v] == 0 并不意味f[v-1] == 0

1
2
3
(f[v-1] f[v-2]) (f[v] f[v-1])
                (1/0    1   )
                ( 1     0   )

代码

https://atcoder.jp/contests/abc258/submissions/32981204

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
#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;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

int n;
ll s ;

ll a[100010];

// Wi = (f[i]  f[i-1])

// (f[v] f[v-1]) = (f[v-1] f[v-2]) *
//                                (1/0    1   )
//                                ( 1     0   )

vector<vector<ll> > mul(vector<vector<ll> >m0,vector<vector<ll> >m1){
  vector<vector<ll> > r = vector<vector<ll> >(m0.size(), vector<ll>(m1[0].size(),0));
  assert(m0[0].size() == m1.size());
  rep(i,0,m0.size()){
    rep(j,0,m1[0].size()){
      rep(k,0,m0[0].size()){
        (r[i][j] += m0[i][k] * m1[k][j] % MOD) %= MOD;
      }
    }
  }
  return r;
}

vector<vector<ll> > mypow(vector<vector<ll> >m0,ll pwr){
  vector<vector<ll> > r = {
    {1,0},
    {0,1}
  };
  while(pwr){
    if(pwr%2) r = mul(r,m0);
    m0 = mul(m0,m0);
    pwr/=2;
  }
  return r;
}


int main(){
  n = read();
  s = read();
  rep(i,0,n) a[i] = read();
  a[n] = s; // dp[s] = f[s-1] =>  w[s][1]
  n++;
  vector<vector<ll> > w; // w[iw] = {f[iw], f[iw-1]}
  ll iw = 1;
  if(a[0] == 1) w = { {0,1} };
  else w = { {1,1} };

  rep(i,0,n){
    ll ai = a[i];
    if(iw == ai)continue;
    if(iw == ai-1){
      w = mul(w,{
          {0,1},
          {1,0}
          });
      iw = ai;
    }else{
      w = mul(
          mul(w,mypow({
              {1,1},
              {1,0}
              }, ai-iw-1)),{
          {0,1},
          {1,0}
          });
      iw = ai;
    }
    // printf("w[%lld] = {%lld %lld}\n",iw, w[0][0],w[0][1]);
  }
  printf("%lld\n",w[0][1]);
  return 0;
}

总结

F

没啥难的

G

内置 bitset 优化一下效率就行了

Ex

也没啥难的

参考

官方题解

發表於 更新於 分類於 ， Disqus： 文章字數： 2.1k 所需閱讀時間 ≈ 7 分鐘
F(数学,数组,相邻无序对)G(GF(2),meet in middle,不懂证明)

F

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

给长度n的数组A和B

每次可以选择A数组中值相等两个数,把它们中间的区间颠倒顺序

求$n^2$次数内的方案得到B

范围

n 500

1s

256MB

题解

我的思路

没有思路

只知道首个和末个 有重复的数字的一定位置不会变,且它们两侧的也不会变

但如何记录翻转并不知道

可行的话, 首先每个值个数要一样

题解

数组不变量

首先a1和an是不会变的

然后是相邻元素构成无序对不变, 因为 区间 v…v颠倒,那么 中间和v连接的依然和v连接

必要显然

充分性, 我们具体构造

假设 前缀 a[..i] 和 b[..i] 相同, a[i] = x

a[i+1] = y

b[i+1] = z

如果存在 a[i..] = [x,y,...,z,x,...] 那么直接翻转 做1次

如果 a[i...] = [x,y,...,x,z,...], 如果 x,z 右侧还有x 则翻转2次

否则 x,z 的x是最后出现的x, 所以, x至少2个

如果x恰好2个, 且是连着 a[i..]= [x,y,x,z,...], b[i..] = [x,z,....y,x,y,...] , 这样转b

否则a[i..] 中 x相邻至少3对相邻

那么根据上面的,只有最后的那一个x的右侧不能通过,x本身交换 完成, 而a和b的操作是对称的

所以 3对中 最多2对无法交换,所以总存在一个相邻,可以0~2次 完成换到a[i..] = [x,?,...]

即只要满足,无序对的性质

那么a[0..i] 一致了 就有办法让b[0..i] 一致

直接暴力找 O(n^2)

注意到的是算法实际的次数是不超过4n的

而需要的是小于$n^2$的次数,所以考察 n=[1..4]的合法的数组的操作次数时候

n=1 0次

n=2 0次

n=3 0次

n=4 0次/1次

所以也满足次数要求

代码

https://codeforces.com/contest/1698/submission/162605498

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

#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)

int read(){int r;scanf("%d",&r);return r;} // read

int n;
int a[510];
int b[510];

// 翻转区间
void rev(int *arr,int i,int j){
  rep(k,i,j+1){
    int rk = j-(k-i);
    if(rk < k)break;
    swap(arr[k],arr[rk]);
  }
}

// 找arr[sti...]中 找 [x,y,...,z,x,...], 翻转成[x,z...]
bool op(int *arr,int sti,int z,vector<pair<int,int>> & ans){
  int x = arr[sti];
  rep(i,sti+1,n){
    // [x,y........z,x]
    // [sti............i]
    if(arr[i] == x && arr[i-1] == z){
      rev(arr, sti+1,i-1);
      ans.push_back({sti+1,i+1});
      return true;
    }
  }
  return false;
}

// 找arr[sti...]中 找 [x,y,...,x,z,...,x,...], 翻转成[x,z...]
bool oprev(int *arr,int sti,int z,vector<pair<int,int>> & ans){
  int x = arr[sti];
  rep(i,sti+1,n){
    // [x,y........x,z,.....x]
    // [sti..........i      j]
    if(arr[i] == z && arr[i-1] == x){
      rep(j,i+1,n){
        if(arr[j] == x){
          rev(arr, sti+1,j-1);
          ans.push_back({sti+1,j+1});
          return op(arr,sti,z,ans);
        }
      }
      return false;
    }
  }
  return false;
}

void w(){
  n = read();
  rep(i,0,n) a[i] = read();
  rep(i,0,n) b[i] = read();
  if(a[0] != b[0]) {
    printf("NO\n");
    return ;
  }
  if(a[n-1] != b[n-1]){
    printf("NO\n");
    return ;
  }
  vector<pair<int,int>> pa;
  rep(i,1,n){
    int u = a[i-1];
    int v = a[i];
    if(u > v) swap(u,v);
    pa.push_back({u,v});
  }
  vector<pair<int,int>> pb;
  rep(i,1,n){
    int u = b[i-1];
    int v = b[i];
    if(u > v) swap(u,v);
    pb.push_back({u,v});
  }
  sort(pa.begin(),pa.end());
  sort(pb.begin(),pb.end());
  if(pa != pb){
    printf("NO\n");
    return ;
  }
  printf("YES\n");
  // 一定可以
  // -------------
  vector< pair<int,int> >ans; // 正向
  vector< pair<int,int> >revans; // 反向
  rep(i,0,n){
    if(a[i] != b[i]){
      int x = a[i-1];
      //
      if(op(   a,i-1,b[i],ans))continue;
      if(oprev(a,i-1,b[i],ans))continue;
      if(op(   b,i-1,a[i],revans))continue;
      if(oprev(b,i-1,a[i],revans))continue;
      int w = -1; // 找既不等于 b[i] 也不等于a[i]的 x相邻的, 至少存在一个
      rep(j,i+1,n){
        if(a[j] == x){
          if(a[j-1] != a[i] && a[j-1] != b[i]){
            w = a[j-1];
          }else if(a[j+1] != a[i] && a[j+1] != b[i]){
            w = a[j+1];
          }
          assert(w!=-1);
          break;
        }
      }
      assert(w!=-1);
      if(!op(a,i-1,w,ans)){
        assert(oprev(a,i-1,w,ans));
      }
      if(!op(b,i-1,w,revans)){
        assert(oprev(b,i-1,w,revans));
      }
    }
  }
  per(i,0,revans.size()) ans.push_back(revans[i]);
  printf("%d\n",(int)ans.size());
  for(auto [u,v]:ans){
    printf("%d %d\n",u,v);
  }
}

int main(){
  int t = read();
  while(t--) w();
  return 0;
}

G

S 是长度n的0/1串

让S与任意个S的任意正位移 做xor

求 结果中1的个数恰好2个,且字符串表示下字典序最大的串中, 这两个1的位置

限制

n 35

2s

256MB

题解

我的思路

显然 第一次取S

然后把首个1以后的内容 的 首个1与S的首个1对齐 做xor, 直到后续剩余的只有1个1

这样的话,S的首个1和末个1各贡献一次, 位置就可以算了

为了简化运算,可以预处理掉S的前后缀0记录下来

然而n有35, 虽然无法估计精确复杂度,但这样做上限是2的35次方会超时,写出来也果然tle 6 了

官方

多项式问题

首先 忽略S前后缀0, 这些零在最后的结果中会加回来

那么把S看作在GF(2)域中多项式P(x)

Galois Field, 只有0,1二元及+（异或运算）×（与运算）

那么要求的是$P(x)Q(x) = x^k+1$ 的最小k

P(x)的常数项是1, Q是任意的, 所以一定存在

证明, 显然 $x^k$ 随着k增大$x^k \mod P(x)$ 成周期,且始终不为0, 那么周期的就是一个$x^k \mod P(x) = 1$的解

所以$k \le 2^{35}$ 依然很大

要用的方法是meet in middle?

emmmmm 就是直接除 然后meet in middle?

我没懂 这个prod 为何一定是 mod 为1, 以及GF(2)域上的相关性质

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
#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=n;i-->(ll)a;)
#define pb push_back
#define all(x) (x).begin(), (x).end()

int n;
char s0[100];
ll mod;

// (i*j)%mod in GF(2)
ll mul(ll i, ll j) {
  ll res = 0;
  rep(x, 0, n-1) {
    if (i & (1LL << x)) res ^= j;
    j <<= 1;
    if (j & (1LL << (n - 1))) j ^= mod; // 取mod in GF(2)
  }
  return res;
}

// (2**i)%mod in GF(2)
ll pow2(ll pwr) {
  ll res = 1; // result
  ll b = 2; // base
  while (pwr) { // pwr
    if (pwr & 1) res = mul(res, b);
    b = mul(b, b);
    pwr >>= 1;
  }
  return res;
}

// v的二进制最高位1在2的多少幂次, high1(3) = 1
int high1(ll v){
  int leadz = __builtin_clzll(v); // x 前缀0个数
  return 63 - leadz;
}

int main() {
  char *s = s0;
  scanf("%s",s);
  n = strlen(s);
  vector<int> pos; // 只用来判断 <= 2的1
  rep(i,0,n){
    if (s[i] == '1') pos.push_back(i+1);
  }
  per(i,0,n) { // remove trailing zero
    if(s[i] != '0') break;
    s[i] = 0;
  }
  rep(i,0,n) { // remove prefix zero
    if(s[0] != '0') break;
    s++;
  }
  int offset = s - s0; // 前导0
  n = strlen(s);
  if (pos.size() == 0) { // all zero
    printf("-1\n");
    return 0;
  }
  if (pos.size() == 1) { // only 1 of 1
    printf("%d %d\n",pos[0],pos[0]+1);
    return 0;
  }
  if (pos.size() == 2) { // 恰好2个
    printf("%d %d\n",pos[0],pos[1]);
    return 0;
  }
  rep(i, 0, n) { // 正向和逆向结果一样的
    if (s[i] == '1') mod |= (1LL << i); // s.trim().tobinary()
  }
  printf("s: %lld\n",mod);

  int h = (n + 1) / 2; // 半长

  ll val = mod;
  ll prod = 1; // (2**h(x)-1)(2**h(x))**(pwr-1)
  rep(x, 3LL, 1 << h) { // GF(2)乘法还满足结合率
    if (!(x & 1)) continue; // x 末位是1
    int pwr = 0; // val = x^pwr * ... 相当于 计算GF(2) 中 val的因子和幂次
    while (true) {
      ll curr = val;
      ll other = 0;
      rep(bit, 0, n) {
        if (!(curr & (1LL << bit))) continue;
        curr ^= x << bit;
        other ^= 1LL << bit;
      }
      if (curr)  break;
      // val = x * other in GF(2)
      printf("%lld = %lld * %lld\n", val, x, other);
      val = other;
      pwr++;
    }
    if (pwr) { // x的pwr次方
      printf("=> %lld ** %d\n",x,pwr);
      printf("high1[%lld] =  %d\n",x,high1(x));
      // prod *= (10-1) * 10 * 10 ,        3**3
      prod *= (1LL << high1(x)) - 1;
      rep(y, 1, pwr) prod *= 1LL << high1(x);
    }
  }
  // val 的 一次方
  if (val > 1) prod *= (1LL << high1(val)) - 1;
  // mod => GF(2) => 基的幂次 乘积 => (2的幂次)的幂次和2的(幂次-1) 的 积

  ll ans = 1LL << 60;
  // printf("prod:%lld\n",prod);
  assert(pow2(prod) == 1); // 2**prod ???????????????????????????????????????????
  for (ll x = 1; x * x <= prod; x++) { // 长度一定是prod的因子 ????????????????????????????????
    if (prod % x ) continue;
    if (pow2(x) == 1) ans = min(ans, x);
    if (pow2(prod / x) == 1) ans = min(ans, prod / x);
  }
  printf("%d %lld\n",offset+1,offset+ans+1);
}

总结

F

这个交换性质 厉害了,之前并不了解,也没有自己推出

相等的位置的交换,必定让相邻无序对是不变的,而且是充要条件

还是不变量的思考

G

GF(2) 真的没有系统学过

通过这个题看起来 乘法还 满足 结合率

加减也是对称的 A+B= C, A-B=C

参考

官方

洛谷 GF(2)

發表於 更新於 分類於 ， Disqus： 文章字數： 711 所需閱讀時間 ≈ 2 分鐘
D(dfs,无向图无桥联通块,强连通分量)

哎 超时8min过了E,但这个D我还是不会

D

评分2229

题目

https://atcoder.jp/contests/arc143/tasks/arc143_d

左边1-n的点

右边1-n的点

左i-右i有边

给你m对数 (ai,bi), 你需要输出长度为m的0/1字符串

如果你要(左ai-右bi) 则第i个字符为0, 如果你要(左bi-右ai)则第i个字符是1

最终让图里的桥最少, 求一个字符串方案

范围

n 2e5

m 2e5

2s

1024mb

题解

我的思路

只想着贪心

首先如果一个边在任意环里那它就不是桥, 所以希望能贪心尽量让边进入环

统计给的m对数中, 每个值出现的次数

对于只出现一次的无药可救,先不管它

对于出现2次的,那就安排让它左右各连出一个

如果运算过程中某个点一侧被连了,另一侧没有连,还有关于这个点的数对,那么就去连另一测

已经两侧都连了的就不管

但就写的来看似乎有问题, 还蛮多人过了这个题

题解

一句话 把它当成一个未定向的有向图， 然后在图上找环， 并定向即可

首先考虑一个n个点, m边的无向图, 按照ai-bi的连接

如果有边在无向图中也是桥, 那么在题目问题中它只能是桥

对于无向图来说,移除了所有桥以后, 每个连通块可以单独独立处理

所以假设 拿到一个无向连通 无桥图

总有办法给所有边一个方向,让连通图变成强联通图

一个办法就是 直接做dfs树

代码

https://atcoder.jp/contests/arc143/submissions/32806181

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;

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

int read(){int r;scanf("%intd",&r);return r;} // read
int n;
int m;

char s[200010]; // answer
pair<int,int> ab[200010];
vector<array<int,3>> u2[200010]; // {v, ab idx, '0','1'}
bool vis[200010];

void dfs(int u){
  vis[u] = true;
  for(auto [v,i,o]:u2[u]){
    if(s[i]) continue; // 边处理过
    s[i] = (char)o;
    if(!vis[v]) dfs(v);
  }
}


int main(){
  n = read();
  m = read();
  rep(i,0,m) ab[i].first = read();
  rep(i,0,m){
    int a = ab[i].first;
    int b = ab[i].second = read();
    u2[a].pb({b,i,(int)'0'});
    u2[b].pb({a,i,(int)'1'});
  }
  rep(i,1,n+1){
    if(vis[i])continue;
    dfs(i);
  }
  rep(i,0,m){
    if(!s[i]) s[i] = '0';
  }
  printf("%s\n",s);
  return 0;
}

总结

D

知道逻辑以后 10min 随便写了QAQ

我不知道应该怎么归类,信息提取,还是有向图无向图连通性质

我觉得有一点 算是 无向图的无桥联通块 能通过指定所有边 变成有向图的强连通分量这一点吧,但好像又是一个提炼性质

哎

参考

官方题解

發表於 更新於 分類於 ， Disqus： 文章字數： 1.6k 所需閱讀時間 ≈ 5 分鐘
G(线性规划,对偶,DP,矩阵乘法,segtree)H(TODO)

G

给一个长n数列

q个操作或询问

  1. 操作修改 a[i] = v
  2. 询问[l,r] 区间上, 最小处理代价(不真实的修改区间)

f(l,r) = 每次可以对 相邻元素,分别 (-xt,-yt) 或(-yt,-xt) 代价为t

问最小代价和让 a[l..r] 全部小于等于0

范围

n 2e5

q 2e5

x,y [1,1e6]

ai, v [1,1e6]

6s

1024MB

题解

我的思路

因为对称,不妨设 ( x < y)

开始没看到相邻以为任意,那么不就是维护区间和与区间最大值 = max(和/(x+y),最大值/y)

但是要相邻这样肯定不对了, 比如样例1, 不相邻可以3,相邻最少要3.5

单次询问怎么做?

题解

线性规划对偶

https://pic1.zhimg.com/80/v2-b780de4a3bd814944026ad22f51518f8_720w.jpg

$max \sum c_j x_j$

限制

$a_{ij} x_{j} \le b_i$

$x_j \ge 0$

$i=1\cdots m,j=1\cdots n$

它的对偶问题

$min \sum b_i y_i$

限制

$a_{ij} y_{i} \ge c_i$

$y_i \ge 0$

$i=1\cdots m,j=1\cdots n$

我看了很多直觉的举例,反而没有理解,通过公式倒是理解了大流程, 下面youtube链接 感觉很清晰

小写字母表示列向量,大写字母表示矩阵

$max (c^Tx)$

$Ax \le b$

$x \ge 0$

对于任意$y \ge 0$满足

$c^Tx \le y^TAx$

有 $c^Tx \le y^TAx \le y^Tb$, 所以所有都满足,那么它的最大 = 右边的最小

所以对于所有$c^T \le y^TA$, $max(c^Tx) = min(y^Tb)$

$c^T \le y^TA$ 即是$Ay \ge c$

更一般的转化

  1. min max 对换

  2. 列个数x 变成行个数y

  3. 右侧约束 和 表达式系数 兑换

  4. 偏序关系

同偏序: max 变量(xi) 与 0关系 和 min 约束(不等式组xi) 左与右 关系

反偏序: min 变量(xi) 与 0关系 和 max 约束(不等式组xi) 左与右 关系

约束等于 对应 变量无约束

回到题目

线性规划 问题

原数组A

最小化 $\sum_{1\le i < n} a_i+b_i $

限制

$Xa_1+Yb_1\ge A_1$

$Xa_i+Yb_i+Ya_{i-1}+Xb_{i-1}\ge A_i (2\le i < n) $

$Ya_{n-1}+Xb_{n-1}\ge A_n $

$a_i,b_i\ge 0$

那么对偶

最大化 $\sum_{1\le i \le n} A_iz_i $

限制

$xz_i + yz_{i+1} \le 1 (1 \le z < n)$

$yz_i + xz_{i+1} \le 1 (1 \le z < n)$

$z_i \ge 0$

很好的把上面要求的所有系数1变成了右侧的限制

所以$z_i$ 可能取值$0,\frac{1}{y},\frac{1}{x+y}$

如果只有两个, 线性规划很明显 https://www.wolframalpha.com/input?i=2x%2B3y+%3C%3D+1%2C+2y%2B3x+%3C%3D+1

去画3个的3d情况,你会发现,和2d一样虽然有些棱,但如果这个棱上最优,那么棱上的顶点也最优,但这些凸点的坐标都是这三个可能值中

然后就可以dp了

dp[i][0/1/2], 即是算 $max \sum_{j \le i} A_jz_j$

代码

jiangly 的, 他整个G只花了15min??????

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

typedef long long ll;
#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;)
#define pb push_back

#define SEG_ROOT 1,0,n
#define mid (l+r)/2
#define SEG_L 2*p
#define SEG_R 2*p+1
#define SEG_L_CHILD SEG_L,l,mid
#define SEG_R_CHILD SEG_R,mid,r

ll read(){ll r;scanf("%lld",&r);return r;} // read

int n;

int a[200010];

template<class Info,
  class Merge = plus<Info> // 合并方法
  >
  struct SegmentTree {
    const int n;
    const Merge merge;
    vector<Info> info;
    SegmentTree(int n) : n(n), merge(Merge()), info(4*n) {}
    SegmentTree(vector<Info> init) : SegmentTree(init.size()) {
      function<void(int, int, int)> build = [&](int p, int l, int r) { // [l,r) 左闭右开
        if (r - l == 1) { // 线段树叶子节点
          info[p] = init[l];
          return;
        }
        build(SEG_L_CHILD);
        build(SEG_R_CHILD);
        pull(p);
      };
      build(SEG_ROOT);
    }
    void pull(int p) {
      info[p] = merge(info[SEG_L], info[SEG_R]);
    }
    void modify(int p, int l, int r, int x, const Info &v) {
      if (r - l == 1) {
        info[p] = v;
        return;
      }
      if (x < mid) {
        modify(SEG_L_CHILD, x, v);
      } else {
        modify(SEG_R_CHILD, x, v);
      }
      pull(p);
    }
    void modify(int p, const Info &v) {
      modify(SEG_ROOT, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
      if (l >= y || r <= x) return Info(); // 直接省去范围判断, 超过范围提前 返回可参与计算的空状态
      if (l >= x && r <= y) return info[p];
      return merge(rangeQuery(SEG_L_CHILD, x, y), rangeQuery(SEG_R_CHILD, x, y));
    }
    Info rangeQuery(int l, int r) {
      return rangeQuery(SEG_ROOT, l, r);
    }
  };

int x, y;

// 0: 0
// 1: 1/(x+y)
// 2: 1/y
// 线段树每个节点
struct Info {
  double f[3][3];
  Info(ll v = 0) {
    rep(i,0,3){
      rep(j,0,3){
        if (i + j > 2) {
          f[i][j] = -1E18; // 不合法
        } else { // 这里直接 值 * z_i(0,1/(x+y),1/y), 因为转移方程里始终要乘 值
          f[i][j] = (j == 0 ? 0.0 : 1.0 * v / (j == 1 ? x + y : y));
        }
      }
    }
  }
};

// 实现合并方法
Info operator+(const Info &a, const Info &b) {
  Info c;
  rep(i,0,3){
    rep(j,0,3){
      c.f[i][j] = -1E18; // 不合法
      rep(k,0,3){
        // max 矩阵乘法
        c.f[i][j] = max(c.f[i][j], a.f[i][k] + b.f[k][j]);
      }
    }
  }
  return c;
}

int main() {
  int n = read();
  int q = read();

  x = read();
  y = read();
  if (x > y) swap(x, y); // 保证 x<=y

  vector<int> b(n);
  rep(i,0,n) b[i] = read();

  SegmentTree seg(vector<Info>(b.begin(), b.end())); // v => Info(v) => segtree(vector<info()>)

  while(q--) {
    int t = read();
    if (t == 1) {
      int k = read() - 1;
      int v = read();
      seg.modify(k, v);
    } else {
      int l = read() - 1;
      int r = read();
      auto info = seg.rangeQuery(l, r) + Info(); // + Info() 整合最大值,否则需要手动for 去取max
      printf("%.15lf\n",info.f[0][0]);
    }
  }

  return 0;
}

H

https://codeforces.com/contest/1696/problem/H

给一个正整数k

大小为n,元素可重复的集合A

f(集合S) = S中恰好选出k个元素能得到的最大乘积

求 A所有元素个数不小于k的子集B,的f(B)的和

mod 1e9+7

范围

n 600

ai [-1e9,1e9

1.5s

512 MB

题解

我的思路

如果全非负, 则最大k个的乘积

如果全负

k为偶数, 则最小k个的乘积

k为奇数, 则最大k个的乘积

如果有负有非负

k为偶数, 则负 和 非负 分两组, 每组按照绝对值 从大到小,两两成对 构成新的乘积, 一对一对选

如果k 为奇数, 取一个最大非负, 剩下的 和偶数方案一样处理

所以肯定要对原来的集合拍个序

但贡献怎么统计没有思路

题解

选k个指定它们最大? 计算会出现在多少个集合中??

总结

G

低分题做多了, 太久没遇到线性规划了,很久以前学过, 但好像也是系数多限制多变量少的,

然后这个对偶学了一下, 希望下次能有用到的地方???

最后转化可以描述为矩阵max乘法,可以用segtree维护

参考

官方

https://sites.math.washington.edu/~burke/crs/407/notes/section3.pdf

https://www.youtube.com/watch?v=yU8updOR87c

https://blog.csdn.net/qq_43539633/article/details/109150749

0%