Codeforces Round #672 (Div. 2) A~D(日更，慢慢来）

 （说实话我很佩服这上面的题，英语描述了这么多，，，，就让我拍排个序呗．．．．我谷歌翻译都搬出来了差点被它的cube搞晕QAQ)

那个n*(n-1)/2-1绝对是某种特殊情况，，，，这样一看，就是那个等差数列的和，，，，所以说，除非是完全递减，才会出现NO的情况

（cf上的题很考思维.....这个我真的是很佩服很佩服的）

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <stack>
 4 #include <vector>
 5 #include <math.h>
 6 #include <string>
 7 #include <algorithm>
 8 #include <unordered_map>
 9 #include <map>
10 #include<set>
11 #include <cstring>
12 #include <queue>
13 
14 #include <stdio.h>
15 #include <stdlib.h>
16 #define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
17 #define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量，a为初始值，n为界限值，递增
18 using namespace std;
19 const int maxn=1e5;
20 int n;
21 int a[maxn];
22 int main(){
23     int num;
24     while(cin>>n){
25         while(n--){
26             cin>>num;
27             rep(i,0,num-1){
28                 cin>>a[i];
29             }
30             bool flag=false;
31             rep(i,0,num-2){
32                 if(a[i]<=a[i+1]){
33                     flag=true;
34                     break;
35                 }
36             }
37             if(flag){
38                 cout<<"YES"<<endl;
39             }
40             else{
41                 cout<<"NO"<<endl;
42             }
43         }
44 
45     }
46     return 0;
47 }

 位运算啊，，，，，呐呐呐呐那就再说吧！！！不会咕不会咕一定来一定来！！！！！！！！！！！

我回来了，，，如果最高位相同的话，那么进行与操作可以还是为1，

进行异或操作就变为0了，而判断两个数的大小比较的就是最高位，所以我们在进行过程中只要判断最高位就行

呐呐呐呐呐，人家大佬都是有手就行，，，，我我我我我我这块还是好好写写吧！

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <stack>
 4 #include <vector>
 5 #include <math.h>
 6 #include <string>
 7 #include <algorithm>
 8 #include <unordered_map>
 9 #include <map>
10 #include<set>
11 #include <cstring>
12 #include <queue>
13 
14 #include <stdio.h>
15 #include <stdlib.h>
16 #define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
17 #define rep(i,a,n) for (int i=a;i<n;i++)//i为循环变量，a为初始值，n为界限值，递增
18 #define ll long long
19 const int maxn = 1e5+6;
20 using namespace std;
21 ll a[maxn];
22 ll n;
23 int main() {
24     //IOS;
25     //cout<<"n="<<n;
26     while (cin >> n) {
27         while (n--) {
28             int num;
29             cin >> num;
30            // cout<<num<<"=num";
31             map<ll, ll> m;
32             for (int i = 0; i < num; ++i) {
33                 cin >> a[i];
34             }
35 //            for (int i = 0; i < num; ++i) {
36 //                cout<<a[i]<<" ";
37 //            }
38             ll ans = 0;
39             for (int j = 0; j < num; ++j) {
40                 ll st = 1;
41                 int pos = 0;
42                 while (st * 2 <= a[j]) {//找最高位（*2是它的下一位）
43                     st <<= 1;
44                     pos++;
45                 }
46                 ans += m[pos];//参考了别人的代码，，，，这里很巧妙，，就是当前数跟原来的配对
47                 //其实直接公式也可以，但是没有这样快
48                 m[pos]++;
49 
50             }
51             cout << ans<<endl;
52 
53         }
54     }
55 
56 }

 （请问为啥每个题题意都这么难懂哦）

这个是个dp

那么我们定义状态点为 d p [ i ] [ 0 ] dp[i][0] dp[i][0]表示为到达第 i i i个元素时结尾进行 + + +操作的最大值，那么下一步自然是要   ? \ -  ?， d p [ i ] [ 1 ] dp[i][1] dp[i][1]表示为到达第 i i i个元素时结尾进行   ? \ -  ?操作的最大值，那么下一步自然是要 + + +。 到了这里就很明显了，两个状态点相互转移，我们可以进行的操作即为选或不选，那么状态转移方程自然好写，即为：
d p [ i ] [ 0 ] = m a x ( d p [ i ? 1 ] [ 0 ] , d p [ i ? 1 ] [ 1 ] + a [ i ] ) dp[i][0]=max(dp[i-1][0],dp[i-1][1]+a[i]) dp[i][0]=max(dp[i?1][0],dp[i?1][1]+a[i])
d p [ i ] [ 1 ] = m a x ( d p [ i ? 1 ] [ 1 ] , d p [ i ? 1 ] [ 0 ] ? a [ i ] ) dp[i][1]=max(dp[i-1][1],dp[i-1][0]-a[i]) dp[i][1]=max(dp[i?1][1],dp[i?1][0]?a[i])

我，先咕为敬，，，，一会儿写嘿嘿

Codeforces Round #672 (Div. 2) A~D(日更，慢慢来）

原文：https://www.cnblogs.com/zhmlzhml/p/13732993.html