2024年ICPC贵州省赛题解

A.破解住宿信息

简单判断。输入字符串含空格，整行输入。

string s;
getline(cin,s);
int sum=0,x;
x=s.find("GZU");
while(x!=-1){
    sum++;
    x=s.find("GZU",x+1);
}
if(sum==0) cout<<"yezhulin";
else if(sum%2) cout<<"heshangpo";
else cout<<"qingrenpo";

B.小帅的车费

确实是分层图最短路模板题。

直接建立 ​层图，层与层间依次用打折后的边权相连。

跑一遍Dijkstra即可。

需要注意数组大小及数据大小。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> PII;
const int N = 4300010,M=1200010;
const ll INF = 1e18;
int n,m,k,s,t;
ll e[N],ne[N],w[N],h[M],p[11],idx;
ll dis[M];
bool vis[M];
priority_queue<PII,vector<PII>,greater<PII> > q;
void add(int a,int b,ll c){    //加边函数
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx++;
}
void dijkstra(int s){   //dijkstra模板
    fill(dis,dis+M,INF);
    dis[s] = 0;
    q.push({0,s});
    while(!q.empty()){
        int u = q.top().second;
        q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = h[u]; ~i;i = ne[i]){
            int v = e[i];
            if(dis[v] > dis[u]+w[i]){
                dis[v] = dis[u]+w[i];
                q.push({dis[v],v});
            }
        }
    }
}
int main(){
    int a,b;ll c;
    cin >> n >> m >> k;
    for(int i=1;i<=k;i++) cin>>p[i];
    cin>>s>>t;
    memset(h,-1,sizeof h);
    for(int i = 0;i < m;i++){
        cin>>a>> b>>c;
        add(a,b,c); //关键的建图，各层内部正常建边
        add(b,a,c);
        for(int j = 1;j <= k;j++){   //从0到k层建k+1张图
            add(j*n+a,j*n+b,c); //每层内部正常建图
            add(j*n+b,j*n+a,c);
            add((j-1)*n+a,j*n+b,(c*p[j])/100);  //各层之间从上到下建边花费为每次打折价格
            add((j-1)*n+b,j*n+a,(c*p[j])/100);
        }
    }
    for(int i = 0;i < k;i++)
        add(i*n+t,(i+1)*n+t,0); //为防止使用小于k次权力就到达终点，在每层的终点间建花费为0的边连起来
    dijkstra(s);    //从起点s出发
    if(dis[n*k+t]!=INF) cout << dis[n*k+t] <<"\n";  //到k层的终点为答案
    else cout<<"Impossible\n";
    return 0;
}

C.细胞的合并

题目数据为 ​，不会超时。

暴力枚举细胞是否相连，相连就并查集加入。

ll n,t;
vector<pair<ll,ll> > vt;
int fa[2010];
int find(int x){
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}
void join(int x1,int x2){fa[find(x1)]=find(x2);}
void solve(){
    vt.clear();
    cin>>n>>t;
    for(int i=0;i<n;i++){
        ll x,y;cin>>x>>y;
        vt.push_back({x,y});
        fa[i]=i;
    }
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            ll x1=vt[i].first,y1=vt[i].second,x2=vt[j].first,y2=vt[j].second;
            if(abs(x1-x2)+abs(y1-y2)<=2*t){
                join(i,j);
            }
        }
    }
    int ans=0;
    for(int i=0;i<n;i++) if(fa[i]==i) ans++;
    if(ans!=1) cout<<"NO\n";
    else cout<<"YES\n";
}

D.还在排队的人

双端队列的模拟。只要会 deque直接秒。不会可以使用数组模拟。

int n,x=1;cin>>n;
deque<int> dq;
while(n--){
    char a,b;cin>>a>>b;
    if(a=='A'&&b=='S') dq.push_front(x++);
    else if(a=='A'&&b=='E') dq.push_back(x++);
    else if(a=='D'&&b=='S'){
        int m;cin>>m;
        while(m--) dq.pop_front();
    }else{
        int m;cin>>m;
        while(m--) dq.pop_back();
    }
}
while(!dq.empty()){
    cout<<dq.front()<<" ";dq.pop_front();
}

E.打怪兽

根据题目我们可以知道几个重要条件：

• 直线分布，第 ​ 只怪兽在 ​ 处。

• 每次魔法只对编号大于等于 ​ 的怪兽生效，所以第 ​ 处怪兽所受伤害只能来源于前面及此处的位置。

• 魔法的溅射伤害为 ​ ，所以对于第 ​ 处怪兽，能造成伤害的位置范围为 ​。

• 伤害最大为 1e18，需要开longlong，而且不会爆ll，不用开int128。

所以首先我们可以写一个二分代码，二分 ​ 。

在 solve 函数中，计算此时 ​ 所需最少次数。

如果次数大于 k，l 增加；次数小于等于 k 的都可以，修改 r，最终答案为 r。

solve 函数如何快速判断。根据上述题意，运行到第 ​ 处时，判断之前对第 ​ 处造成的伤害，如果可以使此处怪兽血量小于 0，则继续判断 ​。若不能，则此处必须施展魔法，魔法次数直接往上取整。

对于第 ​ 处如何快速判断能够受到的伤害呢？双指针，也叫尺取法。维护一段数组，存放造成伤害的下标。若某造成伤害下标对第 ​ 处造成不了伤害（不在对 i 造成伤害下标范围内），也就对 ​造成不了伤害，左指针前移。

我使用预处理 ​ 数组存放 ​ 的平方，减少乘法使用，不知道能不能加快。使用pair 数组存放施展魔法的下标和次数。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k,a[100010];
ll f[100010];
pair<int,ll> b[100010];
bool check(ll x){
    if(x==0) return 1;
    queue<int> q;
    ll kk=0,y=sqrt(x);
    int r=0,l=0;
    for(int i=1;i<=n;i++){
        int tmpr=r;
        ll sum=0,z=0;
        for(int j=l;j<tmpr;j++){
            if(b[j].first+y>=i)
                sum+=(x-f[i-b[j].first])*b[j].second;
            else l++;
        }
        z=(max(a[i]-sum,0ll)+x-1)/x;
        kk+=z;
        if(z!=0) b[r++]={i,z};
    }
    return kk>k;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        f[i]=i*i;
    }
    ll l=0,r=1e18,ans;
    while(l<r){
        ll mid=(l+r)>>1;
        if(check(mid)) l=mid+1;
        else r=mid;
    }
    cout<<r<<"\n";
    return 0;
}

F.关灯

暴力枚举最大长度 len。

每次操作是使 ​ 内的数都减一，所以利用差分数组，在数组中 ​ 即可实现这个操作。

需要考虑为负数之后的影响，即 +P 取模。

还需要考虑数组范围，虽然 n 是5e3，但是差分数组不能开这么小。

接下来请看我的垃圾代码

#include<bits/stdc++.h>
using namespace std;
int n,p,ans;
int level[10010];
int a[10010];
int main(){
    cin>>n>>p;
    for(int i=0;i<n;i++) cin>>level[i];
    for(int i=n;i>=1;i--){
        int d=0,f=1;
        memset(a,0,sizeof(a));
        for(int j=0;j<=n-i;j++){
            d+=a[j];
            int x=(level[j]-d+p)%p;
            if(x!=0){
                a[j]+=x;d+=x;
                a[j+i]-=x;
            }
        }
        for(int j=n-i+1;j<n;j++){
            d+=a[j];
            if((level[j]-d+p)%p!=0){f=0;break;}
        }
        if(f){
            cout<<i<<"\n";
            return 0;
        }
    }
    return 0;
}

G.小帅的骰子

模拟两次投出来的结果。

然后判断满足条件的可能结果有多少种。

求最大公因数约分即可。

我看不懂这个编译器啊，关闭同步取消刷新缓冲区就29s？否则TLE？2e4次输入。

int x,y;
vector<int> v;
void init(){
    for(int i=1;i<7;i++)
        for(int j=1;j<7;j++)
            v.push_back(i+j);
    sort(v.begin(),v.end());
}
void solve(){
    cin>>x>>y;
    if(x>y||y<2||x>12){ cout<<"0\n";return ;}
    int fm=v.size();
    int fz=upper_bound(v.begin(),v.end(),y)-lower_bound(v.begin(),v.end(),x);
    int tmp=__gcd(fm,fz);
    cout<<fz/tmp<<"/"<<fm/tmp<<"\n";
}

H.粉刷匠小帅

线段树，me not can。

I.寻找宝藏数

数位DP。

先利用质数筛预处理出所有4位合数。

for(int i=1000;i<=9999;i++)
    if(!prime(i))
        b[i]=1;

设 ​ 表示最高位为 i ,次高位为 j ，第三位为 k 的 N 位宝藏数的个数。

依次枚举四位初始化 ​ 为对应4位合数个数。

//在筛出所有合数时顺手初始化DP数组
dp[4][i/1000][i/100%10][i/10%10]++;

之后继续依次从低到高枚举高四位数字 i,j,k,p, 则状态转移方程为：

​;

最后继续枚举高三位求和即可。

时间复杂度为​。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7,N=1010;
ll n,ans;
ll dp[N][10][10][10];
int b[10000];
bool prime(int x){
    for(int i=2;i*i<=x;i++)
        if(x%i==0) return 0;
    return 1;
}
void init(){
    for(int i=1000;i<=9999;i++){
        if(!prime(i)){
            b[i]=1;
            dp[4][i/1000][i/100%10][i/10%10]++;
        }
    }
}
int main(){
    cin>>n;
    init();
    for(int len=5;len<=n;len++){
        for(int i=1;i<=9;i++){
            for(int j=1;j<=9;j++){
                for(int k=0;k<=9;k++){
                    for(int p=0;p<=9;p++){
                        int x=i*1000+j*100+k*10+p;
                        if(b[x]){
                            dp[len][i][j][k]=(dp[len][i][j][k]+dp[len-1][j][k][p])%mod;
                        }
                    }
                }
            }
        }
    }
    for(int i=1;i<=9;i++){
        for(int j=0;j<=9;j++){
            for(int k=0;k<=9;k++){
                ans=(ans+dp[n][i][j][k])%mod;
            }
        }
    }
    cout<<ans;
    return 0;
}

J.数字游戏

设删掉一个数字及其生成的所有数字所需要的次数的奇偶性为 ​ ,则 ​。

​，若为奇数则Alice获胜，否则Bob获胜。

但因为x很大，不能直接dp（我都不知道如何dp）。我们可以打表观察到：​，

则当x>1时，​。

所以只需要统计数字1的个数的奇偶性即可。

使用异或来判断操作次数奇偶性，奇偶性又可以反应获胜者。

int n,sum=0;cin>>n;
while(n--){
    int x;cin>>x;
    if(x==1) sum++;
}
if(sum%2) cout<<"Alice\n";
else cout<<"Bob\n";

K.最好的好朋友活动

需要注意，题目中只说了 a 数组和 b 数组是整数，自然也有可能是负数。想要乘积最大，若 ​ 是负数，则在 b 数组中找一个最小的负数，负负得正则乘积最大；反之正数，自然在 b 数组中找一个最大的正数。

时间复杂度为 ​。

void solve(){
    ll mi=1e18,mx=-1e18,sum=0;
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int j=1;j<=m;j++){
        ll x;cin>>x;
        mi=min(mi,x);
        mx=max(mx,x);
    }
    for(int i=1;i<=n;i++){
        if(a[i]<0) sum+=a[i]*mi;
        else sum+=a[i]*mx;
    }
    if(sum>=s) cout<<"YES\n";
    else cout<<"NO\n";
    for(int i=1;i<=n;i++){
        if(a[i]<0) cout<<a[i]*mi<<" ";
        else cout<<a[i]*mx<<" ";
    }
    cout<<"\n";
}

L.GZU的建筑

字典树我都没学，更别说树上启发式合并（dsu on tree）。

后续更新。

M.递增的鸭鸭

此题题解及DP状态设计与官方题解不一致。

DP状态：前只鸭子的合法方案数​

输入，使用vector存储，数组或许更美观。

vector<ll> l(n+1),r(n+1),vt(2*n);
for(int i=1;i<=n;i++) cin>>l[i]>>r[i];

题目中 l 和 r 的取值范围较大，为1e9，使用离散化可以缩小到 1e3。

for(int i=1;i<=n;i++){// 离散化边界
    vt.push_back(l[i]);
    vt.push_back(r[i] + 1);
}
sort(vt.begin(), vt.end());
vt.erase(unique(vt.begin(), vt.end()),vt.end());
// 每只鸭子可用的段区间 [L[i], R[i]]
vector<int> L(n+1),R(n+1);
for(int i = 1; i <= n; i++){//离散化后对应的数字
    int Li = lower_bound(vt.begin(), vt.end(), l[i]) - vt.begin();
    int Ri = lower_bound(vt.begin(), vt.end(), r[i] + 1) - vt.begin() - 1;
    L[i] = Li; R[i] = Ri;
}

预处理逆元，用于后续排列组合计算。我只会小费马定理。

下面逆元数组转移公式的AI推导如下：

vector<ll> inv(n+2);
inv[1] = 1;
for(int i = 2; i <= n+1; i++)
    inv[i] = (MOD - (MOD/i) * inv[MOD % i] % MOD) % MOD;

定义dp数组和初始化

vector<ll> dp(n+1, 0), dpnext;
dp[0] = 1;

组合数学内容。假设这n个数的范围相等，都是[l,r]，那么方案数可以直接用隔板法求出，为C(n+r-l,n)。

DP状态转移如下：

for(int s = 0; s < m; s++){
    // 预计算该段上取 t 个值的组合数 f[t] = C(len[s] + t - 1, t)
    vector<ll> f(n+1, 0);
    f[0] = 1;
    if(n >= 1) f[1] = len[s] % MOD;
    for(int t = 2; t <= n; t++){
        ll mul = (len[s] + t - 1) % MOD;
        f[t] = f[t-1] * mul % MOD * inv[t] % MOD;
    }
    // dpnext 初始为 dp（不选取该段）
    dpnext = dp;
    // 尝试在该段上添加更多鸭子（末尾连续 t 只鸭子）
    for(int j = 0; j <= n; j++){
        if(dp[j] == 0) continue;
        if(j == n) continue;
        // 查看第 j+1 只鸭子是否允许落在该段
        if(!(L[j+1] <= s && s <= R[j+1])) continue;
        // 从 j+1 开始尝试连续放鸭子
        for(int t = 1; j + t <= n; t++){
            int duckPos = j + t;
            if(!(L[duckPos] <= s && s <= R[duckPos])) break;
            dpnext[j+t] = (dpnext[j+t] + dp[j] * f[t]) % MOD;
        }
    }
    dp.swap(dpnext);
}

完整代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
int main(){
    int n;cin>>n;
    vector<ll> l(n+1),r(n+1),vt;
    for(int i=1;i<=n;i++) cin>>l[i]>>r[i];
    vt.reserve(2*n);
    for(int i=1;i<=n;i++){
        vt.push_back(l[i]);
        vt.push_back(r[i] + 1);
    }
    sort(vt.begin(), vt.end());
    vt.erase(unique(vt.begin(), vt.end()), vt.end());
    int m = vt.size() - 1;
    vector<ll> len(m);
    for(int j = 0; j < m; j++)
        len[j] = vt[j+1] - vt[j];
    vector<int> L(n+1),R(n+1);
    for(int i = 1; i <= n; i++){
        int Li = lower_bound(vt.begin(), vt.end(), l[i]) - vt.begin();
        int Ri = lower_bound(vt.begin(), vt.end(), r[i] + 1) - vt.begin() - 1;
        L[i] = Li; R[i] = Ri;
    }
    vector<ll> inv(n+2);
    inv[1] = 1;
    for(int i = 2; i <= n+1; i++)
        inv[i] = (MOD - (MOD/i) * inv[MOD % i] % MOD) % MOD;
    vector<ll> dp(n+1, 0), dpnext;
    dp[0] = 1;
    for(int s = 0; s < m; s++){
        vector<ll> f(n+1, 0);
        f[0] = 1;
        if(n >= 1) f[1] = len[s] % MOD;
        for(int t = 2; t <= n; t++){
            ll mul = (len[s] + t - 1) % MOD;
            f[t] = f[t-1] * mul % MOD * inv[t] % MOD;
        }
        dpnext = dp;
        for(int j = 0; j <= n; j++){
            if(dp[j] == 0) continue;
            if(j == n) continue;
            if(!(L[j+1] <= s && s <= R[j+1])) continue;
            for(int t = 1; j + t <= n; t++){
                int duckPos = j + t;
                if(!(L[duckPos] <= s && s <= R[duckPos])) break;
                dpnext[j+t] = (dpnext[j+t] + dp[j] * f[t]) % MOD;
            }
        }
        dp.swap(dpnext);
    }
    cout << dp[n] % MOD << "\n";
    return 0;
}

N.乐乐爱购物

莫比乌斯反演。

让数学手过来！