NO.1
Description
在一个长方型框子里，最多有N（0≤N≤6）个相异的点。在其中任何一个点上放一个很小的油滴，那么这个油滴会一直扩展，直到接触到其它油滴或者框子的边界。必须等一个油滴扩展完毕才能放置下一个油滴。那么应该按照怎样的顺序在这N个点上放置油滴，才能使放置完毕后所有油滴占据的总体积最大呢？（不同的油滴不会相互融合）
注：圆的面积公式V=pi*r*r，其中r为圆的半径。
Input
第一行一个整数N。
第二行为长方形边框一个顶点及其对角顶点的坐标，x，y，x’，y’。
接下去N行，每行两个整数xi，yi，表示盒子内N个点的坐标。
以上所有的整数都在[-1000, 1000]内。
Output
一行，一个整数，长方体盒子剩余的最小空间（结果四舍五入输出）。
Sample Input
2
0 0 10 10
3 3
7 7
Sample Output
50
思路：DFS+勾股
先用勾股求出每两个点之间的距离
就可以用DFS暴搜
在对于枚举的一个点，求他对于边界、和点的最短距离
记录下当前的半径（因为在我们求两个点的距离的最小值时，前面已求出两个点的距离，那当点被放过，那么两个点之间的距离就是d[i][j]-半径）
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define pi 3.1415926
using namespace std;
double d[15][15],ans,dis,r[15];
int n,x[15],y[15],b[15];
int ok()
{
for(int i=2;i<=n+1;i++)
if(!b[i])return 0;
return 1;
}
double mmin(double x,double y,double z,double p)
{
double num=min(x,y);
num=min(num,z);
num=min(num,p);
return num;
}
void dfs()
{
if(ok()){dis=max(dis,ans);return;}
for(int i=2;i<=n+1;i++)
if(!b[i])
{
double minc=mmin(abs(x[i]-x[0]),abs(x[i]-x[1]),abs(y[i]-y[0]),abs(y[i]-y[1]));
for(int j=2;j<=n+1;j++)
if(j!=i&&b[j])
minc=min(minc,d[i][j]-r[j]);
if(minc<0)minc=0;
b[i]=1;ans+=(minc*minc);r[i]=minc;
dfs();
b[i]=0;ans-=(minc*minc);r[i]=0;
}
}
int main()
{
scanf("%d",&n);
cin>>x[0]>>y[0]>>x[1]>>y[1];
if(n==0)
{
ans=abs(x[0]-x[1])*abs(y[0]-y[1]);
if(ans-(int)ans<0.5)ans=floor(ans);
else ans=floor(ans)+1;
cout<<(int)ans;
return 0;
}
for(int i=2;i<=n+1;i++) cin>>x[i]>>y[i];
for(int j=2;j<=n+1;j++)
for(int i=2;i<=n+1;i++)
if(i!=j)
d[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
dfs();
ans=abs(x[0]-x[1])*abs(y[0]-y[1])-pi*dis;
if(ans-floor(ans)>=0.5)ans=floor(ans)+1;
else ans=floor(ans);
cout<<ans;
return 0;
}NO.2
Description
虽然msh长大了，但她还是很喜欢找点游戏自娱自乐。有一天，她在纸上写了一串数字：1,1,2,5,4。接着她擦掉了一个1，结果发现剩下1,2,4都在自己所在的位置上，即1在第1位，2在第2位，4在第4位。她希望擦掉某些数后，剩下的数列中在自己位置上的数尽量多。她发现这个游戏很好玩，于是开始乐此不疲地玩起来……不过她不能确定最多能有多少个数在自己的位置上，所以找到你，请你帮忙计算一下！
Input
第一行为一个数n，表示数列的长度。
接下来一行为n个用空格隔开的正整数，第i行表示数Ai。
Output
一行一个整数，表示擦掉某些数后，最后剩下的数列中最多能有多少个数在自己的位置上，即Ai=i最多能有多少。
Sample Input
5
1 1 2 5 4
Sample Output
3
Hint
【数据规模】
对于20%的数据，n<=20;
对于60%的数据，n<=100;
对于100%的数据，n<=1000.
思路：DP
如果我们设f[i][j]为前i个数擦掉j个的最大符合数
对于一个点，如果它i-j=a[i]，就说明这个点在擦掉j个数后，它符合条件，那么这种情况的转态转移方程就是f[i][j]=max(f[i-1][j-1],f[i-1][j]+1)
如果不等于，那么就是f[i][j]=max(f[i-1][j-1],f[i-1][j])
代码：
#include<cstdio>
#include<iostream>
using namespace std;
long n,a[100000],ans,f[1000][1000],b[100000];
int main()
{
scanf("%ld",&n);
for (int i=1;i<=n;i++)
{
scanf("%ld",&a[i]);
b[i]=i-a[i];
}
for (int i=1;i<=n;i++)
for (int j=0;j<=i;j++)
{
f[i][j]=f[i-1][j-1];
if (b[i]==j) f[i][j]=max(f[i][j],f[i-1][j]+1);
else f[i][j]=max(f[i][j],f[i-1][j]);
}
for (int i=0;i<=n;i++) ans=max(ans,f[n][i]);
printf("%ld",ans);
}NO.3
Description
一个软件开发公司同时要开发两个软件，并且要同时交付给用户，现在公司为了尽快完成这一任务，将每个软件划分成m个模块，由公司里的技术人员分工完成，每个技术人员完成同一软件的不同模块的所用的天数是相同的，并且是已知的，但完成不同软件的一个模块的时间是不同的，每个技术人员在同一时刻只能做一个模块，一个模块只能由一个人独立完成而不能由多人协同完成。一个技术人员在整个开发期内完成一个模块以后可以接着做任一软件的任一模块。写一个程序，求出公司最早能在什么时候交付软件。
Input
输入文件第一行包含两个由空格隔开的整数n和m，其中1<=n<=100，1<=m<=100，接下来的n行每行包含两个用空格隔开的整数d1和d2，d1表示该技术人员完成第一个软件中的一个模块所需的天数，d2表示该技术人员完成第二个软件中的一个模块所需的天数，其中1<= d1,d2<=100。
Output
输出文件仅有一行包含一个整数d，表示公司最早能于d天后交付软件。
Sample Input
3 20
1 1
2 4
1 6
Sample Output
18
Hint
【样例解释】
最快的方案是第一个技术人员完成第二个软件的18个模块，用时18天，第三个技术人员完成第一个软件的18个模块，用时18天，其余的模块由第二个技术人员完成，用时12天，做完所有模块需要18天。
如果第一个技术人员完成第二个软件的17个模块，第三个技术人员完成第一个软件的17个模块，其余的模块由第二个技术人员完成，需要用时18天，做完所有模块仍然需要18天，所以少于18天不可能做完所有模块。
思路：二分+DP
首先可以二分枚举一个天数time，在判断当前用time天是否符合要求
那么可以设f[i][j]为前i个人第一个软件做了j个模板的第二个软件最多做模板的个数
我们可以这样想，如果从j中分出k个模板的时间去做第二个软件的模板，就可以完成转移了
转态转移方程为f[i][j]=max(f[i][j],f[i-1][j-k]+(time-a[i]*k)/b[i]);
代码：
#include<cstdio>
#include<iostream>
#include<memory.h>
using namespace std;
int n,m,a[105],b[105],f[105][105],ans;
bool pd(int time)
{
for (int i=0;i<=n;i++)
for (int j=0;j<=m;j++)
f[i][j]=-1000000000;
for (int i=0;i*a[1]<=time;i++) f[1][i]=(time-a[1]*i)/b[1];
for (int i=2;i<=n;i++)
for (int j=0;j<=m;j++)
for (int k=0;k*a[i]<=time&&k<=j;k++)
f[i][j]=max(f[i][j],f[i-1][j-k]+(time-a[i]*k)/b[i]);
return f[n][m]>=m;
}
void find()
{
int mid=0,l=0,r=20000;
while (l<=r)
{
mid=(l+r)>>1;
if (pd(mid))
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
find();
printf("%d",ans);
}NO.4
Description
Black Box是一种原始的数据库。它可以储存一个整数数组，还有一个特别的变量 i 。最开始的时候Black Box是空的，而 i 等于 0。这个 Black Box 要处理一串命令。
命令只有两种：
ADD(x): 把 x 元素放进 Black Box;
GET: i 加 1 ，然后输出 Black box 中第 i 小的数。
记住：第 i 小的数，就是 Black Box里的数的按从小到大的顺序排序后的第 i 个元素。
例如
我们来演示一下一个有11个命令的命令串。
现在要求找出对于给定的命令串的最好的处理方法。ADD 和 GET 命令分别最多有200000个。
现在用两个整数数组来表示命令串：
1. A(1), A(2), …, A(M): 一串将要被放进Black Box的元素。每个数都是绝对值不超过2000000000的整数，M <=200000。例如上面的例子就是A=(3, 1, -4, 2, 8, -1000, 2).
2. u(1), u(2), …, u(N): 表示第u(j)个元素被放进了Black Box里后就出现一个GET命令。例如上面的例子中u=(1, 2, 6, 6)。 输入数据不用判错。
Input
第一行，两个整数，M，N，
第二行，M个整数，表示A(1)……A(M)，
第三行，N个整数，表示u(1)……u(N)。
Output
输出 Black Box 根据命令串所得出的输出串，一个数字一行。
Sample Input
7 4
3 1 -4 2 8 -1000 2
1 2 6 6
Sample Output
3
3
1
2
Hint
【数据规模】
对于30%的数据，M<=10000；
对于50%的数据，M<=100000；
对于100%的数据，M<=200000。
一堆大佬打线段树、平衡树，然而我这个蒟蒻神马都不会，只好打了个堆
思路：堆
我们可以维护一个长度为get数量的大根堆，那么第i大的就在小根堆顶
C++自带堆的库，所以。。。
代码:
#include<cstdio>
#include<iostream>
#include <queue>
#define Qmax priority_queue<int>
#define Qmin priority_queue<int,vector<int>,greater<int> >
using namespace std;
int n,m,x,l;
int main()
{
int a[200001];
Qmax A;
Qmin B;
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
l=1;
for (int i=1;i<=m;i++)
{
scanf("%d",&x);
for (int j=l;j<=x;j++)
{
A.push(a[j]);
if (A.size()==i) B.push(A.top()),A.pop();
}
l=x+1;
printf("%d
",B.top());
A.push(B.top()),B.pop();
}
return 0;
}