ABC 274 ABCD(*)

https://atcoder.jp/contests/abc274/tasks
A - Batting Average

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=200200,M=2002;
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        LL n,m;
        cin>>n>>m;
        printf("%.3lf\n",m*1.0/n);
    }
    return 0;
}

B - Line Sensor

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=200200,M=2002;
char a[M][M];
LL sum[N];
int main()
{
    //cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        memset(sum,0,sizeof sum);
        LL n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>a[i][j];
            }
        }
        for(int j=1;j<=m;j++)
        {
            for(int i=1;i<=n;i++)
            {
                if(a[i][j]=='#') sum[j]+=1;
            }
            //cout<<sum[j]<<" ";
        }
        for(int i=1;i<=m;i++)
        {
            cout<<sum[i]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

C - Ameba

题目大意：

最初，有一个虫子，编号为1。

你有N次记录。根据每一次记录，变形虫编号为Ai分裂出2*i和2*i+1。（也就是说Ai是2*i和2*i+1的祖先）。

问我们：对于每个k=1，…，n+1，k离1有多少代？

Sample Input 1 
2
1 2
Sample Output 1 
0
1
1
2
2

求深度问题，直接爆搜

做法一（dfs）

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=500200,M=2002;
LL a[N],dep[N];
vector<LL> v[N];
void dfs(LL idx,LL fa,LL depth)
{
    dep[idx]=depth;
    if(v[idx].size()==0) return ;
    for(LL i=0;i<v[idx].size();i++)
    {
        dfs(v[idx][i],idx,depth+1);
    }
}
int main()
{
    //cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        LL n;
        cin>>n;
        for(LL i=1;i<=n;i++)
        {
            cin>>a[i];
            v[a[i]].push_back(i*2);
            v[a[i]].push_back(i*2+1);
        }
        dfs(1,-1,0);
        for(LL i=1;i<=2*n+1;i++)
            cout<<dep[i]<<endl;
    }
    return 0;
}

做法二（数组）

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=500200,M=2002;
LL a[N];
int main()
{
    //cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        LL n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            LL x;
            cin>>x;
            a[i*2]=a[i*2+1]=a[x]+1;
        }
        for(int i=1;i<=2*n+1;i++)
            cout<<a[i]<<endl;
        //cout<<endl;
    }
    return 0;
}

D - Robot Arms 2

题目大意：

给定n个点，再给定一个坐标（x，y）。

给定长度为n的数组a，分别标记了数组A中相邻两个点的每一段的长度。

已知固定A0在（0，0）,A1在（a1，0），并且每一段前面的那一段都必须和自己垂直。

问我们这些数组能否让我们到达点（x，y）。

Sample Input 1 
3 -1 1
2 1 3
Sample Output 1 
Yes

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=5000200,M=2002;
LL n,x,y;
LL a[N];
LL check(vector<LL> &v,LL flag)
{
    //accumulate(begin,end,min); 加上所有>=min的数字
    LL sum=accumulate(v.begin(),v.end(),0);
    if((sum+flag)%2!=0) return 0;
    else
    {
        flag=(sum+flag)/2;
        if(flag<0) return 0;
        LL dp[flag+1];
        memset(dp,0,sizeof dp);
        dp[0]=1;
        for(LL i:v)
        {
            for(LL j=flag;j>=i;j--)
            {
                dp[j]|=dp[j-i];
            }
        }
        return dp[flag];
    }
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n>>x>>y;
        vector<LL> ou,ji;
        //因为第一步已经固定了只能跳在(a[1],0)的位置上
        //继续任意90°跳变的时候都是奇数位置上的a[i]往x轴变动
        //任意偶数位置上的a[i]往y轴上变动
        for(LL i=1;i<=n;i++)
        {
            cin>>a[i];
            if(i%2==0) ou.push_back(a[i]);
            else if(i!=1) ji.push_back(a[i]);//第一个抛开
        }
        //拆成两份，按x轴，y轴两类情况来考虑是否能够到达(x,y);
        if(check(ji,x-a[1])&&check(ou,y)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}