首页 > 其他分享 >Codeforces Round 713 (Div

Codeforces Round 713 (Div

时间:2023-03-13 19:14:25浏览次数:53  
标签:std 10 const cout int 713 Codeforces cin Div

Codeforces Round 713 (Div. 3)

A-B Palindrome

给定字符串只含有\('?'\ '0' \ '1'\),给定字符串中1的个数\(a\)和0的个数\(b\),你需要将?替换成0 或 1,使得该字符串变成回文串,并且使得1的个数为a,0的个数为b

题解:构造 + 模拟

注意以下几点:

  1. 字符串长度为\(a+b\),a和b只能有一个是奇数;
  2. 对于两个对应的位置,如果一个位置确定,那么另一个位置如果是?,也是确定的
  3. 如果对应的两个位置都是确定的,但是如果不一样,该字符串是不合法的

模拟的过程:

  1. 如果长度为奇数,先确定中间的位置是1还是0
  2. 将所有可以确定的问号都替换掉,并检查字符串是否合法
  3. 将只剩未确定问号的字符串中1的数量和0的数量计算出来,然后a和b各自减去这些数量,如果a或b小于0,说明不合法
  4. 替换所有未确定的问号,如果1有多余就用1,0有多余就用0,如果两个都没有多余的了,说明不合法
  5. 如果以上步骤都合法,说明可以构造出这样一个合法字符串
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;

void solve()
{
    int a, b;
    cin >> a >> b;
    string s;
    cin >> s;
    int n = a + b;
    s = " " + s;
    if (a % 2 == 1 && b % 2 == 1)
    {
        cout << -1 << endl;
        return;
    }
    if (a % 2 == 1)
    {
        if (s[n / 2 + 1] == '?')
        {
            s[n / 2 + 1] = '0';
        }
        else if (s[n / 2 + 1] == '1')
        {
            cout << -1 << endl;
            return;
        }
    }
    else if (b % 2 == 1)
    {
        if (s[n / 2 + 1] == '?')
        {
            s[n / 2 + 1] = '1';
        }
        else if (s[n / 2 + 1] == '0')
        {
            cout << -1 << endl;
            return;
        }
    }
    for (int i = 1; i <= n / 2; ++i)
    {
        if (s[i] != s[n - i + 1] && s[i] != '?' && s[n - i + 1] != '?')
        {
            cout << -1 << endl;
            return;
        }
        else if (s[i] != s[n - i + 1] && (s[i] == '1' || s[n - i + 1] == '1'))
        {
            s[i] = s[n - i + 1] = '1';
        }
        else if (s[i] != s[n - i + 1] && (s[i] == '0' || s[n - i + 1] == '0'))
        {
            s[i] = s[n - i + 1] = '0';
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        if (s[i] == '0')
            a--;
        else if (s[i] == '1')
            b--;
    }
    if (a < 0 || b < 0)
    {
        cout << -1 << endl;
        return;
    }
    for (int i = 1; i <= n / 2; ++i)
    {
        if (s[i] == s[n - i + 1] && s[i] == '?')
        {
            if (a >= 2)
            {
                a -= 2;
                s[i] = s[n - i + 1] = '0';
            }
            else if (b >= 2)
            {
                b -= 2;
                s[i] = s[n - i + 1] = '1';
            }
            else
            {
                cout << -1 << endl;
                return;
            }
        }
    }
    cout << s.substr(1) << endl;
}
signed main(void)
{
    Zeoy;
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

Permutation by Sum

现在又一个由排列构成的序列\(P\)\([1,n]\),给定序列长度n,区间端点\(l,r\),以及\(s\),让你利用这个序列构造出\(s=p_l+p_{l+1}+...+p_r\)

如果无法构造输出\(-1\)

题解:构造 + 思维

  1. 什么情况下可以构造出来:

​ \(len = r-l+1\),如果序列为\(1,2,3.....n\)

​ 那么只有\(s>=1+2+..+i(长度为len)\)并且\(s<=n+n-1+n-2+...+i(长度为len)\)时可以构造出

  1. 如何构造(举个样例):

    1) \(1,2,3...10\) \(len = 4 , s = 16\)

    2)取\(1,2,3,4\)

    3)\(dif = s - (1+2+3+4) = 6\), \(6/4=1,6\%4=2\)

    4)\(1,2,3,4 --> 2,3,4,5 --> 2,3,6,5\)

完成构造

#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;

int n, l, r, s;
int a[N];

void solve()
{
    cin >> n >> l >> r >> s;
    map<int, int> mp;
    int len = r - l + 1;
    if ((n - len + 1 + n) * len / 2 < s || (1 + 1 + len - 1) * len / 2 > s)
    {
        cout << -1 << endl;
        return;
    }
    int dif = s - (1 + 1 + len - 1) * len / 2;
    int x = dif / len, plus = dif % len;
    int cnt = 0;
    for (int i = l; i <= r; ++i)
    {
        a[i] = ++cnt;
        a[i] += x;
        mp[a[i]]++;
    }
    if (plus)
    {
        for (int i = l; i <= r; ++i)
        {
            if (a[i] + plus <= n && !mp[a[i] + plus])
            {
                mp[a[i]] = 0;
                a[i] += plus;
                mp[a[i]] = 1;
                break;
            }
        }
    }
    cnt = 0;
    for (int i = 1; i <= n && cnt < l - 1; ++i)
    {
        if (!mp[i])
        {
            mp[i] = 1;
            cnt++;
            cout << i << " ";
        }
    }
    for (int i = l; i <= r; ++i)
        cout << a[i] << " ";
    cnt = 0;
    for (int i = 1; i <= n && cnt < n - r; ++i)
    {
        if (!mp[i])
        {
            mp[i] = 1;
            cnt++;
            cout << i << " ";
        }
    }
    cout << endl;
}
signed main(void)
{
    Zeoy;
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

Education

一个人想要尽快得到\(m\)元钱,他现在有\(0\)元,他在公司中的职位为\(1\),职位越高每天工资越高,每一天他有两种选择:

  1. 得到相应职位对应的工资 \(a_i\)
  2. 花去\(b_i\)的钱使得自己的职位上升一级

求这个人最少几天能够获得\(m\)元钱

题解:贪心 + 模拟

一开始以为是\(dp\),后来发现是个贪心问题,对于一个人来说他想获得m元钱的最快方法就是先快速到达一个理想的职位,然后一直拿工资,直到获得m元

所以,该题我们只需要枚举在每个职位能够多久获得m元,然后取\(min\)即可

接下来的事情只剩下模拟了,注意使自己职位上升也要算一天

#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;

int n, m;
int a[N];
int b[N];

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i < n; ++i)
        cin >> b[i];
    int ans = INF;
    int now = 0;
    int sum = 0;
    for (int i = 1; i <= n; ++i)
    {
        ans = min(ans, sum + (long long)(ceil(1.0 * max(0ll, m - now) / a[i])));
        if (i < n)
        {
            int p = (long long)ceil(1.0 * max(0ll, (b[i] - now)) / a[i]);
            sum += p + 1;
            now += p * a[i] - b[i];
        }
    }
    cout << ans << endl;
}
signed main(void)
{
    Zeoy;
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

Short Task

规定\(d(n)=\sum_{k|n}k\),即\(d(n)\)为n的约数之和,现在每次询问给定c,求出最小的n使得\(d(n)=c,c<=1e7\),如果不存在输出-1

题解:约数之和 : 需要知道调和级数和如何求约数之和

引理:调和级数:\(n+\frac{n}{2}+\frac{n}{3}+...+\frac{n}{n}=nlogn\)

首先n一定小于1e7,我们先\(nlogn\)预处理出le7以内的所有\(d(n)\),然后\(map\)映射一下即可,查询出直接查询\(map\)即可

#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 1e7 + 10, M = 4e5 + 10;

int d[N];
int ans[N];

void solve()
{
    int n;
    cin >> n;
    if (!ans[n])
        cout << -1 << endl;
    else
        cout << ans[n] << endl;
}
signed main(void)
{
    Zeoy;
    int T = 1;
    cin >> T;
    for (int i = 1; i < N; ++i)
        for (int j = i; j < N; j += i)	//i是j的约数,复杂度是调和级数nlogn
            d[j] += i;
    for (int i = 1; i < N; ++i)
    {
        if (d[i] > N - 10)
            continue;
        if (!ans[d[i]])
            ans[d[i]] = i;
    }
    while (T--)
    {
        solve();
    }
    return 0;
}

标签:std,10,const,cout,int,713,Codeforces,cin,Div
From: https://www.cnblogs.com/Zeoy-kkk/p/17212491.html

相关文章

  • Codeforces Round 857 (Div. 2)
    比赛地址做到F心态崩了,自然不会去做G.F考虑最终路径一定是这样的1到x节点在x处攒够路费再到n.后者可以通过从n跑dij来求最短路。考虑前者需要求从1~x的最小代价。......
  • A. K-divisible Sum
    A.K-divisibleSum思路\[ans=\left\lceil\frac{kx}{n}\right\rceil\]\[x=x_{min}\ge\left\lceil\frac{n}{k}\right\rceil\]代码点击查看代码#inc......
  • CodeForces 1147F Zigzag Game
    洛谷传送门CF传送门很有意思的题。考虑若无边权的限制则B必胜,不妨猜想有了限制之后仍然是B必胜。假设A选了I(若A选了D可以边权取相反数),若B走了\((a,b)\)......
  • Vue.js框架:单个div盒子(元素)放至全屏显示
    一、页面元素需要全屏展示的div或其他元素标签的id要设置,方便获取dom节点。再添加一个可以触发点击事件的元素进行操作。<divid="fullDom"><span@click......
  • 2023学校周赛Round1 Div1
    \(A\)拿个栈模拟一下。\(B\)推一推式子,把\((\displaystyle\sum_{i=1}^{n}a_i)^3\)展开,会得到三种类型的式子,其中两个都是可以线性求出来的,第三个的6倍就是答案。\(C\)......
  • Codeforces Round 857 (Div. 2)
    题目链接A核心思路读懂题目也就不难了。//Problem:A.Likes//Contest:Codeforces-CodeforcesRound857(Div.2)//URL:https://codeforces.com/contest/180......
  • Codeforces比赛规则梳理
    1、排名div选手们按Rating以1700为界划分为Div.1和Div.2两类,Div.1的比赛较难,Div.1的ABC三题会和Div.2的CDE三题相同。每次比赛结束后Rating都会依据此前各个选手的Rating和......
  • Codeforces Round #666 (Div. 2)D. Stoned Game(博弈问题)
    problemT和HL玩游戏,n堆石头,玩家轮流在石堆中选择一个(但不能是上一个人取的那堆)取一个石子一旦有一方不能取石头则判输solution统计所有石头数,如果总数小于mx(最多石头的一堆)......
  • Codeforces Round 857 (Div. 2)
    更好的阅读第一次进入时加载缓慢,请耐心等待。赛时降智,菜是原罪。A.Likes简单题。#include<bits/stdc++.h>usingnamespacestd;intT,n,a[11111],s[11111];intm......
  • 练习记录-cf-div2-A-D
    上课的时候抓紧时间写的,状态不好,c也没过,估计换个环境也很难想吧ALikes题意点赞,a<0表示取消赞a>0表示增加赞,a数组乱序输出如何排让赞数价值最多分别记录大于0和小......