26水题大应战有些题解

P2690 接苹果,p2690接苹果

2017.10.26水题大应战某些题解,2017.10.26题解

澳门网上正规赌场网址 1

 

感到这一场的标题超纲了QWQ。。。

好难啊QWQ。。。。。。

P2885 [USACO07NOV]电话线Telephone Wire,p2885usaco07nov

主题材料背景

USACO

A  P2907 [USACO08OPEN]农场四周的征程Roads Around The Farm

怎么本身感觉那题完全不像入门难度的题啊。。

本人的思绪是那般的

对此每三个n,k

解四个方程组使得

x-y=kx−y=k

x+y=nx+y=n

接下来对于拿到的x,y分别打开类似的操作

看起来挺轻巧,

可是本身被精度卡了QWQ。。。。

澳门网上正规赌场网址 2 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

难题陈诉

Farmer John’s cows are getting restless about their poor telephone
service; they want FJ to replace the old telephone wire with new, more
efficient wire. The new wiring will utilize N (2 ≤ N ≤ 100,000)
already-installed telephone poles, each with some heighti meters (1 ≤
heighti ≤ 100). The new wire will connect the tops of each pair of
adjacent poles and will incur a penalty cost C × the two poles’ height
difference for each section of wire where the poles are of different
heights (1 ≤ C ≤ 100). The poles, of course, are in a certain sequence
and can not be moved.

Farmer John figures that if he makes some poles taller he can reduce his
penalties, though with some other additional cost. He can add an integer
X number of meters to a pole at a cost of X2.

Help Farmer John determine the cheapest combination of growing pole
heights and connecting wire so that the cows can get their new and
improved service.

交由若干棵树的万丈,你能够扩充一种操作:把某棵树增高h,开支为h*h。

操作完毕后连线,两棵树间费用为中度差*定值c。

求二种成本加和微小值。

难点汇报

比非常少有人知晓水牛爱吃苹果。农夫John的农场上有两棵苹果树(编号为1和2),
每一棵树上都长满了苹果。白牛贝茜无法摘下树上的苹果,所以他不得不等待苹果
从树上落下。可是,由于苹果掉到地上会摔烂,贝茜必得在上空中接住苹果(未有人爱吃摔烂的苹果)。贝茜吃东西非常的慢,她接到苹果后仅用几分钟就可以吃完。每一分钟,两棵苹果树当中的一棵会掉落贰个苹果。贝茜已经过了足足的教练,
只要站在树下就料定能接住那棵树上掉落的苹果。同有时候,贝茜能够在两棵树之间
快捷移动(移动时间远点儿1分钟),由此当苹果掉落时,她必然站在两棵树当中的一棵下边。另外,水牛不乐意不停地往来于两棵树之间,因此会失去一些苹果。苹果每分钟掉落一个,共T(1<=T<=1000)分钟,贝茜最多愿意移动W(1<=W<=30)
次。现给出每秒钟掉落苹果的树的编号,供给推断贝茜能够接住的最多苹果数。
初始时贝茜在1号树下。

B  P1851 好朋友

亲和数

直白暴力总括就好

澳门网上正规赌场网址 3 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

输入输出格式

输入格式:

 

  • Line 1: Two space-separated integers: N and C

  • Lines 2..N+1: Line i+1 contains a single integer: heighti

 

输出格式:

 

  • Line 1: The minimum total amount of money that it will cost Farmer
    John to attach the new telephone wire.

 

输入输出格式

输入格式:

 

第一行2个数,t和k。接下来的t行,每行一个数,代表在时刻t苹果是从1号苹果树照旧从2号苹果树上掉下来的。

 

出口格式:

 

对此各种测量试验点,输出一行,三个数,为红牛最多抽取的苹果的多少。

 

C  P1927 小书童——刷题大军

01手提袋,计算出最大的价值,能够生产时间

对于要做最多的主题素材,贪心总结

澳门网上正规赌场网址 4 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

 

输入输出样例

输入样例#1:

5 2
2
3
5
1
4

输出样例#1:15

一开始自己写了个DP,居然能过样例
特别兴奋,
但是交上去只有70分
发现时间复杂度有点高
思路比较简单:
我们可以很容易的看出这道题具有无后效性,
用dp[i][j]表示前i棵树,第i棵树高度为j的最小代价
先预处理一下dp[1][j],然后对于每一棵树,我们枚举它的前一棵树的高度和这棵树的高度,
计算一下就好
时间复杂度n*h*h

澳门网上正规赌场网址 5 1
#include<iostream> 2 #include<cstdio> 3
#include<cstring> 4 #include<cmath> 5
#include<cstring> 6 #include<algorithm> 7
#include<queue> 8 #include<cstdlib> 9 using namespace std;
10 const int MAXN=100001; 11 const int INF =0x7f7f7f7f; 12 inline void
read(int &n) 13 { 14 char c=’+’;bool flag=0;n=0; 15
while(c<‘0’||c>’9′){c=getchar();if(c==’-‘)flag=1;} 16
while(c>=’0’&&c<=’9’)n=n*10+c-48,c=getchar(); 17 } 18 int
dp[MAXN][201];// 第i棵树,高度为j的矮小耗费 19 int n,C; 20 int
a[MAXN]; 21 int maxheight; 22 int main() 23 { 24 read(n);read(C); 25
memset(dp,INF,sizeof(dp)); 26 for(int i=1;i<=n;i++) 27
read(a[i]),maxheight=max(maxheight,a[i]); 28 for(int
i=a[1];i<=maxheight;i++) 29 dp[1][i]=(i-a[1])*(i-a[1]); 30
31 for(int i=2;i<=n;i++)//枚举全体树 32 for(int
j=a[i];j<=maxheight;j++)//枚举那棵树的高度 33 for(int
k=a[i-1];k<=maxheight;k++)//枚举前一棵树的可观 34
dp[i][j]=min(dp[i][j], 35
((j-a[i])*(j-a[i])+(dp[i-1][k])+abs(j-k)*C)); 36 37 38 int
ans=0x7fffff; 39 for(int i=a[n];i<=maxheight;i++) 40
ans=min(ans,dp[n][i]); 41 printf(“%d”,ans); 42 return 0; 43 } View Code

然后化简一下式子

 

澳门网上正规赌场网址 6 1
#include<iostream> 2 #include<cstdio> 3
#include<cstdlib> 4 #include<cstring> 5 using namespace
std; 6 const int MAXN=300005; 7 const int INF =0x7fffff; 8 const int
maxheight=100; 9 int dp[301];// 第i棵树,中度为j的一丁点儿花费 10 int
f[301]; 11 int n,C; 12 int a[MAXN]; 13 int bgsum[MAXN]; 14 int
edsum[MAXN]; 15 int main() { 16 scanf(“%d%d”,&n,&C); 17 for(int i=0;
i<n; i++) 18 scanf(“%d”,&a[i]); 19 memset(dp, 0x3f, sizeof(dp)); 20
for(int i=a[0]; i<=maxheight; i++) 21
dp[i]=(i-a[0])*(i-a[0]); 22 23 for(int i=1; i<n; i++) {
//枚举全体树 24 memcpy(f,dp,sizeof(dp)); 25 for(int j=0;
j<=maxheight; j++) dp[j]=bgsum[j]=edsum[j]=INF; 26 27
bgsum[0]=f[0]; 28 for(int j=1; j<=maxheight; j++) 29
bgsum[j]=min(bgsum[j-1],f[j]-C*j); 30 31
edsum[maxheight]=f[maxheight]+maxheight*C; 32 for(int
j=maxheight-1; j>=0; j–) 33
edsum[j]=min(edsum[j+1],f[j]+C*j); 34 35 for(int j=a[i];
j<=maxheight; j++) //枚举那棵树的可观 36
dp[j]=min(edsum[j]-C*j,bgsum[j]+C*j)+(j-a[i])*(j-a[i]); 37
} 38 int ans=0x7fffff; 39 for(int i=a[n-1]; i<=maxheight; i++) 40
ans=min(ans,dp[i]); 41 printf(“%d”,ans); 42 return 0; 43 } View Code

 

 

[USACO07NOV]电话线Telephone
Wire,p2885usaco07nov 标题描述 Farmer John’s cows are getting restless
about their poor telephone service; they want FJ to replace the
old…

输入输出样例

输入样例#1:

7 2
2
1
1
2
2
1
1

输出样例#1:

6

D  P1496 火烧赤壁

遵从左端点排序

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

澳门网上正规赌场网址 7 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

 

说明

DP

 

深感温馨的DP有所长进了,从前连转移方程都不会列,以往竟是能过两个点。。

不堪设想,(不会报告你们难度是普遍-)

澳门网上正规赌场网址 8 1
#include<iostream> 2 #include<cstdio> 3
#include<cstring> 4 #include<cmath> 5
#include<queue> 6 using namespace std; 7 void read(int &n) 8 { 9
char c=’+’;int x=0;bool flag=0; 10 while(c<‘0’||c>’9′) 11
{c=getchar();if(c==’-‘)flag=1;} 12 while(c>=’0’&&c<=’9’) 13
{x=x*10+(c-48);c=getchar();} 14 flag==1?n=-x:n=x; 15 } 16 int n,m; 17
int a[10001]; 18 int dp[10001][31]; 19 int main() 20 { 21
read(n);read(m); 22 for(int i=1;i<=n;i++) 23 read(a[i]); 24
if(a[1]==1) 25 dp[1][0]=1; 26 else dp[1][1]=1; 27 for(int
i=2;i<=n;i++) 28 for(int j=0;j<=m&&j<=i;j++) 29
if(a[i]==a[i-1])// 一样不用移动 30
dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+1; 31 else // 不相同
32 dp[i][j]=max(dp[i-1][j-1]+1,dp[i-1][j]); 33 int ans=0; 34
for(int i=1;i<=m;i++) 35 ans=max(ans,dp[n][i]); 36
printf(“%d”,ans); 37 return 0; 42,即便不掌握怎么错了。。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 using namespace std;
 7 void read(int &n)
 8 {
 9     char c='+';int x=0;bool flag=0;
10     while(c<'0'||c>'9')
11     {c=getchar();if(c=='-')flag=1;}
12     while(c>='0'&&c<='9')
13     {x=x*10+(c-48);c=getchar();}
14     flag==1?n=-x:n=x;
15 }
16 int n,m;
17 int a[10001];
18 int dp[10001][31];
19 int main()
20 {
21     read(n);read(m);
22     for(int i=1;i<=n;i++)
23         read(a[i]);
24 /*    if(a[1]==1)
25         dp[1][0]=1;
26     else dp[1][1]=1;*/
27     for(int i=1;i<=n;i++)
28         for(int j=0;j<=m&&j<=n;j++)
29         {
30             if(j==0)
31                 dp[i][j]=dp[i-1][j];
32             else // 相同不用移动
33                 dp[i][j]=max(dp[i-1][j-1],dp[i-1][j]);
34             if(a[i]==j%2+1)
35                 dp[i][j]++;
36         }
37             
38         //    else // 不相同 
39         //        dp[i][j]=max(dp[i-1][j-1]+1,dp[i-1][j]);
40     int ans=0;
41     for(int i=1;i<=m;i++)    
42         ans=max(ans,dp[n][i]);
43     printf("%d",ans);
44     return 0;
45 }

 

接苹果,p2690接苹果 标题背景 USACO 标题陈诉比较少有人知晓水牛爱吃苹果。农夫John的农场上有两棵苹果树(编号为1和2),
每一棵树…

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; }

认为本场的难题超纲了QWQ。。。 好难啊QWQ。。。。。。 A P2907
[USACO08OPEN]农场方圆的征程Road…

Post Author: admin

发表评论

电子邮件地址不会被公开。 必填项已用*标注