AtCoder Beginner Contest 234

2023-11-21 23:56:16

A - Weird Function

给出f函数表达式，求：f(f(f(t)+t)+f(f(t)))
签到题
重复利用的代码，最好写一个函数出来

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

int f(int x)
{
    return x * x + 2 * x + 3;
}
int main() {
    int t;
    cin >> t;
    int ans = 0;

    int ft = f(t);
    int ftt = ft + t;
    int fftt = f(ftt);
    int fft = f(ft);
    ans = f(fftt +  fft);
    cout << ans << endl;
    return 0;
}

B - Longest Segment

给出n个点，找出两点间最长距离
签到题

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

double f(double x1, double y1, double x2, double y2)
{
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}

int main() {
    int n;
    cin >> n;
    vector<pair<double, double>> vec(n);
    double ans = 0;
    for(int i = 0; i < n; i ++)
    {
        double x1, y1;
        cin >> x1 >> y1;
        vec[i] = {x1, y1};
    }
    for(int i = 0; i < n; i ++)
    {
        for(int j = i + 1; j < n; j ++)
        {
            double temp = f(vec[i].first, vec[i].second, vec[j].first, vec[j].second);
            if(temp - ans > 1e-18) ans = temp;
        }
    }
    printf("%.10f\n", sqrt(ans));
    return 0;
}

C - Happy New Year!

求第k个仅由0和2组成的十进制数字。
二进制模拟
此题中：十进制数字中，填写2的可以看成二进制中的1， 填写0的可以看成二进制中的0。 这样每一个仅由0、2组成的十进制数字均唯一对应一个二进制数字。在此规则下，把该十进制转化为相应的二进制表示，逆序输出即可。（大小关系不变）

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
    LL n;
    cin >> n;
    vector<int> vec;
    while(n)
    {
        if(n & 1) vec.push_back(2);
        else vec.push_back(0);
        n >>= 1;
    }
    for(int i = vec.size() - 1; i >= 0; i --)
    {
        printf("%d", vec[i]);
    }
    return 0;
}

D - Prefix K-th Max

题目大意：给出一个排列P， 从前i个数中，找到第k大的数（i >= k时)。
STL应用 此处给出两种写法 堆、set
堆（优先队列版本）

思路：
小根堆，保证堆顶为堆中最小的元素。我们维护堆中的元素为k个，堆顶的即为所求。即堆中一定有 k - 1个大于堆顶的元素，堆顶即为第k大的元素

//从前i个数中，找到第k大的数（i >= k时)

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, k;
    scanf("%d%d", &n, &k);
    priority_queue<int, vector<int>, greater<int>> que; //小根堆
    for(int i = 1; i <= n; i ++)
    {
        int num;
        scanf("%d", &num);
        que.push(num);
        if(i == k)
        {
            printf("%d\n", que.top());
        }
        else if(i > k)
        {
            que.pop();
            printf("%d\n", que.top());
        }
    }
}

set版本
set的特性：去重、自动排序（默认从小到大）

  1. 当i <= k时，我们直接插入num, i == k时，直接输出set头元素。
  2. 当i > k时， set中第一个元素last(为前i个的第k大)，如果num > last, 则将last删除，并将num插入set中。set中的第一个元素仍为第k大。
//从前i个数中，找到第k大的数（i >= k时)

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, k;
    scanf("%d%d", &n, &k);
    set<int> st;
    for(int i = 1; i <= n; i ++)
    {
        int num;
        scanf("%d", &num);
        if(i <= k) st.insert(num);
        if(i == k)
        {
            printf("%d\n", *st.begin());
        }
        else if(i > k)
        {
            auto last = *st.begin();
            if(num > last){
                st.insert(num);
                st.erase(last);
            }
            printf("%d\n", *st.begin());
        }
    }
}

E - Arithmetic Number

题目大意：当一个十进制数字满足：d[2] - d[1] = d[3] - d[2] = …= d[n] - d[n - 1]时（一共由n位数字组成，从低位到高位以此为d[1] …到d[n]），就是一个arithmetic number。
给出x, 求不小于x的最小的arithmetic number。
思维、代码实现
思路：

  1. 十进制数字由0-9组成，且x < 10 ^ 17， 不多于18位。直接枚举d[n] - d[n - 1]的值，最高位的数字，最多18位，即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long  LL;
int main(){
    LL n;
    cin >> n;
    LL ans = 1e18;
    for(int i = 0; i < 10; i ++)
    {
        for(int j = 0; j < 10; j ++)
        {
            int d = j - i, temp = i; //两者之间的差值，前一个数
            LL y = 0;
            for(int k = 0; k < 18; k ++)
            {
                if(temp < 0 || temp > 9){
                    break;
                }
                y = y * 10 + temp;
                temp += d;
                if(y >= n) ans = min(ans, y);
            }
        }
    }
    cout << ans <<endl;
}

F - Reordering

题目大意：
S是由小写字母组成的长度为[1, 5000]的字符串，求能从S中得到多少非空子串（此题中字母出现的顺序可以和S不一样）。
组合数、dp

分析：

  1. 没有思路时，观察样例，一个字串可以包含两部分：组成的子串包含的字母；以及各个字母所用的数量。由此我们可以想到dp
  2. 状态表示：dp[i,j]:从前i个字母中选(1 <= i <= 26)，组成长度为j的方案数
  3. 状态计算：
    （freqi：表示 i + ‘a’ 这个字母出现了多少次。）
    AtCoder Beginner Contest 234
    即：从前i - 1个字母中选，选择长度为（j - k）的方案数(即dp[i-1][j-k]) * 从j个位置中选择k个该字母的位置方法数(即g数组). 再求和（0 <= k <= min(j, freqi))

AtCoder Beginner Contest 234

思考：从i个位置中选择j个位置该怎么求？
（1）第i个位置选， 则从前i-1中选j个。即g[i-1][j-1]
（2）第i个位置不选：即g[i-1][j]
所以 g[i][j] = g[i-1][j-1]+g[i-1][j]

代码如下：

  1. 解释sum数组：从前i个字母中选，总长度最大为多少。
  2. 解释第三重循环：当我枚举选择第三个字母的数量时，会超时；而枚举前i-1个选择的数量时，不会超时。（会卡aaaaaaaaaa这样的数据）
#include <bits/stdc++.h>
using namespace std;
const int N = 5010, mod = 998244353;
typedef long long LL;
int g[N][N];
char str[N];
int cnt[30];
int sum[30]; //前i个字母一共有多少个
int dp[30][N];
int main(void)
{
    cin >> str;
    int n = strlen(str);
    //预处理g数组
    for(int i = 0; i <= n; i ++)
    {
        g[i][0] = 1;
        for(int j = 1; j <= i; j ++)
        {
            g[i][j] = (g[i - 1][j] + g[i - 1][j - 1]) % mod;
        }
    }
    //处理cnt数组，每个字母有多少个
    for(int i = 0; i < n; i ++)
    {
        cnt[str[i] - 'a' + 1] ++;
    }
    for(int i = 1; i <= 26; i ++) sum[i] = sum[i-1] + cnt[i];

    dp[0][0] = 1;
    for(int i = 1; i <= 26; i ++)
    {
        for(int j = 0; j <= sum[i]; j ++) //总长度
        {
          /*
            for(int k = 0; k <= min(cnt[i], sum[i]); k ++) //选择第i个字母的个数
            {
                dp[i][j] = (dp[i][j] + (LL) dp[i - 1][j - k] * g[j][k]) % mod;
            }
          */
          for(int k = 0; k <= min(j, sum[i - 1]); k ++) //前i-1个字母组成的长度
          {
              if(j - k <= cnt[i]) dp[i][j]  = (dp[i][j] + (LL)dp[i - 1][k] * g[j][j - k]) % mod;
          }
        }
    }
    LL ans = 0;
    for(int i = 1; i <= sum[26]; i ++)
    {
        ans = (ans + dp[26][i]) % mod;
    }
    cout << ans <<endl;
    return 0;
}
上一篇：vue+elementUI 时间控件范围设置


下一篇：里程计标定：直接线性方法