2013PKU计算概论入学测试

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<queue>
#include<cmath>
#include<vector>
#include<algorithm>
#include<map>
#define ll long long
#define inf 2147483647
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,p,m;
vector<int> a;
int main()
{
    while(scanf("%d%d%d",&n,&p,&m)!=EOF)
    {
        if(!n)return 0;
        for(int i=1;i<=n;i++)a.push_back(i);
        int t=p-1;
        for(int i=1;i<=n;i++)
        {
            t=(t+m-1)%a.size();
            if(i!=n)printf("%d,",a[t]);
            else printf("%d\n",a[t]);
            a.erase(a.begin()+t);           
        }
    }
    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

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<queue>

#include<cmath>

#include<vector>

#include<algorithm>

#include<map>

#define ll long long

#define inf 2147483647

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,p,m;

vector<int> a;

int main()

{

while(scanf("%d%d%d",&n,&p,&m)!=EOF)

{

if(!n)return 0;

for(int i=1;i<=n;i++)a.push_back(i);

int t=p-1;

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

{

t=(t+m-1)%a.size();

if(i!=n)printf("%d,",a[t]);

else printf("%d\n",a[t]);

a.erase(a.begin()+t);

}

return 0;

}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<queue>
#include<cmath>
#include<vector>
#include<algorithm>
#include<map>
#define ll long long
#define inf 2147483647
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,S;
ll c[10005],y[10005];
ll ans,now;
int main()
{
    n=read();S=read();
    for(int i=1;i<=n;i++)
        c[i]=read(),y[i]=read();
    now=inf;
    for(int i=1;i<=n;i++)
    {
        ans+=min(now,c[i])*y[i];
        now=min(now,c[i])+S;
    }
    cout<<ans<<endl;
    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

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<queue>

#include<cmath>

#include<vector>

#include<algorithm>

#include<map>

#define ll long long

#define inf 2147483647

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,S;

ll c[10005],y[10005];

ll ans,now;

int main()

{

n=read();S=read();

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

c[i]=read(),y[i]=read();

now=inf;

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

{

ans+=min(now,c[i])*y[i];

now=min(now,c[i])+S;

}

cout<<ans<<endl;

return 0;

}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<queue>
#include<cmath>
#include<vector>
#include<algorithm>
#include<map>
#define ll long long
#define inf 2147483647
#define next(x,y,z) y==n?dfs(x+1,1,z):dfs(x,y+1,z)
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,K,ans;
bool r[15],c[15];
char a[15][15];
void dfs(int x,int y,int now)
{
    if(now==K)
    {
        ans++;
        return;
    }
    if(x==n+1)return;
    next(x,y,now);
    if(a[x][y]=='#'&&!r[x]&&!c[y])
    {
        r[x]=c[y]=1;
        next(x,y,now+1);
        r[x]=c[y]=0;
    }
}
int main()
{
    while(scanf("%d%d",&n,&K))
    {
        if(n==-1)return 0;
        ans=0;
        memset(r,0,sizeof(r));
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++)
            scanf("%s",a[i]+1);
        dfs(1,1,0);
        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

53

54

55

56

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<queue>

#include<cmath>

#include<vector>

#include<algorithm>

#include<map>

#define ll long long

#define inf 2147483647

#define next(x,y,z) y==n?dfs(x+1,1,z):dfs(x,y+1,z)

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,K,ans;

bool r[15],c[15];

char a[15][15];

void dfs(int x,int y,int now)

{

if(now==K)

{

ans++;

return;

}

if(x==n+1)return;

next(x,y,now);

if(a[x][y]=='#'&&!r[x]&&!c[y])

{

r[x]=c[y]=1;

next(x,y,now+1);

r[x]=c[y]=0;

}

int main()

{

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

{

if(n==-1)return 0;

ans=0;

memset(r,0,sizeof(r));

memset(c,0,sizeof(c));

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

scanf("%s",a[i]+1);

dfs(1,1,0);

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

}

return 0;

}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<queue>
#include<cmath>
#include<vector>
#include<algorithm>
#include<map>
#define ll long long
#define inf 2147483647
#define next(x,y,z) y==n?dfs(x+1,1,z):dfs(x,y+1,z)
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,ans=inf;
int a[105];
int f[55][45005],g[55][45005];
int tot;
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        tot+=a[i];
    }
    f[0][0]=1;
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=min(i,n/2);j++)
            for(int k=0;k<=tot;k++)
                if(f[j][k])
                {
                    if(i==n&&j==n/2)
                        ans=min(ans,abs(tot-2*k));
                    g[j+1][k+a[i+1]]=1;
                    g[j][k]=1;
                }
        for(int j=0;j<=min(i,n/2);j++)
            for(int k=0;k<=tot;k++)
            {
                swap(f[j][k],g[j][k]);
                g[j][k]=0;
            }
    }
    printf("%d %d\n",(tot-ans)/2,(tot+ans)/2);
    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

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<queue>

#include<cmath>

#include<vector>

#include<algorithm>

#include<map>

#define ll long long

#define inf 2147483647

#define next(x,y,z) y==n?dfs(x+1,1,z):dfs(x,y+1,z)

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,ans=inf;

int a[105];

int f[55][45005],g[55][45005];

int tot;

int main()

{

n=read();

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

{

a[i]=read();

tot+=a[i];

}

f[0][0]=1;

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

{

for(int j=0;j<=min(i,n/2);j++)

for(int k=0;k<=tot;k++)

if(f[j][k])

{

if(i==n&&j==n/2)

ans=min(ans,abs(tot-2*k));

g[j+1][k+a[i+1]]=1;

g[j][k]=1;

}

for(int j=0;j<=min(i,n/2);j++)

for(int k=0;k<=tot;k++)

{

swap(f[j][k],g[j][k]);

g[j][k]=0;

}

printf("%d %d\n",(tot-ans)/2,(tot+ans)/2);

return 0;

}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<queue>
#include<cmath>
#include<vector>
#include<algorithm>
#include<map>
#define ll long long
#define inf 1000000000
#define next(x,y,z) y==n?dfs(x+1,1,z):dfs(x,y+1,z)
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,P,ans=inf,rt;
vector<int>e[205];
bool deg[205];
int f[205][205];
void dp(int x)
{
    f[x][1]=e[x].size();
    for(int i=0;i<e[x].size();i++)
    {
        int y=e[x][i];
        dp(y);
        for(int j=n;j>=1;j--)
            for(int k=1;k<=n;k++)
                if(f[x][j]!=inf&&f[y][k]!=inf)
                    f[x][j+k]=min(f[x][j+k],f[x][j]+f[y][k]-1);
    }
    if(x==rt&&f[x][P]<ans)ans=f[x][P];
    if(x!=rt&&f[x][P]+1<ans)ans=f[x][P]+1;
        
}
int main()
{
    n=read();P=read();
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read();
        e[u].push_back(v);
        deg[v]=1;       
    }
    for(int i=1;i<=n;i++)
        if(!deg[i])rt=i;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            f[i][j]=inf;
    dp(rt);
    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

53

54

55

56

57

58

59

60

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<queue>

#include<cmath>

#include<vector>

#include<algorithm>

#include<map>

#define ll long long

#define inf 1000000000

#define next(x,y,z) y==n?dfs(x+1,1,z):dfs(x,y+1,z)

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,P,ans=inf,rt;

vector<int>e[205];

bool deg[205];

int f[205][205];

void dp(int x)

{

f[x][1]=e[x].size();

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

{

int y=e[x][i];

dp(y);

for(int j=n;j>=1;j--)

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

if(f[x][j]!=inf&&f[y][k]!=inf)

f[x][j+k]=min(f[x][j+k],f[x][j]+f[y][k]-1);

}

if(x==rt&&f[x][P]<ans)ans=f[x][P];

if(x!=rt&&f[x][P]+1<ans)ans=f[x][P]+1;

}

int main()

{

n=read();P=read();

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

{

int u=read(),v=read();

e[u].push_back(v);

deg[v]=1;

}

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

if(!deg[i])rt=i;

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

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

f[i][j]=inf;

dp(rt);

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

return 0;

}

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

分类目录

热门文章

Myfriends

近期评论