Codeforces Rating 1900+ 题目练习¶

2025-04-20

早该多刷 1900 的题目的，虽然 1600 也没太做熟，重点是做。不会就早看题解。不过当前是先按人多的刷，不然会很吃力。

人多的可能比较板，更容易有成就感，可能也会比较有教育意义。而且数量也不会很多。

通过时间为倒序，上面的会是新写的，下面的是旧的。

CF600E *2300¶

2025-04-30

从这题决定看线段树合并的，现在懂得差不多了。

这题是给一棵树，每个节点会有一个颜色 \(c\) ，我们需要计算每个子树中的出现次数最多的颜色的和。

这个题我们可以用线段树去维护每种颜色出现的次数。

我们对树进行 dfs，那么每个节点只需要合并它的每个子结点的线段树，就可以知道这颗子树的信息。

push up¶

这里是看左边和右边，哪边出现的次数更多，来决定如何合并。这个还是比较显然的，这里要理解左右孩子实际上是左右的区间，是颜色的信息。比如 \([l, r]\) 之间的颜色出现的次数以及答案。

update¶

实际上这题这涉及到单点修改，如果这个点是空的，肯定给它分配一个，然后递归去改，这里改的就是说给这个值的数量去增加。改完记得 push up ，跟普通线段树一样的。

merge¶

merge 函数是用于合并线段树的，一般是把 \(b\) 给合并到 \(a\) 上，递归合并，若果有一个是空的，肯定分配非空的那个，到叶子节点时，就是进行一个单点的合并。

constexpr int N = int(1e5) + 5;
struct tree{
    int l, r, cnt;
    ll ans;
    tree(int v = 0){
        l = r = cnt = ans = v;
    }
};
tree tr[N * 50];
#define mi ((l + r) >> 1)
#define lson tr[p].l
#define rson tr[p].r
int cnt = 0, rt[N];

void push_up(int p)
{
    tr[p].cnt = max(tr[lson].cnt, tr[rson].cnt);
    if(tr[lson].cnt > tr[rson].cnt)
        tr[p].ans = tr[lson].ans;
    else if(tr[lson].cnt < tr[rson].cnt)
        tr[p].ans = tr[rson].ans;
    else
        tr[p].ans = tr[lson].ans + tr[rson].ans;
}
void update(int &now, int l, int r, int pos, int v)
{
    if(!now) now = ++cnt;
    if(l == r){
        // 到叶子节点了
        tr[now].cnt += v;
        tr[now].ans = l;
        return;
    }
    // 递归处理
    if(pos <= mi) update(tr[now].l, l, mi, pos, v);
    else update(tr[now].r, mi + 1, r, pos, v);
    push_up(now);
}
int merge(int a, int b, int l, int r)
{
    if(!a) return b;
    if(!b) return a;
    if(l == r){
        tr[a].cnt += tr[b].cnt;
        tr[a].ans = l;
        return a;
    }
    tr[a].l = merge(tr[a].l, tr[b].l, l, mi);
    tr[a].r = merge(tr[a].r, tr[b].r, mi + 1, r);
    push_up(a);
    return a;
}
void ChatGptDeepSeek() // Date: 2025-04-29
{                      // Time: 23:52:50 
    int n;
    cin >> n;
    cnt = n;
    vi c(n + 1);
    vl ans(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> c[i];
        rt[i] = i;
    }
    vector<vi> g(n + 1, vi());
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    auto dfs = [&](auto &&self, int u, int pre) -> void{
        for(auto v : g[u]){
            if(v == pre) continue;
            self(self, v, u);
            rt[u] = merge(rt[u], rt[v], 1, 100000);
        }
        update(rt[u], 1, 100000, c[u], 1);
        ans[u] = tr[rt[u]].ans;
    };
    dfs(dfs, 1, 0);
    for(int i = 1; i <= n; i++)
        cout << ans[i] << " \n"[i == n];
}

CF86D *2200¶

2025-04-25

莫队算法模板题，去学了一下发现学个模板还是很快的。

constexpr int N = int(1e6)+5;
int cnt[N];
struct node{
    int l, r, idx;
};
node Q[N];
void ChatGptDeepSeek() // Date: 2025-04-25
{                      // Time: 21:27:09 
    int n, q;
    cin >> n >> q;
    vi a(n + 1), pos(n + 1);
    vl ans(q + 1);
    int siz = sqrt(n);
    for(int i = 1; i <= n; i++)
        cin >> a[i], pos[i] = i / siz;
    // vector<node>Q(q);
    for(int i = 0; i < q; i++){
        cin >> Q[i].l >> Q[i].r;
        Q[i].idx = i;
    }
    sort(Q, Q + q, [&](node x, node y){
        return (pos[x.l] == pos[y.l]) ? (x.r < y.r) : (pos[x.l] < pos[y.l]);
    });
    // sort(all(Q), [&](node x, node y){
    //     return (pos[x.l] == pos[y.l]) ? (x.r < y.r) : (pos[x.l] < pos[y.l]);
    // });
    ll res = 0;
    auto add = [&](int i){
        res -= (ll)cnt[a[i]] * cnt[a[i]] * a[i];
        cnt[a[i]]++;
        res += (ll)cnt[a[i]] * cnt[a[i]] * a[i];
    };
    auto sub = [&](int i){
        res -= (ll)cnt[a[i]] * cnt[a[i]] * a[i];
        cnt[a[i]]--;
        res += (ll)cnt[a[i]] * cnt[a[i]] * a[i];
    };
    int L = 1, R = 0;
    for(int i = 0; i < q; i++){
        auto [l, r, idx] = Q[i];
        while(L > l) add(--L);
        while(R < r) add(++R);
        while(L < l) sub(L++);
        while(R > r) sub(R--);
        ans[idx] = res;
    }
    for(int i = 0; i < q; i++)
        cout << ans[i] << "\n";
}

CF5C *1900¶

2025-04-21

这题评分完全瞎搞吧，这题完全应该是 1300 吧。。虽然不妨碍我 WA 两次。我是正着找一遍逆着找一遍，其实也不需要。但简单题也没必要多看了。

void ChatGptDeepSeek() // Date: 2025-04-21
{                      // Time: 17:32:33 
    string s;
    cin>>s;
    int now=0,cnt=1,len=0,cur_len=0;
    for(auto x:s){
        cur_len++;
        if(x=='(') now++;
        else now--;
        if(now<0){
            now=0;
            cur_len=0;
        }else if(now==0){
            if(cur_len>len){
                cnt=1;
                len=cur_len;
            }else if(cur_len==len)
                cnt++;
        }
    }
    int ans_len=len,ans_cnt=cnt;
    now=0,cnt=1,len=0,cur_len=0;
    reverse(all(s));
    for(auto x:s){
        cur_len++;
        if(x=='(') now++;
        else now--;
        if(now>0){
            now=0;
            cur_len=0;
        }else if(now==0){
            if(cur_len>len){
                cnt=1;
                len=cur_len;
            }else if(cur_len==len)
                cnt++;
        }
    }
    if(len>ans_len) cout<<len<<" "<<cnt<<'\n';
    else if(len==ans_len&&cnt>ans_cnt) cout<<len<<" "<<cnt<<'\n';
    else cout<<ans_len<<" "<<ans_cnt<<'\n';
}

CF380C *2000¶

2025-04-20

给一个括号串，每次询问区间的最长的合法括号子序列。没想到这也能线段树做哇。记的是每个节点未匹配的左括号和右括号的数量，然后左子节点的左括号可以和右子节点的右括号匹配。

string s;
#define ls p<<1
#define rs p<<1|1
#define mi ((l+r)>>1)

constexpr int N = int(1e6)+5;
struct node{
    int l,r;
};
node tr[N<<2];

node merge(node x,node y){
    node res;
    res.l=x.l+y.l-min(x.l,y.r);
    res.r=x.r+y.r-min(x.l,y.r);
    return res;
}
void build(int p,int l,int r){
    if(l==r){
        if(s[l]=='(') tr[p]={1,0};
        else tr[p]={0,1};
        return;
    }
    build(ls,l,mi),build(rs,mi+1,r);
    tr[p]=merge(tr[ls],tr[rs]);
}
node query(int p,int l,int r,int lx,int rx)
{
    if(l>=lx&&r<=rx) return tr[p];
    node res{0,0};
    if(lx<=mi) res=merge(res,query(ls,l,mi,lx,rx));
    if(rx>mi) res=merge(res,query(rs,mi+1,r,lx,rx));
    return res;
}
void ChatGptDeepSeek() // Date: 2025-04-16
{                      // Time: 11:32:28 
    cin>>s;
    int n=sz(s);
    s=" "+s;
    build(1,1,n);
    int m; cin >> m;
    while(m--){
        int l,r; cin>>l>>r;
        node res=query(1,1,n,l,r);
        cout<<r-l+1-res.l-res.r<<'\n';
    }
}