首页 > 其他分享 >Codeforces Round 867 (Div. 3)

Codeforces Round 867 (Div. 3)

时间：2023-04-27 20:36:28浏览次数：50  
标签：typedef const int ll Codeforces 867 cin cnt Div

Codeforces Round 867 (Div. 3)

A - TubeTube Feed

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=50+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;

int q,n,t,a[N],b[N];

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>q;
    while(q--){
        cin>>n>>t;
        for(int i=1;i<=n;++i)cin>>a[i];
        for(int i=1;i<=n;++i)cin>>b[i];
        int s=0,ma=0,p=-1;
        for(int i=1;i<=n;++i){
            if(s+a[i]<=t){
                if(b[i]>ma){
                    ma=b[i];p=i;
                }
            }
            s++;
        }
        cout<<p<<'\n';
    }
    return 0;
}
View Code

 

B - Karina and Array

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;

ll t,n,a[N];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=0;i<n;++i)cin>>a[i];
        sort(a,a+n);
        ll x=a[0]*a[1],y=a[n-1]*a[n-2];
        cout<<max(x,y)<<'\n';
    }
    return 0;
}
View Code

 

C - Bun Lover

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;

ll t,n;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        ll s=n*n+2*n+2;
        cout<<s<<'\n';
    }
    return 0;
}
View Code

 

D - Super-Permutation

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;

int t,n;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--) {
        cin>>n;
        if(n==1)cout<<1<<'\n';
        else if(n%2)cout<<-1<<'\n';
        else{
            int l=n,r=1,p=n/2;
            while(p--){
                cout<<l<<' ';l-=2;
                cout<<r<<' ';r+=2;
            }cout<<"\n";
        }
    }
    return 0;
}
View Code

 

E - Making Anti-Palindromes

思路：分类讨论，奇数和某种字母个数超过n/2的不行，否则交换有两种：a.回文对与回文对，b.回文对与非回文对；显然优先进行a；

判断回文对中出现次数的最大值ma，若ma大于总回文对数的一半，则交换ma次，否则直接回文对两两互换，交换总回文对数/2（上取）

 

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;

int t,n,a[30],b[30];
string s;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--) {
        cin>>n;
        cin>>s;
        memset(a,0,sizeof a);
        memset(b,0,sizeof b);
        int ma=0,cnt=0,mma=0;
        if(n%2)cout<<-1<<'\n';
        else{
            for(int i=0;i<n;++i){
                a[s[i]-'a']++;
                ma=max(ma,a[s[i]-'a']);
                if(i<n/2){
                    if(s[i]==s[n-i-1]){
                        cnt++;
                        b[s[i]-'a']++;
                        mma=max(mma,b[s[i]-'a']);
                    }
                }
            }
            if(ma>n/2)cout<<-1<<'\n';
            else{
                int s=max(mma,(int)ceil(1.0*cnt/2));
                cout<<s<<'\n';
            }
        }
    }
    return 0;
}
View Code

 

F - Gardening Friends

思路：找到直径的两端点p，q，根节点到树上任意一点的最远路径一定过p或q，求出1，p，q到每个点最短路即可算出最大收益

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=1e6+5,INF=0x3f3f3f3f,Mod=1e6,S=1e6;

const double eps=1e-6;
typedef long long ll;
ll t,n,k,c;

auto bfs(vector<vector<int>>ve,int u){
    vector<ll>d(n+1,-1);
    queue<int>q;
    q.push(u),d[u]=0;
    while(q.size()){
        int v=q.front();q.pop();
        for(auto w:ve[v]){
            if(d[w]!=-1)continue;
            d[w]=d[v]+1;q.push(w);
        }
    }
    return d;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>k>>c;
        vector<vector<int>>ve(n+1);
        for(int i=0,x,y;i<n-1;++i){
            cin>>x>>y;
            ve[x].push_back(y),ve[y].push_back(x);
        }
        auto d1=bfs(ve,1);
        int p= max_element(d1.begin(),d1.end())-d1.begin();
        auto d2=bfs(ve,p);
        int q=max_element(d2.begin(),d2.end())-d2.begin();
        auto d3=bfs(ve,q);
        ll res=0;
        for(int i=1;i<=n;++i){
            res=max(res,max(d2[i],d3[i])*k-d1[i]*c);
        }
        cout<<res<<'\n';
    }
    return 0;
}
View Code

 

G1 - Magic Triples (Easy Version)

思路：ai，aj=b*ai，ak=b*b*ai，枚举ai和b可以求出总个数，b的范围为1e3

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=1e6+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;
ll t,n,cnt[N];
int main(){
    cin>>t;
    while(t--){
        set<ll>se;
        ll x;
        cin>>n;
        for(int i=0;i<n;++i){
            cin>>x;
            se.insert(x);cnt[x]++;
        }
        ll res=0;
        for(auto v:se){
            if(cnt[v]>=3)res+=(cnt[v]*(cnt[v]-1)*(cnt[v]-2));
            for(int b=2;b*b*v<=*se.rbegin();++b){
                res+=(cnt[v]*cnt[v*b]*cnt[v*b*b]);
            }
        }
        for(auto v:se)cnt[v]=0;
        cout<<res<<'\n';
    }
    return 0;
}
View Code

 

G2 - Magic Triples (Hard Version)

思路：可以枚举aj，那么 ai=aj/b，aj，ak=aj*b，ai和b为aj的因子，那就枚举aj所有因子，复杂度为aj开根号，暴力枚举会超；

方法：当aj<S，枚举因子，否则暴力枚举，可知当S取1e6时，复杂度为1e3

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=1e6+5,INF=0x3f3f3f3f,Mod=1e6,S=1e6;

const double eps=1e-6;
typedef long long ll;
int t,n;
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        map<ll,ll>cnt;

        for(int i=0;i<n;++i){
            ll x;
            cin>>x;
            cnt[x]++;
        }
        ll res=0;
        for(auto [x,y]:cnt){
            res+=y*(y-1)*(y-2);
            if(x<S){
                vector<ll>f;
                for(int i=1;i<=x/i;++i){
                    if(x%i)continue;
                    f.push_back(i);
                    if(x/i!=i)f.push_back(x/i);
                }
                for(auto v:f){
                    if(v==1)continue;
                    if(v*x>cnt.rbegin()->first)continue;
                    if(cnt.count(x/v)&&cnt.count(x*v))
                        res+=cnt[x/v]*cnt[x*v]*y;
                }
            }
            else{
                for(int b=2;b*x<=cnt.rbegin()->first;++b){
                    if(x%b==0&&cnt.count(x/b)&&cnt.count(x*b))
                        res+=cnt[x/b]*cnt[x*b]*y;
                }
            }
        }
        cout<<res<<'\n';

    }
    return 0;
}
View Code

 

标签：typedef,const,int,ll,Codeforces,867,cin,cnt,Div
From： https://www.cnblogs.com/bible-/p/17360123.html

相关文章

  • js javascript 鼠标触碰select下拉列表渐变出div层,鼠标离开渐变缩回
    <!DOCTYPEhtmlPUBLIC"-//W3C//DTDXHTML1.0Transitional//EN""http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><htmlxmlns="http://www.w3.org/1999/xhtml"><head><metahttp-equiv="Content-......
  • Codeforces Round 866 (Div. 1) C. The Fox and the Complete Tree Traversal （构造）
    传送门题目大意：  给定一个有n个点的树，我们可以任意选择一个点作为起点，这个点可以跳到跟自己距离为1或者距离为2的点，已经到达的点不能再到达（最终必须回到起点），询问是否存在一种方案可以从一个点出发经过所有的点最终再回到这个点来。  输入一个整数n。紧接着输入n-1条边。大......
  • Codeforces Round 847 (Div. 3) G.Tokens on Graph （构造）
    传送门题目大意  给定一个无向图，我们定义图中有四种点，一种是黑色的点表示终点，并且黑色的点始终是1号点，一种是红色的点，一种是灰色的点，最后一种就是没有颜色的点。  游戏规则：我们必须移动任意一个灰色的点到相邻的点上，如果灰色的点移动到了红色的点上，那么我们可以移动其他灰......
  • 前端隐藏和显示div的方式js和beetle：
    方式一：设置元素style对象中的display属性1、vart=document.getElementById('demo');//选取id为test的div元素2、t.style.display='none';//隐藏选择的元素3、t.style.display='block';//以块级样式显示方式二：设置元素style对象中的visibility属性1、vart=documen......
  • 让CSS里div上下左右绝对居中几种方式
    1、绝对定位（常用于登录模块）备注：前提条件div需要有宽高1<divclass="box"></div>2#css3.box{4position:absolute/fixed;5left:0;6right:0;7top:0;8bottom:0;9margin:auto;10}2、margin负值备注：前提条件div需要有宽高1<divclass="box"&g......
  • Codeforces Round 867 (Div. 3)
    A.TubeTubeFeed#include<bits/stdc++.h>usingnamespacestd;intmain(){intq;cin>>q;while(q--){intn,t,res=-1,id=-1;cin>>n>>t;vector<int>a(n+1),b(n+1);......
  • Educational Codeforces Round 147 (Rated for Div. 2)
    Preface补题这周比赛挺少，不过后面可能就很少有时间补以前的比赛了的说现在除了要做学校的集训专题外，还要刷一下蓝桥杯国赛的题，可以说是很忙碌了而且由于JAVA的期末考试要来了，为了熟悉下语法以后补题的时候前面的题目可能会用JAVA来写（其实我写的JAVA看起来和C++真没啥区别）A.......
  • B. Equalize by Divide - 贪心+思维+构造+数学+排序
    题意：给定一个数组，可以进行任意多次以下操作：1.选择第i和第j个数。2.使a[i]=a[i]/a[j]（向上取整）。不可以插入或者删减数组元素，求多少次使数组元素都相同，输出次数以及每次操作的两个下标i,j；如果无法实现输出-1.分析：数组中存在1一定无法实现，或者数组元素都相......
  • Codeforces 1781G - Diverse Coloring（构造）
    vp时候想到大致思路了，但是死活调不对，赛后套取cf的数据调了好久才过/ll首先直觉告诉我们答案不会太大。稍微猜一猜可以猜出除了四个点的菊花之外答案都是\(n\bmod2\)，下面我们来通过构造证明这件事情。首先，链的情况是trivial的，直接根据奇偶性间隔染色即可。如果不是链，那么......
  • Educational Codeforces Round 147(A~E)(补提记录)
    EducationalCodeforcesRound147(RatedforDiv.2)A:题意：每个问号都能被替换成0~9，求替换每个问号后所能的到的数的数量注：所得到的序列不能有前导0思路：先判断第一位是什么，作为特判，为0，则不能得到任何数输出0，为？则答案×9再依次枚举之后的每一个数，若为问号答案*10#include<io......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99