这场前面几题感觉都不是很难。

A：很显然很大的时候都用最大的来塞就行了，对于较小的时候用背包计算下最优的方案。

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,int> pii;
const int N = 1e6 + 1;
const int M = 1e5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;

LL dp[N];
void init() {
    memset(dp,0x3f3f3f3f,sizeof(dp));
    dp[0] = 0;
    dp[1] = dp[2] = dp[3] = dp[4] = dp[5] = dp[6] = 15;
    dp[7] = 20,dp[8] = 20,dp[9] = 25,dp[10] = 25;
    for(int i = 11;i < N;++i) {
        dp[i] = min(dp[i],dp[i - 6] + 15);
        dp[i] = min(dp[i],dp[i - 8] + 20);
        dp[i] = min(dp[i],dp[i - 10] + 25);
    }
}
int main() {
    init();
    int ca;scanf("%d",&ca);
    int up = 1e6;
    LL ma = M * 25;
    while(ca--) {
        LL n;scanf("%lld",&n);
        if(n > up) {
            LL x = n / up;
            LL y = n - x * up;
            LL ans = ma * x + dp[y];
            printf("%lld\n",ans);
        }
        else printf("%lld\n",dp[n]);
    }



    //system("pause");
    return 0;
}

View Code

B：显然四个角落代表四种最优情况。

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,int> pii;
const int N = 1e6 + 1;
const int M = 1e5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;

int main() {
    int ca;scanf("%d",&ca);
    while(ca--) {
        int W,H;scanf("%d %d",&W,&H);
        int x1,y1,x2,y2;scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        int w,h;scanf("%d %d",&w,&h);
        int w1 = x2 - x1,h1 = y2 - y1;
        int lenw = w1 + w,lenh = h1 + h;
        if(lenw > W && lenh > H) printf("-1\n");
        else {
            int dis1 = 0;
            if(x1 < w) dis1 = w - x1;
            if(lenw > W) dis1 = INF;
            int dis2 = 0;
            if(x2 > W - w) dis2 = x2 - (W - w);
            if(lenw > W) dis2 = INF;
            int dis3 = 0;
            if(y1 < h) dis3 = h - y1;
            if(lenh > H) dis3 = INF;
            int dis4 = 0;
            if(y2 > H - h) dis4 = y2 - (H - h);
            if(lenh > H) dis4 = INF;
           // printf("d1 is %d d2 is %d d3 is %d d4 is %d\n",dis1,dis2,dis3,dis4);
            double ans = min(1.0 * dis1,1.0 * dis2);
            ans = min(ans,1.0 * dis3);
            ans = min(ans,1.0 * dis4);
            printf("%.8f\n",ans);
        }

    }

   // system("pause");
    return 0;
}

View Code

C：感觉比A都简单。

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,int> pii;
const int N = 1e5 + 1;
const int M = 1e5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e18
#define dbg(ax) cout << "now this num is " << ax << endl;

int a[5][N];
LL sum[5][N];
int main() {
    int ca;scanf("%d",&ca);
    while(ca--) {
        memset(sum,0,sizeof(sum));
        int m;scanf("%d",&m);     
        for(int i = 1;i <= 2;++i)
            for(int j = 1;j <= m;++j) scanf("%d",&a[i][j]),sum[i][j] = sum[i][j - 1] + a[i][j];
        LL ans = INF;
        for(int i = 1;i <= m;++i) {
            LL ma1 = sum[1][m] - sum[1][i];
            LL ma2 = sum[2][i - 1];
            ans = min(ans,max(ma1,ma2));
        }
        printf("%lld\n",ans);
    }

    //system("pause");
    return 0;
}

View Code

D：分析题意可以发现，满足条件的字符串只有abc三种交叉着来。

那么我们可以发现，如果开头的两个字符固定，那么后面的所有字符也就固定了。

也就是说字符串只有ab,ac,ba,bc,ca,cb六种开头的形式，前缀和一下，取最小的即可。

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,int> pii;
const int N = 2e5 + 5;
const int M = 1e5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;

int n,m;
string s;
LL pre[10][N];
char cal(char a,char b) {
    if(a == 'a' && b == 'b' || a == 'b' && b == 'a') return 'c';
    if(a == 'a' && b == 'c' || a == 'c' && b == 'a') return 'b';
    if(a == 'b' && b == 'c' || a == 'c' && b == 'b') return 'a';
}
void solve(int id,char a,char b) {
    char c1 = a,c2 = b;
    if(s[0] != a) pre[id][1] = 1;
    pre[id][2] = pre[id][1];
    if(s[1] != b) pre[id][2]++;
    for(int i = 3;i <= n;++i) {
        char now = cal(c1,c2);
        pre[id][i] = pre[id][i - 1];
        if(s[i - 1] != now) pre[id][i]++;
        c1 = c2,c2 = now;
    }
}
int main() {
    scanf("%d %d",&n,&m);
    cin >> s;
    solve(1,'a','b');
    solve(2,'a','c');
    solve(3,'b','a');
    solve(4,'b','c');
    solve(5,'c','a');
    solve(6,'c','b');
    while(m--) {
        int L,r;scanf("%d %d",&L,&r);
        if(L == r) printf("0\n");
        else if(r - L == 1) printf("%d\n",s[L - 1] == s[r - 1] ? 1 : 0);
        else {  
            LL ans = INF;
            for(int i = 1;i <= 6;++i) ans = min(ans,pre[i][r] - pre[i][L - 1]);
            printf("%lld\n",ans);
        }
    }

   // system("pause");
    return 0;
}
/*
5 10
aaaac
1 5

*/

View Code

E：这个题一开始的想法是在按线段左界排 ，在线段树上维护dp，但是如果用set维护答案，那么复杂度会过高。

正解：考虑尺取，这个真的很巧妙。

我们考虑维护一个下界对应的最小上界，所以我们将所有线段按权值来排序，然后尺取去加上线段，当满足覆盖到所有点之后。

说明我们维护的这段区间是以当前左界为下界的最小上界，这很显然。

对于所有点都被覆盖的情况，我们通过线段树去统计每个点被覆盖的次数，然后查询最小值即可，如果最小值 > 0，说明满足。

这里还有个细节就是，他这里其实是要线段覆盖，也就是说明每个点之间要有边连起来，那么我们就可以把每次维护的右端点看成是断开的。

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 3e5 + 5;
const int M = 1e6 + 5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;

int n,m;
struct PT{
    int L,r,w;
    bool operator < (const PT &a) const {
        return w < a.w;
    }
}p[N];
struct Node{int L,r,tag,micnt;}node[M << 2];
void Pushup(int idx) {
    node[idx].micnt = min(node[idx << 1].micnt,node[idx << 1 | 1].micnt);
}
void Pushdown(int idx) {
    if(node[idx].tag != 0) {
        node[idx << 1].micnt += node[idx].tag;
        node[idx << 1 | 1].micnt += node[idx].tag;
        node[idx << 1].tag += node[idx].tag;
        node[idx << 1 | 1].tag += node[idx].tag;
        node[idx].tag = 0;
    }
}
void build(int L,int r,int idx) {
    node[idx].L = L,node[idx].r = r,node[idx].micnt = node[idx].tag = 0;
    if(L == r) {
        return ;
    }
    int mid = (L + r) >> 1;
    build(L,mid,idx << 1);
    build(mid + 1,r,idx << 1 | 1);
    Pushup(idx);
}
void update(int L,int r,int idx,int val) {
    if(node[idx].L >= L && node[idx].r <= r) {
        node[idx].micnt += val;
        node[idx].tag += val;
        return ;
    }
    Pushdown(idx);
    int mid = (node[idx].L + node[idx].r) >> 1;
    if(mid >= L) update(L,r,idx << 1,val);
    if(mid < r) update(L,r,idx << 1 | 1,val);
    Pushup(idx);
}
int main() {
    scanf("%d %d",&n,&m);
    for(int i = 1;i <= n;++i) scanf("%d %d %d",&p[i].L,&p[i].r,&p[i].w);
    sort(p + 1,p + n + 1);
    int ans = INF;
    if(m == 1) printf("0\n");
    else {
        build(1,m - 1,1);
        int L = 1,r = 1;
        if(p[1].L != p[1].r) update(p[1].L,p[1].r - 1,1,1);
        while(L <= r && r <= n) {
            if(node[1].micnt > 0) {
                ans = min(ans,p[r].w - p[L].w);
                if(ans == 0) break;
                if(p[L].L != p[L].r) update(p[L].L,p[L].r - 1,1,-1);
                L++;
            }
            else {
                r++;
                if(p[r].L != p[r].r) update(p[r].L,p[r].r - 1,1,1);
            }
        }
        printf("%d\n",ans);
    }

    //system("pause");
    return 0;
}

View Code

F：这题很不错我觉得，而且解法好像有很多。

首先，我们考虑什么情况下可以加边。

如果该条边是两个不同连通块的边，那么很显然可以加入，这里用并查集判断即可。

这时我们可以发现一个很显然的结论，如果一条边能连通两个简单环，那么一定不能加入，因为另外两个简单环的异或和一定是权值一样的(因为都异或这条边 = 1)。

那么加入这条边后，两个简单环组成的大环异或和肯定 = 0。

也就是说对于一条边，它最多只能在一个简单环中。那么很显然是叫我们去维护一个仙人掌图。

我们考虑这个树形图。

对于这棵树，如果我们加入的这条边，连通的全部都是树边，那么就满足。如果连通的有非树边，那么就不满足。

我们可以考虑虚加入这条边，也就是计算上但是不真正加入到图中，那么我们维护的就会始终是一棵树。

所以我们需要支持一种操作，对所有非树边打上标记，且一次性查询一段树上的异或和。

对于一段树上异或和的查询，我们可以维护从树根开始的一个异或和。

那么对于树上任意两点的异或和  = dp[u] ^ dp[lca(u,v)] ^ (dp[v] ^ dp[lca(u,v)] = dp[u] ^ dp[v]。

可以发现我们甚至都不需要计算出lca就能实现维护。

对于非树边的打标记操作，有很多种做法，看很多大佬都用的LCT，但是本蒟蒻并不会。

我这里用了树剖来维护。

有很多细节需要注意：首先这里可能是很多的不同的树，所以需要不断增长下标来保证线段树的节点不会冲突.

id,rk这些数组也同理。

同时由于这里维护的是边的状态，那么我们可以用每个点来代表他与父节点连通的那条边的状态。

这样也会导致我们树剖跳链的时候会把lca代表的那条边算上，但实际上是不应该算上的。

这里我想到了两种处理方法，一种不直接跳到lca，而是最后倍增跳，第二种是我们再单独对lca进行一次处理。

我这里用了第二种做法，但是这里又可能出现前面被标记过然后再标记的情况，所以我们就需要去维护标记次数。

因为除了比较特殊的lca之外，其他点肯定只会被标记一次，所以我们对线段树上的叶子要做稍微不一样的处理。

最后再有亿点细节就解决了.

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 3e5 + 5;
const int M = 5e5 + 5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;

int n,q,fa[N],ans[M];
int ssize[N],son[N],top[N],id[N],rk[N],ffa[N],tim = 0,tot = 0,vis[N],rt[N],dep[N],dp[N],st[N],ed[N];
struct Edge{int to,dis;};
vector<Edge> G[N];
int Find(int x) {return x == fa[x] ? x : fa[x] = Find(fa[x]);}
struct PT{int u,v,x;}p[M];
void dfs1(int u,int fa) {
    ssize[u] = 1;
    vis[u] = tot;
    ffa[u] = fa;
    dep[u] = dep[fa] + 1;
    for(auto v : G[u]) {
        if(v.to == fa) continue;
        dp[v.to] = dp[u] ^ v.dis;
        dfs1(v.to,u);
        ssize[u] += ssize[v.to];
        if(ssize[v.to] > ssize[son[u]]) son[u] = v.to;
    }
}
void dfs2(int u,int fa,int sta) {
    id[u] = ++tim;
    rk[tim] = u;
    top[u] = sta;
    if(son[u] == 0) return ;
    dfs2(son[u],u,sta);
    for(auto v : G[u]) {
        if(v.to == fa || v.to == son[u]) continue;
        dfs2(v.to,u,v.to);
    }
}
int mx;
struct Node{int L,r,cnt,tag;}node[N << 2];
void Pushup(int idx) {
    node[idx].cnt = node[idx << 1].cnt + node[idx << 1 | 1].cnt;
}
void Pushdown(int idx) {
    if(node[idx].tag != 0) {
        if(node[idx << 1].L == node[idx << 1].r) node[idx << 1].cnt++;
        else node[idx << 1].cnt = node[idx << 1].r - node[idx << 1].L + 1;
        if(node[idx << 1 | 1].L == node[idx << 1 | 1].r) node[idx << 1 | 1].cnt++;
        else node[idx << 1 | 1].cnt = node[idx << 1 | 1].r - node[idx << 1 | 1].L + 1;
        node[idx << 1].tag = node[idx << 1 | 1].tag = 1;
        node[idx].tag = 0;
    }
}
void build(int L,int r,int idx) {
    mx = max(mx,idx);
    node[idx].L = L,node[idx].r = r,node[idx].cnt = node[idx].tag = 0;
    if(L == r) return ;
    int mid = (L + r) >> 1;
    build(L,mid,idx << 1);
    build(mid + 1,r,idx << 1 | 1);
    Pushup(idx);
}
void update(int L,int r,int idx) {
    if(node[idx].L >= L && node[idx].r <= r) {
        if(node[idx].L == node[idx].r) node[idx].cnt++;
        else node[idx].cnt = node[idx].r - node[idx].L + 1;
        node[idx].tag = 1;
        return ;
    }
    Pushdown(idx);
    int mid = (node[idx].L + node[idx].r) >> 1;
    if(mid >= L) update(L,r,idx << 1);
    if(mid < r) update(L,r,idx << 1 | 1);
    Pushup(idx);
}
void upd(int x,int idx) {
    if(node[idx].L == node[idx].r) {
        node[idx].cnt--;
        return ;
    }
    Pushdown(idx);
    int mid = (node[idx].L + node[idx].r) >> 1;
    if(mid >= x) upd(x,idx << 1);
    else upd(x,idx << 1 | 1);
    Pushup(idx);
}
int query(int L,int r,int idx) {
    if(node[idx].L >= L && node[idx].r <= r) return node[idx].cnt;
    int mid = (node[idx].r + node[idx].L) >> 1,ans = 0;
    Pushdown(idx);
    if(mid >= L) ans += query(L,r,idx << 1);
    if(mid < r) ans += query(L,r,idx << 1 | 1);
    return ans;
}
int qy(int x,int idx) {
    if(node[idx].L == node[idx].r) return node[idx].cnt;
    int mid = (node[idx].r + node[idx].L) >> 1;
    Pushdown(idx);
    if(mid >= x) return qy(x,idx << 1);
    else return qy(x,idx << 1 | 1);
}
pii Tree_query(int x,int y) {
    int ans = 0;
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x,y);
        ans += query(id[top[x]],id[x],rt[vis[x]]);
        x = ffa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x,y);
    ans += query(id[x],id[y],rt[vis[x]]);
    ans -= qy(id[x],rt[vis[x]]);
    return pii{ans,x};
}
void Tree_update(int x,int y) {
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x,y);
        update(id[top[x]],id[x],rt[vis[x]]);
        x = ffa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x,y);
    update(id[x],id[y],rt[vis[x]]);
    upd(id[x],rt[vis[x]]);
}
int main() {
    scanf("%d %d",&n,&q);
    for(int i = 1;i <= n;++i) fa[i] = i;
    for(int i = 1;i <= q;++i) {
        scanf("%d %d %d",&p[i].u,&p[i].v,&p[i].x);
        int xx = Find(p[i].u),yy = Find(p[i].v);
        if(xx != yy) {
            fa[xx] = yy;
            ans[i] = 1;
            G[p[i].u].push_back(Edge{p[i].v,p[i].x});
            G[p[i].v].push_back(Edge{p[i].u,p[i].x});
        }
    }
    for(int i = 1;i <= n;++i) {
        if(vis[i]) continue;
        st[++tot] = tim + 1;
        dfs1(i,0);
        dfs2(i,0,i);
        ed[tot] = tim;
        rt[tot] = mx + 1;
        mx = 0;
        build(st[tot],ed[tot],rt[tot]);
    }
    for(int i = 1;i <= q;++i) {
        if(ans[i] == 1) continue;
        pii ma = Tree_query(p[i].u,p[i].v);
        if(ma.first == 0 && (dp[p[i].u] ^ dp[p[i].v] ^ p[i].x) == 1) {
            ans[i] = 1;
            Tree_update(p[i].u,p[i].v);
        }
        //printf("u is %d v is %d ma.first is %d ans[%d] is %d\n",p[i].u,p[i].v,ma.first,i,ans[i]);
    }
    for(int i = 1;i <= q;++i) printf("%s\n",ans[i] ? "YES" : "NO");
    system("pause");
    return 0;
}

View Code