20250812测试

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

S+20250812测试

A. 炫彩染色

枚举两种情况，输出最小答案即可，
代码：

#include<bits/stdc++.h>
using namespace std;
string s;
int ans1,ans2;
int main(){
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(i%2==1&&s[i]=='1') ans1++;
        if(i%2==0&&s[i]=='0') ans1++;
    }
    for(int i=0;i<s.size();i++){
        if(i%2==1&&s[i]=='0') ans2++;
        if(i%2==0&&s[i]=='1') ans2++;
    }
    cout<<min(ans1,ans2);
    return 0;
}
C++

B. 寻找饼干

可以发现，
当一个“.”四面起码有两面是“#”时，
证明它在长方形内。
代码：

#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,m;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
char a[N][N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
        if(a[i][j]=='#') continue;
        int cnt=0;
        for(int k=0;k<4;k++){
            int x=i+dx[k],y=j+dy[k];
            if(x<1||x>n||y<1||y>m) continue;
            if(a[x][y]=='#') cnt++;
        }
        if(cnt>1){
            cout<<i<<" "<<j;
            return 0;
        }
    }
    return 0;
}
C++

C. 戴帽子

对于每种颜色肯定是一个公差为一，第一个元素为0的等差数列。
所以维护3个序列的结尾即可。
每个可以添加到结尾的序列，可能性加一，
最后答案乘上可能性即可。
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5,mod=1e9+7;
int n,ans=1,a[N],t[]={0,-1,-1,-1},fnl,cnt;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        cnt=0;
        for(int j=1;j<=3;j++) if(t[j]+1==a[i]) cnt++,fnl=j;
        (ans*=cnt)%=mod,t[fnl]++;
    }
    cout<<ans%mod;
    return 0;
}
C++

D. 极大递增子序列

根据性质暴搜即可，
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=55;
int n,ans;
int a[N];
void dfs(int id){
    int y=1,minn=INT_MAX;
    for(int i=id+1;i<=n;i++){
        if(a[i]<=a[id]||a[i]>minn) continue;
        minn=a[i],y=0;
        dfs(i);
    } 
    if(y) ans++;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    dfs(0);
    cout<<ans;
    return 0;
}
C++

E. 守卫树

设 $dp_{u,j,k}$ 表示点 $u$ 的子树中恰好有 $j$ 个符合题意的子节点的方案数量，
其中 $k\in[0,2]$，表示该节点被守护的状态：

  1. $k=0$ 时，表示该点有一名守卫
  2. $k=1$ 时，表示该点没有守卫，但是被儿子守护
  3. $k=2$ 时，表示该店没有守卫，也不被守护

综上，代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2005,mod=1e9+7;
int n;
int siz[N],dp[N][N][3],f[N][3];
vector<int> t[N];
void dfs(int u,int fa){
    dp[u][0][1]=dp[u][1][0]=siz[u]=1;
    for(int i=0;i<t[u].size();i++){
        int v=t[u][i];
        if(v==fa) continue;
        dfs(v,u);
        memset(f,0,sizeof f);
        for(int j=0;j<=siz[u];j++) for(int k=0;k<=siz[v];k++){
            (f[j+k][0]+=dp[u][j][0]*(dp[v][k][0]+dp[v][k][2])%mod)%=mod;
            (f[j+k+1][0]+=dp[u][j][0]*dp[v][k][1]%mod)%=mod;//覆盖v 
            (f[j+k][1]+=dp[u][j][1]*(dp[v][k][1]+dp[v][k][2])%mod)%=mod;
            (f[j+k+1][2]+=dp[u][j][1]*dp[v][k][0]%mod)%=mod;//覆盖u 
            (f[j+k][2]+=dp[u][j][2]*(dp[v][k][0]+dp[v][k][1]+dp[v][k][2])%mod)%=mod;
        }
        siz[u]+=siz[v];
        for(int j=0;j<=siz[u];j++){
            dp[u][j][0]=f[j][0];//选自己 
            dp[u][j][1]=f[j][1];//不选，未被覆盖 
            dp[u][j][2]=f[j][2];//不选，被覆盖 
        }
    }
}
signed main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        t[u].push_back(v);
        t[v].push_back(u);
    }
    dfs(1,0);
    for(int i=0;i<=n;i++) cout<<(dp[1][i][0]+dp[1][i][1]+dp[1][i][2])%mod<<endl;
    return 0;
}
C++

F. 计算

根号分治题。
首先将左右端点都单点离线处理，最后差分，按照端点升序排序，
当 $p<=100$ 时，直接预处理答案，
否则直接枚举每一个 $p·x+k$ 即可。
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
struct node{
    int end,p,k,id1,id2;
}q[N*2];
int n,m,mx;
int a[N],ans[2][N],mod[105][105],t[N];
bool cmp(node x,node y) {return x.end<y.end;}
void add(int x){
    for(int i=1;i<=100;i++) mod[i][x%i]++;
    t[x]++;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i],mx=max(mx,a[i]);
    for(int i=1;i<=m;i++){
        int l,r,p,k;
        cin>>l>>r>>p>>k;
        q[2*i-1]={l-1,p,k,0,i};
        q[2*i]={r,p,k,1,i};
    }
    sort(q+1,q+1+2*m,cmp);
    int idx=0;
    for(int i=1;i<=2*m;i++){
        int end=q[i].end,p=q[i].p,k=q[i].k,id1=q[i].id1,id2=q[i].id2;
        while(idx<=end) add(a[idx]),idx++;
        if(p<=100) ans[id1][id2]=mod[p][k];
        else for(int i=k;i<=mx;i+=p) ans[id1][id2]+=t[i];
    }
    for(int i=1;i<=m;i++) cout<<ans[1][i]-ans[0][i]<<endl;
    return 0;
}
C++

G. 旅行家

边双+缩点，
缩点后数上差分，
最后前缀和一边，权为正的点加上其边双的点权和，
代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
struct node{
    int v,id;
};
vector<node> g[N];
vector<int> t[N];
stack<int> s;
int n,m,q,ans;
int dfn[N],low[N],vis[N],idx,cnt;
int w1[N],w[N],sum[N];
int fa[N][25],d[N];

void tj(int u,int e){
    dfn[u]=low[u]=++idx;
    s.push(u);
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i].v,id=g[u][i].id;
        if(!dfn[v]){
            tj(v,id);
            low[u]=min(low[u],low[v]);
        }
        else if((id^1)!=e) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        cnt++;
        while(1){
            int y=s.top();s.pop();
            vis[y]=cnt;
            w[cnt]+=w1[y];
            if(y==u) break;
        }
    }
}
void dfs(int u,int f){
    fa[u][0]=f,d[u]=d[f]+1;
    for(int i=1;i<=20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=0;i<t[u].size();i++){
        int v=t[u][i];
        if(v==f) continue;
        dfs(v,u);
    }
}
int lca(int u,int v){
    if(d[u]<d[v]) swap(u,v);
    for(int i=20;i>=0;i--){
        if(d[fa[u][i]]>=d[v]){
            u=fa[u][i];
        }
    }
    if(u==v) return u;
    for(int i=20;i>=0;i--){
        if(fa[u][i]!=fa[v][i]){
            u=fa[u][i];
            v=fa[v][i];
        }
    }
    return fa[u][0];
}
void dfs2(int u){
    for(int i=0;i<t[u].size();i++){
        int v=t[u][i];
        if(v==fa[u][0]) continue;
        dfs2(v);
        sum[u]+=sum[v];
    }
    if(sum[u]) ans+=w[u];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>w1[i];
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back({v,i<<1});
        g[v].push_back({u,i<<1|1});
    }
    tj(1,-1);
    for(int u=1;u<=n;u++) for(int i=0;i<g[u].size();i++){
        int v=g[u][i].v;
        if(vis[u]!=vis[v]){
            t[vis[u]].push_back(vis[v]);
            t[vis[v]].push_back(vis[u]);
        }
    }
    for(int i=1;i<=cnt;i++){
        sort(t[i].begin(),t[i].end());
        t[i].erase(unique(t[i].begin(),t[i].end()),t[i].end());
    }
    dfs(1,0);
    cin>>q;
    while(q--){
        int x,y;
        cin>>x>>y;
        x=vis[x],y=vis[y];
        sum[x]++,sum[y]++,sum[lca(x,y)]--,sum[fa[lca(x,y)][0]]--;
    }
    dfs2(1);
    cout<<ans<<"\n";
    return 0;
}
C++