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

發表於 更新於 分類於 ， Disqus： 文章字數： 1.6k 所需閱讀時間 ≈ 5 分鐘
G(网络流)H/Ex(分块,讨论)

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

G - Grid Card Game

题目

HxW的数阵

选择任意的一些行和一些列, 让被选到的所有格子的和最大(同时被行和列选只统计一次)

且 限制条件,如果格子上的值为负那么 不能同时选它的行和列

范围

H,W [1,100]

Aij [-1e9,+1e9]

2s

1024mb

题解

我的思路

显然 纯非负的行和列一定被选,

所以可以预处理让剩下的所有行列至少包含一个负数

然后考虑说纯选行或选列

但是显然有反例

1
2
3
  1     -1    100
 -1      1 -10000
100 -10000      1

这种情况 最优的是选1行和1列

然后另一个性质是, 显然 和为非正的行和列不会被选, 因为 如果即选了行又选了列,重叠部分非负 两个都选的和是 小于 两个分别的和的

然后没思路了

题解

首先我们令 结果 = 全部正值 都被选了, 考虑变化对结果的影响

  1. 如果一个正的没有被选, 那么它的行列没有直接被选, -Aij
  2. 如果一个负值被选了, 那么它的行和列有一个被选, Aij

如果 Aij < 0 被选了,

  • 如果是行被选, 那么 影响的是 加上 i行的所有负数

  • 如果是列被选, 那么 影响的是 加上 j列的所有负数

于是改变题目

初始分 = 正数和

那么如果 选了i行, 则 损失 i行的所有负值的和

那么如果 选了j列, 则 损失 j列的所有负值的和

对于正的单元没被选的 损失上面值的代价

对于负的单元, 不恩那个同时选行和列

答案 = 正数和 减去 下面网络流的最小割

点:

R[1..H]

C[1..W]

源S,汇T

边:

S->R[i], 容量 行i的所有负值和的绝对值

C[j]->T, 容量 行j的所有负值和的绝对值

R[i] -> C[j] 如果是 Aij > 0, 则 权重 Aij

C[j] -> R[i] 如果是 Aij < 0, 则 权重 无限大

这样考虑

对于 Aij > 0

S->R[i]->C[j]->T 在最小割中, 至少有一条边被割(说至少是因为, 可能 R和T一个集合,S和C一个集合)

对 Aij < 0

也就是最小割一定不会同时割S->R[i],和C[j]->T, 因为如果这样割了

意味着, S,C[j] 是一个集合,R[i],T是一个集合, 就有 C[j] -> R[i] 的无限大, 就不会是最小割了

对于Aij < 0 一定是 S->R[i] 或 C[j]->T, 表示

也就是对于Aij < 0, 至多一个成为割边

然后最小割 = 最大流 Dinic, 或者直接调用官方的maxflow

代码

https://atcoder.jp/contests/abc259/submissions/33171094

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
#include <bits/stdc++.h>
#include <atcoder/maxflow>
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;)

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

int n;
int m;
const int N = 100;

const ll inf = 0x3f3f3f3f3f3f3f3f;
int h, w; // 输入
ll a[N+10][N+10]; // 输入
ll rsum[N+10], csum[N+10]; // 行列负数绝对值和

int main() {
  h = read();
  w = read();
  rep(i,1,h+1){
    rep(j,1,w+1) a[i][j] = read();
  }
  atcoder::mf_graph<ll> g(h+w+2); // 传入点数
  int S = 0; // 源
  int T = h+w+1; // 汇
  ll ans = 0;
  rep(i,1,h+1){
    rep(j,1,w+1){
      if(a[i][j] >= 0){
        ans += a[i][j];
        g.add_edge(i, h+j, a[i][j]); // R[i] -> C[j], a[i][j]
      } else {
        g.add_edge(h+j, i, inf); // C[j] -> R[i], inf
        rsum[i] += -a[i][j];
        csum[j] += -a[i][j];
      }
    }
  }
  rep(i,1,h+1) g.add_edge(S, i, rsum[i]); // S -> R[i], 行负数和的绝对值
  rep(j,1,w+1) g.add_edge(h+j, T, csum[j]); // C[j] -> T, 列负数和的绝对值
  printf("%lld\n", ans - g.flow(S, T));
  return 0;
}

H/Ex - Yet Another Path Counting

NxN的矩阵

每次向右或向下走

问有多少种路径,头和尾所在位置的数字相同

范围

n 400

aij [1,N^2]

2s

1024 MB

题解

我的思路

最朴素就是 对不同值分开处理,直接变成 每个值=> 所有位置

然后 (i0,j0) => (i1,j1) 就是组合数

问题是, 如果一个一算,是(N^4)的样子会TLE

考虑是否有办法把结果变成统计合并

题解

分块

更朴素的纯色+dp是, O(n^2)的

所以对于每个颜色根据个数来做不同处理

如果当前颜色点个数 <= n

显然用我的思路里两两去算, 复杂度不超过O(个数^2),这一类的总复杂度小于O(sum{个数^2}) <= O(sum{n * 个数})<= O(n * sum{个数}) <= O(n^3)

如果当前颜色个数 > n , 那就直接dp,也不超过O(n^2), 而这种最多n种颜色最多O(n^3)

综上

都在n^3内

代码

https://atcoder.jp/contests/abc259/submissions/35946797

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
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint=atcoder::modint998244353;
using namespace std;
#define rep(i,a,n) for(int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}
int a[410][410];
vector<pair<int,int>>b[160010];//value->{i,j}
mint c[410][410];
int main() {
  int n=read();
  rep(i,0,n)rep(j,0,n)b[a[i][j]=read()].push_back({i,j});
  rep(i,0,n)c[0][i]=c[i][0]=1;
  rep(i,1,n)rep(j,1,n)c[i][j]=c[i-1][j]+c[i][j-1];
  mint s=0;
  rep(k,1,n*n+1){//kolour
    if((int)size(b[k])<=n){//点少枚举点对
      for(auto[x0,y0]:b[k])for(auto[x1,y1]:b[k])if(x0<=x1&&y0<=y1)s+=c[x1-x0][y1-y0];
    } else{//点多二维dp
      auto t=vector(n,vector<mint>(n,0));
      rep(i,0,n)rep(j,0,n){
        t[i][j]=(i?t[i-1][j]:0)+(j?t[i][j-1]:0)+(a[i][j]==k);
        if(a[i][j]==k)s+=t[i][j];
      }
    }
  }
  printf("%d\n",s.val());
  return 0;
}

总结

G

感觉 完全对网络流类型不熟,即使看了答案也仅是证明, 感觉没有系统的练习相关的建图, 还是不知道从何而起

这里相当于网络流求的是尽可能删除得小的, 利用了 最小割 = 最大流 , 这也是一个点,要求最小值的时候可以考虑让图能含义到最小割

然后就是atcoder内置的maxflow真香啊

Ex

有一说一感觉比G简单

这个分类的第一个复杂度上限推导还是很有意思,有点像之前树上左右部分平方的dp总复杂度是n3不是n4的感觉

参考

官方题解

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

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

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

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

哎

参考

官方题解

0%