本文通过工具从以前的 html 转成 markdown，格式可能有问题。
ACM语法基础
C/CPP不常用的知识点
字符串拆分
char ss[] = "(1,2,3,4)";
char *p = strtok(ss, "(,)");
for (int i(1); i<=n; i++) {
sscanf(p, "%d", &k);
p = strtok(NULL, ",)");
}
gets 、fgets 、getline
- gets 会过滤行首空格（不含
\n） - fgets 完全读入，把
\n吃进字符串末位，与scanf混用时容易出错 - getline 自动跳转下一行，不会过滤行首空格
Java快速读写
例题
@ hdoj 5047 Sawtooth
读入一个大数，按照特定公式计算结果。
import java.math.*;
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter cout = new BufferedWriter(new OutputStreamWriter(System.out));
BigInteger n, ans, a1, a2, a7, a8;
a1 = BigInteger.valueOf(1);
a2 = BigInteger.valueOf(2);
a7 = BigInteger.valueOf(7);
a8 = BigInteger.valueOf(8);
String ss = cin.readLine();
int T = Integer.parseInt(ss);
for(int i=1; i<=T; i++){
ss = cin.readLine();
n = new BigInteger( ss );
cout.write( "Case #"+i+": " );
ans = n.multiply(n).multiply(a8);
ans = ans.subtract(a7.multiply(n));
ans = ans.add(a1);
cout.write( ans.toString() );
cout.newLine();
cout.flush();
}
}
}
模拟易错点
a
b
@ POJ 1017 Packets | 装完大包装小包
/*
6种物品，体积分别为1*1 2*2 ... 6*6 。每种数量有20000
包裹体积为6*6，问装满所有的物品至少需要多少个包裹。
solution：
从大到小装，有缝隙了依次选小的。
*/
#include <cstdio>
#include <iostream>
using namespace std;
int n=6,t;
int a[8];
int push(int t,int i, int num){ // 把num个a[i]放进容量为t的箱子里，返回箱子容量
if ( num > a[i]) num = a[i];
t -= i*i * num;
a[i] -= num;
return t;
}
int main(){
for(;;){
int ts = 0;
for ( int i(1);i<=n;i++){
cin >> a[i];
ts+=a[i];
}
if (!ts) break;
int s =a[6]+a[5]+a[4];
// a5
if (a[5]*11 >= a[1]) a[1] = 0;
else a[1] -= a[5]*11;
// a4
for ( int i(1);i<=a[4];i++){
t = push(20,2,5);
if (t) t = push(t,1,t);
}
// a3
s += a[3] / 4; // 整装3
a[3] %= 4;
if (a[3]){ // 剩下的空间分情况装2
t = 36 - a[3]*9;
if ( a[3] == 1 ) t = push(t,2,5);
if ( a[3] == 2 ) t = push(t,2,3);
if ( a[3] == 3 ) t = push(t,2,1);
if (t) t = push(t,1,t); // 剩下的空间都装1
s++;
}
// a2
s += a[2] / 9;
a[2] %= 9;
if (a[2]){
t = 36 - a[2] * 4;
t = push(t,1,t);
s++;
}
// a1
s += a[1] / 36;
a[1] %= 36;
if (a[1]) s++;
cout << s << endl;
}
return 0;
}
@ USACO 1.4.3 The Clocks
/*
根据九个表和九个操作的关系，得出下列关系表：
先列一下钟表与矩阵的关系图：
Ci = C[i] / 3;
clocks operates
1 1 2 4 ( C1 + p1 + p2 + p4 ) % 4 == 0
2 1 2 3 5 ( C2 + p1 + p2 + p3 + p5 ) % 4 == 0
3 2 3 6 ...
4 1 4 5 7 ...
5 1 3 5 7 9 ...
6 3 5 6 9
7 4 7 8
8 5 7 8 9
9 6 8 9
把上面的关系式反过来，就能在已知 c[i] 通过枚举部分 pi 求出其它 pi
我枚举的是123三个操作，然后剩下6个操作就可以就确定了。
*/
#include <cstdio>
#include <iostream>
using namespace std;
int c[11];
int cal(int a, int b, int c){
int t = - a - b - c;
while ( t < 0 ) t += 4;
return t;
}
int cal(int a, int b, int c, int d){
int t = - a - b - c - d;
while ( t < 0 ) t += 4;
return t;
}
int main(){
freopen("clocks.in","r",stdin);
freopen("clocks.out","w",stdout);
for (int i(1);i<=9;i++) {
cin >> c[i];
c[i] /= 3;
}
int p[11];
bool found = false;
for ( p[1] = 0; p[1] < 4; p[1]++ ){
for ( p[2] = 0; p[2] < 4; p[2]++ ){
for ( p[3] = 0; p[3] < 4; p[3]++ ){
p[4] = cal(c[1], p[1], p[2]);
p[5] = cal(c[2], p[1], p[2], p[3]);
p[6] = cal(c[3], p[2], p[3]);
p[7] = cal(c[4], p[1], p[4], p[5]);
p[8] = cal(c[7], p[4], p[7]);
p[9] = cal(c[9], p[6], p[8]);
if (((c[5] + p[1] + p[3] + p[5] + p[7] + p[9]) % 4 == 0) &&
((c[8] + p[5] + p[7] + p[8] + p[9] ) % 4 == 0) &&
((c[6] + p[3] + p[5] + p[6] + p[9] ) % 4 == 0 )){
found = 1;
break;
}
if ( found ) break;
}
if ( found ) break;
}
if ( found ) break;
}
int i = 1;
while ( p[i] == 0 ) i++;
printf("%d",i);
p[i--]--;
while ( ++i <= 9 ) while ( p[i]-- ) printf(" %d",i);
printf("\n");
return 0;
}
搜索
多状态标记
@ HDU 5024 Wang Xifeng’s Little Plot 广州区域赛
/*
题意：找到一个最长的L型
思路：把L拆成两个直线，枚举所有的情况，记忆化搜索
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 110;
int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};
int n, f[maxn][maxn][8];
char g[maxn][maxn];
int dfs(int x, int y, int dir) {
if (f[x][y][dir] != -1)
return f[x][y][dir];
if (g[x+dx[dir]][y+dy[dir]] == '.')
return f[x][y][dir] = 1 + dfs(x+dx[dir], y+dy[dir], dir);
else return f[x][y][dir] = 1;
}
int main() {
while (scanf("%d", &n) != EOF && n) {
memset(f, -1, sizeof(f));
memset(g, 0, sizeof(g));
for (int i = 1; i <= n; i++)
scanf("%s", g[i]+1);
int ans = -1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (g[i][j] == '.') {
ans = max(ans, dfs(i, j, 0) + dfs(i, j, 2) - 1);
ans = max(ans, dfs(i, j, 1) + dfs(i, j, 2) - 1);
ans = max(ans, dfs(i, j, 1) + dfs(i, j, 3) - 1);
ans = max(ans, dfs(i, j, 0) + dfs(i, j, 3) - 1);
ans = max(ans, dfs(i, j, 4) + dfs(i, j, 5) - 1);
ans = max(ans, dfs(i, j, 4) + dfs(i, j, 6) - 1);
ans = max(ans, dfs(i, j, 7) + dfs(i, j, 5) - 1);
ans = max(ans, dfs(i, j, 7) + dfs(i, j, 6) - 1);
}
printf("%d\n", ans);
}
return 0;
}
@ HDU 5025 Saving Tang Monk
题意：给一个地图，孙悟空(K)救唐僧(T)，地图中’S’表示蛇，第一次到这要杀死蛇（蛇最多5条），多花费一分钟，’1’~’m’表示m个钥匙(m<=9)，孙悟空要依次拿到这m个钥匙，然后才能去救唐僧，集齐m个钥匙之前可以经过唐僧，集齐x个钥匙以前可以经过x+1,x+2..个钥匙，问最少多少步救到唐僧。
/*
本题主要是每一条蛇状态的记录，使用状态压缩，将每一条蛇的状态用二进制位记录下来，1代表活，0代表死。
使用vis四维数组记录每一点走过的状态，x,y分别表示位置，k 钥匙，s 表示蛇的状态，b 表示步数。
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
const int inf=0xfffffff;
typedef long long ll;
using namespace std;
char m[105][105];
int vis[105][105][15][40];
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int sx, sy, sn, N, M;
struct node
{
int x, y, k, s, b;
};
queue<node> q;
int ans;
void bfs()
{
node now;
q.push((node){sx, sy, 0, 0, 0});
while(!q.empty()){
now = q.front();
q.pop();
int x = now.x, y = now.y, k = now.k, s = now.s, b = now.b;
if(k == M && m[x][y] == 'T'){
ans = min(ans, b);
}
if(vis[x][y][k][s] != 0) continue;
vis[x][y][k][s] = 1;
for(int i = 0; i < 4; i ++){
int nx = x + dx[i], ny = y + dy[i];
int snn = m[nx][ny] - 'A';
if(snn >= 0 && snn < sn){
if((1<<snn) & s) q.push((node) {nx, ny, k, s, b + 1});
else q.push((node) {nx, ny, k, (1<<snn) | s, b + 2});
}
else{
if(m[nx][ny] == k + '1'){
q.push((node) {nx, ny, k + 1, s, b + 1});
}
else if(nx > 0 && nx <= N && ny > 0 && ny <= N && m[nx][ny] != '#')
q.push((node) {nx, ny, k, s, b + 1});
}
}
}
}
int main()
{
//freopen("in", "r", stdin);
while(~scanf("%d %d", &N, &M)){
if(N == 0 && M == 0) break;
memset(m, 0, sizeof(m));
memset(vis, 0, sizeof(vis));
sn = 0;
for(int i = 1; i <= N; i ++){
scanf("%s", m[i] + 1);
for(int j = 1; j <= N; j ++){
if(m[i][j] == 'K'){
sx = i;
sy = j;
}
if(m[i][j] == 'S'){
m[i][j] = 'A' + sn;
sn ++;
}
}
}
ans = inf;
bfs();
if(ans == inf) printf("impossible\n");
else printf("%d\n", ans);
}
return 0;
}
/*
解法：BFS，每个节点维护四个值：
x,y ： 当前坐标
key ：已经集齐了key个钥匙
step：已经走了多少步
S ： 蛇的访问状态 (2^5的数表示，某位为1表示已经杀过了)
然后把唐僧看做钥匙m+1，再加点优化：
为了避免超时，用一个全局的dis[x][y][key][S] 表示到(x,y),已经集齐到key个钥匙，蛇的访问状态为S时的最小步数，如果BFS扩展的时候，当前状态的步数>=dis[当前状态]，那么就不再扩展下去了。
BFS中的逻辑就很简单了，看代码吧。
最后，枚举蛇的状态S，取dis[x][y][m+1][S]的最小值即为最小步数。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#define INF 0x3f3f3f3f
using namespace std;
#define N 1000007
int dis[104][104][12][33],Stot,M;
struct node
{
int x,y,key,step,S;
};
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
map<pair<int,int>,int> snake;
char ss[105][105];
int n,m;
bool OK(int nx,int ny)
{
if(nx < n && nx >= 0 && ny < n && ny >= 0 && ss[nx][ny] != '#')
return true;
return false;
}
void bfs(node s)
{
queue<node> que;
que.push(s);
while(!que.empty())
{
node now = que.front();
que.pop();
int nx = now.x, ny = now.y;
int key = now.key, step = now.step;
int S = now.S;
node tmp;
for(int k=0;k<4;k++)
{
int kx = nx + dx[k];
int ky = ny + dy[k];
if(!OK(kx,ky)) continue;
tmp.x = kx,tmp.y = ky;
if(ss[kx][ky] == 'S') //蛇
{
int ind = snake[make_pair(kx,ky)]; //是第几条蛇
tmp.key = key;
if(S & (1<<(ind-1))) //如果已经杀死
{
tmp.S = S;
tmp.step = step+1;
}
else //否则要杀
{
tmp.S = S|(1<<(ind-1));
tmp.step = step+2;
}
if(tmp.step < dis[kx][ky][tmp.key][tmp.S])
{
dis[kx][ky][tmp.key][tmp.S] = tmp.step;
que.push(tmp);
}
}
else if(ss[kx][ky] >= '1' && ss[kx][ky] <= '9') //钥匙点
{
int num = ss[kx][ky] - '0';
tmp.step = step+1;
tmp.S = S;
if(num == key+1) //正好是要拿的那个
tmp.key = key+1;
else
tmp.key = key;
if(tmp.step < dis[kx][ky][tmp.key][tmp.S])
{
dis[kx][ky][tmp.key][tmp.S] = tmp.step;
que.push(tmp);
}
}
else if(ss[kx][ky] == '$') //唐僧这个点
{
tmp.key = key;
tmp.S = S;
tmp.step = step+1;
if(M == key+1) //已经集齐了所有钥匙，不再扩展，更新dis即可
dis[kx][ky][M][S] = min(dis[kx][ky][M][S],step+1);
else //没有集齐，继续走
que.push(tmp);
}
else if(ss[kx][ky] == '.')
{
tmp.key = key;
tmp.S = S;
tmp.step = step+1;
if(tmp.step < dis[kx][ky][tmp.key][tmp.S])
{
dis[kx][ky][tmp.key][tmp.S] = tmp.step;
que.push(tmp);
}
}
}
}
}
int main()
{
int Sx,Ex,Sy,Ey;
int i,j;
while(scanf("%d%d",&n,&m)!=EOF && n+m)
{
if(n == 1)
{
puts("impossible");
continue;
}
snake.clear();
Stot = 0;
M = m+1;
for(i=0;i<n;i++)
{
scanf("%s",ss[i]);
for(j=0;j<n;j++)
{
if(ss[i][j] == 'K')
Sx = i,Sy = j, ss[i][j] = '.';
else if(ss[i][j] == 'T')
Ex = i,Ey = j, ss[i][j] = '$';
else if(ss[i][j] == 'S')
snake[make_pair(i,j)] = ++Stot;
}
}
node tmp;
tmp.x = Sx,tmp.y = Sy,tmp.key = 0,tmp.step = 0,tmp.S = 0;
memset(dis,INF,sizeof(dis));
dis[Sx][Sy][0][0] = 0;
bfs(tmp);
int mini = INF;
for(i=0;i<(1<<Stot);i++)
mini = min(mini,dis[Ex][Ey][M][i]);
if(mini == INF)
puts("impossible");
else
printf("%d\n",mini);
}
return 0;
}
图论
欧拉回路 哈密顿回路
判断存在
判断欧拉通路：
- 一个有向图存在欧拉回路必定也存在欧拉通路…因为通路的定义包括了回路
- 不考虑为欧拉回路的情况..一个有向图是欧拉通路就必须有一个点出度-入度=1,一个点入度-出度=1..这两点就是欧拉通路的起点和终点..并且该图连通
- 我自己加一条，其实是对2的理解：入读-出度>1 时直接return false ，排除 a->b a->c 这种情况
判断欧拉回路：
无向图是欧拉图的充要条件是所有点的度为偶数并且所有点联通
有向图是欧拉图的充要条件是所有点的入度=出度..并且联通…
判断连通:
- dfs遍历，这里有一份参考代码不过我一直怀疑其正确性。因为你无法确定有向图的起点，比如 a->b->c 如果你从b点开始搜的话就会悲催，但是你不知道b点上面还有没有点。
- 并查集，并查集的方便之处不用废话。但是在图论中两点之间有多条边时需要注意一些细节的处理。
关于判断入读出度:
一种办法是分别记录 in[] out[] 我用的办法是一个数组：sz[x]++ 表示拉出一条边，sz[x]–表示走来一条边，sz[x]==1 sz[x]==-1 就是上面的两种情况
@ UVa 10129 Play on Words
/*
题意就是给你一堆单词，按首位顺序排列起来，问你有没有解。
第一眼看上去是个哈密顿通路，单词当做节点，首尾关系作边，听上去妥妥的不过N有100000 复杂度太恐怖。
其实是从刘汝佳的小白书第二版（其实该叫小紫红书了）上欧拉回路那节看到的，所以得考虑考虑转换
把单词当边，首尾字符当做点 题目就转变为 欧拉通路
*/
#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#define N 101010
using namespace std;
int sz[333];
int fa[333];
bool ok[333]; // 数据中使用到的单词
int n, T;
int getfa(int v)
{
if ( fa[v] == v ) return v;
return fa[v] = getfa(fa[v]);
}
void init()
{
memset(ok, 0, sizeof(ok));
memset(sz, 0, sizeof(sz));
cin >> n;
string a;
for ( int i('a'); i <= 'z'; i++) fa[i] = i;
for ( int i(1); i <= n; i++)
{
cin >> a;
int x = a[0], y = a[a.size() - 1];
fa[getfa(x)] = getfa(y);
ok[x] = ok[y] = true;
sz[x]++;
sz[y]--;
}
}
bool check()
{
int tf = 0 , i;
for ( i = 'a'; i <= 'z'; i++)
{
if (ok[i])
{
if ( !tf ) tf = getfa(i);
else if ( getfa(i) != tf ) return false; // 不连通
}
}
int c1 = 0, c2 = 0;
for ( int i('a'); i <= 'z'; i++)
{
if (!ok[i]) continue;
if ( sz[i] == 0 ) continue;
else if ( sz[i] == 1 ) c1++;
else if ( sz[i] == -1) c2++;
else return false; // 其它乱七八糟的情况 比如 ab ab out[a]=2 in[b]=2
}
if ( (c1 == 1 && c2 == 1) || (c1 == 0 && c2 == 0) ) // 单向路径 or 回路
return true;
else
return false;
}
int main()
{
freopen("in.txt", "r", stdin);
for ( cin >> T; T--; )
{
init();
if (check())
cout << "Ordering is possible." << endl;
else
cout << "The door cannot be opened." << endl;
}
}
二分图最大匹配
@ POJ 3041 Asteroids 匈牙利算法
/*
看起来像个 DP 神马的。竟然是二分图匹配。。
看着啊，行与行之间相互独立，一个行可以就炸掉很多列。（列的道理一样），如果替换一些字。
点与点之间相互独立，一个点就可以炸掉很多边。
so，可以把行列看成一个点，把一个炸弹看成一条边，然后题目就转换城了最小点击覆盖（即最大匹配）。
这个题的思路就是上面说的，每一个炸弹（x，y）看做一条边，两个端点就是它的行列x 和 y。任意炸掉x y期中一个点都可以把可以把这条边炸掉。跟题目一样了。
就这么神奇。。
*/
#include <cstdio>
#include <cstring>
const int N = 555;
int n, m, g[N][N], chk[N], match[N];
int dfs(int v){
int t;
for ( int i = 1; i <= n; i++){
if ( g[i][v] && !chk[i] ){
chk[i] = 1;
t = match[i];
match[i] = v;
if ( t == -1 || dfs(t) ) return 1;
match[i] = t;
}
}
return 0;
}
int main(){
while ( ~scanf("%d%d", &n ,&m) ){
memset(g, 0, sizeof(g));
while ( m-- ){
int a, b;
scanf("%d%d", &a, &b);
g[a][b] = 1;
}
int ans = 0;
memset(match, 255, sizeof(match));
for ( int i = 1; i <= n; i++){
memset( chk, 0, sizeof(chk));
ans += dfs(i);
}
printf("%d\n", ans);
}
return 0;
}
