总结

只打了 \(T1\)，想正解无果以致于没时间打暴力

\(\text{T1}\)

考虑到最后一个面基者要么落在点上，要么落在边上

所以可以枚举点和边，统计最久的落在此处的时间

落在边时考虑到有两个端点作为入口，需要一部分人在一端入，另一部分人从另一端入

这时贪心处理，按从某一端入需要的时间从小到大排序，前缀入这端，后缀入另一端

于是就是最短路预处理加统计，\(O(nk\log n+nk+mk\log k)\)

\(\text{Code}\)

$\text{Code}$

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#define IN inline
using namespace std;
typedef long long ll;

const int N = 1e5 + 5;
const ll INF = 1e12;
int n, m, K, h[N], tot;

struct Edge{int x, y, z;}E[N * 2];
struct edge{int to, nxt, w;}e[N * 4];
IN void add(int u, int v, int w){e[++tot] = edge{v, h[u], w}, h[u] = tot;}

IN void read(int &x) {
    x = 0; char ch = getchar(); int f = 1;
    for(; !isdigit(ch); f = (ch == '-' ? -1 : f), ch = getchar());
    for(; isdigit(ch); x = (x<<3)+(x<<1)+(ch^48), ch = getchar());
    x *= f;
}

struct node {
    int x; ll d;
    IN bool operator < (node c) const {return d > c.d;}
};
priority_queue <node> Q;
int vis[N], key[N];
ll f[23][N];

IN void dijsktra(int x) {
    memset(vis, 0, sizeof vis);
    for(int i = 1; i <= n; i++) f[x][i] = INF;
    Q.push(node{key[x], f[x][key[x]] = 0});
    while(!Q.empty()) {
        node now = Q.top(); Q.pop();
        if (vis[now.x]) continue;
        vis[now.x] = 1;
        for(int i = h[now.x]; i; i = e[i].nxt) {
            int v = e[i].to;
            if (f[x][v] > f[x][now.x] + e[i].w) {
                f[x][v] = f[x][now.x] + e[i].w;
                Q.push(node{v, f[x][v]});
            }
        }
    }
}

struct nod {ll x, y;}g[N];
IN bool cmp(nod a, nod b) {return a.x > b.x;}

IN ll calc(int id) {
    ll res = INF;
    for(int i = 1; i <= K; i++) g[i] = nod{f[i][E[id].x], f[i][E[id].y]};
    sort(g + 1, g + K + 1, cmp);
    ll Y = 0;
    for(int i = 1; i <= K; i++) {
        if (abs(g[i].x - Y) <= E[id].z) res = min(res, g[i].x + Y + E[id].z);
        Y = max(Y, g[i].y);
    }
    return res;
}

int main() {
    read(n), read(m);
    for(int i = 1, x, y, z; i <= m; i++)
        read(x), read(y), read(z), add(x, y, z), add(y, x, z), E[i] = Edge{x, y, z};
    read(K), ++K, key[1] = 1;
    for(int i = 2; i <= K; i++) read(key[i]);
    for(int i = 1; i <= K; i++) dijsktra(i);
    ll ans = INF;
    for(int i = 1; i <= n; i++) {
        ll d = 0;
        for(int j = 1; j <= K; j++) d = max(d, f[j][i]);
        ans = min(ans, d * 2);
    }
    for(int i = 1; i <= m; i++) ans = min(ans, calc(i));
    printf("%lld\n", ans);
} 

\(\text{T2,T3}\) 就不会了

\(T3\) 有点思路：贪心考虑，分治加主席树维护

考虑一个询问，从前往后两个两个选时，假设这两个都选，超过限制，扔掉选了的最小的

同理可以从后往前两个两个选，假设这两个都不选，超过限制，选没选的最大的

那么一个询问区间 \([l,r]\) 可以拼凑起来，假设分割点是 \(mid\)

用主席树维护维护 \([l,mid]\) 的每个后缀选了的数，\([mid+1,r]\) 的每个前缀没选的数

考虑拼起来时，前一段某些选了的数被后一段某些没选的数替换掉

数量相同，且前面最大的数小于后面最小的数

那么就可以二分替换数量，维护前一段的前 \(k\) 小和后一段的前 \(k\) 大

注意到分割拼凑可以分治，于是就是 \(O((n+q)log^2n)\) 的了

\(T1\) 烂掉了，\(T2\) 交互题做得太少，且本身也不会高点的暴力分

\(T3\) 看错题。。。看对了也只能拿十分

\(\text{T1}\)

我们只考虑集合中的数选还是不选

那么就是要找到两个不相交的子集，使得它们各自和相等

也等价于找到两个可相交的子集，使得它们各自和相等

因为可以不选，把两个子集相同的数去掉即可

又看到这个限制：\(p<2^n\) 其实是保证有解

子集和范围在 \([0,p-1]\)，和的数量又是 \(2^n\) 的

根据鸽巢原理，必然有解，使得两个子集和相等

考虑子集和为 \([l,r]\) 的数量 \(s_{l,r}\)

那么 \(s_{0,p-1}>p\)

若答案的子集和在区间 \([l,r]\) 内，那么 \(s_{l,r}>r-l+1\)

于是可以二分确定答案的子集和

那么如何计算 \(s_{l,r}\) 呢

考虑折半搜索，分成两个集合，全集的某子集和就是两个集合各自的一个元素加起来

不难想到分别排序后双指针统计

但和是模 \(p\) 意义下的，若要取模，这部分范围在 \([p,2p-2]\)，且仍具单调性

所以四个指针维护两个区间即可

\(\text{Code}\)

$\text{Code}$

#include <cstdio>
#include <algorithm>
#include <iostream>
#define IN inline
typedef long long LL;
using namespace std;

const int N = 45, M = 1e6 + 1e5;
int n, ans[N];
LL a[N], p;
int ct1, ct2;
struct node {LL v; int s;}g1[M], g2[M];
IN bool cmp(node a, node b) {return a.v < b.v;}

void dfs1(int x, LL v, int s) {
    if (x > n / 2) return g1[++ct1] = node{v, s}, void();
    dfs1(x + 1, (v + a[x]) % p, s | (1 << x - 1)), dfs1(x + 1, v, s);
}
void dfs2(int x, LL v, int s) {
    if (x > n) return g2[++ct2] = node{v, s}, void();
    dfs2(x + 1, (v + a[x]) % p, s | (1 << x - 1 - n / 2)), dfs2(x + 1, v, s);
}

int S[7];
IN void trans(int x, int m, int f) {
    for(int p = 1; x; x >>= 1, p++) if (x & 1) ans[p + m] += f;
}
IN void update(int i, int l, int r) {
    for(int j = l; S[0] < 4 && j < r; j++) S[++S[0]] = g1[i].s, S[++S[0]] = g2[j].s;
}
IN int check(LL L, LL R) {
    if (L > R) return 0;
    LL res = 0; S[0] = 0;
    for(int i = 1, l1 = 1, r1 = 1, r2 = 1, l2 = 1; i <= ct1; i++) {
        while (l1 <= ct2 && g1[i].v + g2[l1].v < L) ++l1;
        while (r1 <= ct2 && g1[i].v + g2[r1].v <= R) ++r1;
        while (l2 <= ct2 && g1[i].v + g2[l2].v < L + p) ++l2;
        while (r2 <= ct2 && g1[i].v + g2[r2].v <= R + p) ++r2;
        res += r1 - l1 + r2 - l2, update(i, l1, r1), update(i, l2, r2);
    }
    return res > R - L + 1;
}

int main() {
    scanf("%d%lld", &n, &p);
    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    dfs1(1, 0, 0), dfs2(n / 2 + 1, 0, 0), sort(g2 + 1, g2 + ct2 + 1, cmp);
    sort(g1 + 1, g1 + ct1 + 1, cmp), reverse(g1 + 1, g1 + ct1 + 1);
    LL l = 0, r = p - 1, mid = l + r >> 1;
    for(; l < r; mid = l + r >> 1) if (check(l, mid)) r = mid; else l = mid + 1;
    check(l, l), trans(S[1], 0, 1), trans(S[2], n / 2, 1), trans(S[3], 0, -1), trans(S[4], n / 2, -1);
    for(int i = 1; i <= n; i++) printf("%d ", ans[i]);
}