思路

这道题其实跟 LOJ 6002 建模方式差不多，只是加了一个二分答案来进行动态建图。见代码：

代码

// LOJ6003.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e4 + 100, INF = 0x3f3f3f3f;
int head[MAX_N], current, s, t, dep[MAX_N], cur[MAX_N], n, tot, upward[MAX_N], tag[MAX_N], unit;
struct edge
{
    int to, nxt, weight;
} edges[500010];
void addpath(int src, int dst, int weight)
{
    edges[current].to = dst, edges[current].weight = weight;
    edges[current].nxt = head[src], head[src] = current++;
}
void add(int u, int v, int w) { addpath(u, v, w), addpath(v, u, 0); }
bool bfs()
{
    queue<int> q;
    q.push(s), memset(dep, 0, sizeof(dep));
    dep[s] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (edges[i].weight > 0 && dep[edges[i].to] == 0)
                dep[edges[i].to] = dep[u] + 1, q.push(edges[i].to);
    }
    return dep[t] != 0;
}
int dfs(int u, int flow)
{
    if (u == t || flow == 0)
        return flow;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (dep[edges[i].to] == dep[u] + 1 && (edges[i].weight > 0))
        {
            int to = edges[i].to, fl = dfs(to, min(flow, edges[i].weight));
            if (fl > 0)
            {
                upward[u] = to;
                if (u != s)
                    tag[edges[i].to - unit] = true;
                edges[i].weight -= fl, edges[i ^ 1].weight += fl;
                return fl;
            }
        }
    return 0;
}
int dinic()
{
    memset(tag, false, sizeof(tag));
    int ans = 0;
    while (bfs())
    {
        for (int i = 0; i <= tot; i++)
            cur[i] = head[i];
        while (int f = dfs(s, INF))
            ans += f;
    }
    return ans;
}
bool check(int num)
{
    unit = num;
    tot = (num << 1) + 2, s = tot - 1, t = tot;
    memset(head, -1, sizeof(head)), current = 0;
    for (int i = 1; i <= num; i++)
        add(s, i, 1), add(i + num, t, 1);
    for (int i = 1; i <= num; i++)
        for (int j = 1; j * j - i <= num; j++)
            if (i < j * j - i)
                add(j * j - i, i + num, 1);
    return num - dinic() <= n;
}
int main()
{
    scanf("%d", &n);
    int l = 1, r = MAX_N - 2000, ans;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
            l = mid + 1, ans = mid;
        else
            r = mid - 1;
    }
    printf("%d\n", ans);
    check(ans);
    for (int i = 1; i <= ans; i++)
        if (!tag[i])
        {
            int p = i;
            printf("%d ", p);
            while (upward[p] && upward[p] != t && upward[p] - ans >= 0)
                printf("%d ", upward[p] - ans), p = upward[p] - ans;
            puts("");
        }
    return 0;
}

A – Binary & B – Chess

傻逼题，不分析。

C – Sum

这道题非常的有趣（精心调参之后随机化程序可以拿 90 分），正解非常的巧妙。我们可以把问题化为求\(min\{ S_{i,j} \mod P, K \leq S_{i,j} \mod P\}\)。我们先用\(O(n)\)的时间来进行前缀和的预处理，之后我们倒序处理前缀和，从后往前加入 set。在加入 set 的过程中二分查找\(s[i]+k\)和\(s[i]+k-p\)这两个目标最优解，之后记录答案即可，非常的巧妙。

// C.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 100010;
int n, k, p, ans = 0x7f7f7f7f, s[MAX_N];
set<int> st;
int main()
{
    scanf("%d%d%d", &n, &k, &p);
    for (int i = 1; i <= n; i++)
        scanf("%d", &s[i]), (s[i] += s[i - 1]) %= p;
    set<int>::iterator it;
    st.insert(s[n]);
    for (int i = n - 1; i >= 1; i--)
    {
        it = st.lower_bound(s[i] + k);
        if (it != st.end())
            ans = min(*it - s[i], ans);
        it = st.lower_bound(s[i] + k - p);
        if (it != st.end() && *it < s[i])
            ans = min(*it - s[i] + p, ans);
        st.insert(s[i]);
    }
    printf("%d", ans);
    return 0;
}

D – Jail

哦，傻逼题。——crazydave

这道题算是套路吧，用状态压缩枚举每一维符号的状态，求出最大最小值，最大值减去最小值（最小值代表着状态相反的曼哈顿贡献）即可。

// D.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1000010;
int n, d, info[MAX_N][6], st[10], ans;
void calc(int stat)
{
    int mn = (1 << 29), mx = -mn;
    for (int i = 1; i <= d; i++, stat >>= 1)
        st[i] = stat & 1;
    for (int i = 1; i <= n; i++)
    {
        int acc = 0;
        for (int j = 1; j <= d; j++)
            acc += (st[j] == 1) ? info[i][j] : -info[i][j];
        if (acc != 0)
            mn = min(mn, acc), mx = max(mx, acc);
    }
    ans = max(mx - mn, ans);
}
int main()
{
    scanf("%d%d", &n, &d);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= d; j++)
            scanf("%d", &info[i][j]);
    for (int i = 0; i < (1 << d); i++)
        calc(i);
    printf("%d", ans);
    return 0;
}

思路

好神仙啊。

这道题思路非常的巧妙。答案很容易可以知道，为

\[ ans = \lfloor \sum_{i=1}^{n} \frac{L*C*speed[i]}{maxSpeed*C} \rfloor \]

化简得：

\[ ans = \lfloor \sum_{i=1}^{n} \frac{L*speed[i]}{maxSpeed} \rfloor \]

如果我们统计括号内的实数集和的话，会出现一些只有在计算机上才会出现的恶心误差，所以我们可以考虑分开取整再求和。这里有一个小技巧，对于两个数而言：

\[ \lfloor a – b \rfloor = \begin{cases} \lfloor a \rfloor – \lfloor b \rfloor, a的小数部分 \leq b的小数部分 \\ \lfloor a \rfloor – \lfloor b \rfloor – 1, a的小数部分>b的小数部分 \end{cases} \]

在判断小数部分的时候，我们可以把小数部分之间的大小关系转化为余数之间的大小关系进行判断，答案默认减掉那个取整的1，然后用树状数组补全那些被误删的取整项。

代码

// FOJ2930.cpp
#include <bits/stdc++.h>
#define ll long long
#define lowbit(p) (p & -p)
using namespace std;
const ll MAX_N = 1e5 + 200;
ll n, l, c, spd[MAX_N], mxspd, f[MAX_N], tree[1000100];
void update(int num)
{
    num++;
    while (num <= mxspd)
        tree[num] += 1, num += lowbit(num);
}
ll sum(int num)
{
    num++;
    ll ans = 0;
    while (num)
        ans += tree[num], num -= lowbit(num);
    return ans;
}
int main()
{
    scanf("%lld%lld%lld", &n, &l, &c);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &spd[i]);
    sort(spd + 1, spd + 1 + n), mxspd = spd[n];
    for (int i = 1; i <= n; i++)
        f[i] = (l * spd[i]) / mxspd;
    update((l * spd[1]) % mxspd);
    ll prefix = f[1], ans = 0;
    for (int i = 2; i <= n; i++)
    {
        prefix += f[i];
        ans += i * f[i] - prefix - i;
        update((l * spd[i]) % mxspd);
        ans += sum((l * spd[i]) % mxspd);
    }
    printf("%lld", ans);
    return 0;
}

主要思路

这道题是一道偏思维的题，应该在巨佬眼中是那种被秒切的题吧。我们可以把三条线分成两种情况：

• 三根线平行
• 两根平行，一根垂直

通过变换\(x,y\)坐标可以标化问题，然后用 map 记录\(y\)坐标出现的次数，比较删掉一根竖线前后\(y\)坐标的变化即可作出判断。

代码

// FOJ2929.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1001000;
map<int, int> mp;
pair<int, int> pts[MAX_N];
int n, dist;
void add(int x)
{
    if (mp[x] == 0)
        dist++;
    mp[x]++;
}
void remove(int x)
{
    mp[x]--;
    if (mp[x] == 0)
        dist--;
}
bool judge()
{
    sort(pts + 1, pts + 1 + n);
    dist = 0, mp.clear();
    for (int i = 1; i <= n; i++)
        add(pts[i].second);
    if (dist <= 3)
        return true;
    int i = 1, i1 = 1;
    while (i <= n)
    {
        while (pts[i].first == pts[i1].first && i1 <= n)
            i1++;
        for (int i2 = i; i2 < i1; i2++)
            remove(pts[i2].second);
        if (dist <= 2)
            return true;
        for (int i2 = i; i2 < i1; i2++)
            add(pts[i2].second);
        i = i1;
    }
    return false;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &pts[i].first, &pts[i].second);
    if (judge())
        puts("1");
    else
    {
        for (int i = 1; i <= n; i++)
            swap(pts[i].first, pts[i].second);
        if (judge())
            puts("1");
        else
            puts("0");
    }
    return 0;
}

思路

这个模型有点儿牛逼哦。

我们先来建一个网络。我们把我们得到的\(n\)个点复制一遍，变成第\(i\)与第\(i+n\)个点。让源点全部连接点域\([1,n]\)内的点，让点域\([n+1,2n]\)内的点全部连接汇点。如果有边\((u,v)\)，连接边\((u,v+n)\)。这里面所有的边容量都是\(1\)。求最大流做差即可。

我们把网络分层（把它想成 3D 的形状），第一层是源点和原生点，第二层是复制点和汇点。这两层之间的边都相当于有向无环图里的单向边，求最大流即可知道哪些不是路径覆盖中的点。

代码

// LOJ6002.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200 * 3, INF = 0x3f3f3f3f;
int n, m, head[MAX_N], current, upward[MAX_N], s, t, dep[MAX_N], cur[MAX_N], tmpx, tmpy;
bool tag[MAX_N];
struct edge
{
    int to, nxt, weight;
} edges[6000 << 2];
void addpath(int src, int dst, int weight)
{
    edges[current].to = dst, edges[current].weight = weight;
    edges[current].nxt = head[src], head[src] = current++;
}
void add(int src, int dst, int w) { addpath(src, dst, w), addpath(dst, src, 0); }
bool bfs()
{
    memset(dep, 0, sizeof(dep));
    queue<int> q;
    q.push(s), dep[s] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (edges[i].weight > 0 && !dep[edges[i].to])
                q.push(edges[i].to), dep[edges[i].to] = dep[u] + 1;
    }
    return dep[t] != 0;
}
int dfs(int u, int flow)
{
    if (u == t || flow == 0)
        return flow;
    for (int &i = cur[u]; i != -1; i = edges[i].nxt)
        if (edges[i].weight > 0 && dep[edges[i].to] == dep[u] + 1)
        {
            int to = edges[i].to, fl = dfs(to, min(edges[i].weight, flow));
            if (fl > 0)
            {
                upward[u] = edges[i].to;
                if (u != s)
                    tag[edges[i].to - n] = true;
                edges[i].weight -= fl, edges[i ^ 1].weight += fl;
                return fl;
            }
        }
    return 0;
}
int Dinic()
{
    int ans = 0;
    while (bfs())
    {
        for (int i = 1; i <= 2 * n + 2; i++)
            cur[i] = head[i];
        while (int fl = dfs(s, INF))
            ans += fl;
    }
    for (int i = 1; i <= n; i++)
        if (!tag[i])
        {
            int p = i;
            printf("%d ", p);
            while (upward[p] && upward[p] != t)
                printf("%d ", upward[p] - n), p = upward[p] - n;
            printf("\n");
        }
    return ans;
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    s = n * 2 + 1, t = s + 1;
    for (int i = 1; i <= n; i++)
        add(s, i, 1), add(i + n, t, 1);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &tmpx, &tmpy);
        add(tmpx, tmpy + n, 1);
    }
    printf("%d", n - Dinic());
    return 0;
}