当前位置：首页 > ds >正文

Codeforces 2025/6/11 日志

ds 2025/7/15 2:20:32

B. Kevin and Geometry

题目大意：给你一堆木棒，问你是否能从中取4跟组成等腰梯形

#1 考虑等腰梯形的构造条件

思路：等腰梯形的两腰要相等且越大越好，从大到小枚举，符合条件则取出并删除，然后再遍历上下底边，只需上下底边只差小于2*腰长即可

代码：

int n; cin>>n;

vector<int> v(n);

for (int i = 0; i < n; i++)

cin>>v[i];

sort(v.begin(),v.end(),greater<int>());

int u = 0,k = 0,w = 0;

for (int i = 1; i < n; i++)

if (v[i] == v[i - 1])

{

u = v[i];

v.erase(find(v.begin(),v.end(),u));

break;

}

for (int i = 1; i < v.size(); i++)

if (v[i-1] - v[i] < 2 * u)

{

k = v[i-1];

w = v[i];

break;

}

if (u && k && w) cout<<u<<" "<<u<<" "<<k<<" "<<w<<endl;

else cout<<-1<<endl;

D. Subtract Min Sort

题目大意：一个由正整数组成的序列，问你能否通过无限次的选择索引i，让ai和a(i+1）减去min（ai，ai+1）的方法，得到一个非递减序列

思路：

每次操作可以看作把其中较小数变成 0，较大的数变成 ∣ai−ai−1∣。如果 ai>ai+1 的话，操作后 ai+1 会变成 0，而此时必须 a1 到 ai 全部为 0 才能满足条件。

这样看来，如果 ai>ai+1 时执行操作，不会更优，所以我们可以只在 ai≤ai+1 时执行操作。

将序列从前往后扫一遍，操作完之后，如果不满足不递减，那么这个序列就没救了。因为第一次每一步都局部解决了 ai>ai+1 的问题，经过一次完整扫描后，序列中所有的递减关系都已被消除，若存在这样的操作方案，就已经得到非递减序列。

代码：

int n; cin>>n;

for (int i = 0; i < n; i++) cin>>a[i];

for (int i = 1; i < n; i ++)

{

int x = min(a[i-1], a[i]);

a[i-1] -= x;

a[i] -= x;

}

bool flag = true;

for (int i = 1; i < n; i++)

if (a[i] < a[i-1])

{

flag = false;

break;

}

if (flag) cout<<"YES"<<endl;

else cout<<"NO"<<endl;

链接：Problem - D - Codeforces

B. pspspsps

思路：

容易发现由于 p 会占有前方的 1∼i，若有 s 在前面而又不在最前面，会得到这样的图：

其中红色区域是一个公用的排列，长度为 len，但两边都需要一个 len+1 的数字，不可行。s 在最前面就不受影响，因为左边没有不重叠部分。

代码：

int n; cin>>n;

string str; cin>>str;

if (str[0] == 's') str[0] = '.';

if (str.back() == 'p') str.back() = '.';

bool _s = false;

bool _p = false;

for (char t : str)

{

if (t == 's') _s = true;

if (t == 'p') _p = true;

}

cout<<((_s&&_p)?"NO":"YES")<<endl;

链接：Problem - B - Codeforces

C. Limited Repainting

思路：求最大值的最小值，常见的二分答案题。
进行 check 时，我们使用 lst 记录上一个 ai>x 的 si，初始值为 R。对 a 进行遍历，如果 ai≤x，可以直接忽略，当 ai>x 时，如果 si 为 B 且 lst=si，则需要进行一次涂色，使用 cnt 记录。之后将 lst 值更新为 si。最后 cnt 的值即为答案为 x 时所需的最少涂色次数。
使用 ans 记录答案，二分结束后，输出 ans。

代码：

string s;

int n,k;

vector<int> v;

bool check(int x)

{

int cnt = 0;

for (int i = 0; i < n; i ++ )

{

if (s[i] == 'B' && v[i] > x)

{

int j = i + 1;