挑战赛#14 官方题解

userId_undefined

Yuilice

倔强青铜

2025-01-28 16:29:22

发布于：浙江

110阅读
0回复
0点赞

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

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

题解正文

T1 雪块高度

解题思路

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

由于给出的是相邻两个数，较小的数字xx为(1+2+3+...+n−1)(1 + 2 + 3 +... + n-1),较大的数字yy为(1+2+3+...+n−1+n)(1 + 2 + 3 +... + n-1 + n)，他们的差值为nn。
我们可以得出，未被覆盖的部分的高度为1+2+3+...+n−answer1+2+3+...+n-answer，故答案为(y−x)×(y−x+1)/2−y(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 采矿场

解题思路

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

因为最后的答案一定为6x6^x + 9y9 ^ y + z×1z \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 正除数

解题思路

一个整数xx可以通过质因数分解得到x=p1a1p2a2⋯pkakx=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}，其中pip_i是质数，aia_i是pip_i在xx中出现的次数。对于所有的质因数pip_i，求解N!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%60\%的数据，可以设立f[i]f[i]表示为了使得区间[1,n][1,n]是一个美丽字符串所需最小花费。f[i]f[i]可以由前面的f[j]f[j]转移而来：f[i]=min(f[j−1]+ask(j,i))f[i]=min(f[j-1]+ask(j,i))，其中jj是最后一个偶回文串的左端点，ask(j,i)ask(j,i)是为了使得区间[j,i][j,i]变成偶回文串所需最小花费。

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

解题思路

对于5%5\%的数据，此时从i走到j所需花费为∣xi−xj∣=∣yi−yj∣|x_i-x_j|=|y_i-y_j|，走额外的点不会使得答案更小，因此输出∣xn−x1∣|x_n-x_1|即可。复杂度O(n)O(n)

#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%30\%的数据，可以暴力连边跑最短路。复杂度O(n2)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%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%100\%的数据，考虑优化建图方式。

对于三个点 i,j,ki, j, k, 若 xi<xj<xkx_{i}<x_{j}<x_{k},
则 i→k=xk−xi=(xk−xj)+(xj−xi)=i→j→ki \rightarrow k=x_{k}-x_{i}=\left(x_{k}-x_{j}\right)+\left(x_{j}-x_{i}\right)=i \rightarrow j \rightarrow k, 边 i→ki \rightarrow k 是根本不用连的。
所以将所有点的 xx 坐标排序, 然后从小到大连边即可。
对于 yy 坐标同理。
然后对于限制条件 min⁡∣ax−bx∣,∣ay−by∣\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 又是字符串

题解思路

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

串ss移动成为串tt所需最小花费，我们可以找出tt串中第xx次出现的字符c1c1与其在ss中第xx次出现的相同的字符c1c1的位置，计入aa数组，答案即为aa数组的逆序对数量。可以通过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)2k>={n*(n-1)\over 2}时，可以从原串更改为任意新串，所以kk太大没有什么用。

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

我们f[i][j][k][t]f[i][j][k][t] 表示当前新串已经使用了 i+j+ki+j+k 个位置，使用了 ii 个 K，jK ， j 个 EE ， kk 个 YY ，且一共换了 tt 次，的方案数。枚举下一个字符是什么，所需花费可以O(1)O(1)计算，因此转移的复杂度也为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;
}
userId_undefined
去预览
0/2000

全部评论 2

  • userId_undefined

    复仇者_帅童

    尊贵铂金

    难度严重虚低

    2025-01-28 来自 湖南

    1
  • userId_undefined

    1

    尊贵铂金

    姐们 T6 可是 AT *2400 你怎么评黄了/fn

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

    2025-01-29 来自 山东

    0
    • userId_undefined

      1

      回复1

      不过 yysy 这题 2400 也太虚高了（感觉是 2000 左右

      2025-01-29 来自 山东

      0
    • userId_undefined

      复仇者_帅童

      回复1

      估计是出题时乱标的，比赛结束后忘改回来了

      2025-01-29 来自 湖南

      0
    • userId_undefined

      1

      回复复仇者_帅童

      不过也有可能是出题人一眼会了然后就标了个很低的难度

      印象中我有一次搬了个 CF 3000 然后觉得这题很水扔到普及组模拟赛 T3 了，然后被【】了（

      2025-01-29 来自 山东

      0

热门讨论