第六届山东省ACM总结

拖了好久才写这份总结,中间考试,聚会,等等都推迟了这事儿。写的过程中一度想要不写了,可能是觉得结果有些不尽人意吧。

赛程

早上6点多起床,然后吃了个早饭,大概7点钟出发,路上前面的两位都在听歌,我因为耳机找不到,也没有下电影,思想神游了4个小时,也是挺佩服自己的 — 或者是刷微博?

到了以后大体上逛了下山科的校园,挺大,环境也不错,但是明显能够感觉出年轻,没有岁月的味道,心情一直是比较平静的。下午热身赛,没有特别出彩,已经不记得当时在个什么名次上 — 反正也不是很重要= =

然后就是正式比赛,拿了铜牌。

不想空洞的描述这场比赛,还是随意一点,然后再简单整理一下吧。

比赛之前的晚上发现自己博弈部分没有掌握好,图论部分也是没有完全看完重点,但是因为第五届的比赛的原因,觉得无妨,图论题目应该出了也做不出来(的确,没做出来,笑),博弈因为去年有一个(后来想到可能是记错了),所以也是没有很在意,觉得应该不至于不幸的一次就搞到我不擅长的地方吧!

结果正式比赛正好考到博弈和图论,博弈费了好些力才推理出来,图论一开始搞错了题目的意思,最后分析题目计算时间复杂度的时候就已经发现可能超时间,但是没有找出合理的办法 — 其实在当时看看,也的确应该是去试试,因为感觉可能比较简单,AC的人并不少。

当然赛后发现如果有那个知识,那么这道题目还是比较简单的,哈哈。

GH题目就是比较简单的质因子分解+哈希,但是糟糕的是当时虽然想到质因子分解,但是没有具体的细想,去探究,深度不够。 — 也是因为受了之前比赛的影响,很多时候因为我自己想得太深方向还不对结果浪费了时间。

总结

ACM – 浙江省赛F – 图论

  • 浙江省赛题目,分析后直接暴力即可,奈何场上脑子里全是floyd,WA无数次。

  • 做题一定要先分析时间复杂问题,采取暴力方法,然后再考虑复杂问题解决方法。

  • 此外今天开始使用赛用vimrc才发现出现不少问题,还好提前使用了。

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int n, m, k;
const int maxn = 100 +10;
int g[maxn][maxn];
void debug()
{
    for(int i = 0; i < n; i++)
    {
        for(int j = 0;j < n;j ++)
        {
            cout << g[i][j];
        }
        cout << endl;
    }
}
int main()
{
    //freopen("input", "r", stdin);
    int t;
    cin >> t;
    int u, v;
    while(t--)
    {
        memset(g, 0, sizeof(g));
        scanf("%d%d%d", &n, &m, &k);
        for(int i = 0; i < m; i++)
        {
            scanf("%d%d", &u, &v);
            g[u][v] = g[v][u] = 1;
        }
        int ans, pre;
        ans = 0;
        pre = 1;
        while(pre != ans) {
            pre = ans;
            for(int i = 0; i < n; i++) {
                for(int j = 0;j < n; j++) {
                    // itself
                    if(i == j || g[i][j]) continue;
                    int count = 0;
                    for(int s = 0; s < n; s++)
                        if(s != i && s != j && g[i][s] && g[s][j])
                            count++;
                    if(count >= k) {
                        ans++;
                        g[i][j] = 1;
                        g[j][i] = 1;
                    }
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

ACM – Uva10054 – 欧拉回路

问能不能拼接一条项链,条件是首尾相同构成环。

这个题的坑在:
1. 虽然保证连通,但是不一定每个颜色都有,所以单纯的暴力euler(1)是很愚蠢的。
2. 题目本身是要求顺序输出的,也就是dfs不能回溯,如果回溯,为了保证准确性,需要交换uv的位置来保证。
3. 通过统计出度入度判断是否满足欧拉回路。

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(a, -1, sizeof(a))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
#define CR printf("\n")
const double PI = acos(-1.0);
int n;
const int maxn = 1000+10;
int g[60][60];
void euler(int u)
{
    for(int v = 1; v <= 50; v++) if(g[u][v])
    {
        g[u][v]--, g[v][u]--;
        euler(v);
        printf("%d %d\n", v, u);
    }
}
int degree[60];
bool check()
{
    for(int i = 1; i<= 50; i++)
        if(degree[i] % 2) return false;
    return true;
}
int main()
{
#ifdef DEBUG
    freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    int t;
    cin >> t;
    for(int kase = 1; kase <= t; kase++)
    {
        scanf("%d", &n);
        memset(g, 0, sizeof(g));
        memset(degree, 0, sizeof(degree));
        int f, e;
        for(int i = 0; i < n;i++)
        {
            scanf("%d%d", &f, &e);
            g[f][e] ++;
            g[e][f] ++;
            degree[f]++, degree[e]++;
        }
        printf("Case #%d\n", kase);
        if(check()) for(int i = 1; i<=50; i++) euler(i);
        else puts("some beads may be lost");
        if(kase != t) CR;
    }
    return 0;
}

ACM – Uva10047 – 图论

隐式图搜索,多个状态然后减枝。。没看懂李大大所说可以承受是个啥意思。。

做起来实在太累了。。减枝的部分看了别人的代码,发现着实麻烦,不如用优先队列来的痛快=- =还有用优先队列做的= =

主要是$vis[x][y][p][c]$这组状态比较难搞,但是给了优先级(时间短的先出队),事情就好办了。

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(a, -1, sizeof(a))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
#define CR printf("\n")
const double PI = acos(-1.0);
const int maxn = 30;
char g[maxn][maxn];
// c, 0, 1, 2, 3, 4
// blue,w,g,black,r;
struct Node {
    int x, y, c, p, t;
    Node(int x, int y, int c, int p, int t):x(x), y(y), c(c), p(p), t(t){}
    Node(){}
    bool operator < (const Node b) const {
        return t > b.t;
    }
};
Node s, e;
int n, m;
inline int judge(int x, int y)
{
    return x >= 0 && x < m && y >= 0 && y < n;
}
bool vis[maxn][maxn][4][5];
void test() {
    for(int i = 0; i<m ;i++) {
        for(int j = 0; j <n; j++ ) {
            printf("%2c", g[i][j]);
        }
        cout << endl;
    }
}
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int bfs()
{
    priority_queue <Node> q;
    Node t, next;
    int ans = INF;
    q.push(s);
    while(!q.empty())
    {
        t = q.top(), q.pop();
        vis[t.x][t.y][t.p][t.c] = 1;
        if(t.x == e.x && t.y == e.y && t.c == e.c) return t.t;
        for(int i = 0; i < 4; i++)
        {
            next.x = t.x + dx[i];
            next.y = t.y + dy[i];
            next.c = (t.c+1)%5;
            next.p = i;
            if(next.p == t.p)
                next.t = t.t+1;
            else if(abs(next.p-t.p) == 2)
                next.t = t.t+3;
            else
                next.t = t.t+2;
            if(g[next.x][next.y] != '#' && !vis[next.x][next.y][next.p][next.c]
                    && judge(next.x, next.y))
                q.push(next);
        }
    }
    return ans;
}
int main()
{
#ifdef DEBUG
    freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    int kase = 1;
    while(scanf("%d%d", &m, &n) != EOF)
    {
        MEM(vis);
        if(n == 0 && m == 0) break;
        for(int i = 0; i < m; i++)
            scanf("%s", g[i]);
        // read 
        for(int i = 0; i < m ;i ++) {
            for(int j = 0;j < n; j++) {
                if(g[i][j] == 'S') s = Node(i, j, 2, 0, 0);
                else if(g[i][j] == 'T') e = Node(i, j, 2, 0, 0);
            }
        }
        int ans = bfs();
        if(kase != 1) CR;
        printf("Case #%d\n", kase++);
        if(ans == INF) puts("destination not reachable");
        else printf("minimum time = %d sec\n", ans);
    }
    return 0;
}

灭火

火会蔓延,人被火追着跑,能否跑出边界的问题。

bfs火之后bfs人,或火和人放在一个队列里面bfs

坑是没有火的情况,如果从0更新火势图而不是inf开始,那么可能造成没火不能跑的情况。

/*=============================================================================
#
# Author: svtter - svtter@qq.com
#
# QQ : 57180160
#
# Last modified: 2015-05-04 09:50
#
# Filename: 11634.cpp
#
# Description: 
#
=============================================================================*/
#include <iostream>
#include <string.h>
#include <assert.h>
#include <stdio.h>
#include <cmath>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(a, -1, sizeof(a))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
#define CR printf("\n")
const double PI = acos(-1.0);
const int maxn = 1010;
char g[maxn][maxn];
int gex[maxn][maxn];
bool vis[maxn][maxn];
int r, c;
int dx[] = {0, 1, -1, 0};
int dy[] = {1, 0, 0, -1};
struct Node {
    int i, j, t;
    Node() {}
    Node(int i, int j, int t):i(i), j(j), t(t){}
};
inline int judge(int x, int y)
{
    return x >= 0 && x < r && y >= 0 && y < c;
}
void init(queue <Node> &q) {
    Node temp, next;
    int nx, ny;
    while(!q.empty()) {
        temp = q.front(), q.pop();
        temp.t++;
        for(int i = 0; i < 4; i++) {
            nx = temp.i + dx[i];
            ny = temp.j + dy[i];
            if(g[nx][ny] != '#' && judge(nx, ny) && gex[nx][ny] > temp.t) {
                next.i = nx;
                next.j = ny;
                next.t = temp.t;
                gex[nx][ny] = temp.t;
                q.push(next);
            }
        }
    }
}
int bfs(queue <Node> &q) {
    Node t, n;
    int nx, ny;
    while(!q.empty()) {
        t = q.front(), q.pop();
        if(t.i == r-1 || t.j == c-1 || t.i == 0 || t.j == 0) return t.t;
        t.t ++;
        for(int i = 0; i < 4; i++)
        {
            nx = t.i + dx[i];
            ny = t.j + dy[i];
            if(!vis[nx][ny] && gex[nx][ny] > t.t && judge(nx, ny))
            {
                n.i = nx, n.j = ny, n.t = t.t;
                vis[nx][ny] = 1;
                q.push(n);
            }
        }
    }
    return 0;
}
int main()
{
#ifdef DEBUG
    freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    int t;
    scanf("%d", &t);
    queue <Node> q;
    while(t--) {
        while(!q.empty()) q.pop();
        scanf("%d%d", &r, &c);
        MEM(vis); Node joe;
        memset(gex, INF, sizeof(gex));
        for(int i = 0; i < r; i++)
            scanf("%s", g[i]);
        for(int i = 0; i < r; i++)
        {
            for(int j = 0;j < c;j ++) {
                if(g[i][j] == 'F')
                {
                    vis[i][j] = 1;
                    gex[i][j] = 1;
                    q.push(Node(i, j, 1));
                }
                else if(g[i][j] == 'J')
                {
                    vis[i][j] = 1;
                    joe = Node(i, j, 1);
                }
                else if(g[i][j] == '#') vis[i][j] = 1;
            }
        }
        init(q);
        q.push(joe);
        int ans = bfs(q);
        if(ans == 0) puts("IMPOSSIBLE");
        else printf("%d\n", ans);
    }
    return 0;
}

ACM – Uva10294 – 置换

项链和手镯。

项链的问题在于不可以翻转,因此少了一种置换,而手镯则可以反转。然后我们计算旋转的置换。

旋转的步长可以是0,i,2i…然后我们可以得出循环一共有n/gcd(i,n)个元素,因此,我们可以计算出一共有gcd(i,n)个循环。则不定点的个数为
$a = \Sigma t^{gcd(i,n)}$。

翻转。翻转奇数情况和偶数情况是不一样的,因为奇数情况会多一个不定点,这个不定点就是在轴上的点。剩余的不定点的个数就是$n/2$,总共不定点的个数就是$nt^{(n+1)/2}$。偶数的情况下,如果正好切在两个珠子上,那么循环长度为2的点有$n/2-1$个,长度为1的循环有2个,所以总共$n/2+1$个。如果没有切在珠子上,不定点的个数为$n/2$,和为$b = n/2*(t^{n/2+1} + t^{n/2})$。

然后我们可以计算出项链的个数$a/n$,手镯的个数$(a+b)/2n$

列出式子以后代码就方便了。记得求pow的时候可以顺手打表

/*=============================================================================
#
# Author: svtter - svtter@qq.com
#
# QQ : 57180160
#
# Last modified: 2015-05-03 18:48
#
# Filename: 10294.cpp
#
# Description: 
#
=============================================================================*/
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(a, -1, sizeof(a))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
#define CR printf("\n")
const double PI = acos(-1.0);
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a%b);
}
const int maxn = 60;
ll po[maxn];
int main()
{
#ifdef DEBUG
    // freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    int n, t;
    ll ans, ans2;
    while(scanf("%d%d", &n, &t) != EOF && n)
    {
        po[0] = 1;
        ans = 0;
        for(int i = 1; i <= n; i++) po[i] = po[i-1] * t;
        for(int i = 0; i < n;i++) ans += po[gcd(i, n)];
        ans2 = ans;
        if(n & 1) ans2 += n*po[(n+1)/2];
        else ans2 += n/2*(po[n/2+1] + po[n/2]);
        printf("%lld %lld\n", ans/n, ans2/(2*n));
    }
    return 0;
}

ACM – 置换

终于搞明白置换了,可喜可贺。建议不要看屈的离散数学,看白书即可,通俗易懂。

我在这里简单阐述一下,当然也是依据李大大的书。

置换

置换就是把n个元素全排列,置换可以定义乘法。
循环就是置换的移位。例如:

1 2 3 4 5
3 5 1 4 2

即为(1 3)(2 5)(4)

其中,(1 3)通过这个置换发现形成一个循环,(2 5)通过这个置换形成一个循环,(4)本身构成一个循环。

不动点

对于一个置换f,若一个着色方案s经过置换后不变,则称s为f的不动点,将f的不动点记录为C(f),则可证明等价类数目为所有C(f)的平均值,成为Burnside引理。

Polya定理

一般的,如果f分解成m(f)个循环的乘积,那么每个循环的所有格子的颜色必须相同。(因为这样才是一个不动点)。
假设涂k种颜色,则有
$$C(f) = k^{m(f)}$$
(乘法原理。循环内相同,循环间可以不同)。
代入Burnside引理之后得到Polya定理:等价类的个数等于所有置换f的$k^{m(f)}$的平均数。

ACM – Uva10375 – 组合数公式

有些匪夷所思的题目。。注释部分加上就WA,不加就AC。。

推公式,因为$$C(n,k) = C(n,k-1) * (n-k+1)/k$$
所以$$ans = \frac{C(n, k)}{C(r, s)}\qquad$$改成递推即可。

#include <bits/stdc++.h>
using namespace std;
// 大数,内存处理
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(a, -1, sizeof(a))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
const double PI = acos(-1.0);
#define CR printf("\n")
// 调试用
    template <class Type>
void debug(Type a[], int len)
{
    for(int i = 0; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
int main()
{
#ifdef DEBUG
    freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    int p, q, r, s;
    double ans = 1.0;
    while(scanf("%d%d%d%d", &p, &q, &r, &s) != EOF)
    {
        ans = 1.0;
        // if(p - q > q) q = p - q;
        // if(r - s > s) s = r - s;
        for(int i = 1; i <= q || i <= s; i++)
        {
            if(i <= q) ans = ans * (p-i+1) / i;
            if(i <= s) ans = ans * i / (r-i+1);
        }
        printf("%.5lf\n", ans);
    }
    return 0;
}

ACM – Uva10105 – 组合数

基本上是组合数裸题。。

给出$(x_1+x_2+x_3….x_k)^n$,要求计算$x_1^{n_1}x_2^{n_2}…x_k^{n_k}$的系数。

思想就是从一个算式中取出$n_k$,即$C_n^{n_k}$,然后减去$n_k$,如果直接相乘则会重复。

#include <bits/stdc++.h>
using namespace std;
// 大数,内存处理
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(a, -1, sizeof(a))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
const double PI = acos(-1.0);
#define CR printf("\n")
// 调试用
    template <class Type>
void debug(Type a[], int len)
{
    for(int i = 0; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
const int maxn = 15;
int a[maxn];
int C[maxn][maxn];
void init()
{
    for(int i = 0; i < maxn; i++)
    {
        C[i][0] = C[i][i] = 1;
        for(int j = 1; j < i; j++) C[i][j] = C[i-1][j] + C[i-1][j-1];
    }
}
int main()
{
#ifdef DEBUG
    // freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    int n, k;
    init();
    while(~scanf("%d%d", &n, &k))
    {
        for(int i = 0; i < k;i ++) scanf("%d", &a[i]);
        int ans = 1;
        for(int i = 0; i < k; i++) {
            ans *= C[n][a[i]];
            n -= a[i];
        }
        printf("%d\n", ans);
    }
    return 0;
}

ACM – UVA10308 – 无根树转有根树

比较莫名奇妙的题目,明明是搜索题目居然放在了数学分类,完全找不到数学的影子。。

利用vector,遍历树,找出最大的子树路径,然后与次大的子树路径相加即为答案。

因为图表示这方面太渣,基本上抄袭了别人的代码= =

#include <bits/stdc++.h>
using namespace std;
// 大数,内存处理
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(a, -1, sizeof(a))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
const double PI = acos(-1.0);
#define CR printf("\n")
// 调试用
    template <class Type>
void debug(Type a[], int len)
{
    for(int i = 0; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
const int maxn = 1e5 + 10;
vector < pair <int, int> > node[maxn];
int ans;
int ds(int to, int from)
{
    int lmax = 0, lans = 0, lto;
    for(int i = 0; i < node[to].size(); i++)
    {
        lto = node[to].at(i).first;
        if(lto != from)
        {
            lans = ds(lto, to) + node[to].at(i).second;
            ans = max(ans, lans + lmax);
            lmax = max(lmax, lans);
        }
    }
    return lmax;
}
int main()
{
#ifdef DEBUG
    // freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    char s[20];
    bool c = true;
    int u, v, l;
    while(c)
    {
        for(int i = 0; i < maxn; i++) node[i].clear();
        while(1)
        {
            if(gets(s) == 0)
            {
                c = false;
                break;
            }
            if(s[0])
            {
                sscanf(s, "%d%d%d", &u, &v, &l);
                node[u].push_back(make_pair(v, l));
                node[v].push_back(make_pair(u, l));
            }
            else break;
        }
        ans = 0;
        ds(1, 0);
        printf("%d\n", ans);
    }
    return 0;
}