好久没有写博客了，回来热热手顺便找找感觉（gugugu）
这次因为下午刚打完训练赛又恰巧打的成绩不好，所以基本上没出几题（又掉了一波分），只能现在补补题了。
A. Ilya and a Colorful Walk
题目大概就是说从最大的两个不同颜色的距离是多少。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define mm(i,v) memset(i,v,sizeof i);
using namespace std;
typedef long long ll;
const int maxn=300000+10;
int a[maxn];
int main()
{
int x,n,y;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
if(a[0]!=a[n-1]){
printf("%d\n",n-1);
return 0;
}
for(int i=1;i<n;i++){
if(a[i]!=a[i-1]){
x=n-i-1;
break;
}
}
for(int i=n-2;i>=0;i--){
if(a[i]!=a[i+1]){
y=i;
break;
}
}
int maxx=max(x,y);
printf("%d",maxx);
return 0;
}
大概就是一个h×2的冰箱，给你一堆瓶子，让你按顺序放，求最多能放几瓶。
考虑贪心的做法，每次最大的次大并排放才能保证放的最多，所以我们只需要枚举放几个就行了，时间复杂度 n×n×log.
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define mm(i,v) memset(i,v,sizeof i);
using namespace std;
typedef long long ll;
int n,h;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>h;
vector<int> a(n);
for(int i=0;i<n;i++)
cin>>a[i];
for(int k=n;k>=0;k--){
vector<int> b(a.begin(),a.begin()+k);
sort(b.begin(),b.end());
ll sum=0;
for(int i=(int)b.size()-1;i>=0;i-=2)
sum+=b[i];
if(sum<=h){
cout<<k<<"\n";
return 0;
}
}
return 0;
}
C. Ramesses and Corner Inversion
题意：每次只能变换最少2*2的矩阵的四角，0变1,1变0，然后问给出两个矩阵能不能通过上述变换变得相等。
思路：每次贪心的变换最小的矩阵，也就是2 * 2如果发现这种变换到最会一行或一列出现不等，因为最后一行或一列无法再进行2 * 2的变换了，也就证明不能。否则，就证明可以通过上述变换使两矩阵相等。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define mm(i,v) memset(i,v,sizeof i);
using namespace std;
typedef long long ll;
//const int maxn=505;
//int a[maxn][maxn],b[maxn][maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
cin>>n>>m;
vector<vector<int> > a(n,vector<int>(m));
vector<vector<int> > b(n,vector<int>(m));
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
cin>>a[i][j];
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
cin>>b[i][j];
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(a[i][j]!=b[i][j]) {
if(i==n-1||j==m-1) {
cout<<"No"<<'\n';
return 0;
}
a[i][j]^=1;
a[i+1][j]^=1;
a[i][j+1]^=1;
a[i+1][j+1]^=1;
}
}
}
cout<<"Yes"<<'\n';
return 0;
}
D. Frets On Fire
首先这题要先理解离散化的知识，不懂的小伙伴请戳这里
接下来就是题意，就是求一个数矩阵，给你了每行的开头，让你求出每个段内有多少个不同的数。
注意到数据达到10^18，所以肯定是要离散化的。
具体思路就是
现在，我们可以把每一行看作一个 [s[i],s[i]+r-l] 的闭区间，于是我们把这n个闭区间放到数轴上，如果没有重合，那么答案就是n*(r-l+1)了，但显然区间重合是可能存在的。最暴力的想法就是初始化一个mark[值域]数组，对每一个区间里的数字逐个mark上，最后再遍历值域。然而这玩意儿一次询问就是O(n*值域)，显然不行。
这时我们观察数轴上的这n个闭区间，发现他们无论何时（每组询问）的长度都是一致的，因此我们可以把这些区间分成两类：如果对于一个区间I = [xi,yi]， 存在区间J = [xj,yj], 使得xj <= yi，我们说区间I是”贡献确定“的，因为由于区间长度一致，区间I在yi之后的数字都可以由区间J所替代，所以此时区间I的贡献确定为yi-xi。相反地，如果不存在这样的区间J，那么区间I就是”贡献不确定“的，他的贡献与区间长度有关（其实就是长度+1，闭区间嘛）。
回到这道题，每个询问等价的那个参数（记作q[k], q[k] = rk-lk），本质上就是那个区间长度，所以我们知道对于每个”贡献不确定“的区间，他的贡献是q[k] + 1。那对于”贡献确定“的区间。。。废话他们的贡献都确定了好吗。那这个确定的贡献是多少呢，我们可以把这n个区间排个序，排好序之后第i个区间的确定贡献（也就是最大的贡献，记作t[i]）就是 t[i] = s[i+1] - s[i] , 也就是他和下一个区间开头的距离了。最后，判断一个区间是否确定贡献的方式就是判断t[i] 与 q[k] 的大小关系，如果t[i] <= q[k], 那么他的区间尾就碰到了下一个区间头，贡献就确定为t[i]了。我们可以将 t[i] 排序，二分查找有多少个区间为确定贡献的。
那么，对于每一个询问 q[k], 覆盖的数字的个数 ans[k] = Σpi=1t[i] + (n-p) * (rk-lk+1), 其中p代表有且仅有前p小的t[i] 小于q[k]。需要前缀和数组sum[p]记录前p个t[i] 的和。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define mm(i,v) memset(i,v,sizeof i);
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int n,q;
ll s[maxn],t[maxn];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=0;i<n;i++)
cin>>s[i];
sort(s,s+n);
for(int i=0;i<n-1;i++)
s[i]=s[i+1]-s[i];
sort(s,s+n-1);
for(int i=n-1;i>=1;i--)
s[i]=s[i-1];
s[0]=0;
for(int i=1;i<n;i++)
t[i]=t[i-1]+(s[i]-s[i-1])*(n-i+1);
cin>>q;
for(int i=0;i<q;i++){
ll l,r;
cin>>l>>r;
l=r-l+1;
int temp=lower_bound(s,s+n,l)-s-1;
cout<<t[temp]+(l-s[temp])*(n-temp);
if(i!=n-1)
cout<<" ";
else
cout<<"\n";
}
return 0;
}
E. Pavel and Triangles
题意：给你一个数，代表从2^0 到 2n次方的每个木棍数。让你来匹配三角形，求最多匹配的三角形数量。
题解：优先匹配小的，最后把剩下的一个跟别两个一样的匹配。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define mm(i,v) memset(i,v,sizeof i);
using namespace std;
typedef long long ll;
const int maxn=3e5+10;
int a[maxn];
ll ans;
int n,t,res;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int j;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
j=min(a[i]>>1,t);
a[i]-=(j<<1);
t-=j;
ans+=j;
ans+=(a[i]/3);
a[i]%=3;
t+=a[i];
}
cout<<ans;
return 0;
}