Draw Something http://acm.hdu.edu.cn/showproblem.php?pid=4450
o（n）统计输入每个数的平方和。
#include<cstdio>
int main(){
int n,x;
while(~scanf("%d",&n),n){
int ans=;
while(n--){
scanf("%d",&x);
ans+=x*x;
}
printf("%d\n",ans);
}
return ;
}
Physical Examination http://acm.hdu.edu.cn/showproblem.php?pid=4442
有n个任务要完成，每个任务有x，y两个权值。完成某个任务所需的时间是x+t*y，其中t是当前的时间，也就是之前所有任务的时间总和。为了使总时间小。
贪心的算法。
考虑x，x不论放哪里，对于当前任务的贡献值都是x，但是对后面所有任务的t都有贡献，所以x越小越先做，这样后面t就会相对较小，使得后面任务所需时间也小。
考虑y，y放哪里，对当前任务贡献值是t*y，也就是说y越大，越要先做，因为先做的t肯定比后做的小，而且这样也会使得对之后的贡献值减小。
综上所诉，x越小y越大，那么越优先，定义一个优先系数用x/y表示，系数越小，越先做。因为可能有除不尽的情况，我又不想用double，等下精度又gg，所以转化了一下。
a.x/a.y < b.x/b.y => a.x*b.y <b.x*a.y
o（n*log（n））
#include<cstdio>
#include<algorithm>
using namespace std;
typedef __int64 LL;
const int M=;
const int mod=***;
struct G{
LL x,y;
friend bool operator <(G a,G b){
return a.x*b.y<b.x*a.y;
}
}p[M];
int main(){
int n,x;
while(~scanf("%d",&n),n){
for(int i=;i<n;i++){
scanf("%I64d%I64d",&p[i].x,&p[i].y);
}
sort(p,p+n);
LL ans=,now=;
for(int i=;i<n;i++){
ans+=p[i].x+now*p[i].y;
ans%=mod;
now=ans;
}
printf("%I64d\n",ans);
}
return ;
}
Dressing http://acm.hdu.edu.cn/showproblem.php?pid=4451
根据输入p=10^6处理出两两之间是否有关系，有关系就不能匹配。然后n^2的处理出每一个pants能匹配几个shoes，然后n^2的枚举clothes 和 pants，通过之前处理的值可以直接算出包含这对衣服裤子的匹配数。
总的复杂度还是o（n^2）
#include<cstdio>
#include<cstring>
#define mt(a,b) memset(a,b,sizeof(a))
const int M=;
int sum[M];
bool ctop[M][M],ptos[M][M];
char a[],b[];
int main(){
int n,m,k,p,x,y;
while(~scanf("%d%d%d",&n,&m,&k),n|m|k){
scanf("%d",&p);
mt(ctop,);
mt(ptos,);
while(p--){
scanf("%s%d%s%d",a,&x,b,&y);
if(a[]=='c'){
ctop[x][y]=true;
}
else{
ptos[x][y]=true;
}
}
mt(sum,);
for(int i=;i<=m;i++){
for(int j=;j<=k;j++){
if(!ptos[i][j]){
sum[i]++;
}
}
}
int ans=;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(!ctop[i][j]){
ans+=sum[j];
}
}
}
printf("%d\n",ans);
}
return ;
}
Running Rabbits http://acm.hdu.edu.cn/showproblem.php?pid=4452
o(n)的模拟题。题目怎么说怎么做。题目说11，和nn有两人有初始方向，告诉你每秒的速度，几秒左转一次，撞墙了就向后转把剩余步数走完，两个相遇在同一个点交换方向，万一正好要左转那就忽略这次左转。
#include<cstdio>
#include<algorithm>
using namespace std;
struct G{
int x,y,dir,s,t;
}A,B;
int change(int x){
if(x==) return ;
if(x==) return ;
if(x==) return ;
if(x==) return ;
}
void turnleft(G &C){
C.dir=change(C.dir);
}
int getdir(char c){
if(c=='E') return ;
if(c=='W') return ;
if(c=='N') return ;
if(c=='S') return ;
}
int dx[]={,,-,};
int dy[]={,-,,};
int n,k;
int really(int x){
if(x>=&&x<=n) return x;
if(x>n) return n-(x-n);
if(x<) return +(-x);
}
void onestep(G &C){
int tx=C.x+dx[C.dir]*C.s;
int ty=C.y+dy[C.dir]*C.s;
C.x=really(tx);
C.y=really(ty);
if(C.x!=tx||C.y!=ty){
C.dir^=;
}
}
int main(){
char op[];
while(~scanf("%d",&n),n){
scanf("%s%d%d",op,&A.s,&A.t);
A.dir=getdir(op[]);
A.x=A.y=;
scanf("%s%d%d",op,&B.s,&B.t);
B.dir=getdir(op[]);
B.x=B.y=n;
scanf("%d",&k);
for(int i=;i<=k;i++){
onestep(A);
onestep(B);
if(A.x==B.x&&A.y==B.y){
swap(A.dir,B.dir);
continue;
}
if(!(i%A.t)) turnleft(A);
if(!(i%B.t)) turnleft(B);
}
printf("%d %d\n%d %d\n",A.x,A.y,B.x,B.y);
}
return ;
}
Crazy Tank http://acm.hdu.edu.cn/showproblem.php?pid=4445
有n个炮弹，每个炮弹有各自的速度，炮的角度可以任意选，但是选了之后就不能改变了。敌方有区间L1R1，我方有区间L2R2。现在问在保证没有炮弹进入我方的情况下，最多能有几个炮弹进入敌方区间。
算法，暴力枚举角度θ，算这个角度下满足题意有几个。枚举了1000个角度过了，复杂度200*1000*testcase。
抛物线速度时间都是对称的。枚举的是炮和y轴的角度θ。在这个角度下水平速度Vx=Vi*sin（θ） 垂直速度 Vy=Vi*cos（θ）
达到最高点的时间 t1=Vy/g g=9.8重力加速度
对于对称点到地面 距离H=Vy*t2+1/2*g*t2*t2
解出t2 总时间 t = 2*t1+t2 水平位移 s=Vx*t
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const double eps=1e-;
const double pi=acos(-1.0);
const double g=9.8;
const int M=;
double v[M],H,L1,R1,L2,R2;
void solve2ci(double A,double B,double C,double &x1,double &x2){
double delta=B*B-*A*C;
x1=(-B+sqrt(delta))/(*A);
x2=(-B-sqrt(delta))/(*A);
}
int main(){
int n;
while(~scanf("%d",&n),n){
scanf("%lf%lf%lf%lf%lf",&H,&L1,&R1,&L2,&R2);
for(int i=;i<n;i++){
scanf("%lf",&v[i]);
}
double add=180.0/;
double xita,Vx,Vy,t1,t2,t,s,x1,x2,A=0.5*g,B,C=-H;
int ans=;
for(double x=;x<;x+=add){
xita=x*pi/;
int sum=;
for(int i=;i<n;i++){
Vx=v[i]*sin(xita);
Vy=v[i]*cos(xita);
B=Vy;
solve2ci(A,B,C,x1,x2);
t1=Vy/g;
t2=max(x1,x2);
t=t1+t1+t2;
s=Vx*t;
if(L2-eps<s&&s<R2+eps){
sum=;
break;
}
if(L1-eps<s&&s<R1+eps){
sum++;
}
}
ans=max(ans,sum);
}
printf("%d\n",ans);
}
return ;
}
end