暑假第二十六测

我就是我 2021-09-29 11:08 253阅读 0赞

**今天又考的奇差**

![1121189-20180827174313933-964384567.png][]

![1121189-20180827174329577-816021378.png][]

![1121189-20180827174343524-226997117.png][]

题解：

第一题；

![1121189-20180827174448575-1438457369.png][]

这么简单一道题我想了好久，智商实在是下线了；

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    
    
    
    
    int main(){
        freopen("shortway.in","r",stdin);
        freopen("shortway.out","w",stdout);
        int n, k;
        scanf("%d%d", &n, &k);
        if((n - 1) % k == 0)printf("%d\n", (n - 1) / k * 2);
        if((n - 1) % k == 1)printf("%d\n", (n - 1) / k * 2 + 1);
        if((n - 1) % k >= 2)printf("%d\n", (n - 1) / k * 2 + 2);
    }

第二题：我们发现e的长度很小，我们可以在上面做文章，其实每个位置对应的%strlen(e)都是一样的；我们用树状数组维护rt\[pos\]\[len\]\[yu\]\[id\]表示1到POS每次跳len，当前位置%len = yu的id字符有多少个；对于一个字符串，查询就是rt\[R\]\[len\]\[(L + i - 1) % len\]\[a\[i\]\],修改就把长度枚举一下；

这道题我开始想到每次跳len, 维护一个前缀和，但没有想到树状数组，暴力修改和我直接暴力复杂度差不多；如果想到余数这一维就好了

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int M = 1e5 + 10;
    char s[M], ch[M];
    int rt[M][11][10][4], n, a[M], b[M];
    inline int get(char x){
        switch(x){
            case 'A':return 0;
            case 'T':return 1;
            case 'C':return 2;
            case 'G':return 3;
        }
    }
    inline int lowbit(int x){
         return x & (-x);}
    void add(int pos, int len, int yu, int id, int d){
        for(int x = pos; x <= n; x += lowbit(x)){
                rt[x][len][yu][id] += d;
        }
    }
    int query(int pos, int id, int k, int yu){
        int ret = 0;
        for(int x = pos; x; x -= lowbit(x)){
            ret += rt[x][k][yu][id];
        }
        return ret;
    }
    
    void init(){
        for(int i = 1; i <= n; i++)
            for(int k = 1; k <= 10; k++){
                add(i, k, i % k, a[i], +1);
        }
    }
    void add(int pos, int id, int d){
        for(int k = 1; k <= 10; k++)
            add(pos, k, pos % k, id, d);
    }
    int main(){
        freopen("evolution.in","r",stdin);
        freopen("evolution.out","w",stdout);
        scanf("%s", s);
        n = strlen(s);
        for(int i = 1; i <= n; i++)a[i] = get(s[i - 1]);
        init();
        int q, opt, l, r;
        scanf("%d", &q);
        while(q--){
            scanf("%d", &opt);
            if(opt == 1){
                scanf("%d%s", &l, ch);
                int t = get(ch[0]);
                add(l, a[l], -1);
                add(l, t, +1);
                a[l] = t;
            }
            else {
                scanf("%d%d%s", &l, &r, ch );
                int ans = 0, len = strlen(ch);
                
                for(int i = 1; i <= len; i++){
                    b[i] = get(ch[i - 1]);
                    ans += query(r, b[i], len, (l + i - 1) % len);
                    ans -= query(l - 1, b[i], len, (l + i - 1) % len);
                }
                printf("%d\n", ans);
            }
        }
    }

第三题：

![1121189-20180827175401221-574454951.png][]

线段树存树边，维护最大值更新非树遍，用非树边更新线段树上的限制；

#include<bits/stdc++.h>
    using namespace std;
    const int M = 2e5 + 10;
    const int oo = 0x3f3f3f3f;
    #define ex(i, u) for(int i = h[u]; i; i = G[i].nxt)
    #define Ls nd->ls, lf, mid
    #define Rs nd->rs, mid + 1, rg
    int fa[M], ans[M], n, m, h[M], top[M], siz[M], son[M], dep[M], in[M];
    int idc, tot, seq[M], line[M];
    bool intree[M], fg;
    struct edge{
        int u, v, w, id;}g[M];
    struct Edge{
        int nxt, v, id;}G[M << 1];
    void add(int u, int v, int i){
        G[++tot].v = v; G[tot].nxt = h[u]; h[u] = tot; G[tot].id = g[i].id;
    }
    bool cmp(edge a, edge b){
        return a.w < b.w;
    }
    bool cmp_id(edge a, edge b){
        return a.id < b.id;
    }
    int find(int x){
        if(x == fa[x])return x;
        return fa[x] = find(fa[x]);
    }
    void uni(int u, int v){
        fa[find(u)] = find(v);
    }
    struct Node;
    void modify(int L, int R, int d, Node * nd, int lf, int rg);
    struct Node{
        Node *ls, *rs;
        int mx, mi, tag;
        
      
        inline void down(int lf, int rg){
            if(tag != oo){
                int mid = (lf + rg) >> 1;
                modify(lf, mid, tag, ls, lf, mid);
                modify(mid + 1, rg, tag, rs, mid + 1, rg);
                tag = oo;
            }
        }
        
        inline void up(){
            mx = max(ls->mx, rs->mx);
        }
    }pool[M << 2], *tail = pool, *root;
    Node * build(int lf = 1, int rg = n){
        Node *nd = ++tail;
        if(lf == rg) {
            nd->mi = nd->tag = oo;
            nd->mx = g[line[seq[lf]]].w;
        }
        else {
            int mid = (lf + rg) >> 1;
            nd->ls = build(lf, mid);
            nd->rs = build(mid + 1, rg);
            nd->tag = nd->mi = oo;
            nd->up();
        }
        return nd;
    }
    
    int query(int L, int R, Node * nd = root, int lf = 1, int rg = n){
        if(L <= lf && rg <= R) return nd->mx;
        else {
            nd->down(lf, rg);
            int mid = (lf + rg) >> 1;
            int ans = 0;
            if(L <= mid)ans = max(ans, query(L, R, Ls));
            if(R > mid)ans = max(ans, query(L, R, Rs));
            return ans;
        }
        
    }
    void modify(int L, int R, int d, Node * nd = root, int lf = 1, int rg = n){
        if(L <= lf && rg <= R) {
            nd->tag = min(nd->tag, d);
            nd->mi = min(nd->mi, d);
            return ;
        }
        else {
            nd->down(lf, rg);
            int mid = (lf + rg) >> 1;
            if(L <= mid)modify(L, R, d, Ls);
            if(R > mid)modify(L, R, d, Rs);
            //nd->up();// ???
        }
    }
    
    
    void getdown(Node * nd = root, int lf = 1, int rg = n){
        if(lf == rg){
            ans[line[seq[lf]]] = nd->mi;
            return ;
        }
        nd->down(lf, rg);
        int mid = (lf + rg) >> 1;
        getdown(Ls);
        getdown(Rs);    
    }
    void dfs(int u, int f){
        dep[u] = dep[f] + 1;
        siz[u] = 1;
        fa[u] = f;
        
        ex(i, u){
            int v = G[i].v;
            if(v == f)continue;
            dfs(v, u);
            line[v] = G[i].id;
            siz[u] += siz[v];
            if(siz[v] > siz[son[u]])son[u] = v;
        }
    }
    void dfs2(int u, int tp){
        in[u] = ++idc;
        seq[idc] = u;    
        top[u] = tp;
        
        if(son[u])dfs2(son[u], tp);
        ex(i, u){
            int v = G[i].v;
            if(v == fa[u] || v == son[u])continue;
            dfs2(v, v);
        }
    }
    void Modify(int u, int v, int d){
        while(top[u] != top[v]){
            if(dep[top[u]] < dep[top[v]])swap(u, v);
            modify(in[top[u]], in[u], d);
            u = fa[top[u]];
        }
        if(dep[u] < dep[v])swap(u, v);
        if(in[u] != in[v])modify(in[v] + 1, in[u], d);
    }
    int Query(int u, int v){
        int ans = 0;
        while(top[u] != top[v]){
            if(dep[top[u]] < dep[top[v]])swap(u, v);
            ans = max(ans, query(in[top[u]], in[u]));
            //if(fg)printf("%d %d %d %d %d %d %d\n", u, v, dep[top[u]], dep[top[v]], in[top[u]], in[u], ans);
            u = fa[top[u]];
        }
        if(dep[u] < dep[v])swap(u, v);
        if(in[u] != in[v])ans = max(ans, query(in[v] + 1, in[u]));
        //if(fg)printf("%d %d %d\n", u, v, ans);
        return ans;
    }
    
    int main(){
        freopen("mst.in","r",stdin);
        freopen("mst.out","w",stdout);
        int u, v, w;
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= m; i++){
            scanf("%d%d%d", &u, &v, &w);
            g[i] = (edge){u, v, w, i};
        }
        sort(g + 1, g + 1 + m, cmp);
        for(int i = 1; i <= n; i++)fa[i] = i;
        for(int i = 1; i <= m; i++){
            int u = g[i].u, v = g[i].v;
            if(find(u) == find(v))continue;
            uni(u, v);
            intree[g[i].id] = 1;
            add(u, v, i); add(v, u, i);
        }
        line[1] = 0;
        dfs(1, 0); 
        dfs2(1, 1);
        //for(int i = 1; i <= n; i++)printf("%d %d %d\n", i, dep[i], top[i]);puts("");
        sort(g + 1, g + 1 + m, cmp_id);
        root = build();    
        
        for(int i = 1; i <= m; i++){
            if(intree[i])continue;
            int u = g[i].u, v = g[i].v;
            if(i == 473)fg = 1;
            int t = Query(u, v);
            ans[i] = t - 1;
            Modify(u, v, g[i].w - 1);
            fg = 0;
        }
        getdown();
        for(int i = 1; i <= m; i++)
            printf("%d ",ans[i] == oo ? -1 : ans[i]);
    }

转载于:https://www.cnblogs.com/EdSheeran/p/9543925.html

[1121189-20180827174313933-964384567.png]: /images/20210725/26dfcc339c4e4617bb4c71690c0cb8b1.png
[1121189-20180827174329577-816021378.png]: /images/20210725/384a718642024d9ca8c9445fdd557310.png
[1121189-20180827174343524-226997117.png]: /images/20210725/f69b9d89fce5497e9015a7dcc8c3f5b9.png
[1121189-20180827174448575-1438457369.png]: /images/20210725/7de43bc5b34b4e778d6801f313b78d57.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20210725/06bb77fd4fbd42df9964d3102ee9a1cb.png
[1121189-20180827175401221-574454951.png]: /images/20210725/35d494fa61e54dabbe0b51d2e07171a0.png