Educational Codeforces Round 171 (Rated for Div. 2)(A~D题题解)
真不愧是教育场,老老实实给我收拾了一顿,直接给我干报废了
当时b题一直没有看清楚题,一直以为一个点可以用多次,导致直接错了12发
话不多说,直接来进入今日份快乐
A. Perpendicular Segments
思路:我们发现边最大是1e3,但是k最大可以达到1414,那么就知道有可能会是对角线形式的,因此我们不妨可以大胆猜想一下,就是最大的正方形的对角线,最大正方形,肯定就是有最小的边决定
#include <iostream>
using namespace std;
#define int long long
int t;
int x, y, k;
void solve() {
cin >> x >> y >> k;
int flag = min(x, y);
cout << 0 <<" "<< 0 <<" ";
cout << flag <<" "<< flag <<" ";
cout << 0 <<" "<< flag <<" ";
cout << flag <<" "<< 0 <<" ";
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> t;
while (t--) {
solve();
}
return 0;
}
B. Black Cells
思路:我们题目要求的是a数组中的每一个单元格都要标记为黑的,而且最多只能由一个地方(不处于a数组中的值)可以为黑的——这个地方就是为了处理奇数情况
我们对于偶数来说,每个点只能用一次,必然是相邻两个点两两链接才能获得最小的k,1和2连接,3和4连接,依次对应,对于奇数,我们就枚举每一个数被移出去的情况下,剩下的点所需要的最小的k,然后找到最小的即可
二分板题吧算是
#include <bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n;
int a[200005];
bool check(int x)
{
for (int i = 2; i <= n; i+=2)
{
if (a[i] - a[i - 1] > x)
{
return false;
}
}
return true;
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
if (n % 2 == 0)
{
int l = 1, r = 1e18 + 3;
while (l < r)
{
int mid = (l + r) / 2;
if (check(mid))
{
r = mid;
}
else
{
l = mid + 1;
}
}
cout << l << "\n";
}
else
{
int minn = LLONG_MAX;
for (int i = 1; i <= n; i++)
{
int q[200005], index = 0;
for (int j = 1; j <= n; j++)
{
if (j != i)
{
q[++index] = a[j];
}
}
int l = 1, r = 1e18;
while (l < r)
{
int mid = (l + r) / 2;
bool valid = true;
for (int j = 2; j <= index; j+=2)
{
if (q[j] - q[j - 1] > mid)
{
valid = false;
break;
}
}
if (valid)
{
r = mid;
}
else
{
l = mid + 1;
}
}
minn = min(minn, l);
}
cout << minn << "\n";
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> t;
while (t--)
{
solve();
}
return 0;
}
C. Action Figures
思路:从后往前遍历每一天,记录可以购买的物品。对于每一天,如果 可以访问商店并且有可购买的商品,我们将其加入队列。若当天无法购买商品,我们可以把这个商品和队列中的商品进行匹配,将最贵的商品零元购。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n;
string s;
void solve()
{
cin>>n;
cin>>s;
vector<int> a(n,0);
int flag=n-1;
for(int i=n-2;i>=0;i--)
{
if(s[i]=='1')
continue;
while(s[flag]=='0'&&flag>i)
{
flag--;
}
if(flag>i)
{
a[flag]=1;
flag--;
}
}
int sum=0;
for(int i=0;i<n;i++)
{
if(a[i]||s[i]=='0')
continue;
sum++;
}
for(int i=n-1;i>=0;i--)
{
if(s[i]=='1'&&sum>=2&&a[i] ==0)
{
a[i]=1;
sum-=2;
}
}
int ans=0;
for(int i=0;i<n;i+=1)
{
if(a[i]==0)
ans+=i+1;
}
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--)
solve();
return 0;
}
D. Sums of Segments
思路:类似与套娃前缀和吧,然后用二分优化时间复杂度
a数组:就是我们的原数组
pre数组:a数组的前缀和数组
prepre数组:pre数组的前缀和数组
这里说一下b数组的一些操作,我们可以将b数组分为n个区间,每个区间的值都是从s(i,i)到s(i,n)
sum数组,用来统计b数组的每个区间的总和
preb数组,b数组区间的前缀和数组
pos数组,用来统计b数组每个区间的结尾位置是多少
我们首先来分析一下题意要干什么,就是说给你一个两个下标,让你计算这个区间内的b数组的值的累加和
n的数据大小为3e5,也就是说如果存一个一维数组要存到4.5*1e10的大小,很明显,不论是时间还是空间都会爆掉,所以不能用1维数组存
因此我们采用上述方法将b数组分成n个区间,这样就能计算了,我们用前缀和可知,如果我们能够得到 preb[ r ] 的值和 preb[ l - 1 ]的值,相减就是最终结果
那我们现在想要做的就是如何去就出这两个数,我们可以求出这两个数在第几行第几列,然后直接计算即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, q;
int a[300005];
int l, r, mid;
int f(int x) {
return (n + n - x + 1) * x / 2;
}
void solve() {
cin >> n;
vector<int> pre(n + 1, 0); // a数组前缀和数组
vector<int> prepre(n + 1, 0); // pre数组前缀和数组
vector<int> sum(n + 1, 0); // 将b数组分为n个区间,每个区间的和
vector<int> preb(n + 1, 0); // b数组的区间前缀和
vector<int> pos(n + 1, 0);
for (int i = 1; i <= n; i++) {
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
prepre[i] = prepre[i - 1] + pre[i];
}
for (int i = 1; i <= n; i++) {
sum[i] = (prepre[n] - prepre[i - 1]) - (n - i + 1) * pre[i - 1];
preb[i] = preb[i - 1] + sum[i];
pos[i] = pos[i - 1] + (n - i + 1);
}
cin >> q;
for (int i = 1; i <= q; i++) {
int posl, posr;
cin >> posl >> posr;
// 先计算posl在第几行第几列
l = 0; r = n;
while (l < r) {
mid = (l + r + 1) / 2;
if (pos[mid] < posl) {
l = mid;
} else {
r = mid - 1;
}
}
int il = l + 1, jl = posl - pos[l];
// 再计算posr在第几行第几列
l = 0; r = n;
while (l < r) {
mid = (l + r + 1) / 2;
if (pos[mid] < posr) {
l = mid;
} else {
r = mid - 1;
}
}
int ir = l + 1, jr = posr - pos[l];
// 准备计算preb[posr]-preb[posl-1]
int prebr = preb[ir - 1];
prebr+=prepre[ir+jr-1]-prepre[ir-1]-jr*pre[ir-1];
int prebl = preb[il - 1];
prebl+=prepre[il+jl-2]-prepre[il-1]-(jl-1)*pre[il-1];
cout<<prebr-prebl<<"\n";
}
}
signed main() {
solve();
return 0;
}