日常训练记录

WZB's Harem（状压dp）

关键看到20的数据范围要想到状压dp

想到状压dp就很容易做了

#include 
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;

typedef long long ll;
const int mod = 1e9 + 7;
ll dp[25][1 << 20];
int a[25][25], n;

int main()
{
    scanf("%d", &n);
    _for(i, 1, n)
        _for(j, 1, n)
            scanf("%d", &a[i][j]);
    
    ll ans = 0;
    dp[0][0] = 1;
    _for(i, 1, n)
        rep(S, 0, 1 << n)
        {
            int cnt = 0;
            _for(j, 1, n)
                if(S & (1 << (j - 1)))
                    cnt++;
            if(cnt != i) continue;

            _for(j, 1, n)
                if((S & (1 << (j - 1))) && !a[i][j])
                    dp[i][S] = (dp[i][S] + dp[i - 1][S ^ (1 << (j - 1))]) % mod;
            if(i == n) ans = (ans + dp[i][S]) % mod;
        }
    _for(i, 1, n) ans = (ans * i) % mod;
    printf("%lld\n", ans);
 
	return 0;
}

Split Game（SG函数）

sg函数的题做的有点少

　　

sg函数的值为它所有子状态中的sg函数的ｍｅｘ

意思是从0开始的最小的没有的值

如子状态的sg值有0　1　3　4

那么ｍｅｘ就是２

初始化是先手败的值为0，先手胜为非0

还有关键的一点，多个游戏看作一个游戏的sg值为子游戏的异或和

那么知道这些，这道题只需要把边界条件，也就是必败为0的部分设置好，那么要计算一个新的状态的值，就枚举所有情况，新的sg值即子游戏的异或，从而得到当前的sg值即可

#include 
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

const int N = 160;
int sg[N][N], a[N << 1];

int check(int i, int j)
{
    return i == 1 && j == 1;
}
 
int main()
{   
    memset(sg, -1, sizeof sg);
    sg[1][2] = sg[2][1] = 0;
    sg[1][3] = sg[3][1] = 0;
    _for(i, 1, 150)
        _for(j, 1, 150)
        {
            if(i == 1 && j == 1 || !sg[i][j]) continue;
            memset(a, 0, sizeof a);
            _for(k, 1, i - 1)
            {
                if(check(k, j) || check(i - k, j)) continue;
                a[sg[k][j] ^ sg[i - k][j]] = 1;
            }
            _for(k, 1, j - 1)
            {
                if(check(i, k) || check(i, j - k)) continue;
                a[sg[i][k] ^ sg[i][j - k]] = 1;
            }

            rep(k, 0, N << 1)
                if(!a[k])
                {
                    sg[i][j] = k;
                    break;
                }
        }
    
    int n, m;
    while(~scanf("%d%d", &n, &m))
        puts(sg[n][m] ? "Alice" : "Bob");

	return 0;
}

Snacks（dfs序+线段树）

挺模板的一道题，但是我犯了一个经常犯的错误，就是用dfs序的时候，下标和dfs序弄混了

初始化的时候应该赋值在dfs序的位置，询问的时候也是

#include 
#define l(k) (k << 1)
#define r(k) (k << 1 | 1)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

typedef long long ll;
const int N = 1e5 + 10;
ll t[N << 2], flag[N << 2], d[N], a[N];
int L[N], R[N], k[N], n, m, cnt;
vector g[N];

void dfs(int u, int fa, ll val)
{
    L[u] = ++cnt;
    d[cnt] = val;             //关键
    for(int v: g[u])
    {
        if(v == fa) continue;
        dfs(v, u, val + a[v]);
    }
    R[u] = cnt;
}

void up(int k)
{
    t[k] = max(t[l(k)], t[r(k)]);
}

void build(int k, int l, int r)
{
    flag[k] = 0;
    if(l == r)
    {
        t[k] = d[l];
        return;
    }
    int m = l + r >> 1;
    build(l(k), l, m);
    build(r(k), m + 1, r);
    up(k);
}

void update(int k, ll x)
{
    t[k] += x;
    flag[k] += x;
}

void down(int k)
{
    if(flag[k])
    {
        update(l(k), flag[k]);
        update(r(k), flag[k]);
        flag[k] = 0;
    }
}

void add(int k, int l, int r, int L, int R, ll x)
{
    if(L <= l && r <= R)
    {
        update(k, x);
        return;
    }
    down(k);
    int m = l + r >> 1;
    if(L <= m) add(l(k), l, m, L, R, x);
    if(R > m) add(r(k), m + 1, r, L, R, x);
    up(k);
}

ll ask(int k, int l, int r, int L, int R)
{
    if(L <= l && r <= R) return t[k];
    down(k);
    int m = l + r >> 1;
    ll res = -1e18;
    if(L <= m) res = max(res, ask(l(k), l, m, L, R));
    if(R > m) res = max(res, ask(r(k), m + 1, r, L, R));
    return res;
}

int main()
{   
    int T; scanf("%d", &T);
    int kase = 0;
    while(T--)
    {
        printf("Case #%d:\n", ++kase);
        cnt = 0;
        scanf("%d%d", &n, &m);
        _for(i, 1, n) g[i].clear();
        _for(i, 1, n - 1)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            u++; v++;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        _for(i, 1, n) scanf("%lld", &a[i]);

        dfs(1, 0, a[1]);
        build(1, 1, n);

        while(m--)
        {
            int op, x;
            scanf("%d%d", &op, &x); x++;
            if(op == 0)
            {
                ll y;
                scanf("%lld", &y);
                add(1, 1, n, L[x], R[x], -a[x] + y);
                a[x] = y;
            }
            else printf("%lld\n", ask(1, 1, n, L[x], R[x]));
        }
    }

	return 0;
}

HDU5723（最小生成树+期望）

其实是一道蛮简单的题

先用最小生成树建图，然后算出所有的点对和，除以点对数即可

算点对和就枚举每一条边的贡献即可

注意多组数据清空，注意类型转换

#include 
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

typedef long long ll;
const int N = 1e5 + 10;
struct Edge { int u, v, w; };
vector edge;
vector> g[N];
int f[N], siz[N], n, m;
ll ans, sum;

bool cmp(Edge x, Edge y)
{
    return x.w < y.w;
}

int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }

void dfs(int u, int fa)
{
    siz[u] = 1;
    for(auto x: g[u])
    {
        int v = x.first, w = x.second;
        if(v == fa) continue;
        dfs(v, u);
        ans += 1LL * w * siz[v] * (n - siz[v]);
        siz[u] += siz[v];
    }
}

int main()
{   
    int T; scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        edge.clear();
        _for(i, 1, n) f[i] = i, g[i].clear();
        while(m--)
        {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            edge.push_back({u, v, w});
        }
        sort(edge.begin(), edge.end(), cmp);

        sum = 0;
        for(auto x: edge)
        {
            int u = x.u, v = x.v, w = x.w;
            int fu = find(u), fv = find(v);
            if(fu != fv)
            {
                g[u].push_back({v, w});
                g[v].push_back({u, w});
                f[fu] = fv;
                sum += x.w;
            }
        }

        ans = 0;
        dfs(1, 0);

        double t = ans / ((double)n * (n - 1) / 2);
        printf("%lld %.2f\n", sum, t);
    }

	return 0;
}

统计子矩阵（二维前缀和+双指针）

其实挺简单的，但是可能挺久没训练了，没反应过来是双指针

先看一维的情况，如果sum[l, r] <= k 那么一定有sum[l + 1, r] <= k

也就是具有单调性，那么这时候就可以用双指针

这道题是二维的，那么用二维前缀和，两个循环枚举行，就可以转化为一维的

#include 
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

const int N = 500 + 10;
int a[N][N], s[N][N], n, m, k;

int get(int x1, int y1, int x2, int y2)
{
    return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
}

int main()
{   
    scanf("%d%d%d", &n, &m, &k);
    _for(i, 1, n)
        _for(j, 1, m)
        {
            scanf("%d", &a[i][j]);
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    
    int ans = 0;
    _for(i, 1, n)
        _for(j, i, n)
        {
            int l = 1, r = 0;
            for(; l <= m; l++)
            {
                while(r + 1 <= m && get(i, l, j, r + 1) <= k) r++;
                ans += r - l + 1;
            }
        }
    printf("%d\n", ans);
    
	return 0;
}

扫雷（建图+搜索）

这题的关键是区分单向边和双向边

我用并查集，并查集是双向边，但这题是单向边

建图后搜索即可，输出有多少个点被访问过

#include
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
map, int> mp;
const int N = 5e4 + 10;
int vis[N], x[N], y[N], r[N], n, m;
vector g[N];
 
bool check(int xx, int yy, int x1, int y1, int r)
{
	return (xx - x1) * (xx - x1) + (yy - y1) * (yy - y1) <= r * r;
}

void dfs(int u)
{
    vis[u] = 1;
    for(int v: g[u])
        if(!vis[v]) 
            dfs(v);
}
 
int main()
{
	scanf("%d%d", &n, &m);
	_for(i, 1, n)
	{
		scanf("%d%d%d", &x[i], &y[i], &r[i]);
		mp[{x[i], y[i]}] = i;
	}
	
	_for(i, 1, n)
		_for(xx, x[i] - r[i], x[i] + r[i])
			_for(yy, y[i] - r[i], y[i] + r[i])
			{
				if(!check(xx, yy, x[i], y[i], r[i])) continue;
				if(xx == x[i] && yy == y[i]) continue;
				if(mp[{xx, yy}]) g[i].push_back(mp[{xx, yy}]);
			}

	_for(i, 1, m)
	{
		int xx, yy, rr;
		scanf("%d%d%d", &xx, &yy, &rr);
		_for(x1, xx - rr, xx + rr)
			_for(y1, yy - rr, yy + rr)
			{
				if(!check(x1, y1, xx, yy, rr)) continue;
				if(mp[{x1, y1}]) dfs(mp[{x1, y1}]);
			}
	}

    int ans = 0;
    _for(i, 1, n) ans += vis[i];
	printf("%d\n", ans);
	
	return 0;
}