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

Codeforces Round 909 (Div. 3)

时间：2024-02-08 16:56:03浏览次数：29  
标签：int 909 Codeforces long cin solve Div define left

题目链接

A.

若n是3的倍数，那么输出第二，因为不管先手如何操作，后手只要跟先手出的相反那么先手就永远不会赢
其他情况，先手都能赢

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+10;

void solve() {
    int n;cin>>n;
    if((n+1)%3==0||(n-1)%3==0)cout<<"First\n";
    else cout<<"Second\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int left=1;
    cin>>left;
    while(left--){
        solve();
    }
}

B.

暴力枚举

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+10;

#define inf 0x3f3f3f3f3f3f3f3f
void solve() {
    int n;cin>>n;
    vector<int>a(n+1),pre(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pre[i]=pre[i-1]+a[i];
    }
    int ans=0;
    int t_mi=inf,t_ma=0;
    for(int i=1;i<n;i++){
        t_mi=inf,t_ma=0;
        if(n%i!=0)continue;
        for(int j=1;j+i-1<=n;j+=i){
            t_ma=max(t_ma,pre[j+i-1]-pre[j-1]);
            t_mi=min(t_mi,pre[j+i-1]-pre[j-1]);
        }
        ans=max(ans,abs(t_ma-t_mi));
    }
    cout<<ans<<'\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int left=1;
    cin>>left;
    while(left--){
        solve();
    }
}

C.

dp，其实和最大子序列和一样，只是加上奇偶性不能相邻这个限制即可

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+10;

#define inf 0x3f3f3f3f
void solve() {
    int n;cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    vector<int>dp(n+1);
    dp[1]=a[1];
    for(int i=2;i<=n;i++){
        if(abs(a[i])%2==0&&abs(a[i-1])%2==0||abs(a[i])%2==1&&abs(a[i-1])%2==1){
           // cout<<"i="<<i<<'\n';
            dp[i]=a[i];
        }
        else dp[i]=max({dp[i-1]+a[i],a[i]});
    }
    int ma=-inf;
    for(int i=1;i<=n;i++)ma=max(ma,dp[i]);
    cout<<ma<<'\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int left=1;
    cin>>left;
    while(left--){
        solve();
    }
}

D.

把式子化简，以2为底的指数形式，发现要让两个相等
需满足2^x/x == 2^y/y
指数是爆炸式增长，比一次函数快得多，发现只有1和2满足相等
其他必须相同才会相等

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+10;

#define inf 0x3f3f3f3f

void solve() {
    int n;cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    map<int,int>mp;
    int ans=0;
    for(int i=1;i<=n;i++){
        if(a[i]==1)ans+=mp[2];
        else if(a[i]==2)ans+=mp[1];
        ans+=mp[a[i]];
        mp[a[i]]++;
    }
    cout<<ans<<'\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int left=1;
    cin>>left;
    while(left--){
        solve();
    }
}

E.

若最小值在队头，那么它就会一直在队头，因为没有值比它更小
其他值经过操作都会去到自己应该在的位置
所以若第一个最小值后都是非降序的，那么最小操作次数就是第一个最小值前的数的个数

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+10;

#define inf 0x3f3f3f3f

void solve() {
    int n;cin>>n;
    vector<int>a(n+1);
    int mi=inf,id=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];mi=min(mi,a[i]);
    }
    int f=0;
    for(int i=2;i<=n;i++){
        if(a[i]>=a[i-1])continue;
        f=1;break;
    }
    if(f==0){
        cout<<0<<'\n';return ;
    }
    for(int i=1;i<=n;i++){
        if(a[i]==mi){
            id=i;break;
        }
    }
    f=0;
    for(int i=id;i<n;i++){
        if(a[i]<=a[i+1])continue;
        f=1;break;
    }
    if(f){
        cout<<-1<<'\n';return ;
    }
    cout<<id-1<<'\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int left=1;
    cin>>left;
    while(left--){
        solve();
    }
}

F.

最优的构造方法就是一条单链，因为这样的路径最长
把n号节点作为移动节点，记录链接它的是谁
需要m的路径就把n号节点移动到m号节点上
若n号节点本来就链接的m号节点就是-1

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+10;

#define inf 0x3f3f3f3f

void solve() {
    int n,q;cin>>n>>q;
    for(int i=1;i<n;i++)cout<<i<<' '<<i+1<<'\n';
    int last=n-1;
    for(int i=1;i<=q;i++){
        int d;cin>>d;
        if(last==d){
            cout<<"-1 -1 -1\n";
            continue;
        }
        cout<<n<<' '<<last<<' '<<d<<'\n';
        last=d;
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int left=1;
    cin>>left;
    while(left--){
        solve();
    }
}

G.

可以将树上的顶点编号改成对应排列的数组下标
这样使毫无顺序的区间有了顺序
维护每个节点的后代，用set去二分找答案
把询问离线
一个优化：找重儿子，其他的暴力merge合并

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+10;
#define inf 0x3f3f3f3f

int n,q;
void solve() {
    cin>>n>>q;
    vector<pair<int,int>>e(n-1);
    for(auto &[u,v]:e)cin>>u>>v;
    vector<int>p(n+1);
    for(int i=0;i<n;i++){
        int x;cin>>x;p[x]=i;
    }
    vector<vector<int>>g(n);
    for(auto &[u,v]:e){
        g[p[u]].emplace_back(p[v]);
        g[p[v]].emplace_back(p[u]);
    }
    vector<vector<tuple<int,int,int>>>w(n);
    vector<bool>b(q);
    for(int i=0;i<q;i++){
        int l,r,x;cin>>l>>r>>x;
        w[p[x]].emplace_back(l-1,r-1,i);
    }
    vector<set<int>>s(n);
    function<void(int,int)>dfs=[&](int u,int f){
        int h=u;
        for(int i:g[u]){
            if(i!=f){
                dfs(i,u);
                if(s[i].size()>s[h].size())h=i;
            }
        }
        if(h!=u)s[u].swap(s[h]);
        for(int i:g[u]){
            if(i!=f&&i!=h)s[u].merge(s[i]);
        }
        s[u].emplace(u);
        for(auto [l,r,i]:w[u]){
            if(auto p=s[u].lower_bound(l);p!=s[u].end()&&*p<=r)b[i]=true;
        }
    };
    dfs(p[1],p[1]);
    for(bool i:b)cout<<(i?"YES\n":"NO\n");
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int left=1;
    cin>>left;
    while(left--){
        solve();
    }
}

标签：int,909,Codeforces,long,cin,solve,Div,define,left
From： https://www.cnblogs.com/wwww-/p/18009618

相关文章

  • Codeforces-Round-917
    比赛链接A.LeastProduct假如序列中有\(0\)，那么答案是\(0\)。否则如果有奇数个负数，只需要让每个数的绝对值最大：不操作是最优的。否则如果有偶数个负数，乘积只会\(\ge0\)，为了达到最小值\(0\)，只需要将任意一个数改成\(0\)。时间复杂度\(\mathcal{O}(n)\)。codeforA......
  • Codeforces-Pinely-Round-3
    比赛链接A.DistinctButtons扣掉一个方向就是只能走到相邻两个象限以及和这两个象限相邻的坐标轴上，判一下是不是所有的点都满足就行。判的时候只需要判是否所有\(x\le0\)(落到二、三象限)，或者所有\(x\ge0\)(四、一象限)，或者所有\(y\le0\)或者所有\(y\ge0\)就行，......
  • Codeforces Round 923 (Div. 3)
    CodeforcesRound923(Div.3)A-MakeitWhite分析在字符串中找到第一个B的位置l和最后一个B的位置r,打印r-l+1即可如果找不到B打印-1code#include<bits/stdc++.h>#defineintlonglong#defineyescout<<"YES"<<'\n'#defineno cout<<"NO"......
  • Codeforces Round 921 (Div. 2)
    https://codeforces.com/contest/1925恶心round，从C题开始每题都是一眼看出做法但是细节挺多的题，烦的一比。A.WeGotEverythingCovered!*800给定\(n,k\)，若所有长度为\(n\)且仅由字母表中前\(k\)个小写字母组成的串都是\(s\)的子序列，则称\(s\)是"EverythingCover......
  • Codeforces Round 923 (Div. 3)(A~F)
    目录ABCDEFA#include<bits/stdc++.h>#defineintlonglong#definerep(i,a,b)for(inti=(a);i<=(b);++i)#definefep(i,a,b)for(inti=(a);i>=(b);--i)#definepiipair<int,int>#definepllpair<longlong,longlong>#de......
  • Codeforces-Hello-2024-Round
    比赛链接A.WalletExchange签到，某个人操作的时候只要一方有金币就行，所以最终赢的应该是拿到最后一个硬币的人，当\(a+b\equiv1\pmod2\)的时候Alice获胜，否则Bob获胜。时间复杂度\(\mathcal{O}(1)\)。codeforA#include<bits/stdc++.h>usingnamespacestd;inli......
  • CF1401E Divide Square 题解
    解题思路其实多看几组也能发现块数等于交点的数量加上两个端点都在边上的线段数量再加一。证明如下（图见样例）：对于两条只有一个端点位于边上的线段，因为保证有一个端点位于边上，那么这两条线段的交点一定会和已存在的点、边构成一个新的矩形；对于其中有一条为两个端点均位于边上的......
  • Codeforces Round 920 (Div. 3)（A~F）
    目录ABCDEFA按题意模拟即可#include<bits/stdc++.h>#defineintlonglong#definerep(i,a,b)for(inti=(a);i<=(b);++i)#definefep(i,a,b)for(inti=(a);i>=(b);--i)#definepiipair<int,int>#definepllpair<longlong,longlong......
  • Codeforces div2 C题补题
    Codeforcesdiv2C题补题1922C.ClosestCitiesC.ClosestCities很容易看出，端点的两个城市的最近城市就是他的直接后继和直接前驱，而中间的城市的最近城市就是他前驱和后继中距离绝对值最小的那个，因此我们可以先预处理出每个城市对应的最近城市，用map存储。然后因为区间可以从......
  • 从BigDecimal的divide的异常说起
    在过去做项目的某一天中，突然有小伙伴说两个BigDecimal的数据相除（divide）报错了，觉得不可能，然后问他是怎么编写的，他说很简单呀，就是new了2个BigDecimal，然后相除的结果赋值给另外一个BigDecimal对象。听起来觉得没有问题，正常来说，2个Integer(int)，2个Double(double）都不会报错，然后问是什么......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99