15年-ICPC长春-网络赛

ID	name	status	one word
POJ 5437	Alisha’s Party	赛后AC、	优先队列，模拟。对时间t排序
POJ 5438	Ponds	赛后AC	循环链表
POJ 5439	Aggregated Counting
POJ 5440	Clock Adjusting
POJ 5441	Travel	赛后AC	并查集+离线化。注音可以休息、
POJ 5442	Favorite Donut
POJ 5443	The Water Problem	题如其名，水题。	..........就是水。
POJ 5444	Elven Postman	赛后AC	二叉树建和遍历。
POJ 5445	Food Problem
POJ 5446	Unknown Treasure
POJ 5447	Good Numbers
POJ 5448	Marisa’s Cake
POJ 5449	Robot Dog

很多题就是想不到思路。其实是可以做的。第一场只过了1道。。。。。。。。。人艰不拆。。。。。。

poj 5437

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

struct Node {
    char name[210];
    int val;
    int t;
    bool operator < (const Node &a) const {
       if (a.val != val)
        return a.val > val;
       else return a.t < t;
    }
}node[150010];

struct Open {
    int t, per;
}open[150010];

bool cmp(Open a, Open b) {
    return a.t < b.t;
}

Node rem[150010];
priority_queue<Node>que;

int main() {
    int k, m, q;
    int t;
    scanf("%d", &t);
    while (t--) {
        memset(open, 0, sizeof(open));
        memset(rem, 0, sizeof(rem));
        scanf("%d%d%d", &k, &m, &q);
        for (int i=0; i<k; ++i) {
            scanf("%s%d", node[i].name, &node[i].val);
            node[i].t = i;
        }

        for (int i=0; i<m; ++i) {
            scanf("%d%d", &open[i].t, &open[i].per);
        }
        while (!que.empty()) {
            que.pop();
        }
        sort(open, open+m, cmp);

        int cnt = 0;
        int t = 0;
        for (int i=0; i<m; ++i) {
            if (t < open[i].t) {
                for (int j=t; j < open[i].t; ++j) {
                    que.push(node[j]);
                }
                t = open[i].t;
            }
            int num = 0;
            while(num < open[i].per && !que.empty() && cnt < k) {
                rem[cnt++] = que.top();
                num++;
                que.pop();
            }
        }

         if (open[m-1].t < k) {
            for (int i=open[m-1].t; i<k; ++i) {
                que.push(node[i]);
            }
         }

         while(!que.empty() && cnt < k) {
            rem[cnt++] = que.top();
            que.pop();
         }

         int a;
         for (int i=0; i<q; ++i) {
            scanf("%d", &a);
            if (i == 0)
            printf("%s", rem[a-1].name);
            else printf(" %s", rem[a-1].name);
         }
         printf("
");
    }
    return 0;
}

View Code

poj 5438

#include <queue>
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

#define maxn 100000+50  // 边的个数
#define maxm 10000+50  // 节点个数
int t, p, m, a, b;

int val[maxm];
int head[maxm];
int deg[maxm];
bool vis[maxm];
long long ans, temp;
int num;

struct Edge {
  int v, next;
}edge[maxn];

int totEdge;
queue<int>que;

void addEdge(int a, int b) {
   edge[totEdge].v = b;
   edge[totEdge].next = head[a];
   head[a] = totEdge++;
}

void init() {
   memset(head, -1, sizeof(head));
   memset(edge, 0, sizeof(edge));
   memset(val, 0, sizeof(val));
   memset(vis, 0, sizeof(vis));
   memset(deg, 0, sizeof(deg));
   totEdge = 0;
   ans = 0;
   while(!que.empty())
    que.pop();
}


void topSort() {
    for (int i=1; i<=p; ++i) {
        if (deg[i] == 0)
            vis[i] = true;
        if (deg[i] == 1) {
            vis[i] = true;
            que.push(i);
        }
    }

    while(!que.empty()) {
        int top = que.front();
        //cout << top << "===
";
        que.pop();
        for (int i=head[top]; i!=-1; i=edge[i].next) {
            int v = edge[i].v;
            //cout << v << "----
";
            deg[v]--;
            if (!vis[v]) {
                if (deg[v] == 0)
                    vis[v] = true;
                else if (deg[v] == 1) {
                    vis[v] = true;
                    que.push(v);
                }
            }
        }
        //cout << "***
";
    }
}

void Dfs(int u, int fa) {
//    cout << val[u] << "===" << u << endl;;
    num += 1;
    temp += val[u];
    vis[u] = true;
    for (int i=head[u]; i!=-1; i=edge[i].next) {
        int v = edge[i].v;
        if (!vis[v] && v != fa) {
            Dfs(v, u); // u开头的这条链上的最后一个子节点，如果是u ,就说明到环的开始了。
        }
    }
}

int main() {
   cin >> t;
   while (t--) {
      init();
      cin >> p >> m;

      for (int i=1; i<=p; ++i) {
        cin >> val[i];
      }

      for (int i=0; i<m; ++i) {
        cin >> a >> b;
        addEdge(a, b);
        addEdge(b, a);
        deg[a]++;
        deg[b]++;
      }
      topSort();
      for (int i=1; i<=p; ++i) {
        num = 0;
        temp = 0;
        if (!vis[i])
        Dfs(i, 0);
        if (num & 1) {
            ans += temp;
        }
      }
      cout << ans << endl;
   }
   return 0;
}

View Code

poj 5441

// 先对边按权值排序，然后对询问按照权值排序。
// 每次在满足当前条件下，遍历。把两个端点所在的集合
// 并起来。此时增加的pair数就是2*num1*num2.
// 因为已经对询问按照权值排序。所以后面的集合一定会覆盖前面的、
// 所以只要一直询问下去。记录就可以了。
// 有一点并查集离线查询的地方。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;

#define maxn 201000  // 节点数
#define maxm 51000  // 询问数
#define tot 1001000  // 边数

int t, n, m, q;
int num[maxn]; // 维护每个节点当前所在集合的节点个数、
int ans[maxm];  // 保存每次询问的结果、
int fa[maxn]; // 并查集

struct Node {
    int st, ed, dis;
}node[tot];

int cmp(Node a, Node b) {
    return a.dis < b.dis;
}

struct Querry{
  int id, ask;
}que[maxm];

void init() {
   for (int i=1; i<=n; ++i) {
       fa[i] = i;
       num[i] = 1;
   }
   memset(ans, 0, sizeof(ans));
}

int cmp2(Querry a, Querry b) {
    return a.ask < b.ask;
}

int find_(int i) {
    if (fa[i] == i) return i;
    else return fa[i] = find_(fa[i]);
}

int main() {
  int a, b, d;
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d%d", &n, &m, &q);
    init();
    for (int i=1; i<=m; ++i) {
        scanf("%d%d%d", &a, &b, &d);
        node[i].st = a;
        node[i].ed = b;
        node[i].dis = d;
    }
    sort(node+1, node+1+m, cmp);
    for (int i=0; i<q; ++i) {
        scanf("%d", &que[i].ask);
        que[i].id = i+1;
    }
    sort(que, que+q, cmp2);

    int now = 1;
    int tempans = 0;
    int flag = 0;

    for (int i=0; i<q; ++i) {
       flag = que[i].id;
       for(; node[now].dis<=que[i].ask && now<=m; now++) {
            int t1 = node[now].st;
            int t2 = node[now].ed;
            if (t1 == t2) {
                continue;
            }
            if (find_(t1) == find_(t2)) {
                continue;
            }
            else if (find_(t1) != find_(t2)) {
                tempans += 2*num[find_(t1)]*num[find_(t2)];
                num[find_(t1)] += num[find_(t2)];
                fa[find_(t2)] = find_(t1);
            }
        }
       ans[flag] += tempans;
    }
    for (int i=1; i<=q; ++i) {
        printf("%d
", ans[i]);
    }
  }
  return 0;
}

View Code

poj 5444

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

struct Tree {
   int l, r;
}node[1010];

bool flag;

void init() {
   memset(node, 0, sizeof(node));
}

void addNode(int u, int c) {
    if (node[u].l==0 && u<c) {node[u].l = c;return;}
    else if (node[u].r==0 && u>c) {node[u].r = c;return;}
    else if (u<c) addNode(node[u].l, c);
    else addNode(node[u].r, c);
}

void find(int u, int c) {
   if (u == c)
    return;
   else if (u<c) {
    cout << 'W';
    find(node[u].l, c);
   }
   else if (u > c) {
    cout << 'E';
    find(node[u].r, c);
   }
}

int main() {
   int t, n, q, r, c;
   cin >> t;
   while(t--) {
    init();
    cin >> n;
    cin >> r;
    node[r].l = node[r].r = 0;

    for (int i=1; i<n; ++i) {
        cin >> c;
        addNode(r, c);
    }
    cin >> q;
    for (int i=0; i<q; ++i) {
        flag = true;
        cin >> c;
        find(r, c);
        cout << endl;
    }
   }
   return 0;
}

View Code