C++博客-51isoft's ACM Journey

PKU 3076 Sudoku Dancing Links (DLX) 果然很生猛……

51isoft — Mon, 27 Jul 2009 18:37:00 GMT

摘要: Sudoku Time Limit: 10000MS Memory Limit: 65536K Total Submissions: 638 ... 阅读全文

51isoft 2009-07-28 02:37 发表评论

TOPCODER SRM405 DIV1 250分题 Relative Path

51isoft — Thu, 13 Nov 2008 12:37:00 GMT

崩溃了……这个破题写了这么久…………但是确实自己要注意这些字符串处理的问题…………

4eZepuWr

Problem Statement

In a typical filesystem, there are files, representing complete units of data. These files are contained in directories, and these directories, in turn, may be contained in other directories, and so on. A path is a pointer to a specific file or directory in this stucture. Most Unix-like OSes have a single root directory, that has all other directories and files directly or indirectly (via other directories) inside it. Such OSes use the following structure for file paths:

///...//

and, correspondingly, the following structure for directory paths:

///.../

For example, "/etc/passwd" (all quotes here and below are for clarity only) points to a file named "passwd" inside a directory named "etc" inside the root directory. Other valid file names might be "/home/user/pictures/me" or just "/file". In this problem, we allow only nonempty sequences of lowercase letters ('a'-'z') as file and directory names.

A special case is the root directory itself, which is referred to as just "/".

When a user works with such an OS, one of the directories is chosen as 'current'. Such a designation allows her to refer to the files in that directory without specifying the full path to the current directory. For example, if the current directory is "/home/user/pictures", then one might refer to the file "/home/user/pictures/me" as just "me" (note that such a short form can be easily spotted by the absence of the starting '/' character). Moreover, the files in subdirectories of the current directory can also be referred to in a short manner: "/home/user/pictures/others/she" can be referred to as "others/she".

And even more exciting is the ability to have short references for files outside the current folder. More specifically, ".." means "the directory one level above the current directory", "../.." means "the directory two levels above the current directory", and so on. For example, if the current directory is "/home/user/pictures", and you want to refer to "/home/top/data/file", you can express that as "../../top/data/file".

Given a String path, indicating the complete path to the file that needs to be referred to, and a String currentDir, indicating the current directory, return a String that contains the relative path to that file according to the above rules. You should choose the shortest of all possible relative paths (for example, if the current directory is "/home/user/pictures", you should use "../movies/title" and not "../../user/movies/title" as a pointer to "/home/user/movies/title").

Some files and/or directories may have coinciding names, but it is impossible to have two files or two directories or a file and a directory with the same name inside the same directory, so file and directory paths are not ambiguous. It is guaranteed that the given data describes a valid file and directory according to the above rules. In particular, they will not contradict - for example, path="/home/user/some" and currentDir="/home/user/some/other" are a contradiction, since it implies that a file and a directory both named "some" exist inside the directory "/home/user".

Definition

Class:	RelativePath
Method:	makeRelative
Parameters:	String, String
Returns:	String
Method signature:	String makeRelative(String path, String currentDir)
(be sure your method is public)

Notes

A file name never ends with the '/' character. A directory name never ends with the '/' character, with the exception of the root directory, which is specified as just "/".

Constraints

path and currentDir will each contain between 1 and 50 characters, inclusive.

Each character of path and currentDir will be '/', or a lowercase letter ('a'-'z').

path will contain a valid file path according to the above rules.

currentDir will contain a valid directory path according to the above rules.

path and currentDir will not contradict (see the last paragraph of the statement).

Examples

"/home/top/data/file"

"/home/user/pictures"

Returns: "../../top/data/file"

The example from the problem statement.

"/home/user/movies/title"

"/home/user/pictures"

Returns: "../movies/title"

And another one from the statement.

"/file"

"/"

Returns: "file"

Remember about the root directory.

"/a/b/a/b/a/b"

"/a/b/a/a/b/a/b"

Returns: "../../../../b/a/b"

Some file and directory names may be the same.

"/root/root/root"

"/root"

Returns: "root/root"

Some files and/or directories can be named "root" - but that doesn't make them root directories.

代码：

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class RelativePath {
public:
    string makeRelative(string, string);
};

string RelativePath::makeRelative(string path, string cD) {
    int sz1=path.size();
    int sz2=cD.size();
    int td1=0;
    int td2=0;
    int i;
    int cloc,cdepth=0,tmp;
    string ret="";
    for (i=0;i<sz1;i++) if (path[i]=='/') td1++;
    if (sz1==1) td1=0;
    for (i=0;i<sz2;i++) if (cD[i]=='/') td2++;
    if (sz2==1) td2=0;
    for (i=0;i<sz2;i++)
    {
        if (path[i]!=cD[i]) break;
        if (path[i]=='/') cdepth++;
    }
    if (i==sz2&&sz2<sz1&&path[sz2]!='/') cdepth--;
    if (i!=sz2) cdepth--;
    if (i==0||sz2==1) cdepth=0;
    for (i=0;i<td2-cdepth;i++) ret+="../";
    tmp=-1;cloc=0;
    for (i=0;i<sz1&&tmp<cdepth;i++)
    {
        if (path[i]=='/') tmp++;
        cloc=i;
    }
    ret+=path.substr(cloc+1);
    return ret;
}

//Powered by [KawigiEdit] 2.0!

51isoft 2008-11-13 20:37 发表评论

PKU2318 TOYS

51isoft — Thu, 18 Sep 2008 09:45:00 GMT

Description

Calculate the number of toys that land in each bin of a partitioned toy box.
Mom and dad have a problem - their child John never puts his toys away when he is finished playing with them. They gave John a rectangular box to put his toys in, but John is rebellious and obeys his parents by simply throwing his toys into the box. All the toys get mixed up, and it is impossible for John to find his favorite toys.

John's parents came up with the following idea. They put cardboard partitions into the box. Even if John keeps throwing his toys into the box, at least toys that get thrown into different bins stay separated. The following diagram shows a top view of an example toy box.

For this problem, you are asked to determine how many toys fall into each partition as John throws them into the toy box.

Input

The input file contains one or more problems. The first line of a problem consists of six integers, n m x1 y1 x2 y2. The number of cardboard partitions is n (0 < n <= 5000) and the number of toys is m (0 < m <= 5000). The coordinates of the upper-left corner and the lower-right corner of the box are (x1,y1) and (x2,y2), respectively. The following n lines contain two integers per line, Ui Li, indicating that the ends of the i-th cardboard partition is at the coordinates (Ui,y1) and (Li,y2). You may assume that the cardboard partitions do not intersect each other and that they are specified in sorted order from left to right. The next m lines contain two integers per line, Xj Yj specifying where the j-th toy has landed in the box. The order of the toy locations is random. You may assume that no toy will land exactly on a cardboard partition or outside the boundary of the box. The input is terminated by a line consisting of a single 0.

Output

The output for each problem will be one line for each separate bin in the toy box. For each bin, print its bin number, followed by a colon and one space, followed by the number of toys thrown into that bin. Bins are numbered from 0 (the leftmost bin) to n (the rightmost bin). Separate the output of different problems by a single blank line.

Sample Input

5 6 0 10 60 0
3 1
4 3
6 8
10 10
15 30
1 5
2 1
2 8
5 5
40 10
7 9
4 10 0 10 100 0
20 20
40 40
60 60
80 80
5 10
15 10
25 10
35 10
45 10
55 10
65 10
75 10
85 10
95 10
0

Sample Output

0: 2
1: 1
2: 1
3: 1
4: 0
5: 1
0: 2
1: 2
2: 2
3: 2
4: 2

Hint

As the example illustrates, toys that fall on the boundary of the box are "in" the box.

Source

Rocky Mountain 2003

题意：给出一个盒子以及N条线，把这个格子划分成N+1部分。然后给出一些坐标，统计这些坐标落在各个格子的次数。

线性规划，左上顶点一定是在每根线的左手边。这样就可以从左到右算出每根线的方程后，拿顶点坐标和当前坐标代入后计算其正负性，第一个同号的时刻就是他所在的格子。

#include <stdio.h>
#include <string.h>

int n,m,x1,y1,x2,y2,x,y;
int loc[5000][2];
double a[5000],b[5000];
int num[5001];

int i,j;
double v1,v2;
bool pd;

int main()
{
    while (scanf("%d",&n)&&n)
    {
        if (m!=0) printf("\n");
        memset(num,0,sizeof(num));
        scanf ("%d %d %d %d %d",&m,&x1,&y1,&x2,&y2);
        for (i=0;i<n;i++)
        {
            scanf("%d %d",&loc[i][0],&loc[i][1]);
            a[i]=double(loc[i][1]-loc[i][0])/double(y1-y2);
            b[i]=-a[i]*y1-loc[i][0];
        }
        for (i=0;i<m;i++)
        {
            scanf("%d %d",&x,&y);
            pd=false;
            for (j=0;j<n;j++)
            {
                if (x>loc[j][0]&&x>loc[j][1]) continue;
                v1=x1+a[j]*y1+b[j];
                v2=x+a[j]*y+b[j];
                if (v1*v2>0) {
                    pd=true;
                    num[j]++;
                    break;
                }
            }
            if (!pd) num[n]++;
        }
        for (i=0;i<=n;i++)
            printf("%d: %d\n",i,num[i]);
    }
    return 0;
}

51isoft 2008-09-18 17:45 发表评论

PKU1077 Eight

51isoft — Thu, 18 Sep 2008 09:31:00 GMT

摘要: Description The 15-puzzle has been around for over 100 years; even if you don't know it by that name, you've seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, a... 阅读全文

51isoft 2008-09-18 17:31 发表评论

HDOJ2185 Chess

51isoft — Thu, 18 Sep 2008 09:20:00 GMT

Problem Description

The Association of Chess Monsters (ACM) is planning their annual team match up against the rest of the world. The match will be on 30 boards, with 15 players playing white and 15 players playing black. ACM has many players to choose from, and they try to pick the best team they can. The ability of each player for playing white is measured on a scale from 1 to 100 and the same for playing black. During the match a player can play white or black but not both. The value of a team is the total of players' abilities to play white for players designated to play white and players' abilities to play black for players designated to play black. ACM wants to pick up a team with the highest total value.

Input

Input consists of a sequence of lines giving players' abilities. Each line gives the abilities of a single player by two integer numbers separated by a single space. The first number is the player's ability to play white and the second is the player's ability to play black. There will be no less than 30 and no more than 1000 lines on input.

Output

Output a single line containing an integer number giving the value of the best chess team that ACM can assemble.

Sample Input

Sample Output

题意大概是在一堆人里选择30个人（一半执黑，另一半执白），使棋力和最大。

算法：DP。f[i][j][k]表示前i个人中选j个执黑k个执白的最大棋力。

#include <stdio.h>
#include <string.h>

int f[2000][16][16];
int a[2000][2];
int n;

int i,j,k;

int main()
{

    n=0;
    while (scanf("%d %d",&a[n][0],&a[n][1])!=EOF) n++;
    for (i=1;i<16;i++) f[0][0][i]=a[0][1];
    for (i=1;i<16;i++) f[0][i][0]=a[0][0];
    for (i=1;i<n;i++)
    {
        for (j=0;j<16;j++)
        {
            for (k=0;k<16;k++)
            {
                if (j==0) f[i][1][k]=f[i-1][0][k]+a[i][0];
                if (k==0) f[i][j][1]=f[i-1][j][0]+a[i][1];
                if (j!=0)
                    if (f[i-1][j-1][k]+a[i][0]>f[i-1][j][k])
                    {
                        if (f[i][j][k]<f[i-1][j-1][k]+a[i][0]) f[i][j][k]=f[i-1][j-1][k]+a[i][0];
                    }
                    else if (f[i][j][k]<f[i-1][j][k]) f[i][j][k]=f[i-1][j][k];
                if (k!=0)
                    if (f[i-1][j][k-1]+a[i][1]>f[i-1][j][k])
                    {
                        if (f[i][j][k]<f[i-1][j][k-1]+a[i][1]) f[i][j][k]=f[i-1][j][k-1]+a[i][1];
                    }
                    else if (f[i][j][k]<f[i-1][j][k]) f[i][j][k]=f[i-1][j][k];
            }
        }
    }
    printf("%d\n",f[n-1][15][15]);
    return 0;
}

51isoft 2008-09-18 17:20 发表评论