A. Cubes Sorting
为何直接判断a[i] >= a[i-1]即可，因为(n -1)*n/2 是从小到大逆序后，恢复原状的操作数，我们只要保证其中一个数是正序的，就可以保证排序后操作数是正虚的。
#include<bits/stdc++.h> using namespace std; int T,n,a[50003]; int main(){ cin>>T; while(T--){ cin>>n; for(int i=0;i<n;i++) cin>>a[i];string ans="NO\n"; for(int i=1;i<n;i++) if(a[i]>=a[i-1]) ans="YES\n"; cout<<ans; } }B. Rock and Lever
a & b > a ^ b (i < j) 范围, 这也是考二进制
#include <bits/stdc++.h> using namespace std; int main(){ int t,n,x; cin>>t; while(t--){ long long ans=0,arr[32]={0}; cin>>n; for(int i=0;i<n;i++){ cin>>x; int sum=0; while(x/2>0){ x/=2; sum++; } ans+=arr[sum]; arr[sum]++; } cout<<ans<<'\n'; } }C1. Pokémon Army (easy version) 我们定义状态点为d p [ i ] [ 0 ] dp[i][0]dp[i][0]表示为到达第i ii个元素时结尾进行+ ++操作的最大值，那么下一步自然是要 − \ - −，d p [ i ] [ 1 ] dp[i][1]dp[i][1]表示为到达第i ii个元素时结尾进行 − \ - −操作的最大值，那么下一步自然是要+ ++。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 3e5 + 10; int t; ll arr[maxn]; ll dp[maxn][2]; int main() { scanf("%d",&t); while(t--) { int n,q; // memset(dp,0,sizeof(dp)); scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) { scanf("%lld",arr+i); dp[i][0] = max(dp[i-1][0],dp[i-1][1]+arr[i]); dp[i][1] = max(dp[i-1][1],dp[i-1][0]-arr[i]); } printf("%lld\n",max(dp[n][0],dp[n][1])); } // system("pause"); return 0; } //第二种写法 #include <bits/stdc++.h> #define li long long int using namespace std; int main(){ int t; cin>>t; while(t--){ int n; cin>>n; bool q; cin>>q; int a[n]; for(int i=0;i<n;i++) cin>>a[i]; li sum=a[0]; for(int i=1;i<n;i++) sum+=max(0,a[i]-a[i-1]); cout<<sum<<endl;} }C2. Pokémon Army (hard version) 解析：用dp会爆栈 比如5 4 3找的是5 3（在上面的例子中)找出来的差值其实就是(5 - 4) + (4 - 3) 找到的那个最小值，一定波峰和波谷的值程单调性，那这两个值之间所有数的两两之差就是答案 如果画一个模拟的图5-4-3直线可以发现中间的点差不多没有影响，其实也就是这些值之间的两两之差。 那么发现了这个之后，后面的操作就是相当于把这个数组里的两个数字位置改变一下，重新进行这样类似的操作。 交换前考虑一下l的前后是不是正数，如果是就减掉，r的前后是不是正数，如果是就减掉。注意l==r-1的情况特判，防止多加多减。包含在里面一个情况就好了。
#include<iostream> #include<vector> #include<queue> #include<cstring> #include<cmath> #include<map> #include<set> #include<cstdio> #include<algorithm> #define debug(a) cout<<#a<<"="<<a<<endl; using namespace std; const int maxn=3e5+100; typedef long long LL; LL a[maxn]; void solve() { LL n,q;cin>>n>>q; LL res=0; for(LL i=1;i<=n;i++) { cin>>a[i]; } for(LL i=1;i<=n;i++){ if(a[i]-a[i+1]>0) res+=(a[i]-a[i+1]); } cout<<res<<endl; while(q--) { LL l,r;cin>>l>>r; //交换的两个数，把他们的前驱和后继都还原 if(a[l-1]-a[l]>0) res-=(a[l-1]-a[l]); if(a[r-1]-a[r]>0&&l!=r-1) res-=(a[r-1]-a[r]); if(a[l]-a[l+1]>0) res-=(a[l]-a[l+1]); if(a[r]-a[r+1]>0) res-=(a[r]-a[r+1]); swap(a[l],a[r]); //然后再进行操作 if(a[l-1]-a[l]>0) res+=(a[l-1]-a[l]); if(a[r-1]-a[r]>0&&l!=r-1) res+=(a[r-1]-a[r]); if(a[l]-a[l+1]>0) res+=(a[l]-a[l+1]); if(a[r]-a[r+1]>0) res+=(a[r]-a[r+1]); cout<<res<<endl; } } int main(void) { cin.tie(0);std::ios::sync_with_stdio(false); LL t;cin>>t; while(t--) { memset(a,0,sizeof(a)); solve(); } return 0; }D. Rescue Nibel!
通过零和一的不同来辨别到底是开灯时间还是关灯时间来确定是否在时间段内。
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 3e5 + 10, mod = 998244353; LL f[N], inf[N], sum; int n, k, db; vector<pair<int, int>> s; LL qmi(LL a) { LL p = mod - 2, ans = 1; while(p) { if(p & 1) ans = (ans * a) % mod; p >>= 1; a = (a * a) % mod; } return ans; } int main() { cin >> n >> k; //k--是因为我有一盏灯是必须要选的 k -- ; f[0] = inf[0] = 1; for(int i = 1; i <= n; i ++ ) { f[i] = f[i - 1] * i % mod; inf[i] = inf[i - 1] * qmi(i) % mod; int x, y; cin >> x >> y; s.push_back({x, 0}); s.push_back({y, 1}); } sort(s.begin(), s.end()); for(int i = 0; i < 2 * n; i ++ ) { if(s[i].second == 0) db ++ ; else { db -- ; //和k--一样 if(db >= k) sum += f[db] * inf[k] * inf[db - k] % mod; sum %= mod; } } cout << sum << endl; return 0; }