EDU-102-Div2

# edu_102_div2

[toc]

## A Replacing Elements

考虑最小的两个元素的和是否小于等于 $d$ 即可。

## B String LCM

枚举两个串的“GCD串”即可，注意`C++`中`substr`的使用。

## C No More Inversions(构造好题)

题目描述：
![0](https://picture-bed-bucket.oss-cn-beijing.aliyuncs.com/img/20210116015556.png)

题解：
![1](https://picture-bed-bucket.oss-cn-beijing.aliyuncs.com/img/20210116015721.png)

自己的理解回头再整理，基本和上面的一致，我寻思这构造的思路挺难想的，自己铁five一个，淦。
发现性质 $\Rightarrow$ 序列拆解以及逆序对总数分析 $\Rightarrow$ 构造

## D Program

考虑将减号看作-1，加号看作1。计算前缀和数组s。
ST表维护区间最值。
每次询问的答案一定是去除该区间后剩下序列顺序操作能够得到的最大值减最小值+1（若0不在最大值与最小值之间说明0卡在区间边缘要再加一个1）.
而剩下序列顺序操作能够得到的最值可能又两种情况：
（1）前缀和数组在[1,l-1]的最值（ST表查询）
（2）前缀和数组在[r+1,n]的最值（ST表查询）再减去[l,r]区间本身的贡献。

```cpp
#include<bits/stdc++.h>
using namespace std;
#define N 200020
int op[N], s[N], st1[N][20], st2[N][20], n, m;
int a1[N], a0[N]; // 用于计算区间内加号以及减号的个数
char ch[N];
void init(){
    scanf("%d%d", &n, &m);
    scanf("%s", ch + 1);
    a1[0] = a0[0] = s[0] = 0;
    for(int i = 1; i <= n; i++){
        a1[i] = a1[i - 1]; a0[i] = a0[i - 1];
        if(ch[i] == '-') op[i] = -1, a0[i]++;
        else op[i] = 1, a1[i]++;
        s[i] = s[i - 1] + op[i];
    }
    return ;
}
void pre_st(){
    // 计算前缀和数组s[]的st表，维护区间最大、最小值
	for(int i = 1; i <= n; i++) st1[i][0] = s[i];
	for(int i = 1; i <= n; i++) st2[i][0] = s[i];
	for(int k = 1; (1 << k) <= n; k++){
		for(int i = 1; i + (1 << k) - 1 <= n; i++){
			st1[i][k] = min(st1[i][k - 1], st1[i + (1 << (k - 1))][k - 1]);
			st2[i][k] = max(st2[i][k - 1], st2[i + (1 << (k - 1))][k - 1]);
		}
	}
    return ;
}

// ST表查询区间最小值
int query_min(int l, int r){
    if(l > r) return INT_MAX / 2; // 防止solve中溢出
	int k = 0;
	while((1 << (k + 1)) <= r - l + 1) k++;
	int minx = min(st1[l][k], st1[r - (1 << k) + 1][k]);
	return minx;
}
// ST表查询区间最大值
int query_max(int l, int r){
    if(l > r) return INT_MIN / 2; // 防止solve中溢出
	int k = 0;
	while((1 << (k + 1)) <= r - l + 1) k++;
	int maxx = max(st2[l][k], st2[r - (1 << k) + 1][k]);
	return maxx;
}

void solve(int l, int r){
    if(l == 1 && r == n){
        cout<<1<<endl;
        return ;
    }
    int max1 = query_max(1, l - 1);
    int max2 = query_max(r + 1, n) - (a1[r] - a1[l - 1]) + (a0[r] - a0[l - 1]);
    int maxx = max(max1, max2);
    int min1 = query_min(1, l - 1);
    int min2 = query_min(r + 1, n) - (a1[r] - a1[l - 1]) + (a0[r] - a0[l - 1]);
    int minx = min(min1, min2);
    int o = 0;
    if(minx > 0 || maxx < 0) ++o;
    printf("%d\n", maxx - minx + 1 + o);
    return ;
}
int main(){
    int T; cin>>T;
    while(T--){
        init();
        pre_st();
        while(m--){
            int l, r; scanf("%d%d", &l, &r);
            solve(l, r);
        }
    }
    return 0;
}
```

## E Minimum Path

![1](https://picture-bed-bucket.oss-cn-beijing.aliyuncs.com/img/20210116120708.png)

两点：
1.问题转化与证明
2.构造状态并建图

![2](https://picture-bed-bucket.oss-cn-beijing.aliyuncs.com/img/20210116120848.png)
建图如下：
(x,f1,f2)表示点x，发
表示是否已走了一条double边，f2表示是否已经跳过了一条边。
下图为无向边(x,y,z)的拆点后的状态转移图示。
![4](https://picture-bed-bucket.oss-cn-beijing.aliyuncs.com/img/20210116133906.png)
更清楚的图示：
![3](https://picture-bed-bucket.oss-cn-beijing.aliyuncs.com/img/20210116133541.png)

```cpp
#include<bits/stdc++.h>
using namespace std;
#define N 220000
typedef long long ll;
struct edge{
    int to, val, nxt;
}e[N * 20];
int head[N * 4], vis[N * 4], len, n, m;
ll dist[N * 4];
void add_edge(int from, int to, int val){
    e[++len].to = to; e[len].val = val; e[len].nxt = head[from]; head[from] = len; return ;
}
void init(){
    len = 0; 
    scanf("%d%d", &n,&m);
    for(int i = 1; i <= m; i++){
        int x, y, z; scanf("%d%d%d", &x, &y, &z);
        add_edge(x, y, z); add_edge(y, x, z);
        add_edge(x + n, y + n, z); add_edge(y + n, x + n, z);
        add_edge(x + 2 * n, y + 2 * n, z); add_edge(y + 2 * n, x + 2 * n, z);
        add_edge(x + 3 * n, y + 3 * n, z); add_edge(y + 3 * n, x + 3 * n, z);

add_edge(x, y + n, 0); add_edge(y, x + n, 0);
        add_edge(x, y + 2 * n, 2 * z); add_edge(y, x + 2 * n, 2 * z);
        add_edge(x, y + 3 * n, z); add_edge(y, x + 3 * n, z);
        
        add_edge(x + n, y + 3 * n, 2 * z); add_edge(y + n, x + 3 * n, 2 * z);

add_edge(x + 2 * n, y + 3 * n, 0); add_edge(y + 2 * n, x + 3 * n, 0);
    }
    return ;
}
struct qnode{
    ll idx, val;
    qnode(ll x, ll y){idx = x; val = y;}
    bool operator < (const qnode &x) const{
        return val > x.val;
    }
};
void dijkstra(){
    memset(dist, 0x7f/3, sizeof(dist));
    priority_queue<qnode>  q;
    q.push(qnode(1, 0));
    dist[1] = 0;
    while(!q.empty()){
        int cur = q.top().idx; q.pop();
        if(vis[cur]) continue;
        vis[cur] = 1;
        for(int i = head[cur]; i; i = e[i].nxt){
            if(dist[cur] + e[i].val < dist[e[i].to] && !vis[e[i].to]){
                dist[e[i].to] = dist[cur] + e[i].val;
                q.push(qnode(e[i].to, dist[e[i].to]));
            }
        }
    }
    return ;
}

void solve(){
    dijkstra();
    for(int i = 2; i <= n; i++) printf("%lld ", dist[i + 3 * n]);
    return ;
}
int main(){
    init();
    solve();
    return 0;
}
```

epee_no_front's Notes

导航

最近发表

友情链接