Wanafly挑战赛2 题解

A：

给你一个长度为n的序列，你每次可以将一个序列分割成两个连续的的子序列，
分割的代价为原序列的总和。
现在允许你在初始时将序列重新排列一次。
问分割成n个长度为1的序列的最大总代价是多少？

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 100010;
int n, sum, a[maxn];
 
int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]), sum += a[i];
    sort(a+1, a+n+1);
    LL ans = 0;
    for(int i=1; i<n; i++){
        ans += sum;
        sum -= a[i];
    }
    return 0*printf("%lld\n", ans);
}

精灵王国有N座美丽的城市，它们以一个环形排列在Bzeroth的大陆上。其中第i座城市到第i+1座城市花费的时间为d[i]。特别地，第N座城市到第1座城市花费的时间为d[N]。这些道路都是双向的。

另外，精灵们在数千年的时间里建造了M座传送门，第i座传送门连接了城市u[i]与城市v[i]，并且需要花费w[i]的时间通过（可能有两座传送门连接了同一对城市，也有可能一座传送门连接了相同的两座城市）。这些传送门都是双向的。

小S是精灵王国交通部部长，她的职责是为精灵女王设计每年的巡查路线。每次陛下会从某一个城市到达另一个城市，沿路调查每个城市的治理情况，她需要找出一条用时最短的路线。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
const int maxm = 110;
typedef long long LL;
LL n, m, q, cnt, a[maxn], sum[maxn], b[maxm], dis[maxm][maxm];
LL getAns(LL x, LL y){
    if(x>y) swap(x, y);
    return min(abs(sum[y]-sum[x]), abs(sum[x]+sum[n]-sum[y]));
}
LL getid(LL x){
    return lower_bound(b+1, b+cnt+1, x) - b;
}
struct node{
    LL u,v,w;
}g[maxm];
int main(){
    scanf("%lld %lld", &n,&m);
    for(LL i=1; i<=n; i++) scanf("%lld", &a[i]);
    for(LL i=n+1; i>1; i--) a[i] = a[i-1];
    a[1] = a[n+1];
    for(LL i=1; i<=n; i++) sum[i]=sum[i-1]+a[i];
    for(LL i=1; i<=m; i++){
        scanf("%lld %lld %lld", &g[i].u,&g[i].v,&g[i].w);
        if(g[i].u==g[i].v) continue;
        b[++cnt] = g[i].u;
        b[++cnt] = g[i].v;
    }
    sort(b+1, b+cnt+1);
    cnt = unique(b+1, b+cnt+1)-b-1;
    for(LL i=1; i<=cnt; i++)
        for(LL j=1; j<=cnt; j++)
            dis[i][j] = dis[j][i] = getAns(b[i], b[j]);
    for(LL i=1; i<=m; i++){
        LL x = getid(g[i].u), y = getid(g[i].v);
        dis[x][y] = dis[y][x] = min(dis[x][y], g[i].w);
    }
    //floyd
    for(LL k=1; k<=cnt; k++)
        for(LL i=1; i<=cnt; i++)
            for(LL j=1; j<=cnt; j++)
                if(dis[i][j]>dis[i][k]+dis[k][j])
                    dis[i][j]=dis[i][k]+dis[k][j];
    scanf("%lld", &q);
    while(q--){
        LL x,y;
        scanf("%lld %lld", &x,&y);
        LL ans = getAns(x,y);
        for(LL i=1; i<=cnt; i++)
            for(LL j=1; j<=cnt; j++)
                ans = min(ans, getAns(x,b[i])+dis[i][j]+getAns(b[j],y));
        printf("%lld\n", ans);
    }
    return 0;
}

给定一个n*m的矩阵，矩阵元素由X和O构成，请求出其中最大的由X构成的蝴蝶形状。
由X构成的蝴蝶形状的定义如下：
存在一个中心点，并且其往左上、左下、右上、右下四个方向扩展相同的长度（扩展的长度上都是X)，且左上顶点与左下顶点、右上顶点与右下顶点之间的格子全由X填充。我们不在意在蝴蝶形状内部是X还是O。
例如：
XOOOX
XXOXX
XOXOX
XXOXX
XOOOX
是一个X构成的蝴蝶形状。
X
也是。
而
XOOX
OXXO
OXXO
XOXX
不是（不存在中心点）。

#include <bits/stdc++.h>
using namespace std;
//j <= k <= min(dp[1][i][j],dp[2][i][j]) + j - 1
//Max{k} && min(dp[0][i][k],dp[1][i][k]) - k - 1 >= -j
const int inf = 0x3f3f3f3f;
const int maxn = 2010;
struct SegmentTree
{
    struct node
    {
        int l, r, mx;
    } Tree[maxn * 4];
    void pushup(int rt)
    {
        Tree[rt].mx = max(Tree[rt << 1].mx, Tree[rt << 1 | 1].mx);
    }
    void build(int l, int r, int rt)
    {
        Tree[rt].l = l, Tree[rt].r = r, Tree[rt].mx = -inf;
        if (l == r) return;
        int mid = (l + r) / 2;
        build(l, mid, rt * 2);
        build(mid + 1, r, rt * 2 + 1);
        pushup(rt);
    }
    void update(int pos, int val, int rt)
    {
        if (Tree[rt].l == Tree[rt].r)
        {
            Tree[rt].mx = val;
            return;
        }
        int mid = (Tree[rt].l + Tree[rt].r) / 2;
        if (pos <= mid) update(pos, val, rt * 2);
        else update(pos, val, rt * 2 + 1);
        pushup(rt);
    }
    int query(int L, int R, int v, int rt)
    {
        if(Tree[rt].l == Tree[rt].r) return Tree[rt].l;
        int ret=0;
        if(L<=Tree[rt].l&&Tree[rt].r<=R){
            if(Tree[rt*2+1].mx>=v) ret = query(L, R, v, rt*2+1);
            else if(Tree[rt*2].mx>=v) ret = query(L, R, v, rt*2);
            return ret;
        }
        int mid = (Tree[rt].l+Tree[rt].r)/2;
        if(mid<R&&Tree[rt*2+1].mx>=v) ret = query(L, R, v, rt*2+1);
        if(ret) return ret;
        if(L<=mid&&Tree[rt*2].mx>=v) ret = query(L, R, v, rt*2);
        return ret;
    }
}T1, T2;
char s[maxn][maxn];
int dp[3][maxn][maxn];
 
int main()
{
    int n, m;
    scanf("%d %d", &n,&m);
    for(int i=1; i<=n; i++){
        scanf("%s", s[i]+1);
    }
    for(int i=n; i>=1; i--){
        for(int j=1; j<=m; j++){
            if(s[i][j]!='X') continue;
            dp[0][i][j] = dp[0][i+1][j-1]+1;
            dp[1][i][j] = dp[1][i+1][j]+1;
            dp[2][i][j] = dp[2][i+1][j+1]+1;
        }
    }
    int ans=0;
    for(int i=1; i<=n; i++){
        T1.build(1, m, 1);
        T2.build(1, m, 1);
        for(int k=1; k<=m; k++){
            if(k&1) T1.update(k, min(dp[0][i][k],dp[1][i][k])-k-1,1);
            else T2.update(k, min(dp[0][i][k],dp[1][i][k])-k-1,1);
        }
        for(int j=1; j<=n; j++){
            if(s[i][j]!='X') continue;
            int pos=0, x = min(dp[1][i][j], dp[2][i][j]);
            if(x<=ans) continue;
            if(j&1) pos = T1.query(j, x+j-1, -j, 1);
            else pos = T2.query(j, x+j-1, -j, 1);
            if(pos) ans = max(ans, pos-j+1);
        }
    }
    printf("%d\n", ans);
    return 0;
}

D
给定一张n个点，m条边的带权有向无环图，同时给定起点S和终点T，一共有q个询问，每次询问删掉某个点和所有与它相连的边之后S到T的最短路，询问之间互相独立(即删除操作在询问结束之后会立即撤销)，如果删了那个点后不存在S到T的最短路，则输出-1。

这题的代码是别的AC代码，实现了题解的意思。

#include <bits/stdc++.h>
using namespace std;
#define ll rt<<1
#define rr rt<<1|1
#define lson l, mid, ll
#define rson mid+1, r, rr
#define PB push_back
 
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, int> pli;
const int N = 1e5 + 5;
const LL INF = 10000000000000000LL;
int n, m, s, t;
int x[N<<1], y[N<<1], z[N<<1], deg[N], f[N];
int id[N], tot;
LL dt[N], ds[N];
LL sum[N<<2], laz[N<<2];
queue<int> q;
vector<pii> edges[N];
inline void pushUp(int rt) {
  sum[rt] = min(sum[ll], sum[rr]);
}
inline void pushDown(int rt) {
  sum[ll] = min(sum[ll], laz[rt]); laz[ll] = min(laz[ll], laz[rt]);
  sum[rr] = min(sum[rr], laz[rt]); laz[rr] = min(laz[rr], laz[rt]);
  laz[rt] = INF;
}
 
void build(int l, int r, int rt) {
  sum[rt] = laz[rt] = INF;
  if (l == r) return ;
  int mid = l+r>>1;
  build(lson);
  build(rson);
  pushUp(rt);
}
 
void update(int L, int R, LL v, int l, int r, int rt) {
  if (L <= l && r <= R) {
    sum[rt] = min(sum[rt], v);
    laz[rt] = min(laz[rt], v);
    return ;
  }
  pushDown(rt);
  int mid = l+r>>1;
  if (L <= mid) update(L, R, v, lson);
  if (mid < R) update(L, R, v, rson);
  pushUp(rt);
}
LL query(int p, int l, int r, int rt) {
  if (l == r) return sum[rt];
  pushDown(rt);
  int mid = l+r>>1;
  if (p <= mid) return query(p, lson);
  else return query(p, rson);
}
int dfs(int u) {
  if (f[u] != -1) return f[u];
  if (u == t) {
    f[u] = 1;
    return 1;
  }
  f[u] = 0;
  for (pii edge: edges[u]) {
    if (dfs(edge.first) == 1) f[u] = 1;
  }
  return f[u];
}
int main() {
  while (~scanf("%d%d%d%d", &n, &m, &s, &t)) {
    for (int i = 1; i <= n; ++i) deg[i] = 0;
    for (int i = 1; i <= n; ++i) edges[i].clear();
    for (int i = 1; i <= n; ++i) f[i] = -1;
    for (int i = 1; i <= n; ++i) ds[i] = INF;
    for (int i = 1; i <= n; ++i) dt[i] = INF;
    for (int i = 1; i <= m; ++i) {
      scanf("%d%d%d", x+i, y+i, z+i);
      edges[x[i]].PB(pii(y[i], z[i]));
    }
    dfs(s);
    for (int i = 1; i <= m; ++i) if (f[x[i]] == 1 && f[y[i]] == 1) {
      ++deg[y[i]];
    }
    while (!q.empty()) q.pop();
    ds[s] = 0;
    for (int i = 1; i <= n; ++i) if (!deg[i] && f[i] == 1) q.push(i);
    tot = 0;
    int u, v, w;
    while (!q.empty()) {
      u = q.front(); q.pop();
      id[u] = ++tot;
      for (pii edge: edges[u]) {
        v = edge.first; w = edge.second;
        if (f[v] != 1) continue;
        ds[v] = min(ds[v], ds[u]+w);
        if (--deg[v] == 0) q.push(v);
      }
    }
    dt[t] = 0;
    for (int i = 1; i <= n; ++i) deg[i] = 0;
    for (int i = 1; i <= n; ++i) edges[i].clear();
    for (int i = 1; i <= m; ++i) if (f[x[i]] == 1 && f[y[i]] == 1) {
      ++deg[x[i]];
      edges[y[i]].PB(pii(x[i], z[i]));
    }
    for (int i = 1; i <= n; ++i) if (!deg[i] && f[i] == 1) q.push(i);
    while (!q.empty()) {
      u = q.front(); q.pop();
      for (pii edge: edges[u]) {
        v = edge.first; w = edge.second;
        if (f[v] != 1) continue;
        dt[v] = min(dt[v], dt[u]+w);
        if (--deg[v] == 0) q.push(v);
      }
    }
    build(1, tot, 1);
    for (int i = 1; i <= m; ++i) if (f[x[i]] == 1 && f[y[i]] == 1) {
      if (id[x[i]]+1 > id[y[i]]-1) continue;
      update(id[x[i]]+1, id[y[i]]-1, ds[x[i]] + dt[y[i]] + z[i], 1, tot, 1);
    }
    scanf("%d", &m);
    while (m--) {
      scanf("%d", &u);
      if (ds[t] == INF) {
        printf("-1\n");
        continue;
      }
      if (f[u] != 1) {
        printf("%lld\n", ds[t]);
        continue;
      }
      LL ret = query(id[u], 1, tot, 1);
      if (ret >= INF) ret = -1;
      printf("%lld\n", ret);
    }
  }
}