A - Sorted Adjacent Differences
题意：
给定一个序列，要求将它们排序使得i与i+1的差小于i+1与i+2小于i+2与i+3，依次排序。
题解：
先将它们从小到大排序，差最大值的肯定是最小的和最大的，然后差第二个就是最大的和次小的，第三个是次小的和次大的，依次输出就好了，注意下n为奇数的情况。
代码：
#include<bits/stdc++.h> using namespace std; int main(){ int t,n; int g; cin>>t; while(t--){ g=0; scanf("%d",&n); int a[n+10],b[n+10]; for(int i=0;i<n;i++){ scanf("%d",&a[i]); } sort(a,a+n); for(int i=0;i<n/2;i++){ b[g]=a[n-1-i]; g++; b[g]=a[i]; g++; } if(n%2!=0){ b[g]=a[n/2]; g++; } for(int i=g-1;i>=0;i--){ printf("%d ",b[i]); } cout<<endl; } return 0; }
B - Powered Addition
题意：
给定一个序列，要求使它们变成后面一个数都比前面的数大于等于，再每一秒可以对它们任何数字加2^(s-1),s是秒数，问多少秒可以把它们变成这样的序列。
题解：
其实就是一个遍历，只要遇到后面的数比前面最大的数小的话，把它们标记下，找出一个数与最大的数差最多的值记为x，这样只有2^(s-1）>=x时，是最小的秒数。例如（1，7，6，5，就是在6的时候比7小所以起码要加到7，5的话也要加到7，它们之间差值最大为2，也就是2秒才可以）
代码：
#include<bits/stdc++.h> using namespace std; int main(){ int t; cin>>t; while(t--){ int n; scanf("%d",&n); int a[n+10]; cin>>a[0]; int maxn=a[0]; int x=0; for(int i=1;i<n;i++){ scanf("%d",&a[i]); maxn=max(maxn,a[i]); if(maxn>a[i]){ x=max(x,maxn-a[i]); } } //cout<<x<<endl; int ans=0; while(x>0){ x=x-pow(2,ans); ans++; } printf("%d ",ans); } return 0; }
C - Middle Class
题意：
给定n个数，它们之间可以加起来除以它们的个数，问最终有多少个数大于等于x
题解：
先把它们从大到小排序（如果最大的都比x小，那就是0）然后设一个sum为这些数加起来的和，如果平均数大于等于x的话就继续，否则就break，因为后面的数更小平均数更小。
代码：
#include<bits/stdc++.h> #define ll long long #define N 500001 using namespace std; bool cmp(int p,int q){ return p>q; } int main(){ ll t; ll n,x,ans; double sum; int a[N]; cin>>t; while(t--){ memset(a,0,sizeof(a)); sum=0; ans=0; cin>>n>>x; for(int i=0;i<n;i++){ cin>>a[i]; } sort(a,a+n,cmp); // for(int i=0;i<n;i++){ // cout<<a[i]<<endl; // } for(int i=0;i<n;i++){ sum+=a[i]; if(sum/(i+1)>=x){ ans++; } else{ break; } } cout<<ans<<endl; } return 0; }
E - Kind Anton
题意：
给定一个a数组和b数组长度一样（a只有1 0 -1），可以把ai加到aj上（i<j)，问能否使得把a变成b。
题解：
如果ai<bi只要判断i前面的a是否有1，有1的话就可以把ai变成bi了，如果ai>bi判断i前面的a是否有-1，有-1的话就可以把ai变成bi，如果都不满足这个条件就break。
代码：
#include<bits/stdc++.h> using namespace std; signed main() { int T; cin >> T; while(T--) { int n; cin>>n; int a[n+10],b[n+10]; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++) cin>>b[i]; int flag1=0,flag2=0; int flag =0; for(int i=0;i<n;i++){ if(a[i]<b[i]&&flag1==0) { flag = 1; break; } if(a[i]>b[i]&&flag2==0) { flag =1; break; } if(a[i]<0) flag2 = 1; if(a[i]>0) flag1= 1; } if(flag==1) cout<<"NO"<<endl; else cout<<"YES"<<endl; } return 0; }
D - Circle of Monsters
题意：
有n个怪物围成一圈，每个怪物都有hp，消灭一个怪物会对下一个怪物造成x的伤害，你有一把武器，一个子弹一次只能打1hp，问如何使得你发射的子弹数量最少而消灭所有怪物。
题解：
根据例题：a1=7 b1=15 a2=2 b2=14 a3=5 b3=3 如果从a1开始打先需要打出a1发子弹，然后对a2造成了b1，因为b1>a2就不需要子弹，然后对a3造成了b2，也不需要子弹了，最终子弹就是a1=7.
如果从a2开始打的话，对a2需要发射2发子弹，然后对a3造成了b2伤害可以消灭a3，就不需要子弹，再对a1造成了b3，因为b3<a1，所以a1怪物没有消灭，还需要补上a1-b3的子弹，最终子弹是6。
从a3开始的话，最终子弹是9.
根据例题可以得到 a1+(a2-b1)+(a3-b2) a2+(a3-b2)+(a1-b3) a3+(a1-b3)+(a2-b1) ，再把数据从环形变成直线，求前缀和（就是打死怪物需要的子弹）。（借鉴大佬题解）
代码：
#include<bits/stdc++.h> #define maxn 600010 #define LL long long using namespace std; LL a[maxn],b[maxn],c[maxn],sum[maxn]; int main(){ int t,n,i; LL mn; scanf("%d",&t); while(t--){ scanf("%d",&n); mn=1e18;//超出int范围的赋值 for(i=1;i<=n;i++)scanf("%lld%lld",&a[i],&b[i]); for(i=n+1;i<=2*n;i++)a[i]=a[i-n],b[i]=b[i-n];//变环形为直线 for(i=2;i<=2*n;i++)c[i]=((a[i]>b[i-1])?(a[i]-b[i-1]):0);//爆炸对应的子弹消耗 //c是每一个怪物消耗的子弹 //sum是到这个怪物消耗的子弹 sum[1]=0; for(i=2;i<=2*n;i++)sum[i]=sum[i-1]+c[i];//前缀和 for(i=1;i<=n;i++) mn=min(mn,a[i]+sum[i+n-1]-sum[i]); printf("%lld ",mn); } return 0; }
F - Eugene and an array
题意：
给定一个序列，如果它的子序列加起来不为0那就是好序列（比如41，-41，41，好序列就是41，-41，41另外两个不论怎样都是有41和-41存在为0就是坏的）。
题解：
其实也不是子序列而应该是从左开始减或者从右开始减的序列。 包含a[i]总共有n个左边i-1个，右边n-i个加上自己1个。然后枚举a[i]往左边可以枚举多少个好序列，再把值相加。
那么很显然，左端点不可能在L3L3 L_3L3的前面。那么是不是相当于我们在枚举a[i]的时候要维护，和为0的区间的最大左端点？是的。
假设我们维护的这个最大左端点是max_l，那么对于每一个a[i]，我们让ans += i-max_l就好了。
维护就好了。可能难点在于怎么维护。我说说我的思路。我一看到区间和为0，我想到了前缀和，区间[i,j][i,j] [i,j][i,j]和为0等价于sum[i−1]=sum[j]sum[i−1]=sum[j] sum[i-1]=sum[j]sum[i−1]=sum[j]。那么我们可以先前缀和一下，然后考虑每一个a[i]的时候，直接找距离i最近的j且sum[j]=sum[i]。就能找到这个和为0的区间了，然后用这个更新max_l，再用max_l更新答案即可。
（大佬思路借鉴）
代码：
#include<bits/stdc++.h> using namespace std; const int maxn = 2e5 + 10; long long dp[maxn]; map<long long, int> rec;//维护每个前缀和最近一次出现的位置 void solve() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> dp[i], dp[i] += dp[i - 1]; rec[dp[i]] = -1; } long long ans = 0; int max_l = -1; rec[0] = 0; for (int i = 1; i <= n; i++) { if (rec[dp[i]] != -1) max_l = max(max_l, rec[dp[i]]); rec[dp[i]] = i; ans += i - (max_l + 1);//max_l表示前缀和相等的下标，而max_l+1才是实际的区间 } cout << ans; } int main() { solve(); return 0; }