比赛地址: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; }