首页 > 其他分享 >20230120

20230120

时间：2024-01-21 15:44:50浏览次数：29  
标签：return cur int rep define 20230120 MOD

A. 真实排名

分类 当前选手是否被操作，组合

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)
{
	if (a > b)
		return a;
	return b;
}
int min(int a, int b)
{
	if (a < b)
		return a;
	return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 998244353;
const int N = 2e5 + 10;

// bool st;
int n, m;
int a[N];
vector<int> vec;
int fct[200009], divfct[200009];
int qpow(int a, int b)
{
	int ans = 1;
	while (b)
	{
		if (b & 1)
			ans = (ans * a) % MOD;
		a = (a * a) % MOD;
		b /= 2;
	}
	return ans;
}
void init()
{
	fct[0] = 1;
	for (int i = 1; i <= 200000; i++)
		fct[i] = (fct[i - 1] * i) % MOD;
	divfct[200000] = qpow(fct[200000], MOD - 2);
	for (int i = 200000 - 1; i >= 0; i--)
		divfct[i] = (divfct[i + 1] * (i + 1)) % MOD;
}
int C(int x, int y)
{
	if (x < 0 || y < 0 || x < y)
		return 0;
	if (x == y || y == 0)
		return 1;
	else
		return fct[x] * divfct[x - y] % MOD * divfct[y] % MOD;
}
// bool en;

int get(int x)
{
	return upper_bound(ALL(vec), x) - vec.begin();
}

void solve()
{
	init();
	cin >> n >> m;
	rep(i, 1, n)
	{
		cin >> a[i];
		vec.push_back(a[i]);
	}
	sort(ALL(vec));
	rep(i, 1, n)
	{
		if (a[i] == 0)
		{
			cout << (C(n - 1, m) + C(n - 1, m - 1)) % MOD << endl;
			continue;
		}
		cout << (C(get((a[i] - 1) / 2) + n - get(a[i] - 1) - 1, m) + C(get(a[i] - 1) + n - get(a[i] * 2 - 1), m - get(a[i] * 2 - 1) + get(a[i] - 1))) % MOD << endl;
	}
}

signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	// cerr<<(&en-&st)/1024.0/1024.0<<endl;
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int testcase = 1;
	// cin >> testcase;
	while (testcase--)
		solve();
	return 0;
}

B. 树的重心

\(dp_{i,j}\) 表示考虑到 \(i\) 这个点，子树内选择 \(j\) 个点，\(i\) 必须选的方案数

有2个重心则要保证左右的节点个数一样，则 \(res=\sum dp_{rt_1,i} \cdot dp_{rt_2,i}\)

只有一个重心时则要保证每个子树选择的点的个数小于总点数的一半

正难则反，计算不合法的方案数，枚举最大的子树和选择的个数，回撤背包

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b) {
    if (a > b)
        return a;
    return b;
}
int min(int a, int b) {
    if (a < b)
        return a;
    return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 10007;
const int N = 5e3 + 10;

// bool st;
int n;
vector<int> g[N];
int siz[N];
int dp[N][N], f[N], rec[N];
int rt = 0, cur = INF, rtt = 0;
// bool en;

void getrt(int x, int fa) {
    siz[x] = 1;
    int mx = 0;
    for (auto v : g[x]) {
        if (v == fa)
            continue;
        getrt(v, x);
        siz[x] += siz[v];
        mx = max(mx, siz[v]);
    }
    mx = max(mx, n - siz[x]);
    if (mx < cur) {
        cur = mx;
        rt = x;
        rtt = 0;
    } else if (mx == cur) {
        rtt = x;
    }
}

void dfs(int x, int fa) {
    siz[x] = 1;
    dp[x][1] = 1;
    for (auto v : g[x]) {
        if (v == fa)
            continue;
        dfs(v, x);
        siz[x] += siz[v];
        // memset(rec, 0, sizeof(rec));
        per(i, siz[x], 1) {
            rep(j, 1, min(siz[v], i - 1)) { (dp[x][i] += dp[x][i - j] * dp[v][j] % MOD) %= MOD; }
        }
        // memcpy(dp[x], rec, sizeof(rec));
    }
    // rep(i, siz[x], 1) cerr<<x<<' '<<i<<
}

void solve() {
    cin >> n;
    rep(i, 1, n - 1) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    getrt(1, 0);
    if (!rtt) {
        dfs(rt, 0);
        int res = 0;
        rep(i, 1, n)(res += dp[rt][i]) %= MOD;
        for (auto v : g[rt]) {
            memcpy(f, dp[rt], sizeof(f));
            rep(i, 1, n) {
                rep(j, 1, min(siz[v], i - 1)) { f[i] = (f[i] - f[i - j] * dp[v][j] % MOD + MOD) % MOD; }
            }
            rep(i, 1, n)(f[i] += f[i - 1]) %= MOD;
            rep(i, 1, siz[v]) { res = (res - f[i] * dp[v][i] % MOD + MOD) % MOD; }
        }
        cout << res % MOD << endl;
    } else {
        // cerr << "flag" << endl;
        dfs(rt, rtt);
        dfs(rtt, rt);
        int res = 0;
        rep(i, 1, n) { res = (res + dp[rt][i] * dp[rtt][i] % MOD) % MOD; }
        cout << res << endl;
    }
}

signed main() {
    freopen("center.in", "r", stdin);
    freopen("center.out", "w", stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--) solve();
    return 0;
}

C. 匹配

考虑任意一个完美匹配

如果这个匹配已经合法则输出

否则这个匹配与合法匹配异或后一定会得到1个边权异或和为1的偶环，所以只要找到这个偶环即可

设 \(x,x+n\) 分别匹配，那么可以缩点到 \(x\)

对于原图 \((y,x+n)\rightarrow (x,y)\) 边权为 \((x,x+n),(x+n,y)\) 的异或和

只要在新的图中找一个边权异或和为1的环即可 拆点bfs

// Author: xiaruize
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b) {
    if (a > b)
        return a;
    return b;
}
int min(int a, int b) {
    if (a < b)
        return a;
    return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 5e2 + 10;

// bool st;
int n, m;
struct edge {
    int v, w, id;
};
bool vis[N];
vector<edge> g[N];
vector<pii> vec[N];
int mch[N], col[N], id[N];
// bool vis[N];
int dis[N][2];
pii pre[N][2];
int tmp[N];
// bool en;

bool hungary(int x) {
    if (vis[x])
        return false;
    vis[x] = true;
    for (auto v : g[x]) {
        if (!mch[v.v] || hungary(mch[v.v])) {
            mch[v.v] = x;
            col[v.v] = v.w;
            id[v.v] = v.id;
            return true;
        }
    }
    return false;
}

void solve() {
    memset(mch, 0, sizeof(mch));
    memset(vis, 0, sizeof(vis));
    memset(col, 0, sizeof(col));
    cin >> n >> m;
    rep(i, 1, n) {
        g[i].clear();
        vec[i].clear();
    }
    rep(i, 1, m) {
        int u, v, w;
        cin >> u >> v >> w;
        v -= n;
        g[u].push_back({ v, w, i });
    }
    rep(i, 1, n) {
        memset(vis, 0, sizeof(vis));
        hungary(i);
    }
    bool tot = false;
    rep(i, 1, n) {
        if (!mch[i]) {
            cout << "-1" << endl;
            return;
        }
        tot ^= col[i];
    }
    if (!tot) {
        rep(i, 1, n) cout << id[i] << ' ';
        cout << endl;
        return;
    }
    rep(i, 1, n) {
        for (auto v : g[i]) {
            vec[i].push_back({ mch[v.v], v.w ^ col[v.v] });
        }
    }
    vector<pii> res;
    rep(i, 1, n) {
        memset(dis, 0, sizeof(dis));
        memset(pre, 0, sizeof(pre));
        memset(vis, 0, sizeof(vis));
        dis[i][0] = 1;
        queue<pii> q;
        q.push({ i, 0 });
        while (!q.empty()) {
            auto [x, val] = q.front();
            q.pop();
            for (auto v : vec[x]) {
                if (!dis[v.first][val ^ v.second]) {
                    dis[v.first][val ^ v.second] = true;
                    pre[v.first][val ^ v.second] = { x, val };
                    q.push({ v.first, val ^ v.second });
                }
            }
        }
        if (!dis[i][1])
            continue;
        pii cur = { i, 1 };
        bool flag = true;
        while (cur.first != i || cur.second != 0) {
            res.push_back(cur);
            if (vis[cur.first]) {
                flag = false;
                break;
            }
            vis[cur.first] = true;
            cur = pre[cur.first][cur.second];
        }
        if (!flag) {
            res.clear();
            continue;
        }
        rep(i, 1, n) tmp[mch[i]] = i;
        reverse(ALL(res));
        rep(i, 0, res.size() - 1) {
            for (auto v : g[res[i].first]) {
                if (v.v == tmp[res[(i + 1) % res.size()].first]) {
                    id[v.v] = v.id;
                    break;
                }
            }
        }
        rep(i, 1, n) { cout << id[i] << ' '; }
        cout << endl;
        return;
    }
    cout << "-1" << endl;
    return;
}

signed main() {
    freopen("matching.in", "r", stdin);
    freopen("matching.out", "w", stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase = 1;
    cin >> testcase;
    while (testcase--) solve();
    return 0;
}

D. deadline

网络流

\(S\xrightarrow{1} \text{0类型的任务} \xrightarrow{1} \text{一段时间l} \xrightarrow{1} \text{一段时间r}\xrightarrow{1}\text{1类型的任务}\xrightarrow{1} T\)

// Author: xiaruize
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b) {
    if (a > b)
        return a;
    return b;
}
int min(int a, int b) {
    if (a < b)
        return a;
    return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

struct MF {
    struct edge {
        int v, nxt, cap, flow;
    } e[N];

    int fir[N], cnt = 0;

    int n, S, T;
    int maxflow = 0;
    int dep[N], cur[N];

    void init() {
        // cerr << "flag" << endl;
        memset(fir, -1, sizeof(fir));
        cnt = 0;
    }

    void addedge(int u, int v, int w) {
        e[cnt] = { v, fir[u], w, 0 };
        fir[u] = cnt++;
        e[cnt] = { u, fir[v], 0, 0 };
        fir[v] = cnt++;
    }

    bool bfs() {
        queue<int> q;
        memset(dep, 0, sizeof(int) * (n + 1));

        dep[S] = 1;
        q.push(S);
        while (q.size()) {
            int u = q.front();
            q.pop();
            for (int i = fir[u]; ~i; i = e[i].nxt) {
                int v = e[i].v;
                if ((!dep[v]) && (e[i].cap > e[i].flow)) {
                    dep[v] = dep[u] + 1;
                    q.push(v);
                }
            }
        }
        return dep[T];
    }

    int dfs(int u, int flow) {
        if ((u == T) || (!flow))
            return flow;

        int ret = 0;
        for (int &i = cur[u]; ~i; i = e[i].nxt) {
            int v = e[i].v, d;
            if ((dep[v] == dep[u] + 1) && (d = dfs(v, min(flow - ret, e[i].cap - e[i].flow)))) {
                ret += d;
                e[i].flow += d;
                e[i ^ 1].flow -= d;
                if (ret == flow)
                    return ret;
            }
        }
        return ret;
    }

    void dinic() {
        while (bfs()) {
            memcpy(cur, fir, sizeof(int) * (n + 1));
            maxflow += dfs(S, INF);
            // cerr << maxflow << endl;
        }
    }
} mf;

// bool st;
int n, m, k;
int t[N];
vector<int> vec[N];
// bool en;

void solve() {
    mf.init();
    cin >> n >> m >> k;
    mf.S = 0;
    mf.n = n + 2 * m + 1;
    mf.T = n + 2 * m + 1;
    rep(i, 1, n) cin >> t[i];
    rep(i, 1, k) {
        int u, v;
        cin >> u >> v;
        vec[v].push_back(u);
    }
    rep(i, 1, n) {
        if (t[i])
            mf.addedge(0, i, 1);
        else
            mf.addedge(i, n + 2 * m + 1, 1);
    }
    rep(i, 1, m) {
        mf.addedge(n + i * 2 - 1, n + i * 2, 1);
        for (auto v : vec[i]) {
            if (t[v])
                mf.addedge(v, n + i * 2 - 1, 1);
            else
                mf.addedge(n + i * 2, v, 1);
        }
    }
    mf.dinic();
    cout << mf.maxflow << endl;
}

signed main() {
    freopen("deadline.in", "r", stdin);
    freopen("deadline.out", "w", stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--) solve();
    return 0;
}

标签：return,cur,int,rep,define,20230120,MOD
From： https://www.cnblogs.com/xiaruize/p/17977836

相关文章

  • 20230120 常用动词
    Ifyoulookcarefullyyoucanseethatthepaintingrepresentsahumanfigure.如果仔细看，就会看出画上是一个人形。Ginacoveredhereyes,afraidtolook.吉娜......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99