首页 > 代码库 > 2016.9.15 --- 2014 北京
2016.9.15 --- 2014 北京
1001 A Curious Matt
求最大的平均速度
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 7 typedef long long LL; 8 const int maxn = 1e5+5; 9 int n,m;10 11 struct node{12 int x,t;13 }a[maxn];14 15 int cmp(node n1,node n2){16 return n1.t < n2.t;17 }18 19 void solve(){20 double ans = 0;21 sort(a+1,a+n+1,cmp);22 for(int i = 2;i <= n;i++){23 int fz = abs(a[i].x-a[i-1].x);24 int fm = a[i].t - a[i-1].t;25 double res = (1.0*fz)/(1.0*fm);26 ans = max(ans,res);27 }28 printf("%.2lf\n",ans);29 }30 31 int main(){32 int T;33 int kase = 0;34 scanf("%d",&T);35 while(T--){36 scanf("%d",&n);37 for(int i = 1;i <= n;i++){38 scanf("%d %d",&a[i].t,&a[i].x);39 }40 printf("Case #%d: ",++kase);41 solve();42 }43 return 0;44 }
1002 Black And White
n*m 的格子，一共 k 种颜色
c1 + c2 + c3 +...+ck = n*m 求相邻格子的颜色不同的染色方案
题解说的本应该是构造，姿势好的爆搜也可以过
剪枝 是 当一种颜色超过剩余格子的一半的时候，就不行了
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 7 int ans[15][15],c[105],n,m,k; 8 int flag; 9 int cnt[105];10 11 void print(){12 puts("YES");13 for(int i = 1;i <= n;i++){14 for(int j = 1;j < m;j++) printf("%d ",ans[i][j]);15 printf("%d\n",ans[i][m]);16 }17 }18 19 bool dfs(int x,int y){20 for(int i = 1;i <= k;i++){21 if((n*m - (x-1)*m-y+2)/2 < c[i]) return false;22 }23 for(int i = 1;i <= k;i++){24 if(c[i]){25 if(ans[x][y-1] == i || ans[x-1][y] == i) continue;26 ans[x][y] = i;27 //printf("ans[%d][%d] = %d\n",x,y,ans[x][y]);28 c[i]--;29 if(x == n && y == m){print();return true;}30 if(y != m && dfs(x,y+1)) return true;31 if(y == m && dfs(x+1,1)) return true;32 c[i]++;33 }34 }35 return false;36 }37 38 int cmp(int x,int y){39 return x > y;40 }41 42 void solve(){43 flag = 0;44 for(int i = 1;i <= k;i++){45 if(c[i] > (n*m+1)/2){46 puts("NO");47 return;48 }49 }50 memset(ans,0,sizeof(ans));51 if(k == 1 && n*m != 1){52 puts("NO");53 return;54 }55 if(dfs(1,1)) return;56 puts("NO");57 }58 59 int main(){60 int T,kase = 0;61 scanf("%d",&T);62 while(T--){63 scanf("%d %d %d",&n,&m,&k);64 for(int i = 1;i <= k;i++) {65 scanf("%d",&c[i]);66 }67 printf("Case #%d:\n",++kase);68 solve();69 }70 return 0;71 }
1003 Collision
给出一个矩形.两个开始的点，运动速度都相同，运动方向是 （1,1）碰到矩形的边的时候，会发生弹性碰撞
求第一次碰撞的坐标..
第三个样例画不出来怎么撞的啊...第二个点不是运动出去了么...wwww
不懂
1004 Dire Wolf
有 n 只狼排成一排，每只狼有一个初始的伤害值ai ，同时每只狼还有附加的伤害值 bi ，每只狼可以给它相邻的狼增加伤害值，杀死一只狼需要的伤害值 是 ai + bi-1,bi+1
可以任意选择杀狼的顺序，问杀死这 n 只狼需要的最小的伤害值
比赛的时候，还是没太搞清楚伤害值该怎么去算，dp 顺序有问题，而且转移也有问题
dp[i][j] 表示 杀死从i 到 j 的狼所需要的最小伤害值
枚举这段区间最后杀死的狼 是 k ，那么杀死这只狼的代价，就是 a[k] + b[i-1] + b[j+1] （因为它是最后一只狼，左右两端是 i-1,j+1）
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 7 typedef long long LL; 8 const int maxn = 205; 9 int a[maxn],b[maxn],dp[maxn][maxn];10 const int INF = (1<<30)-1;11 int n;12 13 void solve(){14 dp[0][0] = 0;15 b[0] = b[n+1] = 0;16 for(int i = 1;i <= n;i++){17 for(int j = 1;j <= n;j++){18 if(i == j) dp[i][i] = a[i]+b[i-1]+b[i+1];19 else dp[i][j] = INF;20 }21 }22 23 for(int l = 2;l <= n;l++){24 for(int s = 1;s+l-1 <= n;s++){25 int e = s+l-1;26 for(int k = s;k <= e;k++){27 if(k == s) dp[s][e] = min(dp[s][e],dp[s+1][e]+a[s]+b[s-1]+b[e+1]);28 else if(k == e) dp[s][e] = min(dp[s][e],dp[s][e-1]+a[e]+b[e+1]+b[s-1]);29 else{30 dp[s][e] = min(dp[s][e],dp[s][k-1]+dp[k+1][e]+a[k]+b[s-1]+b[e+1]);31 }32 }33 }34 }35 printf("%d\n",dp[1][n]);36 }37 38 int main(){39 int T,kase = 0;40 scanf("%d",&T);41 while(T--){42 scanf("%d",&n);43 for(int i = 1;i <= n;i++) scanf("%d",&a[i]);44 for(int i = 1;i <= n;i++) scanf("%d",&b[i]);45 printf("Case #%d: ",++kase);46 solve();47 }48 return 0;49 }
1005 Everlasting L
给出 一个点集，称这样的点集是 good 的
(x,y),(x+1,y),....(x+a,y),(x,y+1),(x,y+2),.... (x,y+b) gcd(a,b) = 1
问点集中满足，A ,B都是 good 且 A交B为空 的有多少对
不会捉..搜一个题解说是dp
1006 Fluorescent
一共 m 个开关，每个开关控制一些灯
最后灯亮的个数为 X ，求 X^3的期望
设最后灯亮的情况为 x1 + x2 + x3 +... +xn
所以 x^3 可以写成 (x1+x2+x3+...+xn)*(x1+x2+...+xn)*(x1+x2+...+xn)
x^3 就是 sum(xi*xj*xk) （1 <= i ,j , k <= n）只有当 xi ,xj ,xk 都为 1 的时候才对答案有贡献
1007 GRE Words Once More!
1008 Happy Matt Friends
1009 Intersection
1010 Just A Mistake
1011 K.Bro Sorting
2016.9.15 --- 2014 北京