2025/2/10 心得

第一题。J. C - Grand Garden (AI)

问题陈述

在一个花坛里，有 NN 朵花，编号为 1,2,\ldots,N1,2,…,N。最初，所有花的高度都是 00。你将得到一个高度序列 h={h\_1,h\_2,h\_3,\ldots\} 作为输入。你希望通过重复以下“浇水”操作来将所有花的编号为 kk 的花的高度改变为 h_khk，对所有 kk (1 \leq k \leq N)(1≤k≤N)：

指定整数 ll 和 rr。对所有满足 l \leq x \leq rl≤x≤r 的花 xx，将其高度增加 11。

找出满足条件的最小浇水操作次数。

约束条件

1 \leq N \leq 1001≤N≤100
0 \leq h_i \leq 1000≤hi≤100
输入中的所有值均为整数。

输入

从标准输入以以下格式给出输入：

h_1h1 h_2h2 h_3h3 ............ h_NhN

输出

打印满足条件的最小浇水操作次数。

示例输入 1

1 2 2 1

示例输出 1

满足条件的最小浇水操作次数是 22。一种实现方式是：

执行操作，(l,r)=(1,3)(l,r)=(1,3)。
执行操作，(l,r)=(2,4)(l,r)=(2,4)。

示例输入 2

3 1 2 3 1

示例输出 2

示例输入 3

4 23 75 0 23 96 50 100

示例输出 3

221

这道题我本来的想法是

首先先把全部最小值全部交一遍。

然后把他们分成一块一块的一块一块来浇他们的最小值

这样写也行，但是呢需要用分治来写。

哦由于我现在刚学分治,不太会，所以就不能用治来写。

其实这道题还有另外一种办法。

就是求出它们右边比左边大的值，所有加起来。

再加上第一个数。

便是他们。最小浇水的次数了。

代码如下，

#include<bits/stdc++.h>
using namespace std;
int n,a[110],sum,maxx=9999999999;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
   cin>>a[i];
   }
   for(int i=1;i<=n;i++)
   {
       if(a[i+1]>a[i])
       sum+=a[i+1]-a[i];
   }
   cout<<sum+a[1];
return 0;
}

第二题 K. C - Attack Survival (AI)

题目描述

高桥决定举办一场最快的手指速算游戏。负责计分的木村在编写管理玩家分数的程序时遇到了困难，游戏规则如下：

有NN名玩家参加游戏，编号为1到NN。游戏开始时，每个玩家都有KK分。

当一个玩家正确回答问题时，其他N-1N−1名玩家各减一分（-1）。没有其他因素影响玩家的分数。

游戏结束时，得分为0或更低的玩家被淘汰，剩余的玩家幸存下来。

在最后一场比赛中，共有QQ个正确答案，第ii个答案是由玩家A_i给出的。请木村编写一个程序，判断每个玩家是否在这个游戏中幸存下来。

约束条件

输入的所有值都是整数。
2 \leq N \leq 10^52≤N≤105
1 \leq K \leq 10^91≤K≤109
1 \leq Q \leq 10^51≤Q≤105
1 \leq A\_i \leq N\ (1 \leq i \leq Q)1≤A_i≤N (1≤i≤Q)

输入

从标准输入以以下格式给出输入：

NN KK QQ

A_1A1

A_2A2

A_QAQ

输出

打印NN行。第ii行应包含Yes（如果玩家ii在比赛中幸存下来），否则为No。

样例输入1

6 3 4

样例输出1

Yes

一开始，玩家的分数是(3, 3, 3, 3, 3, 3)。

玩家3正确回答一个问题。玩家的分数现在是(2, 2, 3, 2, 2, 2)。
玩家1正确回答一个问题。玩家的分数现在是(2, 1, 2, 1, 1, 1)。
玩家3正确回答一个问题。玩家的分数现在是(1, 0, 2, 0, 0, 0)。
玩家2正确回答一个问题。玩家的分数现在是(0, 0, 1, -1, -1, -1)。

得分为0或更低的玩家1、2、4、5和6被淘汰，玩家3在这场比赛中幸存下来。

样例输入2

6 5 4

样例输出2

Yes

样例输入3

10 13 15

样例输出3

Yes

这道题我当初第一遍就做出来了。

我的思路是这样的。

首先先用一个数组存储出所有学生答每个人答对题的数量。

其中总分加这个每个人答对的。提亮再减去一共的轮数。如果大于零，那么就输出yes。

否则就输出no

其实这道题还有另外一种思路。

就是让他们首先先把全部总分数都为零的话减去轮数。

如果有一个人答对题，就让他那个负数或者是正数加上一

到最后再判断一下。代码

如下，

#include<bits/stdc++.h>
using namespace std;
int n,k,q,a[100010],stu[100010];
int main()
{
cin>>n>>k>>q;
for(int i=1;i<=q;i++)
{
   cin>>a[i];
   stu[a[i]]++;
   }
   for(int i=1;i<=n;i++)
   {
       if(k+stu[i]-q>0)
       {
           cout<<"Yes"<<endl;
       }
       else
       {
           cout<<"No"<<endl;
       }
   }
return 0;
}

第三题。

L. D - String Formation (AI)

问题描述

高桥有一个由小写英文字母组成的字符串S。

从这个字符串开始，他将按照以下给定的程序产生一个新字符串。

程序包括Q个操作。在操作i（1≤i≤Q）中，提供一个整数T_i，其含义如下：

如果T_i = 1：反转字符串S。
如果T_i = 2：另外提供两个信息，一个整数F_i和一个英文小写字母C_i。
- 如果F_i = 1：在字符串S的开头添加C_i。
- 如果F_i = 2：在字符串S的末尾添加C_i。

帮助高桥找到该程序最终生成的字符串。

约束条件

1≤|S|≤10^5
S由小写英文字母组成。
1≤Q≤2×10^5
T_i = 1或2。
如果提供了F_i，则F_i = 1或2。
如果提供了C_i，则C_i是一个小写英文字母。

输入

标准输入以以下格式给出输入：

Query_1

Query_Q

在第3行到第(Q+2)行中，Query_i是以下之一：

表示T_i = 1，以及：

F_i

C_i

表示T_i = 2。

输出

打印结果字符串。

样例输入1

2 1 p

2 2 c

样例输出1

cpa

将有Q = 4次操作。最初，S是'a'。

操作1：在S的开头添加'p'。S变为'pa'。
操作2：反转S。S变为'ap'。
操作3：在S的末尾添加'c'。S变为'apc'。
操作4：反转S。S变为'cpa'。

因此，结果字符串是'cpa'。

样例输入2

2 2 a

2 1 b

2 2 c

样例输出2

aabc

将有Q = 6次操作。最初，S是'a'。

操作1：S变为'aa'。
操作2：S变为'baa'。
操作3：S变为'aab'。
操作4：S变为'aabc'。
操作5：S变为'cbaa'。
操作6：S变为'aabc'。

因此，结果字符串是'aabc'。

样例输入3

2 1 x

样例输出3

这道题挺难。

我做了好久

到最后终于模拟出来了。

我最初的代码如下，

#include<bits/stdc++.h>
using namespace std;
string a,e,a1,a2;
int b,c,d;
int main()
{
getline(cin,a);
cin>>b;
for(int i=1;i<=b;i++)
{
    cin>>c;
    if(c==2)
    {
        cin>>d;
       cin>>e;
       if(d==2)
       {
       a+=e;
       }
       if(d==1)
       {
       a=e+a;
       }
   }
   if(c==1)
   {
      reverse(a.begin(),a.end());
   }
}
cout<<a;
return 0;
}

只得了64分。

还有一些超时了。

因为这道题用的是10的5次方。

For循环最多也就18次方。

里边还套了个reverse函数。

所以说有些数据会超时。

那我们不妨想一下。

如果这题中他让我们翻转的个数一共为偶数。

那么翻来翻去又翻回来了。如果为奇数

那也就翻一次跟9嗯还是一样的。

所以便可以把这个reverse拿到下面。

For循环外边来用。

但如果这样做的话，原来这个数据重量是奇数。

我本来要加在前面就不能加在前面，应该加在后边。

如果偶数如果是偶数则还是一样。

应加在前面的加在前面

，应加在后边儿，加在后面。

最终代码如下，

#include<bits/stdc++.h>
using namespace std;
string a,e,a1,a2;
int b,c,d,sum;
int main()
{
getline(cin,a);
cin>>b;
for(int i=1;i<=b;i++)
{
    cin>>c;
   if(c==1)
   {
   sum++;
   }
   if(sum%2==1)
   {
          if(c==2)
      {
          cin>>d;
           cin>>e;
           if(d==2)
           {
           a=e+a;
           }
           if(d==1)
           {
           a+=e;
           }
       }
   }
   if(sum%2==0)
   {
          if(c==2)
      {
          cin>>d;
           cin>>e;
           if(d==2)
           {
           a+=e;
           }
           if(d==1)
           {
           a=e+a;
           }
       }
   }
}
if(sum%2==0)
cout<<a;
else
{
reverse(a.begin(),a.end());
cout<<a;
}
return 0;
}