以后不好意思放报告就在这记一下心得啦
POJ1083
http://wenku.baidu.com/view/98287f0c844769eae009edf9.html 这个说此题是DP, 我琢磨了一下贪心不就行嘛, 再看了下discuss连贪心都不用.. 将路线的线段压扁后, 设最多的地方有n层, 那么最优解显然不会n, 可以推出必然总是存在至少一个点上有m条线段, 因为每一个点上有多少条线段都是常数, 这显然也是不成立的..
STL好好用 =D swap() max_element()
#include <stdio.h> #include <algorithm> #include <string.h> using namespace std; int main() { int T,N; scanf("%d",&T); while(T--) { scanf("%d",&N); int s,t,press[200]; memset(press,0x00,sizeof(press)); for(int i=0;i<N;i++) { scanf("%d%d",&s,&t); if(s>t) swap(s,t); for(int k=(s-1)>>1;k<=(t-1)>>1;k++) press[k]++; } printf("%d\n",*max_element(press,press+200)*10); } return 0; }
POJ1456
又是DP list上的题目想了想用贪心做了.. 算法没啥难度细节挺恶心, 数据结构又用了位, 感觉思维复杂度和struct差不多, 打出来酷一点..
恶心了有两小时.. 大概是有点困了
#include <stdio.h> #include <stdlib.h> int __comp1(const void *a,const void *b) { return (*(int *)a&((1<<14)-1)) - (*(int *)b&((1<<14)-1)); } int __comp2(const void *a,const void *b) { return (*(int *)a>>14) - (*(int *)b>>14); } int seqMax(int a[],int from,int to) { int p=from; for(int i=from+1;i<=to;i++) { if((a[p]>>14)<(a[i]>>14)) p=i; } int r=(a[p]>>14); a[p]=a[to]; return r; } int main() { int a[10001],n; while(1) { if(scanf("%d",&n)==EOF) break; for(int i=0;i<n;i++) { scanf("%d",a+i); a[i]<<=14; int temp; scanf("%d",&temp); a[i]+=temp; } qsort(a,n,sizeof(int),__comp1); int edge=-1; int head=n-1; int result=0; for(int i=n-1;i>=0 && head >=0;) { for(;head>0;head--) if((a[head-1]&((1<<14)-1))!=edge) break; int days=(a[head]&((1<<14)-1))-(head==0?0:(a[head-1]&((1<<14)-1))); //qsort(a+head,i-head+1,sizeof(int),__comp2); too much time cost, according to the test data int cut=(i-head+1)<days?(i-head+1):days; for(int j=0;j<cut;j++) result+=seqMax(a,head,i--); head--; } printf("%d\n",result); } return 0; }
POJ 1730
*pow()以后就用double pow(double a,double b)不要多想
*接上面, 算一个数的开房, 可以b=1/n. 需要注意的是a是负数时即使n是奇数, 函数值也是NaN
*判断NaN可以 a!=a 或使用
中的isnan() . a!=a是因为所有带有NaN的逻辑表达式值都为false, a!=a就是!(a==a)
*这道囧题说”The value of x will have magnitude at least 2″(绝对值>=2, 有可能是负的), 重点是”and be within the range of a (32-bit) int”, 但是当时是ISO C90的标准,那时候2^31还是在int型以内的.. 所以2^31要单独考虑或者用long long.. 太囧了阿..
#include <stdio.h> #include <math.h> int main() { while(1) { long long n; scanf("%lld",&n); if(!n) break; int max=1; for(int i=31;i>=2;i--) { if(n<0 && !(i%2)) continue; long long __n=(long long)fabs((double)n); double m=pow((double)__n,(double)1/i); if(m-(int)m<1E-12||(int)m+1-m<1E-12) { max=i>max?i:max; break; } } printf("%d\n",max); } return 0; }
POJ 1953
就是Fibonacci数列, 推了一下发现a[i] = sum(a[k])+1, k=1..i-2
#include <stdio.h> int main() { int dp[46][2]; dp[0][0]=1; dp[0][1]=0; for(int i=1;i<=45;i++) { dp[i][0]=dp[i-1][0]+dp[i-1][1]; dp[i][1]=dp[i-1][0]; } int N; scanf("%d",&N); for(int i=1;i<=N;i++) { int a; scanf("%d",&a); printf("Scenario #%d:\n%d\n\n",i,dp[a+1][0]); } return 0; }
来支持下神牛。Orz.你是在哪读书?
= = 不敢当, 赶紧拜回去.. Orz
扬州有个大学叫扬州大学.. 我就在那里, 神奇吧…
大三了, 没时间了, 拼一年 🙂
哈哈,我也大三了,是北京化工大学的。
不过我很菜,今天五大赛区也没找到队友,没参加了。
以后就是偶尔水几题混过去算了。唉~~~
我老早就看过你博客了。以前刚开始在POJ上混时,遇到不会的题目,经常搜解答报告就搜到你的了。
Orz.
我也是凑到队友.. 赛区网络赛比完看能不能忽悠点低年级的来拼命一年.. 为了荣誉
我知道的.. 我们还加过QQ不过我一般隐身 -_,-
顺便问一句.. 我这回复你有没有email提示的?
没有诶,你是安装了插件吗?
要是没回复应该是你空间不支持,这个可以问下你的空间商,
反正我的博客安装了回复通知的插件似乎也没用。
插件有用的,没装, 一般空间不会不支持这个…. 我用的host2ez