[数据结构与算法]Codeforces Round #570 (Div. 3)部分题解(A ~ E)

前言

我把权游第4季看完都没想明白这个问题到底是啥意思。

随着人工智能的发展，在技术对人类本身的监控方面有哪些（建议字数：300字以上）

虽然我语文不是很行，但是也没到看不懂中文题目的程度：
虽然最后瞎编了一堆话交了上去，但是我还是对这个题的题意表示很纠结。

8说了，上主菜。

A - Nearest Interesting Number(暴力+水题)

比赛链接：https://codeforces.com/problemset/problem/1183/A

题目大意

给你一个数$x$，找出离$x$最近的一个数$y$满足：
$1.y>=x$；
$2.y的每个数位之和可以整除4$；

思路

从$x$开始暴力所有的数，直到遇到一个满足条件的数为止。

AC代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=55000;

int main()
{
    int n;
    cin>>n;
    while(true){
        int m=n;
        int sum=0;
        while(m){
            sum+=m%10;
            m/=10;
        }
        if(sum%4==0){
            cout<<n<<endl;
            break;
        }
        n++;
    }
}

B - Equalize Prices (思维)

比赛链接：https://codeforces.com/problemset/problem/1183/B

题目大意

现在给你一个长度为$n$的数组$a$。
你可以把数组$a$中的任意一个数$a_i$变成[$a_i?k,a_i+k$]中的任意一个数字。但每个数字只能改一次。
例如$a_i=4$，$k=3$，则$a_i$可以改为$1$~$7$中的任意一个数字。

现在问，你现在可不可以把数组$a$中的所有数字改成同一个数字$B$？

不能就输出$?1$，如果能则输出$B$的最大值。

思路

一个很简单的思维题。

首先我们先想最简单的：数字$B$存不存在？

我们只需要找到数组中最大的数$maxx$和数组中最小的数$minx$。
$minx$最大可以变成$minx+k$，$maxx$最小可以变成$maxx?k$.
如果此时最小的最大还是小于最大的最小，那么$B$就肯定不存在了，输出$?1$；否则就存在$B$。

那么最大的$B$是多少呢？
是$minx+k$。

AC代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=150;
int a[maxn];
int main()
{
    int q,n,k;
    cin>>q;
    while(q--)
    {
        cin>>n>>k;
        for(int i=0;i<n;i++)
            cin>>a[i];
        sort(a,a+n);
        if(a[0]+k>=a[n-1]-k) cout<<a[0]+k<<endl;
        else cout<<"-1"<<endl;
    }
}

C - Computer Game (思维)

比赛链接：https://codeforces.com/problemset/problem/1183/C

题目大意

宿舍断电了，$Vova$的电脑还有$k$的电量，但是他刚入手了一款非常好玩的游戏，于是他决定上号玩一把。

这个游戏有$n$个关卡，$Vova$作为一个游戏高手自然想要玩通关。关卡分为两种：$a和b$。

1.当$Vova$的电脑电量严格大于$a$时，他可以玩一把$a$类型的关卡，此时电量会减少$a$；
2.当$Vova$的电脑电量严格大于$b(b<a)$时，他可以玩一把$b$类型的关卡，此时电量会减少$b$；
3.当$Vova$的电脑电量小于$b$时，他就没法玩游戏了。

$Vova$想知道他能否在电脑歇菜之前通关这个游戏，不能输出$?1$。
如果可以，$Vova$想知道他最多能玩几场$a$类型的关卡，输出这个数量。

思路

彼时彼刻，恰如此时此刻，宿舍断电了，有点裂开。
一道有点难度的思维题，推了好一会才出的答案。

首先还是先判断最简单的：
从题目中可以看出$b<a$，那么我们就看如果我们玩$n$场$b$类型的关卡电脑能否撑得住。
玩n场b类型的关卡需要的电量为$n?b$，电脑电量为$k$，则根据题目描述：$n?b<k$

接下来我们设可以玩$x_1$场$a$类型的关卡，$x_2$场$b$类型的关卡，则有公式：

$x_1+x_2=n$
$x_1?a+x_2?b<k$

此时再根据$a>b$可以推得：

$x_1?(a?b)+(x_1+x_2)?b<k$

再结合$x_1+x_2=n$，再次化简：

$x_1?(a?b)+n?b<k$

$x_1<\frac{k?(n?b)}{(a?b)}$

再利用C语言中的$/$是向下取整，所以$x_1=\frac{k?(n?b)}{(a?b)}$。

不过还有一个点：当$k?(n?b)$可以整除$(a?b)$时，代表电量是正好够的.
但实际上是没法完成的，因为你的用电量是要严格大于$k$的，所以此时我们需要少玩一局$a$类型的关卡($x_1??$)。

AC代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=150;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        ll k,n,a,b;
        cin>>k>>n>>a>>b;
        if(k<=n*b) cout<<"-1"<<endl;
        else
        {
            ll x=(k-n*b)/(a-b);
            if((k-n*b)%(a-b)==0) x--;
            cout<<min(n,x)<<endl;
        }
    }
}

D - Candy Box (easy version) (魔鬼题+贪心)

比赛链接：https://codeforces.com/problemset/problem/1183/D

题目大意

你现在有$n$个糖果，第$i$个糖果的种类是$a_i$。
现在你想拿着你的糖果去送人。

你不喜欢把糖果混在一起，所以你都只给每个人一种不同于其他人的糖果。
你希望送给每个人的糖果的数量都不同，你现在想知道你最多能送出多少糖果。

思路

这个题的时间复杂度很魔鬼，给了$3s$，却在那里卡死你的memset，只要用这个初始化数组就会$T$。

很简单的一道贪心题。
我们先把所有糖果按照种类统计一下：

for(int i=0;i<=n;i++)
	a[i]=0;          //a[i]:种类为i的糖果的数量
for(int i=0;i<n;i++){
	int x;
	cin>>x;
	a[x]++;
}

接下来从大到小排个序，然后贪心模拟整个过程就可以。

每次记录上次送出的糖果数量$pre$：

如果此次要送的糖果的数量小于上次的数量$pre$，那我们就全部送出去，并更新上一次的数量$pre$；
否则我们就送$pre?1$个，并更新上一次的数量$pre$；

AC代码

///memset会T
///不是3s吗？
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=2e5+100;

int a[maxn];

int main()
{
    int t;
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=0;i<=n;i++)
            a[i]=0;
        for(int i=0;i<n;i++){
            int x;
            cin>>x;
            a[x]++;
        }
        sort(a+1,a+n+1,greater<int>());
        ll ans=a[1];
        int pre=a[1];
        for(int i=2;i<=n;i++){
            if(a[i]==0) break;
            if(a[i]<pre){
                ans+=a[i];
                pre=a[i];
            }
            else{
                ans+=pre-1;
                pre--;
            }
            if(pre==0) break;
            //cout<<"ans="<<ans<<endl;
        }
        cout<<ans<<endl;
    }
}

E - Subsequences (easy version) (BFS)

比赛链接：https://codeforces.com/problemset/problem/1183/E

题目大意

给一个字符串$s$，每次你可以删除任意一个字符形成一个新串$s^{\prime }$。

问字符串$s$是否可以生成$k$个不同的字符串。
不可以的话输出$?1$，可以的话输出生成$k$个不同的字符串最少要删除多少个字符。

思路

暴力就可以，直接写一个$BFS$爆搜出所有结果，用$map$来进行标记。

AC代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=2e5+100;

string ss;
map<string,int> mp;
int n,k;
int bfs()
{
    queue<string> q;
    q.push(ss);
    mp[ss]=1;
    int cnt=0;
    while(!q.empty()&&k){
        string str=q.front();
        q.pop();
        k--;
        cnt+=n-str.size();
        for(int i=0;i<str.size();i++)
        {
            string s1=str.substr(0,i)+str.substr(i+1,str.size()-i-1);
            if(mp[s1]==0){
                mp[s1]=1;
                q.push(s1);
            }
        }
    }
    if(k) return -1;
    else return cnt;
}
int main()
{

    cin>>n>>k;
    cin>>ss;
    int ans=bfs();
    cout<<ans<<endl;
}

感谢阅读，希望能对你产生一点用处。