离生物制剂开始还有最后的3天，坚持住，控制住疾病，养好身体才有革命的本钱
期待已久的新生ACM队集训终于开始啦，第一天我全勤参加，第二天因为身体不适没有参加，第三天参加了下午的集训
来了集训就见到了很强很强的大佬，他们的码力非常惊人，我即荣幸又有些害怕哈哈哈哈他们太强了
当然，我也在飞快进步中，加油
先给出一下前面自己跟着洛谷学的数据结构内容吧
第一道题是我用的是插入排序（是洛谷提单里面数据结构的题，但是怎么是排序哈哈哈哈），插入排序的复杂度是n平方，而这道题用线段树似乎可以nlogn写出来，但是对我来说太难，而插入排序已经能够AC
出自洛谷P2234
Tiger 最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。
Tiger 拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：当最小波动值越大时，就说明营业情况越不稳定。
而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助 Tiger 来计算这一个值。
| 我们定义，一天的最小波动值 = $\min{ | \text{该天以前某一天的营业额}-\text{该天营业额} | }$。 |
特别地，第一天的最小波动值为第一天的营业额。
| 第一行为正整数 $n$（$n \leq 32767$） ，表示该公司从成立一直到现在的天数，接下来的 $n$ 行每行有一个整数 $a_i$（$ | a_i | \leq 10^6$) ，表示第 $i$ 天公司的营业额，可能存在负数。 |
输出一个整数，即每一天最小波动值的和，保证结果小于 $2^{31}$。
6
5
1
2
5
4
6
12
| 结果说明：$5+ | 1-5 | + | 2-1 | + | 5-5 | + | 4-5 | + | 6-5 | =5+4+1+0+1+1=12$ |
下面是我的解题代码，其实是我第一次写插入排序
#include<iostream>
using namespace std;
#include<vector>
int main()
{
vector<int> v;
int n,sum=0,num;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>num;
v.push_back(num);
int j=i-1;
for(j=i-1;j>=0;j--)
{
if(num<v[j])
{
v[j+1]=v[j];
}
else
{
break;
}
}
v[j+1]=num;
if(i==0)
{
sum+=num;
}
else if(j==i-1)
{
sum+=num-v[j];
}
else if(j==-1)
{
sum+=v[1]-v[0];
}
else
{
sum+=min(num-v[j],v[j+2]-num);
}
}
cout<<sum;
return 0;
}
显然，这道题目的意思是说一个数字与前面已经出现过的数字中的某一个的绝对值之差的最小值，那么我们只需要在插入排序的时候把插入的数字与前面后面的数字相比较即可
下面这道题目是栈题，而且是黄题，（哈哈哈第一次自己敲出黄题）下面附上题目
给出两个序列 pushed 和 poped 两个序列，其取值从 $1$ 到 $n(n \le 100000)$。已知入栈序列是 pushed，如果出栈序列有可能是 poped，则输出 Yes，否则输出 No。请注意，给定的序列一定是一个排列（即没有重复数字）。
为了防止骗分，每个测试点有多组数据，不超过 $5$ 组。
第一行一个整数 $q$，询问次数。
接下来 $q$ 个询问，对于每个询问：
第一行一个整数 $n$ 表示序列长度；
第二行 $n$ 个整数表示入栈序列；
第三行 $n$ 个整数表示出栈序列；
对于每个询问输出答案。
2
5
1 2 3 4 5
5 4 3 2 1
4
1 2 3 4
2 4 1 3
Yes
No
#include<iostream>
using namespace std;
#include<vector>
#include<stack>
int main()
{
int n,m,num;
cin>>n;
vector<int> instack,outstack;
for(int i=0;i<n;i++)
{
stack<int> s;
int point=0;
int judge=10;
instack.resize(0);
outstack.resize(0);
cin>>m;
for(int j=0;j<m;j++)
{
cin>>num;
instack.push_back(num);
}
for(int j=0;j<m;j++)
{
cin>>num;
outstack.push_back(num);
}
for(int k=0;k<m;k++)
{
while(s.empty()||s.top()!=outstack[k])
{
if(point==m)
{
judge=0;
break;
}
s.push(instack[point++]);
}
if(judge==0)
{
break;
}
else
{
s.pop();
}
}
if(judge==0)
{
cout<<"No"<<endl;
}
else
{
cout<<"Yes"<<endl;
}
}
return 0;
}
这里题目还算好理解，入栈序列是入栈的顺序（入的过程中可能有出），出栈同理
那么我们只需要模拟这个过程，一一读取入栈序列，如果顶栈不是这个数字，就再接着入，入到是了就出，出完读取一下个入栈数字，没有找到（就是在前面入了）就失败，记得用变量好好标记一下，出了循环才知道是已经失败了
其实我觉得也可以不标记继续循环，最后检查栈是不是空的。不过过程感觉思路不是很清晰
再接下来我放一下前天写的集训题，集训题就是难哈哈哈，第一天教了最长上升子序列LIS的n平方做法和nlogn做法，背包DP的基础（01背包和完全背包），动态规划通用思路理解状态表示和状态转移等等
下面这道题是我第一天集训唯一写出来的一道题目，是01背包，但是难度因为主件附件，dp值为money*level而提高了非常多
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 $n$ 元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
| 主件 | 附件 |
|---|---|
| 电脑 | 打印机，扫描仪 |
| 书柜 | 图书 |
| 书桌 | 台灯，文具 |
| 工作椅 | 无 |
如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 $0$ 个、$1$ 个或 $2$ 个附件。每个附件对应一个主件，附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的 $n$ 元。于是，他把每件物品规定了一个重要度，分为 $5$ 等：用整数 $1 \sim 5$ 表示，第 $5$ 等最重要。他还从因特网上查到了每件物品的价格（都是 $10$ 元的整数倍）。他希望在不超过 $n$ 元的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第 $j$ 件物品的价格为 $v_j$，重要度为 $w_j$，共选中了 $k$ 件物品，编号依次为 $j_1,j_2,\dots,j_k$，则所求的总和为：
\[v_{j_1} \times w_{j_1}+v_{j_2} \times w_{j_2}+ \dots +v_{j_k} \times w_{j_k}\]请你帮助金明设计一个满足要求的购物单。
第一行有两个整数，分别表示总钱数 $n$ 和希望购买的物品个数 $m$。
第 $2$ 到第 $(m + 1)$ 行，每行三个整数，第 $(i + 1)$ 行的整数 $v_i$，$p_i$，$q_i$ 分别表示第 $i$ 件物品的价格、重要度以及它对应的的主件。如果 $q_i=0$，表示该物品本身是主件。
输出一行一个整数表示答案。
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
2200
对于全部的测试点，保证 $1 \leq n \leq 3.2 \times 10^4$，$1 \leq m \leq 60$，$0 \leq v_i \leq 10^4$，$1 \leq p_i \leq 5$，$0 \leq q_i \leq m$，答案不超过 $2 \times 10^5$。
NOIP 2006 提高组 第二题
直到刚刚到洛谷复制markdown的时候，我才知道这竟然是一道绿题，不可思议，我独自写出了绿题，确实难度非常的大，我的思路很清晰，把主件和附件看作一个整体，然后一个整体一个整体地考虑
每次考虑的时候分几种情况，某个特定money下，不考虑新整体，只买新整体的主件，买新整体的主件和附件，买新整体的主件和所有附件，情况很多很难，这里附上代码
#include<iostream>
using namespace std;
#include<algorithm>
struct boj
{
int zhup,zhulp,zhu;
int fu1p,fu1lp,fu2lp,fu2p;
};
boj arr[61];
int main()
{
for(int i=0;i<=60;i++)
{
arr[i].fu1p=-1;
arr[i].fu2p=-1;
arr[i].zhup=-1;
arr[i].zhu=0;
}
int mony,n,pri,level,from;
cin>>mony>>n;
mony=mony/10*10;
int dp[n+1][mony+1];
for(int i=0;i<=mony;i+=10)
{
dp[0][i]=0;
}
for(int i=1;i<=n;i++)
{
cin>>pri>>level>>from;
if(from==0)
{
arr[i].zhulp=pri*level;
arr[i].zhup=pri;
arr[i].zhu=1;
}
else
{
if(arr[from].fu1p==-1)
{
arr[from].fu1lp=pri*level;
arr[from].fu1p=pri;
}
else{
arr[from].fu2lp=pri*level;
arr[from].fu2p=pri;
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=mony;j+=10)
{
dp[i][j]=dp[i-1][j];
if(arr[i].zhu==0)
{
continue;
}
if(arr[i].fu1p==-1)
{
if(j-arr[i].zhup<0)
{
dp[i][j]=dp[i-1][j];
}
else
dp[i][j]=max({dp[i-1][j],dp[i-1][j-arr[i].zhup]+arr[i].zhulp});
}
else if(arr[i].fu2p==-1)
{
if(j-arr[i].zhup<0)
{
dp[i][j]=dp[i-1][j];
}
else if(j-arr[i].zhup-arr[i].fu1p<0)
{
dp[i][j]=max({dp[i-1][j],dp[i-1][j-arr[i].zhup]+arr[i].zhulp});
}
else
dp[i][j]=max({dp[i-1][j],dp[i-1][j-arr[i].zhup]+arr[i].zhulp,
dp[i-1][j-arr[i].zhup-arr[i].fu1p]+arr[i].zhulp+arr[i].fu1lp});
}
else{
if(j-arr[i].zhup<0)
{
dp[i][j]=dp[i-1][j];
}
if(j-arr[i].zhup>=0&&j-arr[i].fu1p-arr[i].zhup<0&&j-arr[i].fu2p-arr[i].zhup<0)
{
dp[i][j]=max({dp[i-1][j],dp[i-1][j-arr[i].zhup]+arr[i].zhulp});
}
if(j-arr[i].zhup-arr[i].fu1p>=0&&j-arr[i].zhup-arr[i].fu2p-arr[i].fu1p<0)
{
dp[i][j]=max({dp[i-1][j],dp[i-1][j-arr[i].zhup]+arr[i].zhulp,
dp[i-1][j-arr[i].zhup-arr[i].fu1p]+arr[i].zhulp+arr[i].fu1lp});
}
if(j-arr[i].zhup-arr[i].fu1p-arr[i].fu2p<0&&j-arr[i].zhup-arr[i].fu2p>=0)
{
dp[i][j]=max({dp[i-1][j],dp[i-1][j-arr[i].zhup]+arr[i].zhulp,
dp[i-1][j-arr[i].zhup-arr[i].fu2p]+arr[i].zhulp+arr[i].fu2lp});
}
if(j-arr[i].zhup-arr[i].fu1p-arr[i].fu2p>=0){
dp[i][j]=max({dp[i-1][j],dp[i-1][j-arr[i].zhup]+arr[i].zhulp,
dp[i-1][j-arr[i].zhup-arr[i].fu2p]+arr[i].zhulp+arr[i].fu2lp,
dp[i-1][j-arr[i].zhup-arr[i].fu1p]+arr[i].zhulp+arr[i].fu1lp,
dp[i-1][j-arr[i].zhup-arr[i].fu1p-arr[i].fu2p]+arr[i].zhulp+arr[i].fu1lp+arr[i].fu2lp});
}
}
}
}
cout<<dp[n][mony];
return 0;
}
好了，利用集训时间写blog也只能写这么久了，我看得到很快的进步，继续打题了