首页 > 其他分享 >cf1879 edu 做题记录

cf1879 edu 做题记录

时间：2023-09-25 18:12:55浏览次数：32  
标签：ch cf1879 记录 int void long write edu define

A

题面

判断有没有两维均大于等于第一个人的人即可。有就无解，否则答案为 \(s_1\)。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
int n,stx,sty;
void solve(){
    read(n);
    read(stx),read(sty);
    bool flag=1;
    for(int i=2,x,y;i<=n;i++){
        read(x),read(y);
        if(x>=stx&&y>=sty){
            flag=0;
        }
    }
    if(flag){
        write_endl(stx);
    }
    else{
        write_endl(-1);
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t;
    read(t);
    while(t--){
        solve();
    }
    return 0;
}

B

题面

容易发现，选择的一定是一行或一列，求所有行与列中答案最小的即可。

注意要开 long long。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=3e5+10;
int n,sum1,sum2,a[N],b[N],mn1,mn2;
void solve(){
    sum1=sum2=0;
    mn1=mn2=inf;
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
        sum1+=a[i];
        mn1=min(mn1,a[i]);
    }
    for(int i=1;i<=n;i++){
        read(b[i]);
        sum2+=b[i];
        mn2=min(mn2,b[i]);
    }
    write_endl(min(mn1*n+sum2,mn2*n+sum1));
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t;
    read(t);
    while(t--){
        solve();
    }
    return 0;
}

C

题面

推错式子，吃了两发罚时，好烦。

先算数量，将连续的相同的数缩成一块，假定第 \(i\) 块的大小为 \(s_i\)，答案 \(num=\sum s_i\)。

再算方案，因为每个连续段是分开的并不会相互影响，先删A块中的数再删B块中的数和反过来是两种方案，所以删除的数是可以任意排列。选出删除的数的方案为 \(\prod s_i\)，排列的方案为 \(num!\)，总方案数为 \(\prod s_i\times num!\)。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=2e5+10,mod=998244353;
string s;
int fac[N],inv[N];
int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1){
            res=res*a%mod;
        }
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void init(int mx){
    fac[0]=1;
    for(int i=1;i<=mx;i++){
        fac[i]=fac[i-1]*i%mod;
    }
    inv[mx]=qpow(fac[mx],mod-2);
    for(int i=mx-1;i>=0;i--){
        inv[i]=inv[i+1]*(i+1)%mod;
    }
}
void solve(){
    cin>>s;
    int num=1;
    vector<int>sum;
    for(int i=1;i<s.size();i++){
        if(s[i]!=s[i-1]){
            sum.pb(num);
            num=1;
        }
        else{
            num++;
        }
    }
    sum.pb(num);
    sort(sum.begin(),sum.end());
    int ans=1,res=0;
    for(auto x:sum){
        res+=x-1;
        ans*=x;
        ans%=mod;
    }
    write_space(res),write_endl(ans*fac[res]%mod);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    init(2e5);
    int t;
    read(t);
    while(t--){
        solve();
    }
    return 0;
}

D

题面

先做前缀和，令 \(s_i\) 表示 \(\oplus_{j=1}^i a_j\)，可得 \(ans=\sum\limits_{i=0}^n\sum\limits_{j=0}^{i-1}(s_i\oplus s_j)\times(i-j)\)

拆开 \(ans=\sum\limits_{i=0}^n\sum\limits_{j=0}^{i-1}(s_i\oplus s_j)\times i-\sum\limits_{j=0}^n\sum\limits_{i=j+1}^{n}(s_i\oplus s_j)\times j\)。

可以发现两个部分是等价的。算出前一个部分的贡献，再反过来做一遍求出后一个部分的贡献并将其减掉即可。拆到每一位，令 \(cnt_i\) 表示第 \(i\) 位有值的数的个数。对于 \(s_j\) 有值的位 \(i\)，贡献为 \((j-cnt_i)\times j\times 2^i\)，否则贡献为 \(cnt_i\times j\times 2^i\)。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=3e5+10,Lg=30,mod=998244353;
int n,a[N],s[N],cnt[Lg+5];
void solve(){
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
        s[i]=s[i-1]^a[i];
    }
    int ans=0;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=Lg;j++){
            if(s[i]>>j&1){
                ans=(ans+i*(i-cnt[j])%mod*(1<<j)%mod)%mod;
                cnt[j]++;
                continue;
            }
            ans=(ans+i*cnt[j]%mod*(1<<j)%mod)%mod;
        }
    }
    // cerr<<ans<<endl;
    for(int i=0;i<=Lg;i++){
        cnt[i]=0;
    }
    for(int i=n;i>=0;i--){
        for(int j=0;j<=Lg;j++){
            if(s[i]>>j&1){
                ans=(ans+mod-i*((n-i)-cnt[j])%mod*(1<<j)%mod)%mod;
                cnt[j]++;
                continue;
            }
            ans=(ans+mod-i*cnt[j]%mod*(1<<j)%mod)%mod;
        }
    }
    write_endl(ans);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

E

题面

被题意恶心到了，导致没有做出来本题。

简明题意：用尽量少的颜色将一棵树的边染色，并得到一个策略，使得无论给出与哪个点相连的边的染色情况，都根据策略选出一个颜色，且该颜色只有一条往根走的边。

给出结论，颜色数一定小于等于 \(3\)。因为不会其它证明，所以只给出构造性证明，即提供构造方法。

颜色数为 \(1\)：该图为菊花图。

颜色数为 \(2\)：所有 \(deg\) 等于 \(2\) 的点的深度模 \(2\) 的余数相同。颜色为 \(2\) 肯定是交替出现，对于度数为 \(2\) 的点肯定是要给出一个统一策略的，即所有度数为 \(2\) 的点的染色情况是一定的。

颜色数为 \(3\)：将深度模 \(3\) 的值视作到父亲的边的颜色，这时 \(deg\) 为 \(2\) 的点会划分为三种，\(cnt_1=cnt_2=1\)；\(cnt_2=cnt_3=1\)；\(cnt_1=cnt_3=1\)。对于这三种情况，每个情况都可以有唯一的方案去选择颜色，剩下的点直接找数量为 \(1\) 的颜色即可。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,fa[N],dep[N],sum=-1,ans[N];
vector<int>e[N];
bool flag=1;
void dfs(int u){
    if(e[u].size()==1){
        cerr<<u<<' '<<dep[u]<<endl;
        if(sum==-1){
            sum=(dep[u]-1)&1;
        }
        if(sum!=((dep[u]-1)&1)){
            flag=0;
        }
    }
    for(auto v:e[u]){
        dfs(v);
    }
}
void query(int u){
    for(auto v:e[u]){
        query(v);
    }
    if(sum<=0){
        ans[u]=((dep[u]-1)&1)+1;
    }
    else{
        ans[u]=(dep[u]&1)+1;
    }
}
signed main(){
    cin>>n;
    for(int i=2;i<=n;i++){
        cin>>fa[i];
        dep[i]=dep[fa[i]]+1;
        e[fa[i]].push_back(i);
        if(dep[i]>1){
            flag=0;
        }
    }
    if(flag){
        cout<<1<<endl;
        for(int i=2;i<=n;i++){
            cout<<1<<' ';
        }
        cout<<endl;
        int x;
        cin>>x>>x;
        cout<<1<<endl;
        return 0;
    }
    flag=1;
    for(auto v:e[1]){
        sum=-1;
        dfs(v);
        query(v);
    }
    if(flag){
        cout<<2<<endl;
        for(int i=2;i<=n;i++){
            cout<<ans[i]<<' ';
        }
        cout<<endl;
        while(1){
            int a,b,opt;
            cin>>opt;
            if(opt==1||opt==-1){
                break;
            }
            cin>>a>>b;
            if(a==1){
                cout<<1<<endl;
            }
            else{
                cout<<2<<endl;
            }
        }
        return 0;
    }
    cout<<3<<endl;
    for(int i=2;i<=n;i++){
        cout<<dep[i]%3+1<<' ';
    }
    cout<<endl;
    while(1){
        int opt,a,b,c;
        cin>>opt;
        if(opt==1||opt==-1){
            break;
        }
        cin>>a>>b>>c;
        if(c!=0&&b==1){
            cout<<2<<endl;
        }
        else if(a!=0&&c==1){
            cout<<3<<endl;
        }
        else if(b!=0&&a==1){
            cout<<1<<endl;
        }
        else if(a==1){
            cout<<1<<endl;
        }
        else if(b==1){
            cout<<2<<endl;
        }
        else if(c==1){
            cout<<3<<endl;
        }
    }
    return 0;
}

F

题面

题意：对于一个 \(t\)，令 \(b_i=\lceil\frac{a_i}{t}\rceil\times h_i\)，对于每个位置 \(i\)，其 \(b_i\) 为最大值时，\(b_i-b_{cmax}\) 的差的最大值，其中 \(cmax\) 表示次大值的位置。

枚举 \(t\in [0,\max a_i]\)，枚举 \(\lceil\frac{a_i}{t}\rceil\)，对应的权值是一段区间。因为只要求最大值和次大值，可以用 ST 表维护区间的权值对应的 \(h_i\) 最大值和次大值及对应位置。可以在 \(O(n\log n)\) 的复杂度求出最大值与次大值的值。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=2e5+10,Lg=20;
int n,lg[N],h[N],a[N];
struct node{
    pii mx,nxt;
}ST[N][Lg+5];
node merge(node x,node y){
    node z=node{max(x.mx,y.mx),max(x.nxt,y.nxt)};
    if(x.mx!=y.mx){
        z.nxt=max(z.nxt,min(x.mx,y.mx));
    }
    return z;
}
node query(int l,int r){
    return merge(ST[l][lg[r-l+1]],ST[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);
}
int ans[N];
void solve(){
    read(n);
    for(int i=1;i<=n;i++){
        read(h[i]);
    }
    int mx=0;
    for(int i=1;i<=n;i++){
        read(a[i]);
        mx=max(mx,a[i]);
        --a[i];
        ans[i]=0;
    }
    if(n==1){
        write_endl((a[1]+1)*h[1]);
        return;
    }
    for(int i=0;i<=mx;i++){
        ST[i][0]=node{mp(0,0),mp(0,0)};
    }
    for(int i=1;i<=n;i++){
        ST[a[i]][0]=merge(ST[a[i]][0],node{mp(h[i],i),mp(0,0)});
    }
    for(int i=1;i<=Lg;i++){
        for(int j=0;j+(1<<i)-1<=mx;j++){
            ST[j][i]=merge(ST[j][i-1],ST[j+(1<<(i-1))][i-1]);
        }
    }
    for(int i=1;i<=mx;i++){
        node res=node{mp(0,0),mp(0,0)};
        for(int j=1;(j-1)*i<=mx;j++){
            int l=(j-1)*i,r=j*i-1;
            r=min(r,mx);
            node x=query(l,r);
            x.mx.first*=j;
            x.nxt.first*=j;
            res=merge(res,x);
        }
        ans[res.mx.second]=max(ans[res.mx.second],res.mx.first-res.nxt.first);
    }
    for(int i=1;i<=n;i++){
        write_space(ans[i]);
    }
    putchar('\n');
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    lg[0]=-1;
    for(int i=1;i<N;i++){
        lg[i]=lg[i>>1]+1;
    }
    int t;
    read(t);
    while(t--){
        solve();
    }
    return 0;
}

标签：ch,cf1879,记录,int,void,long,write,edu,define
From： https://www.cnblogs.com/luoshen0/p/17728138.html

相关文章

  • abc321记录
    SuntoryProgrammingContest2023（AtCoderBeginnerContest321）-AtCoderD题意：给定常数\(k\)和长度为\(n\)的数组\(a\)和长度为\(m\)的数组\(b\)，求\(\sum_{i=1}^n\sum_{j=1}^mmin\{a_i+b_j,k\}\)。数据范围：\(n,m\le2\times10^5\)tag:二分前缀和枚举\(a_i\)，在......
  • ESXI6.7升级7.0u3过程记录
    ESXI6.7升级7.0u3过程记录对ESXI集群进行了EOS升级，从6.7升级至7.0u3，简单记录一下过程，方便以后回顾回溯。vCenter升级整个集群升级的过程中，需要对vc进行升级,VC是可以向下兼容的，先将6.7的vc升级到7.0，由7.0vc对6.7的ESXI主机进行管理。整个升级的过程也比较傻瓜式，对原VC打了内存......
  • 记录返回上一页滚动条的位置
    scrollBehavior可以记录滚动条位置,也可以自己设定滚动条位置constrouter=createRouter({//createRouter返回一个router实例history:createWebHistory(),scrollBehavior:(to,from,savePosition)=>{if(savePosition){returnsavePosition;......
  • Educational Codeforces Round 155 (Rated for Div. 2)
    EducationalCodeforcesRound155(RatedforDiv.2)A.Rigged!解题思路:若存在\(s[i]>=s[1]\)并且\(e[i]>=e[i]\),那么答案为\(-1\).否则，答案为\(s[1]\).代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;constintN=1e6+10;con......
  • 多通道振弦数据记录仪在预防地质灾害中的重要性
    多通道振弦数据记录仪在预防地质灾害中的重要性地质灾害是指在地表或岩体内部发生的、由地质原因引起的、对人类生命、财产和环境安全造成威胁或损害的各种灾害。地质灾害的预测和预防对于保障人民生命财产安全、维护社会稳定和可持续发展具有重要的意义。而多通道振弦数据记录仪......
  • JOISC做题记录
    题目真的很好！！！所以来写一写。但都是一句话题解，因为我实在很懒。打*的是没独立做出来的。慢慢补，不急2023Day1T1TwoCurrencies签到题。主席树上二分就行。$O((n+Q)\logn)$。*2023Day1T2FestivalsinJOIKingdom2还不会。2023Day1T3Passport走遍$1\simn$显然......
  • zTree使用记录
    <linkhref="zTree/zTreeStyle/zTreeStyle.css"rel="stylesheet"/><divid="treeDemo"class="ztree"></div><scriptsrc="zTree/jquery.ztree.all.js"type="text/javascript"><......
  • 文心一言——试用记录
    问题：你是一名专业的原画师，请画一幅坐在咖啡厅的少女给我当头像。     加入“性感”二字，生成失败：    保持关键词：咖啡厅、少年，生成的图片基本一样：请画一幅坐在咖啡厅的少女给我当头像     ==============================......
  • CF_EduRound155小丑寄
    一句话总结：A题理解错了，数据又水，所以寄了。过程：22:35开题。22:40怎么还没加载出来？？急急急22:42哦，严格大于，但是主宾对调了，乐乐乐乐乐乐乐，cout<<ans;\(\rightarrow\)cout<<ans-1;22:45一发过。。。22:45-23:38啥事没有。23:38开E题23:50左右好像有点思路......
  • Educational Codeforces Round 155 (Rated for Div. 2)
    比赛链接A.Rigged!题目链接就是一个比较简单的模拟就可以解决，如何判断能不能第一只需要考虑比他力量大的耐力是不是也比他大就行，而只要比他大，他就不可能第一，否则输出他的力量作为标杆就行，这样也可以避免比他力量小的也可以举起来。#include<bits/stdc++.h>usingnamespaces......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99