20250808测试

用户头像 发布于 2025-08-08 45 次阅读 OI

S+20250808测试

A. 沙漠化

暴力BFS即可。

#include<bits/stdc++.h>
using namespace std;
int n,m,t,ans;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
string a[15];
struct node{
    int x,y,id;
};
queue<node> q;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    m=a[1].size();
    for(int i=1;i<=n;i++) for(int j=0;j<m;j++)
        if(a[i][j]=='D') ans++,q.push({i,j,0});
    cin>>t;
    if(!ans){
        cout<<0;
        return 0;
    }
    if(t>=n*m){
        cout<<n*m;
        return 0;
    }
    while(q.size()){
        node now=q.front();
        q.pop();
        int x=now.x,y=now.y,id=now.id;
        if(id==t) continue;
        for(int i=0;i<4;i++){
            int nx=x+dx[i],ny=y+dy[i];
            if(nx<1||nx>n||ny<0||ny>=m) continue;
            if(a[nx][ny]=='F'){
                a[nx][ny]='D';
                ans++,q.push({nx,ny,id+1});
            }
        }
    }
    cout<<ans;
    return 0;
}
C++

B. 筒装球

相当于模拟一个包含分别为数字与数字个数两个元素的栈。

#include<bits/stdc++.h>
using namespace std;
int n,x,ans;
struct node{
    int a,sum;
};
stack<node> s;
int main(){
    cin>>n;
    s.push({0,0});
    while(n--){
        cin>>x;
        node now=s.top();
        if(now.a==x){
            s.pop();
            ans-=now.sum;
            if(now.sum+1!=x) s.push({x,now.sum+1}),ans+=now.sum+1;
        }
        else{
            s.push({x,1});
            ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}
C++

C. 双循环锦标赛

暴力DFS，在结尾判断序列是否合法。
判断方式：
用四个变量 $a,b,c,d$ 分别表示胜场为 $n(n-1)$，$n(n-1)-1$，$1$，$0$ 的数量，
若 $a>1$ 或 $d>1$，显然不对，因为全输和全胜只能存在一个。
若 $a=1$ 且 $b=1$ 显然也是不正确的，因为这是双循环赛制，如果有人全胜，不可能存在只输一场的人，对于全败也同理。
最后在循环的时候还要判断与没有出现胜场次数大于 $n(n-1)$ 的，这显然不符合。
所以代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=15;
int n,m,ans;
int a[N];
void dfs(int x,int y,int sum){
    if(x==n){
        if(sum==n*(n-1)){
            int sum1=0,sum2=0,sum3=0,sum4=0;
            for(int i=1;i<=n;i++){
                if(a[i]==0) sum1++;
                if(a[i]==2*(n-1)) sum2++;
                if(a[i]==1) sum3++;
                if(a[i]==2*(n-1)-1) sum4++;
                if(a[i]>2*(n-1)) return;
            }
            if((sum1==0||sum1==1&&sum3==0)&&(sum2==0||sum2==1&&sum4==0)){
                ans++;
            } 
        }
    }
    else{
        for(int i=0;i<=min(y,n*(n-1)-sum);i++){
            a[x+1]=i;
            dfs(x+1,i,sum+i);
        }
    }
}
int main(){
    cin>>n>>m;
    a[1]=m;
    dfs(1,m,m);
    cout<<ans;
    return 0;
}
C++

D. 奶牛求幂

根据题面很容易想到使用迭代加深搜索，
但显而易见是需要一点剪枝的。
可以发现，设当前两个存储器内存储的指数分别为 $a,b$，深度限制为 $dep$，当前深度为 $now$。
首先：无论操作几次，最终都只能得到 $na+mb$，又因为 $gcd(a,b)|na+mb$，所以当 $gcd(a,b)\nmid p$ 时可以直接退出；
其次：当目前最大的数乘上 $2^{dep-now}$ 还是小于 $p$ 时，也直接退出。
所以代码如下：

#include<bits/stdc++.h>
using namespace std;
int p,dep;
int gcd(int x,int y){
    if(!y) return x;
    else return gcd(y,x%y);
}
bool dfs(int a,int b,int now){
    if(a<b) swap(a,b);
    if(now==dep) return a==p;
    if(a&&b) if(p%gcd(a,b)) return 0;
    if(a<<(dep-now)<p) return 0;
    if(dfs(a+a,b,now+1)) return 1;
    if(dfs(a+a,a,now+1)) return 1;
    if(dfs(a,b+b,now+1)) return 1;
    if(dfs(b+b,b,now+1)) return 1;
    if(dfs(a+b,b,now+1)) return 1;
    if(dfs(b+a,a,now+1)) return 1;
    if(dfs(b,abs(a-b),now+1)) return 1;
    if(dfs(a,abs(a-b),now+1)) return 1;
    return 0;
}

int main(){
    cin>>p;
    while(!dfs(1,0,0)) dep++;
    cout<<dep;
    return 0;
}
C++

E. 方格路径K大和

可以先用 $n^2$ 的复杂度枚举一个点 $(i,j)$，
并以该点为参考，再以 $n^3$ 的复杂度进行dp，
设 $dp_{i,j,k}$ 表示走到点 $(i,j)$ 时选了 $k$ 个大于或等于参考点的最小权值和，
就可以很轻松地想到如下代码中的转移

#include<bits/stdc++.h>
using namespace std;
#define N 35
#define int long long
int n,m,k;
int mp[N][N],dp[N][N][2*N];
int ans=1e18;
signed main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>mp[i][j];
    for(int x=1;x<=n;x++) for(int y=1;y<=m;y++){
        memset(dp,0x3f,sizeof(dp));
        dp[1][0][0]=dp[0][1][0]=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(mp[i][j]>=mp[x][y])
                    for(int cnt=1;cnt<=k;cnt++)
                        dp[i][j][cnt]=min(dp[i][j][cnt],min(dp[i-1][j][cnt-1],dp[i][j-1][cnt-1])+mp[i][j]);
                if(mp[i][j]<=mp[x][y])
                    for(int cnt=0;cnt<=k;cnt++)
                        dp[i][j][cnt]=min(dp[i][j][cnt],min(dp[i-1][j][cnt],dp[i][j-1][cnt]));
            }
            ans=min(ans,dp[n][m][k]);
        }

    }
    cout<<ans;
    return 0;
}
C++

F. 树上字符串匹配

这题可以考虑kmp。
可以发现，建树时将边权改为字符串，
当dfs树的时候，只需保留小字符串的指针就可以。
所以如下代码比较板子：

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
struct node{
    int v;
    string w;
};
int n,ans,siza;
int next1[N];
string a;
vector<node> t[N];

void get_next(){
    next1[0]=-1;
    int k=-1;
    for(int i=1;i<siza;i++){
        while(k>-1&&a[k+1]!=a[i]) k=next1[k];
        if(a[k+1]==a[i]) k++;
        next1[i]=k;
    }
}

void dfs(int u,int idx,int fa){
    for(int i=0;i<t[u].size();i++){
        int v=t[u][i].v;
        string s=t[u][i].w;
        if(v==fa) continue;
        int j=idx;
        for(int k=0;k<s.size();k++){
            while(j>-1&&a[j+1]!=s[k]) j=next1[j];
            if(a[j+1]==s[k]) j++;
            if(j==siza-1){
                ans++;
                j=next1[j];
            }
        }
        dfs(v,j,u);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=2;i<=n;i++){
        int u;
        string s;
        cin>>u>>s;
        t[i].push_back({u,s});
        t[u].push_back({i,s});
    }
    cin>>a;
    siza=a.size();
    if(siza==0){
        cout<<0;
        return 0;
    }
    get_next();
    dfs(1,-1,0);
    cout<<ans;
    return 0;
}
C++