Contest 7.21（贪心专练）

这一次都主要是贪心练习

练习地址http://acm.hust.edu.cn/vjudge/contest/view.action?cid=26733#overview

对于每一个点，可以找到他在x轴上的可行区域，这样的话就变为了对区间的贪心。

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<map>
 5 #include<vector>
 6 #include<set>
 7 #include<stack>
 8 #include<queue>
 9 #include<algorithm>
10 #include<cmath>
11 #include<stdlib.h>
12 using namespace std;
13 #define MAX(a,b) (a > b ? a : b)
14 #define MIN(a,b) (a < b ? a : b)
15 #define MAXN  10000001
16 #define INF 1000000007
17 #define mem(a) memset(a,0,sizeof(a))
18 #define eps 1e-15
19 
20 struct node{double s,t;}ma[1001];
21 double R;
22 int N;
23 
24 
25 const int island_max=1000;
26 
27 
28 void get_len(int index,double a,double b)
29 {
30     double temp = sqrt(R*R - b*b);
31     ma[index].s=a-temp;
32     ma[index].t=a+temp;
33 }
34 
35 int cmp(node a,node b)
36 {
37     if(a.t!=b.t)return (a.t < b.t);
38     return (b.s > a.s);
39 }
40 
41 int main()
42 {
43     int ca = 1;
44     while(~scanf("%d%lf",&N,&R) && (N || R))
45     {
46         int i;
47         double a,b;
48         int flag = 0;
49         for(i=0;i<N;i++)
50         {
51             scanf("%lf %lf",&a,&b);
52             if(b<=R && !flag)
53             {
54                 get_len(i,a,b);
55             }
56             else flag = 1;
57         }
58         if(flag){printf("Case %d: -1
",ca++);continue;}
59         sort(ma,ma+N,cmp);
60         double key = ma[0].t;
61         int ans=1;
62         for(i=1;i<N;i++)
63         {
64             if(ma[i].s-key >eps)
65             {
66                 key = ma[i].t;
67                 ans ++;
68             }
69         }
70          printf("Case %d: %d
",ca++,ans);
71     }
72     return 0;
73 }

View Code

Problem B POJ 2109

可以拿double水过pow（p，1/n）

 1 //Memory Time 
 2 //280K    0MS 
 3 
 4 #include<iostream>
 5 #include<math.h>
 6 using namespace std;
 7 
 8 
 9 int main(void)
10 {
11     double n,p;
12     while(cin>>n>>p)
13         cout<<pow(p,1.0/n)<<endl;  //指数的倒数就是开n次方
14     return 0;
15 }

View Code

另外，看大神的二分+大数乘法

http://paste.ubuntu.com/5906043/

然后我也写了一个（在章爷的指导下终于AC了）

  1 #include <stdio.h>
  2 #include <math.h>
  3 #include <string.h>
  4 #define MAX(a,b) (a)>(b)?(a):(b)
  5 
  6 
  7 void strrevv(char s[])
  8 {
  9     int i=0,j=strlen(s)-1;
 10     while(i<j)
 11     {
 12         int a = s[i];
 13         s[i] = s[j];
 14         s[j] = a;
 15         i++;j--;
 16     }
 17 }
 18 
 19 char ans[205];
 20 char* huge_multiply(char s[],char t[])
 21 {
 22     int a[205];
 23     memset(a, 0, sizeof(a));
 24     memset(ans,0,sizeof(ans));
 25     strrevv(s);strrevv(t);
 26     int lens = strlen(s), lent = strlen(t),i,j;
 27     for(i=0;i<lens;i++)
 28     {
 29         for(j=0;j<lent;j++)
 30         {
 31             a[i+j] += (s[i] - '0')*(t[j] - '0');
 32         }
 33     }
 34     i=200;
 35     while(a[i] == 0)
 36         i--;
 37     for(j=0;a[j] || j<=i;j++)
 38     {
 39         a[j+1]+=a[j]/10;
 40         a[j] = a[j]%10;
 41     }
 42     for(i=0;i<j;i++)
 43     {
 44         ans[i]=a[i]+'0';
 45     }
 46     strrevv(ans);
 47     strrevv(s);strrevv(t);
 48     return ans;
 49 }
 50 
 51 char res[205]={0};
 52 char re[205]={0};
 53 char* power(char p[],int n)
 54 {
 55     if(n == 1)return p;
 56     char* pstr;
 57     pstr = power(p,n/2);
 58     strcpy(re,pstr);
 59     strcpy(res,pstr);
 60     pstr = huge_multiply(re, res);
 61     strcpy(re,pstr);
 62     if(n%2)pstr = huge_multiply(re, p);
 63     strcpy(re, pstr);
 64     return re;
 65 }
 66 
 67 //30517578125000
 68 
 69 
 70 
 71 int compare_str(char *s, char *t)
 72 {
 73     int lens = strlen(s);
 74     int lent = strlen(t);
 75     if(lens != lent)return lens < lent ? -1 : 1;
 76     while(*s == *t && *s){s++;t++;}
 77     if(!(*s))return 0;
 78     return *s < *t ? -1: 1;
 79 }
 80 
 81 int b_search(int n, char* p)
 82 {
 83     char str[12]={0};
 84     char *pstr;
 85     int l = 0,r = 1000000002;
 86     int lenp = strlen(p);
 87     int ans = 1,compare;
 88     while(r - l > 1)
 89     {
 90         ans = (l+r)/2;
 91         sprintf(str,"%d", ans);
 92         int lenstr = strlen(str)-1;
 93         if(lenstr*n > lenp){r=ans;continue;}
 94         pstr = power(str, n);
 95         compare = compare_str(pstr, p);
 96         if(compare == 0)break;
 97         else if(compare < 0)l = ans;
 98         else r = ans;
 99    //     printf("%d %d %d
",l,r,ans);
100     }
101     if(l == r)return ans - 1;
102     return ans;
103 }
104 
105 
106 int main()
107 {
108     int n;
109     char pstr[110]={0};
110     while(~scanf("%d %s", &n, pstr))
111     {
112         char *p = pstr;
113         printf("%d
", b_search(n, p));
114     }
115     return 0;
116 }

View Code

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中情况）

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 int main()
 5 {
 6       int s, d, re;
 7       while(scanf("%d%d",&s, &d)==2)
 8       {
 9           if(4*s-d<0)
10               re=10*s-2*d;
11           else if(3*s-2*d<0)
12               re=8*s-4*d;
13           else if(2*s-3*d<0)
14               re=6*s-6*d;
15           else if(s-4*d<0)
16               re=3*s-9*d;
17           else 
18               re=-1;
19           if(re<0)
20               printf("Deficit
");
21           else
22               printf("%d
", re);
23       }
24       return 0;
25 }

View Code

Problem D URAL 1303

感觉自己没有错了，还是WA，不做了

ural 1303 Minimal Coverage(贪心)

Problem E SGU 195

题木意思就是说第i+1个的上司是num[i],而一个人要么给下属发钱，要么从上司拿钱，问这个图里面最多可以拿到多少钱。

由于num[i]是下属是i+1所以可以从后往前扫一遍（也就是从叶子往根找），同时标记一下就可以了

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<map>
 5 #include<vector>
 6 #include<set>
 7 #include<stack>
 8 #include<queue>
 9 #include<algorithm>
10 #include<cmath>
11 #include<stdlib.h>
12 using namespace std;
13 #define MAX(a,b) (a > b ? a : b)
14 #define MIN(a,b) (a < b ? a : b)
15 #define MAXN   500005
16 #define INF 1000000007
17 #define mem(a) memset(a,0,sizeof(a))
18 #define eps 1e-15
19 
20 int vis[MAXN], p[MAXN], ans[MAXN];
21 int N;
22 
23 
24 int main()
25 {
26     mem(vis);
27     scanf("%d",&N);
28     int i,a;
29     for(i=2;i<=N;i++)
30     {
31         scanf("%d",&a);
32         p[i]=a;
33     }
34     int num=0;
35     for(i=N;i>=2;i--)
36     {
37         if(!vis[i] && !vis[p[i]])
38         {
39             vis[p[i]] = vis[i] = 1;
40             ans[num++] = i;
41         }
42     }
43     printf("%d
",num*1000);
44     sort(ans,ans+num);
45     for(i=0;i<num;i++)
46     {
47         printf("%d%c", ans[i],i==num-1?'
':' ');
48     }
49     return 0;
50 }

View Code

Problem F SGU 171

不是很好做，是很不好做。题解见http://www.cnblogs.com/gj-Acit/p/3213370.html