W1
# 怪兽训练计划1
## 题目描述
小明有一个怪兽训练计划。
初始时，怪兽充满能量，能量值为8800。如果训练怪兽，每分钟损耗能量值400；如果让怪兽休息，每分钟增加能量值200。能量的损耗和增加都是均匀变化的。小明打算让怪兽训练一分钟、休息一分钟、再训练一分钟、再休息一分钟……如此循环，如果某个时刻怪兽的体力到达0，小明就停止训练怪兽。
请问小明在多久以后停止训练怪兽。请以秒为单位输出答案。答案钟只填写数，不填写单位。
## 输入格式
无
## 输出格式
输出为一个整数。
#include<iostream>
using namespace std;
int main (){
int a=8800,b=0,i;
for (i=1;i<=100;i++)
{
a=a-200;
if (a<=200){
a+=200;
b=a/400 ;
cout<<120*(i-1)+60*b<<endl;
break;
}
}
return 0;
}
W2
# 独木桥
## 题目背景
战争已经进入到紧要时间。你是运输小队长，正在率领运输部队向前线运送物资。运输任务像做题一样的无聊。你希望找些刺激，于是命令你的士兵们到前方的一座独木桥上欣赏风景，而你留在桥下欣赏士兵们。士兵们十分愤怒，因为这座独木桥十分狭窄，只能容纳 $1$ 个人通过。假如有 $2$ 个人相向而行在桥上相遇，那么他们 $2$ 个人将无法绕过对方，只能有 $1$ 个人回头下桥，让另一个人先通过。但是，可以有多个人同时呆在同一个位置。
## 题目描述
突然，你收到从指挥部发来的信息，敌军的轰炸机正朝着你所在的独木桥飞来！为了安全，你的部队必须撤下独木桥。独木桥的长度为 $L$，士兵们只能呆在坐标为整数的地方。所有士兵的速度都为 $1$，但一个士兵某一时刻来到了坐标为 $0$ 或 $L+1$ 的位置，他就离开了独木桥。
每个士兵都有一个初始面对的方向，他们会以匀速朝着这个方向行走，中途不会自己改变方向。但是，如果两个士兵面对面相遇，他们无法彼此通过对方，于是就分别转身，继续行走。转身不需要任何的时间。
由于先前的愤怒，你已不能控制你的士兵。甚至，你连每个士兵初始面对的方向都不知道。因此，你想要知道你的部队最少需要多少时间就可能全部撤离独木桥。另外，总部也在安排阻拦敌人的进攻，因此你还需要知道你的部队最多需要多少时间才能全部撤离独木桥。
## 输入格式
第一行共一个整数 $L$，表示独木桥的长度。桥上的坐标为 $1, 2, \cdots, L$。
第二行共一个整数 $N$，表示初始时留在桥上的士兵数目。
第三行共有 $N$ 个整数，分别表示每个士兵的初始坐标。
## 输出格式
共一行，输出 $2$ 个整数，分别表示部队撤离独木桥的最小时间和最大时间。$2$ 个整数由一个空格符分开。
## 样例 #1
### 样例输入 #1
```
4
2
1 3
```
### 样例输出 #1
```
2 4
```
## 提示
对于 $100\%$ 的数据，满足初始时，没有两个士兵同在一个坐标，$1\le L\le5\times 10^3$，$0\le N\le5\times10^3$，且数据保证 $N\le L$。
~~~~~~~~~~~~~~~~
#include<iostream>
#include<algorithm>
using namespace std;
int main (){
int L, N, S, Max=0, Min=0;
cin>>L>>N;
for(int i=1;i<=N;i++){
cin>>S;
Max=max(Max,max(L-S+1,S));
Min=max(Min,min(L-S+1,S));
//cout<<Max<<" "<<Min<<endl;
}
cout<<Min<<" "<<Max<<endl;
return 0;
}
W3
# 【深基15.例1】询问学号
## 题目描述
有 $n(n \le 2 \times 10^6)$ 名同学陆陆续续进入教室。我们知道每名同学的学号（在 $1$ 到 $10^9$ 之间），按进教室的顺序给出。上课了，老师想知道第 $i$ 个进入教室的同学的学号是什么（最先进入教室的同学 $i=1$），询问次数不超过 $10^5$ 次。
## 输入格式
第一行 $2$ 个整数 $n$ 和 $m$，表示学生个数和询问次数。
第二行 $n$ 个整数，表示按顺序进入教室的学号。
第三行 $m$ 个整数，表示询问第几个进入教室的同学。
## 输出格式
输出 $m$ 个整数表示答案，用换行隔开。
## 样例 #1
### 样例输入 #1
```
10 3
1 9 2 60 8 17 11 4 5 14
1 5 9
```
### 样例输出 #1
```
1
8
5
```
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#include<iostream>
using namespace std;
int main()
{
int n=0,m=0;
cin>>n>>m;
int number[n];
for(int i=0;i<n;i++)
{
cin>>number[i];
}
int ask[m];
for(int i=0;i<m;i++)
{
cin>>ask[i];
}
for(int i=0;i<m;i++)
{
cout<<number[ask[i]-1]<<endl;
}
return 0;
}
W4
# 队列安排
## 题目描述
一个学校里老师要将班上 $N$ 个同学排成一列，同学被编号为 $1\sim N$，他采取如下的方法：
1. 先将 $1$ 号同学安排进队列，这时队列中只有他一个人；
2. $2\sim N$ 号同学依次入列，编号为 $i$ 的同学入列方式为：老师指定编号为 $i$ 的同学站在编号为 $1\sim(i-1)$ 中某位同学（即之前已经入列的同学）的左边或右边；
3. 从队列中去掉 $M$ 个同学，其他同学位置顺序不变。
在所有同学按照上述方法队列排列完毕后，老师想知道从左到右所有同学的编号。
## 输入格式
第一行一个整数 $N$，表示了有 $N$ 个同学。
第 $2\sim N$ 行，第 $i$ 行包含两个整数 $k,p$，其中 $k$ 为小于 $i$ 的正整数，$p$ 为 $0$ 或者 $1$。若 $p$ 为 $0$，则表示将 $i$ 号同学插入到 $k$ 号同学的左边，$p$ 为 $1$ 则表示插入到右边。
第 $N+1$ 行为一个整数 $M$，表示去掉的同学数目。
接下来 $M$ 行，每行一个正整数 $x$，表示将 $x$ 号同学从队列中移去，如果 $x$ 号同学已经不在队列中则忽略这一条指令。
## 输出格式
一行，包含最多 $N$ 个空格隔开的整数，表示了队列从左到右所有同学的编号。
## 样例 #1
### 样例输入 #1
```
4
1 0
2 1
1 0
2
3
3
```
### 样例输出 #1
```
2 4 1
```
## 提示
**【样例解释】**
将同学 $2$ 插入至同学 $1$ 左边，此时队列为：
`2 1`
将同学 $3$ 插入至同学 $2$ 右边，此时队列为：
`2 3 1`
将同学 $4$ 插入至同学 $1$ 左边，此时队列为：
`2 3 4 1`
将同学 $3$ 从队列中移出，此时队列为：
`2 4 1`
同学 $3$ 已经不在队列中，忽略最后一条指令
最终队列：
`2 4 1`
**【数据范围】**
对于 $20\%$ 的数据，$1\leq N\leq 10$。
对于 $40\%$ 的数据，$1\leq N\leq 1000$。
对于 $100\%$ 的数据，$1<M\leq N\leq 10^5$。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int mx=1e5+10;
int n,m;
struct T{
int l,r;
int d;
}t[mx]={0};
void add(int i,int k,int f)
{
if(f==1)
{
t[k].r=t[i].r;
t[k].l=i;
t[i].r=k;
t[t[k].r].l=k;
}
else
{
t[k].r=i;
t[k].l=t[i].l;
t[i].l=k;
t[t[k].l].r=k;
}
}
int main()
{
int x,k,f;
cin>>n;
t[0].r=0,t[0].l=0;
add(0,1,1);
for (int i=2;i<=n;i++)
{
cin>>x>>f;
add(x,i,f);
}
cin>>m;
while(m--)
{
cin>>x;
t[x].d=1;
}
for (int i=t[0].r;i;i=t[i].r)
{
if (t[i].d==0)
cout<<i<<" ";
}
return 0;
}
W5
# [NOIP2009 普及组] 多项式输出
## 题目描述
一元 $n$ 次多项式可用如下的表达式表示：
$$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots +a_1x+a_0,a_n\ne 0$$
其中，$a_ix^i$ 称为 $i$ 次项，$a_i$ 称为 $i$ 次项的系数。给出一个一元多项式各项的次数和系数，请按照如下规定的格式要求输出该多项式：
1. 多项式中自变量为 $x$，从左到右按照次数递减顺序给出多项式。
2. 多项式中只包含系数不为 $0$ 的项。
3. 如果多项式 $n$ 次项系数为正，则多项式开头不出 `+` 号，如果多项式 $n$ 次项系数为负，则多项式以 `-` 号开头。
4. 对于不是最高次的项，以 `+` 号或者 `-` 号连接此项与前一项，分别表示此项系数为正或者系数为负。紧跟一个正整数，表示此项系数的绝对值（如果一个高于 $0$ 次的项，其系数的绝对值为 $1$，则无需输出 $1$）。如果 $x$ 的指数大于 $1$，则接下来紧跟的指数部分的形式为“$x^b$”，其中 $b$ 为 $x$ 的指数；如果 $x$ 的指数为 $1$，则接下来紧跟的指数部分形式为 $x$；如果 $x$ 的指数为 $0$，则仅需输出系数即可。
5. 多项式中，多项式的开头、结尾不含多余的空格。
## 输入格式
输入共有 $2$ 行
第一行 $1$ 个整数，$n$，表示一元多项式的次数。
第二行有 $n+1$ 个整数，其中第 $i$ 个整数表示第 $n-i+1$ 次项的系数，每两个整数之间用空格隔开。
## 输出格式
输出共 $1$ 行，按题目所述格式输出多项式。
## 样例 #1
### 样例输入 #1
```
5
100 -1 1 -3 0 10
```
### 样例输出 #1
```
100x^5-x^4+x^3-3x^2+10
```
## 样例 #2
### 样例输入 #2
```
3
-50 0 0 1
```
### 样例输出 #2
```
-50x^3+1
```
## 提示
NOIP 2009 普及组 第一题
对于100%数据，$0 \le n \le 100$，$-100 \le $系数$ \le 100$
---
$\text{upd 2022.8.1}$：新增加一组 Hack 数据。
~~~~~~~~~~~~~~~~~~~~
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int main(){
int n,a;
cin>>n;
int i=n;
while(n!=-1){
cin>>a;
if(a){
if(n!=i&&a>0)cout<<"+";
if(a*a>1||n==0)cout<<a;
if(a==-1&&n)cout<<"-";
if(n>1)cout<<"x^"<<n;
if(n==1)cout<<"x";
}
n--;
}
return 0;
}
W6
# 【模板题】冒泡排序
## 题目描述
读入$N$个整数，利用**冒泡排序法**对这些数排序，输出排序后的$N$个数，两个数之间用空格间隔。
这里排序指的是升序。
## 输入格式
两行，第一行一个正整数$N$，表示待排序的数的个数。
第二行为$N$个整数。
## 输出格式
一行，排序后的$N$个数。
## 样例 #1
### 样例输入 #1
```
5
4 2 4 5 1
```
### 样例输出 #1
```
1 2 4 4 5
```
## 提示
$1\leq N\leq 10^3$
每个数不超过$10^9$.
~~~~~~~~~~~~~~~~~
#include<iostream>
using namespace std;
int main(){
int a[1000];
int n;
cin>>n;
for(int i=0;i!=n;i++){
cin>>a[i];
}
int i, j;
for (i = 0; i < n; i++)
for (j = 1; j < n - i; j++)
if (a[j - 1] > a[j])
swap(a[j - 1], a[j]);
for(int i=0;i!=n;i++){
cout<<a[i]<<" ";
}
return 0;
}
W7
# 【模板题】简单选择排序
## 题目描述
读入$N$个整数，利用简单选择排序法对这些数排序，输出排序后的$N$个数，两个数之间用空格间隔。
这里排序指的是升序。
## 输入格式
两行，第一行一个正整数$N$，表示待排序的数的个数。
第二行为$N$个整数。
## 输出格式
一行，排序后的$N$个数。
## 样例 #1
### 样例输入 #1
```
5
4 2 4 5 1
```
### 样例输出 #1
```
1 2 4 4 5
```
## 提示
$1\leq N\leq 10^3$
每个数不超过$10^9$.
~~~~~~~~~~~~~~~~~~~~
#include<iostream>
using namespace std;
int main(){
int N,min=0;
cin>>N;
int a[N];
for(int i=0;i<N;i++){
cin>>a[i];
}
for(int i=0;i<N;i++){
min=i;
for(int j=i;j<N;j++){
if(a[j]<a[min]) min=j;
}
if(min!=i) swap(a[i],a[min]);
}
for(int i=0;i<N;i++){
cout<<a[i]<<" ";
}
return 0;
}