C++博客-wyh123

poj 1042（DP）

wyh — Wed, 10 Aug 2011 13:16:00 GMT

题目大意：john现有h个小时的空闲时间，他打算去钓鱼。john钓鱼的地方共有n个湖，所有的湖沿着一条单向路顺序排列（john每在一个湖钓完鱼后，他只能走到下一个湖继续钓），john必须从1号湖开始钓起，但是他可以在任何一个湖结束他此次钓鱼的行程。输入给出john在每个湖中每5分钟钓的鱼数（此题中以5分钟作为单位时间），随时间的增长而线性递减。而每个湖中头5分钟可以钓到的鱼数以及每个湖中相邻5分钟钓鱼数的减少量，John从任意一个湖走到它下一个湖的时间。

解题思路：1）设fish[i][j]表示到了第i个池塘用了j*5分钟所钓到的雨的数目
2）转移：fish[i][j]=Max{fish[i-1][j-k-t[i]],fish[i][j]+sum}
sum是呆着这个池塘经过k*5分钟所钓到的鱼的数目~sum=f[i]*(k+1)-(k+1)*k/2*d[i]

代码：

1#include <iostream>
2#include <cstdio>
3#include <cstring>
4#include <cstring>
5#include <cmath>
6#include <algorithm>
7
8using namespace std;
9
10int f[30],d[30],t[30],path[30];
11int fish[30][400];
12int n,h,maxx,k;
13
14void init()
15{
16    memset(path, 0, sizeof(path));
17    memset(fish,-1,sizeof(fish));
18}
19
20void find_Path(int i, int time)
21{
22    if(i==0) return;
23    int summ=0;
24    for(int k=0; k<=12*h; ++k)
25    {
26        if(fish[i-1][time-k-t[i-1]]+summ==fish[i][time])
27        {
28            path[i]=k*5;
29            return find_Path(i-1,time-k-t[i-1]);
30        }
31        if (f[i]-k*d[i]>0)
32            summ=f[i]*(k+1)-(k+1)*k/2*d[i];
33    }
34}
35
36void get_DP()
37{
38    fish[0][0]=0;
39    for(int i=0; i<=n-1; ++i)
40        for(int j=0; j<=12*h; ++j)
41        {
42            int summ=0;
43            for(int k=0; k<=12*h && fish[i][j]!=-1; ++k)
44            {
45                if(j+k+t[i]<=12*h)
46                    fish[i+1][j+k+t[i]]=max(fish[i+1][j+k+t[i]],fish[i][j]+summ);
47                else
48                    break;
49                if (f[i+1]-k*d[i+1]>0)
50                   summ=f[i+1]*(k+1)-(k+1)*k/2*d[i+1];
51            }
52        }
53        maxx=0;
54        k=1;
55        for(int i = 1; i <= n; ++i)
56            if(maxx<fish[i][12*h])
57            {
58                maxx=fish[i][12*h];
59                k=i;
60            }
61}
62
63int main()
64{
65    while (~scanf("%d",&n))
66    {
67        if (n==0) break;
68        scanf("%d",&h);
69        for (int i=1; i<=n; i++) scanf("%d",&f[i]);
70        for (int i=1; i<=n; i++) scanf("%d",&d[i]);
71        for (int i=1; i<=n-1; i++) scanf("%d",&t[i]);
72        init();
73        get_DP();
74        find_Path(k, 12*h);
75        for(int i = 1; i <= n-1; ++i)
76            printf("%d, ",path[i]);
77        printf("%d\n",path[n]);
78        printf("Number of fish expected: %d\n", fish[k][12*h]);
79        printf("\n");
80    }
81    return 0;
82}
83

wyh 2011-08-10 21:16 发表评论

poj 1036（DP）

wyh — Tue, 09 Aug 2011 12:40:00 GMT

题目大意：宾馆有个伸缩门，其开放状态用[0,k]之间某个数来表示，每秒钟它至多可以伸长或减少1个单位。现在有n个强盗，他们会在ti的时间到达宾馆，如果此时门的开放度和他的身材si恰好相同，他就会进来，并得到pi的加分。一开始门是关闭的(开放度为0)，请你求出时刻t的最大加分。

解题思路：1）这道题的状态很容易就可以找出来：dp[i][j]表示在第i秒钟门的宽度为j所取得的最大加分。
2）那么转移就是：dp[i][j]=Max{dp[i-1][j+1],dp[i-1][j-1],dp[i][j]}+dp[i][j]~前一个时刻可以由三个状态转变而来，直接求最大值就可以了
3) 这道题的空间限制是10000K~，完整的数组开不了，只能开滚动数组~（WA了之后才发现的）

~~本以为改为滚动数组后就过了~~，没想到果断T了~~，没办法，又加了张hash记录强盗在什么时刻到达宾馆来稍微稍微降低复杂度。

代码：

1#include <iostream>
2#include <cstdio>
3#include <cstring>
4#include <string>
5#include <cmath>
6#include <algorithm>
7
8using namespace std;
9
10struct Person
11{
12    int t,s,p;
13}num[110];
14int dp[3][110];
15int hash[30100];
16int n,t,k,summ;
17
18
19void init()
20{
21    memset(dp,0,sizeof(dp));
22    memset(hash,0,sizeof(hash));
23}
24
25void get_DP()
26{
27    for (int i=0; i<=t; i++)
28    {
29        for (int j=0; j<=k && j<=i; j++)
30        {
31            summ=0;
32            if (hash[i]!=0)
33            {
34                for (int l=0; l<n; l++)
35                    if (i==num[l].t && j==num[l].s) summ+=num[l].p;
36            }
37            if (j==k) dp[i%3][j]=max(dp[(i+2)%3][j-1],dp[(i+2)%3][j]);
38            else if (j==0) dp[i%3][j]=max(dp[(i+2)%3][j+1],dp[(i+2)%3][j]);
39            else dp[i%3][j]=max(max(dp[(i+2)%3][j-1],dp[(i+2)%3][j]),dp[(i+2)%3][j+1]);
40            dp[i%3][j]+=summ;
41        }
42    }
43}
44
45int cmp(const Person &a,const Person &b)
46{
47    if (a.t==b.t) return a.s<b.s; else return a.t<b.t;
48}
49
50int main()
51{
52    scanf("%d%d%d",&n,&k,&t);
53
54    for (int i=0; i<n; i++)
55        scanf("%d",&(num[i].t));
56    for (int i=0; i<n; i++)
57        scanf("%d",&(num[i].p));
58    for (int i=0; i<n; i++)
59        scanf("%d",&(num[i].s));
60    sort(num,num+n,cmp);
61    init();
62    for (int i=0; i<n; i++)
63        hash[num[i].t]=1;
64    get_DP();
65    int maxx=-1;
66    for (int i=0; i<=k; i++)
67        if (maxx<dp[t%3][i])  maxx=dp[t%3][i];
68    printf("%d",maxx);
69    return 0;
70}
71

wyh 2011-08-09 20:40 发表评论

poj 1029（模拟）

wyh — Tue, 09 Aug 2011 09:08:00 GMT

题目大意：给出n个硬币（真币和假币质量不同），和k次比较。每次比较去p个硬币置于天平左盘，p个至于右盘，先给出每次比较的硬币编号和比较结果，要求找出假币的编号。找不到就输出“0”

解题思路：根据题意可以知道一下几点：
              1）每次出现"="，一定是真币
              2）真币一定不会出现在不等式中
              3）如果假币唯一则一定出现在每一次不等式中。
              4）因为不知道假币是比真币重还是轻，但是不管是轻还是重，它都只会出现在不等式小的一边（或者大的一边）

               基于上面几点：我们可以将=号左右出现的真币先排除，然后统一大于小于号，统计硬币在重的一方，轻的一方出现的次数。
               如果存在且仅存在一个硬币在不等号一个方向出现的次数等于不等式出现的次数，那个硬币就一定是假币。

               *_*。。。。。。在写这道程序之前写了一道多达150行的按操作模拟的程序，虽然A了，但是看起来好恶心！！

代码：

1#include <iostream>
2#include <string>
3#include <cmath>
4#include <cstring>
5#include <algorithm>
6
7using namespace std;
8
9const int MAX=1001;
10
11int n,k,p,total=0;
12char temp;
13int a[MAX]={0};
14int r[MAX]={0};
15int times[MAX]={0};
16
17int main()
18{
19    cin >> n >> k;
20    while (k--)
21    {
22        cin >> p;
23        for (int i=0; i<2*p; i++)
24        {
25            cin >> a[i];
26        }
27        cin >> temp;
28        if (temp=='=')
29        {
30            for (int i=0; i<2*p; i++)
31            {
32                r[a[i]]=1;
33            }
34        }
35        if (temp=='<')
36        {
37            total++;
38            for (int i=0; i<p; i++)
39            {
40                times[a[i]]--;
41            }
42            for (int i = p; i<2*p; i++)
43            {
44                times[a[i]]++;
45            }
46        }
47        if (temp=='>')
48        {
49            total++;
50            for (int i=0; i<p; i++)
51            {
52                times[a[i]]++;
53            }
54            for (int i=p; i<2*p; i++)
55            {
56                times[a[i]]--;
57            }
58        }
59    }
60    int cnt=0,s=0;
61    for (int i= 1; i<=n; i++)
62    {
63        if (r[i]!=1)
64            if (times[i]==total || times[i]==-total)
65            {
66                cnt++;
67                s=i;
68            }
69    }
70    if (cnt==1) cout << s << endl;
71    else  cout << 0 << endl;
72    return 0;
73}
74

wyh 2011-08-09 17:08 发表评论

poj 1015（DP）

wyh — Tue, 09 Aug 2011 06:47:00 GMT

摘要: 题目大意：在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选n 个人作为陪审团的候选人，然后再从这n 个人中选m 人组成陪审团。选m 人的办法是：控方和辩方会根据对候选人的喜欢程度，给所有候选人打分，分值从0 到20。为了公平起见，法官选出陪审团的原则是：选出的m 个人，必须满足辩方总分和控方总分的差的绝对值最小。如果有多种选择方案的辩方总分... 阅读全文

wyh 2011-08-09 14:47 发表评论

poj 1971（数学题）

wyh — Mon, 08 Aug 2011 16:05:00 GMT

题目大意：给出n个点，求出这n个点能够组成平行四边形的个数。

解题思路：1）平行四边形的对角线的中点一定相交。<=> 如果有两条不同线段的中点相交，就是一个平行四边形
2）利用点坐标求出中点的集合，离散化后求出同个中点的出现的个数k。
3）对于每一个k ，利用组合公式C(k,2)的答案就是平行四边行的个数

代码：

1#include <iostream>
2#include <cstdio>
3#include <cmath>
4#include <cstring>
5#include <string>
6#include <algorithm>
7
8using namespace std;
9
10struct Node
11{
12   int x,y;
13}node[1010],mid[1001000];
14int T,n,summ,num;
15
16int cmp(const Node &a,const Node &b)
17{
18    if (a.x==b.x) return a.y<b.y; else return a.x<b.x;
19}
20
21int count(int k)
22{
23    if (k==1) return 0;
24    else
25    {
26        return k*(k-1)/2;
27    }
28}
29
30int main()
31{
32    cin >> T;
33    while (T--)
34    {
35        summ=0;
36        scanf("%d",&n);
37        for (int i=1; i<=n; i++)
38          {
39              scanf("%d%d",&(node[i].x),&(node[i].y));
40          }
41        num=-1;
42        for (int i=1; i<=n; i++)
43        {
44            for (int j=i+1; j<=n; j++)
45              {
46                  num++;
47                  mid[num].x=node[i].x+node[j].x;
48                  mid[num].y=node[i].y+node[j].y;
49              }
50        }
51        sort(mid,mid+num+1,cmp);
52        Node temp;
53        int k;
54        k=1;
55        for (int i=0; i<=num; i++)
56        {
57            if (mid[i].x==mid[i+1].x && mid[i].y==mid[i+1].y) k++;
58                else
59                {
60                    summ+=count(k);
61                    k=1;
62                }
63        }
64        cout << summ << endl;
65
66    }
67    return 0;
68}
69

wyh 2011-08-09 00:05 发表评论

HDOJ 3823(素数)

wyh — Sun, 07 Aug 2011 01:39:00 GMT

题目大意：给出两个数，a,b（均小于等于150），让他们加上一个数使得他们得到的数是素数，并且两个素数相邻，如果存在这样的数，则输出，否则，输出-1

解题思路：1）a,b均小于或等于150，那么加上后素数的差值绝对小于150
              2）存在相邻素数小于150的素数范围感觉应该不大...暴力筛一下，看到哪里的间隔会大于150；
              3）开一个数组，dis[i][j]，表示两个差距为i的两个相邻素数中，较小的那个素数是dis[i]中第j小的
              4）接下来就是枚举了，先算差值m，然后套到dis[m]中求不比给定的数a,b小的最小素数，有就输出，没有就输出-1

         第一次用vector ~~~

代码：

1#include <iostream>
2#include <cstdlib>
3#include <vector>
4#include <algorithm>
5#include <cstdio>
6#include <cstring>
7#include <cmath>
8
9using namespace std;
10
11bool pri[20000000];
12int pr[1500000];
13int summ,T,a,b,m,maxx;
14bool f;
15vector<int> dis[150];
16
17void prime()
18{
19    memset(pri,0,sizeof(pri));
20    for(int i=2;i<20000000;i++)
21    {
22        if(pri[i]==true) continue;
23        for(int j=i+i;j<20000000;j+=i)
24        {
25            pri[j] = true;
26        }
27    }
28    summ=0;
29    for(int i=2;i<20000000;i++)
30    {
31        if(pri[i]) continue;
32        pr[summ] = i;
33        summ++;
34    }
35}
36
37int main()
38{
39
40    prime();
41    for(int i=0;i<summ-1;i++)
42    {
43        if(pr[i+1]-pr[i]>149) continue;
44        dis[pr[i+1]-pr[i]].push_back(pr[i]);
45    }
46    cin >> T;
47    for(int i=1;i<=T;i++)
48    {
49        cin >> a >> b;
50        m=abs(a-b);
51        if (a>b) maxx=b;
52          else maxx=a;
53        f=true;
54        cout << "Case " << i << ": ";
55        for(int j=0;j<dis[m].size();j++)
56        {
57            if(dis[m][j]<maxx) continue;
58            cout << dis[m][j]-maxx<< endl;
59            f=false;
60            break;
61        }
62        if(f==true) cout << "-1" << endl;
63    }
64}
65

wyh 2011-08-07 09:39 发表评论

HDOJ 3826(素数)

wyh — Sat, 06 Aug 2011 16:04:00 GMT

题目大意：给出一个数，判断其是否有含有平方因子

解题思路：1）10^18这是一个很大的数据，暴力是绝对不可行的。
              2）如果其含有平方因子，则有n=a^2*b，这里的n<=10^18，所以a,b中必定有一个是小于10^6~。
              3）筛10^6以内的素数，然后用n去除以这些质数的平方，如果能除，返回NO，否则，则看是否能够除以这个素数。
              4）10^6以内的素数除光了，如果是1返回YES
              5）剩下的也就只有三种可能，素数，素数的平方和，或者两个素数的积。
                     （证明：首先，剩下的肯定是比10^6大的素数，这个是毫无疑问的，而且这些素数因子的个数不可能超过3个，所以只有以上三种情况）
              6）是两个素数的积返回NO，其他的YES

代码：

1#include <cstdio>
2#include <cstdlib>
3#include <cmath>
4#include <iostream>
5#include <algorithm>
6
7using namespace std;
8
9int prime[80000];
10bool p[1000002];
11
12void PRIME(int M)
13{
14    int i,i2,k;
15    for(i=0;i<=M;i+=2){ p[i]=0; }
16    for(i=1;i<=M;i+=2){ p[i]=1; }
17    p[2]=1;
18    p[1]=0;
19    for(i=3;i<=1000;i+=2)
20    {
21        if(p[i]==1)
22          {
23              i2=i+i;
24              k=i*i;
25              while(k<=M)
26              {
27                  p[k]=0;
28                  k+=i2;
29              }
30           }
31     }
32     prime[1]=2;
33     k=1;
34     for(i=3;i<=M;i+=2)
35        if(p[i])   prime[++k]=i;
36     prime[0]=k;
37     return ;
38}
39
40
41int Int(long long n)
42{
43    int i,s,k;
44    long long d,e;
45    k=0;
46    for(i=1;i<=prime[0];i++)
47    {
48       s=0;
49       while(n%prime[i]==0)
50         {
51             s++;
52             n/=prime[i];
53         }
54
55       if(s>1) return -1;
56       if(n==1) return 1;
57       if(n/prime[i]<prime[i]) return 1;
58     }
59     d=(long long)sqrt((double)n);
60     d--;
61     while(1)
62     {
63         e=d*d;
64         if(e==n)return -1;
65         if(e>n)break;
66         d++;
67     }
68    return 1;
69 }
70
71int main()
72 {
73   int T,i,k;
74   long long N,d;
75   PRIME(1000000);
76   scanf("%d",&T);
77   for(i=1;i<=T;i++)
78    {
79      scanf("%I64d",&N);
80      k=Int(N);
81      if(k==1) printf("Case %d: Yes\n",i);
82      else  printf("Case %d: No\n",i);
83     }
84    return 0;
85}
86
87

wyh 2011-08-07 00:04 发表评论

poj 1150（求末尾非0数字）

wyh — Sat, 06 Aug 2011 02:34:00 GMT

题目大意：给出n,m，求P(n,m)最后一位末尾非0数字

解题思路：已知P(n,m)=n!/(n-m)! 由于n,m<=200000000

这里利用到数论中求n！最尾非零数的非零数字的方法（下列数字2，5，1，3，7，9均表示数的个位）：

1)因为2，5组成10，故可以删去能配对的2,5，记录下剩余2的个数；（2显然多于5）

2)每一个数，在mod2,5之后只有1,3,7,9四种结果，1可以忽略不计，故我们只需要统计3,7,9的个数

统计方法如下：f(n,x)和g(n,x)中的n代表n!中的n，x取3，7，9中的一个

有：f(n,x)=f(n/2,x)+g(n,x)

g(n,x)=n/10+g(n/5,x)+k

if (n>=x) k=1; else k=0;

这里面是将阶层中的项分为奇数项和偶数项，其中先对奇数项求3,7或9的个数。这里面，很容易知道，每10个数里面一定有一个以3,7或者9结尾的数，而且当n>=3，7或9时，必存在一个3,7,9（当n=16时，前10个数有一个以3结尾，而13也是以上结尾，所以此处有两个3，不是n/10）；另外由于要约去成对的2和5那么无可避免的会出现其他的数字（2,3,7,9,1,其中2另外考虑），所以此处要加上g(n/5,x)。对于偶数项，不难发现当偶数项除以2（这里的2由于有另外统计，所以除后对结果没有影响）后就变成了n！的前一半（如10！有1，2，3，4，5，6，7，8，9，10，偶数项除以而后可以转化为1,2,3,4,5。）。

3)最后，找规律，如出现几个2的乘积末尾是多少~~

代码：

1#include <cstdio>
2#include <string>
3#include <iostream>
4using namespace std;
5
6int n,m,a,b,c,temp,temp1,d;
7int p(int n,int x)
8{
9    if(n<x) return 0;
10    return n/x+p(n/x);
11}
12int g(int n,int x)
13{  if (n<1) return 0;
14   else
15     if (n%10>=x) return n/10+1+g(n/5,x);
16     return n/10+g(n/5,x);
17}
18int f(int n,int x)
19{  if (n<1) return 0;
20   else return f(n/2,x)+g(n,x);
21}
22void working()
23{ int k;
24  a=f(n,3)-f(n-m,3);
25  b=f(n,7)-f(n-m,7);
26  c=f(n,9)-f(n-m,9);
27  temp=p(n,5)-p(n-m,5);
28  temp1=p(n,2)-p(n-m,2);
29  d=temp1-temp;
30  if (a%4==0) a=1; else
31  if (a%4==1) a=3; else
32  if (a%4==2) a=9; else
33  if (a%4==3) a=7;
34
35  if (b%4==0) b=1; else
36  if (b%4==1) b=7; else
37  if (b%4==2) b=9; else
38  if (b%4==3) b=3;
39
40  if (c%4==0) c=1; else
41  if (c%4==1) c=9; else
42  if (c%4==2) c=1; else
43  if (c%4==3) c=9;
44
45  if (d%4==0) d=6; else
46  if (d%4==1) d=2; else
47  if (d%4==2) d=4; else
48  if (d%4==3) d=8;
49
50  printf("%d\n",a*b*c*d%10);
51
52}
53int main()
54{  while (scanf("%d%d",&n,&m)!=EOF)
55   { working();
56   }
57
58}
59

wyh 2011-08-06 10:34 发表评论

HDOJ 1286（欧拉函数）

wyh — Sat, 06 Aug 2011 02:30:00 GMT

题目大意：

新年快到了，“猪头帮协会”准备搞一个聚会，已经知道现有会员N人，把会员从1到N编号，其中会长的号码是N号，凡是和会长是老朋友的，那么该会员的号码肯定和N有大于1的公约数，否则都是新朋友，现在会长想知道究竟有几个新朋友？请你编程序帮会长计算出来。

解题思路：这是一道裸的欧拉函数题目
对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等。

Euler函数

       欧拉函数通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1      （唯一和1互质的数就是1本身）。


代码：

1#include <iostream>
2#include <cstdio>
3#include <cmath>
4#include <cstring>
5
6using namespace std;
7
8int n,T;
9
10int euler(int x)
11{  int i,res=x;
12   for (i=2; i<(int)sqrt(x*1)+1; i++)
13     {  if (x % i ==0)
14           {
15               res=res/i*(i-1);
16               while (x % i==0) x=x/i;
17           }
18     }
19    if (x>1) res=res/x*(x-1);
20    return res;
21
22}
23
24int main()
25{   cin >> T;
26    while (T--)
27    {  cin >> n;
28       cout << euler(n)<< endl;
29
30    }
31    return 0;
32}
33

wyh 2011-08-06 10:30 发表评论

HDOJ 1163（树根）

wyh — Thu, 04 Aug 2011 16:01:00 GMT

题目大意：给你一个n，输出n^n 的数根。
              树根的定义是求一个数各个位数的和，如果和是多位数，就继续求和，直到和为一位数。

解题思路：1）树根要怎么求，每个人都知道，或是递归或是两个while，怎么写都行
              2）这道题的重点在于n^n的计算。
                   假设一个数：b*10+c;
                   则这个数的树根是: b+c
                   那么：这个数的平方的树根勒，不妨算一下：root((b*10+c)^2)=root(100*b*b+10*2*b*c+c*c)=b^2+2b*c+c^2
                     （是不是很眼熟）       ~~~                没错，root()=(b+c)^2
                   .....
                   .....
                   推一下，n^n就知道该怎么算啦~~~

代码：

1#include <iostream>
2#include <cstdio>
3#include <cstring>
4#include <cmath>
5#include <algorithm>
6
7using namespace std;
8
9int n,ro,i,ans,summ;
10
11int root(int a)
12{
13    summ=0;
14    while(a>0)
15    {
16        summ+=(a%10);
17        a/=10;
18    }
19    if(summ/10!=0)
20    {
21        return root(summ);
22    }
23    else
24    return summ;
25}
26
27int main()
28{
29
30    while(~scanf("%d",&n))
31    {
32        if(n==0) break;
33        ro=root(n);
34        ans=1;
35        for(i=0;i<n;i++)
36        {
37            ans=root(ans*ro);
38        }
39        cout << ans << endl;
40    }
41    return 0;
42}
43

wyh 2011-08-05 00:01 发表评论