acmtips


本文通过工具从以前的 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. 一个有向图存在欧拉回路必定也存在欧拉通路…因为通路的定义包括了回路
  2. 不考虑为欧拉回路的情况..一个有向图是欧拉通路就必须有一个点出度-入度=1,一个点入度-出度=1..这两点就是欧拉通路的起点和终点..并且该图连通
  3. 我自己加一条,其实是对2的理解:入读-出度>1 时直接return false ,排除 a->b a->c 这种情况

判断欧拉回路:

无向图是欧拉图的充要条件是所有点的度为偶数并且所有点联通
有向图是欧拉图的充要条件是所有点的入度=出度..并且联通…

判断连通:

  1. dfs遍历,这里有一份参考代码不过我一直怀疑其正确性。因为你无法确定有向图的起点,比如 a->b->c 如果你从b点开始搜的话就会悲催,但是你不知道b点上面还有没有点。
  2. 并查集,并查集的方便之处不用废话。但是在图论中两点之间有多条边时需要注意一些细节的处理。

关于判断入读出度:

一种办法是分别记录 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;
}


Avatar
huiren
Code Artisan

问渠那得清如许,为有源头活水来

下一页
上一页
comments powered by Disqus