概要

比赛地址

2020 Multi-University Training Contest 2

题目

1005. New Equipments

题目大意：

给出 n 个工人和 m 台机器，第 i 个工人和第 j 台机器匹配的代价是 a[ i ] \cdot j^2 + b[ i ] \cdot j + c[ i ] ，问如何进行匹配，可以使得代价和最小。要求分别输出匹配 1 至 n 个工人的最小代价。

解题思路：

代价可以视为二次函数，且数据范围限制了系数 a 是大于 0 的，即二次函数的开口向上，这样函数就存在着最小值。

考虑 n 最大只有 50 ，所以我们可以对于每个工人的二次函数，求出与其匹配所花费代价的前 n 小的位置（方法：找出二次函数对称轴，往左往右分别找 n 个点，排序后取最小的 n 个点），直接将工人与机器连边求解即可。注意到零件的编号可能会很大，需要进行离散化处理。因为每个工人都与 n 个机器建边，所以最终一定可以达到完全匹配，最终有 n 个工人，至多 n^2 台机器，使用 spfa 的费用流即可通过。

对于题目要求的输出，即求匹配数为 1 至 n 的最小费用，我们可以在源点之前再建立一个超级源点，每次向源点连一条容量为 1、费用为 0 的边，在参与网络上继续跑费用流即可。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const long long INF = 1e18;
const int N = 5e3 + 50;
const int MAXM = 6e5 + 50;

int head[N], tot = 1;
struct Edge
{
    int nex, to, w;
    long long c;
}e[2 * MAXM];
void addedge(int a, int b, int c, long long d)
{
    e[++tot] = (Edge) {head[a], b, c, d};
    head[a] = tot;
}
void add(int a, int b, int c, long long d) {
    addedge(a, b, c, d);
    addedge(b, a, 0, -d);
}

struct MCMF {
    queue<int> q;
    int n, S, T;
    long long maxflow, mincost;
    int pre[N], last[N], vis[N], flow[N];
    long long dis[N];

    void init(int _n, int _S, int _T) {
        n = _n; S = _S; T = _T;
        maxflow = mincost = 0;
        memset(head, 0, sizeof(head));
        tot = 1;
    }
    int spfa() {
        for (int i = 1; i <= n; i++) {
            dis[i] = INF; vis[i] = 0;
        }
        dis[S] = 0; vis[S] = 1;
        flow[S] = 1e9; pre[T] = 0;
        while(!q.empty()) q.pop(); q.push(S);
        while(!q.empty())
        {
            int now = q.front();
            q.pop(); vis[now] = 0;
            for(int i = head[now]; i; i = e[i].nex)
            {
                int to = e[i].to;
                if(e[i].w && dis[to] > dis[now] + e[i].c)
                {
                    dis[to] = dis[now] + e[i].c;
                    pre[to] = now;
                    last[to] = i;
                    flow[to] = min(e[i].w, flow[now]);
                    if(!vis[to])
                    {
                        vis[to] = 1;
                        q.push(to);
                    }
                }
            }
        }
        return pre[T] > 0;
    }

    void solve() {
        while(spfa()) {
            maxflow += flow[T];
            mincost += 1LL * flow[T] * dis[T];
            for(int now = T; now != S; now = pre[now])
            {
                e[last[now]].w -= flow[T];
                e[last[now]^1].w += flow[T];
            }
        }
    }
}mcmf;

int n, m;
long long a[55], b[55], c[55];

__int128 f(int i, int j) {
    return (__int128)a[i] * j * j + b[i] * j + c[i];
}

struct Node {
    int i, j;
    bool operator < (const Node &x) const {
        return f(i, j) < f(x.i, x.j);
    }
};

vector<Node> v[55];
vector<int> all;

void discreate(vector<int> &v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}

int id(int j, vector<int> &v = all) {
    return (int)(lower_bound(v.begin(), v.end(), j) - v.begin()) + 1;
}

void solve() {
    int SS = mcmf.S, S = SS - 2;
    for (int i = 1; i <= n; i++) {
        add(SS, S, 1, 0);
        mcmf.solve();
        printf("%lld%c", mcmf.mincost, i == n ? '\n' : ' ');
    }
}

int main()
{
    int ; scanf("%d", &);
    while ($--) {
        scanf("%d%d", &n, &m);
        all.resize(0);
        for (int i = 1; i <= n; i++) {
            v[i].resize(0);
            scanf("%lld %lld %lld", &a[i], &b[i], &c[i]);
            int pos = (int)(-b[i] / (2 * a[i]));
            pos = min(pos, m);
            pos = max(pos, 1);
            for (int j = pos, cnt = 0; j <= m && cnt <= n; j++, cnt++) {
                v[i].push_back((Node){i, j});
            }
            for (int j = pos - 1, cnt = 0; j > 0 && cnt <= n; j--, cnt++) {
                v[i].push_back((Node){i, j});
            }
            sort(v[i].begin(), v[i].end());
            v[i].resize(n);
            for (Node x : v[i]) {
                all.push_back(x.j);
            }
        }
        discreate(all);
        int S = n + (int)all.size() + 1, T = S + 1, SS = T + 1;
        mcmf.init(SS, SS, T);
        for (int i = 1, sz = (int)all.size(); i <= sz; i++) {
            add(n + i, T, 1, 0);
        }
        for (int i = 1; i <= n; i++) {
            add(S, i, 1, 0);
            for (Node x : v[i]) {
                long long cost = (long long)f(i, x.j);
                int to = id(x.j) + n;
                add(i, to, 1, cost);
            }
        }
        solve();
    }
    return 0;
}

1006. The Oculus

题目大意：

定义 F_i 为斐波那契数列第 i 项，F_1=1,F_2=2,F_i=F_{i-1}+F_{i-2}(i≥3)

已知任意正整数 x 都拥有一个唯一的长度为 n 的 01 数列 b，使得

b_1\cdot F_1+b_2\cdot F_2+…+b_n\cdot F_n=x

b_n=1;\ b_i= 0\ or\ 1;\ b_i\cdot b_{i+1}=0

以这样的表示法给出 A、B、C 三个数

已知数字 C 是由 A\cdot B 的结果在这样的表示法下将某个原本是 1 的位置改成 0 得来的，问抹去的是哪个位置。

解题思路：

使用双模数哈希，预处理出斐波那契数列的前 N 项分别对 10^9+7 和 10^9+9 取模。将 (f[i],i) 作为一个 pair 放入 vector 中并排好序。

利用预处理，我们可以很方便地得到 A,B,C 代表的数对 10^9+7 和 10^9+9 取模后得到的值 x,y,z。则被除去的数应当等于 ans=x\times y-z。遍历两个 vector 中所有满足条件的 pair（f[i]=ans），如果它们的 i 相同则为答案。

AC代码：

#include <bits/stdc++.h>
using namespace std;
const int P1 = 1e9 + 7;
const int P2 = 1e9 + 9;
const int N = 1e6 + 50;
int f1[N + N], f2[N + N];
vector< pair<int, int> > ma1, ma2;

void init() {
    f1[1] = f2[1] = 1;
    ma1.push_back(make_pair(1, 1));
    ma2.push_back(make_pair(1, 1));
    f1[2] = f2[2] = 2;
    ma1.push_back(make_pair(2, 2));
    ma2.push_back(make_pair(2, 2));
    int cnt = 0;
    for (int i = 3; i < N + 1e6; i++) {
        f1[i] = (f1[i - 1] + f1[i - 2]) % P1;
        f2[i] = (f2[i - 1] + f2[i - 2]) % P2;
        ma1.push_back(make_pair(f1[i], i));
        ma2.push_back(make_pair(f2[i], i));
    }
    sort(ma1.begin(), ma1.end());
    sort(ma2.begin(), ma2.end());
}

int main()
{
    init();
    int T; scanf("%d", &T);
    while (T--) {
        int a, b, c;
        int x1 = 0, y1 = 0, z1 = 0;
        int x2 = 0, y2 = 0, z2 = 0;
        scanf("%d", &a);
        for (int i = 1, ; i <= a; i++) {
            scanf("%d", &);
            (x1 += * f1[i]) %= P1;
            (x2 += * f2[i]) %= P2;
        }
        //printf("#%d %d\n", x1, x2);
        scanf("%d", &b);
        for (int i = 1, ; i <= b; i++) {
            scanf("%d", &);
            (y1 += * f1[i]) %= P1;
            (y2 += * f2[i]) %= P2;
        }
        //printf("#%d %d\n", y1, y2);
        scanf("%d", &c);
        for (int i = 1, ; i <= c; i++) {
            scanf("%d", &);
            (z1 += * f1[i]) %= P1;
            (z2 += * f2[i]) %= P2;
        }
        int d1 = (1LL * x1 * y1 % P1 - z1 + P1) % P1;
        int d2 = (1LL * x2 * y2 % P2 - z2 + P2) % P2;
        //printf("#%d %d\n", d1, d2);
        int a1 = lower_bound(ma1.begin(), ma1.end(), make_pair(d1, -1)) - ma1.begin();
        int a2 = upper_bound(ma1.begin(), ma1.end(), make_pair(d1, P1)) - ma1.begin();
        int b1 = lower_bound(ma2.begin(), ma2.end(), make_pair(d2, -1)) - ma2.begin();
        int b2 = upper_bound(ma2.begin(), ma2.end(), make_pair(d2, P2)) - ma2.begin();
        for (int cnt1 = a1; cnt1 < a2; ++cnt1) {
            int flag = 0;
            int ans1 = ma1[cnt1].second;
            for (int cnt2 = b1; cnt2 < b2; ++cnt2) {
                int ans2 = ma2[cnt2].second;
                if (ans1 == ans2) {
                    printf("%d\n", ans1);
                    flag = 1;
                    break;
                }
            }
            if (flag) {
                break;
            }
        }
    }
    return 0;
}