Unlimited Code Works

这一题多数用的是线段树+离散化，但是今天正好看到矩阵切割，所以就用矩阵切割试了一下。

参考了 http://www.2cto.com/kf/201209/156711.html 的代码，进行了一些修改，个人感觉更简洁且比较容易理解。

#include<iostream>
#include<stack>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<cmath>
using namespace std;
const int M = 100000;
const int N = 10000;

struct line
{
    int l, r;
    int color;
    line(int ll = 0, int rr = 0, int c = 0) : l(ll), r(rr), color(c) {}
}post[M], cur;
int tot;

bool used[N];

inline bool cross(const line& l1, const line& l2)
{
    return !(
             (l1.l > l2.r)
             || (l1.r < l2.l));
}

inline void add(const line& t)
{
    post[tot++] = t;
}

void cut(const line& t)
{
    if(t.l < cur.l)
    {
        add(line(t.l, cur.l-1, t.color));
    }
    if(t.r > cur.r)
    {
        add(line(cur.r+1, t.r, t.color));
    }
}


int main(int argc, char *argv[])
{
#ifdef ACM_LOCAL // Local
    freopen("in", "r", stdin);
#else
    #ifndef  ONLINE_JUDGE // not HDOJ / POJ
    freopen("humble.in", "r", stdin);
    freopen("humble.out", "w", stdout);
    #endif
#endif

    int ncase;
    scanf("%d", &ncase);
    while(ncase--)
    {
        tot = 0;
        int color = 0;
        int n;

        scanf("%d", &n);
        while(n--)
        {
            scanf("%d %d", &cur.l, &cur.r);
            cur.color = color++;

            // 倒序，否则在cut操作中增加的线段也会再被检查一遍
            for(int i = tot-1; i>= 0; i--)
            {
                if(cross(post[i], cur))
                {
                    cut(post[i]);
                    post[i] = post[--tot];
                }
            }
            add(cur);
        }

        memset(used, false, sizeof(used));
        int cnt = 0;
        for(int i = 0; i!= tot; i++)
        {
            if(!used[post[i].color])
            {
                used[post[i].color] = true;
                cnt++;
            }
        }

        printf("%d\n", cnt);
    }

    return 0;
}

BTW，按说注释中提到的那个循环改成顺序的应该也可以的，只是会慢一些，但实际提交了却是RE。目前还不清楚原因。

标准的最小生成树，用了Kruskal算法，写了一个可以以后用的并查集类。

/*
ID: xjtuacm1
PROG: agrinet
LANG: C++
*/
#include<iostream>
#include<stack>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<cmath>
using namespace std;
const int MAXDIS = 100000 + 10;
const int N = 100;
const int M = N * (N - 1) / 2;

int n, m;
int e;
int u[M], v[M], w[M];

int wr[M];

void initGraph()
{
    e = 0;
}

void addEdge(int x, int y, int cost)
{
    u[e] = x;
    v[e] = y;
    w[e++] = cost;
}

class UnionFind
{
    int n;
    int fa[N];
    int r[N];

public:
    UnionFind(int nn)
        : n(nn)
    {
        init();
    }

    void init()
    {
        memset(r, 0, sizeof(r));
        for(int i = 0; i!= n; i++)
            fa[i] = i;
    }

    int Find(int x)
    {
        if(x != fa[x])
        {
            fa[x] = Find(fa[x]);
        }
        return fa[x];
    }

    void Union(int x, int y)
    {
        Link(Find(x), Find(y));
    }
private:
    void Link(int x, int y)
    {
        if(r[x] > r[y])
        {
            fa[y] = x;
        }
        else
        {
            fa[x] = y;
            if(r[x] == r[y])
                r[y]++;
        }
    }
};

bool cmp(int a, int b)
{
    return w[a] < w[b];
}

int kruskal()
{
    UnionFind uf(n);
    for(int i = 0; i!= m; i++)
        wr[i] = i;
    int ret = 0;

    sort(wr, wr+m, cmp);

    for(int i = 0; i!= m; i++)
    {
        int ed = wr[i];
        if(uf.Find(u[ed]) != uf.Find(v[ed]))
        {
            ret += w[ed];
            uf.Union(u[ed], v[ed]);
        }
    }

    return ret;
}

int main(int argc, char *argv[])
{
#ifdef ACM
    freopen("in", "r", stdin);
#else
    freopen("agrinet.in", "r", stdin);
    freopen("agrinet.out", "w", stdout);
#endif // ACM

    scanf("%d", &n);
    m = n * (n - 1) / 2;
    for(int i = 0; i!= n; i++)
        for(int j = 0; j!= n; j++)
        {
            int t;
            scanf("%d", &t);
            if(i > j)
                addEdge(i, j, t);
        }

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

    return 0;
}

floyd + dfs染色。

重点是添加新的边之后的field的直径等于

1.原来两个field的直径 2.新的边长加从它的两个端点可以延伸的最大长度

这其中的最大值。

/*
ID: xjtuacm1
PROG: cowtour
LANG: C++
*/
#include<iostream>
#include<stack>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<cmath>
using namespace std;
const int N = 150;
const double DINF = 1e30;

struct Point
{
    int x, y;
} pes[N];

int adj[N][N];
int color[N];

double dis[N][N];
double maxDis[N];
double dia[N];
int n;

void floodfill(int cur, int tag)
{
    color[cur] = tag;
    for(int i = 0; i!= n; i++)
    {
        if(adj[cur][i] && color[i] == -1)
        {
            floodfill(i, tag);
        }
    }
}

int find_component()
{
    int cnt = 0;
    for(int i = 0; i < n; i++)
        if(color[i] == -1)
            floodfill(i, cnt++);
    return cnt;
}

double dist(int a, int b)
{
    if(!adj[a][b])
        return DINF;

    return sqrt((pes[a].x - pes[b].x) * (pes[a].x - pes[b].x)
                + (pes[a].y - pes[b].y) * (pes[a].y - pes[b].y));
}

void floyd()
{
    for(int i = 0; i!= n; i++)
        for(int j = 0; j!= n; j++)
            dis[i][j] = dist(i, j);

    for(int k = 0; k!= n; k++)
        for(int i = 0; i!= n; i++)
            for(int j = 0; j!= n; j++)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}

int main(int argc, char *argv[])
{
#ifdef ACM
    freopen("in", "r", stdin);
#else
    freopen("cowtour.in", "r", stdin);
    freopen("cowtour.out", "w", stdout);
#endif // ACM

    scanf("%d\n", &n);
    for(int i = 0; i!= n; i++)
    {
        scanf("%d %d\n", &pes[i].x, &pes[i].y);
    }
    for(int i = 0; i!= n; i++)
    {
        char line[N + 1];
        gets(line);
        for(int j = 0; j!= n; j++)
        {
            adj[i][j] = (line[j] == '0'? 0 : 1);

            dis[i][j] = dist(i, j);

        }
    }

    memset(color, -1, sizeof(color));
    int ncom = find_component();
    floyd();

    for(int i = 0; i!= ncom; i++)
        dia[i] = 0;

    for(int i = 0; i!= n; i++)
    {
        maxDis[i] = 0;
        for(int j = 0; j!= n; j++)
        {
            if(i!= j && color[i] == color[j])
            {
                maxDis[i] = max(maxDis[i], dis[i][j]);
            }
        }

        dia[color[i]] = max(dia[color[i]], maxDis[i]);
    }

    double diameter = DINF;
    for(int i = 0; i!= n; i++)
        for(int j = 0; j!= n; j++)
    {
        if(color[i] == color[j])
            continue;

        double d1 = 0;
        double d2 = 0;
        for(int k = 0; k!= n; k++)
        {
            if(i != k && color[i] == color[k])
                d1 = max(d1, dis[i][k]);

            if(j != k && color[j] == color[k])
                d2 = max(d2, dis[j][k]);
        }

        double dist = sqrt( (pes[i].x - pes[j].x) * (pes[i].x - pes[j].x)
                           + (pes[i].y - pes[j].y) * (pes[i].y - pes[j].y) );

        diameter = min(diameter,
                       max(dist + d1 + d2,
                           max(dia[color[i]], dia[color[j]])));
    }

    printf("%.6lf\n", diameter);

    return 0;
}

带权边的Dijkstra

/*
ID: xjtuacm1
PROG: comehome
LANG: C++
*/
#include<iostream>
#include<stack>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
const int INF = 0x3f3f3f3f;
const int M = 10000;
const int N = 52;

// Graph structure
int n;
int to[M], nxt[M], head[N];
int w[M];
bool vis[N];
int e;
int dist[N]; // Distance array
struct cmp
{
    bool operator() (int a, int b)
    {
        return dist[a] > dist[b];
    }
};

void init()
{
    memset(vis, false, sizeof(vis));
    memset(head, -1, sizeof(head));
    e = 0;
}
void addEdge(int u, int v, int c)
{
    to[e] = v;
    nxt[e] = head[u];
    w[e] = c;
    head[u] = e++;
}

void addBiEdge(int u, int v, int c)
{
    addEdge(u, v, c);
    addEdge(v, u, c);
}

void dijkstra(int src)
{
    // Reset distance array
    memset(vis, false, sizeof(vis));
    for(int i = 0; i!= n; i++)
        dist[i] = INF;

    priority_queue<int, vector<int>, cmp> que;
    vis[src] = true;
    dist[src] = 0;
    que.push(src);
    int pnt = src;
    for(int i = 1; i!=n; i++)
    {
        for(int j = head[pnt]; j!= -1; j = nxt[j])
        {
            int v = to[j];
            if(!vis[v] && dist[pnt] + w[j] < dist[v])
            {
                dist[v] = dist[pnt] + w[j];
                que.push(v);
            }
        }
        while(!que.empty() && vis[que.top()])
            que.pop();
        if(que.empty())
            break;

        pnt = que.top(); que.pop();
        vis[pnt] = true;
    }
}

set<char> cows;
int r[N];
bool indirectCmp(int a, int b)
{
    return dist[a] < dist[b];
}

int toIdx(char ch)
{
    if(ch != tolower(ch))
        return ch - 'A';
    else
        return ch - 'a' + 26;
}
char toChar(int idx)
{
    if(idx < 26)
        return idx + 'A';
    else
        return idx - 26 + 'a';
}

int main(int argc, char *argv[])
{
    freopen("comehome.in", "r", stdin);
#ifndef USACO
    freopen("comehome.out", "w", stdout);
#endif // USACO

    int p;
    scanf("%d\n", &p);

    n = N;
    init();

    while(p--)
    {
        char f, t;
        int c;
        scanf("%c %c %d\n", &f, &t, &c);
        if(f == t)
            continue;

        bool flag = false;
        for(int edge = head[toIdx(f)]; edge != -1; edge = nxt[edge])
            if(to[edge] == (toIdx(t)))
        {
            w[edge] = min(w[edge], c);
            flag = true;
            break;
        }
        for(int edge = head[toIdx(t)]; edge != -1; edge = nxt[edge])
            if(to[edge] == (toIdx(f)))
        {
            w[edge] = min(w[edge], c);
            flag = true;
            break;
        }
        if(flag)
            continue;

        addBiEdge(toIdx(f), toIdx(t), c);
    }

    dijkstra(toIdx('Z'));

    for(int i = 0; i!= n; i++)
        r[i] = i;

    sort(r, r+n, indirectCmp);
    for(int i = 1; i!= n; i++)
    {
        if(r[i] < 26)
        {
            printf("%c %d\n", toChar(r[i]), dist[r[i]]);
            break;
        }
    }

    return 0;
}

题意是给你一个迷宫，有两个出口，找出最长的从迷宫内任意一点到出口的最短距离。

一开始想到的是dijkstra，在两个出口分别运行一次，取每个点到两个出口距离中最短的，再去其中最大的即可。

然后想到其实分别从两个出口作BFS，标注每个点的距离即可。

/*
ID: xjtuacm1
PROG: maze1
LANG: C++
*/
#include<iostream>
#include<stack>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
const int W = 38;
const int H = 100;
const int INF = 0x3f3f3f3f;

const int dir[4] = { 1, 2, 4, 8};

int stage[H][W];
int color[H][W];
int h, w;

struct Point
{
    int x, y;
    Point(int xx = 0, int yy = 0) :x(xx), y(yy) {}
    bool operator<(const Point& rhs) const
    {
        if(x == rhs.x)
            return y < rhs.y;
        return x < rhs.x;
    }

    bool connect(int d) const
    {
        return !(stage[x][y] & dir[d]);
    }

    Point next(int d) const
    {
        switch(dir[d])
        {
        case 1:
            return Point(x, y-1);
        case 2:
            return Point(x-1, y);
        case 4:
            return Point(x, y+1);
        case 8:
            return Point(x+1, y);
        }
        return Point();
    }
};

void init()
{
    for(int i = 0; i!= h; i++)
        for(int j = 0; j!= w; j++)
        {
            stage[i][j] = 0xF;
            color[i][j] = INF;
        }
}

void addEdge(const Point& u, const Point& v)
{
    const Point& a = u<v ? u : v;
    const Point& b = u<v ? v : u;
    if(a.x == b.x)
    {
        stage[a.x][a.y] ^= 1<<2;
        stage[b.x][b.y] ^= 1;
    }
    if(a.y == b.y)
    {
        stage[a.x][a.y] ^= 1<<3;
        stage[b.x][b.y] ^= 1<<1;
    }
}

void bfs(const Point& src)
{
    color[src.x][src.y] = 1;
    queue<pair<Point, int> > que;
    que.push(make_pair(src, 1));

    while(!que.empty())
    {
        Point pt = que.front().first;
        int dis = que.front().second;
        que.pop();

        for(int i = 0; i!= 4; i++)
        {
            if(pt.connect(i))
            {
                Point nxt = pt.next(i);
                if(dis+1 < color[nxt.x][nxt.y])
                {
                    color[nxt.x][nxt.y] = dis + 1;
                    que.push(make_pair(nxt, color[nxt.x][nxt.y]));
                }
            }
        }
    }
}

int main(int argc, char *argv[])
{
    freopen("maze1.in", "r", stdin);
#ifndef USACO
    freopen("maze1.out", "w", stdout);
#endif // USACO


    scanf("%d %d", &w, &h); getchar();
    init();

    Point extCell[2];
    int extCnt = 0;

    char line[2*W + 2];

    // first line
    gets(line);
    for(int i = 0; i!= strlen(line); i++)
    {
        if(line[i] == ' ')
            extCell[extCnt++] = Point(0, (i - 1) / 2);
    }
    for(int i = 0; i!= 2 * h - 1; i++)
    {
        gets(line);
        if(i & 1)
        {
            for(int j = 0; j != strlen(line); j++)
            {
                if(line[j] == ' ')
                {
                    addEdge(Point((i-1)/2, (j-1)/2),
                            Point((i+1)/2, (j-1)/2) );
                }
            }
        }
        else
        {
            if(line[0] == ' ')
            {
                extCell[extCnt++] = Point(i / 2, 0);
            }
            if(line[strlen(line) - 1] == ' ')
            {
                extCell[extCnt++] = Point(i / 2, w - 1);
            }
            for(int j = 2; j< strlen(line) - 1; j+= 2)
            {
                if(line[j] == ' ')
                {
                    addEdge(Point(i/2, j/2 - 1),
                            Point(i/2, j/2) );
                }
            }
        }
    }
    // last line
    gets(line);
    for(int i = 0; i!= strlen(line); i++)
    {
        if(line[i] == ' ')
            extCell[extCnt++] = Point(h-1, (i - 1) / 2);
    }

    bfs(extCell[0]);
    bfs(extCell[1]);

    int m = 0;
    for(int i = 0; i!= h; i++)
        for(int j = 0; j!= w; j++)
        m = max(m, color[i][j]);

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


    return 0;
}

扩展的并查集，参考了以下两个，结合了一下，然后对Query的部分有一些改动，主要是用了map来判断出现次数的奇偶

• http://www.cppblog.com/Yuan/archive/2010/09/02/125667.html?opt=admin
• http://blog.csdn.net/acm_cxlove/article/details/8101710

$X_1...X_{n-1}$，这是题中所说的未给出的$n$个数，维护一个带权的并查集，每个点有一个权$w$

保证有w[k] = Xk ^ Xfa[k]，Xfa[k]表示Xk的父亲。

对于

牛和农夫按照固定的走法在10x10的地图中走，每分钟走一步，求经过几分钟相遇。永远不能相遇输出0。

纯模拟的题。

判断永远不能相遇的方法是如果遇到了一个先前的状态，那么肯定存在循环，必定不能相遇。

程序中把状态表示为牛和农夫的位置以及面向的方向，通过map判断是否遇到重复状态，因为map中不存在的键会有默认值，对于bool来说就是false。

一点点空间的优化是地图只用存一份，牛和农夫不显示在地图上，尽通过状态里的点间接表示。

恩，暴力解决。

参考了 http://haipeng31.blog.163.com/blog/static/105623344201011984618863/，不过很可惜原始文章已经不在了。

主要是changed变量的使用。

/*
ID: xjtuacm1
PROG: concom
LANG: C++
*/
#include<iostream>
#include<stack>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;

const int CMAX = 100 + 1;

int comp[CMAX][CMAX];
bool owns[CMAX][CMAX];

int main(int argc, char *argv[])
{
    freopen("concom.in", "r", stdin);
#ifndef USACO
    freopen("concom.out", "w", stdout);
#endif // USACO

    memset(comp, 0, sizeof(comp));
    memset(owns, false, sizeof(owns));

    int n;
    scanf("%d", &n);
    while(n--)
    {
        int i, j;
        scanf("%d %d", &i, &j);
        scanf("%d", &comp[i][j]);
    }

    for(int i = 0; i!= CMAX; i++)
        owns[i][i] = true; // First condition

    for(int i = 0; i!= CMAX; i++)
        for(int j = 0; j!= true; j++)
            owns[i][j] = (comp[i][j] >= 50); // Second condition. This can be merged with third condition.

    bool changed = true;
    while(changed)
    {
        changed = false;
        for(int i = 1; i!= CMAX; i++)
        {
            for(int j = 1; j!= CMAX; j++)
            {
                if(!owns[i][j])
                {
                    int sum = 0;
                    for(int k = 1; k!= CMAX; k++)
                    {
                        if(owns[i][k])
                            sum += comp[k][j];
                    }

                    if(sum >= 50)
                    {
                        owns[i][j] = true;
                        changed = true;
                    }
                }
            }
        }
    }

    for(int i = 1; i!= CMAX; i++)
    {
        for(int j = 1; j!= CMAX; j++)
        {
            if(owns[i][j] && i!= j)
                printf("%d %d\n", i, j);
        }
    }

    return 0;
}

BTW，发现现在碰到暴力的题都有点儿不敢做了。。= =

题目意思就是给定1～200个短的Primitive (长度1～10)，以及一个长字符串 (长度200,000以内)，需要找出由这些Primitive任意重复连接形成的后者的最长前缀。

DP + Trie

设长字符串为seq，基本思路是若seq[0…i]是满足要求的前缀，那么seq[0…i+len]也是满足要求的前缀，len是各个Primitive的长度。

然后就是用Trie优化一下判断seq[i…i+len]是否在Primitive集合的过程。

/*
ID: xjtuacm1
PROG: prefix
LANG: C++
*/
#include<iostream>
#include<stack>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
using namespace std;

const int PRISIZE = 205;
const int PRILEN = 10 + 1;
const int SEQLEN = 200005;
const int LINELEN = 76 + 2;

struct _trie
{
    int next[26];
    int cnt;
} trie[PRISIZE * PRILEN];
int trieNodeCnt;

int trieInit()
{
    memset(trie, 0, sizeof(trie));
    trieNodeCnt = 1;

    return 0; // trie tree's root
}

void trieAdd(int root, const char *str)
{
    int p = root;
    while(*str)
    {
        if(trie[p].next[*str - 'A'] == 0)
        {
            trie[p].next[*str - 'A'] = trieNodeCnt++;
        }
        p = trie[p].next[*str - 'A'];
        str++;
    }
    trie[p].cnt += 1;
}

bool trieSearch(int root, const char* str, int len)
{
    int p = root;
    for(int i = 0; i!= len; i++)
    {
        if(trie[p].next[str[i] - 'A'] == 0)
            return false;

        p = trie[p].next[str[i] - 'A'];
    }

    return trie[p].cnt > 0;
}

char seq[SEQLEN];
int seqlen = 0;
bool reach[SEQLEN]; // reach[i] =  if seq[0...i) (length = i) can be composed from primitives.

int main(int argc, char *argv[])
{
    freopen("prefix.in", "r", stdin);
#ifndef USACO
    freopen("prefix.out", "w", stdout);
#endif // USACO

    int root = trieInit(); // root = 0
    memset(reach, false, sizeof(reach));

    char temp[PRILEN];
    for(int i = 0; i!= PRISIZE; i++)
    {
        scanf("%s", temp);
        if(temp[0] == '.')
            break;

        trieAdd(root, temp);
    }

    while(true)
    {
        scanf("%s", seq + seqlen);
        int len = strlen(seq + seqlen);
        if(len == 0)
            break;

        seqlen += len;
    }

    for(int i = 1; i!= PRILEN; i++)
    {
        reach[i] = trieSearch(root, seq, i);
    }

    for(int i = 0; i!= seqlen; i++)
    {
        if(reach[i])
        {
            for(int j = 1; j!= PRILEN; j++)
            {
                if(trieSearch(root, seq + i, j))
                    reach[i + j] = true;
            }
        }
    }

    for(int i = seqlen ; i != 0; i--)
    {
        if(reach[i])
        {
            printf("%d\n", i);
            return 0;
        }
    }

    printf("0\n");
    return 0;
}

• 经常在网上看到i18n和l10n的说法，于是很好奇它们的意思
  • i18n是internationalization (国际化)的缩写,首位的i和末尾的n之间有18个字母,所以简写为i18n
  • 同理l10n是localization (区域化)的缩写