首页 > 其他分享 >Codeforces Round 971 (Div. 4) A-G1

Codeforces Round 971 (Div. 4) A-G1

时间：2024-09-04 13:03:31浏览次数：3  
标签：__ typedef G1 int Codeforces long cin Div define

A

b-a

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
#define int long long
typedef tuple<int,int,int> tp;
#define x first
#define y second
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
constexpr int N=200010,mod=1e9+7,inf=1e18;
constexpr double pi=3.1415926535897932384626,eps=1e-5;
const ll  P=rnd()%mod;
#define all(a) a.begin(),a.end()
#define get_count(x) __builtin_popcount(x)
#define fors(i,a,b) for(int i=a;i<=b;i++)
#define forr(i,a,b) for(int i=b;i>=a;i--)
#define pb(x) push_back(x)
int dx[]={0,1,0,-1,1,1,-1,-1,0};
int dy[]={1,0,-1,1,1,-1,-1,1,0};
int random(int l,int r){
    return rand()%r+l;
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int __=1;
    cin >> __;
    while(__--){
        int a,b;
        cin >> a >> b;
        int ans=inf;
        for(int c=a;c<=b;c++) ans=min(ans,c-a+b-c);
        cout << ans << '\n';
    }
    system("color 04");
    return 0;
}

B

模拟，从最后向前遍历找每行的第一个\(#\)记录列数，然后输出

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
#define int long long
typedef tuple<int,int,int> tp;
#define x first
#define y second
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
constexpr int N=200010,mod=1e9+7,inf=1e18;
constexpr double pi=3.1415926535897932384626,eps=1e-5;
const ll  P=rnd()%mod;
#define all(a) a.begin(),a.end()
#define get_count(x) __builtin_popcount(x)
#define fors(i,a,b) for(int i=a;i<=b;i++)
#define forr(i,a,b) for(int i=b;i>=a;i--)
#define pb(x) push_back(x)
int dx[]={0,1,0,-1,1,1,-1,-1,0};
int dy[]={1,0,-1,1,1,-1,-1,1,0};
int random(int l,int r){
    return rand()%r+l;
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int __=1;
    cin >> __;
    while(__--){
        int n,m=4;
        cin >> n;
        vector<vector<char>> g(n+1,vector<char>(m+1));
        fors(i,1,n){
            fors(j,1,m){
                cin >> g[i][j];
            }
        }
        vector<int> ans;
        forr(i,1,n){
            fors(j,1,m){
                if(g[i][j]=='#'){
                    ans.pb(j);
                }
            }
        }
        fors(i,0,ans.size()-1) cout << ans[i] << " \n"[i==ans.size()-1];
    }
    system("color 04");
    return 0;
}

C

如果最后一次x没到，y到了，仅需要一次 \((t-1)*2+1\)如果最后一次x到了，y没到，需要俩次 \(t*2\),t为到x或者y的步数最大值

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
#define int long long
typedef tuple<int,int,int> tp;
#define x first
#define y second
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
constexpr int N=200010,mod=1e9+7,inf=1e18;
constexpr double pi=3.1415926535897932384626,eps=1e-5;
const ll  P=rnd()%mod;
#define all(a) a.begin(),a.end()
#define get_count(x) __builtin_popcount(x)
#define fors(i,a,b) for(int i=a;i<=b;i++)
#define forr(i,a,b) for(int i=b;i>=a;i--)
#define pb(x) push_back(x)
int dx[]={0,1,0,-1,1,1,-1,-1,0};
int dy[]={1,0,-1,1,1,-1,-1,1,0};
int random(int l,int r){
    return rand()%r+l;
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int __=1;
    cin >> __;
    while(__--){
        int x,y,k;
        cin >> x >> y >> k;
        int a=(x+k-1)/k,b=(y+k-1)/k;
        int t=max(a,b);
        if(a>b){
            cout << (t-1)*2+1 << '\n';
        }
        else cout << t*2 << '\n';
    }
    system("color 04");
    return 0;
}

D

\(0<=x<=n,0<=y<=1\),可以枚举x的位置，组成直角三角形的点可以有，俩个点在同一列，其余各点都能组成直角三角形，一个点上面或者下面左右俩侧皆有点也可以组成直角三角形。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
#define int long long
typedef tuple<int,int,int> tp;
#define x first
#define y second
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
constexpr int N=200010,mod=1e9+7,inf=1e18;
constexpr double pi=3.1415926535897932384626,eps=1e-5;
const ll  P=rnd()%mod;
#define all(a) a.begin(),a.end()
#define get_count(x) __builtin_popcount(x)
#define fors(i,a,b) for(int i=a;i<=b;i++)
#define forr(i,a,b) for(int i=b;i>=a;i--)
#define pb(x) push_back(x)
int dx[]={0,1,0,-1,1,1,-1,-1,0};
int dy[]={1,0,-1,1,1,-1,-1,1,0};
int random(int l,int r){
    return rand()%r+l;
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int __=1;
    cin >> __;
    while(__--){
        int n;
        cin >> n;
        vector<vector<int>> a(2,vector<int>(n+1));
        fors(i,1,n){
            int x,y;
            cin >> x >> y;
            a[y][x]=1;
        }
        int ans=0;
        fors(i,0,n){
            if(a[0][i]&&a[1][i]){
                ans+=n-2;
            }
            if(i>=1&&i<=n-1){
                if(a[0][i]&&a[1][i+1]&&a[1][i-1]) ans++;
                if(a[1][i]&&a[0][i+1]&&a[0][i-1]) ans++;
            }
        }
        cout << ans << '\n';
    }
    system("color 04");
    return 0;
}

E

找到一个位置i分割俩侧，使得俩侧差绝对值最小，有俩种做法，一种是二元一次方程找根，一种是凸凹函数用三分。

二元一次方程

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
#define int long long
typedef tuple<int,int,int> tp;
#define x first
#define y second
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
constexpr int N=200010,mod=1e9+7,inf=1e18;
constexpr double pi=3.1415926535897932384626,eps=1e-5;
const ll  P=rnd()%mod;
#define all(a) a.begin(),a.end()
#define get_count(x) __builtin_popcount(x)
#define fors(i,a,b) for(int i=a;i<=b;i++)
#define forr(i,a,b) for(int i=b;i>=a;i--)
#define pb(x) push_back(x)
int dx[]={0,1,0,-1,1,1,-1,-1,0};
int dy[]={1,0,-1,1,1,-1,-1,1,0};
int random(int l,int r){
    return rand()%r+l;
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int __=1;
    cin >> __;
    while(__--){
        int n,k;
        cin >> n >> k;
        int a=2,b=2*(2*k-1),c=-n*(2*k+n-1);
//        cout << a << ' ' << b << ' ' << c << '\n';
        vector<int> r(2);
        auto get=[&](int a,int b,int c)->vector<int>{
            double t=(double)b*b-(double)4ll*a*c;
            vector<int> ans;
            if(t<0) return ans;
            int ts=sqrt(t);
//            cout << ts << '\n';
            ans.pb((ts-b)/(2*a));
            ans.pb((-b-ts)/(2*a));
            return ans;
        };
        r=get(a,b,c);
        auto sum=[&](int l,int r)->int{
            return (r-l+1)*(l+r)/2;
        };
        int ans=sum(k,k+n-1);
//        cout << r[0] << ' ' << r[1] << '\n';
        for(int i=0;i<2;i++){
            for(int j=r[i]-10;j<=r[i]+10;j++){
                if(j<1||j>n) continue;
                int x1=sum(k,k+j-1);
                int x2=sum(k+j,k+n-1);
                ans=min(ans,abs(x1-x2));
            }
        }
        cout << ans << '\n';
    }
    system("color 04");
    return 0;
}

三分

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
#define int long long
typedef tuple<int,int,int> tp;
#define x first
#define y second
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
constexpr int N=200010,mod=1e9+7,inf=1e18;
constexpr double pi=3.1415926535897932384626,eps=1e-5;
const ll  P=rnd()%mod;
#define all(a) a.begin(),a.end()
#define get_count(x) __builtin_popcount(x)
#define fors(i,a,b) for(int i=a;i<=b;i++)
#define forr(i,a,b) for(int i=b;i>=a;i--)
#define pb(x) push_back(x)
int dx[]={0,1,0,-1,1,1,-1,-1,0};
int dy[]={1,0,-1,1,1,-1,-1,1,0};
int random(int l,int r){
    return rand()%r+l;
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int __=1;
    cin >> __;
    while(__--){
        int n,k;
        cin >> n >> k;
        auto get=[&](int l,int r)->int{
            return (r-l+1)*(l+r)/2;
        };
        auto check=[&](int i)->int{
            return abs(get(k,k+i-1)-get(k+i,k+n-1));
        };
        int l=1,r=n;
        while(r-l>10){
            int m1=(2*l+r)/3;
            int m2=(l+2*r)/3;
            if(check(m1)<check(m2)) r=m2;
            else l=m1;
        }
        int ans=check(l);
        fors(i,l,r) ans=min(ans,check(i));
        cout << ans << '\n';
    }
    system("color 04");
    return 0;
}

F

一个小技巧破环成链前缀和，可以分为三部分来计算，完整的数组加上左右俩侧，sum+[l,L]+[R,r],算出[l,L]和[R,r]属于第几次偏移量进行前缀和即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
#define int long long
typedef tuple<int,int,int> tp;
#define x first
#define y second
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
constexpr int N=200010,mod=1e9+7,inf=1e18;
constexpr double pi=3.1415926535897932384626,eps=1e-5;
const ll  P=rnd()%mod;
#define all(a) a.begin(),a.end()
#define get_count(x) __builtin_popcount(x)
#define fors(i,a,b) for(int i=a;i<=b;i++)
#define forr(i,a,b) for(int i=b;i>=a;i--)
#define pb(x) push_back(x)
int dx[]={0,1,0,-1,1,1,-1,-1,0};
int dy[]={1,0,-1,1,1,-1,-1,1,0};
int random(int l,int r){
    return rand()%r+l;
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int __=1;
    cin >> __;
    while(__--){
        int n,q,sum=0;
        cin >> n >> q;
        // 开一个俩倍长度的前缀和
        vector<int> a(2*n+1),pre(2*n+1);
        fors(i,1,n) cin >> a[i],sum+=a[i],a[i+n]=a[i];
        fors(i,1,2*n) pre[i]=pre[i-1]+a[i];
        while(q--){
            int l,r;
            cin >> l >> r;
            int L=(l%n==0?l:l+(n-l%n));
            L=min(L,r);
            int R=(r%n==0?r:r-r%n+1);
            R=max(R,l);
//            cout << l << ' ' << L << ' ' << R << ' ' << r << '\n';
            int len=r-l+1;
            if(l%n==1) L=-1;
            if(r%n==0) R=-1;
            if(L!=-1){
                len-=(L-l+1);
            }
            if(R!=-1){
                len-=(r-R+1);
            }
            len=max(0ll,len);
            int k=len/n;
//            cout << "len=" << len << '\n';
//            cout << l << ' ' << L << ' ' << R << ' ' << r << '\n';
            int ans=k*sum;
//            cout << "First:ans " << ans << '\n';
            int i=(l+n-1)/n-1,j=(r+n-1)/n-1;
            int res=0;
            int pl=(l%n==0?n:l%n);
            int pr=(r%n==0?n:r%n);
            if(L!=-1){
                int pl=(l%n==0?n:l%n);
                int pr=(L%n==0?n:L%n);
//                cout << "L:" << pl << ' ' << pr << '\n';
                res+=pre[pr+i]-pre[pl+i-1];
            }
//            cout << "L " << res << '\n';
            if(R!=-1){
                int pl=(R%n==0?n:R%n);
                int pr=(r%n==0?n:r%n);
//                cout << "R:" << pl << ' ' << pr << '\n';
                res+=pre[pr+j]-pre[pl+j-1];
            }
//            cout << "R " << res << '\n';
            ans+=res;
            if(l==R&&L==r) ans-=res/2;
            cout << ans << '\n';
        }
    }
    system("color 04");
    return 0;
}

G1

给一个定长的子数组[l,r]求使得[l,r]为连续子数组的最小操作数。有一个小技巧，让\(ai=ai-i\) 就可以转换成区间众数问题，可以使用滑动窗口或者莫队来解决。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
#define int long long
typedef tuple<int,int,int> tp;
#define x first
#define y second
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
constexpr int N=200010,mod=1e9+7,inf=1e18;
constexpr double pi=3.1415926535897932384626,eps=1e-5;
const ll  P=rnd()%mod;
#define all(a) a.begin(),a.end()
#define get_count(x) __builtin_popcount(x)
#define fors(i,a,b) for(int i=a;i<=b;i++)
#define forr(i,a,b) for(int i=b;i>=a;i--)
#define pb(x) push_back(x)
int dx[]={0,1,0,-1,1,1,-1,-1,0};
int dy[]={1,0,-1,1,1,-1,-1,1,0};
int random(int l,int r){
    return rand()%r+l;
}
struct node{
    int l,r,id;
}e[N];
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int __=1;
    cin >> __;
    while(__--){
        int n,k,q;
        cin >> n >> k >> q;
        vector<int> a(n+1),alls;
        map<int,int> cnt,p;
        fors(i,1,n) cin >> a[i],a[i]-=i,alls.pb(a[i]);
        sort(all(alls));
        alls.erase(unique(all(alls)),alls.end());
        fors(i,1,n) a[i]=lower_bound(all(alls),a[i])-alls.begin()+1;
        fors(i,1,q){
            int l,r;
            cin >> l >> r;
            e[i]={l,r,i};
        }
        int len=sqrt(n),res=0;
        auto get=[&](int i)->int{
            return i/len;
        };
        auto cmp=[&](const node& a,const node& b)->bool{
            int i=get(a.l),j=get(b.l);
            if(i!=j) return i<j;
            if(i&1) return a.r<b.r;
            return a.r>b.r;
        };
        auto add=[&](int x)->void{
            cnt[++p[x]]++;
            res=max(res,p[x]);
        };
        auto del=[&](int x)->void{
            if(cnt[p[x]]==1&&p[x]==res) res--;
            cnt[p[x]--]--;
        };
        sort(e+1,e+q+1,cmp);
        vector<int> ans(q+1);
        for(int t=1,i=1,j=0;t<=q;t++){
            auto [l,r,id]=e[t];
            while(i<l) del(a[i++]);
            while(i>l) add(a[--i]);
            while(j<r) add(a[++j]);
            while(j>r) del(a[j--]);
            ans[id]=res;
        }
        fors(i,1,q) cout << max(0ll,k-ans[i]) << '\n';
        // 区间众数
    }
    system("color 04");
    return 0;
}

标签：__,typedef,G1,int,Codeforces,long,cin,Div,define
From： https://www.cnblogs.com/stability/p/18396241

相关文章

  • Educational Codeforces Round 169（A-D）
    A.ClosestPoint        给你一组点。你必须在这个集合中加入一个整数的点，使它与集合中现有的每一个点不同，并且它成为与集合中每一个点**最近的点。这可能吗？（输入yesorno）    一道思路题，简单思考可以发现，如果数字超过两个，那么这题答案就是NO。当两个数字的......
  • Codeforces Round 966 (Div. 3)
    ab略...C:map嵌套水过去的，复杂度\(nlog^2n\),感觉不如正解#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#definepiipair<int,int>#definemkpmake_pair#definefirfirst#definesecsecond#definepbpush_backconstintmaxn=2e5+100;......
  • 【杀戮尖塔】G1-铁甲战士 23 层
    获得火焰吐息。火焰吐息：抽到伤害或者诅咒时造成6点伤害。升级火焰吐息。火焰吐息+：抽到状态或者诅咒时造成10点伤害。略过。获得战吼。移除打击。升级战吼。战吼+：抽2放1，消耗。略过。获得盛怒、速度药水。67/80生命。盛怒：1费得2费，消耗。精致折扇。恢复生命80/......
  • Codeforces Round 970 (Div. 3)（VP）
    A.Sakurako'sExam总结：一看n<=20,直接暴力+剪枝即可inlinevoidsolve(){ inta,b; cin>>a>>b; vector<int>d; d.reserve(a+b); while(a--){ d.push_back(1); } while(b--){ d.push_back(2); } autodfs=[&](auto&......
  • Codeforces Round 968 (Div. 2)
    vp的，老规矩跳过abC:根据题意我们知道三个不一样的字母连续放一定可以，然后观察样例发现好像把两个不同的字母轮流放也可以。进一步猜测（瞎猜的)发现这个好像只要把不同的挨个放进去就行了（本来以为可能要按数量排序但是似乎根本不用），最后剩下的全放一起也没事。然后就过了。#includ......
  • Codeforces Round 970 div3
    CodeforcesRound970div3错过的一场比赛,第二天早晨VP,题目的通过率还挺奇怪A.Sakurako'sExamhttps://codeforces.com/contest/2008/problem/A题意:有a个1和b个2的数组,在1和2前面增添加减号,判断是否能让结果为0思路:1个2需要2个1进行填补,不如先让2自己进行消去,如......
  • Codeforces Round 969 Div.2+Div.1
    A.Dora'sSet注意到任意两个偶数的\(\gcd\)都大于\(1\)，因此选择的三个数中至多一个偶数，而注意到相邻的奇数一定互质，因此每次选两个奇数一个偶数，答案=奇数的个数÷2点击查看代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineullunsigned......
  • 学习指纹浏览器 处理美团mtgsig1.2 环境检测
    声明:本文章中所有内容仅供学习交流使用，不用于其他任何目的，抓包内容、敏感网址、数据接口等均已做脱敏处理，严禁用于商业用途和非法用途，否则由此产生的一切后果均与作者无关！有相关问题请第一时间头像私信联系我删除博客！前言去网上随便找个指纹浏览器默认都有免费10个免费浏......
  • codeforces做题记录（1924B）& 回顾线段树
    1924B.SpaceHarbour题意：n个点排成一行，其中某些点上面建有港湾，港湾有一个权值，对每个点我们定义点的权值为“左边（包括自己）第一个港湾上的权值\(\times\)到右边（包括自己）第一个港湾的距离”（保证在一开始1号和n号点上都有港湾）。有q次操作：操作1给定x和v，表示在x点上建立权值为v的......
  • Codeforces Round 969 (Div. 2)
    ab题没啥好说的，b题一开始看题错成线段树了，后面发现维护最大值就过了（我就说b怎么会有线段树）。。。C:DoraandC++卡的我死死的，好久没卡c了，数论果然是最短板。。。我有两个推论，但是一个都不会用：1.翡蜀定理。（但是这题只有正数）（处理两个数的情况）2.断环为链。（但是我只会n方，即以每个......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99