挑战赛#14 官方题解

Yuilice

2025-01-28 16:29:22

发布于：浙江

100阅读

8回复

2点赞

~~因为篇幅较长，因此题解分为两个帖子发放。~~

突然发现上面三片其实也没那么长(bushi

题解正文

T1 雪块高度

解题思路

一共有 $999$ 个数字，从低到高分别为 $1,(1+2),(1+2+3),(1+2+3+4),...,(1+2+3...+999)$ 。给定两个数字 $a$ 和 $b$ ，为相邻两个数减去 $x$ 后的结果，求解 $x$ 。

由于给出的是相邻两个数，较小的数字 $x$ 为 $(1 + 2 + 3 +... + n-1)$ ,较大的数字 $y$ 为 $(1 + 2 + 3 +... + n-1 + n)$ ，他们的差值为 $n$ 。
我们可以得出，未被覆盖的部分的高度为 $1+2+3+...+n-answer$ ，故答案为 $(y - x) \times (y - x + 1) / 2 - y$ 。

参考代码

#include<bits/stdc++.h>
using namespace std;

int main() {
    int x,y;
    cin >> x >> y;
    int answer = (y - x) \times (y - x + 1) / 2 - y;
    cout << answer << endl;
    return 0;
}

T2 采矿场

解题思路

经过观察，可以发现 $N$ 的取值为 $10^5$ ，同时 $6$ 与 $9$ 的幂次结果会在某个阶段重合，因此我们可以先行枚举 $6$ 幂次的最大值，然后枚举 $9$ 幂次的最大值，剩余部分用1补足。

因为最后的答案一定为 $6^x$ + $9 ^ y$ + $z \times 1$ ，因此枚举其组合方式是可行的。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int min_sum = n;

    for (int i = 0; i <= n; i++) {
        int digit_sum = 0;
        int temp = i;
        while (temp > 0) {
            digit_sum += temp % 6;
            temp /= 6;
        }

        temp = n - i;
        while (temp > 0) {
            digit_sum += temp % 9;
            temp /= 9;
        }

        if (min_sum > digit_sum) {
            min_sum = digit_sum;
        }
    }

    cout << min_sum << endl;
    return 0;
}

T3 正除数

解题思路

一个整数 $x$ 可以通过质因数分解得到 $x=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ ，其中 $p_i$ 是质数， $a_i$ 是 $p_i$ 在 $x$ 中出现的次数。对于所有的质因数 $p_i$ ，求解 $N!$ 对于所有的质因数能够整除的次数即可。

参考代码

#include <iostream>
using namespace std;

bool isprime(int x) {
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

int cnt(int n, int p) {
    int res = 0;
    for (int f = p; f <= n; f *= p) {
        res += n / f;
    }
    return res;
}

int main() {

    int n;
    cin >> n;
    long long ans = 1;

    for (int p = 2; p <= n; p++) {
        if (isprime(p)) {
            ans = (ans * (1 + cnt(n, p))) % 1000000007;
        }
    }
    cout << ans;

    return 0;
}

T4 Yuilice的偶数回文串

题解思路

对于 $60\%$ 的数据，可以设立 $f[i]$ 表示为了使得区间 $[1,n]$ 是一个美丽字符串所需最小花费。 $f[i]$ 可以由前面的 $f[j]$ 转移而来： $f[i]=min(f[j-1]+ask(j,i))$ ，其中 $j$ 是最后一个偶回文串的左端点， $ask(j,i)$ 是为了使得区间 $[j,i]$ 变成偶回文串所需最小花费。

对于 $100\%$ 的数据，可以在 $60\%$ 数据的基础上将 $ask(j,i)$ 用动态规划预处理一下。设 $g[i][j]$ 是 $ask(i,j)$ ，则 $g[i][i+1]$ 可以直接判断 $t[i]$ 和 $t[i+1]$ 得到，其他 $g[i][j]$ 需要判断 $t[i]$ 和 $t[j]$ 得到。

参考代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read()
{
    int x;scanf("%d",&x);return x;
}
int n,ans,f[2010],w[2010],g[2010][2010];
char t[2010];
int main()
{
    n=read();
    scanf("%s",t+1);
    for(int i=1;i<=n;i++)
        w[i]=read();
    for(int len=2;len<=n;len++)
        for(int i=1,j=len;j<=n;i++,j++)
            if(t[i]==t[j])//如果左右端点相等，则g[i][j]=g[i+1][j-1]
                g[i][j]=g[i+1][j-1];
            else//如果不相等，需要在g[i+1][j-1]的基础上，修改某一个端点
                g[i][j]=g[i+1][j-1]+min(w[i],w[j]);
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=2;i<=n;i+=2)
        for(int j=1;j<i;j+=2)
            f[i]=min(f[i],f[j-1]+g[j][i]);
    cout<<f[n];
    return 0;
}

T5 先到为敬

解题思路

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read()
{
    int x;scanf("%d",&x);return x;
}
int n;
struct node
{
    int x,y;
}o[200010];
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        o[i]={read(),read()};
    cout<<abs(o[n].x-o[1].x);//直接输出|xn-x1|
}

对于 $30\%$ 的数据，可以暴力连边跑最短路。复杂度 $O(n^2)$ 。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read()
{
    int x;scanf("%d",&x);return x;
}
int n,e[1010][1010];
ll d[1010];
struct node
{
    int x,y;
}o[200010];
priority_queue<pair<ll,int>>q;
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        o[i]={read(),read()};
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)//暴力建图
            e[i][j]=e[j][i]=min(abs(o[i].x-o[j].x),abs(o[i].y-o[j].y));
    memset(d,0x3f,sizeof(d));
    d[1]=0;
    q.push({0,1});
    while(q.size())//dij最短路
    {
        int x=q.top().second;
        if(-q.top().first!=d[x])
        {
            q.pop();
            continue;
        }
        q.pop();
        for(int i=1;i<=n;i++)
            if(d[i]>d[x]+e[x][i])
            {
                d[i]=d[x]+e[x][i];
                q.push({-d[i],i});
            }
    }
    cout<<d[n];
}

对于另外 $35\%$ 的数据，此时从1到2到3到4...到n是最优秀的，循环一遍计算花费即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read()
{
    int x;scanf("%d",&x);return x;
}
int n;
ll ans;
struct node
{
    int x,y;
}o[200010];
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        o[i]={read(),read()};
    for(int i=1;i<n;i++)
        ans=ans+min(abs(o[i].x-o[i+1].x),abs(o[i].y-o[i+1].y));
    cout<<ans;
}

对于 $100\%$ 的数据，考虑优化建图方式。

对于三个点 $i, j, k$ , 若 $x_{i}<x_{j}<x_{k}$ ,
则 $i \rightarrow k=x_{k}-x_{i}=\left(x_{k}-x_{j}\right)+\left(x_{j}-x_{i}\right)=i \rightarrow j \rightarrow k$ , 边 $i \rightarrow k$ 是根本不用连的。
所以将所有点的 $x$ 坐标排序, 然后从小到大连边即可。
对于 $y$ 坐标同理。
然后对于限制条件 $\min \left|a_{x}-b_{x}\right|,\left|a_{y}-b_{y}\right|$ , 只需要跑最短路即可, 因为最短路不可能把你导向一条长的路径。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read()
{
    int x;scanf("%d",&x);return x;
}
int n;
ll ans,d[200010];
struct node
{
    int x,y,i;
}o[200010];
bool x_(node a,node b)
{
    return a.x<b.x;
}
bool y_(node a,node b)
{
    return a.y<b.y;
}
vector<pair<int,int>>e[200010];
priority_queue<pair<ll,int>>q;
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        o[i]={read(),read(),i};
    sort(o+1,o+1+n,x_);//按x排序并连接相邻的边
    for(int i=1;i<n;i++){
        e[o[i].i].push_back({abs(o[i].x-o[i+1].x),o[i+1].i});
        e[o[i+1].i].push_back({abs(o[i].x-o[i+1].x),o[i].i});

    }
    sort(o+1,o+1+n,y_);//按y排序并连接相邻的边
    for(int i=1;i<n;i++){
        e[o[i].i].push_back({abs(o[i].y-o[i+1].y),o[i+1].i});
        e[o[i+1].i].push_back({abs(o[i].y-o[i+1].y),o[i].i});
    }
        memset(d,0x3f,sizeof(d));
    d[1]=0;
    q.push({0,1});
    while(q.size())//dij最短路
    {
        int x=q.top().second;
        if(-q.top().first!=d[x])
        {
            q.pop();
            continue;
        }
        q.pop();
        for(auto it:e[x])
        {
            int w=it.first;
            int y=it.second;
            if(d[y]>d[x]+w)
            {
                d[y]=d[x]+w;
                q.push({-d[y],y});
            }
        }
    }
    cout<<d[n];
}

T6 又是字符串

题解思路

枚举所有的新串，然后计算原有的串变成新串所需的最小移动次数即可。如果最小移动次数 $\leq k$ 时， $ans$ 累加即可。

串 $s$ 移动成为串 $t$ 所需最小花费，我们可以找出 $t$ 串中第 $x$ 次出现的字符 $c1$ 与其在 $s$ 中第 $x$ 次出现的相同的字符 $c1$ 的位置，计入 $a$ 数组，答案即为 $a$ 数组的逆序对数量。可以通过50%的数据

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read()
{
    int x;scanf("%d",&x);return x;
}
string s;
set<string>o;
char t[300];
vector<int>pos[300];
int k,n,ans,cnt[300],now[300];
int a[300];
void dfs(int d)
{
    if(d==n)
    {
        now['K']=now['E']=now['Y']=0;
        int sum=0;

        for(int i=0;i<n;i++)
        {
            a[i]=pos[t[i]][now[t[i]]];//计算ti在s串中的对应位置
            now[t[i]]++;
        }
        for(int i=0;i<n;i++)//暴力计算逆序对数量即为所需最小移动的次数
            for(int j=i+1;j<n;j++)
                if(a[i]>a[j])
                    sum++;
        if(sum<=k)//如果所需最小移动次数小于等于k，则累加答案
            ans++;
        return ;
    }
    if(cnt['K'])//dfs枚举第k位使用了KE还是Y
    {
        cnt['K']--;
        t[d]='K';
        dfs(d+1);
        cnt['K']++;
    }
    if(cnt['E'])
    {
        cnt['E']--;
        t[d]='E';
        dfs(d+1);
        cnt['E']++;
    }
    if(cnt['Y'])
    {
        cnt['Y']--;
        t[d]='Y';
        dfs(d+1);
        cnt['Y']++;
    }
}
int main()
{
    cin>>s>>k;
    n=s.size();
    for(int i=0;i<n;i++)
    {
        pos[s[i]].push_back(i);
        cnt[s[i]]++;
    }
    dfs(0);
    cout<<ans;
}

注意到一个性质：当 $k>={n*(n-1)\over 2}$ 时，可以从原串更改为任意新串，所以 $k$ 太大没有什么用。

为了通过 $100\%$ 的数据，可以考虑动态规划。

我们 $f[i][j][k][t]$ 表示当前新串已经使用了 $i+j+k$ 个位置，使用了 $i$ 个 $K ， j$ 个 $E$ ， $k$ 个 $Y$ ，且一共换了 $t$ 次，的方案数。枚举下一个字符是什么，所需花费可以 $O(1)$ 计算，因此转移的复杂度也为 $O(1)$ 。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read()
{
    int x;scanf("%d",&x);return x;
}
string s;
char t[100];
vector<int>pos[100];
int k,n,anscnt[100],K,sum[31][100];
long long f[31][31][31][910],ans;
int main()
{
    cin>>s>>K;
    n=s.size();
    for(int i=0;i<n;i++)
    {
        pos[s[i]].push_back(i);//存储出现的下标
        cnt[s[i]]++;//存储出现次数
        sum[i+1]['K']=sum[i]['K'];
        sum[i+1]['E']=sum[i]['E'];
        sum[i+1]['Y']=sum[i]['Y'];
        sum[i+1][s[i]]++;//存储前缀和
    }
    f[0][0][0][0]=1;
    for(int i=0;i<=cnt['K'];i++)
        for(int j=0;j<=cnt['E'];j++)
            for(int k=0;k<=cnt['Y'];k++)
                for(int t=0;t<=900;t++)
                {
                    if(i+1<=cnt['K'])//如果可以向下一状态转移
                    {
                        int wei=pos['K'][i];
                        int cost=max(0,sum[wei]['E']-j)+max(0,sum[wei]['Y']-k);
                        //计算所需花费
                        f[i+1][j][k][t+cost]+=f[i][j][k][t];
                        //更新到下一状态中
                    }
                    if(j+1<=cnt['E'])
                    {
                        int wei=pos['E'][j];
                        int cost=max(0,sum[wei]['K']-i)+max(0,sum[wei]['Y']-k);
                        f[i][j+1][k][t+cost]+=f[i][j][k][t];
                    }
                    if(k+1<=cnt['Y'])
                    {
                        int wei=pos['Y'][k];
                        int cost=max(0,sum[wei]['K']-i)+max(0,sum[wei]['E']-j);
                        f[i][j][k+1][t+cost]+=f[i][j][k][t];
                    }
                    if(i==cnt['K']&&j==cnt['E']&&k==cnt['Y']&&t<=K)
                        ans+=f[i][j][k][t];
                   	//如果本状态是合法状态，累加到答案里
                }
    cout<<ans;
}

有帮助，赞一个

去预览

0/2000

全部评论 2

‮队团加不）童帅_者仇复
难度严重虚低

2025-01-28 来自湖南
1
- Yuilice
  回复‮队团加不）童帅_者仇复
  这就调一下(
  
  2025-01-29 来自浙江
  0
OyamaMahiro
姐们 T6 可是 AT *2400 你怎么评黄了/fn

https://atcoder.jp/contests/abc227/tasks/abc227_e

2025-01-29 来自山东
0
- OyamaMahiro
  回复OyamaMahiro
  不过 yysy 这题 2400 也太虚高了（感觉是 2000 左右
  
  2025-01-29 来自山东
  0
- ‮队团加不）童帅_者仇复
  回复OyamaMahiro
  估计是出题时乱标的，比赛结束后忘改回来了
  
  2025-01-29 来自湖南
  0
- OyamaMahiro
  回复‮队团加不）童帅_者仇复
  不过也有可能是出题人一眼会了然后就标了个很低的难度
  
  印象中我有一次搬了个 CF 3000 然后觉得这题很水扔到普及组模拟赛 T3 了，然后被【】了（
  
  2025-01-29 来自山东
  0