USACO 3.4

  • 美国血统 American Heritage
  • 电网 Electric Fences
  • “破锣摇滚”乐队 Raucous Rockers

p1827 美国血统 American Heritage

这道题是已知先序遍历与中序遍历求后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/*
ID: ylx14271
PROG: heritage
LANG: C++
*/
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
string x;//先序遍历
string z;//中序遍历
string h;//后序遍历
string q(string a,string b)//a:先序遍历,b:中序遍历
{
if (a==""||b=="") return "";
int aaa=0;
int fa;//根节点在中序遍历位置
fa=b.find(a[0],aaa);//求
string aa=b.substr(0,fa);//中序遍历左子树
string bb=b.substr(fa+1,b.size()-fa-1);//中序遍历右子树
string a1=a.substr(1,fa);//先序遍历左子树
string b1=a.substr(fa+1,a.size()-fa-1);//先序遍历右子树
//cout<<a1<<endl<<b1<<endl;
//cout<<aa<<endl<<bb<<endl;
return q(a1,aa)+q(b1,bb)+a[0];//根左右
}
int main()
{
cin>>z;
cin>>x;
int ii=0;
cout<<q(x,z);
return 0;
}

//美国血统
还有一题是已知中序遍历与后序遍历求先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var
zx,hx:ansistring;
procedure qxx(zx,hx:ansistring);
var len,zuo1,you1,zuo,you:ansistring;
begin
if zx='' then exit;
len:=hx[length(hx)];
zuo:=copy(zx,1,pos(len,zx)-1);
you:=copy(zx,pos(len,zx)+1,length(zx)-pos(len,zx));
zuo1:=copy(hx,1,length(zuo));
you1:=copy(hx,length(zuo)+1,length(you));
write(len);
qxx(zuo,zuo1);
qxx(you,you1);
end;
begin
readln(zx);
readln(hx);
qxx(zx,hx);
end.

p2735 电网 Electric Fences

下面这段话来自百度百科
一张方格纸上,上面画着纵横两组平行线,相邻平行线之间的距离都相等,这样两组平行线的交点,就是所谓格点。如果取一个格点做原点O,如图1,取通过这个格点的横向和纵向两直线分别做横坐标轴OX和纵坐标轴OY,并取原来方格边长做单位长,建立一个坐标系。这时前面所说的格点,显然就是纵横两坐标都是整数的那些点。如图1中的O、P、Q、M、N都是格点。由于这个缘故,我们又叫格点为整点。
一个多边形的顶点如果全是格点,这多边形就叫做格点多边形。有趣的是,这种格点多边形的面积计算起来很方便,只要数一下图形边线上的点的数目及图内的点的数目,就可用公式算出。
这个公式是皮克(Pick)在1899年给出的,被称为“皮克定理”,这是一个实用而有趣的定理。
给定顶点坐标均是整点(或正方形格点)的简单多边形,皮克定理说明了其面积S和内部格点数目n、边上格点数目s的关系:
S=n+s/2-1
(其中n表示多边形内部的点数,s表示多边形边界上的点数,S表示多边形的面积)
其中我们要求的是n,S很容易求
我们可以设直线(0,0)→(n,m)上的一点坐标为(x,x*m/n)(x<n),且这个点为整点,求符合条件的x的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
ID: ylx14271
PROG: fence9
LANG: C++
*/
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}//最大公约数
int s,b,i,n,m,p;
int main()
{
freopen("fence9.in","r",stdin);
freopen("fence9.out","w",stdout);
scanf("%d%d%d",&n,&m,&p);
b=gcd(n,m)+gcd(abs(p-n),m)+p;//边上格点数目
s=(p*m)/2;//面积 s=i+b/2-1
i=s-b/2+1;
printf("%d\n",i);
return 0;
}

p2736 “破锣摇滚”乐队 Raucous Rockers

01背包,每首歌只有放和不放2种情况
f[i][j][k]表示前i个中,j张k分钟的光盘 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/*
ID: ylx14271
PROG: rockers
LANG: C++
*/
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
int n,t,m,i,j,k;
int a[25];
int f[25][25][25];//f[i][j][k]表示前i个中,j张k分钟的光盘
int main()
{
scanf("%d%d%d",&n,&t,&m);
for (i=1;i<=n;i++)
scanf("%d",&a[i]);
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
for (k=1;k<=t;k++)
{
if (k>=a[i])
{
f[i][j][k]=max(f[i-1][j][k],f[i-1][j][k-a[i]]+1);
//不放或放这张光盘末
f[i][j][k]=max(f[i][j][k],f[i-1][j-1][t]+1);
//放本张光盘最前面
}
else f[i][j][k]=f[i-1][j][k];
}
printf("%d\n",f[n][m][t]);
return 0;
}