A 只有判段相邻的差是不是有奇数, 有奇数 NO, 反之 YES
B 因为题目说随便两个相等 + 另一个数就是 YES, 所以 map 存第一次出现的数字的位置, 如果再次出现, 只要那个数的第一个位置不是 i-1 就是 YES 反之 NO
C 蛋疼题意, 其实只要找两个 RR 之间最短的距离 + 1 就行了
D
题意:
老师的 n 个想法价值 ai, 同学的 n 个想法价值 bi, 相互对应, 找一共有多少对 ai+aj-bi-bj>0
思路:
直接将老师的思路减学生的思路, 从小到大排序, 用 upper_bound 去找他的相反数的大一点的位置, 复杂度是 O(lgn*n)
但是 n 是 2e5 的范围, 答案可能会爆 int, 别忘了开 ll
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define ull unsigned long long
- #define il inline
- #define it register int
- #define inf 0x3f3f3f3f
- #define lowbit(x) (x)&(-x)
- #define pii pair<int,int>
- #define mak(n,m) make_pair(n,m)
- #define mem(a,b) memset(a,b,sizeof(a))
- #define mod 998244353
- const int maxn=2e5+10;
- int a[maxn],b;
- int main(){
- int n;
- scanf("%d",&n);
- for(int i=0;i<n;i++)
- scanf("%d",&a[i]);
- for(int i=0;i<n;i++) {
- scanf("%d",&b);
- a[i]-=b;
- }
- sort(a,a+n);
- ll ans=0;
- for(int i=0;i<n;i++){
- int zhi=-a[i];
- int pos=upper_bound(a+i+1,a+n,zhi)-a;
- ans+=(ll)n-pos;
- }
- printf("%lld\n",ans);
- return 0;
- }
- View Code
- E
题意 (题目描述进行魔改, 但内容大致不变):
给 n,h,l,r 四个值, 表示 n 长度的数组, 0~h-1 的范围, 在 [l,r] 区间得分能获得一个奖品 (1<=n<=2000)
接下来的 n 个数, 是按顺序的比赛得分, 但是你有一个权力, 每次得分可以保持不变, 或者减一, 然后进行累加, 如果超出 h,%h, 问最多有多少奖品
思路:
dp[i] [j] ,i 表示第 i 个数字, j 表示前面减了几次一;
cc 数字 i 全部累加情况 (无减一)- j, 这里有一个坑就是 cc 可能小于 0, 一定要 while(cc<0)cc+h; 而不是 (cc+h)%h, 因为这个 h 可能过小.//u1s1, 比赛的时候如果写出, 也会在这里被 hack, 因为惯性思维下意识写了 (cc+h)%h
状态转移方程就是
- k=(l<=cc && r>=cc);
- dp[i][j]=max(dp[i-1][j-1]+k,dp[i-1][j]+k); (当 j==0 的时候特判一下, 因为没有 - 1 这种)
最后比较 max(dp[n] [i] 0<=i<=n) 中
- #include<iostream>
- #include<map>
- #include<set>
- #include<queue>
- #include<stdio.h>
- #include<string.h>
- #include<algorithm>
- using namespace std;
- #define ll long long
- #define ull unsigned long long
- #define il inline
- #define it register int
- #define inf 0x3f3f3f3f
- #define lowbit(x) (x)&(-x)
- #define pii pair<int,int>
- #define mak(n,m) make_pair(n,m)
- #define mem(a,b) memset(a,b,sizeof(a))
- #define mod 998244353
- const int maxn=2e3+10;
- int n,m,t,h,l,r;
- int a[maxn],dp[maxn][maxn];
- int zhi[maxn][2];
- int main(){
- scanf("%d%d%d%d",&n,&h,&l,&r);
- int ans=0,c=0;mem(dp,0);
- for(it i=1;i<=n;i++){
- scanf("%d",&a[i]);
- }
- for(it i=1;i<=n;i++){
- c+=a[i];c%=h;
- if(l<=c && r>=c){
- dp[i][0]=dp[i-1][0]+1;
- }
- else{
- dp[i][0]=dp[i-1][0];
- }
- for(it j=1;j<=i;j++){
- int cc=(c-j+h)%h;while(cc<0){cc+=h;}
- if(l<=cc && r>=cc){
- dp[i][j]=max(dp[i-1][j-1]+1,dp[i-1][j]+1);
- }
- else{
- dp[i][j]=max(dp[i-1][j-1],dp[i-1][j]);
- }
- }
- }
- for(int i=0;i<=n;i++){
- ans=max(dp[n][i],ans);
- }
- printf("%d\n",ans);
- return 0;
- }
- View Code
F 是个树
来源: http://www.bubuko.com/infodetail-3459762.html