首页 > 其他分享 >Codeforces Round #844(Div. 1 + Div. 2) 赛后补题

Codeforces Round #844(Div. 1 + Div. 2) 赛后补题

时间:2023-01-16 13:11:34浏览次数:46  
标签:844 const int double ++ 补题 ans Div define

A.Parallel Projection

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define cerr(x) std::cerr << (#x) << " is " << (x) << '\n'
#define IOS std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
#define PII pair<int, int>
#define pdd pair<double,double>

#define LL long long

const double CLOCKS_PER_SECOND = ((clock_t) 1000);
const double CLOCKS_PER_MILLISECOND = ((clock_t) 1);
const int N = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f;
const double eps = 1e-6;
//#define x first
//#define y second

int T;
int w, d, h;
int a, b, f, g;//(a,b),(f,g)
int solve1() {//往左
    int ans = 0;
    ans = f + h + a + abs(b - g);
    return ans;
}

int solve2() {//往右
    int ans = 0;
    ans = (w - f) + h + (w - a) + abs(b - g);
    return ans;
}

int solve3() {//往下
    int ans = 0;
    ans = g + h + b + abs(a - f);
    return ans;
}

int solve4() {
    int ans = 0;
    ans = (d - g) + h + (d - b) + abs(a - f);
    return ans;
}

void solve() {
    cin >> w >> d >> h;
    cin >> a >> b >> f >> g;
    int ans = 0;
    ans = min(min(min(solve1(), solve2()), solve3()), solve4());
    printf("%d\n", ans);
}

signed main() {
    IOS;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

B.Going to the Cinema

排序,对于\(a[i]\),如果前\(i-1\)个人人数大于等于\(a[i]\)就加上,同时判断加上第\(i\)个人会不会对第\(i+1\)个人产生影响。

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define cerr(x) std::cerr << (#x) << " is " << (x) << '\n'
#define IOS std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
#define PII pair<int, int>
#define pdd pair<double,double>

#define LL long long

const double CLOCKS_PER_SECOND = ((clock_t) 1000);
const double CLOCKS_PER_MILLISECOND = ((clock_t) 1);
const int N = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f;
const double eps = 1e-6;
//#define x first
//#define y second

int T;

void solve() {
    int a[N];
    int n;
    int ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + 1 + n);
    ans = a[1] == 0 ? 1 : 2;
    for (int i = 1; i < n; i++) {
        if (i - 1 >= a[i] && i < a[i + 1]) ans++;
    }
    printf("%d\n", ans);
}

signed main() {
    IOS;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

C. Equal Frequencies

参考@cup-pyy

问题1:设目标字符串共有\(x\)种字符,那么每种字符的个数就是\(\frac{n}{x}\)。统计原字符串每个字符的频数,并加入大根堆中。

枚举\(x\),对于前\(x\)种字符,判断每种字符的个数是否超过\(\frac{n}{x}\):超过部分计入答案;对于剩余\(n-x\)种字符,需要直接计入答案。

问题2:维护两个\(vector\):\(vector1\)保存上述两种情况字符对应的下标(用于修改),\(vector2\)保存需要补足数量的字符。对于\(vector1\)的每个下标,更改为需要补足数量的字符。

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define cerr(x) std::cerr << (#x) << " is " << (x) << '\n'
#define IOS std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);
#define PII pair<int, int>
#define pdd pair<double,double>

#define LL long long

const double CLOCKS_PER_SECOND = ((clock_t) 1000);
const double CLOCKS_PER_MILLISECOND = ((clock_t) 1);
const int N = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f;
const double eps = 1e-6;
//#define x first
//#define y second

int T;


void solve() {
    int n, f = -1;
    string s;
    cin >> n >> s;
    vector<PII > v;
    int ans = n + 1;
    map<int, vector<int> > m;
    for (int i = 0; i < s.length(); i++) {
        m[s[i] - 'a'].push_back(i);
    }
    for (int i = 0; i < 26; i++) {
        if (m[i].size() == 0) v.push_back({0, i});
        else v.push_back({m[i].size(), i});
    }
    sort(v.begin(), v.end(), greater<PII >());
    for (int i = 1; i <= 26; i++) {
        if (n % i) continue;
        int sum = 0;
        int x = n / i;
        for (int j = 0; j < i; j++)
            if (v[j].first > x) sum += v[j].first - x;
        for (int j = i; j < 26; j++)
            sum += v[j].first;
        if (sum < ans) {
            ans = sum;
            f = i;
        }
    }
    cout << ans << endl;
    int sum = n / f;
    vector<int> v1;
    vector<int> v2;//如果超过,则将对应下标记录,将其加入到未超过的之中。
    for (int i = 0; i < f; i++) {//前f种
        if (v[i].first > sum) {
            for (int j = 0; j < v[i].first - sum; j++)
                v1.push_back(m[v[i].second][j]);//把超过种数的每个下标记录下来
        }
        if (v[i].first < sum) {
            for (int j = 0; j < sum - v[i].first; j++)//补足
                v2.push_back(v[i].second);
        }
    }
    for (int i = f; i < 26; i++) {//对于剩余种数,如果出现在字符中,直接将其视为超过种数的
        if (m[v[i].second].size() == 0) continue;
        for (auto j: m[v[i].second])
            v1.push_back(j);
    }
    for (int i = 0; i < ans; i++)
        s[v1[i]] = (char) (v2[i] + 'a');
    cout << s << endl;
    return;
}

int main() {
    IOS;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

D.Many Perfect Squares

设两个完全平方数分别为\(A^2,B^2\)可以被如下表示:\(a_i+x=A^2,a_j+x=B^2(i>j)\)

相减:\(a_i-a_j=(A+B)(A-B)\)

此时枚举\(x\)变为枚举因子:

令\(u=A+B,v=A-B\),枚举\(u\),可解得\(A=(u+v)/2,B=(u-v)/2\),代入\(x=A^2-a_i\)。

对于每一个\(x\),暴力求出完全平方数个数再判断即可。

枚举因子是\(O(\sqrt x)\),暴力枚举是\(O(n^3)\),都很稳。

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define cerr(x) std::cerr << (#x) << " is " << (x) << '\n'
#define IOS std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
#define PII pair<int, int>
#define pdd pair<double,double>

#define LL long long

const double CLOCKS_PER_SECOND = ((clock_t) 1000);
const double CLOCKS_PER_MILLISECOND = ((clock_t) 1);
const int N = 100, mod = 1e9 + 7, inf = 0x3f3f3f3f;
const double eps = 1e-6;
//#define x first
//#define y second

int T;


void solve() {
    int n, a[N];
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    LL ans = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            LL t = a[i] - a[j];
            for (LL x = 1; x <= sqrt(t); x++) {
                if (t % x) continue;
                LL y = t / x;
                if ((x + y) & 1LL || (x - y) & 1LL) continue;
                LL A = (x + y) >> 1LL, B = (x - y) >> 1LL;
                if (A * A < a[i]) continue;
                LL temp = A * A - a[i];
                LL res = 0;
                for (int k = 1; k <= n; k++) {
                    LL num = a[k] + temp;
                    LL sq = sqrt(num);
                    if (sq * sq == num) res++;
                }
                ans = max(ans, res);
            }
        }
    }
    printf("%lld\n", ans);
}

signed main() {
    IOS;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

标签:844,const,int,double,++,补题,ans,Div,define
From: https://www.cnblogs.com/MrWangnacl/p/17055181.html

相关文章

  • [个人训练]-Codeforces Round #842 (Div. 2)-A~F
    前几天vp的一场,前面的题相对水一点,干脆倒着写题解~题目链接:https://codeforces.com/contest/1768目录F.WonderfulJumpE.PartialSortingD.LuckyPermutationC.Eleme......
  • Educational Codeforces Round 120 (Rated for Div. 2) C,D
    EducationalCodeforcesRound120(RatedforDiv.2)C,DCC这个题目大意是给我们n个数,我们可以把ai变成ai-1,或者是把ai变成aj,而我们需要知道最少的操作数把n个数的和......
  • SMU Winter 2023 Round #3 (Div.2)
    B.三元组题目:给定一个长度为n的数列a,对于一个有序整数三元组(i,j,k),若其满足1≤i≤j≤k≤n并且ai+aj=ak,则我们称这个三元组是「传智的」。现在请你计算,有......
  • Codeforces 732 Div2 A-D题解
    感觉做过这场啊,要不就是看过A题AquaMoonandTwoArrays问前加后减能不能把A变成B,首先这个貌似是经典老题了,无论怎么操作数列总和不变,如果和不相同,变不了,其他情况暴力判......
  • Educational Codeforces Round 119 (Rated for Div. 2)
    EducationalCodeforcesRound119(RatedforDiv.2)我真是越来越菜了,现在竟然连a都做不出来了,o(╥﹏╥)oAA这个题是对于每一个ai和ai+1,(an和a1)都有一个判断,判断这两......
  • Codeforces Round #843 (Div. 2)
    C.InterestingSequence(二进制)题目大意给定两个大于等于0的数\(n,\x\),求满足\(n\&(n+1)\&(n+2)\cdotsm=x\)的最小\(m\),若不存在输出-1。解题思路首先若\(n<x\)肯......
  • Codeforces Round #843 (Div. 2) A1A2BCE(D待补)
    url:Dashboard-CodeforcesRound#843(Div.2)-CodeforcesA1&&A2.GardenerandtheCapybaras题意:给你一个只由$a$和$b$两个字符组成的字符串现在要你把这个字......
  • Codeforces Round #834 (Div. 3) D. Make It Round(贪心/数论)
    https://codeforces.com/contest/1759/problem/D题目大意:给定一个数字n,要求扩大至多m倍,求最大的并且最多0的数字。input106115431354161005012345264......
  • Codeforces Round #843 (Div. 2) F. Laboratory on Pluto
    题目链接首先看问题一(算最小周长),并没有用题解的神奇结论,而是直接整除分块枚举\((n-1)/x\),取对应的最小x,在\(\sqrtn\)种可能内取最优的(能暴力算为什么要考虑结论呢)然而最......
  • CF244A Dividing Orange 题解
    Description有\(n\timesk\)个橘子,\(k\)个小朋友每人拿\(n\)个,但是每个人都指定了一个橘子\(a_i\),分配时必须要把\(a_i\)给第\(i\)个小朋友,求任一分配方案。So......