zzu2024 3月天梯赛选拔赛(A-F,I-K)

zzu2024 3月天梯赛选拔赛(A-F,I-K)

每题下面都写了abc上对应的原题

1,A

abc148f
思路就是求出A和T分别到树上某个点的最短路径长,只要T的路径小于A,T就不会被抓到,满足条件就更新A走过的路径长的最大值,注意最后答案要减1(自己想为什么)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+5;
vector<int>e[maxn];
int n,u,v;
int du[maxn],dv[maxn];
inline void dfs(int dis[],int x,int pr)
{
    for(auto i:e[x])
    {
        if(i==pr)continue;
        dis[i]=dis[x]+1;
        dfs(dis,i,x);
    }
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>u>>v;`
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(du,u,-1);
    dfs(dv,v,-1);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(du[i]<dv[i])//追不到
            ans=max(ans,dv[i]);//t先手,考虑r最优
    }
    cout<<ans-1;
    return 0;
}

2.B

abc148c
签到题,求个最小公倍数即可a*b/(gcd(a,b))

#include<bits/stdc++.h>
using namespace std;
#define int long long
int gcd(int a,int b)
{
    if(b==0)return a;
    return gcd(b,a%b);
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int a,b;
    cin>>a>>b;
    cout<<a*b/gcd(a,b);
    return 0;
}

3.C

abc149D
这题其实是模拟,很简单的,但是编码有点小技巧,不然你可能会写一堆屎山if,死都不知道怎么死的,思路就是前k轮不受影响,可以一直赢,后面如果要赢得出法与i-k轮的出法相同则不能赢,你可能会疑惑,如果我不能出石头,那我是出剪刀还是布呢,其实,
你可以在这里先打个?,然后往后看,把后面的出法定下后,你会发现,不管后面出什么,这个?总能找到一个合适的不违反规则的出法

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,k,r,s,p;
    cin>>n>>k>>r>>s>>p;
    string t;
    cin>>t;
    map<char,char>jie;//应该出什么
    jie['r']='p';jie['s']='r';jie['p']='s';
    map<char,int>fen;//出什么得多少分;
    fen['s']=s;fen['r']=r;fen['p']=p;
    string chu(n+5,0);
    int ans=0;
    for(int i=0;i<t.size();i++)
    {
        //小于k轮
        if(i<k)
        {
            chu[i]=jie[t[i]];
            ans+=fen[jie[t[i]]];
            //cout<<fen[t[i]]<<"\n";
        }
        //大于k轮
        else
        {
            if(jie[t[i]]==chu[i-k])
            chu[i]='?';
            else
            {
                chu[i]=jie[t[i]];
                ans+=fen[jie[t[i]]];
                //cout<<fen[t[i]]<<"\n";
            }
        }
    }
    cout<<ans;
    return 0;
}

4.D

abc147D
这个题最暴力的做法当然是n方枚举了,但明显会超时,涉及到位运算,所以不妨吧目光看到每一个二进制位,因为异或操作0和1答案才是1,所以其实只要1和0两两配对就行,不用管1和1与0和0

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,ans=0;
    cin>>n;
    vector<int>v(n+5);
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    for(int bit=0;bit<60;bit++)
    {
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            if(v[i]&(1ll<<bit))
            {
                cnt++;
            }
        }
         ans=(ans+(cnt)*(n-cnt)%mod*((1ll<<bit)%mod))%mod;        
        // int c=cnt*(n-cnt)%mod;
        // for(int i=0;i<bit;i++)
        // {
        //     c=c*2%mod;
        // }
        // ans=(ans+c)%mod;
    }
    cout<<ans;
    return 0;
}

5.E

abc149B
签到题,不多说

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int a,b,k;
    cin>>a>>b>>k;
    if(k<=a)
    {
        cout<<(a-k)<<" "<<b;
    }
    else if(k<=a+b)
    {
        cout<<0<<" "<<(a+b-k);
    }
    else 
    {
        cout<<0<<" "<<0;
    }
    return 0;
}

6.F

abc150C
这题范围很小,典型的回溯算法暴力求解,存下每种排列,再找给定的排列的下标,相减就行

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<int>>result;
vector<int>path;
int n;
bool vis[20];
void dfs(int x)
{
    if(path.size()==n)
    {
        result.push_back(path);
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(vis[i])continue;
        vis[i]=true;
        path.push_back(i);
        dfs(x+1);
        path.pop_back();
        vis[i]=false;
    }
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    int id1,id2;
    dfs(1);
    vector<int>a(n+5),b(n+5);
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int j=0;j<n;j++)
    {
        cin>>b[j];
    }
    for(int i=0;i<result.size();i++)
    {
        bool flag=1;
        for(int j=0;j<result[0].size();j++)
        {
            if(result[i][j]!=a[j])
            {
                flag=0;
                break;
            }
        }
        if(flag)
        {
            id1=i;
            break;
        }
    }
    for(int i=0;i<result.size();i++)
    {
        bool flag=1;
        for(int j=0;j<result[0].size();j++)
        {
            if(result[i][j]!=b[j])
            {
                flag=0;
                break;
            }
        }
        if(flag)
        {
            id2=i;
            break;
        }
    }
    cout<<abs(id1-id2);
    return 0;
}

7.I

abc148D
这题也好写吧,因为留下的数要跟下标一样,那肯定得从1开始,没有1直接寄

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    int flag=1;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        int t;
        cin>>t;
        if(t==flag)
        {
            flag++;
            cnt++;
        }
    }
    if(cnt==0)
    {
        cout<<-1;
    }
    else
    {
        cout<<(n-cnt);
    }
    return 0;
}

8.J

abc147E
这是个高维dp,dfs找每种路径肯定会超时(指数级别的)
定义dp[i][j][k]表示从(1,1)走到(i,j)和为k是否为真
初始化:因为dp[1][1][k]一定为真,所以dp[0][1][0]和dp[1][0][0]要初始化为1
递归公式在代码中看吧,挺好写的,而权值a[i]-b[i]可能为负,使下标为负,但其实肯定有一种对称的情况为正,所以求个绝对值就行

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[85][85],b[85][85];
bool dp[85][85][6405];//从(1,1)走到(i,j),和为k是否为真
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m;
    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++)
            cin>>b[i][j];

    dp[0][1][0]=dp[1][0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int d=a[i][j]-b[i][j];
            for(int k=0;k<=6400;k++)
            {
                if(k+d<=6400)dp[i][j][abs(k+d)]|=(dp[i-1][j][k]|dp[i][j-1][k]);
                if(k-d<=6400)dp[i][j][abs(k-d)]|=(dp[i-1][j][k]|dp[i][j-1][k]);
            }
        }
    }
    for(int k=0;k<=6400;k++)
    {
        if(dp[n][m][k])
        {
            cout<<k;
            break;
        }
    }
    return 0;
}

9.K

abc146E
这个题要转化一下,每个数字减1,题目就转化成有多少个子数组和对k取模等于0,那是不是找前缀和模k相等的位置就行了,还有一点就是一个数模k只能为0到k-1,所以元素的个数不能大于k,这里有两种做法,一种是把模数相等的下标存起来二分一下,另一种是弄一个长度为k的滑动窗口,明显滑动窗口更优,这里两种方法都贴一下
二分做法

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+5;
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,k;
    cin>>n>>k;
    vector<int>v(n+5),pre(n+5);
    map<int,vector<int>>mp;
    mp[0].push_back(0);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
        v[i]--;
        pre[i]=(pre[i-1]+v[i])%k;
        if(mp.find(pre[i])!=mp.end())
        {
            auto it=lower_bound(mp[pre[i]].begin(),mp[pre[i]].end(),i-k+1);
            ans+=mp[pre[i]].end()-it;
        }
        mp[pre[i]].push_back(i);
    }
    cout<<ans;
    return 0;
}

滑动窗口做法

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,k;
    cin>>n>>k;
    vector<int>v(n+5),pre(n+5,0);
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
        v[i]--;
        pre[i]=(pre[i-1]+v[i])%k;
    }
    map<int,int>mp;
    int ans=0;
    for(int i=0;i<=min(n,k-1);i++)//构造长度为k的窗口
    {
        ans+=mp[pre[i]];
        mp[pre[i]]++;
    }
    for(int i=k;i<=n;i++)
    {
        if(mp[pre[i-k]]==1)
        {
            mp.erase(pre[i-k]);
        }
        else mp[pre[i-k]]--;//左窗口右移
        ans+=mp[pre[i]];
        mp[pre[i]]++;//右窗口右移
    }
    cout<<ans;
    return 0;
}