这一次都主要是贪心练习
练习地址http://acm.hust.edu.cn/vjudge/contest/view.action?cid=26733#overview
Problem APOJ 1328
对于每一个点，可以找到他在x轴上的可行区域，这样的话就变为了对区间的贪心。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<queue>
#include<algorithm>
#include<cmath>
#include<stdlib.h>
using namespace std;
#define MAX(a,b) (a > b ? a : b)
#define MIN(a,b) (a < b ? a : b)
#define MAXN 10000001
#define INF 1000000007
#define mem(a) memset(a,0,sizeof(a))
#define eps 1e-15 struct node{double s,t;}ma[];
double R;
int N; const int island_max=; void get_len(int index,double a,double b)
{
double temp = sqrt(R*R - b*b);
ma[index].s=a-temp;
ma[index].t=a+temp;
} int cmp(node a,node b)
{
if(a.t!=b.t)return (a.t < b.t);
return (b.s > a.s);
} int main()
{
int ca = ;
while(~scanf("%d%lf",&N,&R) && (N || R))
{
int i;
double a,b;
int flag = ;
for(i=;i<N;i++)
{
scanf("%lf %lf",&a,&b);
if(b<=R && !flag)
{
get_len(i,a,b);
}
else flag = ;
}
if(flag){printf("Case %d: -1\n",ca++);continue;}
sort(ma,ma+N,cmp);
double key = ma[].t;
int ans=;
for(i=;i<N;i++)
{
if(ma[i].s-key >eps)
{
key = ma[i].t;
ans ++;
}
}
printf("Case %d: %d\n",ca++,ans);
}
return ;
}
Problem B POJ 2109
可以拿double水过pow（p，1/n）
//Memory Time
//280K 0MS #include<iostream>
#include<math.h>
using namespace std; int main(void)
{
double n,p;
while(cin>>n>>p)
cout<<pow(p,1.0/n)<<endl; //指数的倒数就是开n次方
return ;
}
另外，看大神的二分+大数乘法
http://paste.ubuntu.com/5906043/
然后我也写了一个（在章爷的指导下终于AC了）
#include <stdio.h>
#include <math.h>
#include <string.h>
#define MAX(a,b) (a)>(b)?(a):(b) void strrevv(char s[])
{
int i=,j=strlen(s)-;
while(i<j)
{
int a = s[i];
s[i] = s[j];
s[j] = a;
i++;j--;
}
} char ans[];
char* huge_multiply(char s[],char t[])
{
int a[];
memset(a, , sizeof(a));
memset(ans,,sizeof(ans));
strrevv(s);strrevv(t);
int lens = strlen(s), lent = strlen(t),i,j;
for(i=;i<lens;i++)
{
for(j=;j<lent;j++)
{
a[i+j] += (s[i] - '')*(t[j] - '');
}
}
i=;
while(a[i] == )
i--;
for(j=;a[j] || j<=i;j++)
{
a[j+]+=a[j]/;
a[j] = a[j]%;
}
for(i=;i<j;i++)
{
ans[i]=a[i]+'';
}
strrevv(ans);
strrevv(s);strrevv(t);
return ans;
} char res[]={};
char re[]={};
char* power(char p[],int n)
{
if(n == )return p;
char* pstr;
pstr = power(p,n/);
strcpy(re,pstr);
strcpy(res,pstr);
pstr = huge_multiply(re, res);
strcpy(re,pstr);
if(n%)pstr = huge_multiply(re, p);
strcpy(re, pstr);
return re;
} // int compare_str(char *s, char *t)
{
int lens = strlen(s);
int lent = strlen(t);
if(lens != lent)return lens < lent ? - : ;
while(*s == *t && *s){s++;t++;}
if(!(*s))return ;
return *s < *t ? -: ;
} int b_search(int n, char* p)
{
char str[]={};
char *pstr;
int l = ,r = ;
int lenp = strlen(p);
int ans = ,compare;
while(r - l > )
{
ans = (l+r)/;
sprintf(str,"%d", ans);
int lenstr = strlen(str)-;
if(lenstr*n > lenp){r=ans;continue;}
pstr = power(str, n);
compare = compare_str(pstr, p);
if(compare == )break;
else if(compare < )l = ans;
else r = ans;
// printf("%d %d %d\n",l,r,ans);
}
if(l == r)return ans - ;
return ans;
} int main()
{
int n;
char pstr[]={};
while(~scanf("%d %s", &n, pstr))
{
char *p = pstr;
printf("%d\n", b_search(n, p));
}
return ;
}
Problem CPOJ 2586
由于每个月的亏损或是盈利是固定的，所以我们按贪心的思想，为了让亏损的影响到更多的月份，我们让亏损的尽量放在后面，又由于亏损金额是不会变化的，所以可以分类处理盈利s，亏损d
如果五个月内只有x个月是亏损的 盈利
x = 1 ssssd,ssssd,ss如果是这样的话，只需要d>4s 10s-2d
x = 2 sssdd,sssdd,ss 2*d>3*s 8s-4d
x = 3 ssddd,ssddd,ss 3*d>2*s 6s-6d
x = 4 sdddd,sdddd,sd 4*d>s 3s-9d
x = 5 一定亏损
当然也可以枚举过（一共也就2^12中情况）
#include<stdio.h>
#include<stdlib.h> int main()
{
int s, d, re;
while(scanf("%d%d",&s, &d)==)
{
if(*s-d<)
re=*s-*d;
else if(*s-*d<)
re=*s-*d;
else if(*s-*d<)
re=*s-*d;
else if(s-*d<)
re=*s-*d;
else
re=-;
if(re<)
printf("Deficit\n");
else
printf("%d\n", re);
}
return ;
}
Problem D URAL 1303
感觉自己没有错了，还是WA，不做了
ural 1303 Minimal Coverage(贪心)
Problem E SGU 195
题木意思就是说第i+1个的上司是num[i],而一个人要么给下属发钱，要么从上司拿钱，问这个图里面最多可以拿到多少钱。
由于num[i]是下属是i+1所以可以从后往前扫一遍（也就是从叶子往根找），同时标记一下就可以了
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<queue>
#include<algorithm>
#include<cmath>
#include<stdlib.h>
using namespace std;
#define MAX(a,b) (a > b ? a : b)
#define MIN(a,b) (a < b ? a : b)
#define MAXN 500005
#define INF 1000000007
#define mem(a) memset(a,0,sizeof(a))
#define eps 1e-15 int vis[MAXN], p[MAXN], ans[MAXN];
int N; int main()
{
mem(vis);
scanf("%d",&N);
int i,a;
for(i=;i<=N;i++)
{
scanf("%d",&a);
p[i]=a;
}
int num=;
for(i=N;i>=;i--)
{
if(!vis[i] && !vis[p[i]])
{
vis[p[i]] = vis[i] = ;
ans[num++] = i;
}
}
printf("%d\n",num*);
sort(ans,ans+num);
for(i=;i<num;i++)
{
printf("%d%c", ans[i],i==num-?'\n':' ');
}
return ;
}
Problem F SGU 171
不是很好做，是很不好做。题解见http://www.cnblogs.com/gj-Acit/p/3213370.html