OIers...

http://bbs.mydrs.org/dispbbs.asp?BoardID=13&ID=4986

 小议竞赛的准备和考试技巧
1、良好的心态。无论竞赛多么重要，都不要在考试的时候考虑考试之前或以后的事，这很重要......
2、充足的睡眠和营养。竞赛之前睡好觉，吃好饭，多吃甜食（据我们老师说在吃甜食后15分钟和2小时会各出现一次血糖高峰，会有比较好的竞技状态）。还有，宁可撒尿也不要口渴......口渴会严重影响思路......而尿素有兴奋作用，有利无害......
3、正确的时间安排。一般来说应该先想完所有的题再开始做，但有的题想不出来的时候一定要给想出来的题留出时间。
4、算法的学习。一般的DFS/BFS、贪心、各种DP、二分法、排序、lr论文中的各种奇特算法、最短路、最长路、图的DFS/BFS、最大匹配，最大最小匹配、最佳匹配、差分限制系统、最长不xx子序列、高斯消元、数论算法......
5、数据结构的学习。Hash、并查集、邻接表、边表、堆、树状数组和线段树及它们的多维形式、链表、单词查找树......
6、关于混分：超时的搜索/DP往往能比错误的贪心得到更多的分。
7、数学很重要。比如母函数......
8、专用的方法胜于通用的方法。
9、好的题目往往不能直接用经典算法解决。
10、真正难题的标程往往很短。
11、如果n很大，用汇编写的O(n^2)的程序绝对不如用QB写的O(n)的程序快。
12、如果n很小，利用压缩存储提高速度的O(n^2)的算法有可能比一般的O(n)算法快。
13、如果一个数学问题很复杂，那么看结果找规律有可能比数学推导快。
14、不要总把logn忽略掉。
15、即使是多项式算法，有时也可以加入很有效的剪枝。
16、做一道好题胜过做n道烂题，但如果不做烂题，可能会影响做好题的速度。

Conversation with qq-XXXXXXat 2005-02-13 21:23:24 on 214941247 (qq)

(21:16:05) SwEtDrm*ToMy: 通读一遍算法导论，很重要。
(21:16:05) charles: rpz <自动回复>: 抱歉，我现在不在。请稍候再与我联系。
(21:16:22) SwEtDrm*ToMy: dp应该很熟练了，包括差分约束系统
(21:16:39) SwEtDrm*ToMy: 和四边形不等式
(21:16:56) SwEtDrm*ToMy: 串匹配：KMP
(21:18:01) SwEtDrm*ToMy: 数论方面，求最大公约数，解模线性方程（组）
(21:18:50) SwEtDrm*ToMy: 一种非常非常重要的数据结构：堆；以及堆排序
(21:19:15) SwEtDrm*ToMy: 堆的应用：Dijkstra和Prim
(21:20:04) SwEtDrm*ToMy: 还有非常非常重要的并查集（DisjointSet），以及它的变形和应用，如Kruskal
(21:21:09) SwEtDrm*ToMy: Floyd-Warshall算法的变形非常常见，注意其dp思想，uva上有几道练习
(21:22:29) SwEtDrm*ToMy: 图论部分还有Bellman-Ford求负权回路，以及求欧拉回路的算法
(21:23:06) SwEtDrm*ToMy: 近两年线段树比较热门
(21:24:12) SwEtDrm*ToMy: 求最长不xx子序列、最大公共子序列一类的经典dp算法要牢记
(21:25:44) SwEtDrm*ToMy: 为以防万一，我还看了高斯消元
(21:26:54) SwEtDrm*ToMy: 网络流和二分图，考的可能性不大，但有些想不出最优算法（如dp）的题可以用它来做，也能得不少分
(21:26:54) charles: rpz <自动回复>: 抱歉，我现在不在。请稍候再与我联系。
(21:27:32) SwEtDrm*ToMy: 注意drs上hqm的精华贴子，千万不可小看搜索
(21:29:24) SwEtDrm*ToMy: 计算几何是一大块，应该必考（但04年没考），包括凸包，看看lrj的书hl写的部分
(21:30:34) SwEtDrm*ToMy: 比较琐碎的，如牛顿迭代，LCA，还有zju上那道求爱的题，天知道考不考!
(21:32:15) SwEtDrm*ToMy: 对付noi不用看得太深，比如堆，知道普通堆就够得满分了，不必用Fibonacci堆，等等
(21:33:39) SwEtDrm*ToMy: 佯装没有听说过STL，因为不让用
(21:34:55) SwEtDrm*ToMy: 脑子发木的时候不要用cstring
(21:37:03) SwEtDrm*ToMy: dfs包括Articulation points割顶、bridges桥、Topological sort拓扑排序、Strongly connected components强连同子图
(21:38:40) SwEtDrm*ToMy: 线性规划
(21:38:40) charles: rpz <自动回复>: 抱歉，我现在不在。请稍候再与我联系。
(21:38:58) SwEtDrm*ToMy: FFT算法我到现在都不会
(21:46:31) charles: rpz: hi, 太感谢了
(21:46:38) charles: rpz: 我现在就在肯算法导论
(21:48:14) charles: rpz: 差分约束今天刚学会，在uva上ac过了，kmp还停留在理论阶段
(21:41:38) SwEtDrm*ToMy: 差分约束实际上就是一种转化，建立数学模型
(21:48:58) charles: rpz: 恩
(21:49:08) charles: rpz: 欧拉回路用什么算法求？
(21:49:08) charles: rpz: dfs?
(21:42:28) SwEtDrm*ToMy: usaco的TEXT有标程
(21:50:04) charles: rpz: 行，求割算法，算法导论有吗？
(21:50:09) charles: rpz: hqm讲我没听懂...
(21:42:59) SwEtDrm*ToMy: 欧拉路应该可以说是dfs吧。。。 但usaco专门拿出来讲了
(21:43:35) SwEtDrm*ToMy: 求割得看lrj的书，算法导论上作为练习题出现的，没有程序
(21:51:07) charles: rpz: 网络流要学那个预留推进算法吗？
(21:51:22) charles: rpz: 二分图和网络流我都会dfs/bfs找增广路那种
(21:44:04) SwEtDrm*ToMy: buyong
(21:44:13) SwEtDrm*ToMy: 够了
(21:51:31) charles: rpz: 奥...
(21:44:31) SwEtDrm*ToMy: kmp也不用推广，kmp的推广太麻烦而且变态
(21:52:01) charles: rpz: 感觉你好强啊，我前几天刚开始看算法导论
(21:45:09) SwEtDrm*ToMy: 我差不多也是那个时候开始看算法导论
(21:45:31) SwEtDrm*ToMy: 那本书够沉的...
(21:52:53) charles: rpz: hehe.... en
(21:53:09) charles: rpz: 估计不能带到学校看了...
(21:46:10) SwEtDrm*ToMy: 我就是一边上课一边看
(21:53:37) charles: rpz: 太沉了，以前我是带lrj
(21:53:41) charles: rpz: 就已经很沉了
(21:46:53) SwEtDrm*ToMy: 个人认为lrj的汉语表述不清楚，不适合上课看。。。
(21:54:18) charles: rpz: 比hqm清楚多了...
(21:54:40) charles: rpz: 我感觉算法导论里的图画的太强了
(21:54:45) charles: rpz: 一看就明白
(21:47:47) SwEtDrm*ToMy: 对！算法导论是用LaTeX排版的！！
(21:55:59) charles: rpz: 最长xxx子序列要掌握nlogn的？
(21:56:12) charles: rpz: nlogn的我只写过一遍
(21:49:05) SwEtDrm*ToMy: 经典算法，必背
(21:56:53) charles: rpz: 对了，有类似uva-summary的东西吗
(21:57:06) charles: rpz: 就是题目分类，看了hqm的zju summary觉得挺爽
(21:49:50) SwEtDrm*ToMy: oibh上有，lrj写的
(21:57:26) charles: rpz: 恩？我怎么只看到了ural的
(21:50:17) SwEtDrm*ToMy: 有uva
(21:57:38) charles: rpz: 现在oibh挂了，只好上这里 http://oibh.kuye.cn/
(21:57:41) charles: rpz: 在哪里？
(21:51:20) SwEtDrm*ToMy: 怎么oibh成了这样子。。。等等，我给你传一个
(21:58:42) charles: rpz: 好，thx
(21:58:53) charles: rpz: 我没法传文件，发到charlescpp@gmail.com吧
(22:02:42) charles: rpz: 群论那种东西要学吗？
(21:56:03) SwEtDrm*ToMy: 哦，是的，要知道polya定理
(21:57:01) SwEtDrm*ToMy: gmail上不去。。。用sina发了。。。等等
(22:04:27) charles: rpz: 恩，谢了

这几天 zju 挂了，非常不爽。
以后得狂补作业了，估计做 zju 的时间就不是很多了。usaco 好 BT 啊，连 money system 都要用 long long。

附件 prob.doc：http://blog.blogchina.com/upload/2005-02-08/20050208200032600541.doc

ZJU1140

#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

// FILE *fin = fopen("/tmp/1140/G.DAT", "r");
#define fin stdin

const int MAXN = 1000;
int w[MAXN], way[MAXN], waylen, used[MAXN];
int c[MAXN][MAXN], n, p;
int found;

void dfs(int dep, int i, int b) {
     if (found)
        return;
     if (used[i])
        return;
       
     used[i] = 1;
     way[dep] = i;
     if (b) {
        if (w[i] == 0)
           return;
        else
            dfs(dep+1, w[i], 0);
     }
     else {
          for (int j = 1; j <= n+p; j++)
              if (c[i][j] && w[j] == 0 && i != j) {
                 waylen = dep+1;
                 way[waylen] = j;
                 found = 1;
                 return;
              }
          for (int j = 1; j <= n+p && !found; j++)
              if (c[i][j] && w[i] != j && i != j)
                 dfs(dep+1, j, 1);
     }
}


int match() {
    int r = 0;

    memset(w, 0, sizeof(w));
    for (int i = 1; i <= p; i++) {
        if (w[i] == 0) {
           memset(way, 0, sizeof(way));
           memset(used, 0, sizeof(used));
           found = 0;
           waylen = 0;
           dfs(1, i, 0);

            for (int j = 1; j <= waylen; j += 2) {
                w[way[j]] = way[j+1];
                w[way[j+1]] = way[j];
            }
        }
    }

    r = 0;
    for (int i = 1; i <= p; i++)
        if (w[i] > 0)
           r++;
    return r;
}

int main() {
    int t;
    fscanf(fin, "%d", &t);

    while (t-->0) {
    fscanf(fin, "%d %d", &p, &n);

    memset(c, 0, sizeof(c));
   
    for (int i = 1; i <= p; i++) {
        int nc, q;
        fscanf(fin, "%d", &nc);
        while (nc-- > 0) {
              fscanf(fin, "%d", &q);
              q += p;
              c[i][q] = c[q][i] = 1;
        }
    }

    printf("%s\n", match() == p ? "YES" : "NO");
    }
}

这两天做pku warm up,发现一个叫NPHard的巨强，正奇怪那里出来这么一个强人，结果突然之间发现......
我不说了，大家自己去看

http://acm.pku.edu.cn/JudgeOnline/problemstatus?problem_id=2171

http://acm.pku.edu.cn/JudgeOnline/problemstatus?problem_id=2172

http://acm.pku.edu.cn/JudgeOnline/problemstatus?problem_id=2173

还有很多......

那个NPHard的代码总是跟一个人一样长......

那个人就是......

^_^

http://learn.tsinghua.edu.cn/homepage/2003012267/ZJUsummary.zip

先是看nba,火箭加时输国王，然后巨郁闷，开始做题，这时12:30。

最先看G,DP,5分钟就写完了，一交,CE......原来是忘了把include那行考上了，重交一次，ac......

然后看H,想了一个算法，O(N^2),虽然肯定到不了，但还是没把握，于是看I,巨easy的模拟题，写完代码，一次ac.然后回到H,发现Status里没有tle的，于是坚定信心，写了一个，一交，果然ac。这时才1:00

然后我就开始犹豫，是接着做还是算了，后来读了F,基本感觉是做不出来的，虽然很显然的是要用Hash，但我从来没实践过。就这样犹豫了一会，最终还是决定试一下。于是按照记忆中的方法，写了个线性探察判重的hash,最happy的是，只调了一次就通过样例，然后上去一交，居然ac......

然后兴奋不已的我就去打球了，一打发现球感巨好，看来OI真是一好东西呀......

PKU warm up 2 的Problem B,虽然最后终于过了，但弄的我心情很糟......然后就再也没有心情编下面的题了......

今天看了一道题，感觉不错，虽然没想到算法......

大家看看吧，谁能帮我想想，谢谢了

PKU 1944

Fiber Communications

Description

Farmer John wants to connect his N (1 <= N <= 1,000) barns (numbered 1..N) with a new fiber-optic network. However, the barns are located in a circle around the edge of a large pond, so he can only connect pairs of adjacent barns. The circular configuration means that barn N is adjacent to barn 1.

FJ doesn't need to connect all the barns, though, since only certain pairs of cows wish to communicate with each other. He wants to construct as few
connections as possible while still enabling all of these pairs to communicate through the network. Given the list of barns that wish to communicate with each other, determine the minimum number of lines that must be laid. To communicate from barn 1 to barn 3, lines must be laid from barn 1 to barn 2 and also from barn 2 to barn 3(or just from barn 3 to 1,if n=3).

Input

* Line 1: Two integers, N and P (the number of communication pairs, 1 <= P <= 10,000)

* Lines 2..P+1: two integers describing a pair of barns between which communication is desired. No pair is duplicated in the list.

Output

One line with a single integer which is the minimum number of direct connections FJ needs to make.

Sample Input

5 2
1 3
4 5

5 2
1 3
4 5

 

Sample Output

3

3

 

Hint

[Which connect barn pairs 1-2, 2-3, and 4-5.]

Source

USACO 2002 February

秦腾写了一个栈搜索,怕被BS 现在yz, ls, wd都写栈搜索, 就我一个人用咱们那种dfs

 

 

#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include <fstream.h>

#define bool int
#define true 1
#define false 0

#define MAXN 5

ifstream fin("d:/in.txt");
#define cin fin

enum {TOP = 0, LEFT = 1, BOTTOM = 2, RIGHT = 3};

int n;
bool used[MAXN*MAXN];
int t[MAXN][MAXN];
int a[MAXN*MAXN][4];
bool found;
int w;

bool tlink[26][26], blink[26][26], llink[26][26], rlink[26][26];

bool check(int x, int y) {
 if (x == 0 && y == 0)
  return true;
 else if (x == 0 && y != 0) {
  return (a[t[0][y]][TOP] == a[t[0][y-1]][BOTTOM]);
 }
 else if (y == 0 && x != 0) {
  return (a[t[x][0]][LEFT] == a[t[x-1][0]][RIGHT]);
 }
 else {
  return (a[t[x][y]][TOP] == a[t[x][y-1]][BOTTOM]) && (a[t[x][y]][LEFT] == a[t[x-1][y]][RIGHT]);
 }
}

void dfs(int x, int y) {
 int i, j, k;

 if (found)
  return;

 if (x == n) {
  dfs(0, y+1);
  return;
 }

 if (y >= n) {
  found = true;
  return;
 }

 for (j = 0; j < n*n && !found; j++)
  if (!used[j]) {
   used[j] = true;

   /*for (k = 0; k < 4; k++)
    t[x][y][k] = a[j][k];*/
   t[x][y] = j;

   if (check(x,y))
    dfs(x+1, y);
   used[j] = false;
  }
}

void for_each() {
 int i, j, k1, k2, m;

 memset(used, 0, sizeof(used));
 memset(t, 0, sizeof(t));

 cin >> n;
 if (cin.eof() || n == 0)
  exit(0);
 for (i = 0; i < n*n; i++) {
  for (j = 0; j < 4; j++)
   cin >> a[i][j];
 }

 cout << "Game " << w << ":" << endl;

 for (i = 0; i < n*n; i++)
  for (j = 0; j < n*n; j++) {
    llink[i][j] = (a[i][LEFT] == a[j][RIGHT]);
    rlink[i][j] = (a[i][RIGHT] == a[j][LEFT]);
    tlink[i][j] = (a[i][TOP] == a[j][BOTTOM]);
    blink[i][j] = (a[i][BOTTOM] == a[j][TOP]);
  }

 found = false;
 dfs(0, 0);

 cout << (found ? "Possible" : "Impossible") << endl;
 cout << endl;
}

int main() {
 w = 1;
 while (1) {
  for_each();
  w++;
 }
}