分类目录归档:ACM

[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;
}

C++构造 下一个排列 的函数

之前构造排列都是自己写…真是麻烦啊..

结果今天围观刘汝佳神犇的白书发现了一个好用的函数:

next_permutation();

可以用于可重, 或者不可重集, 寻找下一个排列.

时间复杂度尚不明.

//适用于不可重和可重集的排列.

# include <iostream>
# include <algorithm>
using namespace std;

int a[1003], n;

int main()
{
    cin >> n;
    for (int i = 0; i < n; ++i )
        cin >> a[i];
    sort(a, a+n);
    do
    {
        for(int i = 0; i < n; ++i)
            cout << a[i] << ' ';
        cout << endl;

    } while( next_permutation(a, a+n) );
    return 0;
}

LA 2965 Jurassic Remains 中途相遇法 (Meet-in-the-Middle)

给定N < 25个大写字母组成的字符串, 选择最多的传, 使得每个大写字母都能出现偶数次.

显然字母出现偶数次可以转换为: 每次异或, 最后为零. 由于只有26个英文字母, 故一个字符串可用一个int类型来表示.

直接枚举显然会超时, 故使用 中途相遇法 (Meet-in-the-Middle)

又知, 异或值为零的两个数必然完全相等.故可以使用map来维护xor值及对应使用的句子

# include <iostream>
# include <algorithm>
# include <string>
# include <map>
# define rep(x, n) for(int x = 0; x < (n); ++x)
using namespace std;

int n;

int a[30];

string s;

map <int, int> table;

int bitcount(int x)
{
    return x == 0 ? 0 : bitcount(x>>1) + (x&1);
}

int main()
{
    while ( cin >> n)
    {
        rep(i, n)
        {
            cin >> s;
            a[i] = 0;
            rep(j, s.size())
                a[i] ^= (1<<(s[j]-'A'));
        }
        table.clear();
        int n1 = n / 2;
        int  n2 = n - n1;
        //枚举前n1个元素的所有子集的xor值
        //table保存xor值为x, 包含元素最多的子集s
        rep(i, 1<<n1)
        {
            int x = 0;
            rep(j, n1) if (i & (1<<j)) x ^= a[j];
            if ( !table.count(x) || bitcount(table[x]) < bitcount(i) )
                table[x] = i;
        }
        int ans = 0;
        rep(i, 1<<n2)
        {
            int x = 0;
            rep(j, n2) if (i & (1<<j)) x ^= a[n1+j];
            if ( table.count(x) && bitcount(ans) < bitcount(table[x]) + bitcount(i) )
                ans = (i<<n1) | table[x];
        }
        cout << bitcount(ans) << endl;
        rep(i, n)
            if (ans & (1<<i))
                cout <<i+1<<" ";
        cout << endl;
    }
    return 0;
}