10.16 一中模拟高中3

qdl66666666 · 2025-10-16 21:50:14 · 题解

T1

题意

给定 n 个数 a_{1},a_{2}...,a_{3}，定义不美观度为最大的相邻两数的和。从中去掉 m 个数，相对位置关系不变（一个数没了，两边的数会相邻），问使剩下的数的不美观度最小是多少？

注意力

注意到一个序列当前的不完美度一定是最大的相邻两数的和，我们对这其操作才会对它的不完美度造成影响，反之则不能。所以我们可以用大根堆堆存储相邻两个数的和以及位置等信息，每次取最大的处理。

去掉一个数后的相邻关系如何维护，用链表（连通块可以用并查集）！

小证

我们找出两个数后应该删掉哪个呢？
答案是删掉较大的那个，简单证明：

设 a,b,c,d(b<=c)，b+c 是最大的一对，若删掉 b，会减去 a+b 的贡献，计入 a+c，显然 a+c>a+b；反之，若删掉 c，会减去 c+d 的贡献，计入 b+d，因为 b+d<c+d，所以删去较大的至少不劣。

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int N = 5e5 + 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 tid,n,m,cnt;
struct node{
    int l,r; ll w; 
}z[N];
struct ty{
    int x,y,w;
};
bool vis[N];
priority_queue<pair<ll,pair<int,int> > > Q;
int main(){
    freopen("necklace.in","r",stdin);
    freopen("necklace.out","w",stdout);
    read(tid); read(n); read(m);
    for(int i=1;i<=n;i++){
        read(z[i].w); z[i].l = i - 1, z[i].r = i + 1;
    } 
    z[1].l = n; z[n].r = 1;
    for(int i=1;i<=n;i++){
        Q.push({z[i].w + z[z[i].r].w,{i,z[i].r}});
    }
    while(!Q.empty()){
        if(cnt >= (n - m)){
            while(!Q.empty()){
                int idx = Q.top().se.fi,rr = Q.top().se.se; 
                ll w = Q.top().fi;
                Q.pop(); 
//              cerr<< idx << " " << rr << ";\n";
                if(vis[idx]||vis[rr]) continue;
                cout << w;
                return 0;
            }
        }
        int idx = Q.top().se.fi,rr = Q.top().se.se;
//      cerr << Q.top().fi << "?\n";
        Q.pop();
//      cerr << "-->";
        if(vis[idx]||vis[rr]) continue;
        int rs = z[idx].r, ls = z[idx].l;
//      cerr << idx << " " <<  rs <<  " " <<  z[idx].w + z[rs].w << "?\n";
        if(z[idx].w < z[rs].w){
            vis[rs] = true;
            z[idx].r = z[rs].r; z[z[rs].r].l = idx;
//          cerr << idx << " " << z[rs].r << "oooo\n";
            Q.push({z[idx].w + z[z[idx].r].w,{idx,z[idx].r}});
        }
        else{
            vis[idx] = true;
            z[rs].l = ls, z[ls].r = rs;
//          cerr << ls << " " << rs << " " << z[ls].w + z[rs].w << "kkkkkk\n"; 
            Q.push({z[ls].w + z[rs].w,{ls,rs}});            
        }
        cnt++;
    } 
    return 0;
}

T2

题意

统计满足以下条件的二叉树的个数：

第 i 个节点的儿子数量在 [l_{i},r_{i}] 之间。
若第 i 个节点不为叶子，需要满足其儿子最大的节点编号大于 i。

注意节点选左右儿子是两种状况，答案对 1e9+7 取模。

注意不到

设 f(i,j,k) 表示选了 i 个点，形成了 j 棵树，有 k 个儿子节点待定的方案数。相当于我们先保留 k 个位置，后续会选择合适的儿子来填上，正着考虑以满足条件2。

转移

设好了状态，我们分类讨论第 i 个点的儿子数 l 进行转移：

若 l=0:

新开一棵树：f(i,j,k) -> f(i+1,j+1,k)
把这个点放在缺失的儿子上： f(i,j,k)\times k -> f(i+1,j,k-1)

若 l=1:

新开一颗树：f(i,j,k)\times 2 -> f(i+1,j+1,k)
补儿子：f(i,j,k)\times 2 -> f(i+1,j+1,k)

注意到这里要乘二，因为 i 的儿子可以有左右两种位置选择。

若 l=2:

新开一棵树：f(i,j,k) -> f(i+1,j+1,k)
补儿子： f(i,j,k)\times k -> f(i+1,j,k-1)
将一颗没有父亲的树挂在它的其中一个儿子的位置上，因为他有两个儿子，只要保证另外一个的编号大于自己即可，这棵树可以挂在两种位置，有 j 棵树选择：f(i,j,k)\times 2\times j -> f(i+1,j,k+1)
进行操作三后把以它为根的树挂在另一颗树上，可以挂在 k 棵树上，有 (j-1) 棵树选择挂在左右两个位置：
f(i,j,k)\times 2\times k\times (j-1) -> f(i+1,j,k+1)

所以这道题就做完了，相当于正着考虑，预留儿子的位置维护森林，分类讨论计算方案数。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 310; 
const int mod = 1e9 + 7;
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 tid,T;
ll f[N][N][N];
int n,l[N],r[N]; 
inline void add(ll &x,ll y){
    x += y; if(x > mod) x -= mod;
}
void solve(){
    read(n);
    for(int i=1;i<=n;i++){
        read(l[i]); read(r[i]);
    }
    for(int i=0;i<=n;i++)
    for(int j=0;j<=n;j++){
        for(int k=0;k<=n;k++){
            f[i][j][k] = 0;
        }
    }
    f[0][0][0] = 1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
//          if(j > i) continue;
            for(int k=0;k<=n;k++){
                if(!f[i-1][j][k]) continue;
                if(!l[i]){
                    add(f[i][j+1][k],f[i-1][j][k]);
                    if(k) add(f[i][j][k-1],f[i-1][j][k]*k%mod); 
                }
                if(l[i]<=1&&r[i]>=1){
                    add(f[i][j+1][k+1],2 * f[i-1][j][k]%mod);
                    add(f[i][j][k],2*f[i-1][j][k]*k%mod);
                } 
                if(r[i]==2){//编号大于关系
                    add(f[i][j+1][k+2],f[i-1][j][k]%mod);
                    add(f[i][j][k+1],f[i-1][j][k]*k%mod);
                    add(f[i][j][k+1],2*f[i-1][j][k]*j%mod);
                    if(j>1) add(f[i][j-1][k],f[i-1][j][k]*(j-1)%mod*2*k%mod);
                } 
            }
        }
    }
    cout << f[n][1][0] << "\n"; 
}
int main(){
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    read(tid); read(T);
    while(T--){
        solve();
    }
    return 0;
}

T3

题意

给定字符串 s,t，s 中第 i 个字符的美观度为 w_{i}，每次可以选择一种字符最左边或最右边的位置删除，问在能得到 t 的前提下，删去的字符的最小美观度和是多少？

sub7

字符串全是 a，那么我们就固定了选中间长为 m 的一段 a，用前缀和维护删去的数的和，取最小即可。

sub1,2,3,4,5,6

暴力 DP，设 f(i,j) 表示匹配到 s_{i}，t_{j} 的删去字符的最小美观度和。

若 s_{i+1}=t_{j+1}，f(i,j) -> f(i+1,j+1)
若 s_{i+1}!=t_{j+1}，如果 j < mp[s_{i+1}].fi 或 j+1 > mp[s_{i+1}].se，f(i,j) + w_{i+1} -> f(i+1,j)，换句话说，如果 j 这个位置处于 s_{i+1} 在 t 中第一次出现的位置和最后一次出现的位置中间，说明后面还要匹配 s_{i+1}，如果将此时的 s_{i+1} 删去，就只能根据题目要求将这个数前面或后面的相同字符删去，这样就不能匹配 t，所以不能删去。

复杂度 O(nm)。

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int SN = 4e3 + 10;
const int N = 5e5 + 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 tid,T;
int n,m;
string s,t;
ll w[N],ans;
pair<int,int> mp[30];
ll f[SN][SN],sum[N]; 
void solve7(){
    read(n); read(m);
    cin >> s >> t;
    for(int i=1;i<=n;i++){
        read(w[i]);
    }
    int l = 1, r = n,cnt = 0;
    ll res = 1e18;
    for(int i=1;i<=n;i++){
        sum[i] = sum[i - 1] + w[i];
    }
    for(int i=1;i<=n-m+1;i++){
        int j = i + m - 1; 
        res = min(res,sum[i-1] + sum[n] - sum[j]);
    }
    if(res == 1e18) cout << "-1\n"; 
    else cout << res << "\n";
}
void solve_dp(){
    while(T--){
        read(n); read(m);
        cin >> s >> t;
        s = "#" + s, t = "." + t;
        for(int i=0;i<27;i++){
            mp[i].fi = m + 1;
            mp[i].se = 0;
        }
        for(int i=1;i<=m;i++){
            if(mp[t[i]-'a'].fi == m + 1) mp[t[i]-'a'].fi = i;
            mp[t[i]-'a'].se = i;
        } 
        for(int i=1;i<=n;i++){
            read(w[i]);
        } 
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                f[i][j] = 1e18;
            }
        }
        f[0][0] = 0; 
        for (int i = 1; i <= n; i++) {
            int c = s[i] - 'a';
            if (0 < mp[c].fi || 1 > mp[c].se) {
                if (f[i - 1][0] != 1e18) {
                    f[i][0] = f[i - 1][0] + w[i];
                }
            }
        }
        for(int i=0;i<=n;i++){
            for(int j=0;j<=min(i,m);j++){
                if(s[i+1]==t[j+1]){
                    f[i+1][j+1] = min(f[i+1][j+1],f[i][j]);
                }
                if(j < mp[s[i+1]-'a'].fi || j + 1 > mp[s[i+1]-'a'].se)
                    f[i+1][j] = min(f[i+1][j],f[i][j] + w[i+1]);
            }
        } 
        if(f[n][m]==1e18) cout << "-1\n"; 
        else cout << f[n][m] << "\n";
    }
}
int main(){
    freopen("letter.in","r",stdin);
    freopen("letter.out","w",stdout);
    read(tid); read(T);
    if(tid==7){
        while(T--) solve7();
        return 0;
    }
    solve_dp();
    return 0;
}

T4

题意

给定 n\times m 的网格，每个格子上有个字符 U/D/R/L，表示在这个格子不能走向那个方向的格子。给定 q 次询问，问从 a,b 到 c,d 的所有路径上的点的个数。

sub1,2

注意到给的限制很难搞，但是形成了有向无向关系，想到了缩点成 DAG，一个缩点内部的点能互相到达。

从 a,b 跑缩出来的图，能到达的点打上标记；建反图，从 c,d 再跑一遍，如果说一个点能从起点跑到和从终点反向跑到，那他就是路径上的点。

遍历每个点建图，tarjan 缩点后在 DAG 上遍历。

复杂度 O(Q\times n\times m)。

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;
const int N = 3e3+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 dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int mp[N][N],id[N][N],idx;
unordered_map<int,unordered_map<int,bool> > p; 
int tid,n,m,q,cnt;
pair<int,int> E[N*N];
vector<int> e[N*N],ne[N*N];
inline void chk(int x,int y){
    for(int i=0;i<4;i++){
        if(i == mp[x][y]) continue;
        int xx = x + dx[i], yy = y + dy[i];
        if(xx < 1 || xx > n || yy < 1 || yy > m||p[id[x][y]][id[xx][yy]]||p[id[xx][yy]][id[x][y]]) continue; 
        e[id[x][y]].push_back(id[xx][yy]); 
        p[id[x][y]][id[xx][yy]] = true;
        if(abs(mp[xx][yy]-i)!=2){
            e[id[xx][yy]].push_back(id[x][y]);
            p[id[xx][yy]][id[x][y]] = true;
        }
        else{
            E[++cnt] = {id[x][y],id[xx][yy]};
        }
    }
}
int dfn[N*N],low[N*N],tim,stk[N*N],scc[N*N],tot,top,siz[N*N]; 
//vector<int> h[N*N];
void tarjan(int u){
//  cerr << "?";
    dfn[u] = low[u] = ++tim; stk[++top] = u;
    for(auto x : e[u]){
        if(!dfn[x]){
            tarjan(x);
            low[u] = min(low[u],low[x]); 
        }
        else if(!scc[x]) low[u] = min(low[u],dfn[x]);
    } 
    if(dfn[u] == low[u]){
        tot++;
        while(1){
            int v = stk[top--];
            scc[v] = tot;
            siz[tot]++;
//          h[tot].push_back(v);
            if(u == v) break;
        }
    }
}
bool vis[N*N],is[N*N];
void dfs1(int u){
    if(vis[u]) return;
    vis[u] = true;
    for(auto x : e[u]){
        dfs1(x);
    }   
}
void dfs2(int u){
    if(is[u]) return;  
    is[u] = true;
    for(auto x : ne[u]){
        dfs2(x);
    }
}
int main(){
    freopen("maze.in","r",stdin);
    freopen("maze.out","w",stdout);
    read(tid); read(n); read(m); read(q);
    char ch;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >> ch;
            id[i][j] = ++idx;
            if(ch=='U') mp[i][j] = 0;
            if(ch=='R') mp[i][j] = 1;
            if(ch=='D') mp[i][j] = 2;
            if(ch=='L') mp[i][j] = 3; 
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            chk(i,j);
        }
    }
    for(int i=1;i<=idx;i++){
        if(!dfn[i]) tarjan(i);
    }
//  cerr << "\n";
    for(int i=1;i<=idx;i++) e[i].clear();
    for(int i=1;i<=cnt;i++){
        int u = E[i].fi, v = E[i].se;
        if(scc[u]!=scc[v]){
//          cerr << u << " " << v  << "u->v\n";
//          cerr << scc[u] << " " << scc[v] <<"scc\n";
            e[scc[u]].push_back(scc[v]);
            ne[scc[v]].push_back(scc[u]);
        } 
    }
//  for(int i=1;i<=tot;i++){
//      cerr << i <<":";
//      for(auto x : h[i]){
//          cerr << x << " ";
//      }
//      cerr << "\n";
//  } 
//  cerr << "_____\n";
    int a,b,c,d;
    while(q--){
        read(a); read(b); read(c); read(d);
        dfs1(scc[id[a][b]]);
//      for(int i=1;i<=tot;i++){
//          cerr << vis[i] << " ";
//      } 
//      cerr << "dfs1\n";
        dfs2(scc[id[c][d]]);
        ll res = 0;
        for(int i=1;i<=tot;i++){
            if(vis[i] && is[i]) res+=siz[i];
//          cerr << is[i] << " ";
        }
//      cerr << "dfs2\n";
        if(vis[scc[id[c][d]]] && is[scc[id[c][d]]]) cout << res << "\n"; 
        else cout << "-1\n";
        for(int i=1;i<=tot;i++){
            vis[i] = is[i] = false;
        }
    }
    return 0;
}