比赛地址:https://ac.nowcoder.com/acm/contest/11173

A:
记录每次的时刻及位置,利用上一次已经记录下的时刻及位置,判断是否符合条件即可,因为题目保证时刻按升序排列
设这次的时刻为t2,位置为(x2,y2),上次的时刻为t1,位置为(x1,y1),可以到达,当且仅当:
1、abs(x1-x2)+abs(y1-y2)<=t2-t1
两点的最短距离公式,如果此距离大于相差的时间,肯定到达不了
2、(t2-t1)%2==(abs(x1-x2)+abs(y1-y2))%2)
如果这两点的距离超过相差的时间,需要用两步来消耗时间,所以两者的奇偶性相同

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int f=0;
        int t1=0,x1=0,y1=0;
        for(int i=1;i<=n;i++)
        {
            int t2,x2,y2;
            scanf("%d%d%d",&t2,&x2,&y2);
            if(t2-t1>=abs(x1-x2)+abs(y1-y2)&&(t2-t1)%2==(abs(x1-x2)+abs(y1-y2))%2)
            {
                f++;
            }
            t1=t2,x1=x2,y1=y2;
        }
        if(f==n)
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
    }
    return 0;
}

B:
设与题目的r的二进制位数相等且最大的整数为w,则答案为[l,w]-(r,w],为了方便,我们把答案表示为[l,w]-[r,w],如果r的二进制表示中1的个数也是奇数,答案+1。
因为w的二进制表示中全部数都是1,所以求出[l,w]和[r,w]之间满足条件的数就变得方便很多。

设ji[i]表示l的二进制表示前i位与w的二进制表示前i位之间的1的个数为奇数的数,ou[i]表示l的二进制表示前i位与w的二进制表示前i位之间的1的个数为偶数的数,设n为w的二进制位数,则答案为ji[n]。

因为[l,w]和[r,w]只有下限的不同所以可以调用两次相同的函数,下面把这个下限设为x,x[i]表示x二进制表示中的第i位。

边界条件:图片说明

当x[i]=0,则:图片说明
因为当x[i]=0,当前位置可以填0或1,填0时,奇偶不变,填1时,奇偶交换。

当x[i]=1,如果前面选出来的数大于x前i-1位,则当前位置选0或1都不会小于这个下限,如果前面选出来的数等于x前i-1位,则当前位置只可以选1,不然会小于这个下限,所以先把ji[i]和ou[i]设置为x[i]=0时的情况,用一个变量去计算x前i-1为中1的个数,如果该个数为奇数,ou[i]--,如果该个数为偶数,ji[i]--。

#include<bits/stdc++.h>
using namespace std;
vector<int> a,b;
long long checkk(vector<int> c)
{
    long long ji=0,ou=1,x=0;
    for(int i=c.size()-1;i>=0;i--)
    {
        long long ans1=0,ans2=0;
        if(c[i]==0)
        {
            ans1+=ji+ou,ans2+=ou+ji;
        }
        else
        {
            if(x%2==0)
            {
                ans1+=ji,ans2+=ji;
                ans1+=1;
                ans1+=ou-1,ans2+=ou-1;
            }
            else
            {
                ans1+=ji-1,ans2+=ji-1;
                ans2+=1;
                ans1+=ou,ans2+=ou;
            }
            x++;
        }
        ji=ans1,ou=ans2;
    }
    return ji;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        long long l,r;
        scanf("%lld%lld",&l,&r);
        while(1)
        {
            a.push_back(l%2);
            l/=2;
            if(l==0)    break;
        }
        while(1)
        {
            b.push_back(r%2);
            r/=2;
            if(r==0)    break;
        }
        for(int i=a.size()+1;i<=b.size();i++)
        {
            a.push_back(0);
        }
        long long ans,p1=checkk(a),p2=checkk(b);
        ans=p1-p2;
        int x=0;
        for(int i=0;i<b.size();i++)
        {
            if(b[i]==1)    x++;
        }
        if(x%2==1)    ans++;
        //printf("%lld %lld\n",p1,p2);
        printf("%lld\n",ans);
        a.clear(),b.clear();
    }
    return 0;
}

C:
嗯,这道题让我挺无语的,考试结束后看讨论区才知道原来直接暴力即可,接下来就说一下这种暴力解法:

利用STL中的单调队列priority_queue,每次插入一个数都可自动按大到小排序,按照题目所说模拟即可,不过要注意,要特判n=1的情况,不然会在弹出元素时越界,a.top()表示返回队头元素,a.pop()表示弹出队头元素,最后逆序输出即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
priority_queue<long long> a;
long long ans[maxn];
int main()
{
    int n;
    long long k,p;
    cin>>n>>k>>p;
    for(int i=1;i<=n;i++)
    {
        long long x;
        scanf("%lld",&x);
        a.push(x);
    }
    if(n==1)
    {
        printf("%lld\n",a.top()-k*p);
        return 0;
    }
    while(1)
    {
        long long x=a.top();
        a.pop();
        long long y;
        if(p==0)    y=1e18+10;
        else y=(x-a.top())/p+1;
        if(y<k)
        {
            x-=y*p;
            a.push(x);
            k-=y;
        }
        else
        {
            x-=k*p;
            a.push(x);
            break;
        }
    }
    for(int i=1;i<=n;i++)
    {
        ans[i]=a.top();
        a.pop();
    }
    for(int i=n;i>=1;i--)
    {
        printf("%lld ",ans[i]);
    }
    printf("\n");
    return 0;
}

E:
这道题涉及一个定理:两个互素的数 a 和 b ,不能组成的最大的数为 图片说明 ,不能组成的数一定可以表示为 ,其中 x 和 y 均为正整数,详细证明请见:https://www.cnblogs.com/xxzh/p/9178564.html

我们用一个数组ans[i]表示第i贵的价值是多少,用两个变量aa和bb
aa表示最小的ans[aa]使得 图片说明
bb表示最小的ans[bb]使得 图片说明
选两者最大的就是ans[i],如果选择了前者,aa++,如果选择了后者,bb++,答案即为ans[k]

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7+10;
long long ans[maxn];
int main()
{
    long long a,b;
    int k;
    scanf("%lld%lld%d",&a,&b,&k);
    ans[1]=a*b-a-b;
    int aa=1,bb=1;
    for(int i=2;i<=k;i++)
    {
        ans[i]=max(ans[aa]-a,ans[bb]-b);
        if(ans[i]==ans[aa]-a)    aa++;
        if(ans[i]==ans[bb]-b)   bb++; 
    }
    cout<<ans[k]<<endl;
    return 0;
}