20250808测试

2025年8月8日 ooliver OI

S+20250808测试

A. 沙漠化

暴力BFS即可。

#include
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 q;
int main(){
    cin>>n;
    for(int i=1;i>a[i];
    m=a[1].size();
    for(int i=1;i>t;
    if(!ans){
        cout=n*m){
        coutn||ny=m) continue;
            if(a[nx][ny]=='F'){
                a[nx][ny]='D';
                ans++,q.push({nx,ny,id+1});
            }
        }
    }
    cout

`#include
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 q;
int main(){
    cin>>n;
    for(int i=1;i>a[i];
    m=a[1].size();
    for(int i=1;ifor(int j=0;j
        if(a[i][j]=='D') ans++,q.push({i,j,0});
    cin>>t;
    if(!ans){
        cout0;
        return 0;
    }
    if(t>=n*m){
        cout
        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;i4;i++){
            int nx=x+dx[i],ny=y+dy[i];
            if(nx1||nx>n||ny0||ny>=m) continue;
            if(a[nx][ny]=='F'){
                a[nx][ny]='D';
                ans++,q.push({nx,ny,id+1});
            }
        }
    }
    cout
    return 0;
}`

C++

B. 筒装球

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

#include
using namespace std;
int n,x,ans;
struct node{
    int a,sum;
};
stack 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

`#include
using namespace std;
int n,x,ans;
struct node{
    int a,sum;
};
stack 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
    }
    return 0;
}`

C++

C. 双循环锦标赛

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

#include
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;i2*(n-1)) return;
            }
            if((sum1==0||sum1==1&&sum3==0)&&(sum2==0||sum2==1&&sum4==0)){
                ans++;
            } 
        }
    }
    else{
        for(int i=0;i>n>>m;
    a[1]=m;
    dfs(1,m,m);
    cout

`#include
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
                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;imin(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
    return 0;
}`

C++

D. 奶牛求幂

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

#include
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>p;
    while(!dfs(1,0,0)) dep++;
    cout

`#include
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(aswap(a,b);
    if(now==dep) return a==p;
    if(a&&b) if(p%gcd(a,b)) return 0;
    if(areturn 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
    return 0;
}`

C++

E. 方格路径K大和

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

#include
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>mp[i][j];
    for(int x=1;x=mp[x][y])
                    for(int cnt=1;cnt

`#include
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;ifor(int j=1;j>mp[i][j];
    for(int x=1;xfor(int y=1;y
        memset(dp,0x3f,sizeof(dp));
        dp[1][0][0]=dp[0][1][0]=0;
        for(int i=1;i
            for(int j=1;j
                if(mp[i][j]>=mp[x][y])
                    for(int cnt=1;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
                        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
    return 0;
}`

C++

F. 树上字符串匹配

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

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

void get_next(){
    next1[0]=-1;
    int k=-1;
    for(int i=1;i-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-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>u>>s;
        t[i].push_back({u,s});
        t[u].push_back({i,s});
    }
    cin>>a;
    siza=a.size();
    if(siza==0){
        cout

`#include
using namespace std;
const int N=3e5+5;
struct node{
    int v;
    string w;
};
int n,ans,siza;
int next1[N];
string a;
vector t[N];

void get_next(){
    next1[0]=-1;
    int k=-1;
    for(int i=1;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;it[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;ks.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
        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){
        cout0;
        return 0;
    }
    get_next();
    dfs(1,-1,0);
    cout
    return 0;
}`

C++