以后不好意思放报告就在这记一下心得啦
POJ1083
http://wenku.baidu.com/view/98287f0c844769eae009edf9.html 这个说此题是DP, 我琢磨了一下贪心不就行嘛, 再看了下discuss连贪心都不用.. 将路线的线段压扁后, 设最多的地方有n层, 那么最优解显然不会n, 可以推出必然总是存在至少一个点上有m条线段, 因为每一个点上有多少条线段都是常数, 这显然也是不成立的..
STL好好用 =D swap() max_element()
1 | #include <stdio.h> |
2 | #include <algorithm> |
3 | #include <string.h> |
4 |
5 | using namespace std; |
6 |
7 | int main() { |
8 | int T,N; |
9 | scanf("%d",&T); |
10 | while(T--) { |
11 | scanf("%d",&N); |
12 |
13 | int s,t,press[200]; |
14 | memset(press,0x00,sizeof(press)); |
15 |
16 | for(int i=0;i<N;i++) { |
17 | scanf("%d%d",&s,&t); |
18 | if(s>t) |
19 | swap(s,t); |
20 | for(int k=(s-1)>>1;k<=(t-1)>>1;k++) |
21 | press[k]++; |
22 | } |
23 |
24 | printf("%d\n",*max_element(press,press+200)*10); |
25 | } |
26 |
27 | return 0; |
28 | } |
POJ1456
又是DP list上的题目想了想用贪心做了.. 算法没啥难度细节挺恶心, 数据结构又用了位, 感觉思维复杂度和struct差不多, 打出来酷一点..
恶心了有两小时.. 大概是有点困了
1 | #include <stdio.h> |
2 | #include <stdlib.h> |
3 |
4 | int __comp1(const void *a,const void *b) { |
5 | return (*(int *)a&((1<<14)-1)) - (*(int *)b&((1<<14)-1)); |
6 | } |
7 |
8 | int __comp2(const void *a,const void *b) { |
9 | return (*(int *)a>>14) - (*(int *)b>>14); |
10 | } |
11 |
12 | int seqMax(int a[],int from,int to) { |
13 | int p=from; |
14 | for(int i=from+1;i<=to;i++) { |
15 | if((a[p]>>14)<(a[i]>>14)) |
16 | p=i; |
17 | } |
18 | int r=(a[p]>>14); |
19 | a[p]=a[to]; |
20 | return r; |
21 | } |
22 |
23 | int main() { |
24 | int a[10001],n; |
25 | while(1) { |
26 | if(scanf("%d",&n)==EOF) |
27 | break; |
28 | for(int i=0;i<n;i++) { |
29 | scanf("%d",a+i); |
30 | a[i]<<=14; |
31 | int temp; |
32 | scanf("%d",&temp); |
33 | a[i]+=temp; |
34 | } |
35 |
36 | qsort(a,n,sizeof(int),__comp1); |
37 |
38 | int edge=-1; |
39 | int head=n-1; |
40 | int result=0; |
41 | for(int i=n-1;i>=0 && head >=0;) { |
42 | for(;head>0;head--) |
43 | if((a[head-1]&((1<<14)-1))!=edge) |
44 | break; |
45 | int days=(a[head]&((1<<14)-1))-(head==0?0:(a[head-1]&((1<<14)-1))); |
46 | //qsort(a+head,i-head+1,sizeof(int),__comp2); too much time cost, according to the test data |
47 | int cut=(i-head+1)<days?(i-head+1):days; |
48 | for(int j=0;j<cut;j++) |
49 | result+=seqMax(a,head,i--); |
50 | head--; |
51 | } |
52 |
53 | printf("%d\n",result); |
54 |
55 | } |
56 | return 0; |
57 | } |
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.. 太囧了阿..
1 | #include <stdio.h> |
2 | #include <math.h> |
3 |
4 | int main() { |
5 | while(1) { |
6 | long long n; |
7 | scanf("%lld",&n); |
8 | if(!n) |
9 | break; |
10 | int max=1; |
11 | for(int i=31;i>=2;i--) { |
12 | if(n<0 && !(i%2)) |
13 | continue; |
14 | long long __n=(long long)fabs((double)n); |
15 | double m=pow((double)__n,(double)1/i); |
16 | if(m-(int)m<1E-12||(int)m+1-m<1E-12) { |
17 | max=i>max?i:max; |
18 | break; |
19 | } |
20 | } |
21 | printf("%d\n",max); |
22 | } |
23 | return 0; |
24 | } |
POJ 1953
就是Fibonacci数列, 推了一下发现a[i] = sum(a[k])+1, k=1..i-2
1 | #include <stdio.h> |
2 |
3 | int main() { |
4 | int dp[46][2]; |
5 | dp[0][0]=1; |
6 | dp[0][1]=0; |
7 | for(int i=1;i<=45;i++) { |
8 | dp[i][0]=dp[i-1][0]+dp[i-1][1]; |
9 | dp[i][1]=dp[i-1][0]; |
10 | } |
11 |
12 | int N; |
13 | scanf("%d",&N); |
14 | for(int i=1;i<=N;i++) { |
15 | int a; |
16 | scanf("%d",&a); |
17 | printf("Scenario #%d:\n%d\n\n",i,dp[a+1][0]); |
18 | } |
19 |
20 | return 0; |
21 | } |
来支持下神牛。Orz.你是在哪读书？
= = 不敢当, 赶紧拜回去.. Orz
扬州有个大学叫扬州大学.. 我就在那里, 神奇吧…
大三了, 没时间了, 拼一年
哈哈，我也大三了，是北京化工大学的。
不过我很菜，今天五大赛区也没找到队友，没参加了。
以后就是偶尔水几题混过去算了。唉~~~
我老早就看过你博客了。以前刚开始在POJ上混时，遇到不会的题目，经常搜解答报告就搜到你的了。
Orz.
我也是凑到队友.. 赛区网络赛比完看能不能忽悠点低年级的来拼命一年.. 为了荣誉
我知道的.. 我们还加过QQ不过我一般隐身 -_,-
顺便问一句.. 我这回复你有没有email提示的?
没有诶，你是安装了插件吗？
要是没回复应该是你空间不支持，这个可以问下你的空间商，
反正我的博客安装了回复通知的插件似乎也没用。
插件有用的,没装, 一般空间不会不支持这个…. 我用的host2ez