8-14-Exercise

这次是我这组出题......我出的是B、C、D【虽然本来是想出的很难......╮(╯▽╰)╭但是，没找到AC1000+同时又让我想出的难题......SO...我出的真的不难= =】，荆红出的是A，从此不再出的是D......

A.HDU 1789 Doing Homework again

用贪心做~先按分数从大到小排，若分数相同则按天数从大到小排。排好后，从头开始扫描，扫到未标记的点，就进行标记（A），同时看A点后是否还有要在A点的天数之内一定要完成的作业，直到把A点的天数填完，若天数不够填，则证明哪一门作业无法按时完成~

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 class Node
 8 {
 9 public:
10     int x,y;
11 }a[1010];
12 
13 bool comp(Node w,Node q)
14 {
15     if(w.x==q.x)
16         return w.y>q.y;
17     return w.x>q.x;
18 }
19 
20 int main()
21 {
22     int t,number,b[1010],i,j,n;
23     scanf("%d",&t);
24     while(t--)
25     {
26         scanf("%d",&n);
27         memset(a,0,sizeof(a));
28         for(i=0;i<n;i++)
29             scanf("%d",&a[i].y);
30         for(i=0;i<n;i++)
31             scanf("%d",&a[i].x);
32         sort(a,a+n,comp);
33         number=0;
34         memset(b,0,sizeof(b));
35         for(i=0;i<n;i++)
36         {
37             for(j=a[i].y;j>0;j--)
38                 if(b[j]==0)
39                 {
40                     b[j]=1;
41                     break;
42                 }
43             if(j==0)
44                 number+=a[i].x;
45         }
46         printf("%d
",number);
47     }
48     return 0;
49 }

B.HDU 1846 Brave Game && C.HDU 1527 取石子游戏

这两道单独写的有：链接╮(╯▽╰)╭

D.POJ 1844 Sum

一道小清新的趣味数学题~【很有趣吧╮(╯▽╰)╭】

sum=1+2+3+4+...+i

当sum==s时，直接输出i；

当上一步无法做到时，则当第一次达到(sum-s)%2==0时，输出i即可~

证明【第二步，即此时sum达不到s，且sum>s】：

res=sum-s;

其实仔细想一想~很容易知道当改变sum里的+号时，sum永远是减去一个偶数【why?比如把sum中j前的加号改为减号，就是相当于sum-j-j，会减去2*j】~

SO~若res为奇数，无论如何改变sum中的加号，res永远都无法为0；只有res为偶数时，才有机会通过改变sum中的加号为0。因此当sum无法恰好达到s时，那么第一次达到res%2==0的i就是所求值~~~

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main()
{
    int s,sum,i,res;
    while(~scanf("%d",&s))
    {
        sum=0;
        res=0;
        for(i=1;;i++)
        {
            sum+=i;
            res=sum-s;
            if(sum==s) break;
            if(res>0 && res%2==0)
                break;
        }
        printf("%d
",i);
    }
    return 0;
}

//memory：164KB time：0ms

E.HDU 1142 A Walk Through the Forest

dijkstra+记忆化搜索

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<string.h>
 4 #define N 1010
 5 #define INF 2000000000
 6 
 7 using namespace std;
 8 
 9 int map[N][N],lowcost[N],visited[N],d[N],p[N];
10 
11 
12 void dijkstra(int s,int n)
13 {
14     memset(visited,false,sizeof(visited));
15     int i,j,k,min;
16     for(i=1;i<=n;i++)
17     {
18         lowcost[i]=map[s][i];
19     }
20     d[s]=0;
21     visited[s]=true;
22     for(i=1;i<n;i++)
23     {
24         min=INF;
25         for(j=1;j<=n;j++)
26         {
27             if(!visited[j]&&min>lowcost[j])
28             {
29                 min=lowcost[j];
30                 k=j;
31             }
32         }
33         d[k]=min;
34         visited[k]=true;
35         for(j=1;j<=n;j++)
36         {
37             if(!visited[j]&&lowcost[j]>map[k][j]+d[k])
38                 lowcost[j]=map[k][j]+d[k];
39         }
40     }
41 }
42 
43 int DFS(int s,int n)
44 {
45     if(p[s]) return p[s];
46     if(s==2)  return 1;
47     int i,sum=0;
48     for(i=1;i<=n;i++)
49     {
50         if(map[s][i]<INF&&d[s]>d[i])
51         {
52             if(p[i]) sum=sum+p[i];
53             else sum=sum+DFS(i,n);
54         }
55     }
56     sum=sum+p[s];
57     p[s]=sum;
58     return p[s];
59 }
60 
61 int main()
62 {
63     int i,j,n,m,u,v,w;
64     while(cin>>n&&n)
65     {
66         cin>>m;
67         memset(p,0,sizeof(p));
68         for(i=1;i<=n;i++)
69         {
70             for(j=1;j<=n;j++)
71             {
72                 map[i][j]=(i==j?0:INF);
73             }
74         }
75         for(i=0;i<m;i++)
76         {
77             scanf("%d%d%d",&u,&v,&w);
78             map[u][v]=map[v][u]=w;
79         }
80         dijkstra(2,n);
81         cout<<DFS(1,n)<<endl;
82     }
83     return 0;
84 }

//memory：4276KB time：78ms