作者归档:Alca

[UVa10859 – Placing Lampposts]DP状态表示的转换。

该题给出N个点M条边的无向无环图,在尽量少的节点上放灯,使得所有边都被照亮,每个节点将照亮与它相连的边。在放灯数量最少的前提下要求被两盏灯同时照亮的的边数应尽量大。

该题难点在于如何同时做到放灯最少和被两栈等同时照亮的最大。

首先统一到 “求最小” 的问题中来,问题转化为:在放灯数x最少的情况下使得仅被一条个等照亮的边数c最小。

定义一个较大的数M,使其超过题目情况中 c 的和的上界,该题可定义为2000.

则把状态转换为使得 M * x + c 最小。

那么最后放灯数应该是 ans / M, 仅被一个灯照亮的边数为: ans % M

还是忍不住贴个代码。。

# include <cstdio>
# include <cstring>
# include <algorithm>
# define rep(i, n) for (int i = 0; i < n; ++i )
using namespace std;

const int M = 2000;
int n, m;

struct edge
{
    int v, next;
}e[2009];

int h[1003], tot;

void add(int a, int b)
{
    e[++tot].v = b;
    e[tot].next = h[a];
    h[a] = tot;
}

bool v[2003];
int f[2003][2];

void dfs(int x, int fa)
{
    int j;
    v[x] = true;
    f[x][0] = 0;
    f[x][1] = M;
    for (int i = h[x]; i; i = e[i].next)
    {
        j = e[i].v;
        if ( !v[j] ) dfs(j, x);
        if ( j == fa ) continue;
        f[x][1] += min(f[j][0] + 1, f[j][1]);
        f[x][0] += f[j][1] + 1;
    }
}

int main()
{
    int t, a, b;
    scanf("%d", &t);
    while ( t-- )
    {
        memset(h, 0, sizeof h);
        memset(v, false, sizeof v);
        tot = 0;
        scanf("%d%d", &n, &m);
        rep(i, m)
        {
            scanf("%d%d", &a, &b);
            add(a, b);
            add(b, a);
        }
        int ans = 0;
        rep(i, n)
            if ( !v[i] )
            {
                dfs(i, -1);
                ans += min(f[i][0], f[i][1]);
            }
        printf("%d %d %d\n", ans/M, m - ans % M, ans % M);
    }
    return 0;
}

二进制表示的集合 枚举子集 的快速方法。

令要 枚举子集 的集合为S ,每一个二进制位表示一个元素是否存在。

则可 for (int S0 = S; S0; S0 = (S0 – 1)&S )

证明:

(S0 – 1)&S必然是S的子集

因为是从最后一位开始减小,所以(S0 – 1)&S必然是最十进制数位上最靠近S0的S的自己。

故可以用(S0 – 1) & S 来生成下一个子集并得到所有S的子集。

约瑟夫环问题的递推方法

对于给出的n个人,每隔k个人退出一个,第一次退出第m个人的约瑟夫环:

首先考虑从0开始编号,从第k个开始退出的情况。

则第k人退出后,约瑟夫环变为了:给出 n – 1 个人,每隔 k 个人退出一个 新约瑟夫环问题。给新环重新编号,与旧环建立的映射为:

k+1 => 0

k+2 => 1

k – 1 => n-2

假设 n-1 个人的约瑟夫环退出的人的编号为 x , 那么该人在 n 个人的环中的编号应该是 (x + k) % n

设f[n]表示,有N个人的约瑟夫环问题,最后退出的人的编号,则由上可得到递推式:

f[n] = (f[n-1] + k) % n

那么一个人的约瑟夫环的人必然是赢家,且编号为0,即: f[1] = 0

接下来可以使用递推得到最后结果。

最后对于f[n], 因为我们考虑的是从编号为 k 的开始,而题目要求从第 m 个开始退出,则需要旋转一下。

答案为 f[n] + m +1 – k。。

# include <cstdio>
int n, m, k;
int f[10003];
int main()
{
    while ( scanf("%d%d%d", &n, &k, &m) == 3, n )
    {
        f[1] = 0;
        for (int i = 2; i <= n; ++i )
            f[i] = (f[i-1] + k) % i;
        int ans = ( f[n] + m - k + 1) % n;
        if ( ans <= 0 ) ans += n;
        printf("%d\n", ans);
    }
    return 0;
}