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

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

USACO4.4.1

输入

给你n(2<=n<=32)个点,m(0<=m<=1'000)条边,可包含重边,每条边权重c(0<=c<=2'000'000)

求/输出

最大流

让最小割被割的边数量最小,求该最小值

求在该最小值下,求字典序最小的最小割

解法

忽略0边[如果不忽略,可能在后面的问产生问题]

第一问最大流:最大流就增广路径

第二问:因为要求,让最小割的被割边的数量也最小,在进行最大流后,对所有满载且原始边不为0的边容量改为1,残余改为inf,再进行一次求最大流

第三问:在第二问基础上枚举删边,检查可能性,标记边.在原图上采取枚举删边,

关于此题

有看到这样的解法来处理二三问,把所有边按容量降序排列依次删边尝试,据说能过USACO,然而有反例[USACO数据真弱2333]

1
2
3
4
5
6
3 5
1 2 1
1 2 1
1 2 4
2 3 3
2 3 3

很明显总流量是6,要让最小割的数量最小是点2到点3 的两条流量为3的边

据说,有人的方案是把边容量乘1001再加上边index来做为新容量,从而最小边取%1001,最大流取/1001

测试数据里似乎没有c=0的时候

第二问的操作inf,必要性,简单的反例解释

1
2
3
4
5
6
7
8
4 7
1 2 7
2 3 7
1 3 2
3 4 2
3 4 2
3 4 2
3 4 2

明显1到3的流量可以达到9,而3到4的流量只有8

所以最小割一定是3到4,但如果耗尽改为1的话,且1到2,2到3都被耗尽,则有1到2,2到3都改为流量1,进行做第二问

如果不把1到3的2 改为inf,则会 认为最少的割边数量为3,而不是4

同样第二问结果并不能直接用于第三问,进行尝试删边,样例

1
2
3
4
5
6
4 5
1 2 4
2 3 2
2 4 2
1 3 100
3 4 2

最小割应该为 2->4 和3->4,如果1->2耗尽,在第二问变更后的图做尝试删边操作,则会发现1->2会影响流量,认为1->2属于割边

代码

code

發表於 更新於 分類於 ， Disqus： 文章字數： 694 所需閱讀時間 ≈ 2 分鐘
E 简单三分(CF EDU 55E)

EDU55E

输入

给你n(1<=n<=500'000)个数字(1<=a[i]<=500'000)和 一个目标值 c(1<=c<=500'000)

要求

任选连续一段加上任意值,使最后的c的出现次数最多,

输出

c最多出现的次数

解法

假设选的区间[l,r]是顶着头,或者 抵着尾的,那么和明显

ans= min(max{[0,i)出现k数字的次数}+[i,n)出现c的次数,max{[i,n)出现k数字的次数}+[0,i)出现c的次数)

用前缀和,可以O(n)做出,问题是无法解决 原数组1 2 1 目标是1的这种,只需要改中间的部分的.

想法1是 做分治

f(l,r) = max(fl(l,mid)+fr(mid,r),max(f(l,mid),f(mid,r)))

fl: c...c?...?

fr: ?...?c...c

也就是划分的mid是否 在选取的区间[l,r]内,问题是 看似分治了,但fl(l,mid)+fr(mid,r) 无法处理替换段是一样的情况,如果要处理时间复杂度不会够

之后想法是dp

因为可以观察到如果选取的值为v,那么整个数组上统计出现个数的时候采取的是形如

c…cv…vc…c的形状(其中每个形状均可以长度为0),那么也就是可以dp[state][i]来做,state分为第一段 第二段 第三段,

这样看上去是n*m的,但是 实际上当我们走到i的时候,只有a[i]的dp需要更改,所以是O(n)的

dp的整理

既然上面也观察到进行到i,只会影响到a[i]相关,那么可以把不同数字的都整合到一起,因为只会有当前a[i]对i位置的进行写和读(==c的会有其它读)

考虑形状

1
2
c...c?...?c...c
         i

那么有 ans = max{ [0,i] 中前部分选c后部分选a[i]的最大次数+[i+1,n-1]c出现的次数 }

1
2
3
[0,i]中前部分选c后部分选a[i]的最大次数
= [0,i]中a[i]的次数 + max{[0,j]选c相对于选a[i]的增量} 其中0<=j<=i
= [0,i]中a[i]的次数 + max{[0,j]选c-[0,j]选a[i]} 其中0<=j<=i

至此上面皆可前缀和

1
2
3
4
5
6
7
8
9
i = 1 -> n:
  sumc[i] = sumc[i-1] + (a[i] == c); // 前缀和,求到i个 有多少个c
  sumci[i] = sumci[pre[a[i]]]+1; // 前缀和,求到i个 有多少个a[i]
  maxder[i]=max(maxder[pre[a[i]]],sumc[i-1]-sumv[i]+1); // [0->j] 计算a[i] -> c变化的最大增量
  pre[a[i]]=i; // pre记录a[i]上一次出现的位置
}
ans <- 0;
i = 0 -> n;
  ans=max(ans,maxder[i]+sumci[i]+(sumc[n]-sumc[i])); // 增量+[0,i]中a[i]的个数+[i+1,n-1]中c的个数

代码

code

發表於 更新於 分類於 ， Disqus： 文章字數： 628 所需閱讀時間 ≈ 2 分鐘
B(容斥)

497D1B

输入

t个询问(1<=t<=100'000)

每个询问A,B,C (1<=A,B,C<=100'000)

要求

若a是A的因子，b是B的因子，c是C的因子，则(a,b,c)记为1种方案

(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)视作同一种方案

输出

求总方案数

解法

看了别人超级宽的代码后 才看懂解法，虽然我第一眼也知道是个容斥

首先众所周知，预处理每个数的因子个数。

然后把A的因子个数 分为{A独有的因子的个数，仅AB共有的因子的个数，仅CA共有的因子的个数，ABC共有的因子的个数}

对B和C同样的处理，然后 就会发现，不过是个4*4*4的排列组合(因为不同的分化之间相互不重叠)，注意去重,就随便写都过了，毕竟O(4*4*4*100'000)

497D1B

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (int i=a;i<n;i++)

int yzcnt[100010];

void init(){
  rep(i,1,100001)
    yzcnt[i]++;
  rep(i,2,100001){
    rep(j,1,100000/i+1){
      if(i*j<100001){
        yzcnt[i*j]++;
      }
    }
  }
}

int gcd(int a,int b){
  return b==0?a:gcd(b,a%b);
}

ll calc(ll *v1,ll *v2,ll *v3){
  if(v1 == v2 && v2 == v3){
    return (*v1)*(*v1+1)*(*v1+2)/6;
  }
  if(v1 == v2){
    return (*v3)*((*v1+1)*(*v1)/2);
  }
  if(v2 == v3){
    return (*v1)*((*v2+1)*(*v2)/2);
  }
  if(v3 == v1){
    return (*v2)*((*v3+1)*(*v3)/2);
  }
  return (*v1)*(*v2)*(*v3);
}

int ec(int a,int b,int c){
  return c+7*(b+7*a);
}

int main(){
  init();
  int t;
  cin>>t;
  while(t-->0){
    int v[3];
    scanf("%d %d %d",v,v+1,v+2);
    int gab= gcd(v[0],v[1]);
    int gbc= gcd(v[1],v[2]);
    int gca= gcd(v[2],v[0]);
    int gabc= gcd(gab,v[2]);

    // 计算每一个的仅有的部分
    /*0*/ll a = yzcnt[v[0]] - yzcnt[gab] - yzcnt[gca] + yzcnt[gabc];
    /*1*/ll b = yzcnt[v[1]] - yzcnt[gbc] - yzcnt[gab] + yzcnt[gabc];
    /*2*/ll c = yzcnt[v[2]] - yzcnt[gca] - yzcnt[gbc] + yzcnt[gabc];
    /*3*/ll ab = yzcnt[gab] - yzcnt[gabc];
    /*4*/ll bc = yzcnt[gbc] - yzcnt[gabc];
    /*5*/ll ca = yzcnt[gca] - yzcnt[gabc];
    /*6*/ll abc = yzcnt[gabc];

    // 用于4*4*4的枚举
    ll *slotA[] = {&a,&ab,&ca,&abc};
    ll *slotB[] = {&b,&bc,&ab,&abc};
    ll *slotC[] = {&c,&ca,&bc,&abc};

    // 用于上面枚举的去重
    int slotMaskA[] = {0,3,5,6};
    int slotMaskB[] = {1,4,3,6};
    int slotMaskC[] = {2,5,4,6};
    bool masks[7*7*7];
    rep(i,0,7*7*7){
      masks[i] = false;
    }

    // 枚举
    ll ans = 0;
    rep(i,0,4){
      rep(j,0,4){
        rep(k,0,4){
          int maskarr[] = {slotMaskA[i],slotMaskB[j],slotMaskC[k]};
          sort(maskarr,maskarr+3);
          int code = ec(maskarr[0],maskarr[1],maskarr[2]);
          if(!masks[code]){// 去重
            masks[code] = true;
            ans +=calc(slotA[i],slotB[j],slotC[k]);
          }
        }
      }
    }
    printf("%lld\n",ans);
  }

  return 0;
}

代码

497D1B

参考

493D1C 官方题解

493D1C Petr的代码

497D1B wavator超级宽的代码

發表於 更新於 分類於 ， Disqus： 文章字數： 1.3k 所需閱讀時間 ≈ 4 分鐘
容斥(493D1C,497D1B)

493D1C

输入

给你n*n(1<=n<=1'000'000)的格子

要求

每个格子 图上 有3种颜色可以选择，

如果所有格子都上完色后， 存在一列或一行的颜色全部相同，则称作lucky

输出

求 所有lucky的方案数 modulo 998244353

解法

翻译自官方

A{i}表示 有i 行 颜色相同
B{i}表示 有i 列 颜色相同

然后直接 容斥原理公式(搜索一下就能找到的公式) 计算 $A_1 \cup A_2 \ldots A_n \cup B_1 \cup B_2 \ldots B_n$

然后因为 这些行列在哪里和我们的计算无关，所以对于A{i}可以看成选i行，让这i行每行内颜色相同，也就是C(n,i)倍的 方案数

所以有那个公式$ans = \sum_{i=0 \ldots n, j=0 \ldots n, i + j > 0} C_n^i C_n^j (-1)^{i + j + 1} f(i, j)]$

f(i,j)表示前i行j列 lucky的方案数

然后 具体表示f(i,j)

i,j其中一个有0的情况，这种情况，以行举例来说，同色的行 之间是可以不同色的，所以是$3^k$

$f(k, 0) = f(0, k) = 3^k \cdot 3^{n (n - k)}$

其它情况，这样的话 因为 如果至少有1行+1列是同色的，那么所有的同色的行列 都是同色的，这样就是3

$f(i, j) = 3 \cdot 3^{(n - i)(n - j)}$

很明显 这个n，肯定不是能做出来的

那么 分两块，ij带0的 O(n)时间内算出

其它部分 看数学操作了,首先 带入f(i,j)

$ans=\sum_{i=1}^{n}\sum_{j=1}^{n}C_n^iC_n^j(-1)^{i+j+1}3\cdot3^{(n-i)(n-j)}$

换元 $i \to n-i, j \to n - j$

$ans = 3 \sum_{i=0}^{n - 1}\sum_{j = 0}^{n - 1} C_n^{n - i} C_n^{n - j} (-1)^{n - i + n - j + 1} \cdot 3^{ij}$

等价化简

$ans = 3 \sum_{i=0}^{n - 1} \sum_{j = 0}^{n - 1} C_n^i C_n^j (-1)^{i + j + 1} \cdot 3^{ij}$

分离

$ans = 3 \sum_{i=0}^{n - 1} C_n^i (-1)^{i+1} \sum_{j = 0}^{n - 1} C_n^j (-1)^{j} \cdot (3^i)^j$

乘法分配率

$ans = 3 \sum_{i=0}^{n - 1} C_n^i (-1)^{i+1} \sum_{j = 0}^{n - 1} C_n^j (- 3^i)^j$

考虑对后面的求和简化，考虑下面式子

$(a + b)^n = \sum_{i = 0}^{n} C_n^i a^i b^{n - i}$

这里 我们把a取1，b取$-3^i$，再注意到求和到n不是n-1，进行一个加减消除，最后可以把ans化简为

$ans = 3 \sum_{i=0}^{n - 1} C_n^i (-1)^{i+1} [(1 + (-3^i))^n - (-3^i)^n]$

这个式子，可以累加求和在O(n)时间内做出了

众所周知的 模逆元 快速幂 取模什么的就不说了

感觉这里分类是我的问题，我自己想 始终把三个颜色分开想怎么计算，这里合在一起了。

497D1B

输入

t个询问(1<=t<=100'000)

每个询问A,B,C (1<=A,B,C<=100'000)

要求

若a是A的因子，b是B的因子，c是C的因子，则(a,b,c)记为1种方案

(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)视作同一种方案

输出

求总方案数

解法

看了别人超级宽的代码后 才看懂解法，虽然我第一眼也知道是个容斥

首先众所周知，预处理每个数的因子个数。

然后把A的因子个数 分为{A独有的因子的个数，仅AB共有的因子的个数，仅CA共有的因子的个数，ABC共有的因子的个数}

对B和C同样的处理，然后 就会发现，不过是个4*4*4的排列组合(因为不同的分化之间相互不重叠)，注意去重,就随便写都过了，毕竟O(4*4*4*100'000)

497D1B

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (int i=a;i<n;i++)

int yzcnt[100010];

void init(){
  rep(i,1,100001)
    yzcnt[i]++;
  rep(i,2,100001){
    rep(j,1,100000/i+1){
      if(i*j<100001){
        yzcnt[i*j]++;
      }
    }
  }
}

int gcd(int a,int b){
  return b==0?a:gcd(b,a%b);
}

ll calc(ll *v1,ll *v2,ll *v3){
  if(v1 == v2 && v2 == v3){
    return (*v1)*(*v1+1)*(*v1+2)/6;
  }
  if(v1 == v2){
    return (*v3)*((*v1+1)*(*v1)/2);
  }
  if(v2 == v3){
    return (*v1)*((*v2+1)*(*v2)/2);
  }
  if(v3 == v1){
    return (*v2)*((*v3+1)*(*v3)/2);
  }
  return (*v1)*(*v2)*(*v3);
}

int ec(int a,int b,int c){
  return c+7*(b+7*a);
}

int main(){
  init();
  int t;
  cin>>t;
  while(t-->0){
    int v[3];
    scanf("%d %d %d",v,v+1,v+2);
    int gab= gcd(v[0],v[1]);
    int gbc= gcd(v[1],v[2]);
    int gca= gcd(v[2],v[0]);
    int gabc= gcd(gab,v[2]);

    // 计算每一个的仅有的部分
    /*0*/ll a = yzcnt[v[0]] - yzcnt[gab] - yzcnt[gca] + yzcnt[gabc];
    /*1*/ll b = yzcnt[v[1]] - yzcnt[gbc] - yzcnt[gab] + yzcnt[gabc];
    /*2*/ll c = yzcnt[v[2]] - yzcnt[gca] - yzcnt[gbc] + yzcnt[gabc];
    /*3*/ll ab = yzcnt[gab] - yzcnt[gabc];
    /*4*/ll bc = yzcnt[gbc] - yzcnt[gabc];
    /*5*/ll ca = yzcnt[gca] - yzcnt[gabc];
    /*6*/ll abc = yzcnt[gabc];

    // 用于4*4*4的枚举
    ll *slotA[] = {&a,&ab,&ca,&abc};
    ll *slotB[] = {&b,&bc,&ab,&abc};
    ll *slotC[] = {&c,&ca,&bc,&abc};

    // 用于上面枚举的去重
    int slotMaskA[] = {0,3,5,6};
    int slotMaskB[] = {1,4,3,6};
    int slotMaskC[] = {2,5,4,6};
    bool masks[7*7*7];
    rep(i,0,7*7*7){
      masks[i] = false;
    }

    // 枚举
    ll ans = 0;
    rep(i,0,4){
      rep(j,0,4){
        rep(k,0,4){
          int maskarr[] = {slotMaskA[i],slotMaskB[j],slotMaskC[k]};
          sort(maskarr,maskarr+3);
          int code = ec(maskarr[0],maskarr[1],maskarr[2]);
          if(!masks[code]){// 去重
            masks[code] = true;
            ans +=calc(slotA[i],slotB[j],slotC[k]);
          }
        }
      }
    }
    printf("%lld\n",ans);
  }

  return 0;
}

代码

497D1B

参考

493D1C 官方题解

493D1C Petr的代码

497D1B wavator超级宽的代码

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

关于 强连通分量 缩点 tarjan是什么 自行搜索，这里只是封了一个板子

Codeforces Round #490 (Div. 3) E题

题目一眼可得tarjan 也不是一次两次了 封了板子，最开始还想做个模板类，但仔细一想，时间复杂度导致点个数不会超int，所以如果点序号大于int先离散化再做

E题 AC CODE

板子如下

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
/* construct: vertexsize
 *    auto tarjan = new Tarjan(vertex_size)
 *
 * addpath // 1<=from_vertex,to_vertex<= vertex_size
 *    tarjan.addpath(from_vertex,to_vertex)
 *
 * prepare an result array,and work
 *    int res[vertex_size+1];
 *    tarjan.work(res);
 *
 * return:
 *    res[vertex_id]  ===== after_tarjan_vertex_group_id
 */
class Tarjan{
  int *low;// lowest node
  int *dfn;// deep first node
  int *stk;// stack
  bool *instk;
  bool *visited;

  vector<int> * p; // one-way road
  int stki;
  int id;
  int n;
  // strongly connected components强联通分量
  void scc(int v) {
    low[v] = dfn[v] = ++id;
    stk[stki++] = v;
    instk[v] = true;
    visited[v] = true;
    for(auto w:p[v]){
      if(!visited[w]){
        scc(w);
        low[v] = min(low[v],low[w]);  //v或v的子树能够追溯到的最早的栈中节点的次序编号
      } else if(instk[w]){ //v->w后向边
        low[v] = min(low[v],dfn[w]);
      }
    }
    int u;
    if(low[v] == dfn[v])  {
      do{
        u = stk[--stki];
        dfn[u] = v;  //缩点
        instk[u] = false;    //出栈解除标记
      }while(u != v);
    }
  }
public:
  Tarjan(int SZ){
    n = SZ;
    low =  new int[n+1];
    stk =  new int[n+1];
    dfn =  new int[n+1];
    instk = new bool[n+1];
    visited = new bool[n+1];
    p = new vector<int>[n+1];
    rep(i,0,n+1){
        visited[i] = false;
    }
    id = 0;
    stki = 0;
  }
  ~Tarjan(){
    delete [] low;
    delete [] stk;
    delete [] dfn;
    delete [] instk;
    delete [] visited;
    delete [] p;
  }
  void work(int *ret){
    rep(i,1,n+1){
      if(!visited[i]){
        scc(i);
      }
    }
    rep(i,1,n+1)
      ret[i]=dfn[i];
  }
  void addpath(int i,int j){
    p[i].pb(j);
  }
};

基本上 使用分3个步骤就好

  1. 根据size初始化

  2. 给它加单向边.addpath(from,to)

  3. 准备一个结果数组a，调用.work(a)

  4. 得到的结果数组a[原来的点序号]=缩点后的点序号

  5. emmm 需要加两个宏使用 #define rep(i,a,n) for (int i=a;i<n;i++) 和 #define pb push_back

增强复用+简化

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

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

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);
    stk = {};
    vector<int>(n+1);
    dfn = vector<int>(n+1);
    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);
  }
};

int main(){
  int n,m;
  // 点,有向边,
  cin>>n>>m;
  Tarjan tarjan(n);
  rep(i,0,m){
    int u,v;
    scanf("%d %d",&u,&v);
    tarjan.p2(u,v);
  }
  vector<int> num = tarjan.calc(); // scc 联通分量 标识
  rep(i,1,n+1){
    printf("%lld: %d\n",i,num[i]);
  }
  return 0;
}

/**
1->2->3->1
3->4->5

5 5
1 2
2 3
3 1
3 4
4 5
 */

简述操作

tarjan(u)

  1. 深搜: 标记序号, 到达最小, u进栈
  2. 子点v未访问(dfn[v] == 0), 递归tarjan(v), low[u] = min(low[u],low[v])
  3. 子点v在栈中(result[v] == 0), low[u] = min(low[u],深搜序号[v])
  4. 当low[u] == dfn[u]时, 逐个出栈直到遇到u, 这些出栈的都是属于u这个联通分量 result[i] = u
0%