PKUSC 2013 #1

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long 
#define inf 100000000
#define mod 1000000007
#define eps 1e-10
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
int a[25],ans[25];
void dfs(int x,int k)
{
	if(k==7)
	{
		for(int i=1;i<=6;i++)printf("%d ",ans[i]);
		puts("");
		return;
	}
	if(x==n+1)return;
	ans[k]=a[x];
	dfs(x+1,k+1);
	dfs(x+1,k);
}
int main()
{
	while(scanf("%d",&n))
	{
		if(!n)break;
		for(int i=1;i<=n;i++)a[i]=read();
		dfs(1,1);
		puts("");
	}
	return 0;
}

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

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<cmath>

#define ll long long

#define inf 100000000

#define mod 1000000007

#define eps 1e-10

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n;

int a[25],ans[25];

void dfs(int x,int k)

{

if(k==7)

{

for(int i=1;i<=6;i++)printf("%d ",ans[i]);

puts("");

return;

}

if(x==n+1)return;

ans[k]=a[x];

dfs(x+1,k+1);

dfs(x+1,k);

}

int main()

{

while(scanf("%d",&n))

{

if(!n)break;

for(int i=1;i<=n;i++)a[i]=read();

dfs(1,1);

puts("");

}

return 0;

}

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long 
#define inf 100000000
#define mod 1000000007
#define eps 1e-10
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
double c[3005],a[3005],s[3005];
double ans,t;
void cal()
{
	for(int i=2;i<=n+1;i++)
		a[i]=2*a[i-1]-a[i-2]+2*c[i-1];
}
int main()
{
	n=read();
	scanf("%lf",&a[0]);
	scanf("%lf",&t);
	for(int i=1;i<=n;i++)
		scanf("%lf",&c[i]);
	double l=-1000,r=1000;
	for(int i=1;i<=100;i++)
	{
		double mid=(l+r)/2.0;
		a[1]=mid;
		cal();
		if(a[n+1]<=t)l=mid;
		else r=mid;
	}
	printf("%.2lf",l);
	return 0;
}

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

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<cmath>

#define ll long long

#define inf 100000000

#define mod 1000000007

#define eps 1e-10

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n;

double c[3005],a[3005],s[3005];

double ans,t;

void cal()

{

for(int i=2;i<=n+1;i++)

a[i]=2*a[i-1]-a[i-2]+2*c[i-1];

}

int main()

{

n=read();

scanf("%lf",&a[0]);

scanf("%lf",&t);

for(int i=1;i<=n;i++)

scanf("%lf",&c[i]);

double l=-1000,r=1000;

for(int i=1;i<=100;i++)

{

double mid=(l+r)/2.0;

a[1]=mid;

cal();

if(a[n+1]<=t)l=mid;

else r=mid;

}

printf("%.2lf",l);

return 0;

}

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<complex>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define eps 1e-8
#define ll long long
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,l;
string a,b;
vector<int>e[3005];
unsigned ll H[3005];
int fa[3005];
bool cmp(int a,int b)
{
	return H[a]>H[b];
}
void dfs(int x)
{
	H[x]=19;
	for(int i=0;i<e[x].size();i++)
		dfs(e[x][i]);
	sort(e[x].begin(),e[x].end(),cmp);
	for(int i=0;i<e[x].size();i++)
		H[x]=H[x]*9875321+H[e[x][i]]*197;
}
unsigned ll cal(string a)
{
	l=a.length();
	int now=1,cnt=1;
	for(int i=0;i<l;i++)
		if(a[i]=='0')
		{
			e[now].push_back(++cnt);
			fa[cnt]=now;now=cnt;
		}
		else now=fa[now];
	dfs(1);
	for(int i=1;i<=cnt;i++)e[i].clear();
	return H[1];
}
int main()
{
	n=read();
	while(n--)
	{
		cin>>a;cin>>b;
		if(cal(a)==cal(b))puts("same");
		else puts("different");
	}
	return 0;
}

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

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<complex>

#include<iostream>

#include<algorithm>

#define pi acos(-1)

#define eps 1e-8

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,l;

string a,b;

vector<int>e[3005];

unsigned ll H[3005];

int fa[3005];

bool cmp(int a,int b)

{

return H[a]>H[b];

}

void dfs(int x)

{

H[x]=19;

for(int i=0;i<e[x].size();i++)

dfs(e[x][i]);

sort(e[x].begin(),e[x].end(),cmp);

for(int i=0;i<e[x].size();i++)

H[x]=H[x]*9875321+H[e[x][i]]*197;

}

unsigned ll cal(string a)

{

l=a.length();

int now=1,cnt=1;

for(int i=0;i<l;i++)

if(a[i]=='0')

{

e[now].push_back(++cnt);

fa[cnt]=now;now=cnt;

}

else now=fa[now];

dfs(1);

for(int i=1;i<=cnt;i++)e[i].clear();

return H[1];

}

int main()

{

n=read();

while(n--)

{

cin>>a;cin>>b;

if(cal(a)==cal(b))puts("same");

else puts("different");

}

return 0;

}

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#define ll long long 
#define inf 100000000
#define mod 1000000007
#define eps 1e-10
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
int fa[105];
int q[105][1005],top[105];
int find(int x)
{
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
bool check(int a,int b)
{
	if(top[a]!=top[b])return 0;
	for(int i=1;i<=top[a];i++)
		if(q[a][i]!=q[b][i])return 0;
	return 1;
}
int main()
{
	n=read();m=read();
	int a,b;
	while(scanf("%d%d",&a,&b)!=EOF)
		q[a][++top[a]]=b;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=n;i++)
		sort(q[i]+1,q[i]+top[i]+1);
	for(int i=1;i<=n;i++)
		top[i]=unique(q[i]+1,q[i]+top[i]+1)-q[i]-1;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			if(check(i,j))
				fa[find(i)]=find(j);
	int ans=0;
	for(int i=1;i<=n;i++)if(i==find(i))ans++;
	printf("%d\n",ans);
	return 0;
}

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

51

52

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<vector>

#define ll long long

#define inf 100000000

#define mod 1000000007

#define eps 1e-10

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m;

int fa[105];

int q[105][1005],top[105];

int find(int x)

{

return x==fa[x]?x:fa[x]=find(fa[x]);

}

bool check(int a,int b)

{

if(top[a]!=top[b])return 0;

for(int i=1;i<=top[a];i++)

if(q[a][i]!=q[b][i])return 0;

return 1;

}

int main()

{

n=read();m=read();

int a,b;

while(scanf("%d%d",&a,&b)!=EOF)

q[a][++top[a]]=b;

for(int i=1;i<=n;i++)fa[i]=i;

for(int i=1;i<=n;i++)

sort(q[i]+1,q[i]+top[i]+1);

for(int i=1;i<=n;i++)

top[i]=unique(q[i]+1,q[i]+top[i]+1)-q[i]-1;

for(int i=1;i<=n;i++)

for(int j=i+1;j<=n;j++)

if(check(i,j))

fa[find(i)]=find(j);

int ans=0;

for(int i=1;i<=n;i++)if(i==find(i))ans++;

printf("%d\n",ans);

return 0;

}

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#define ll long long 
#define inf 100000000
#define mod 1000000007
#define eps 1e-10
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
int a[1005][2];
int f[1005][10005];
int main()
{
	n=read();
	for(int i=1;i<=n;i++)a[i][0]=read(),a[i][1]=read();
	memset(f,127,sizeof(f));
	f[0][5000]=0;
	for(int i=0;i<n;i++)
		for(int j=0;j<=10000;j++)
			if(f[i][j]<inf)
			{
				int t1=a[i+1][0],t2=a[i+1][1];
				f[i+1][j+t1-t2]=min(f[i][j],f[i+1][j+t1-t2]);
				f[i+1][j+t2-t1]=min(f[i][j]+1,f[i+1][j+t2-t1]);
			}
	for(int i=0;i<=5000;i++)
		if(f[n][5000+i]<inf||f[n][5000-i]<inf)
		{
			printf("%d\n",min(f[n][5000+i],f[n][5000-i]));
			break;
		}
	return 0;
}

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

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<vector>

#define ll long long

#define inf 100000000

#define mod 1000000007

#define eps 1e-10

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n;

int a[1005][2];

int f[1005][10005];

int main()

{

n=read();

for(int i=1;i<=n;i++)a[i][0]=read(),a[i][1]=read();

memset(f,127,sizeof(f));

f[0][5000]=0;

for(int i=0;i<n;i++)

for(int j=0;j<=10000;j++)

if(f[i][j]<inf)

{

int t1=a[i+1][0],t2=a[i+1][1];

f[i+1][j+t1-t2]=min(f[i][j],f[i+1][j+t1-t2]);

f[i+1][j+t2-t1]=min(f[i][j]+1,f[i+1][j+t2-t1]);

}

for(int i=0;i<=5000;i++)

if(f[n][5000+i]<inf||f[n][5000-i]<inf)

{

printf("%d\n",min(f[n][5000+i],f[n][5000-i]));

break;

}

return 0;

}

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<complex>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define eps 1e-8
#define ll long long
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
bool flag;
int n,m=676,cnt,last[1005];
double dis[1005],mid;
bool vis[1005];
char a[1005];
struct edge{
	int to,next;double v;
}e[100005];
void insert(int u,int v,int w)
{
	e[++cnt]=(edge){v,last[u],w};last[u]=cnt;
}
int cal(char a,char b)
{
	return (a-'a')*26+b-'a'+1;
}
void dfs(int x)
{
	vis[x]=1;
	for(int i=last[x];i;i=e[i].next)
		if(dis[x]+e[i].v-mid>dis[e[i].to])
		{
			if(vis[e[i].to]){flag=1;return;}
			else 
			{
				dis[e[i].to]=dis[x]+e[i].v-mid;
				dfs(e[i].to);
			}
		}
	vis[x]=0;
}
bool check()
{
	memset(dis,0,sizeof(dis));
	memset(vis,0,sizeof(vis));
	flag=0;
	for(int i=1;i<=m;i++)
	{
		dfs(i);
		if(flag)return 1;
	}
	return 0;
}
int main()
{
	while(scanf("%d",&n))
	{
		if(n==0)break;
		cnt=0;
		memset(last,0,sizeof(last));
		for(int i=1;i<=n;i++)
		{
			scanf("%s",a+1);
			int l=strlen(a+1);
			insert(cal(a[1],a[2]),cal(a[l-1],a[l]),l);
		}
		double l=0,r=1000;
		bool f=0;
		for(int i=1;i<=60;i++)
		{
			mid=(l+r)/2;
			if(check())f=1,l=mid;
			else r=mid;
		}
		if(!f)puts("No solution.");
		else printf("%.2f\n",l);
	}
	return 0;
}

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

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<complex>

#include<iostream>

#include<algorithm>

#define pi acos(-1)

#define eps 1e-8

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

bool flag;

int n,m=676,cnt,last[1005];

double dis[1005],mid;

bool vis[1005];

char a[1005];

struct edge{

int to,next;double v;

}e[100005];

void insert(int u,int v,int w)

{

e[++cnt]=(edge){v,last[u],w};last[u]=cnt;

}

int cal(char a,char b)

{

return (a-'a')*26+b-'a'+1;

}

void dfs(int x)

{

vis[x]=1;

for(int i=last[x];i;i=e[i].next)

if(dis[x]+e[i].v-mid>dis[e[i].to])

{

if(vis[e[i].to]){flag=1;return;}

else

{

dis[e[i].to]=dis[x]+e[i].v-mid;

dfs(e[i].to);

}

vis[x]=0;

}

bool check()

{

memset(dis,0,sizeof(dis));

memset(vis,0,sizeof(vis));

flag=0;

for(int i=1;i<=m;i++)

{

dfs(i);

if(flag)return 1;

}

return 0;

}

int main()

{

while(scanf("%d",&n))

{

if(n==0)break;

cnt=0;

memset(last,0,sizeof(last));

for(int i=1;i<=n;i++)

{

scanf("%s",a+1);

int l=strlen(a+1);

insert(cal(a[1],a[2]),cal(a[l-1],a[l]),l);

}

double l=0,r=1000;

bool f=0;

for(int i=1;i<=60;i++)

{

mid=(l+r)/2;

if(check())f=1,l=mid;

else r=mid;

}

if(!f)puts("No solution.");

else printf("%.2f\n",l);

}

return 0;

}

hzwer.com _ Home | http://hzwer.com

分类目录

热门文章

Myfriends

近期评论