NEFU新生个人赛回顾——（附测试数据生成器）
鸽鸽
咕咕咕
题目描述
在化工街上，一共有n个房子，每个房子里面住着一只鸽鸽，分别是库特的n只鸽鸽。每只鸽鸽最初有一个体重值a[i]，库特有两种操作，他将会用这两种操作来严格控制鸽鸽们的体重。库特想考考你，在q次操作之后，每只鸽鸽的体重为多少？
输入格式
第一行包含一个整数n （1<=n<=2e5）的数量。
下一行包含n个整数a[i]（0<=a[i]<=1e9），代表第i只鸽鸽的初始体重为a[i]。
下一行包含一个整数q（0<=q<=2e5），代表库特操作的次数。
接下来q行每行表示库特的一个操作。
第一种操作为 1 x y (1<=x<=n，0<=y<=1e9)：将第x只鸽鸽的体重变为y
第二种操作为 2 x (0<=x<=1e9)：将所有体重小于x的鸽鸽的体重变为x
输出格式
输出n个整数，代表所有操作结束后n只鸽鸽的体重。
样例输入
4
1 2 3 4
3
2 3
1 2 4
2 1
样例输出
3 4 3 4
一点感悟
首先我想我需要指出一点是“鸽子对于周边的刺激反应会非常敏感 ”相比是无法在化工街上生存的。[歪题结束]
第一眼看到这个题目，自然会想到是“简单模拟”，码速比较快的同学就可以很快的给出如下代码
/*
* @Author: Gehrychiang
* @Date: 2019-12-03 00:04:24
* @LastEditors: Gehrychiang
* @LastEditTime: 2019-12-03 00:04:26
* @Website: www.yilantingfeng.site
* @E-mail: gehrychiang@aliyun.com
*/
/*
This is an unrefined version
*/
#include <bits/stdc++.h>
using namespace std;
#define MaxN 200002
int n; //the number of gugugu
int t; //the times of operation
int gezi[MaxN];
void trans_1(int x, int y)
{
gezi[x-1]=y;
return;
}
void trans_2(int x)
{
for (int i = 0; i < n; i++)
{
if(gezi[i]<x)
{
gezi[i]=x;
}
}
return;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> gezi[i];
}
cin >> t;
for (int i = 0; i < t; i++)
{
int label_num;
cin >> label_num;
if (label_num == 1)
{
int x, y;
cin >> x >> y;
trans_1(x, y);
}
else if(label_num==2)
{
int x;
cin>>x;
trans_2(x);
}
}
for (int i = 0; i < n; i++)
{
cout<<gezi[i]<<" ";
}
return 0;
}清晰好懂，读到什么执行什么，操作结束以后输出即可，可是鲜红的2e5和1e9仿佛在嘲笑着我的无知
显然我们需要去优化这样一个复杂的算法。
还记得，曾经有一位伟人说过——“化整为零，各个击破”，在这里，我们也不妨去对每一个鸽子逐个分析，很显然对每一个鸽子而言，操作1就是（通过黑魔法）[划掉] 将其变成另一个体重，而操作2则是（通过白魔法）【屁】将其变成max（现在体重，给定体重下限）。
针对每一个鸽子而言，不管之前的状态如何，只要使用一次黑魔法，就可以变成另一种状态，黑魔法使用的影响是不需要考虑之前的情况的。
与之相反的是白魔法，白魔法的使用是受到前一个状态制约的，只有当目的值大于现有值的时候才会产生影响。
那在从BIG PICTURE来看，对每一个鸽子而言，只要记录下最后一次使用黑魔法的操作顺序的位置，再去和之后他所受到的所有白魔法的最大值比较，取大者即可。
/*
* @Author: Gehrychiang
* @Date: 2019-12-02 23:04:50
* @LastEditors: Gehrychiang
* @LastEditTime: 2019-12-03 01:38:17
* @Website: www.yilantingfeng.site
* @E-mail: gehrychiang@aliyun.com
*/
#include <bits/stdc++.h>
using namespace std;
#define MaxN 200002
int n; //the number of gugugu
int t; //the times of operation
int yuanshi[MaxN]; //yuanshi当中已经存储着对于每一个而言最后一次的操作1的决定量
int vis[MaxN] = {0}; //记录每一个鸽子的最后一次操作1的i值
int base[MaxN] = {0}; //存放操作二的基准量
void trans_1(int x, int y, int i)
{
yuanshi[x - 1] = y;
vis[x - 1] = i; //记录位置
return;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &yuanshi[i]);
}
scanf("%d", &t);
for (int i = 0; i < t; i++)
{
int label_num;
scanf("%d", &label_num);
if (label_num == 1)
{
int x, y;
scanf("%d %d", &x, &y);
trans_1(x, y, i);
}
else if (label_num == 2)
{
int x;
scanf("%d", &x);
base[i] = x;
}
}
for (int i = 0; i < n; i++)
{
int u = 0;
for (int j = vis[i]; j < t; j++)
{
if(u<base[j])
{
u=base[j];
}
}
printf("%d ", max(u, yuanshi[i]));
}
return 0;
}SUBMIT!!!!
可这个时候
再回过头去检查代码，能报TLE的点只有一处就是去寻找第i次操作之后的操作2的最大下限值，大量重复计算了最大下限值数组后面的和
于是，就不难觉得需要去讲各个位置之后最大值的存起来，避免重复计算
前方高能 ！
for (int i = t - 1; i >= 0; i--)
{
base[i] = max(base[i], base[i + 1]);
}这样我们就成功的将下限值的数组中的每一个元素存成了从其本身到数组末尾的最大值。
/*
* @Author: Gehrychiang
* @Date: 2019-12-02 23:04:50
* @LastEditors: Gehrychiang
* @LastEditTime: 2019-12-03 01:38:17
* @Website: www.yilantingfeng.site
* @E-mail: gehrychiang@aliyun.com
*/
#include <bits/stdc++.h>
using namespace std;
#define MaxN 200002
int n; //the number of gugugu
int t; //the times of operation
int yuanshi[MaxN]; //存储着对于每一个而言最后一次的操作1的决定量
int vis[MaxN] = {0}; //记录每一个鸽子的最后一次操作1的i值
int base[MaxN] = {0}; //存放操作二的基准量
void trans_1(int x, int y, int i)
{
yuanshi[x - 1] = y;
vis[x - 1] = i; //记录位置
return;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &yuanshi[i]);
}
scanf("%d", &t);
for (int i = 0; i < t; i++)
{
int label_num;
scanf("%d", &label_num);
if (label_num == 1)
{
int x, y;
scanf("%d %d", &x, &y);
trans_1(x, y, i);
}
else if (label_num == 2)
{
int x;
scanf("%d", &x);
base[i] = x;
}
}
for (int i = t - 1; i >= 0; i--)
{
base[i] = max(base[i], base[i + 1]);
}
for (int i = 0; i < n; i++)
{
int u = 0;
u = base[vis[i]];
printf("%d ", max(u, yuanshi[i]));
}
return 0;
}
生活不易，A题且A且珍惜
最后放出测试数据生成代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
srand(36785649);//更改种子即可
int n = 100;
cout << n << endl;
for (int i = 0; i < n; i++)
{
cout << rand()%10000 << " ";
}
cout << endl;
int t = rand()%100;
cout << t << endl;
for (int i = 0; i < t; i++)
{
if (rand() % 2 == 1)
{
cout << "1 " << rand()%101 << " " << rand()%10000;
}
else
{
cout<<"2 "<<rand()%10000;
}
cout<<endl;
}
}咕咕咕！！！！！！