10.23 高中模拟3

qdl66666666 · 2025-10-23 09:18:00 · 题解

T1

题意

给定 m 个关系形如 p->q,r，表示在 [l,r] 中，如果[l,k] 满足 q，[k+1,r] 满足 r，则 [l,r] 满足 p。问 [1,n] 最后满足几种句法，特别的规定长度为一的序列 x 满足 x。

做法

不难发现大区间只会被小区间所影响，区间DP。转移和初始化题目已告诉，设 f(l,r,p) 表示 [l,r] 是否满足 p，枚举中断点 k，枚举 m 种句法匹配，时间复杂度 O(n^3m)。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 110;
const int M = 310;
template<typename TY>
inline void read(TY &s){
    ll x = 0,f = 1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    s = x * f;
}
int n,m;
int a[N];
struct node{
    int p,q,r; 
}z[M];
bool vis[N][N]; 
bool f[N][N][M];
//f[l][r][p] 表示 [l,r] 中是否满足语法 p
//时间复杂度 O(n^3m) 空间 O(n^2m) 
void dfs(int l,int r){
    if(vis[l][r]) return;
    vis[l][r] = true;
    for(int k=l;k<r;k++){
        dfs(l,k); dfs(k+1,r);
        for(int i=1;i<=m;i++){
            int ps = z[i].p , qs = z[i].q, rs = z[i].r;
            if(f[l][r][ps]) continue;
            if(f[l][k][qs] && f[k+1][r][rs]) f[l][r][ps] = true;
        }
    }
}
int main(){
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    read(m);
    for(int i=1;i<=m;i++){
        read(z[i].p); read(z[i].q); read(z[i].r);
    }
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
        f[i][i][a[i]] = true;
        vis[i][i] = true;
    }
    dfs(1,n);
    bool flag = false;
    for(int i=1;i<=m;i++){
        if(f[1][n][i]){
            flag = true;
            cout << i << " ";
        } 
    }
    if(!flag) cout << "-1";
    return 0;
}

T2

题意

树上第 k 大菊花？ 给定一颗无根树，要求菊花是以一个点为中心，出度至少为 3 的图，问树上前 k 大菊花权值绝对值的异或和。

思路

这是一道很好的关于选前 k 大的题，首先暴力求出每一朵菊花肯定是没有前途的。

先考虑一棵菊花的情况，设我们要求的菊花有 m 条出边，权值最大的菊花，一定是与它相连的节点按权值排完序后，选最前面的 m 个。那我们能不能快速求出前 k 大的来呢，兄弟可以的。

使用多指针+堆来干这件事，我们维护最后的指针 p_1 和倒数第二个指针 p_2，此时我们有两种选择：

1. 继续移动 p_1。
2. 将 p_1 固定看作边界，p2 变为 p_1 移动，p_3 变为 p_2。

将移动的不同情况和权值扔到堆里去维护，每次取最大的更新，这样我们就能保证选出前 k 个一定是前 k 大，且没有重复。

为什么呢？考虑画图证： 注意到每次更新的状态总是小于前驱状态。有人说万一 ade 大于 abf，但是 abf 先被处理怎么办？如果 ade>abf，因为 ade 小于它的前驱状态 ace，所以 ace>abf，所以 ace 一定比 abf 先处理，从而让 ade 也在堆中。

实现

所以我们开一个堆维护每种菊花，只需要记录一下 p_1，p_2 的位置，移动时更新权值。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e5 + 10;
template<typename TY>
inline void read(TY &s){
    ll x = 0,f = 1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    s = x * f;
}
int n,k;
ll ans,a[N]; 
vector<int> e[N];
struct node{
    int id,l,r,lst;
    ll sum;
};
bool operator<(const node &a,const node &b){
    return a.sum < b.sum;
}
bool cmp(const int &x,const int &y){
    return a[x] > a[y];
}
priority_queue<node> Q; 
int main(){
    freopen("b.in","r",stdin);
    freopen("b.out","w",stdout);
    read(n); read(k);
    for(int i=1;i<=n;i++){
        read(a[i]);
    }
    int u,v;
    for(int i=1;i<n;i++){
        read(u); read(v);
        e[u].push_back(v);
        e[v].push_back(u);
    } 
    for(int i=1;i<=n;i++){
        if(e[i].size() < 3) continue;
        sort(e[i].begin(),e[i].end(),cmp);
        ll res = a[i] + a[e[i][0]] + a[e[i][1]];
        for(int j=2;j<int(e[i].size());j++){
            res += a[e[i][j]];
            Q.push({i,j-1,j,int(e[i].size()),res});
        } 
    }
    while(k--){
        auto x = Q.top(); Q.pop();
        int id = x.id , l = x.l , r = x.r, lst = x.lst;
        ll sum = x.sum;
        ans ^= abs(sum);
        if(x.r + 1 < x.lst) Q.push({id,l,r+1,lst,sum - a[e[id][r]] + a[e[id][r+1]]});
        if(x.l >= 0 && x.l + 1 < x.r) Q.push({id,l-1,l+1,r,sum - a[e[id][l]] + a[e[id][l+1]]});
    }
    cout << ans;
    return 0;
}

T3

题意

给你一颗基环树，要求你将点集分别划分成 k=1-n 个集合。定义分歧边为：

• 边 (x,y) 上的符号是 +,但 p_x != p_y。
• 边 (x,y) 上的符号是 -,但 p_x = p_y。

其中 p_i 表示 i 所属的集合。
你需要通过适当的划分，最小化 k=1-n 的分歧边数量。

思路

首先可以倒着考虑，分连通块变为合并连通块。

我们发现最后的答案就是 + 号的数量。我们要最小化分歧边数量，就要先连 + 边，迫不得已连 - 边。

但这是一颗基环树，当连接了环上 s-1 条边时最后一条已经自动连通了，也就是说倒数第二条边连接时一定会有额外的代价：

• 如果最后一条边是 +，那么在合并倒数第二条边时代价额外减小 1；
• 如果最后一条边是 -，那么在合并倒数第二条边时代价额外增加 1。

根据贪心，+ 一定在 - 之前被选中合并其端点。因此第一种情况出现的唯一可能是整个环都是 +，这种情况下我们应当优先把环上的边的端点所在集合合并。 否则环上存在 -，一定对应第二种情况，这时：

• 如果环上仅有一条 - 边，那么倒数第二条边一定是 +，则合并倒数第二条边时代价变化是 +1-1=0，所以应当把倒数第二条边留着，先把挂着的数上的 + 合并完之后再合倒数第二条边，最后把树上的 - 边合并；
• 如果环上有多于一条 - 边，那么优先把环上及树上的 + 边端点合并，然后优先把挂着的树上的 - 边端点合并，最后再把环上的 - 边端点合并。

  实现

  我们按照如下顺序把边的端点合并到一个集合，就得到了各个 k 的最优解：

• 如果环上 - 边数量 \neq 1，则：环上的 + 边；树上的 + 边；树上的 - 边；环上的 - 边。
• 如果环上 - 边数量 =1，则：树上的 + 边；环上的 + 边；树上的 - 边。

并查集+dfs找环，如果一条边两端在已在同一连通块中，说明它是环上的边，这个环就是树上 s->t 和 (s,t)。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e5 + 10; 
template<typename TY>
inline void read(TY &s){
    ll x = 0,f = 1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    s = x * f;
}
int n;
vector<int> e[N];
int f[N];
int cnt,c0,c1,s,t;
int find(int x){
    if(f[x] != x) f[x] = find(f[x]);
    return f[x];
}
int a[N],cc,ans[N];
bool flag;
void dfs(int u,int fa,int l){
//  cerr << u <<"u\n";
    a[l] = u;
    if(u == t){
        flag = true;
        cc = l;
        return;
    }
    for(auto x : e[u]){
        if(x == fa) continue;
        dfs(x,u,l+1);
        if(flag) return;
    }
}
map<int,map<int,int> > mp;
int main(){
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);
    read(n);
    int u,v,w;
    char ch;
    for(int i=1;i<=n;i++){
        f[i] = i;
    } 
    for(int i=1;i<=n;i++){
        read(u); read(v); cin >> ch; 
        if(ch=='+') w = 1,c1++;
        else w = 0,c0++;
        e[u].push_back(v);
        e[v].push_back(u);
        mp[u][v] = mp[v][u] = w; 
        int fu = find(u), fv = find(v);
        if(fu == fv) s = u, t = v;
        else f[fv] = fu;
    }
//  cerr << s << " " << t << "st\n";
    dfs(s,0,1);
    if(mp[s][t]==0) cnt++;
    for(int i=1;i<cc;i++){
//      cerr << a[i] << " ";
        if(mp[a[i]][a[i+1]]==0) cnt++;
    }
    int res = c1;
    ans[n] = c1;
    if(cnt == 0){
        for(int i=n-1;i;i--){
            if(c1){
                c1--; res--; cc--;
                if(cc == 1) res--,c1--,cc--; 
            }
            else{
                c0--; res++; 
            }
            ans[i] = res;
        }
    }
    else if(cnt == 1){
        for(int i=n-1;i;i--){
            if(c1){
                c1--; res--;
                if(!c1) res++,c0--;
            }
            else c0--,res++;
            ans[i] = res;
        }
    }
    else{
        for(int i=n-1;i;i--){
            if(c1){
                c1--; res--;
            }
            else{
                c0--; res++;
                if(c0==1){
                    c0--; res++; 
                }
            }
            ans[i] = res; 
        }
    }
    for(int i=1;i<=n;i++){
        cout << ans[i] << "\n";
    }
    return 0;
}

T4

题意

给定无向完全图，定义权值

求

暴力