D

题目HERE

题目大意

1<=m<=100'000

$ dp[x] =1 + \sum_{j=1}^{m}\frac{dp[gcd(j,x)]}{m} $

求$ans=\sum_{i=1}^{m}\frac{dp[i]}{m}$

上面公式怎么来的呢，一眼可见

解法

我做的时候卡在变形上了

首先，我们观察到右侧的dp中是j与x的gcd，那么也就是取值范围都是 x的约数，那么变形有

$f[n]=1+\sum_{d|n}\frac{f[d]\cdot g(n, d)}{m}$

其中g(n,d)表示 从1到m，和n gcd后结果为d的 数 的个数，也就是

$ g(n, d) = \sum_{i=1}^m[gcd(n, i)=d] $

同时乘上m，并把右侧 的f[n]的部分移到左侧

$(m-\lfloor\frac{m}{n}\rfloor)f[n]=m+\sum_{d|n,d\neq n}f[d]\cdot g(n, d)$

现在问题还有怎么计算g

观察g的表达式，说明i一定是d的倍数，所以可以变成d*?

$ g(n, d) = \sum_{i=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(n,i*d)=d] $

$ g(n, d) = \sum_{i=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(\frac{n}{d},i)=1]$

注意到右侧的 求和部分实际是要gcd=1时，返回1，其它情况返回0，这和

$\mu * 1 = \epsilon$对应，也就是莫比乌斯，$\mu$函数 的因子和的性质，详细内容见下方我之前的莫反总结中写到的性质和证明

$\sum_{i=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{t|gcd(\frac{n}{d},i)}\mu(t)$

$=\sum_{i=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{t|\frac{n}{d},t|i}\mu(t)$

$=\sum_{t|\frac{n}{d}}\mu(t)\cdot \lfloor \frac {\lfloor \frac{m}{d} \rfloor} {t} \rfloor$

$=\sum_{t|\frac{n}{d}}\mu(t)\cdot \lfloor \frac{m}{dt} \rfloor$

综上

$(m-\lfloor\frac{m}{n}\rfloor)f[n]=m+\sum_{d|n,d\neq n}f[d]\sum_{t|\frac{n}{d}}\mu(t)\cdot \lfloor \frac{m}{dt} \rfloor$

官方题解

官方题解

[题解1]

没有看懂后面的变形，怎么突然1就没了，m的系数移动后也没了??

方法也是讲如何计算g(n,d)，计算多少个p=1->m 使得 gcd(p,n)=d

假设用乘法表示n和p，n=d*a,p=d*b, 有1<=p<=m,gcd(a,b)=1,也就是1<=b<=m/d

然后对a因数分解，因此b不能含有a的任何因子，然后用 容斥算，因为n很小最多6个不同的质因子，所以简单dp

[题解2 就是莫反了]

总结

我之前的莫反总结

参考

CODE 代码很丑见谅XD

E

题目HERE

题目大意

n个人 最大5000

m个组 最大5000

每个人有潜力值最大 5000

每个人仅属于一个组

每一轮删除一个指定的人index_i(输入提供)

一共d轮，最大n

每一轮，从各组中选一个人构成数组，选出后放回原来的组，求每一轮的最大mex

mex:{数组中未出现的最小自然数},如 mex{0,1,2,3,6,7} = 4

解法

先倒转顺序，离线处理，把删除人变为向组中加人

网络流

起始节点到各个组节点建一条边，

各组的人向他的潜力值节点建立边

潜力值0 向end建立边

当潜力值i 连接到end后，总流量等于i+1时(因为从0开始)，把潜力值i+1也连接到end

O(轮数*网络流复杂度) <= O(d*(m+n+mex))

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

#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);

#define ST 0
#define END 10005
#define POT(v) (v+5001)

// 0 ,   1-5000 , 5001-10002 10005
// st->1 -> group->1 -> potential(5001+mex+1) ->1(dynamic add) -> end

// reverse order

map<int,int>flow[10010];

int n,m,d;
int p[10010];
int c[10010];
bool notin[10010];
int order[10010];
int ans[10010];
int mex = 0;
int vis[100010];

int dfs(int i,int load){
  if(i == END)return load;
  vis[i] = true;
  for(auto item:flow[i]){
    if(vis[item.first])continue;
    if(item.second != 0){
      int ret = dfs(item.first,min(load,item.second));
      if(ret != 0){
        flow[i][item.first] -= ret;
        flow[item.first][i] += ret;
        return ret;
      }
    }
  }
  return 0;
}

int getflow(){
  int ret = dfs(ST,1);
  rep(i,0,m+1){
    vis[i]=false;
  }
  rep(i,0,5000){
    vis[POT(i)] = false;
  }
  return ret;
}

int main(){
  cin>>n>>m;
  rep(i,1,n+1){
    scanf("%d",p+i);
  }
  rep(i,1,n+1){
    scanf("%d",c+i);
  }
  scanf("%d",&d);
  rep(i,0,d){
    scanf("%d",order+i);
    notin[order[i]] = true;
  }
  // built
  // ST->group
  rep(i,1,m+1){
    flow[ST][i] = 1;
  }
  // group->mex
  rep(i,1,n+1){
    if(notin[i])continue;
    flow[c[i]][POT(p[i])] = 1;
  }
  // mex 0 -> end
  flow[POT(mex)][END] = 1;
  per(i,0,d){
    while(getflow()){
      flow[POT(++mex)][END] = 1;
    }
    ans[i] = mex;
    // [order]->mex
    flow[c[order[i]]][POT(p[order[i]])]+=1;
  }
  rep(i,0,d){
    printf("%d\n",ans[i]);
  }
  return 0;
}

总结

CODE

E

题目HERE

题目大意

数组a[n], 其中2<=n<=100'000,-1'000'000'000<=a[i]<=1'000'000'000

a[i+1]-a[i] >= k[i] ,其中-1'000'000<=k[i]<=1'000'000

q个操作1<=q<=100'000

操作类型1，对a[i] 增加x，其中0<=x<=1'000'000,如果操作后无法满足上面与k的关系，则调整a[i+1]=a[i]+k[i] 直到所有 的值都满足

操作类型2，求sum of a[l->r]

解法

一眼就是个线段树，但是比以往遇到的线段树，要难维护一些，注意一下需要维护的状态

limiaomiao的解法

1. [l->r] 实际的 差: der
2. [l->r] 的差前缀和的和 :sum[l->r] = (der[l])+(der[l]+der[l+1])+...+(der[l]+...+der[r])

build tree

der[o]= der[o<<1] + der[o<<1 | 1] 记录的是a[r]-a[l]的实际差值

sum[o]= sum[o<<1] + sum[o<<1 | 1] + der[o<<1] * length of (o<<1 | 1)

add val

对a[i]增加x的操作

实际是对 a[i-1]和a[i]的差 增加，以及 对a[i]和a[i+1]的差 的减少x

这样，线段树上操作，[这样感觉会被卡，但看limiaomiao的代码 有个神奇操作，加了一个set来记录，哪些的差值和k不同] 这样每次改变值，最多能产生1个 新的和k不同的差，那么每次的时间消耗=1+消耗的不同于k的值

所以总时间 = 操作数+ 总消耗 <= 操作数+ 初始不同的个数+过程中产生的不同的个数，是线性关系

询问

ans_sum[l->r]

=a[l]+...+a[r]

= a[l]*(r-l+1)+ ((der[l])+(der[l]+der[l+1])+...+(der[l]+...+der[r]))

= getval(a[l])×(r-l+1)+query_sum(l->r)

我这里的思路

注意到实际维护的是a[i+1]-a[i]-k[i] >= 0

那么线段树，可以是在数组b[i]=a[i+1]-a[i]-k[i]上面建立

b[i]所以要全非负

build tree

der[o]= der[o<<1] + der[o<<1 | 1] 记录的是a[l->r]的差值再减去这一段k的差值保证非负

sum[o]= sum[o<<1] + sum[o<<1 | 1] + der[o<<1] * length of (o<<1 | 1)

add val

同样 对a[i]增加x的操作

实际是对 a[i-1]和a[i]的差 增加，以及 对a[i]和a[i+1]的差 的减少x

注意到这样的话，增加x的部分就可以先lazy掉，

在减少的部分，如果 der[l->r] < x 那么这一段整个der都是0，可以lazy掉，保证了每次的log级别的操作

除此以外，每次可能访问的时候，把lazy的部分向下分发一下

询问

ans_sum[l->r]

=a[l]+...+a[r]

= a[l]*(r-l+1)+ ((der[l]+k[l])+(der[l]+k[l]+der[l+1]+k[l+1])+...+(der[l]+k[l]+...+der[r]+k[r]))

= getval(a[l])×(r-l+1)+query_sum(l->r)+sum_der_k(l->r)

总结

相比之下 我这样写，线段树的lazytag的多两个lazytag,而且 对于k也要维护一个sum的线段树,更难写

题目HERE

题目大意

给你

a1 个1

a2 个2

…

a8 个8

求用这些数中的一部分相加，得到的 最大的 不大于W的 数为多少

其中

1<=ai<=10^16

0<=W<=10^18

解法

翻译自官方题解

假设在未知的最优解中 i 取c_i个

L = lcm(1,,,,8) = 840

那么c_i可以表示为

c_i= (L/i)*P_i+q_i 根据除法余数性质可以让q满足 0<=q<L/i

(L/i)*P_i个i是L的倍数(且是1,2,3,4…倍 占满)（小学未知数乘法?）

所以只用枚举q_i的部分

然而这样 所有方案840**8/8/7/6/5/4/3/2/1=6147715553280000000时间内肯定过不了

dp[1->x types of items][weight] = 把构成weight的部分去除后 还能最多有多少个L 这里的构成

空间O(8*8L)

时间O(8L*sum(L/1+L/2+...+L/8))

ans = max{ weight + L * min(dp[0][weight],(W-j)/L) (0<=weight<=8L)

代码

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;

const int N = 9;
const int L = 840;

typedef long long li;

li dp[N][L * N];
li W;
li cnt[N];

int main()
{
  cin >> W;
  for(int i = 0; i < 8; i++)
    cin >> cnt[i];
  for(int i = 0; i < N; i++) for(int j = 0; j < L * N; j++) dp[i][j] = -1;
  dp[0][0] = 0;
  for(int i = 0; i < 8; i++)
  {
    for(int j = 0; j < L * N; j++)
    {
      if(dp[i][j] == -1) continue;
      int b = L / (i + 1);
      if(cnt[i] < b)
        b = cnt[i];
      for(int k = 0; k <= b; k++)
      {
        li& d = dp[i + 1][j + k * (i + 1)];
        d = max(d, dp[i][j] + (cnt[i] - k) / (L / (i + 1)));
      }
    }
  }
  li ans = 0;
  for(int j = 0; j < L * N; j++)
  {
    if(j > W || dp[8][j] == -1)
      continue;
    ans = max(ans, j + L * (min(dp[8][j], (W - j) / L)));
  }
  cout << ans << endl;
}

C

题目HERE

题目大意

n 个点 (1<=n<=100000)

m 条边 (1<=m<=100000)

有向图

从端点1出发，总共走d (1<=d<=50)天，每天能走一条边，能访问多少个不同的开放的点

开放时间表 n*d,0表示N号点 在D天关闭，1表示开放

解法

翻译自官方题解

新建一个图

图上的点为 ([1->n],[0->d-1]) O(nd)

如果原来题目图上有(u,v)

建立边 (u,t) -> (v,(t+1)%d) , O(m d d)

然后算 新图 的强连通分量，对每一个强连通分量缩点，计算 不同的开放的点的个数 = cost

在新的DAG上求最长路

假设一个点u 在新图中拆成 (u,j1)和(u,j2),也就是u 能通过某些边走到j1，注意到，新图里的边只和原图是否连通有关，所以 (u,j2) 能走到(u,(j2+(j2-j1))%d) 沿着j1->j2的路径，沿着这条路径走d-1次，那么走到(u,(j2+(d-1)(j2-j1))%d) = (u,j1+d*(j2-j1)%d) = (u,j1) 所以如果(u,j1)和(u,j2)弱连通，则它们强连通

在新的DAG(缩点后的)上 不会存在2个 u

在DAG有向无环图上 做dp

代码

待补

D

题目HERE

题目大意

交互题

1<= t,c,(t+c)<=1000

有一条链表，这个链表上有一个环，其中环的部分长度为c，非环的部分长度为t

从非环的部分开始走，目的地是 环和非环的交界处，也就是环的入口(环上)

不知道t和c

一共有10个单位可以用来走

交互次数应当<=3(t+c)

交互:

每次提供 需要移动的单位列表，比如2 4 5，那么意味着 2号 4号 5号 沿着链表跳向下一个节点

每次操作返回 哪些单位在同一个点上,如129 3745 680 表示，1号2号9号在一个点上，3.7.4.5在一个点上..

当你认为所有点都走到入口上的时候，输出done

解法

分成 甲 乙 丙

甲1步
乙2步

甲t步，乙2*t步在环上，变成环上追击问题，距离为 (c-(2t-t)%c)%c = (c-t%c)%c

然后，甲乙丙，都走1步

当丙进入环时，步数为t

甲和乙相遇后一起走，所以位置相同，甲的步数这时候为 (t+ (c-t%c)%c)+t

注意到(t+ (c-t%c)%c)是c的倍数，也就是，丙刚进入时，甲和乙也同时走到了环的入口

总耗时2(t+(c-t%c)%c)+t = 3t + 2(c-t%c)%c < 3t+3c = 3(t+c)

解了

题目HERE

题目大意给

01串 长度<=100

每次可以任选一段连续的相同数字的串删掉，删掉的代价为cost[长度]，删掉后 原来的串两端相连，求这样操作直到删空，cost和的最大值

如 0011100 删掉中间连续3个1 变成0000，并且获得cost[3]

样例

1
2
3

7
1101001
3 4 9 100 1 2 3

输出109

1101001 → 111001 → 11101 → 1111 → ∅.

解法

状态 dp[开始index][结束index(不包括)][?->开始index 相同的数字的长度len]

[开始index,结束index)且开始的左边还有 len-1个和s[开始index]相同的数字

状态转移

dp[start][end][len] = max(A[len]+dp[start+1][end][1],max(dp[start+1][itr][1]+dp[itr][end][len+1])), 其中s[itr] == s[start]

举例解释

1
2
3
4
5
6

11111100001111011
yyyy
   s             e
          i
   4=len
    xxxxxx

上面假设在求 dp[s][e][len]

那么A[len]+dp[s+1][end][1]表示先一次处理掉yyyy对应部分 再处理s以后的部分

那么dp[s+1][i][1]表示把xxxxx对应部分处理掉的代价,dp[i][e][len+1]表示的是 处理掉xxxxx这部分后，在处理剩余部分的代价

所以最终，答案就是dp[0][N][1]

状态O(n^3)状态转移O(N)所以总时间复杂度 O(N^4)

code