首页 > 其他分享 >Codeforces Round 878 (Div3)

Codeforces Round 878 (Div3)

时间:2023-07-03 20:44:57浏览次数:41  
标签:p2 cnt p1 878 int s2 s1 Codeforces Div3

B. Binary Cafe

image-20230703193601400

\(1 \leq n,k \leq 10^9\)

题解:思维

  • 考虑两种情况
  • 第一种:钱足够多,每种咖啡都可以买的情况下,答案为\(2^k\)
  • 第二种:钱不够多,因为任一面值的钱数都有唯一的二进制表达方式,所以答案为\(n + 1\)
  • 所以我们不妨先判断一下\(2^k\)有没有超过\(10^9\),如果超过了说明钱一定不够多,否则答案为\(min(2^k,n+1)\)
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#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<double, double> pdd;
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 n, k;
    cin >> n >> k;
    if (k >= 30)
    {
        cout << n + 1 << endl;
    }
    else
        cout << min(n + 1, (1LL << k)) << endl;
}
signed main(void)
{
    Zeoy;
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

C. Ski Resort

image-20230703194128518

题解:组合计数

  • 我们不妨将连续的可以度假的时间看成一个线段
  • 那么我们需要在这个线段中挑选连续的子线段作为一种方案
  • 容易发现我们可以使用捆绑法后即可得到答案
  • 假设线段长度为\(len\),且\(len >= k\),那么答案应该为\(\frac{(len - k + 1) \times (len - k + 2)}{2}\)
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#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<double, double> pdd;
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, k, q;
int a[N];

int A(int a, int b)
{
    int res = 1;
    for (int i = a, j = 1; j <= b; --i, ++j)
    {
        res *= a;
    }
    return res;
}

void solve()
{
    cin >> n >> k >> q;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    // cout << n << " " << k << " " << q << endl;
    int len = 0;
    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (a[i] <= q)
            len++;
        else
        {
            if (len >= k)
            {
                int t = len;
                while (t >= k)
                {
                    ans += A(t - k + 1, 1);
                    t--;
                }
            }
            len = 0;
        }
    }
    if (len >= k)
    {
        int t = len;
        while (t >= k)
        {
            ans += A(t - k + 1, 1);
            t--;
        }
    }
    cout << ans << endl;
}
signed main(void)
{
    Zeoy;
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

E. Character Blocking

image-20230703202455846

题解:模拟

  • 我们不妨记录初始状态下两个字符串之间有\(cnt\)个字符不相同
  • 对于封锁操作以及解锁我们可以利用邻接表思想实现
  • 对于交换操作,我们正常模拟,并维护\(cnt\)
  • 对于检查操作,如果\(cnt=0\),那么相等,否则不相等
  • 所以整个模拟过程的核心就是维护好两个字符串之间有多少个字符不相同
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#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<double, double> pdd;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 4e5 + 10, M = 4e5 + 10;

int t, q;
vector<int> g[N];

void solve()
{
    string s1, s2;
    cin >> s1 >> s2;
    cin >> t >> q;
    for (int i = 1; i <= q + 10; ++i)
        g[i].clear();
    int cnt = 0;
    for (int i = 0; i < s1.size(); ++i)
        if (s1[i] != s2[i])
            cnt++;
    s1 = " " + s1;
    s2 = " " + s2;
    vector<int> vis(s1.size() + 10);
    // cout << cnt << endl;
    for (int i = 1; i <= q; ++i)
    {
        int op, p, l, r, p1, p2;
        cin >> op;
        while (g[i].size())
        {
            int pos = g[i].back();
            vis[pos] = 0;
            if (s1[pos] != s2[pos])
                cnt++;
            g[i].pop_back();
        }
        if (op == 1)
        {
            cin >> p;
            vis[p] = 1;
            g[i + t].push_back(p);
            if (s1[p] != s2[p])
                cnt--;
        }
        else if (op == 2)
        {
            cin >> l >> p1 >> r >> p2;
            if (l == 1 && r == 1)
            {
                if (s1[p1] != s2[p1] && !vis[p1])
                    cnt--;
                if (s1[p2] != s2[p2] && !vis[p2])
                    cnt--;
                swap(s1[p1], s1[p2]);
                if (s1[p1] != s2[p1] && !vis[p1])
                    cnt++;
                if (s1[p2] != s2[p2] && !vis[p2])
                    cnt++;
            }
            else if (l == 1 && r == 2)
            {
                if (s1[p1] != s2[p1] && !vis[p1])
                    cnt--;
                if (s1[p2] != s2[p2] && !vis[p2])
                    cnt--;
                swap(s1[p1], s2[p2]);
                if (s1[p1] != s2[p1] && !vis[p1])
                    cnt++;
                if (s1[p2] != s2[p2] && !vis[p2])
                    cnt++;
            }
            else if (l == 2 && r == 1)
            {
                if (s1[p1] != s2[p1] && !vis[p1])
                    cnt--;
                if (s1[p2] != s2[p2] && !vis[p2])
                    cnt--;
                swap(s2[p1], s1[p2]);
                if (s1[p1] != s2[p1] && !vis[p1])
                    cnt++;
                if (s1[p2] != s2[p2] && !vis[p2])
                    cnt++;
            }
            else if (l == 2 && r == 2)
            {
                if (s1[p1] != s2[p1] && !vis[p1])
                    cnt--;
                if (s1[p2] != s2[p2] && !vis[p2])
                    cnt--;
                swap(s2[p1], s2[p2]);
                if (s1[p1] != s2[p1] && !vis[p1])
                    cnt++;
                if (s1[p2] != s2[p2] && !vis[p2])
                    cnt++;
            }
        }
        else
        {
            if (cnt == 0)
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        }
    }
}
signed main(void)
{
    Zeoy;
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

标签:p2,cnt,p1,878,int,s2,s1,Codeforces,Div3
From: https://www.cnblogs.com/Zeoy-kkk/p/17523967.html

相关文章

  • CodeForces 1508D Swap Pass
    洛谷传送门CF传送门先忽略掉所有\(a_i=i\)的点。考虑我们钦定一个点\(s\),每次与\(a_s\)换直到\(a_s=s\)为止。不难发现这样相当于在置换环上删掉\(a_s\)这个点。这样可以解决\(s\)所在的环。问题是可能会形成很多个环。我们把其他点按照\(s\)极角排序,注意......
  • Codeforces 585D Lizard Era: Beginning
    很容易想到可以对于每个任务选不去的那一个人进行搜索,时间复杂度\(O(3^n)\),明显过不了。发现\(n\le25,\lceil\frac{n}{2}\rceil\le13\),且各个任务间不会互相影响,便可以用折半搜索分成\(2\)部分来搜最后来合并。考虑如何合并两部分,令前一部分得到的值分别为\(a,b,c\),后......
  • Codeforces Round 881 Div2 A-F1题解
    codeforcesround881div2题解马上要秋招了,自己本事全丢了,感觉如果这样的话今年就估计要饿死了。先打div3,7月份得开始收心了A.SashaandArrayColoring题意,可以分任意组,每组的贡献是max-min,问最大贡献显然是贪心,从大到小配对一下就行,不想放代码了’B.LongLong给出一......
  • Codeforces Round #877 (Div. 2) A-E
    A代码#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;boolsolve(){intn;cin>>n;intmx=-2e9,mi=2e9;for(inti=1;i<=n;i++){intx;cin>>x;mi=min(x,mi);......
  • Educational Codeforces Round 151 (Rated for Div. 2)
    Preface期末考终于结束了,终于可以回来写题了这场是刚考完最后一门的那个晚上打的,因为太久没有写代码了所以不是很熟练而且脑子也不太灵光,只能堪堪写到D题而且手速感人上次CF第二个号因为Rating被roll了导致从紫名掉下来了,这场就把它又打上去了,再这样后面兴许要用第三个号打了......
  • Educational Codeforces Round 151 [div.2 #A-C] 赛后总结(contest/1845)
    link\(\textcolor{lightgreen}{A}-\textcolor{yellow}{B}-\textcolor{yellow}{C}-\textcolor{red}{D}-\textcolor{red}{E}-\color{red}{F}\)A给你一个数n,在给你一个数列1~k,其中x不能用,然后用其他的数任意累加,如能得到n,输出所用数字数量和具体数列。一眼分类。先分是......
  • CodeForces 高分段 dp 选做
    选取方式:CF*3000+按通过人数排序。CF1188DMakeEqual记\(cnt(x)\)表示\(x\)二进制下\(1\)的个数,题目等价于求\(x\)使得\[\sum_{x=1}^ncnt(x+a_n-a_i)\]最小。令\(a_i=a_n-a_i\)。从低位到高位考虑,假设当前要决策第\(k\)位,我们需要知道:\(1.\)\(x\)......
  • Educational Codeforces Round 151 F. Swimmers in the Pool
    一.前言本来打算打打这个比赛玩玩,结果同学找我打游戏王去了,就没打现场(逃)因为是一道不错的数学题,来写写补题的题解这里点名批评@HOLIC喂给我的假题意,让我查错大半天,最后发现题意错了还重新推了好多东西,拳头都硬了等会儿顺便分享下假题意的一种做法二.正文简单题意:有n个......
  • CodeForces 1845C Strong Password
    洛谷传送门CF传送门我怎么这么多天没写题解了,快来水一篇。考虑对\(s\)串建子序列自动机后dp。设\(n=|s|\)。建子序列自动机,就是求出\(nxt_{i,j}\)为\([i,n]\)中第一个等于\(j\)的位置,不存在则\(nxt_{i,j}=n+1\)。然后我们设\(f_{i,j}\)为填到密码的......
  • Educational Codeforces Round 151 (Rated for Div. 2)(C,D)
    EducationalCodeforcesRound151(RatedforDiv.2)(C,D)C(dp,子序列自动机)C题目大意就就是给你一个字符串\(s\),还给出两个边界字符串\(l\)和\(r\),长度为\(m\),问我们是否可以构造满足一下条件的字符串\(1\),第\(i\)个字符必须在\(l_i\)和\(r_i\)的双闭区间里面\(2\),......