【A】 meeting DFS+LCA

队友AC的，雨我无瓜，大概就是求个树的直径就完事了

给定 (n) 个点和 (n-1) 条边，有 (k) 个人分别在 (k) 个点上，问选择哪一个点作为相遇的点，能使得这些人相遇时间最短，输出相遇时间（每走一条边花一秒）。

考虑距离最远的两个关键点，设它们的距离为 (dis)，(lceil dis/2 ceil) 即为答案。

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

const int maxn = 1e5+5;

vector<int> son[maxn];
int n, k, dep[maxn], fa[maxn][20], in[maxn];
int a[maxn];
int b[maxn], c[maxn];

void dfs(int pre, int rt) {
    dep[rt] = dep[pre] + 1;
    fa[rt][0] = pre;
    for(int i = 1; i < 20; i++) {
        fa[rt][i] = fa[fa[rt][i-1]][i-1];
    }
    for(int i = 0; i < son[rt].size(); i++) {
        if(son[rt][i] != pre)
            dfs(rt, son[rt][i]);
    }
}

int LCA(int x, int y) {
    if(dep[x] < dep[y]) {
        swap(x, y);
    }
    for(int i = 19; i >= 0; i--) {
        if(dep[x] - (1<<i) >= dep[y]) {
            x = fa[x][i];
        }
    }
    if(x == y) {
        return x;
    }
    for(int i = 19; i >= 0; i--) {
        if(fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}

int main() {
    while(~scanf("%d%d", &n, &k)) {
        for(int i = 1; i <= n; i++) {
            son[i].clear();
        }
        memset(in, 0, sizeof(in));
        for(int i = 0; i < n-1; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            son[x].push_back(y);
            son[y].push_back(x);
        }
        dep[0] = -1;
        int rt = 0;
        for(int i = 1; i <= n && rt == 0; i++) {
            if(in[i] == 0) {
                rt = i;
            }
        }
        dep[1] = 0;
        dfs(1, rt);
        for(int i = 1; i <= k; i++){
            scanf("%d", &a[i]);
        }
        int lca, Max = 0, w = 1;
        for(int i = 2; i <= n; i++){
            lca = LCA(a[i], a[1]);
            int x = dep[a[i]]+dep[a[1]]-dep[lca]*2;
            if(x > Max){
                Max = x;
                w = i;
            }
        }
        Max = 0;
        for(int i = 1; i <= n; i++){
            if(i == w) continue;
            lca = LCA(a[w], a[i]);
            int x = dep[a[i]] + dep[a[w]]-dep[lca]*2;
            Max = max(Max, x);
        }
        printf("%d
", (Max+1)/2);

    }
    return 0;
}

【C】 sequence 线段树+单调栈

给定两个长度为 (n) 的序列 (a) 和 (b)，选择一个区间 ([l, r] (1leq lleq rleq n))，使得 (max [min(a_{l...r})*max(b_{l...r})]) 。输出这个最大值。

对于每个 (a_i)，我们找到左边第一个比它小的元素 (a_l)，右边第一个比它小的 (a_r)，那么左端点在 ([l+1,i])，右端点在 ([i,r-1]) 的区间最小值就是 (a_i)。求l和r可以使用单调栈。

得到 (a_i) 后，如果 (a_i>0) 我们就是要最大化 (sum(b[l..r]))。反之亦然。记 (b) 的前缀和为 (s)，那么 (sum(b[l..r])=s[r]-s[l-1])。所以我们只要查询 ([i,r-1]) 最大的 (s) 和 ([l,i-1]) 最小的 (s)，相减即可。查询区间最小值可以使用线段树。

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
const ll inf = 1e16;
const int mod = 1e9 + 7;

const int maxn = 3e6+5;

int a[maxn], b[maxn];
int l[maxn], r[maxn];   // 左（右）边第一个 < ai 的数的位置
ll sum[maxn];
ll MAX[maxn<<2], MIN[maxn<<2];

void push_up(int rt) {
    MAX[rt] = max(MAX[rt<<1], MAX[rt<<1|1]);
    MIN[rt] = min(MIN[rt<<1], MIN[rt<<1|1]);
}

void build(int l, int r, int rt) {
    if(l == r) {
        MIN[rt] = MAX[rt] = sum[l];
        return ;
    }
    int mid = (l+r) >> 1;
    build(l, mid, rt<<1);
    build(mid+1, r, rt<<1|1);
    push_up(rt);
}

ll query_max(int L, int R, int l, int r, int rt) {
    if(L <= l && r <= R) {
        return MAX[rt];
    }
    int mid = (l+r) >> 1;
    ll ans = -inf;
    if(L <= mid) {
        ans = max(ans, query_max(L, R, l, mid, rt<<1));
    }
    if(R > mid) {
        ans = max(ans, query_max(L, R, mid+1, r, rt<<1|1));
    }
    return ans;
}

ll query_min(int L, int R, int l, int r, int rt) {
    if(L <= l && r <= R) {
        return MIN[rt];
    }
    int mid = (l+r) >> 1;
    ll ans = inf;
    if(L <= mid) {
        ans = min(ans, query_min(L, R, l, mid, rt<<1));
    }
    if(R > mid) {
        ans = min(ans, query_min(L, R, mid+1, r, rt<<1|1));
    }
    return ans;
}

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    a[0] = a[n+1] = -(0x3f3f3f3f);
    sum[0] = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
        sum[i] = sum[i-1] + b[i];
    }
    build(0, n, 1);
    
    stack<int> s;
    s.push(0);
    for(int i = 1; i <= n; i++) {   // 找左边
        while(!s.empty() && a[s.top()] >= a[i]) {
            s.pop();
        }
        l[i] = s.top();
        s.push(i);
    }
    while(!s.empty()) {
        s.pop();
    }
    s.push(n+1);
    for(int i = n; i >= 1; i--) {
        while(!s.empty() && a[s.top()] >= a[i]) {
            s.pop();
        }
        r[i] = s.top();
        s.push(i);
    }
    ll ans = -inf;
    for(int i = 1; i <= n; i++) {
        // 左端点在[l+1,i]，右端点在[i,r-1]的区间min就是 ai
        int l1 = l[i];
        int r1 = i-1;
        int l2 = i;
        int r2 = r[i]-1;
        if(a[i] < 0) {// 找最小
            ans = max(ans, (query_min(l2, r2, 0, n, 1) - query_max(l1, r1, 0, n, 1)) * a[i]);
        }
        else {
            ans = max(ans, (query_max(l2, r2, 0, n, 1) - query_min(l1, r2, 0, n, 1)) * a[i]);
        }
    }
    printf("%lld
", ans);
    return 0;
}

【D】 triples I 构造

给定一个数 (n) ，用最少的3的倍数或运算成它，输出构成方案之一。

(n \% 3 == 0) ：直接输出即可

(n \% 3 == 1) ：

(n) 的二进制位有至少两个 (\% 3=1) 的，设为 (p) 和 (q)，取 ([a-p,a-q])即可
二进制位只有一个 (\% 3=1) 的，那么设 (\% 3=1) 的这个位为p，(\% 3=2) 的某个位为 (q)，取 ([a-p,p+q])即可
二进制位没有 (\% 3=1) 的，那么假设有三个 (\% 3 = 2)的位 (p、q、r)，取([a-p-q, p+q+r])即可

(n \% 3 == 2) ：和 1 的情况相同，把 1 和 2 互换即可

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

const int maxn = 100+5;

int a[maxn];
ll m1[maxn], m2[maxn];

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        ll n;
        scanf("%lld", &n);
        if(n % 3 == 0) {
            printf("1 %lld
", n);
            continue;
        }
        ll temp = n;
        int cnt = 0;
        while(temp) {
            a[++cnt] = temp % 2;
            temp /= 2;
        }
        ll x = 1;
        int cnt1 = 0;
        int cnt2 = 0;
        for(int i = 1; i <= cnt; i++) {
            if(a[i]) {
                if(x % 3 == 1) {
                    m1[++cnt1] = x; //mod 3 == 1
                }
                else if(x % 3 == 2) {
                    m2[++cnt2] = x; //mod 3 == 2
                }
            }
            x = x*2;
        }
        if(n % 3 == 1) {
            if(cnt1 >= 2) {
                printf("2 %lld %lld
", n - m1[1], n - m1[2]);
            }
            else if(cnt1 == 1) {
                printf("2 %lld %lld
", n - m1[1], m1[1] + m2[1]);
            }
            else if(cnt2 >= 3) {
                printf("2 %lld %lld
", m2[1] + m2[2] + m2[3], n - m2[1] - m2[2]);
            }
        }
        else if(n % 3 == 2) {
            if(cnt2 >= 2) {
                printf("2 %lld %lld
", n - m2[1], n - m2[2]);
            }
            else if(cnt2 == 1) {
                printf("2 %lld %lld
", n - m2[1], m1[1] + m2[1]);
            }
            else if(cnt1 >= 3) {
                printf("2 %lld %lld
", m1[1] + m1[2] + m1[3], n - m1[1] - m1[2]);
            }
        }
    }
    return 0;
}

【J】 free 最短路dij变形

给定一个 (n) 个点 (m) 条边的无向图，起点 (S) 和终点 (T) 固定，每条边都有 (cost)，现在可以选择其中 (k) 条边的 (cost) 变成 0，问从起点到终点的最小 (cost)。

只要把最短路算法 (dijkstra) 的 (dis) 数组变成二维，(dis[i][j]) 表示：到 (i) 点时候已经用了 (j) 条魔术边（(i leq n , j leq k)）。

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

const int maxn = 1e3+5;

int vis[maxn][maxn];
int head[maxn];
int dis[maxn][maxn];
int n, m, S, T, k;
int tot;
int ans;

struct EDGE {
    int to, nxt, w;
}edge[2*maxn];

struct node {
    int v, w, k;
    bool operator < (const node &h)const {
        return w > h.w;
    }
};

void addedge(int u, int v, int w) {
    edge[tot].to = v;
    edge[tot].w = w;
    edge[tot].nxt = head[u];
    head[u] = tot++;
}

void dij() {
    priority_queue<node> q;
    q.push(node{S, 0, 0});
    while(!q.empty()) {
        node u = q.top();
        q.pop();
        int _k = u.k;
        int _v = u.v;
        if(vis[_v][_k] == 1)
            continue;
        vis[_v][_k] = 1;
        for(int i = head[_v]; ~i; i = edge[i].nxt) {
            int v = edge[i].to;
            int w = edge[i].w;
            if(dis[_v][_k] + w < dis[v][_k]) {
                dis[v][_k] = dis[_v][_k] + w;
                if(vis[v][_k] == 0)
                    q.push(node{v, dis[v][_k], _k});
            }
            if(_k < k && dis[_v][_k] < dis[v][_k+1]) {
                dis[v][_k+1] = dis[_v][_k];
                if(vis[v][_k+1] == 0)
                    q.push(node{v, dis[v][_k+1], _k+1});
            }           
        }
    }
}

int main() {
    while(~scanf("%d%d%d%d%d", &n, &m, &S, &T, &k)) {
        tot = 0;
        ans = inf;
        memset(head, -1, sizeof(head));
        memset(vis, 0, sizeof(vis));
        memset(dis, inf, sizeof(dis));
        for(int i = 0; i <= 1000; i++) {
            dis[S][i] = 0;
        }
        for(int i = 1; i <= m; i++) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            addedge(u, v, w);
            addedge(v, u, w);
        }
        dij();
        for(int i = 0; i <= k; i++)
            ans = min(dis[T][i], ans);
        printf("%d
", ans);
    }
    return 0;
}

【K】 number 规律

给定一个由数字组成的字符串，求出是300倍数的子串个数。0，00都算，并考虑前导零的情况。

遍历一遍每次计算 (\%3)的值，如果本位和后一位都是 0，把之前统计的 (cnt[sum]) 的个数加上。

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

const int maxn = 1e5+5;

char s[maxn];
int cnt[3];

int main() {
    while(~scanf("%s", s)) {
        memset(cnt, 0, sizeof(cnt));
        cnt[0] = 1;
        int n = strlen(s);
        ll ans = 0;
        int sum = 0;
        for(int i = 0; i < n; i++) {
            if(s[i] == '0' && s[i+1] == '0') {
                ans = ans + cnt[sum];
            }
            if(s[i] == '0') {
                ans ++;
            }
            sum = (sum + s[i]-'0') % 3;
            cnt[sum]++;
        }
        printf("%lld
", ans);
    }
    return 0;
}