不知不觉，也有一个多月没更新过了，现在打算一周更一次，整合自己在这一周的做题收获。(做题也只能是做很少的部分)
在上周中打了Codeforces1119——Codeforces Global Round 2，被打自闭了，后面又花了一些时间补了前五道题目。
PS：由于版面问题，题目就以截图形式，需要原题的同学可以自行去CF上查看。
A. Ilya and a Colorful Walk
题解：
-
题意：
有n个房子，编号为1~n，相邻编号的房子相邻(1与n不相邻)，这n个房子的颜色分别是、
、······、
，至少有两个房子的颜色是不同的。
每两个相邻之间的房子的距离为1，要求当两个房子i、j（）的颜色
时，这两个房子之间的最大距离。
-
题解：【贪心】
要求最大距离，那么两个房子i、j必须更加靠近两端断点1和n。
令i=1，j从2~n开始，遍历一遍，求出此时最大的距离max_1。
再令j=n，i从1~n-1开始，遍历一遍，求出此时最大的距离max_2。
再比较max_1和max_2的最大值，即为解。
(即从头、尾对数组c分别进行一次遍历，求出最大的距离)
参考代码：
#include<iostream>
#include<cstdio>
using namespace std;
int c[300010];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&c[i]);
}
int count=0;
int ans=0;
for(int i=n;i>1;i--)
{
if(c[i]!=c[1])
{
count=i-1;
break;
}
}
ans=max(ans,count);
for(int i=1;i<=n;i++)
{
if(c[n]!=c[i])
{
count=n-i;
break;
}
}
ans=max(ans,count);
//printf("i:%d;j:%d\n",i,j);
printf("%d\n",ans);
}
B. Alyona and a Narrow Fridge【思维】
题解：
-
题意：
现在有个的立体冰箱，可以在任何一个格子顶部放隔板，现在有一些牛奶盒按顺序放入冰箱（牛奶盒不能叠起来，只能放在隔板上），第
个牛奶盒为
的长方形，问最多能放几个牛奶盒。
-
题解：
将这些牛奶盒按照高度升序排序，假设现在
数组有
、
、
三个元素(牛奶盒的高度)，从右到左遍历数组
，则
【突破口：升序排序，从右到左遍历，如果
必定可以放入冰箱，即代码中的
】
注意这里牛奶盒是按照顺序开始放入冰箱的，所以，每输入一个
参考代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int h;
int a[1010];
bool cmp(int x,int y)// sort的比较函数，这里可忽略
{
if(x<y)return true;
else return false;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d%d",&n,&h);
while(~scanf("%d%d",&n,&h))
{
int i,j;
int flag=0;
int ans;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(flag==0)
{
sort(a+1,a+i+1,cmp);
//for(int k=1;k<=i;k++)
//printf("%d:%d ",k,a[k]);
//puts("");
long long sum=0;
for(j=i;j>=1;j-=2)
{
sum+=a[j];
}
if(sum<=h)
{
if(i==n)ans=n+1;// 如果加上最后一个牛奶盒，仍然<= h，那个最后一个牛奶盒也算入其中(这里n+1是因为输出结果时需要减去1)
}
else if(sum>h)// 当超过冰箱的高度h，ans记录第一个不满足的牛奶盒的索引
{
flag=1;
ans=i;
}
}
}
printf("%d\n",ans-1);// 最后需要减去1(因为此时ans为不满足条件的第一个牛奶盒的索引)
}
fclose(stdin);
fclose(stdout);
}
C. Ramesses and Corner Inversion【奇偶性、规律】
题解：
- 题意：
给你两个01矩阵（只含有0、1的矩阵)，你只能执行一种操作：就是取上面矩阵中的子矩阵，将子矩阵的四个角的值由零变一，由一变零。求能否通过上述操作让矩阵A等于矩阵B。 - 题解：
解法：【规律性】
观察发现，
- 如果任意一列(行)的任意两个1变为0，那么此时这一列(行)的奇偶性不会改变。
- 如果一列(行)中的恰有一个1和一个0需要改变，那么
、
，奇偶性仍然没有变。
综上的发现，如果矩阵A每一行、每一列的奇偶性与矩阵B对应的每一行、每一列的奇偶性相同，那么就说明可以通过上述的操作，从矩阵A变为矩阵B。
判断奇偶性，可以使用位操作中的&操作
if target$1==1：说明target为奇数
if target&1==0：说明target为偶数
参考代码：【代码略长。。。逃~】
#include<iostream>
#include<cstdio>
using namespace std;
int mat_a[505][505];// 矩阵A
int mat_b[505][505];// 矩阵B
int row_a[505];// 记录矩阵A每一行的奇偶性
int column_a[505];// 记录矩阵A每一列的奇偶性
int row_b[505];// 记录矩阵B每一行的奇偶性
int column_b[505];// 记录矩阵B每一列的奇偶性
int n,m;
int main()
{
//scanf("%d%d",&n,&m);
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
while(~scanf("%d%d",&n,&m))
{
int count_a=0;
int count_b=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&mat_a[i][j]);
count_a+=mat_a[i][j];
}
row_a[i]=(count_a&1);
count_a=0;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&mat_b[i][j]);
count_b+=mat_b[i][j];
}
row_b[i]=(count_b&1);
count_b=0;
}
count_a=0,count_b=0;
for(int j=1;j<=m;j++)
{
for(int i=1;i<=n;i++)
{
count_a+=mat_a[i][j];
count_b+=mat_b[i][j];
}
column_a[j]=(count_a&1);
column_b[j]=(count_b&1);
count_a=0,count_b=0;
}
int flag=0;
for(int i=1;i<=n;i++)
{
if(row_a[i]!=row_b[i])
{
flag=1;
break;
}
}
if(!flag)
{
for(int j=1;j<=m;j++)
{
if(column_a[j]!=column_b[j])
{
flag=1;
break;
}
}
if(flag)puts("No");
else puts("Yes");
}
else puts("No");
}
fclose(stdin);
fclose(stdout);
}
D. Frets On Fire【贡献计算 & 二分查找】
题解：参考博客
- 题意：这里就不过多赘述了
(主要是因为懒)，看一下题目的Note，其实就很明显了。 - 题解：
题目给出多组的L、R，判断从第L列到第R列中，不重复的数字有多少个。(还是说了一下题意，orz)
根据题意，我们可以发现而言，值越大，其对结果的贡献就可能最大。多个相同的
对数组进行升序排序，在算一个点的贡献时：
- 与后一个有重叠：
当，即
时，
与
重叠的部分，都算在
- 无重叠时，贡献为
-
的贡献一定是
最后再处理一下，计算前i个元素对应的贡献值的和，方便进行二分查找，详细看代码。
贡献计算：
我的理解是：有若干个可能的条件，对结果产生贡献，但是这些条件有些贡献是相同的，在计算总的贡献时，就需要剔除重复的贡献。
参考代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long s[100010];
long long contri[100010];
long long sum[100010];
int n;
int q;
long long l,r;
bool cmp(long long x,long long y)// sort的比较函数，这里可忽略
{
if(x<y)return true;
else return false;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++)scanf("%lld",&s[i]);
sort(s+1,s+n+1,cmp);
long long m=unique(s+1,s+n+1)-(s+1);// unique去除重复的s数组元素
//printf("unique:%d\n",m);
for(int i=1;i<m;i++)contri[i]=s[i+1]-s[i];// contri：记录贡献值
sort(contri+1,contri+m,cmp);// 对贡献值升序排序
for(int i=1;i<m;i++)sum[i]=sum[i-1]+contri[i];// 计算前i个的总贡献
scanf("%d",&q);
while(q--)
{
long long ans=0;
scanf("%lld%lld",&l,&r);
/*
// 直接遍历，TLE，需要二分查找
for(int i=1;i<m;i++)
{
long long temp=contri[i]<(r-l+1)?contri[i]:(r-l+1);
ans+=temp;
}
ans+=(r-l+1);
*/
// upper_bound：(大于)二分查找，找到最一个比r-l的位置，即第一个r-l+1的位置
int pos=upper_bound(contri+1,contri+m,r-l)-contri;
ans=sum[pos-1]+(r-l+1)*(m-pos+1);
// 分成大[于等于r-l+1]和[小于r-l+1]两段，相加即为最后的结果
printf("%lld ",ans);
}
puts("");
}
fclose(stdin);
fclose(stdout);
}
E. Pavel and Triangles【思维】
题解：
- 题意：
有一个数组、
，表示长度为
、
、
……
分别的木棒的数量，问：这些木棍最多可以组成的三角形的个数。
- 题解：
首先，根据三角形三边关系，（
&&
），
、
、
不可能组成一个三角形。
所以，要组成三角形，只能是等腰三角形或者等边三角形
。
构成三角形要么等边，要么等腰，等腰的话另外一边只能取小的，
如果小的有剩余，当然拿出2个大的来构成等腰更划算，如果没有那么就本身构成等边。
即temp=min(num/2,last)；
参考代码：
#include<iostream>
#include<cstdio>
using namespace std;
int n;
long long num;
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
//scanf("%d",&n);
while(~scanf("%d",&n))
{
long long last=0,ans=0;// last：前面剩余的
long long temp;// 与前面剩余的形成等腰三角形的个数
for(int i=1;i<=n;i++)
{
scanf("%lld",&num);
// 如果小的边有剩余
if(last)
{
temp=min(num/2,last);
ans+=temp;
last-=temp;
num-=temp*2;
}
ans+=num/3;
last+=num%3;
}
printf("%lld\n",ans);
}
fclose(stdin);
fclose(stdout);
}
写在最后：
还有三道题目没有补（其实是不会做），感兴趣的（大佬们）可以去AK，我（蒟蒻）就算了，等后面会做了再来更新吧。
附上几份题解：
- codeforces上的题解
- zhouyuheng2003
- ccosi
- D题参考：https://www.cnblogs.com/AlphaWA/p/10664509.html
Per Week，Hard Work！不管别人怎么样，坚持自己的选择，不为什么，只是喜欢。
网友评论