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

AtCoder Beginner Contest 361

时间：2024-07-07 17:30:21浏览次数：18  
标签：AtCoder return Beginner int MAX long 序列 include 361

AtCoder Beginner Contest 361

A - Insert

给定一个长度为\(N\)的序列\(A\)，现在希望将数字\(X\)插入到序列的第\(K\)个数字后面，变成一个新的序列\(B\)。输出序列\(B\)。
\(K,N,A_i,X\le 100\)

模拟题。先读入\(N,K,X\)。接着在读入\(A\)的过程中一遍读入一遍输出，如果读到了第\(K\)个，则直接在后面输出\(X\)。

#include<iostream>
#include<cstdio>
using namespace std;
int n,k,x,a;
int main()
{
    cin>>n>>k>>x;
    for(int i=1;i<=n;++i)
    {
        cin>>a;
        cout<<a<<' ';
        if(i==k)cout<<x<<' ';
    }
    cout<<endl;
    return 0;
}

B - Intersection of Cuboids

在三维空间中给出两个长方体的对角线（这样就可以唯一确定一个长方体），判断两个长方体之间是否有体积交。
所有坐标均在\([0,1000]\)之内。

三维依次判断一下是否存在长度不小于\(1\)的交（这是因为交的长度必定是整数，如果有交长度必然大于等于\(1\)）。

可以利用数据范围简化判断是否有交的过程，暴力枚举某一段是否为交。也可以正难则反，判断是否无交。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
int a[10],A[10];
int b[10],B[10];
bool In(int x,int y,int z,int *a)
{
    if(x<=a[1]||x>=a[4])return false;
    if(y<=a[2]||y>=a[5])return false;
    if(z<=a[3]||z>=a[6])return false;
    return true;
}
int main()
{
    for(int i=1;i<=6;++i)cin>>a[i];
    for(int i=1;i<=3;++i)A[i]=min(a[i],a[i+3]),A[i+3]=max(a[i],a[i+3]);
    for(int i=1;i<=6;++i)cin>>b[i];
    for(int i=1;i<=3;++i)B[i]=min(b[i],b[i+3]),B[i+3]=max(b[i],b[i+3]);
    for(int i=1;i<=3;++i)
    {
        bool flag=false;
        /*
        for(int j=0;j<1000;++j)
            if(A[i]<=j&&j<A[i+3]&&B[i]<=j&&j<B[i+3])
                flag=true;
        */
        if(A[i+3]<=B[i]||B[i+3]<=A[i])flag=false;
        else flag=true;
        if(!flag)
        {
            puts("No");
            return 0;
        }
    }
    puts("Yes");
    return 0;
}

C - Make Them Narrow

有一个长度为\(N\)的序列\(A\)。随机从中删去\(K\)个数，剩下的数保留他们原本的顺序构成序列\(B\)。
求如下值的最小值：序列\(B\)中的最大值与序列\(B\)中的最小值的差。
\(K,N\le 2\times 10^5，A_i\le 10^9\)

首先，序列中的最大值和最小值都与序列本身的顺序无关，而随机删去\(K\)个数也与序列本身的顺序无关。因此原本的顺序就是一个无用的限制。

所以将\(A_i\)从小往大排序，贪心的考虑，剩余的一定是其中连续的一段子序列。因此扫一遍整个序列，枚举所有长度为\(n-k\)的连续子段，由于已经排好序，所以最大值和最小值一定是小标最大和最小的元素。求出其中最小值即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int MAX=200200;
int n,k,a[MAX],ans=1e9;
int main()
{
    scanf("%d%d",&n,&k);
    k=n-k;
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    sort(&a[1],&a[n+1]);
    for(int i=1;i+k-1<=n;++i)
        ans=min(ans,a[i+k-1]-a[i]);
    printf("%d\n",ans);
    return 0;
}

D - Go Stone Puzzle

有\(N+2\)个格子排成一排，其中\(1-N\)号格子中一开始有石头，石头只能是黑色或者白色。\(N+1、N+2\)号格子是空的。
接下来可以进行若干次如下的操作：

  • 选择相邻的、且其中均有石头的两个格子，将其中的石头拿走，按照原顺序移动到空格子中。（不拿发现操作完之后仍然是N个格子中有石头，且有相邻的两个格子是空的）
    回答最少几次操作之后\(1-N\)号格子中的石头颜色恰好是指定的样子。
    \(N\le 14\)

注意到格子只有黑色、白色和空总共三种情况，如果采用三进制进行状压总共情况也就\(3^{16}\le 5\times 10^7\)，这是可以存下的。并且最终会被使用到的状态远远小于这个值。

而最少步骤只需要使用\(BFS\)进行搜索就不难得出。

还有一种更好的做法：注意到空格子有且仅有两个，还是相邻的，所以实际上我们只需要使用二进制状压剩余非空格子的黑白状态，然后额外记录一个位置信息，这样至多只有\(2^{14}\times 14\)个，当然代码会略复杂一些。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
int n,s,t;
char S[20],T[20];
struct Node{int s,p;};
queue<Node> Q;
int step[1<<14][15];
int main()
{
    scanf("%d",&n);
    scanf("%s",S);
    scanf("%s",T);    
    int cnt1=0,cnt2=0;
    for(int i=0;i<n;++i)
        if(S[i]=='B')
            s|=1<<i,cnt1+=1;
    for(int i=0;i<n;++i)
        if(T[i]=='B')
            t|=1<<i,cnt2+=1;
    if(cnt1!=cnt2)
    {
        puts("-1");
        return 0;
    }
    memset(step,-1,sizeof(step));
    step[s][n]=0;
    Q.push((Node){s,n});
    while(!Q.empty())
    {
        Node a=Q.front();
        Q.pop();
        for(int i=0;i<n-1;++i)
        {
            if(i==a.p-1)continue;
            Node b;
            b.p=i+((i>=a.p)?2:0);
            int ss=(a.s>>i)&3;
            b.s=(a.s&((1<<a.p)-1))|((a.s>>a.p)<<(a.p+2))|(ss<<a.p);
            b.s=(b.s&((1<<b.p)-1))|((b.s>>(b.p+2))<<b.p);
            if(step[b.s][b.p]!=-1)continue;
            step[b.s][b.p]=step[a.s][a.p]+1;
            Q.push(b);
        }
    }
    int ans=step[t][n];
    printf("%d\n",ans);
    return 0;
}

E - Tree and Hamilton Path 2

给定一棵树，每条边有边权。可以从任何一个点出发，回答遍历所有点至少一次所需的最短路径长度和。

假设最终要回到起点的话，不难看出答案就是所有边权之和的二倍，这个很容易理解：只考虑每条边，一定是进一次子树，出一次子树，恰好被通过两次。

而现在最终可以不回到终点，意味着我们可以任意选定一个点，那么此时的距离就是所有边权和的二倍减去这个点到起点的距离。

这个点可以任选，而起点也可以任选，意味着答案就是所有边权的和的二倍减去树上距离最长的两个点的距离，这个本质就是求树上的直径。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<vector>
using namespace std;
const int MAX=200200;
int read(){int x;scanf("%d",&x);return x;}
struct Edge{int v,next,w;}e[MAX<<2];
int h[MAX],cnt;
void Add(int u,int v,int w){e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;}
int n;
long long dep[MAX],lf[MAX];
long long sumlen,d;
void dfs(int u,int ff)
{
    for(int i=h[u];i;i=e[i].next)
    {
        int v=e[i].v,w=e[i].w;
        if(v==ff)continue;
        dep[v]=dep[u]+w;
        dfs(v,u);
        d=max(d,lf[u]+lf[v]+w);
        lf[u]=max(lf[u],lf[v]+w);
    }
}
int main()
{
    n=read();
    for(int i=1;i<n;++i)
    {
        int u=read(),v=read(),w=read();
        Add(u,v,w);
        Add(v,u,w);
        sumlen+=w;
    }
    dfs(1,0);
    cout<<sumlen*2-d<<endl;
    return 0;
}

F - x = a^b

给定\(N\)，求出所有小于等于\(N\)的正整数中，有多少个可以写成\(a^b\)的形式，其中\(b\ge 2\)。
\(N\le 10^{18}\)。

首先如果只需要对于特定的\(b\)计算答案的话，那么显而易见的答案就是\(\sqrt[b]{N}\)。注意开根不能直接使用浮点数计算，这样可能丢失精度导致答案有偏差，可以二分计算。

但是简单的累加会计算重复，考虑容斥。

如果\(b\)是质数，那么显然只会被计算一次。

如果\(b=\prod_{i=1}^n p_i^{a_i}\)，假设存在一个\(a_i>1\)，那么显而易见的，它会被\(p_i\)完全覆盖，因此完全不需要计算次数。

如果\(b=\prod_{i=1}^n p_i\)，那么根据容斥原理，其应该需要被计算\((-1)^{n-1}\)次。可以使用数学归纳法证明。

当然，其实这个数值就是\(\mu(b)\)。

注意\(1\)这个数需要单独拿出来算。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
int mu[100],pri[100],tot;
bool zs[100];
void calc()
{
    zs[1]=true;mu[1]=1;
    for(int i=2;i<100;++i)
    {
        if(!zs[i])pri[++tot]=i,mu[i]=-1;
        for(int j=1;j<=tot&&pri[j]*i<100;++j)
        {
            zs[i*pri[j]]=true;
            if(i%pri[j])mu[i*pri[j]]=-mu[i];
            else{mu[i*pri[j]]=0;break;}
        }
    }
}
long long fpow(long long a,long long b)
{
    long long ret=1;
    while(b){if(b&1)ret*=a;b>>=1,a*=a;}
    return ret;
}
long long pre[100];
long long Sqrt(long long n,int k)
{
    long long l=1,r=pre[k];
    long long ret=1;
    while(l<=r)
    {
        long long mid=(l+r)>>1;
        if(fpow(mid,k)>n)r=mid-1;
        else l=mid+1,ret=mid;
    }
    return ret;
}
long long n,ans;
int main()
{
    calc();
    cin>>n;
    for(int i=2;i<=60;++i)
        if(mu[i]!=0)
            pre[i]=(long long)pow(1ll<<61,1.0/i);
    for(int i=2;i<=60;++i)
        if(mu[i]!=0)
            ans-=mu[i]*(Sqrt(n,i)-1);
    cout<<ans+1<<endl;
    return 0;
}

G - Go Territory

在第一象限和坐标轴的整点坐标上有若干个石头，回答有多少个整点坐标能够在不碰到任何石头的情况下，能够仅通过上下左右抵达\((-1,-1)\)。

此处输入图片的描述

如图所示，沿着\(x\)轴坐标（或者\(y\)轴坐标划分所有的非石头的连续段），如果两个连续段之间有格子相邻，那么在它们之间连一条边。于是问题变成了有多少个点不和\((-1,-1)\)所在的连续段在一个联通快内。使用\(BFS\)即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int MAX=200200;
int read(){int x;scanf("%d",&x);return x;}
int n;
pair<int,int> p[MAX];
vector<pair<int,int> > l[MAX];
int sz[MAX<<2];
struct Edge{int v,next;}e[MAX<<3];
int h[MAX<<2],cnt=1;
void Add(int u,int v){e[cnt]=(Edge){v,h[u]};h[u]=cnt++;}
bool vis[MAX<<2];
queue<int> Q;
int main()
{
    n=read();
    int MX=0,MY=0;
    for(int i=1;i<=n;++i)
    {
        int x=read()+1,y=read()+1;
        p[i]=make_pair(x,y);
        MX=max(MX,x);
        MY=max(MY,y);
    }
    MX++;MY++;
    sort(&p[1],&p[n+1]);
    for(int i=0,L=0;i<=MX;++i)
    {
        int R=L;
        while(R+1<=n&&p[R+1].first==i)++R;
        int Low=0;
        for(int j=L+1;j<=R;++j)
        {
            if(Low<p[j].second)l[i].push_back(make_pair(Low,p[j].second-1));
            Low=p[j].second+1;
        }
        l[i].push_back(make_pair(Low,MY));
        L=R;
    }
    int tot=1;
    for(int i=0;i<MX;++i)
    {
        int len=l[i].size();
        int nxtlen=l[i+1].size();
        for(int j=0,pos=0;j<len;++j)
        {
            int now=tot+j;
            int L=l[i][j].first,R=l[i][j].second;
            sz[now]=R-L+1;
            while(pos<nxtlen&&l[i+1][pos].second<L)++pos;
            while(pos<nxtlen&&l[i+1][pos].second<=R)
            {
                int nxt=tot+len+pos;
                Add(now,nxt);Add(nxt,now);
                ++pos;
            }
            if(pos<nxtlen&&l[i+1][pos].first<=R)
            {
                int nxt=tot+len+pos;
                Add(now,nxt);Add(nxt,now);
            }
        }
        tot+=len;
    }
    Q.push(1);vis[1]=true;
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        for(int i=h[u];i;i=e[i].next)
        {
            int v=e[i].v;
            if(vis[v])continue;
            vis[v]=true;
            Q.push(v);
        }
    }
    long long ans=0;
    for(int i=1;i<=tot;++i)
        if(!vis[i])ans+=sz[i];
    cout<<ans<<endl;
    return 0;
}

标签：AtCoder,return,Beginner,int,MAX,long,序列,include,361
From： https://www.cnblogs.com/cjyyb/p/18288731

相关文章

  • abc361
    A-Inserthttps://atcoder.jp/contests/abc361/tasks/abc361_ahttps://atcoder.jp/contests/abc361/submissions/55260626intn,k,x;vector<int>a;intmain(){cin>>n>>k>>x;a.resize(n+1);for(inti=0;i<n+1;......
  • AtCoder Beginner Contest 361）
    推荐个C++编程仓库模板https://github.com/yxc-s/programming-templateA-Insertvoidsolve(){ intn,k,x; cin>>n>>k>>x; vector<int>a(n); for(auto&x:a){ cin>>x; } a.insert(a.begin()+k,x); for(inti=0;......
  • Denso Create Programming Contest 2024（AtCoder Beginner Contest 361）
    DensoCreateProgrammingContest2024（AtCoderBeginnerContest361）\(A\)Insert\(AC\)循环结构。点击查看代码inta[200];intmain(){intn,k,x,i;cin>>n>>k>>x;for(i=1;i<=n;i++){cin>>a[i];cout......
  • ABC361
    A.Insert模拟代码实现n,k,x=map(int,input().split())a=list(map(int,input().split()))a.insert(k,x)print(*a)B.IntersectionofCuboids模拟代码实现#include<bits/stdc++.h>#definerep(i,n)for(inti=0;i<(n);++i)usingnamespacest......
  • AtCoder Beginner Contest 361 补题记录（A~F）
    开题顺序：A-C-F-D-B-E。A直接模拟即可。boolbegmem;#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;classFastIO{public:intread(){into=1,x;charch;while(!isdigit(ch=getchar())){if......
  • Solution - Atcoder ARC125E Snack
    观察到这种都是数量上限的限制，且求\(\max\)。所以可以考虑网络流建模，而流量就对应着给的糖果数。令\(S\)为源点，\(T\)为汇点，编号为\(1\simn\)的点对应的糖果的种类，编号为\(n+1\simn+m\)的点对应的小孩。连边\((S,i,a_i)\)，表示第\(i\)种糖果数不超过\(a_i\)......
  • #贪心#洛谷 3615 如厕计划
    题目传送门分析如果男生数目比女生数目多显然无解，在原队列的基础上考虑调换实际是将男生往前移实际上不满意度就是最后一位女生后移了多少位，记女生为一，男生为负一，运用数学归纳法证明只要后缀最小值不低于负一，那么一定存在一种方案，实际上就是求出后缀最小值，并将其调整至不低......
  • AtCoder Beginner Contest 359
    AtCoderBeginnerContest359A-CountTakahashi有\(n\)个字符串，每个串要么是Takahashi要么是Aoki，问有多少个字符串是Takahashi额....这还要有题解吗(?)#include<iostream>#include<cstring>usingnamespacestd;intmain(){stringa;intn,ans=0;cin>......
  • Solution - Atcoder AGC010E Rearranging
    因为只有相邻的互质的\(a_i\)可以交换，那么就说明不互质的\(a_i\)无法相交换，对应的位置关系也就不会改变。于是可以考虑图论建模，对于\(\gcd(a_i,a_j)>1\)，连边\((i,j)\)。那么对于先手，就相当于要把这些边定向，变为一个DAG。而后手因为要保证最大，所以肯定是在DAG上跑......
  • AtCoder Beginner Contest 359
    AtCoderBeginnerContest359这场我赛时打的非常不好，只做出了\(2\)题。A-CountTakahashi签到//Problem:A-CountTakahashi//Contest:AtCoder-UNIQUEVISIONProgrammingContest2024Summer(AtCoderBeginnerContest359)//URL:https://atcoder.jp/conte......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99