首页 > 其他分享 >AtCoder Beginner Contest 365

AtCoder Beginner Contest 365

时间：2024-08-04 22:07:39浏览次数：12  
标签：AtCoder include return Beginner int MAX mid long 365

AtCoder Beginner Contest 365

A - Leap Year

给出年份，判断这一年有多少天

闰年条件已经给出，逐条判断模拟即可。

#include<iostream>
using namespace std;
int main()
{
    int y;
    cin>>y;
    if(y%400==0||y%4==0&&y%100!=0)
        cout<<366<<endl;
    else
        cout<<365<<endl;
    return 0;
}

B - Second Best

求序列中第\(2\)大的数在原序列中是第几个元素。

双指针记录最大值和次大值，扫一遍更新即可。

#include<iostream>
int n,a[105];
using namespace std;
int main()
{
    cin>>n;
    int maxp=1,smaxp=0;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=2;i<=n;++i)
    {
        if(a[i]>a[maxp])smaxp=maxp,maxp=i;
        else if(a[i]>a[smaxp])smaxp=i;
    }
    cout<<smaxp<<endl;
    return 0;
}

C - Transportation Expenses

给出一个预算\(M\)，求最大的\(x\)，使得\(\sum_{i=1}^n \min{(a_i,x)}\le M\)。

二分答案，暴力扫一遍判断即可。

#include<iostream>
#include<cstdio>
using namespace std;
const int MAX=200200;
#define ll long long
int n;
long long m,a[MAX];
int main()
{
    scanf("%d",&n);
    scanf("%lld",&m);
    for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
    ll l=0,r=m+1,ret=l;
    while(l<=r)
    {
        ll mid=(l+r)>>1,tot=0;
        for(int i=1;i<=n;++i)
            tot+=min(a[i],mid);
        if(tot<=m)ret=mid,l=mid+1;
        else r=mid-1;
    }
    if(ret>m)
    {
        puts("infinite");
        return 0;
    }
    printf("%lld\n",ret);
    return 0;
}

D - AtCoder Janken 3

两个人玩石头剪刀布，已知第一个人的出招顺序。第二个人不能输任何一局，也不能相邻两局出同样的东西。
问最多能赢几局。

dp。设\(f[i][0/1/2]\)表示当前第\(i\)轮，上一轮出的是什么。转移的时候枚举这轮出什么，判断会不会输、有没有和上轮重复。判断胜负情况然后转移即可。

#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
#define MAX 200200
int n;
char s[MAX];
int f[MAX][3];
map<char,int> M;
int check(int a,int b)
{
    if(b==((a+1)%3))return 1;
    else return 0;
}
int main()
{
    scanf("%d",&n);
    scanf("%s",s+1);
    f[0][0]=f[0][1]=f[0][2]=0;
    M['R']=0;
    M['P']=1;
    M['S']=2;
    for(int i=1;i<=n;++i)
        for(int j=0;j<3;++j)
            for(int k=0;k<3;++k)
                if(j!=k)
                    if(!check(k,M[s[i]]))
                        f[i][k]=max(f[i][k],f[i-1][j]+check(M[s[i]],k));
    int ans=max(max(f[n][0],f[n][1]),f[n][2]);
    printf("%d\n",ans);
    return 0;
}

E - Xor Sigma Problem

求\(\sum_{i=1}^{N-1}\sum_{j=i+1}^n \oplus_{k=i}^j A_{k}\)

拆位，然后变成\(01\)序列问题。
设\(f[i]\)表示以\(i\)结尾的、异或和为\(1\)的序列数量。
转移判断这一位是\(1\)还是\(0\)。
最后求和即可。

#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 200200
int n,a[MAX];
long long f[MAX],ans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    for(int i=0;i<30;++i)
        for(int j=1;j<=n;++j)
        {
            int b=(a[j]>>i)&1;
            f[j]=b?(j-1-f[j-1]):f[j-1];
            ans+=1ll*(1<<i)*f[j];
            f[j]+=b;
        }
    printf("%lld\n",ans);
    return 0;
}

F - Takahashi on Grid

有一个网格图，第\(i\)列只有\(L[i]\)到\(U[i]\)位置可以走，每次给出两个坐标，问最短路。

首先，如果能向右走，就一定向右走。这样子一定不会更差。

于是区间子段可以分成两种：一种是可以一路向右走到顶，不需要沿着上下方向走的，称为\(A\)型。另一种是一路向右会撞墙，不得不通过上下移动走到特定位置才能继续向右，称为\(B\)型。

记录\(A\)型为三元组\((l,r,c)\)，\(l,r\)表示贯穿范围，\(c=-1\)用来标识。

记录\(B\)型为三元组\((l,r,c)\)，\(l\)表示最佳入口，如果不从这个位置进入，则需要先通过上下移动到达这个位置才能向右继续走（可以证明这个路径不会更差）。\(r\)表示根据一直向右走的条件，迫不得已才上下移动的情况下的出口位置。\(c\)表示区间内在符合一直向右走情况下，从最佳入口到出口的迫不得已的上下移动距离。

发现这两种区间和其三元组表示可以合并。

于是可以使用线段树进行维护。

#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 200200
#define ll long long
#define lson (x<<1)
#define rson (x<<1|1)
int n,Q;
int U[MAX],D[MAX];
struct Node{int l,r;ll c;}t[MAX<<2];
int dis(int i,int p1,int p2)
{
    int L=max(D[i],D[i+1]);
    int R=min(U[i],U[i+1]);
    if(L<=p1&&p1<=R)return 1+abs(p1-p2);
    int dis=min(abs(p1-L)+1+abs(L-p2),abs(p1-R)+1+abs(R-p2));
    return dis;
}
Node pushup(Node a,Node b)
{
    Node ret;
    if(a.c==-1)
    {
        if(b.c==-1)
        {
            if(max(a.l,b.l)<=min(a.r,b.r))
                ret.l=max(a.l,b.l),ret.r=min(a.r,b.r),ret.c=-1;
            else
            {
                if(a.r<b.l)
                    ret.l=a.r,ret.r=b.l,ret.c=b.l-a.r;
                else   
                    ret.l=a.l,ret.r=b.r,ret.c=a.l-b.r;
            }
        }
        else
        {
            if(a.l<=b.l&&b.l<=a.r)
                ret.l=b.l,ret.r=b.r,ret.c=b.c;
            else
            {
                if(a.l>b.l)
                    ret.l=a.l,ret.r=b.r,ret.c=b.c+a.l-b.l;
                else
                    ret.l=a.r,ret.r=b.r,ret.c=b.c+b.l-a.r;
            }
        }
    }
    else
    {
        if(b.c==-1)
        {
            if(b.l<=a.r&&a.r<=b.r)
                ret.l=a.l,ret.r=a.r,ret.c=a.c;
            else
            {
                if(a.r<b.l)
                    ret.l=a.l,ret.r=b.l,ret.c=a.c+b.l-a.r;
                else
                    ret.l=a.l,ret.r=b.r,ret.c=a.c+a.r-b.r;
            }
        }
        else
            ret.l=a.l,ret.r=b.r,ret.c=a.c+b.c+abs(a.r-b.l);
    }
    return ret;
}
void Build(int x,int l,int r)
{
    if(l==r)
    {
        t[x]=(Node){D[l],U[l],-1};
        return;
    }
    int mid=(l+r)>>1;
    Build(lson,l,mid);
    Build(rson,mid+1,r);
    t[x]=pushup(t[lson],t[rson]);
}
Node Query(int x,int l,int r,int L,int R)
{
    if(L==l&&r==R)return t[x];
    int mid=(l+r)>>1;
    if(R<=mid)return Query(lson,l,mid,L,R);
    if(L>mid)return Query(rson,mid+1,r,L,R);
    return pushup(Query(lson,l,mid,L,mid),Query(rson,mid+1,r,mid+1,R));
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d%d",&D[i],&U[i]);
    Build(1,1,n);
    scanf("%d",&Q);
    while(Q--)
    {
        int sx,sy,tx,ty;
        scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
        if(sx>tx)swap(sx,tx),swap(sy,ty);
        if(sx==tx)
        {
            printf("%d\n",abs(sy-ty));
            continue;
        }
        Node a=Query(1,1,n,sx,tx);
        a=pushup((Node){sy,sy,-1},a);
        a=pushup(a,(Node){ty,ty});
        if(a.c==-1)puts("0");
        else printf("%lld\n",a.c+tx-sx);
    }
    return 0;
}

G - AtCoder Office

有若干条出退勤记录，每条记录表示一个人状态变更（出勤变退勤，退勤变出勤）。
每次给出两个人，问这两个人同时出勤时长。

分块。

对于出退勤记录较少的两个人，维护双指针暴力计算线段交。

对于出退勤记录较多的单人，先用前缀和维护其出勤时间，剩下所有人通过前缀和计算出共事的时间。

复杂度\(O(M\sqrt M)\)。

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
#define MAX 200200
int read(){int x;scanf("%d",&x);return x;}
int n,m,q;
int cnt[MAX],tot,ID[MAX];
vector<int> t[MAX];
int Ans[1005][MAX];
int T[MAX],P[MAX];
int tmp[MAX];
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;++i)
    {
        T[i]=read(),P[i]=read();
        ++cnt[P[i]];
        t[P[i]].push_back(i);
    }
    for(int i=1;i<=n;++i)
        if(cnt[i]>=500)
        {
            ID[i]=++tot;
            for(int j=1,f=0;j<=m;++j)
            {
                if(f)tmp[j]=T[j]-T[j-1];
                else tmp[j]=0;
                if(P[j]==i)f^=1;
            }
            for(int j=1;j<=m;++j)tmp[j]+=tmp[j-1];
            for(int j=1;j<=n;++j)
                if(i!=j)
                    if(t[j].size())
                        for(int k=0,l=t[j].size();k<l;k+=2)
                            Ans[tot][j]+=tmp[t[j][k+1]]-tmp[t[j][k]];
        }
    int Q=read();
    while(Q--)
    {
        int a=read(),b=read();
        if(ID[a])
        {
            printf("%d\n",Ans[ID[a]][b]);
            continue;   
        }
        if(ID[b])
        {
            printf("%d\n",Ans[ID[b]][a]);
            continue;
        }
        int p1=0,p2=0,l1=t[a].size(),l2=t[b].size();
        int f1=0,f2=0,lt=0,ans=0;
        while(p1<l1&&p2<l2)
        {
            if(t[a][p1]<t[b][p2])
            {
                if(f1&&f2)ans+=T[t[a][p1]]-lt;
                f1^=1;
                lt=T[t[a][p1]];
                p1++;
            }
            else
            {
                if(f1&&f2)ans+=T[t[b][p2]]-lt;
                f2^=1;
                lt=T[t[b][p2]];
                p2++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

标签：AtCoder,include,return,Beginner,int,MAX,mid,long,365
From： https://www.cnblogs.com/cjyyb/p/18342284

相关文章

  • AtCoder Beginner Contest 365
    F-TakahashionGrid用线段树上的节点维护一下\((l,r,c)\)，如果\(c\)为\(-1\)：\(l,r\)表示这一段区间内\([l,r]\)的交。如果\(c\ne-1\)，\(l,r\)表示这一段第一次上下界相等的时候的位置为\(l\)，合并后走出来的位置为\(r\)，然后转折的步数为\(c\)。然后这玩意可以合并......
  • ABC365
    Alink题目已经说的很明白了，判断即可。点击查看代码#include<bits/stdc++.h>usingnamespacestd;inty;signedmain(){ cin>>y; if(y%4!=0)cout<<365; elseif(y%4==0&&y%100!=0)cout<<366; elseif(y%100==0&&y%400!......
  • ABC365
    A.LeapYear模拟代码实现importcalendary=int(input())ifcalendar.isleap(y):print(366)else:print(365)B.SecondBest模拟代码实现n=int(input())a=list(map(int,input().split()))print(a.index(sorted(a)[-2])+1)C.TransportationEx......
  • 【A~E】AtCoder Beginner Contest 365
    A-LeapYear题目大意给定\(n\)，求第\(n\)年的天数（\(365\)或\(366\)）。思路显然地，我们需要判断这个是否为闰年。如果\(n\)不能被\(4\)整除，那么不是闰年。如果\(n\)可以被\(400\)整除，那么是闰年。如果\(n\)不可以被\(100\)整除但是可以被\(4\)整除，那么是......
  • 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";......
  • AtCoder Beginner Contest 365 随笔
    擦，F假了A判断闰年B输出次大值的下标用pair排序后即可C给定一个数组\(A_n\)和整数\(M\)，尝试找到一个最大的\(m\)，使得：\[\sum_{i=1}^n\min(A_i,m)\leM\]不等号左边显然随着\(m\)的增大而增大，所以可以二分一个\(m\)，然后判断即可D两个人玩\(n\)局剪刀石头布......
  • ABC365（A-D）未补
    A-LeapYear（模拟）题意：给定一个数字n，如果n不是4的倍数，输出365；如果n是4的倍数但不是100的倍数，输出366；如果n是100的倍数但不是400的倍数，输出365；如果n是400的倍数，输出366分析：模拟题目即可代码：#include<bits/stdc++.h>usingnamespacestd;intmain(){intn;cin>>n;......
  • 如何通过PowerShell批量修改O365用户的office phone属性值
    我的博客园：https://www.cnblogs.com/CQman/如何通过PowerShell批量修改O365用户的officephone属性值？需求信息： 组织中的O365用户在创建时，已手动录入了办公电话(Officephone)，现在需要在办公电话前面加上统一的数字，如“0571-0985”，以批量的方式统一修改。备注：O365用户的Offic......
  • Atcoder ABC298 D-F
    AtcoderABC298D-FD-WritingaNumeral链接:D-WritingaNumeral(atcoder.jp)简要题意:问题陈述我们有一个字符串\(S\)。初始值为\(S=\)1.按以下格式依次处理\(Q\)查询。1x：在\(S\)的末尾添加一个数字\(x\)。2：删除\(S\)开头的数字。3:以十进制形......
  • 每日一题——A - Max/Min AtCoder - abc356_e
    1.题目大意：枚举两个数的Max/Min向下取整之和。2.思路：一开始并没有想时间复杂度问题发现通过sort()排序来遍历每个最小值Min和后面最大值的和就是题目答案。你会发现仍然有问题，那就是取整的问题你就必须要优化然后发现很明显超时了。现在我们来换一个角度思考。搭配前缀和嘛。为......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99