? 今天下午日常考试，交上去的时候以为稳稳300(满分),一评测190，**真香**。好吧，那来总结下本次考试。
**题面**
**和为给定数** (sum.cpp)
**【题目描述】**
给出若干个整数，询问其中是否有一对数的和等于给定的数。
**【输入】**
第一行是整数n(0 < n ≤ 100,000)，表示有n个整数。
第二行是n个整数。整数的范围是在0到10^8之间。
第三行是一个整数m（0≤m≤2^30)，表示需要得到的和。
**【输出】**
若存在和为m的数对，输出两个整数，小的在前，大的在后，中间用单个空格隔开。若有多个数对满足条件，选择数对中较小的数更小的。若找不到符合要求的数对，输出一行No。
**【输入样例】**
4
2 5 1 4
6
**【输出样例】**
1 5
** **
**插队**(que.cpp)
【题目描述】
有N个人（编号1到N）排队，一开始这N个人从1到N号顺序排队，接下来出现Q次插队，每一次为X号插入到了Y号的后面，询问最终结果。
【输入】
第一行两个数字，代表N，Q
接下来Q行，每行两个数字X，Y代表X号插入到了Y号的后面
【输出】
Q次插入后的结果
【输入样例】
53
12
24
35
【输出样例】
14 2 5 3
【样例解释】
原始数据：1 2 3 4 5
一次插队：2 1 3 4 5
两次插队：1 3 4 2 5
三次插队：1 4 2 5 3
【提示】
1<=N， Q<=100000
## 方格取数（弱化版）(box.cpp)
## 题目描述
设有N*N的方格图(N<=10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示（见样例）：
某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数。
此人从A点到B 点，试找出1条这样的路径，使得取得的数之和为最大。
## 输入
输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。
## 输出
只需输出一个整数，表示路径上取得的最大的和。
## 样例输入
```
8
```
```
2 3 13
```
```
2 6 6
```
```
3 5 7
```
```
4 4 14
```
```
5 2 21
```
```
5 6 4
```
```
6 3 15
```
```
7 2 14
```
```
0 0 0
```
## 样例输出
```
36
```
# **题解**
### sum.cpp
~~比较简单~~，用二分查找就可以了，提交，90分。 （啪~啪）
后来发现是数组开的不够大，加大了一些就过了
```
#include<bits/stdc++.h>
using namespace std;
int n,m,s[100009],i; //注意这里要开大一点
int ans[1005][3],p;
bool b=true;
int rain(int x){ //二分模板
int l=1,r=n,mid;
while(l<=r)
{
mid=l+((r-l)>>1);
if(s[mid]==x)return mid;
if(s[mid]<x)l=mid+1;
if(s[mid]>x)r=mid-1;
}
return 0;
}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&s[i]);
scanf("%d",&m);
sort(s+1,s+n+1);
for(i=1;s[i]<=m/2;i++)
{
if(rain(m-s[i]) && rain(m-s[i])!=i)
{
p++;
ans[p][1]=s[i];
ans[p][2]=m-s[i];
b=false;
}
}
int minn=9999999,minx;
if(!b){
for(i=1;i<=p;i++){
if(ans[i][1]>ans[i][2])swap(ans[i][1],ans[i][2]);
if(ans[i][1]<minn){
minn=ans[i][1];
minx=i;
}
}
printf("%d %d",ans[minx][1],ans[minx][2]);
}
else if(b)printf("No");
return 0;
}
```
### que.cpp
这道题目交上去的时候以为是稳100的，可结果是0分啊！！！0分啊！！！
自己看了半天没看出问题来，（以下是刚开始的伪代码）
```
int rain(){
if(f[x] > f[y]){
for(j=f[x]-1;j>=f[y]+1;j--){
f[s[j]]++;
s[j+1]=s[j];
}
}
else{
for(j=f[x]+1;j<=f[y];j++){
f[s[j]]--;
s[j-1]=s[j];
}
}
}
int main(){
scanf("%d%d",&n,&t);
for(i=1;i<=n;i++)f[i] = s[i] = i;
for(i=1;i<=t;i++){
scanf("%d%d",&x,&y);
rain();
f[x] = x;
s[y] = x;
}
for(i=1;i<=n;i++)printf("%d ",s[i]);
}
```
后来看了半天实在没看懂只能屁颠屁颠跑去问老师，标程是张这样的~~（落差好大）~~：
```
#include<cstdio>
#define maxn 393939
using namespace std;
int n, q, x, y;
int f[maxn], g[maxn], head;
int main(){
freopen("que10.in", "r", stdin);
freopen("que10.out", "w", stdout);
scanf("%d%d", &n, &q);
for(int i = 1; i < n+1; i++)f[i] = i+1, g[i] = i-1;
head = 1;
while(q--){
scanf("%d%d", &x, &y);
if(x==head)head = f[x];
f[g[x]] = f[x];
g[f[x]] = g[x];
f[x] = f[y];
g[f[y]] = x;
f[y] = x;
g[x] = y;
}
int i = head, j = 0;
while(i!=n+1){
printf("%d ", i);
i = f[i];
}
return 0;
}
```
### box.cpp
标准的动态规划，比较简单。
每个点的最大值用递推公式得：max(sum[x-1][y],sum[x][y-1])+s[x][y]
那么这道题目的思路就清晰了：把每个点的最大值得出，然后输出就行了；
但据说原题不是张这样的，原题链接：https://www.luogu.org/problemnew/show/P1004
```
#include<bits/stdc++.h>
#define l 15
using namespace std;
int x,y,z;
int n,s[l][l],sum[l][l];
int t,i,j;
int rain(int x,int y){return max(sum[x-1][y],sum[x][y-1])+s[x][y];}
int main(){
scanf("%d",&n);
while(scanf("%d %d %d",&x,&y,&z)){
if(x==0 && y==0 && z==0)break;
s[x][y] = z;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
sum[i][j]=rain(i,j);
printf("%d\n",sum[n][n]);
return 0;
}
```
原文：https://www.cnblogs.com/jiangfengyang/p/10809685.html