前言:

第一次英语读题.

A - Three-Point Shot

三分球直接判断+3即可.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    if(max(a,b)<min(a,b)+3)    puts("Yes");
    else                    puts("No");
    return 0;
}

B - Orthogonality

emmm按题目写的做就好了.

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+50;
int a[N],b[N];
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)    scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)    scanf("%d",&b[i]);
    int flag=0;
    for(int i=1;i<=n;i++)
    {
        flag+=a[i]*b[i];
    }
    if(flag)    puts("No");
    else        puts("Yes");
    return 0;
}

C - ABC Tournament

定义那么答案就算第n-1次获胜的时候那个较小值.直接dp即可.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=(1<<17),M=17;
int f[N][M];//i号点进行了j次比赛后获胜的人id是多少. 
int w[N];
int main()
{
    int n;scanf("%d",&n);
    int mod=(1<<n);
    for(int i=0;i<(1<<n);i++)
    {
        scanf("%d",&w[i]);
        f[i][0]=i;
    }
    for(int i=1;i<n;i++)
    {
        int next=(1<<(i-1));
        for(int j=0;j<(1<<n);j++)
        {
            if(w[f[j][i-1]]<w[f[(j+next)%mod][i-1]])    f[j][i]=f[(j+next)%mod][i-1];
            else                                        f[j][i]=f[j][i-1];
        }
    }int ans;//cout<<f[2][1]<<endl;
    if(w[f[0][n-1]]<w[f[mod/2][n-1]])    ans=f[0][n-1];
    else                                ans=f[mod/2][n-1];
    printf("%d\n",ans+1);
    return 0;
}

D - Snuke Prime

差分记录下要改变的值,然后拿map这个迭代器遍历记录下,这个点和上个点,以及选拿个最优即可.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<int,ll>cost;
int main()
{
    int n;ll c;
    cin>>n>>c;
    for(int i=1;i<=n;i++)
    {
        int l,r,x;
        cin>>l>>r>>x;
        cost[l]+=x;cost[r+1]-=x;
    }int lastid=0;ll lastval=0;//上个位子的坐标. 
    ll ans=0,sum=0;
    for(auto x:cost)
    {
        int f=x.first;
        ll s=x.second;
        lastval=sum;
        sum+=s;
        if(!lastid)
        {
            lastid=f;
        }
        else
        {
            ans+=(f-lastid)*min(lastval,c);
            lastid=f;
        }
    }cout<<ans<<'\n';
    return 0;
}

E - Peddler

直接记忆化搜索dp即可,定义dfs(u)为不包含当前的点u的子树maxval.然后搜完就好了.

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+500;
vector<int>v[N];
int deg[N];
bool vis[N];
int a[N];
int f[N];
int ans=-2e9;
int dfs(int u)//不包含当前的点的子树maxval 
{
    if(f[u]) return f[u];
    int res=-2e9;    
    for(int x:v[u])
    {
        res=max(res,a[x]);
        res=max(res,dfs(x));
        ans=max(ans,res-a[u]);
    }return f[u]=res;
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)    scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        v[x].push_back(y);
        vis[x]=true;vis[y]=true;
        deg[y]++;
    }a[0]=-1e9;
    for(int i=1;i<=n;i++)
    {
        if(vis[i]&&!deg[i])    ans=max(ans,dfs(i)-a[i]);
    }printf("%d\n",ans);
    return 0;
}

F - +1-1x2

贪心+数位dp,本的原则就算能/2的尽量/2,然后再记忆化搜索就行了~

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x,y;
map<ll,ll>f;
ll dfs(ll u)
{
    if(!u)        return x;
    if(f[u])    return f[u];
    ll    &ans=f[u];
    ans=abs(x-u);
    if(u%2==0)    ans=min(ans,1+dfs(u/2));
    else        ans=min(ans,min(1+dfs(u-1),1+dfs(u+1)));
    return ans;
}
int main()
{
    cin>>x>>y;
    printf("%lld\n",dfs(y));            
    return 0;
}