题目链接：https://codeforces.com/contest/1119
A. Ilya and a Colorful Walk
题意：
给出n个数，问从一个数到另外一个不同数的最长距离是多少。
题解：
从前往后，从后往前扫两遍即可。证明可用反证法，这里略去。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + ;
int n;
int c[N];
int main() {
ios::sync_with_stdio(false);cin.tie();
cin >> n;
for(int i = ; i <= n ;i++) {
cin >> c[i] ;
}
int ans = ;
for(int i = ; i <= n ;i++) {
if(c[i] != c[]) ans=max(i - , ans);
}
for(int i = n - ; i >= ; i--) {
if(c[i] != c[n]) ans=max(n - i, ans);
}
cout << ans;
return ;
}
B. Alyona and a Narrow Fridge
题意：
给一个冰箱n行2列，然后n个瓶子，每个瓶子都有一个高度。现在要把最多的前k个瓶子放进冰箱里面去，最后会形成若干个隔层，每个隔层中最多两个瓶子。现在要求确定这个k最大为多少。
题解：
放瓶子的话肯定是贪心放的，将最高的尽可能放入一个隔层中。最后二分判断一下就行了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + ;
int n, h;
int a[N], b[N];
bool check(int x) {
for(int i = ; i <= x ; i++) b[i] = a[i];
sort(b + , b + x + ) ;
int tmp = h;
for(int i = x; i >= ; i -= ) {
int j = max(, i - ) ;
tmp -= max(b[i], b[j]) ;
if(tmp < ) break ;
}
return tmp >= ;
}
int main() {
ios::sync_with_stdio(false);cin.tie();
cin >> n >> h;
for(int i = ; i <= n ;i++)
cin >> a[i] ;
int l = , r = n + , mid ;
while(l < r) {
mid = (l + r) >> ;
if(check(mid)) l = mid + ;
else r = mid;
}
cout << l - ;
return ;
}
C. Ramesses and Corner Inversion
题意：
给出两个n*m的01矩阵，现在每次可以选择任意一个有四个角的子矩阵（不存在为长度为1的边），并且将四个角取反，问最后是否能将第一个矩阵变为第二个矩阵。
题解：
考虑每次选择(1,1),(1,y),(x,1),(x,y)这样的四个点，那么我们就能够让所有除开第一行第一列的值都与第二个矩阵相等。
现在就只剩下第一行第一列了，如果每行、每列的奇偶性两个矩阵相等，那么剩下的第一行第一列必然也与第二个矩阵相等的。所以就这么判断一下就好了。
代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = ;
int a[N][N], b[N][N] ;
int n, m ;
int main() {
ios::sync_with_stdio(false);cin.tie();
cin >> n >> m ;
for(int i = ; i <= n ; i++) {
for(int j = ; j <= m ; j++) {
cin >> a[i][j] ;
}
}
for(int i = ; i <= n ; i++) {
for(int j = ; j <= m ; j++) {
cin >> b[i][j] ;
}
}
int f = ;
for(int i = ; i <= n ; i++) {
int cnt1 = , cnt2 = ;
for(int j = ; j <= m ; j++) {
if(a[i][j]) cnt1++;
if(b[i][j]) cnt2++;
}
if((cnt1 & ) != (cnt2 & )) f = ;
}
for(int i = ; i <= m ; i++) {
int cnt1 = , cnt2 = ;
for(int j = ; j <= n ; j++) {
if(a[j][i]) cnt1++;
if(b[j][i]) cnt2++;
}
if((cnt1 & ) != (cnt2 & )) f = ;
}
if(f) cout << "No" ;
else cout << "Yes" ;
return ;
}
D. Frets On Fire
题意：
给出n个数字，然后有多个询问，每次询问一个区间[L,R]，回答这n个数字从L起加到R中所有数的集合中有多少个元素。
题解：
首先可以发现这题中数的位置顺序不影响答案，那么我们可以对其排序。接下来就考虑每一个数的贡献。
假设我们现在考虑ai的贡献，设di = ai+1 - ai，D = R - L，如果di <= D，那么很显然贡献就为di；如果di > D，此时贡献就为D，因为多出的那一部分必然会被ai+1给遍历到，我们之后考虑ai+1的时候计算就行了，这样就可以不重复也不遗漏了。
具体做法的话就需要维护差值前缀和，然后对于每次询问二分查找位置，计算就行了。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + ;
int n;
ll a[N], s[N], sum[N]; int main() {
ios::sync_with_stdio(false);cin.tie() ;
cin >> n;
for(int i = ; i <= n; i++) {
cin >> a[i] ;
}
sort(a + , a + n + );
int l = unique(a + , a + n + ) - a - ;
for(int i = ; i < l ; i++) s[i] = a[i + ] - a[i] ;
sort(s + , s + l) ;
for(int i = ; i < l ; i++) sum[i] =sum[i - ] + s[i] ;
int q;
ll x, y;
cin >> q;
while(q--) {
cin >> x >> y ;
ll d = y - x + ;
int p = upper_bound(s + , s + l, d) - s - ;
ll ans = sum[p] ;
ans += 1ll * (l - p) * d;
cout << ans << ' ' ;
}
return ;
}
E. Pavel and Triangles
题意：
给出a0,a1...an-1，分别表示有a1个20长度的木棍，有a2个21长度的木棍...有an-1个2n-1长度的木棍。现在问怎么选取木棍，使得拼出三角形的数量最多（每个三角形由三根木棍拼成）。
题解：
通过分析就会发现，木棍的组合方式就只有(i,i,i)或者(i,j,j)，其中i < j。这两种方式都是需要3根木棍，我们考虑贪心的方法来选取:
从后往前遍历，统计当前对数pairs，如果当前有奇数个并且pairs > 0，那么我们就用这剩下的一个随便与后面的一个pair配对，这样肯定是最优的。最后利用pairs统计答案即可。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = ;
int n;
int a[N];
int main() {
ios::sync_with_stdio(false);cin.tie();
cin >> n;
for(int i = ; i <= n ; i++) cin >> a[i] ;
ll pairs = ;
ll ans = ;
for(int i = n ; i >= ;i--) {
pairs += a[i] / ;
if(a[i] & && pairs > ) {
ans++;
pairs--;
}
}
ans += pairs * / ;
cout << ans ;
return ;
}