hdu 4791
A - Alice's Print Service
t n m
a1 b1 a2 b2... an bn
数目 价格
代表你要买东西的数目如果在 a1 到a2 [a1,a2)之间 那么价格是b1 当然你可以买数目更多的时候 可能会便宜 可能会贵
然后m 个查询
c1 ... cm 每个查询输出最少花的钱
n*m的复杂度显然不行
1 二分数目 但是可能后面有更小的 所以可以从后往前维护一个后缀 m log(n)
2 这种方法没事过 离线操作 把查询排序 后缀还是要维护的 应该只是 n + m
long long
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 5 using namespace std; 6 7 #define MAXN 100010 8 #define ll long long 9 int s[MAXN],p[MAXN]; 10 ll sum[MAXN]; 11 12 int main() 13 { 14 int t; 15 scanf("%d",&t); 16 while(t--) 17 { 18 int n,m; 19 scanf("%d%d",&n,&m); 20 for(int i=1;i<=n;i++) 21 { 22 scanf("%d%d",&s[i],&p[i]); 23 } 24 sum[n]=(ll)s[n]*p[n]; 25 for(int i=n-1;i>=1;i--) 26 sum[i]=min(sum[i+1],(ll)s[i]*p[i]); 27 28 while(m--) 29 { 30 int a; 31 scanf("%d",&a); 32 int l=1,r=n; 33 int ans=1; 34 while(l<=r) 35 { 36 int mid=(l+r)>>1; 37 if(s[mid]>a) 38 r=mid-1; 39 else 40 { 41 l=mid+1; 42 ans=max(ans,mid); 43 } 44 } 45 if(ans==n) 46 { 47 printf("%lld ",(ll)p[ans]*a); 48 } 49 else 50 printf("%lld ",min((ll)p[ans]*a,sum[ans+1])); 51 } 52 } 53 return 0; 54 }
J - Josephina and RPG
n 个人 3个人可以组成一队
总数是d=C(n,3);
随意有d*d的矩阵 a[i][j] 代表 i 打败j 的概率
m
然后m 个数字
ai 的队伍 开始你可以挑任意一个队伍 和ai 打
打赢 你可以和刚刚打赢的换队伍 然后接着打 求最大打赢ai所有人的队伍
dp[i][j] 代表 第j个队打赢第i个ai队伍的概率
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define MAXN 100010 #define ll long long double z[130][130]; int x[10010]; double dp[10010][130]; int main() { int n; while(scanf("%d",&n)!=EOF) { int en=n*(n-1)*(n-2)/3/2; for(int i=0;i<en;i++) { for(int j=0;j<en;j++) scanf("%lf",&z[i][j]); } int m; scanf("%d",&m); for(int i=1;i<=m;i++) scanf("%d",&x[i]); double mx=0; memset(dp,0,sizeof(dp)); for(int i=0;i<en;i++) dp[1][i]=z[i][x[1]]; for(int i=2;i<=m;i++) { for(int j=0;j<en;j++) { dp[i][j]=max(dp[i][j],dp[i-1][j]*z[j][x[i]]); dp[i][x[i-1]]=max(dp[i][x[i-1]],dp[i-1][j]*z[x[i-1]][x[i]]); } } for(int i=0;i<en;i++) mx=max(mx,dp[m][i]); printf("%.6lf ",mx); } return 0; }
G++会re
K - Pocket Cube
k 然后24个数 代表魔方每个面的颜色
问 k步以内 最多 整个面的颜色相同 最多多少个面
dfs 方向
#include<stdio.h> #include<string.h> #include<algorithm> #include<string> #include<iostream> using namespace std; #define MAXN 100010 #define ll long long int mx,n; int s[7][24]={ 1,3,0,2,23,22,4,5,6,7,10,11,12,13,14,15,16,17,18,19,20,21,9,8, 0,1,2,3,4,5,6,7,8,9,21,20,10,11,12,13,18,16,19,17,15,14,22,23, 6,1,12,3,5,11,16,7,8,9,4,10,18,13,14,15,20,17,22,19,0,21,2,23, 0,7,2,13,4,5,6,17,14,8,10,11,12,19,15,9,16,21,18,23,20,1,22,3, 0,1,11,5,4,16,12,6,2,9,10,17,13,7,3,15,14,8,18,19,20,21,22,23, 10,4,2,3,18,5,6,7,8,0,19,11,12,13,14,1,16,17,15,9,21,23,20,22, }; void dfs(int a,int cnt,int x[]) { if(cnt>n) return ; int y[24]; for(int i=0;i<24;i++) y[i]=x[s[a][i]]; int c1=0; if(y[0]==y[1]&&y[0]==y[2]&&y[0]==y[3]) c1++; if(y[4]==y[5]&&y[4]==y[10]&&y[4]==y[11]) c1++; if(y[6]==y[7]&&y[6]==y[12]&&y[6]==y[13]) c1++; if(y[8]==y[9]&&y[8]==y[14]&&y[8]==y[15]) c1++; if(y[16]==y[17]&&y[16]==y[18]&&y[16]==y[19]) c1++; if(y[20]==y[21]&&y[20]==y[22]&&y[20]==y[23]) c1++; mx=max(mx,c1); for(int i=0;i<=5;i++) dfs(i,cnt+1,y); } int main() { int z[24]; while(scanf("%d",&n)!=EOF) { mx=0; for(int i=0;i<24;i++) scanf("%d",&z[i]); int c1=0; if(z[0]==z[1]&&z[0]==z[2]&&z[0]==z[3]) c1++; if(z[4]==z[5]&&z[4]==z[10]&&z[4]==z[11]) c1++; if(z[6]==z[7]&&z[6]==z[12]&&z[6]==z[13]) c1++; if(z[8]==z[9]&&z[8]==z[14]&&z[8]==z[15]) c1++; if(z[16]==z[17]&&z[16]==z[18]&&z[16]==z[19]) c1++; if(z[20]==z[21]&&z[20]==z[22]&&z[20]==z[23]) c1++; mx=max(mx,c1); for(int i=0;i<=5;i++) dfs(i,1,z); printf("%d ",mx); } return 0; }
C - Collision
Rm R r x y vx vy
在原点 有Rm R 2个圆 x y 有个 r 的运动的圆 速度 vx vy
运动的圆 可以走到R里面 但是碰到 Rm 会被弹回去 保证动圆在外面
问在R里面运行多久
x'=x+vx*t;
y'=y+vy*t;
x'^2+y'^2=(r1+r2)^2
求出的解就是相外切的时间 然后讨论下就行
#include<stdio.h> #include<string.h> #include<algorithm> #include<string> #include<iostream> #include<math.h> using namespace std; #define MAXN 100010 #define ll long long #define exp 1e-8 int main() { int r1,r2,r3,x,y,vx,vy; while(scanf("%d%d%d%d%d%d%d",&r1,&r2,&r3,&x,&y,&vx,&vy)!=EOF) { //r2 最大 double a1,b1,c1,a2,b2,c2; a1=vx*vx+vy*vy; b1=2*x*vx+2*y*vy; c1=x*x+y*y-(r2+r3)*(r2+r3); a2=a1; b2=b1; c2=x*x+y*y-(r1+r3)*(r1+r3); double d1=b1*b1-4*a1*c1; double d2=b2*b2-4*a2*c2; double x11,x12,x21,x22; x11=(-b1+sqrt(d1))/2/a1; x12=(-b1-sqrt(d1))/2/a1; x21=(-b2+sqrt(d2))/2/a2; x22=(-b2-sqrt(d2))/2/a2; if(d1<=exp) printf("0.000 "); else if(x11>exp) { if(d2<=exp) printf("%.3lf ",x11-x12); else printf("%.3lf ",x11-x12-(x21-x22)); } else printf("0.000 "); } return 0; }
H - Skycity
圆台 R r h 分成 f 层 每层高度相同 然后有个面积S
每层 的边上要被正多边形包起来 也就是相切 多边形变要尽量少
正多变行的长 * 一层的高度>=s
二分边的数目
#include<stdio.h> #include<string.h> #include<algorithm> #include<string> #include<iostream> #include<math.h> using namespace std; #define MAXN 100010 #define ll long long #define exp 1e-8 double pi =atan(1.0)*4; double get(int n,double r1) { return 2.0*r1*tan(pi/n); } int main() { int R,r,h,f,s; while(scanf("%d%d%d%d%d",&R,&r,&h,&f,&s)!=EOF) { double a=1.0*(R-r)/f; int limit=100000; double ans=0; for(int i=1;i<=f;i++) { // printf("11 "); double r1=R-i*a; int ma=limit; int mi=3; int num=0; double mx=0; while(mi<=ma) { int mid=(mi+ma)>>1; double l1=get(mid,r1); double S=l1*h/f; if(S-s>exp) { mi=mid+1; mx=S; num=mid; } else ma=mid-1; } ans=ans+mx*num; //printf("%d %lf ",num,mx); limit=num; } printf("%.3lf ",ans); } return 0; }