首页 > 其他分享 >Codeforces Round 963 (Div. 2) 补题记录（A~D，F1）

Codeforces Round 963 (Div. 2) 补题记录（A~D，F1）

时间：2024-08-05 08:54:34浏览次数：17  
标签：F1 ch 963 int read 补题 define getchar

不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.不会做 F1.

A

直接计算每一个选项最多对多少个题加起来即可。

时间复杂度为 \(O(n)\)。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define pb emplace_back
#ifdef __unix__
#define getchar getchar_unlocked
#else
#define getchar _getchar_nolock
#endif
#define int long long
using namespace std;
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')w=-w;
        ch=getchar();
    }
    while(isdigit(ch))
        s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
void read(int &x){
    int s=0,w=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')w=-w;
        ch=getchar();
    }
    while(isdigit(ch))
        s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    x=s*w;
}
template<typename...argme>
void read(int &x,argme &...vv){
    read(x),read(vv...);
}
const int N=1000100;
int a[N];
signed main(){
    int T=read();
    while(T--){
        string s;
        int n;
        cin>>n>>s;
        s=' '+s;
        int box[10]={0};
        for(int i=1;i<=4*n;++i)
            if(s[i]!='?')++box[s[i]-'A'];
        int mx=0;
        for(int i=0;i<4;++i)
            mx+=min(box[i],n);
        cout<<mx<<'\n';
    }
}

B

这是 B？这不比 C 难？

首先如果一开始全部是奇数或者全部是偶数的话不需要操作。其他的时候一定是把所有的数都变成奇数。

然后贪心的找到最大的奇数 \(v\)，把所有的偶数从小到大排序，令当前枚举到的偶数值为 \(w\)：

  • \(v\ge w\)。那么此时 \(w\leftarrow v+w\)，有 \(2\not\mid w\)。\(w\) 变成新的最大的奇数，\(v\leftarrow w\)。
  • \(v<w\)。那么此时 \(v\leftarrow v+w\)，有 \(v>w\)，随后 \(w\leftarrow v+w\)，有 \(2\not\mid w\)。\(w\) 变成新的最大的奇数，\(v\leftarrow w\)。

但是上面的贪心策略其实是错误的。发现 \(v<w\) 的时候所有未取到的偶数均 \(\ge v\)。因此直接对做大的 \(w\) 做交换，剩下的全部变为 \(v\ge w\) 的情况。时间复杂度为 \(O(n\log n)\)，瓶颈在于排序。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define pb emplace_back
#ifdef __unix__
#define getchar getchar_unlocked
#else
#define getchar _getchar_nolock
#endif
#define int long long
using namespace std;
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')w=-w;
        ch=getchar();
    }
    while(isdigit(ch))
        s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
void read(int &x){
    int s=0,w=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')w=-w;
        ch=getchar();
    }
    while(isdigit(ch))
        s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    x=s*w;
}
template<typename...argme>
void read(int &x,argme &...vv){
    read(x),read(vv...);
}
const int N=1000100;
int a[N];
signed main(){
    int T=read();
    while(T--){
        int n=read();
        for(int i=1;i<=n;++i)a[i]=read();
        int cnt=0;
        for(int i=1;i<=n;++i)if(a[i]%2!=a[1]%2){cnt=1;break;}
        if(!cnt)cout<<"0\n";
        else{
            sort(a+1,a+n+1);
            int val;
            for(int i=1;i<=n;++i)
                if(a[i]&1)val=a[i];
            int cnt=0;
            for(int i=1;i<=n;++i)
                if(~a[i]&1){
                    if(val>=a[i]){
                        ++cnt;
                        a[i]+=val;
                        val=a[i];
                    }
                    else{
                        int p=n;
                        for(int j=n;j;--j)
                            if(~a[j]&1){
                                p=j;
                                break;
                            }
                        val+=a[p];
                        ++cnt,++cnt;
                        a[p]+=val;
                        val=a[p];
                        --i;
                    }
                }
            cout<<cnt<<'\n';
        }
    }
}

C

对 \(a_i\bmod 2m\) 破换成链。则若某一段区间的极差不超过 \(m\) 则有解，否则无解。有解的部分取最大值。问题在于怎么计算最大值为多少。

可以发现大体上就是解一个方程组：

\[\left\{ \begin{aligned} &\quad x\ge \text{MAX}\\ &\quad x\equiv V_i(\bmod 2m) \end{aligned} \right. \]

其中 \(\text{MAX}\) 表示所有 \(a_i\) 的最大值即所有芯片全部安装的最小时间，\(V_i\) 表示当前所枚举区间的终点。

求 \(x\) 的最小值可以：

\[\left\{ \begin{aligned} &\quad x\ge \text{MAX}\\ &\quad x+2Qm=V_i \end{aligned} \right. \]

其中 \(Q\in\textbf{Z}\)。

方程可以解得 \(x_\text{min}=2m\times \lceil\frac{\text{MAX}-V_i}{2m}\rceil+V_i\)。直接带进去求最大值即可。

时间复杂度为 \(O(n\log n)\)。瓶颈同样在于排序。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define pb emplace_back
#ifdef __unix__
#define getchar getchar_unlocked
#else
#define getchar _getchar_nolock
#endif
#define int long long
using namespace std;
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')w=-w;
        ch=getchar();
    }
    while(isdigit(ch))
        s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
void read(int &x){
    int s=0,w=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')w=-w;
        ch=getchar();
    }
    while(isdigit(ch))
        s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    x=s*w;
}
template<typename...argme>
void read(int &x,argme &...vv){
    read(x),read(vv...);
}
const int N=1000100;
int a[N];
signed main(){
    int T=read();
    while(T--){
        int n=read(),m=read();
        for(int i=1;i<=n;++i)a[i]=read();
        vector<int>v;
        sort(a+1,a+n+1);
        for(int i=1;i<=n;++i)v.pb(a[i]%(m+m));
        sort(v.begin(),v.end());
        int mx=*max_element(a+1,a+n+1);
        int res=-1;
        if(v.back()-v[0]<m){
            //mod 2m 同余 v.back()
            //且>=mx
            res=max(res,((mx-v.back()+m+m-1)/(m+m))*(m+m)+v.back());
        }
        for(int i=1;i<v.size();++i){
            //从v[i]到v[i-1]+m+m
            int cho=v[i-1]+m+m-v[i]+1;
            if(cho<=m){
                //mod 2m 同余 v[i-1]
                //且>=mx
                res=max(res,((mx-v[i-1]+m+m-1)/(m+m))*(m+m)+v[i-1]);
                // cout<<i-1<<": "<<(mx-v[i-1]+m+m-1)/(m+m)<<'\n';
                // int rres=mx-v[i-1];
                // rres=(rres+m+m-1)/(m+m);
                // res=max(res,rres);
            }
        }
        cout<<res<<'\n';
    }
}

D

考虑经典套路二分答案 \(p\)。问题变为判定中位数为 \(p\) 是否可行。

考虑判定的时候 dp。定义 \(a_i\ge p\) 的时候 \(a_i\) 权值为 \(1\)，否则权值为 \(-1\)。令 \(f_i\) 表示前 \(i\) 个元素权值之和最大是多少（需要在数量合法的前提下）。定义 \(V_i\) 表示 \(i\) 点权值。

因此有初始条件 \(f_0=0\)。然后考虑每一个 \(i\)：若 \(i-1\equiv 0(\bmod k)\) 则此时不可以从前面一个元素转移过来，只能往前跳 \(k\) 个元素。因此有 \(f_i\leftarrow f_{i-k}\)。否则既可以往前跳 \(k\) 个元素也可以直接从上一个元素转移过来，有 \(f_i\leftarrow\max(f_{i-1}+V_i,f_{i-k})\)。只需要判定 \(f_n\) 是否 \(\ge 0\) 即可。时间复杂度为 \(O(n\log n)\)。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define pb emplace_back
#ifdef __unix__
#define getchar getchar_unlocked
#else
#define getchar _getchar_nolock
#endif
using namespace std;
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')w=-w;
        ch=getchar();
    }
    while(isdigit(ch))
        s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
void read(int &x){
    int s=0,w=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')w=-w;
        ch=getchar();
    }
    while(isdigit(ch))
        s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    x=s*w;
}
template<typename...argme>
void read(int &x,argme &...vv){
    read(x),read(vv...);
}
const int N=1000100;
int a[N],n,k,f[N],g[N];
bool check(int p){
    //需要有至少Q/2+1个数>=p
    f[0]=0;g[0]=0;
    int Q=n%k;if(!Q)Q=k;
    // for(int i=1;i<=k;++i)g[i]=-1e9;
    for(int i=1;i<=n;++i)f[i]=-1e9;
    for(int i=1;i<=n;++i)if(a[i]>=p){
        if((i-1)%k==0){
            if(i-k>=0)f[i]=max(f[i-k],1);
            else f[i]=1;
        }else{
            if(i-k>=0)
                f[i]=max(f[i-1]+1,f[i-k]);
            else
                f[i]=f[i-1]+1;
        }
    }else{
        if((i-1)%k==0){
            if(i-k>=0)f[i]=max(f[i-k],-1);
            else f[i]=-1;
        }else{
            if(i-k>=0)
                f[i]=max(f[i-1]-1,f[i-k]);
            else
                f[i]=f[i-1]-1;
        }
    }
    // for(int i=1;i<=n;++i)if(a[i]>=p){
    //     f[i]=g[(i-1+k)%k]+1;
    //     g[i%k]=max(g[i%k],f[i]);
    // }
    return f[n]>0;
}
signed main(){
    int T=read();
    while(T--){
        n=read(),k=read();
        for(int i=1;i<=n;++i)a[i]=read();
        int l=1,r=1e9,best=-1;
        while(l<=r){
            int mid=l+r>>1;
            if(check(mid))best=mid,l=mid+1;
            else r=mid-1;
        }
        printf("%d\n",best);
    }
}

F1

考虑忘了是哪一场远古 CF 的一个题套路，每 \(2w\) 行 \(2h\) 列即为一个循环。因此开一个 map 记录出第一次操作每一个位置走到过的次数。然后考虑枚举 \(k\) 次不同的走法。每一次直接使用公式计算出其所对应的起点并更新答案即可。

设第一次结束之后位于坐标 \((x,y)\) 那么第 \(i\) 轮的起点即为 \((-(i-1)x\bmod 2w,-(i-1)y\bmod 2h)\)。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define pb emplace_back
#ifdef __unix__
#define getchar getchar_unlocked
#else
#define getchar _getchar_nolock
#endif
#define int long long
using namespace std;
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')w=-w;
        ch=getchar();
    }
    while(isdigit(ch))
        s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
void read(int &x){
    int s=0,w=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')w=-w;
        ch=getchar();
    }
    while(isdigit(ch))
        s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    x=s*w;
}
template<typename...argme>
void read(int &x,argme &...vv){
    read(x),read(vv...);
}
const int N=1000100;
int a[N],n,k,f[N],g[N];
signed main(){
    int T=read();
    while(T--){
        int n,k,w,h;read(n,k,w,h);
        string s;cin>>s;
        map<pair<int,int>,int>mp;
        int x=0,y=0;
        for(int i=0;i<n;++i){
            if(s[i]=='L')--x;
            else if(s[i]=='R')++x;
            else if(s[i]=='U')++y;
            else --y;
            x=(x+w+w)%(w+w);
            y=(y+h+h)%(h+h);
            ++mp[{x,y}];
        }
        int res=0;
        for(int i=0;i<k;++i){
            int _x=(-i*x%(w+w)+(w+w))%(w+w);
            int _y=(-i*y%(h+h)+(h+h))%(h+h);
            res+=mp[{_x,_y}];
        }
        cout<<res<<'\n';
    }
}

标签：F1,ch,963,int,read,补题,define,getchar
From： https://www.cnblogs.com/yhbqwq/p/18342560

相关文章

  • 基于stm32f103c8t6的蓝牙小车（可以控制车速，以及有数码管显示速度）
    蓝牙模块的理解：蓝牙可以理解为一个无线的串口，手机和单片机之间可以通过蓝牙来发送数据，控制单片机IO口，进而来控制小车，总体的逻辑是，手机发送数据给蓝牙，蓝牙将这个数据再发送给单片机。另外蓝牙的代码跟我们学的串口通信差不多。usart2.c#include"usart2.h" voiduart......
  • 边分治维护强连通分量（CF1989F，P5163）
    这里的边分治和树上的点分治边分治不一样，是维护强连通分量用的，每条边有一个出现时间，通过将每条边按连通关系分流重新排列，从而维护每个时间点整张图的连通性。具体的，这个算法是维护这样的一类问题：n个点，m条边按时间顺序依次加入，每加入一条边，你需要回答一些问题，比如在这个时间点......
  • CF1995D-状态压缩
    CF1995D-状态压缩大致题意你是一名语言学家，正在研究一种神秘的古代语言。你知道它的单词只由拉丁字母的前c个字母组成。每个单词都有一个大小写，可以通过其最后一个字母明确地确定(不同的字母对应不同的大小写)。例如，单词"ABACABA"和"ABA"(如果存在的话)在该语言中具有相......
  • AtCoder Beginner Contest 365 补题记录（A~E，G）
    Perf2000+，但是补不回来上场超低的Rating/llA#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;signedmain(){intn;cin>>n;if(n%400==0)cout<<"366\n";elseif(n%100==0)cout<<"365\n";......
  • CF1946F Nobody is needed 题解
    Nobodyisneeded推销我的洛谷博客。题意多组数据。给定一个长度为\(n\)的排列\(a\)，你需要回答\(q\)组询问，每组询问给出\(l,r\)，求有多少个子序列\(t\)使得：\(l\leqslantt_1<t_2<\cdots<t_k\leqslantr\)。\(a_{t_i}|a_{t_{i+1}}(1\leqslanti<k)\)......
  • 18963 最大数字
    这个问题可以使用贪心算法来解决。我们需要定义一个新的比较函数，对于两个数字a和b，如果ab>ba，那么我们就说a大于b。然后我们将所有的数字按照这个新的比较函数进行排序，然后将排序后的数字拼接起来，就可以得到最大的数字。以下是C++代码实现：#include<iostream>#include<vec......
  • 2024牛客暑期多校训练营5赛后补题
    2024牛客暑期多校训练营5赛后补题B.珑题意：若干2×12\times12×1的多米诺骨牌去填充......
  • 2024牛客暑期多校训练营6赛后补题
    2024牛客暑期多校训练营6赛后补题B.Cake2题意：一块正n边形的蛋糕，沿着iii和i+......
  • CF1883E+CF1995C-对数+贪心
    CF1883E+CF1995C对数+贪心CF1883ELookBack大致题意给你一个整数数组$a_1,a_2,…,a_n$。你需要用最少的运算次数使数组不递减。在一次操作中，您需要执行以下操作：选择一个索引\(1\leqi\leqn\)、设置$a_i=a_i⋅2$.数组\(b_1,b_2,…,b_n\)在所有$1\leqi\l......
  • 题解：CF1537E2 Erase and Extend (Hard Version)
    CF1537E2EraseandExtend题解分析通过观察题目，可以证明结果一定是由多次前缀复制得来的。题目要求你进行删和复制的操作，与其交替着操作，不如直接先删到最优的前缀再进行复制。现在就是要找最优的前缀。从头一位一位往后遍历。用\(l\)来存储目前最优前缀的长度，第\(i\)位......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99