Aising Programming Contest 2022（AtCoder Beginner Contest 255）A-F

A - You should output ARC, though this is ABC.

B - Light It Up

C - ±1 Operation 1

D - ±1 Operation 2

E - Lucky Numbers

F - Pre-order and In-order

A - You should output ARC, though this is ABC.

A - You should output ARC, though this is ABC.https://atcoder.jp/contests/abc255/tasks/abc255_a

水题,输入r,c,和一个2*2的矩阵a,输出a[r][c]即可

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
int a[3][3];
void solve()
{
    int x,y;
    cin>>x>>y>>a[1][1]>>a[1][2]>>a[2][1]>>a[2][2];
    cout<

B - Light It Up

B - Light It UpAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.https://atcoder.jp/contests/abc255/tasks/abc255_b告诉你有n个点,其中k个可以发光,问让每个不发光的点被照射到,问最小需要多大的光照强度(即以发光点为圆心,发光强度为半径画圆,不发光的点在圆上或者圆内)

思路:看见数据很小,1000,直接把不发光的点和每个发光的点进行匹配,取这个点被光笼罩的最小值,在对于每个不发光点的最小值取最大值即可,时间复杂度是n方.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int vis[1003];
double x[1003],y[1003];
void solve()
{
    int n,k;
    memset(vis,0,sizeof vis);
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)
    {
        int a;
        scanf("%d",&a);
        vis[a]=1;
    }
    for(int i=1;i<=n;i++)
        scanf("%lf%lf",&x[i],&y[i]);
    double ans1=-10000000000;
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==1)
            continue;
        double ans=10000000000;
        for(int j=1;j<=n;j++)
        {
            if(vis[j]==0)
                continue;
            ans=min(ans,(double)sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])));
        }
        ans1=max(ans1,ans);
    }
    printf("%.6lf",ans1);
}
signed main()
{
    solve();
    return 0;
}

C - ±1 Operation 1

C - ±1 Operation 1https://atcoder.jp/contests/abc255/tasks/abc255_c给你一个数x,一个等差数列的首项,公差和项数,问x需要几步变成这个数列的一员(只可以++或者- -);

思路:分情况讨论贪心.

因为这个等差数列可能是递增也有可能是递减,所以我们统一把它替换成递增等差数列计算.

分三个情况,当x<=首项时,直接计算首项和x的差即可,当x>=末项,直接计算末项和x的差即可.当x在等差数列范围之内,那么我们直接看x减去首项之后最近的能被公差整除的距离即可.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
void solve()
{
    int x,a,d,n;
    cin>>x>>a>>d>>n;
    if(d<0)
        a+=(n-1)*d,d=-d;
    if(x<=a)
        cout<=(a+(n-1)*d))
        cout< 

D - ±1 Operation 2 
D - ±1 Operation 2https://atcoder.jp/contests/abc255/tasks/abc255_d 
给出n个数,q次询问,每次询问,x变到这n个数的总距离和(x只可以+ +或者- -); 
思路:前缀和+二分 
对于x变成这个数组中的每个数的操作,我们可以分成两种,第一种就是由x一直减1得到的,另一种是由x一直加1得到的.很容易想到我们把他们分类去集体讨论,刚好,只要小到大排序之后,就可以用从一个地方把排好序的数组按照上述方法分成两边.一边计算贡献都是数组元素-x,另一边都是x-数组元素.只需要求一下两边元素的和再用x减去或者减去x即可,那么很容易就想到排序之后求一个前缀和,在采用二分的方法找到数组分成两办的位置,直接计算即可; 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define int long long
using namespace std;
int a[200005];
int sum[200005];
bool cmp(int x,int y)
{
    return x=a[n])
            printf("%lldn",x*n-sum[n]);
        else
        {
            int id=lower_bound(a+1,a+1+n,x)-a;
            int ans=0;
            ans+=(x*(id-1)-(sum[id-1]-sum[0]));
            ans+=(sum[n]-sum[id-1]-x*(n-id+1));
            printf("%lldn",ans);
        }
    }
    return;
}
signed main()
{
    solve();
    return 0;
} 

E - Lucky Numbers 
E - Lucky NumbersAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.https://atcoder.jp/contests/abc255/tasks/abc255_e一道有趣的思维题 
给出长度为n-1(1= 
直接手写推导过程(字不太好): 
 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
int s[100005],x[12],t[100005];
mapma;
void solve()
{
    int n,m;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n-1;i++)
        scanf("%lld",&s[i]);
    for(int i=1;i<=m;i++)
        scanf("%lld",&x[i]);
    t[1]=0;
    for(int i=2;i<=n;i++)
        t[i]=s[i-1]-t[i-1];
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            int tr=1;
            if(j%2==0)
                tr=-1;
            int res=x[i]-t[j];
            res*=tr;
            ma[res]++;
        }
    int ans=0;
    for(auto x:ma)
        ans=max(ans,x.second);
    printf("%lld",ans);
    return;
}
signed main()
{
    solve();
    return 0;
} 

F - Pre-order and In-order 
F - Pre-order and In-orderAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.https://atcoder.jp/contests/abc255/tasks/abc255_f给你先序和中序遍历,重构建树.不成立就输出-1. 
模拟 
根据先序遍历是:根,左,右 
和中序遍历是:    左,根,右 
该问题本质就是根据先序遍历来找到根节点,再由根节点将当前区间(中序遍历)分割成两个小区间,进行递归,再由先序找到根节点,依次往复即可. 
的性质,再将两者关联起来,建树: 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N =5e5+10,mod=998244353;
int n;
int pp[200005];
int ii[200005];    
int ptoi[200005];
int itop[200005];
int vis[200005]={0};
int l[200005],r[200005];
int dfs(int pi,int il,int ir)
{
    if(pi>n||il>ir)
        return 0;
    int root=pp[pi],lsum=ptoi[root]-il,rsum=n-ptoi[root];

    if(vis[root]==1)
    {
        printf("-1n");
        exit(0);
    }
    vis[root]=1;
    
    if(lsum==0)
        l[root]=0;
    else
        l[root]=dfs(pi+1,il,ptoi[root]-1);
    if(rsum==0)
        r[root]=0;
    else
        r[root]=dfs(pi+lsum+1,ptoi[root]+1,ir);
    return root;
}
void solve()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&pp[i]);
        itop[pp[i]]=i;

    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&ii[i]);
        ptoi[ii[i]]=i;

    }
    if(pp[1]!=1)
    {
        printf("-1n");
        return;
    }
    dfs(1,1,n);
    for(int i=1;i<=n;i++)
        printf("%d %dn",l[i],r[i]);
    return;
}
signed main()
{
    solve();
    return 0;
}

Aising Programming Contest 2022（AtCoder Beginner Contest 255）A-F

C/C++/C#相关栏目本月热门文章