题意：对于给定数列，求解 a[i] != a[j] 时 j-i+1 的最大值。
思路：对于任意数列，假设存在某两个数字(ap，aq)不同，并且假设最长的区间就是[p,q]：a1,a2......ap,ap+1......aq......an；
那么对于这个序列，显然ap左边的数字都必须等于aq，否则就出现了更长的区间，右边也同理。
如此我们发现对于这个数组，a1 == ap，an == aq。显然最大的区间变成了整个数组。
所以，无论什么数组，最长的区间一定是从左端点开始，或者到右端点结束的。所以这道题只需要暴力的找一遍就好了。
1 #include2 using namespace std; 3 4 int a[300005]; 5 int main(){ 6 int n;cin >> n; 7 for(int i = 0;i < n;i ++){ 8 cin >> a[i]; 9 }10 int ans = 0;11 int L = 0;int R = n - 1;12 while(L <= R){13 if(a[L] != a[R]){14 ans = max(ans,R - L);15 }16 L ++;17 }18 L = 0;R = n - 1;19 while(L <= R){20 if(a[L] != a[R]){21 ans = max(ans,R - L);22 }23 R --;24 }25 cout << ans << endl;26 27 return 0;28 }
题意：有一个架子高度已知为 m，宽度为2，但是只能摆一排东西。现在有若干个东西，宽度都是1，但是高度不等。
我们要依次地将这些东西摆到架子上，我们可以事先在架子上的整数高度搭上数量随意的木板，一旦搭上木板，这个架子就被彻底分成两层。再搭一块就变成三层。。。
高度大于某一层的高度的话，这个东西就摆不到架子上。求解最多依次摆放多少个物品。
思路：一开始被这给唬住了，一时没想到方案，后来发现是个二分。
对于这个架子，每次二分的 mid 都代表可以从第一个摆到第 mid 个，那么对于1到 mid 的所有高度降序排序，每次处理两个物品的最大高度。
如果这些高度的和超过了货架的总高度 m，那么就不能成功摆放。（又因为 longlong WA了一发）
1 #include2 using namespace std; 3 4 int n; 5 long long m; 6 int a[1005]; 7 8 int check(int x){ 9 int b[1005];10 for(int i = 1;i <= x;i ++){11 b[i] = a[i];12 }b[x + 1] = 0;13 sort(b + 1,b + 1 + x,greater ());14 // for(int i = 1;i <= x;i ++){15 // cout << b[i] << " ";16 // }cout << endl;17 long long now = 0;18 for(int i = 1;i <= x;i += 2){19 now += max(b[i],b[i + 1]);20 }21 if(now <= m){ return 1;}22 return 0;23 }24 25 int main(){26 cin >> n;27 cin >> m;28 for(int i = 1;i <= n;i ++){29 cin >> a[i];30 }31 int L = 1;int R = n;32 while(L < R){33 int mid = L + R + 1;34 mid /= 2;35 //cout << mid << " " << check(mid) << endl;36 if(check(mid) == 1){37 L = mid;38 }39 else{40 R = mid - 1;41 }42 }43 cout << L << endl;44 45 return 0;46 }
题意：给定两个大小相同的 01 矩阵，规定一种操作：选择一个第一个矩阵的子矩阵，将子矩阵的四个角取反。但是这个子矩阵至少应该是 2*2 的。
求解第一个矩阵能否在有限步骤之内变成第二个矩阵。
思路：口胡的答案竟然就过了。其实就是记录两个矩阵不一样的地方，因为你每次变动都是某两行改变两个数并且某两列改变两个数。
所以如果有某行或者某列的不同点是奇数个，那么就不能转化。
1 #include2 using namespace std; 3 4 int a[505][505]; 5 int b[505][505]; 6 int c[505][505]; 7 int main(){ 8 memset(c,0,sizeof(c)); 9 int n;cin >> n;10 int m;cin >> m;11 for(int i = 0;i < n;i ++){12 for(int j = 0;j < m;j ++){13 cin >> a[i][j];14 }15 }16 for(int i = 0;i < n;i ++){17 for(int j = 0;j < m;j ++){18 cin >> b[i][j];19 if(a[i][j] != b[i][j]){20 c[i][j] = 1;21 }22 }23 }24 int f = 1;25 for(int i = 0;i < n;i ++){26 int cnt = 0;27 for(int j = 0;j < m;j ++){28 if(c[i][j] == 1){cnt ++;}29 }30 if(cnt % 2){f = 0;break;}31 }32 for(int i = 0;i < m;i ++){33 if(f == 0){ break;}34 int cnt = 0;35 for(int j = 0;j < n;j ++){36 if(c[j][i] == 1){cnt ++;}37 }38 if(cnt % 2){f = 0;break;}39 }40 if(f){cout << "Yes" << endl;}41 else{cout << "No" << endl;}42 43 return 0;44 }
留坑，没想通。
题意：给定一个数组。ai 代表长度为 2的 i 次方的小木棍有 ai 个。问你这些木棍能组成多少个三角形。木棍不能复用。
思路：我们发现，对于任意三个不同长度的木棍，因为2的幂次的特性，是不会组成三角形的。所以符合题意的三角形一定是等腰或等边。
所以在这里贪心。一开始我的思路是能等边就等边，不能等边就和前面剩下的木棍组成等腰，傻了吧唧的交上去被 WA 回来。
后来发现贪心贪反了，应该是能等腰就等腰。
但是对于某个ai，要注意的是，如果是偶数，就是 ai/2 个等腰，并且消耗掉前面剩余的 ai/2 个小木棍，
如果是奇数，则会消耗掉 ai/2 - 1 个剩余小木棍，ai 中最后三个小木棍要变成等边。
从头计算一遍即可。
1 #include2 using namespace std; 3 4 int main(){ 5 long long n;cin >> n; 6 long long ans = 0; 7 long long m; 8 long long left = 0; 9 for(int i = 0;i < n;i ++){10 cin >> m;11 if(left * 2 <= m){12 m -= left;13 m -= left;14 ans += left;15 ans += m / 3;16 left = m % 3;17 }18 else{19 ans += m / 2;20 left -= m / 2 - m % 2;21 }22 }23 cout << ans << endl;24 25 return 0;26 }