20250814测试

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

S+20250814测试

A. 交换序列

暴力枚举即可
代码：

#include<bits/stdc++.h>
using namespace std;
int n,y=1,ans;
int a[55];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        if(a[i]<=a[i-1]) y=0;
    }
    if(y){
        cout<<"YES";
        return 0;   
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j){
        swap(a[i],a[j]);
        int ye=1;
        for(int k=1;k<=n;k++) if(a[k]<=a[k-1]) ye=0;
        if(ye){
            cout<<"YES";
            return 0;
        }
        swap(a[i],a[j]);
    }
    cout<<"NO";
    return 0;
}
C++

B. 最小绝对值

解方程：
$$
\begin{align}
x^2+y^2-D&=0 \\
y&=\sqrt{D-x^2} \\
\end{align}
$$
因为精度问题需要将 $y$ 的上下界都计算一遍，
代码：

#include<bits/stdc++.h>
using namespace std;
long long d,ans=LONG_LONG_MAX;
int main(){
    cin>>d;
    for(long long x=0;x*x<=d;x++){
        long long y=sqrt(d-x*x);
        ans=min(min(ans,abs(d-x*x-y*y)),abs(d-x*x-(y+1)*(y+1)));
    }
    cout<<ans;
    return 0;
}
C++

C. 3色骨牌

染色问题，
一共有两种可能，两个横着的和一个竖着的。
动手模拟一下就可以，这里不赘述。
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int n,ans=1;
char a[3][55];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=2;i++) for(int j=1;j<=n;j++) cin>>a[i][j];
    for(int i=1;i<=n;i++){
        if(a[1][i]!=a[2][i]){
            if(i==1) (ans*=6)%=mod;
            else if(a[1][i-1]!=a[2][i-1]) (ans*=3)%=mod;
            else (ans*=2)%=mod;
            i++;
        }
        else{
            if(i==1) (ans*=3)%=mod;
            else if(a[1][i-1]!=a[2][i-1]) ans%=mod;
            else (ans*=2)%=mod;
        }
    }
    cout<<ans;
    return 0;
}
C++

D. 翻转行列

枚举每行每列最终反转了几个，
判断是否与条件所给的数模 $2$ 同余，
再用组合数计算一下答案即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e3+5,mod=555555555;
int c[N][N];
int h,w,r,c1,s,ans;
int check(int m,int n,int k){
    if(k%2!=n%2) return 0;
    return (c[m][k]%mod*c[(n-k)/2+m-1][m-1])%mod;
}
signed main(){
    cin>>h>>w>>r>>c1>>s;
    c[0][0]=1;
    for(int i=1;i<N;i++) for(int j=0;j<=i;j++){
        if(j==i||j==0) c[i][j]=1;
        else (c[i][j]=c[i-1][j]+c[i-1][j-1])%=mod;
    }
    for(int i=0;i<=r;i++) for(int j=0;j<=c1;j++){
        if(i*w+j*h-2*i*j==s)
            (ans+=check(h,r,i)*check(w,c1,j%mod))%=mod;
    }
    cout<<ans;
    return 0;
}
C++

E. 键帽

暴力的dp：
$$
\begin{align}
dp_{i,0}&=\sum_{j=max(0,i-k)}^{i-1}dp_{j,1}·5^{i-j} \\
dp_{i,1}&=(dp_{i-1,1}+dp_{i-1,1})·21 \\
\end{align}
$$
其中 $0$ 表示以元音结尾，$1$ 以辅音结尾。
发现第一个转移和哈希非常像，
可以用类似的思想优化，
代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int N=5e6+5;
int T;
int n,k,dp[N][2],p[N];
signed main(){
    p[0]=1;
    for(int i=1;i<N;i++) (p[i]=p[i-1]*5)%=mod;
    cin>>T;
    while(T--){
        int hsh=1;
        cin>>n>>k;
        dp[0][0]=dp[0][1]=1;
        for(int i=1;i<=n;i++){
            dp[i][1]=dp[i-1][0]*21%mod,(hsh=hsh*5+dp[i][1])%=mod;
            if(i>k) (hsh+=mod-dp[i-k-1][1]*p[k+1]%mod)%=mod;
            dp[i][0]=hsh;
        }
        cout<<dp[n][0]<<endl;
    }
    return 0;
}
C++

F. 偷金计划

计算出每个点与守卫的距离作为点权
那么新的边权可以看成两个端点的点权最小值，
然后计算最大生成树，做树上lca。
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5, K=20, INF=2e18;
int n,m,k,qs,x,y,dis[N],f[N][K+1],mm[N][K+1],dep[N],fa[N];
bool vis[N];
struct edge{int u,v,w;} p[N];
struct node{int id,val;};
vector<node> e[N],g[N];
priority_queue<node> q;
bool operator<(node a,node b){return a.val>b.val;}
bool operator<(edge a,edge b){return a.w>b.w;}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void dfs(int u,int fa){
    f[u][0]=fa, dep[u]=dep[fa]+1;
    for(auto v:g[u]) if(v.id!=fa){
        mm[v.id][0]=v.val, dfs(v.id,u);
    }
}
int lca(int x,int y){
    int res=INF;
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=K;i>=0;i--) if(dep[f[x][i]]>=dep[y])
        res=min(res,mm[x][i]),x=f[x][i];
    if(x==y) return res-1;
    for(int i=K;i>=0;i--) if(f[x][i]!=f[y][i]){
        res=min({res,mm[x][i],mm[y][i]});
        x=f[x][i],y=f[y][i];
    }
    return min({res,mm[x][0],mm[y][0]})-1;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>p[i].u>>p[i].v>>p[i].w;
        e[p[i].u].push_back({p[i].v,p[i].w});
        e[p[i].v].push_back({p[i].u,p[i].w});
    }
    cin>>k;
    for(int i=1;i<=n;i++) dis[i]=INF,fa[i]=i;
    while(k--) cin>>x,q.push({x,dis[x]=0});
    while(!q.empty()){
        auto u=q.top(); q.pop();
        if(vis[u.id]) continue;
        vis[u.id]=1;
        for(auto v:e[u.id]) if(dis[v.id]>dis[u.id]+v.val)
            q.push({v.id,dis[v.id]=dis[u.id]+v.val});
    }
    for(int i=1;i<=m;i++) p[i].w=min(dis[p[i].u],dis[p[i].v]);
    sort(p+1,p+m+1);
    for(int i=1;i<=m;i++){
        int fu=find(p[i].u),fv=find(p[i].v);
        if(fu==fv) continue;
        fa[fu]=fv;
        g[p[i].u].push_back({p[i].v,p[i].w});
        g[p[i].v].push_back({p[i].u,p[i].w});
    }
    dfs(1,0);
    for(int j=1;j<=K;j++) for(int i=1;i<=n;i++){
        f[i][j]=f[f[i][j-1]][j-1];
        mm[i][j]=min(mm[i][j-1],mm[f[i][j-1]][j-1]);
    }
    cin>>qs;
    while(qs--){
        cin>>x>>y;
        cout<<max(0ll,lca(x,y))<<'\n';
    }
    return 0;
}
C++