2 篇博文含有标签「题解」

一些题解

查看所有标签

线下第二场题解

2025年2月23日 · 阅读需 8 分钟

孙更欣

2024-2025学年负责人，ICPC银牌

F

奖励题，输出 $N-1$ 。

没过的都拉出去突突了。

I

阅读题，

A contest date is too late for TOPC if it is not at least 35 days prior to Octobor 21, 2023. Please write a program to determine whether a tentative contest date is too late for TOPC.

L

签到题，比预期中的发现时间要早。如果 $m\times s\geq n$ 则输出 $1$ ，否则输出 $0$ 。

A

输出一个两边为 $1$ ，中间为 $0$ 的金字塔。

B

暴力即可

枚举 $k$ ，之后删去其倍数，遇到需要保留的就break掉。

G

排序，之后从小到大选三个数，以中间的数字为标准，修改两边的木棍，遍历一遍求最小值即可。

E

首先预处理出从那些位置开始的 s 的子串刚好可以匹配 t,之后用前缀和维护，注意查询的时候右端点改为 $r-t.size()+1$ 。

J

爆搜题，注意可能会爆int。

把士兵当作节点，士兵之间的关系当作边。

用dfs遍历图，如果发现一个士兵之前已经分配过营地，且当前给到的营地位置与上次不同则不满足，否则遍历下来没有矛盾的话就是可以满足。

K

三国杀题，（恶趣味）。

经典背包DP 模型， $dp_{i,j,k}$ 表示前 $i$ 张卡牌中，两组牌的点数差值为 $j$ （可以为负），共 $k$ 张牌选择翻倍。

状态转移方程如下：

$\begin{cases}dp_{i,j,k}=\max(dp_{i-1,j-t_i,k}+v_i)\\dp_{i,j,k}=\max(dp_{i-1,j+t_i,k}+v_i)\\ dp_{i,j,k}=\max(dp_{i-1,j+t_i\times2,k-1}+v_i)& k>0\\ dp_{i,j,k}=\max(dp_{i-1,j-t_i\times2,k-1}+v_i)& k>0\end{cases}$

代码

#include<bits/stdc++.h>
#define int long long
#define N 110
using namespace std;
int n,k,v[N],t[N],dp[2][4610][N];
signed main(){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&v[i],&t[i]);
    }
    for(int i=0;i<=4600;i++){
        for(int j=0;j<=k;j++){
            dp[1][i][j]=dp[0][i][j]=-1e18;
        }
    }
    dp[0][2300][0]=0;
    for(int i=1;i<=n;i++){
        for(int x=0;x<=k;x++){
            for(int j=0;j<=4600;j++){
                dp[i&1][j][x]=dp[i&1^1][j][x];
                if(j>=t[i]){
                    dp[i&1][j][x]=max(dp[i&1][j][x],dp[i&1^1][max(0ll,j-t[i])][x]+v[i]);
                }
                if(j+t[i]<=4600){
                    dp[i&1][j][x]=max(dp[i&1][j][x],dp[i&1^1][min(4600ll,j+t[i])][x]+v[i]);
                }
                if(x&&j>=2*t[i]){
                    dp[i&1][j][x]=max(dp[i&1][j][x],dp[i&1^1][max(0ll,j-t[i]*2)][x-1]+v[i]);
                }
                if(x&&j<=4600-t[i]*2){
                    dp[i&1][j][x]=max(dp[i&1][j][x],dp[i&1^1][min(4600ll,j+t[i]*2)][x-1]+v[i]);
                }
            }
        }
    }
    int ans=-1e18;
    for(int i=0;i<=k;i++){
        ans=max(ans,dp[n&1][2300][i]);
    }
    printf("%lld",ans);
    return 0;
}

C

我们考虑朴素的枚举做法，用一个链表暴力模拟，并判断当前的歌和上一首歌的风格的 GCD 是否为 1 即可，一直到一轮下来没有任意一首歌被删除为止。

但这样做的话很显然会超时，我们发现有些歌在上面暴力枚举的时候被重复计算了多次，但有些歌被重复计算多次，我们考虑如何将重复的计算优化掉。

我们不难发现，判断歌曲风格的关系是按一定顺序的，而且这个顺序与队列的 First in First out 的关系是相同的，我们考虑用一个队列进行维护，记录所有需要判断关系的歌曲的编号，这样在计算 GCD 时只需要计算队列中的，可以省去所有重复的计算。最后按队列模拟时删除的顺序输出即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n,T,sum,maxn;
bool v[100010];
struct node{
    int a;
    int l,r;
}a[100010];
struct nod{
    int x,y;
};
vector <int>ans;
signed main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i].a);
            v[i]=0;
        }
        ans.clear();
        queue<nod>q;
        for(int i=1;i<n;i++){
            q.push(nod{i,i+1});
            a[i].l=i-1;
            a[i].r=i+1;
        }
        a[1].l=n;
        a[n].l=n-1;
        a[n].r=1;
        q.push(nod{n,1});
        sum=0;
        while(!q.empty()){
            int x=q.front().x,y=q.front().y;
            q.pop();
            if(v[x]){
                continue;
            }
            if(__gcd(a[x].a,a[y].a)==1){
                v[y]=1;
                int p=a[y].r;
                a[p].l=x,a[x].r=p;
                q.push(nod{x,p});
                ans.push_back(y);
            }
        }
        printf("%d ",(int)ans.size());
        for(int i=0;i<ans.size();i++){
            printf("%d ",ans[i]);
        }
        putchar('\n');
    }
    return 0;
}

H

没想到赛时被新生做出来了，膜拜orz。

根据题目中建图的性质，我们可以考虑对一个数转化成二进制的形式，并记录每一位的 $1$ 的个数，若在某一位上，有至少 $3$ 个点这一位为 $1$ ，那么这三个点之间都有一条边，也就是形成了一个三元环，根据数据范围，把所有数转化成二进制后最多有 $64$ 位，根据抽屉原理，当 $n> 128$ 时，一定存在一位，该位为 $1$ 的点的个数超过 $3$ ，对于其他的情况，因为 $n\le128$ ，我们直接用 floyd 判最小环即可。

注意， $a_i$ 可能存在为 $0$ 的情况，我们要排除所有为 $0$ 的点，用非 $0$ 的点的个数作为 $n$ 进行判断。

D

首先看到求最短路径的最大值，最小值最大，妥妥的二分答案。

根据题目中两个点之间连边的边权的性质，不难推断出最大值一定出现在相邻的两个点之间，不相邻的两个点之间可能存在更小的值，即使是有更大的值也不会成为边权。

两个点之间的最短路要么是两个点之间的边直达，要么是找一个最小的点，以最小的点作为中转站在两个点之间折跃，即点 $l$ 和点 $r$ 之间的最短路为 $\min( \min(1,n)\times2,\min(l,r))$ 。

在二分枚举答案时，假设当前枚举的答案为 $pos$ ，可以考虑设一个前缀和和一个后缀和，统计 $a_i\times2\le pos$ 的 $i$ 的数量，因为每个 $a_i\times2\le pos$ 的 $i$ 即是我们需要修改的点。

我们从 $1$ 到 $n-1$ 枚举，统计最小的 $pre_{i-1}+sub_{i+2}+ord(a_i<pos)+ord(a_{i+1}<pos)$ ，判断是否成立即可。

M

防AK题，看上去这道题有很多不同的做法，我讲一下我的随机化做法：异或哈希。

因为这里只需要考虑区间内的数字的出现情况，不需要考虑他们的先后顺序，所以我们可以用异或运算来计算他们的哈希值。

为了避免异或值重复的情况，我们用梅森旋转算法将 $1\sim n$ 赋成一个随机值，用一个数组 $base_i$ 记录前 $i$ 个数的异或和，这样一会在判断该序列是否为一个自排列的时候会方便很多。

我们考虑枚举所有 $1$ 的位置，分别向左和向右搜索能达到的最大值，用这个最大值当做序列的长度，设这个最大值为 $m$ ，并判断序列内的异或和是否与前 $m$ 个元素的异或和相等即可。

为了节省时间复杂度，我们考虑利用前缀和进行优化，用前缀和模拟向左搜索的过程，再将整个序列倒过来模拟向右搜索的过程即可。

线下第一场题解

2025年2月22日 · 阅读需 6 分钟

孙更欣

2024-2025学年负责人，ICPC银牌

这场的题目感觉出的还是很不错的，很多经典套路题和模板题的修改，感觉至少 A,B,D,E,H,I,L都是可做题，下面简单讲一下题目：

A

原题链接

内向型选手直接自己住一屋就好，不用考虑。

外向型选手必须住三人间，首先满足所有外向型选手，如果不是 3 的倍数就从综合型选手里补，这题就结束了。

B

原题链接

最大子段和模板，找出最大子段和并一直在最大子段和的末尾插入最大子段和，之后最大值翻倍，这样一直加 $k$ 次。

注意子数组可以为空。

L

原题链接

这道题可以考虑在原数据上变化，首先大于等于 $2$ 的数可以在原基础上任意变大或者减小，我们需要考虑其中为 $1$ 的值，因为 $1$ 只能增大不能减小。

用一个前缀和维护区间 $1$ 的个数，另一个前缀和维护区间内所有数的和。

每次判断所有数的和能不能令所有的 $1$ 增大即可。

I

原题链接

也是一道简单题，但赛时似乎一直没人发现。

将数组 $a_i$ 与 $b_i$ 排序，之后令 $a$ 的后 $x$ 项与 $b$ 的前 $x$ 项对比，再令 $a$ 的前 $n-x$ 项与 $b$ 的后 $n-x$ 项对比，判断是否满足条件即可。

E

原题链接

二分答案题。

通过二分枚举答案 $x$ 。

每次 dfs 遍历树，贪心，若当前子树的节点和已经大于 $x$ （去掉已经分离出去的子树），则将该子树分离出来。判断分离出来的子树的个数是否大于 $k$ 即可。

代码

#include<bits/stdc++.h>
#define N 200010
#define ls x<<1
#define rs x<<1|1
#define MID ((l+r)>>1)
#define mkp(a,b) make_pair(a,b)
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
//#define int long long
//#define P pair<int,int>
using namespace std;
vector<int>G[N];
int T=1,n,k,cnt;
int dfs(int x,int fa,int ans){
    int res=1;
    for(int to:G[x]){
        if(to==fa)continue;
        res+=dfs(to,x,ans);
    }
    if(res>=ans){
        cnt++;
        return 0;
    }
    return res;
}
bool check(int x){
    cnt=0;
    dfs(1,0,x);
    if(cnt>k){
        return true;
    }
    return false;
}
void solve(){
    int l=0,r=100001;
    int ans=0;
    while(l<=r){
        if(check(MID)){
            ans=MID;
            l=MID+1;
        }
        else{
            r=MID-1;
        }
    }
    printf("%d\n",ans);
}
signed main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)G[i].clear();
        for(int i=1;i<n;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        solve();
    }
    return 0;
}

D

原题链接

单调栈模板。

我们考虑当 $s_i>s_{i+1}$ 时，删掉 $s_i$ 会使字符串的字典序变小。

根据字典序的定义，我们每次删掉最左边的满足上述条件的 $i$ ，得到的下一个字符串的字典序是所有的可能的情况中最小的。

朴素做法是 $O(n^2)$ 的，所以我们用栈来模拟位置 $pos$ 所在的字符串的情况，遇到上述情况就将栈中最后一个字符串弹出即可。

代码

#include<bits/stdc++.h>
#define N 1000010
#define ls x<<1
#define rs x<<1|1
#define MID ((l+r)>>1)
#define mkp(a,b) make_pair(a,b)
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define int long long
//#define P pair<int,int>
using namespace std;
char s[N];
bool v[N];
vector<int> p[26];
int T=1,n,pos;
void init(){
for(int i=0;i<26;i++) p[i].clear();
memset(v,0,sizeof(v));
}
signed main(){
scanf("%lld",&T);
while(T--){
    scanf("%s",s+1);
    n=strlen(s+1);
    scanf("%lld",&pos);
    init();
    int round=0,siz=n;
    stack <int> st;
    for(int i=1;i<=n;i++){
        while(!st.empty()&&pos>siz&&st.top()>s[i]){
            st.pop();
            pos-=siz;
            // cout<<pos<<endl;
            siz--;
            round++;
        }
        st.push(s[i]);
    }
    while(pos>siz){
        pos-=siz;
        st.pop();
        siz--;
        round++;
    }
    while(st.size()>pos){
        st.pop();
    }
    putchar(st.top());
}
return 0;
}

H

原题链接

可以考虑倒过来处理查询。

倒过来之后把插入点改为将点的值修改为 $0$ 。

用树剖和线段树维护子树和即可。

F

一道 $\mathcal O(n^4)$ 的 DP。

考虑设置状态 $dp_{i,j,k}$ ，其中 $i$ 表示前 $i$ 个瓶子， $j$ 表示其中选择了 $j$ 个瓶子作为容器， $k$ 表示剩余瓶子的容量。状态转移方程如下：

$dp_{i,j+1,k+b_i-a_i}=\min{dp_{i-1,j,k}}$

$dp_{i,j,k-a_i}=\min{dp_{i-1,j,k-a_i}}$

代码

#include<bits/stdc++.h>
#define M 20000
#define N 200010
#define ls x<<1
#define rs x<<1|1
#define MID ((l+r)>>1)
#define mkp(a,b) make_pair(a,b)
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
//#define int long long
//#define P pair<int,int>
using namespace std;
int T=1,n,m;
vector<int>a,b;
int dp[2][110][M+10];
signed main(){
    // scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        a.resize(n+1);
        b.resize(n+1);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&b[i]);
            b[i]-=a[i];
        }
        for(int i=0;i<2;i++)for(int j=0;j<=n;j++)for(int k=0;k<=20000;k++) dp[i][j][k]=1e9;
        dp[0][0][10000]=0;
        for(int i=1;i<=n;i++){
            int x=i&1;
            for(int j=0;j<=n;j++){
                for(int k=0;k<=M;k++){
                    dp[x][j][k]=1e9;
                }
            }
            for(int j=0;j<=n;j++){
                for(int k=0;k<=M;k++){
                    if(k+b[i]<=M){
                        dp[x][j+1][k+b[i]]=min(dp[x][j+1][k+b[i]],dp[x^1][j][k]);
                    }
                    if(k-a[i]>=0){
                        dp[x][j][k-a[i]]=min(dp[x][j][k-a[i]],dp[x^1][j][k]+a[i]);
                    }
                }
            }
        }
        for(int i=1;i<=n;i++){
            int ans=1e9;
            for(int j=10000;j<=M;j++){
                ans=min(ans,dp[n&1][i][j]);
            }
            if(ans<1e9){
                printf("%d %d\n",i,ans);
                return 0;
            }
        }
    }
    return 0;
}

C

原题连接

24年成都站原题。

F​

I​

L​

A​

B​

G​

E​

J​

K​

C​

H​

D​

M​

A​

B​

L​

I​

E​

D​

H​

F​

C​

F

I

L

A

B

G

E

J

K

C

H

D

M

A

B

L

I

E

D

H

F

C