【Codeforces Global Round 2】A-E题解 【Frets On Fire、Pavel and Triangles】
狄钧
A. Ilya and a Colorful Walk：
题意:
n
n
n个数，每个数都有一个属性，还有一个值。要求找到两个数，数字属性不同，求出最大的数字差值。
思路: 简单题，直接对所有数字排序，对于最大值找一个与其属性不同的最小值，再对于最小值，找一个与其属性不同的最大值，比较求出最大差值即可。
代码:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define LOG1(x1,x2) cout << x1 << ": " << x2 << endl;
#define LOG2(x1,x2,y1,y2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << endl;
#define LOG3(x1,x2,y1,y2,z1,z2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << " , " << z1 << ": " << z2 << endl;
typedef long long ll;
typedef double db;
const int N = 3*1e5+100;
const int M = 1e5+100;
const db EPS = 1e-9;
using namespace std;
int mp[N][2],n;
int main()
{
memset(mp,-1,sizeof mp);
scanf("%d",&n);
rep(i,1,n) mp[i][0] = -1, mp[i][1] = 1e7;
rep(i,1,n){
int xx; scanf("%d",&xx);
mp[xx][0] = max(mp[xx][0],i);
mp[xx][1] = min(mp[xx][1],i);
}
int maxn = -1, pos, ans = -1, minn = 1e7;
rep(i,1,n){
if(mp[i][0] > maxn){
maxn = mp[i][0];
pos = i;
}
}
rep(i,1,n){
if(i != pos && mp[i][0] != -1) ans = max(ans,maxn-mp[i][1]);
}
rep(i,1,n){
if(mp[i][1] < minn){
minn = mp[i][1];
pos = i;
}
}
rep(i,1,n){
if(i != pos && mp[i][1] != 1e7) ans = max(ans,mp[i][0]-minn);
}
printf("%d\n",ans);
return 0;
}
B. Alyona and a Narrow Fridge
题意: 一个高度为
h
h
h的冰箱，冰箱内一共两列。现在有
n
n
n个物品，需要往冰箱中进行插板，使得前
k
k
k个物品能放入冰箱，求
k
k
k的最大值。
(
1
≤
n
≤
1
0
3
)
(1\leq n \leq 10^3)
(1≤n≤103)
思路: 由于
n
n
n比较小，直接枚举k即可，然后将前
k
k
k个物品排序，倒序放入冰箱，判断是否可以成功即可完成此题。当然也可以将枚举改为二分，也可以通过此题。
代码:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define LOG1(x1,x2) cout << x1 << ": " << x2 << endl;
#define LOG2(x1,x2,y1,y2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << endl;
#define LOG3(x1,x2,y1,y2,z1,z2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << " , " << z1 << ": " << z2 << endl;
typedef long long ll;
typedef double db;
const int N = 1000+100;
const int M = 1e5+100;
const db EPS = 1e-9;
using namespace std;
int n,h,a[N];
int solve(int x)
{
int tmp[N], th = h;
rep(i,1,x) tmp[i] = a[i];
sort(tmp+1,tmp+1+x);
int i = x, j = max(i-1,1), ans = 0;
while(i >= 1 && th > 0){
if(th < tmp[i]) break;
else if(max(tmp[i],tmp[j]) <= th){
ans += 1;
if(i != j) ans++;
th -= max(tmp[j],tmp[i]);
i = j-1, j = max(i-1,1);
}
else if(a[j] <= h){
ans += 1;
break;
}
}
if(ans != x) return 0;
else return 1;
}
int main()
{
scanf("%d%d",&n,&h);
rep(i,1,n) scanf("%d",&a[i]);
int ans = 0;
// sort(a+1,a+1+n);
rep(i,1,n){
if(solve(i)) ans = i;
else break;
}
printf("%d\n",ans);
return 0;
}
C. Ramesses and Corner Inversion
题意: 给你两个矩形A、B，矩形中每个位置可能为
1
1
1或
0
0
0，现在可以在矩形
A
A
A中选取一个子矩形，然后翻转这个子矩形的四个端点。问能否通过这种方式将A翻转成B。
思路: 可以发现，翻转一个子矩阵的四个角，不会改变矩阵
A
A
A与矩阵
B
B
B中每行每列不相同区域个数的奇偶性，即只需要判断矩阵
A
A
A与矩阵
B
B
B中每行每列中不相同区域个数是否为偶数即可完成此题。
代码:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define LOG1(x1,x2) cout << x1 << ": " << x2 << endl;
#define LOG2(x1,x2,y1,y2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << endl;
#define LOG3(x1,x2,y1,y2,z1,z2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << " , " << z1 << ": " << z2 << endl;
typedef long long ll;
typedef double db;
const int N = 500+10;
const int M = 1e5+100;
const db EPS = 1e-9;
using namespace std;
int n,m,a[N][N],b[N][N],row[N],col[N];
int main()
{
scanf("%d%d",&n,&m);
rep(i,1,n)
rep(j,1,m) scanf("%d",&a[i][j]);
rep(i,1,n)
rep(j,1,m){
scanf("%d",&b[i][j]);
if(a[i][j] != b[i][j]) row[i]++, col[j]++;
}
int jud = 0;
rep(i,1,n)
if(row[i]%2 != 0) jud = 1;
rep(i,1,m)
if(col[i]%2 != 0) jud = 1;
if(jud) printf("No\n");
else printf("Yes\n");
return 0;
}
D. Frets On Fire
题意: 一共
n
n
n个序列，已知每个序列开头元素的大小，序列为等差数列，公差为
1
1
1，序列长度为1018+1。先有
q
q
q组询问，每组询问给出
l
l
l与
r
r
r，求出这
n
n
n个序列在
[
l
,
r
]
[l,r]
[l,r]这个区间内一共有多少个不相同的数。
(
1
≤
n
≤
1
0
5
,
1
≤
q
≤
1
0
5
)
(1\leq n \leq 10^5, 1\leq q \leq 10^5)
(1≤n≤105,1≤q≤105)
思路: 其实这个问题可以抽象为现在有
n
n
n个区间，这
n
n
n个区间长度均为
r
−
l
+
1
r-l+1
r−l+1，已知每个区间开头元素，问
n
n
n个区间重叠之后一共有多少个不一样的数字。
很明显，我们首先需要对每个区间开头元素进行排序，然后来考虑相邻两个区间会有多少重复的元素。假如区间 1 1 1与区间 2 2 2差距为 l e n len len，如果 r − l + 1 ≤ l e n r-l+1\leq len r−l+1≤len，则区间 1 1 1与区间 2 2 2没有相互覆盖，而如果 l e n < r − l + 1 len < r-l+1 len<r−l+1，则区间 1 1 1的有效长度为 l e n len len，因此我们求出相邻两个区间的差距，存入数组 d [ x ] d[x] d[x]，然后对于 d d d 数组进行排序，然后二分出第一个间距大于等于 r − l + 1 r-l+1 r−l+1的点，该点之后的区间有效长度均为 r − l + 1 r-l+1 r−l+1，而该点之前的区间有效长度均为 l e n len len。
此处还需要注意，由于差分数组只维护了前 n − 1 n-1 n−1个区间，即最后一个区间的贡献显然是 r − l + 1 r-l+1 r−l+1，因此最后的答案还需要加上最后一个区间的长度。到此，即可完成此题。
代码:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define LOG1(x1,x2) cout << x1 << ": " << x2 << endl;
#define LOG2(x1,x2,y1,y2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << endl;
#define LOG3(x1,x2,y1,y2,z1,z2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << " , " << z1 << ": " << z2 << endl;
typedef long long ll;
typedef double db;
const int N = 1e5+100;
const int M = 1e5+100;
const db EPS = 1e-9;
using namespace std;
int n,m;
ll a[N],d[N],sum[N];
int main()
{
scanf("%d",&n);
rep(i,1,n) scanf("%lld",&a[i]);
sort(a+1,a+1+n);
d[1] = sum[0] = 0;
rep(i,2,n) d[i] = a[i]-a[i-1];
sort(d+2,d+1+n);
rep(i,1,n) sum[i] = sum[i-1]+d[i];
scanf("%d",&m);
rep(i,1,m){
ll xx,yy; scanf("%lld%lld",&xx,&yy);
int l = 2, r = n, ans = -1;
while(l <= r){
int mid = (l+r)>>1;
if(d[mid] >= (yy-xx+1)){
ans = mid; //第一个大于等于k的点
r = mid-1;
}
else l = mid+1;
}
// LOG3("xx",xx,"yy",yy,"ans",ans);
ll total = 0;
if(ans == -1)
total = sum[n]-sum[0]+(yy-xx+1);
else
total = (n-ans+2)*(yy-xx+1)+sum[ans-1]-sum[0];
printf("%lld ",total);
}
printf("\n");
return 0;
}
E. Pavel and Triangles
题意: 一共有
n
n
n类木棒，每类木棒都有其固定的数目，现在需要用这些木棒组成三角形。组成三角形的规则是，同类型的三根木棒，或者同类型的两根木棒+一根比这个类型编号更小的木棒，问最多可以组成多少根木棒。
思路: 很明显，这是一个贪心题目，但是怎么贪是一个问题。比赛时，怎么贪心都过不去，还是太欠缺贪心的练习，哭…
我们现在来研究一下这题应该如何去做，当你匹配到 j j j时，这时你有三种选择。① 选择< j , j , j j,j,j j,j,j> ②选择< k 1 , j , j k_1,j,j k1,j,j>， k 1 k_1 k1类型更小 ③ 选择< j , k 2 , k 2 j,k_2,k_2 j,k2,k2>， k 2 k_2 k2类型更大。可以发现必定是优先进行第二种选择的匹配，因为你已经匹配到了 j j j， k 1 k_1 k1已经无法进行匹配了，而此时也只用消耗两个 j j j，而第一种选择需要消耗三个 j j j，显然没有第二种优。而第三种选择，可以发现第三种选择最多和第二种一致，绝对不会比第二种更优，因此我们优先考虑第二种选择。
然后匹配完所有 k 1 k_1 k1之后，我们只剩下了两种选择，然后我们来考虑一下哪种方案更优。假设我们现在一共有 3 3 3个 j j j， 2 2 2个 a 1 a_1 a1、 a 2 a_2 a2、 a 3 a_3 a3。第一种选择< j , j , j j,j,j j,j,j>，< a 1 , a 2 , a 2 a_1,a_2,a_2 a1,a2,a2>，< a 1 , a 3 , a 3 a_1,a_3,a_3 a1,a3,a3> 形成 3 3 3个三角形。第三种选择< j , a 1 , a 1 j,a_1,a_1 j,a1,a1>、< j , a 2 , a 2 j,a_2,a_2 j,a2,a2>、< j , a 3 , a 3 j,a_3,a_3 j,a3,a3>，也是形成 3 3 3个三角形。而现在是我们假设还有 2 2 2个 a 1 a_1 a1、 a 2 a_2 a2、 a 3 a_3 a3，如果没有，则第三种选择很可能会变差。因此第三种选择不会优于第一种选择，所以我们直接进行第一种选择即可。
所以最后的算法是，先匹配 2 2 2个的，再匹配 3 3 3个的。
总结: 贪心问题总是在当前做出看来是最好的选择，而不从整体最优上加以考虑，做出的选择是局部最优解。贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。而在这道贪心问题中，如果优先考虑当前元素对后续元素的贡献，则违背了只考虑当前最优的原则，这也是我比赛时犯的错误，需要深刻反思。
贪心问题的证明可以从局部策略着手，证明其他的几种策略中没有比我所执行的这个策略更优的，充分列举其他情况，即可完成证明。
代码:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define LOG1(x1,x2) cout << x1 << ": " << x2 << endl;
#define LOG2(x1,x2,y1,y2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << endl;
#define LOG3(x1,x2,y1,y2,z1,z2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << " , " << z1 << ": " << z2 << endl;
typedef long long ll;
typedef double db;
const int N = 3*1e5+100;
const int M = 1e5+100;
const db EPS = 1e-9;
using namespace std;
int n;
ll ans,a[N];
int main()
{
scanf("%d",&n);
rep(i,1,n) scanf("%lld",&a[i]);
ll sum = 0;
rep(i,1,n){
ll xx = min(a[i]/2,sum);
ans += xx;
sum -= xx;
a[i] -= xx*2;
ans += a[i]/3;
a[i] = a[i]%3;
sum += a[i];
}
printf("%lld\n",ans);
return 0;
}
类似资料：