首页 > > 程序设计 > C/C++ >

2017.10.26水题大作战部分题解

2018-06-17 21:40:49来源：未知阅读 ()

感觉这一场的题目超纲了QWQ。。。

好难啊QWQ。。。。。。

A　　P2907 [USACO08OPEN]农场周围的道路Roads Around The Farm

为什么我感觉这题完全不像入门难度的题啊。。

我的思路是这样的

对于每一个n,k

解一个方程组使得

然后对于得到的x,y分别进行类似的操作

看起来挺简单，

但是我被精度卡了QWQ。。。。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<stdlib.h>
 6 #include<ctime>
 7 using namespace std;
 8 const int MAXN=0x7fffff;
 9 const int INF=50;
10 inline int read()
11 {
12     char c=getchar();int f=1,x=0;
13     while(c<'0'||c>'9')    {if(c=='-')    f=-1;c=getchar();}
14     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();return x*f;
15 }
16 int ans=0;
17 void dfs(int n,int k)
18 {
19     double p=(double)(n+k)/2;
20     double q=(double)n-(n+k)/2;
21     int o=(n+k)/2;
22     double l=p-(double)o;
23     if(l!=0||p>=n&&q<=0||q>=n&&p<=0)
24     {
25         ans++;
26         return ;
27     }
28     dfs(p,k);dfs(q,k);
29 }
30 int main()
31 {
32     int n=read(),k=read();
33     dfs(n,k);
34     printf("%d",ans);
35     return 0;
36 }

View Code

B　　P1851 好朋友

亲和数

直接暴力计算就好

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<stdlib.h>
 6 #include<ctime>
 7 #define LL long long 
 8 using namespace std;
 9 const LL MAXN=0x7fffff;
10 const LL INF=50;
11 inline LL read()
12 {
13     char c=getchar();LL f=1,x=0;
14     while(c<'0'||c>'9')    {if(c=='-')    f=-1;c=getchar();}
15     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();return x*f;
16 }
17 int main()
18 {
19     LL n=read();
20     while(n++)
21     {
22         LL p=n;
23         LL tot=0,tot2=0;
24         for(LL i=1;i<p;i++)    if(p%i==0)    tot+=i;
25         for(LL i=1;i<tot;i++)    if(tot%i==0)    tot2+=i;
26         if(p==tot2&&p!=tot)
27         {    printf("%lld %lld",p,tot);    exit(0);    }
28             
29     }
30     return 0;
31 }

View Code

C　　P1926 小书童——刷题大军

01背包，计算出最大的价值，可以推出时间

对于要做最多的题目，贪心计算

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<stdlib.h>
 6 #include<ctime>
 7 #include<algorithm>
 8 using namespace std;
 9 const int MAXN=151;
10 const int INF=50;
11 inline int read()
12 {
13     char c=getchar();int f=1,x=0;
14     while(c<'0'||c>'9')    {if(c=='-')    f=-1;c=getchar();}
15     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();return x*f;
16 }
17 int n,m,r,k;
18 int dp[MAXN][MAXN];
19 // 0 时间
20 // 1 分值 
21 int ti[MAXN];
22 struct node
23 {
24     int time;
25     int val;
26 }hw[MAXN];
27 int main()
28 {
29     n=read();m=read();k=read();r=read();
30     for(int i=1;i<=n;i++)    ti[i]=read();
31     for(int i=1;i<=m;i++)    hw[i].time=read();
32     for(int i=1;i<=m;i++)    hw[i].val=read();
33     for(int i=1;i<=m;i++)
34         for(int j=0;j<=r;j++)
35             if(j<hw[i].time)    dp[i][j]=dp[i-1][j];
36             else dp[i][j]=max(dp[i-1][j],dp[i-1][j-hw[i].time]+hw[i].val);
37     int ans=0,totcnt=0;
38     sort(ti+1,ti+n+1);
39     for(int i=1;i<=m;i++)
40         for(int j=0;j<=r;j++)
41             if(dp[i][j]>=k)
42                 totcnt=max(totcnt,r-j);
43     int tot=0;
44     int totnum=0;
45     for(int k=1;k<=n;k++)
46         if(ti[k]+tot<=totcnt)
47             tot+=ti[k],totnum++;
48     ans=max(ans,totnum);
49     printf("%d",ans);
50     return 0;
51 }

View Code

D　　P1496 火烧赤壁

按照左端点排序

维护最左端的值和最右端的值

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<stdlib.h>
 6 #include<ctime>
 7 #include<algorithm>
 8 #define LL long long 
 9 using namespace std;
10 const LL MAXN=20001;
11 const LL INF=50;
12 inline LL read()
13 {
14     char c=getchar();LL f=1,x=0;
15     while(c<'0'||c>'9')    {if(c=='-')    f=-1;c=getchar();}
16     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();return x*f;
17 }
18 struct node
19 {
20     LL bg,ed;
21 }a[MAXN];
22 LL n;
23 LL comp(const node &a,const node &b)
24 {
25     return a.bg<b.bg;
26 }
27 LL ans;
28 LL nowleft,nowright;
29 int main()
30 {
31     n=read();
32     for(LL i=1;i<=n;i++)
33     {
34         a[i].bg=read(),a[i].ed=read();
35         if(a[i].bg>a[i].ed)    swap(a[i].bg,a[i].ed);
36     }
37         
38     sort(a+1,a+n+1,comp);
39     nowleft=a[1].bg,nowright=a[1].ed;
40     a[n+1].bg=1e10+10;
41     a[n+1].ed=1e10+20;
42     for(LL i=2;i<=n+1;i++)
43     {
44         if(a[i].bg<=nowright)    nowright=max(nowright,a[i].ed);
45         else
46         {
47             ans+=abs(nowright-nowleft);
48             nowleft=a[i].bg;nowright=a[i].ed;
49         }
50     }
51     printf("%lld",ans);
52     return 0;
53 }

View Code

E　　P1302 可见矩形

不会做哈哈哈

#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<stdlib.h>#include<ctime>#define LL long long usingnamespacestd; const LL MAXN=0x7fffff; const LL INF=50; inline LL read() { char c=getchar();LL f=1,x=0; while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*f; } int main() { LL n=read(); while(n++) { LL p=n; LL tot=0,tot2=0; for(LL i=1;i<p;i++) if(p%i==0) tot+=i; for(LL i=1;i<tot;i++) if(tot%i==0) tot2+=i; if(p==tot2&&p!=tot) { printf("%lld %lld",p,tot); exit(0); } } return0; }