1001：
签到题，二分一下即可
代码：
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-;
const int maxn = 1e5+;
ll s[maxn],p[maxn],q[maxn];
ll res[maxn],minv[maxn];
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int t;
scanf ("%d",&t);
while (t--)
{
int n,m;
scanf ("%d%d",&n,&m);
minv[] = inf;
for (int i = ; i < n; i++)
{
scanf ("%I64d%I64d",s+i,p+i);
res[i] = (s[i]-) * p[i];
}
minv[n] = (ll)<<;
for (int i = n - ; i >= ; i--)
{
minv[i] = min(res[i],minv[i+]);
}
for (int i = ; i < m; i++)
scanf ("%I64d",q+i);
for (int i = ; i < m; i++)
{
int idx = lower_bound(s,s+n,q[i]) - s;
ll ans = q[i] * p[idx-];
printf("%I64d\n",min(ans,minv[idx]));
}
}
return ;
}
1003：
题意：
几何题，有两个同心圆，撞到小圆会反弹，求在大圆中呆的时间
解法：
先判断能否进去，再判断能否碰撞
代码：
#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std; const double eps=1e-;
int dcmp(double x)
{
if(fabs(x)<eps)
return ;
else
return x<?-:;
} double dot(double x1,double y1,double x2,double y2)
{
return x1*x2+y1*y2;
} int main()
{
//freopen("in.txt","r",stdin);
double rmax, rmin, r, x, y;
double vx, vy;
while(~scanf("%lf%lf%lf%lf%lf%lf%lf",&rmin, &rmax, &r, &x, &y, &vx, &vy))
{
if(dcmp(vx)==)
vx=eps;
double k=vy/vx;
double d=fabs(y-k*x)/sqrt(k*k+); // 不能相交
if(d>=r+rmax || dot(x,y,vx,vy)>)
{
printf("0\n");
continue;
} if(d>r+rmin)
{
double l1=sqrt((rmax+r)*(rmax+r)-d*d);
double t=l1/sqrt(vx*vx+vy*vy)*.;
printf("%.6f\n",t);
continue;
}
double l1=sqrt((rmax+r)*(rmax+r)-d*d);
double l2=sqrt((rmin+r)*(rmin+r)-d*d);
double t=(l1-l2)/sqrt(vx*vx+vy*vy)*.;
printf("%.6f\n",t);
} return ;
}
1007：
题意：
有一个图，已知每个点的度数，问能否还原这个简单图，如果有多种方案要全部输出
简单图的定义是没有重边和自环
解法：
havel定理http://www.cnblogs.com/oneshot/p/4117632.html
1009:
题意：
有一棵树，每个点有一个权值（票数），还有一个种类，代表给like或者candle投票，每次可以花费x代价翻转某个子树，对于某些点他们已经被别人翻转，再次翻转的代价是y
消耗代价就是消耗like的票数（可以无限消耗，即使为负），求最后like和candle投票的差值得最大值
解法：
树形dp
每个点维护两个值，一个代表差值最大为多少，另一个代表差值最小为多少，进行转移即可
代码：
还没写
1010：
题意：
有c(m,3)支队伍，起初可以选一支，每次打败某只队伍后可以换成被打败的队伍，打败是有概率的，最后求最大概率
解法：
数据范围不大，直接dp就可以了
代码：
#include <iostream>
#include <stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<ctype.h>
#include<math.h>
using namespace std;
#define eps 0.00000000001
int M,m,n;
double g[][];
int a[];
double dp[][];
void ini()
{
M=m*(m-)*(m-)/;
for(int i=;i<M;i++)
{
for(int j=;j<M;j++)
scanf("%lf",g[i]+j);
}
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",a+i);
}
}
void solve()
{
memset(dp,,sizeof(dp));
for(int i=;i<M;i++)
{
dp[][i]=1.0;
}
for(int i=;i<=n;i++)
{
for(int j=;j<M;j++)
{
if(fabs(dp[(i-)%][j])<eps)
{
continue;
}
dp[i%][j]=max(dp[i%][j],dp[(i-)%][j]*g[j][a[i]]);
dp[i%][a[i]]=max(dp[i%][a[i]],dp[(i-)%][j]*g[j][a[i]]);
dp[(i-)%][j]=;
}
}
double ans=;
for(int i=;i<M;i++)
{
ans=max(ans,dp[n%][i]);
}
printf("%.6f\n",ans);
}
int main()
{
while(scanf("%d",&m)!=EOF)
{
ini();
solve();
}
return ;
}
1011：
题意：
给一个二维魔方的初始状态，求还原此魔方的最小步数，且步数不超过n步
解法：
由于限定了上界，所以直接dfs
代码：
#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std; int n;
int state[];
const int same[][]={
{,,,},
{,,,},
{,,,},
{,,,},
{,,,},
{,,,}
}; const int change[][]=
{
{,,,,,,,,,,,,,,,,,,,,,,,},
{,,,,,,,,,,,,,,,,,,,,,,,},
{,,,,,,,,,,,,,,,,,,,,,,,},
{,,,,,,,,,,,,,,,,,,,,,,,},
{,,,,,,,,,,,,,,,,,,,,,,,},
{,,,,,,,,,,,,,,,,,,,,,,,}
};
int tmp[];
void Change(int type)
{
for(int i=;i<;i++)
tmp[i]=state[change[type][i]]; memcpy(state,tmp,sizeof tmp);
} // 得到相同的面数
int getSame()
{
int ans=;
for(int i=;i<;i++)
for(int j=;j<;j++)
if(state[same[i][]]!=state[same[i][j]])
{
ans--;
break;
}
return ans;
} int ans=;
void dfs(int cur=)
{
ans=max(ans,getSame());
if(cur>=n)
return ;
for(int i=;i<;i++)
{
Change(i);
dfs(cur+);
Change(i^);
}
} int main()
{
//freopen("in.txt","r",stdin); while(~scanf("%d",&n))
{
for(int i=;i<;i++)
scanf("%d",&state[i]);
ans=getSame();
dfs();
printf("%d\n",ans);
} return ;
}