[ACM] 水题tips集合

以后不好意思放报告就在这记一下心得啦

POJ1083

http://wenku.baidu.com/view/98287f0c844769eae009edf9.html 这个说此题是DP, 我琢磨了一下贪心不就行嘛, 再看了下discuss连贪心都不用.. 将路线的线段压扁后, 设最多的地方有n层, 那么最优解显然不会n, 可以推出必然总是存在至少一个点上有m条线段, 因为每一个点上有多少条线段都是常数, 这显然也是不成立的..
STL好好用 =D swap() max_element()

[cpp]#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;
}[/cpp]

POJ1456

又是DP list上的题目想了想用贪心做了.. 算法没啥难度细节挺恶心, 数据结构又用了位, 感觉思维复杂度和struct差不多, 打出来酷一点..
恶心了有两小时.. 大概是有点困了

[cpp]
#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;
}
[/cpp]

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.. 太囧了阿..

[cpp]
#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;
}
[/cpp]

POJ 1953

就是Fibonacci数列, 推了一下发现a[i] = sum(a[k])+1, k=1..i-2
[cpp]#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;
}
[/cpp]

Asher.GG

git gut together

[ACM] 水题tips集合

POJ1083

POJ1456

POJ 1730

132 thoughts on “[ACM] 水题tips集合”

Leave a Reply Cancel reply