[Fortuna OJ]Aug 5th – Group A 解题报告

A – 矩阵游戏

这道题看了题解之后发现就是一道 sb 题。

考虑将每一列看成一个数,发现如果忽略掉列的操作,这些数仍然满足等差的条件,所以我们只要暴力算完第一列就可以进行等差了。如果考虑列的操作,那么我们就大力暴力就行了,时间复杂度是\(O(n + m)\)。

继续阅读[Fortuna OJ]Aug 5th – Group A 解题报告

被文化课吊打 & 佛系应对新政策

文化课

回来了一个星期有余,一切都挺顺利的(特别是逃掉了寒假作业),只不过周末发了个烧,现在喉咙还是很痛。这些都算是小插曲,没什么大不了的。

在经历了几周的 OI 训练之后回到学校,感觉文化课在变得越来越简单了。除了毒瘤数学上的速度跟开飞机一样、这一段时间的作业有点跟不上之外,其他的科目都算是小清新,物理补完的天数已经可以预估出来了,化学再巩固巩固,必修二的时候,必修一的综合练习也做做。生物这种平常写题周末抱抱佛脚 80 就稳了的科目目前还不需要担心。语文比较毒瘤,随它去吧。

班上最近出了点事情,反正没触及到我的事情我基本上懒得理。触及到了估计也是些鸡毛蒜皮的小事情,反正他就喜欢管这种玩意,也管不好这种玩意。我就佛系的学习就行了。

新政策

其实刚开始我心态是很崩的,简章发布的那天我又是发烧,所以心情直接爆炸。之后细读简章,发现 WHU 只需要铜牌就可以到一本线上 40 的优惠了。这个分数不是傻逼都考得到吗?

即使明年政策会更加缩紧,我也会继续全力学。管他狼来不来,我特么就是要杀出一条血路,即使凉了我就把这套放在文化课上。我就不信一堆死老头老太太能掌握我的人生。

先这样吧,上晚自习了。

[Fortuna OJ]Mar 2nd – Group A 解题报告

今天比赛状态极差,又困、又饿,眼睛又干。

A – 拯救奶牛

我们先把问题转换为三角矩阵上两点的距离,可以类比曼哈顿距离,我们可以把距离分为纵向和横向两种来考虑。

首先是纵向。如果\((x_1,y_1)\)要到\((x_2,y_2)\),那么分下面几种情况:

  • 如果\(x_1\)和\(x_2\)的奇偶性不同,那么贡献为\(2|x_1-x_2|-1\)。
  • 如果相同,那么贡献为\(2|x_1-x_2|\)。

那么再来看横向。我们发现,如果我们把上方的三角形扩大成这样:

我们发现,这一范围内的三角形不需要额外的横向贡献,只需要计算纵向贡献即为答案。对于在同一行却不在这个区域内的三角形,横向贡献也非常好计算,做差乘二即可。

记得要对输入点进行排序。

代码

// A.cpp
#include <bits/stdc++.h>
#define pr pair<int, int>
using namespace std;
const int MAX_N = 1001000;
pr prs[MAX_N];
int n, m, si, sj;
int answer, exitI, exitJ;
int main()
{
    answer = 0x3f3f3f3f;
    scanf("%d%d%d%d", &m, &n, &si, &sj);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &prs[i].first, &prs[i].second);
    sort(prs + 1, prs + 1 + n);
    for (int i = 1; i <= n; i++)
    {
        pr pta = prs[i], ptb = make_pair(si, sj);
        if (pta.first < ptb.first)
            swap(pta, ptb);
        int jl = ptb.second, jr = ptb.second + (pta.first - ptb.first) * 2;
        int ans = (pta.first - ptb.first) << 1;
        if (pta.second >= jl && pta.second <= jr &&
            (ans < answer || (ans == answer && exitJ >= prs[i].second)))
        {
            answer = ans, exitI = prs[i].first, exitJ = prs[i].second;
            if ((pta.second & 1) != (ptb.second & 1))
                answer -= 1;
            continue;
        }
        ans += min(abs(pta.second - jl), abs(pta.second - jr));
        if (ans < answer || (ans == answer && exitJ >= prs[i].second))
            answer = ans, exitI = prs[i].first, exitJ = prs[i].second;
    }
    printf("%d %d\n%d", exitI, exitJ, answer + 1);
    return 0;
}

B – 邮递员

首先,这道题的\(w_i\)毫无卵用。我们来看这个\(w_i\)对亏损的贡献:

\[ \sum_{i=1}^{n}( i-w_{s_i} )= \frac{n(n-1)}{2}-\sum_{i=1}^{n} w_i \]

所以顺序根本不会造成影响。所以,我们来找一条最短的一笔画路径且字典序最小,方可保证答案最简。

因为题目里明显的说了(可惜我没看到,眼瞎了)

能够离开每个村子的路口的数目一定是2,4或者8。

我可真是个傻逼。

所以,用邻接表存图,然后按标号从小到大进行 DFS 写栈,最后反向弹栈输出即可。

代码

// B.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 220;
int n, m, wi[MAX_N], tmpx, tmpy, dist[MAX_N][MAX_N], tot;
stack<int> stk;
void dfs(int u)
{
    for (int i = 1; i <= n; i++)
        if (dist[u][i])
        {
            dist[u][i]--, dist[i][u]--;
            dfs(i);
        }
    stk.push(u);
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &wi[i]);
    for (int i = 1; i <= m; i++)
        scanf("%d%d", &tmpx, &tmpy), dist[tmpx][tmpy]++, dist[tmpy][tmpx]++;
    dfs(1);
    printf("%d\n", stk.size() - 1);
    while (!stk.empty())
        printf("%d ", stk.top()), stk.pop();
    return 0;
}

C – 最小密度路径

我们可以考虑设置状态\(f[i][j][k]\)为从节点\(i\)到\(j\)走了\(k\)条边的总长度,然后 Floyd 预处理,最后\(O(n)\)回答即可,傻逼题。

代码

// C.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 55, MAX_M = 1200;
int n, m, tmpx, tmpy, tmpz, f[MAX_N][MAX_N][MAX_M], dist[MAX_N][MAX_N], q;
int main()
{
    scanf("%d%d", &n, &m);
    memset(f, 0x3f, sizeof(f)), memset(dist, 0x3f, sizeof(dist));
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d", &tmpx, &tmpy, &tmpz), dist[tmpx][tmpy] = min(dist[tmpx][tmpy], tmpz);
    for (int i = 1; i <= n; i++)
        f[i][i][0] = 0;
    for (int s = 1; s <= n; s++)
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    if (f[i][j][s] > f[i][k][s - 1] + dist[k][j])
                        f[i][j][s] = f[i][k][s - 1] + dist[k][j];
    scanf("%d", &q);
    while (q--)
    {
        double ans = (double)0x3f3f3f3f;
        int i, j;
        bool flag = true;
        scanf("%d%d", &i, &j);
        for (int s = 1; s <= n; s++)
            if (1.0 * f[i][j][s] / (1.0 * s) < ans && f[i][j][s] != (double)0x3f3f3f3f)
                ans = min(ans, 1.0 * f[i][j][s] / (1.0 * s)), flag = false;
        if (flag)
            puts("OMG!");
        else
            printf("%.3lf\n", ans);
    }
    return 0;
}

 

[Fortuna OJ]Feb 26th – Group A 解题报告

A – 礼物

说实话,这就是我最薄弱的一项,且在比赛中一览无余的暴露出来了。

我们可以把这道题转换一下,可以发现,这个喜悦值毫无关系,第二题的题意即为

给一些物品\(a_i\),每次操作有\(p_i\)的概率可能出现,求要使所有物品出现的期望操作次数。

考虑物品的个数很少,可以进行状压,压缩到\(S\)。对于每一个出现过物品\(i\)的情况,都可以从没有出现过的状态转移过来,即S^(1<<(i - 1))。对之前的情况乘上一个\(p_i\)即为这一部分的贡献。之后,因为\(\sum_{i} {p_i} \neq 1\),所以存在操作无效的情况,也就是\((1-\sum_{i\in S} p_i)*E_S\)。之后加上操作次数\(1\),式子全貌为:

\[ E_S = (\sum_{i\in S} p_i*E_{S’}) + (1-\sum_{i\in S} p_i)*E_S + 1 \]

移项合并可得:

\[ (\sum_{i\in S} p_i)*E_S = (\sum_{i\in S} p_i*E_{S’}) + 1 \\ E_S = \frac{(\sum_{i\in S} p_i*E_{S’}) + 1}{\sum_{i\in S} p_i} \]

代码

// A.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 21;
int n, wi[MAX_N];
long long ans1;
double pi[MAX_N], dp[(1 << 20)];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lf%d", &pi[i], &wi[i]), ans1 += wi[i];
    for (int stat = 0; stat < (1 << n); stat++)
    {
        double psum = 0, ans = 0;
        for (int i = 1; i <= n; i++)
            if (stat & (1 << (i - 1)))
            {
                int prestat = stat ^ (1 << (i - 1));
                psum += pi[i];
                ans += pi[i] * dp[prestat];
            }
        if (psum != 0)
            dp[stat] = (ans + 1) / psum;
    }
    printf("%lld\n%.3lf", ans1, dp[(1 << n) - 1]);
    return 0;
}

B – 通讯

啊,我*。

这道题很水,不讲。

代码

/// B.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 100400, MAX_M = 1e5 + 2000;
int head[MAX_N], current, dfn[MAX_N], low[MAX_N], tot, st[MAX_N], hd, aff[MAX_N];
int totp, n, m, tmpx, tmpy, tmpz, ufs[MAX_N], dist[MAX_N];
bool inst[MAX_N];
struct edge
{
    int to, nxt, weight, from;
    bool operator<(const edge &e) const { return weight > e.weight; }
} edges[MAX_M << 1];
int find(int x) { return (ufs[x] == x) ? x : ufs[x] = find(ufs[x]); }
void unite(int x, int y)
{
    if (find(x) != find(y))
        ufs[find(x)] = find(y);
}
int addpath(int u, int v, int weight)
{
    edges[current].to = v, edges[current].nxt = head[u];
    edges[current].from = u;
    edges[current].weight = weight, head[u] = current++;
    return current - 1;
}
void tarjan(int u)
{
    inst[u] = true, st[++hd] = u;
    dfn[u] = ++tot, low[u] = dfn[u];
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (dfn[edges[i].to] == 0)
            tarjan(edges[i].to), low[u] = min(low[u], low[edges[i].to]);
        else if (inst[edges[i].to])
            low[u] = min(low[u], dfn[edges[i].to]);
    if (dfn[u] == low[u])
    {
        int j;
        totp++;
        do
        {
            j = st[hd], aff[j] = totp;
            inst[j] = false;
        } while (st[hd--] != u);
    }
}
int main()
{
    while (scanf("%d%d", &n, &m) && n != 0 && m != 0)
    {
        memset(dist, 0x3f, sizeof(dist));
        memset(st, 0, sizeof(st)), memset(dfn, 0, sizeof(dfn)), hd = 0;
        for (int i = 1; i <= 2 * n; i++)
            ufs[i] = i;
        memset(head, -1, sizeof(head)), memset(aff, 0, sizeof(aff));
        totp = n, current = 0, tot = 0;
        for (int i = 1; i <= m; i++)
            scanf("%d%d%d", &tmpx, &tmpy, &tmpz), addpath(tmpx + 1, tmpy + 1, tmpz);
        tarjan(1);
        for (int i = 1; i <= n; i++)
            for (int e = head[i]; e != -1; e = edges[e].nxt)
                if (aff[i] != aff[edges[e].to])
                    dist[aff[edges[e].to]] = min(dist[aff[edges[e].to]], edges[e].weight);
        long long ans = 0;
        for (int i = n + 1; i <= totp; i++)
            if (aff[1] != i)
                ans += dist[i];
        printf("%lld\n", ans);
    }
    return 0;
}

C – 奇袭

这道题来自于 Codeforces,画风十分一至。

首先转换题意,这道题提示了每一个横纵坐标都只会存在一个点,求长为\(len\)且纵坐标最大最小值也为\(len\)的区间个数。我们可以用分治来搞一搞。首先定一个区间\([l,r]\),中点为\(mid\)。我们来探索跨这两个小区间的几种情况。

首先,我们在分类讨论之前设定几个数组:

  1. 设\(minl[i]\)为区间\([i,mid]\)的最小值,\(maxl[i]\)为区间\([i,mid]\)的最大值;

  2. 设\(minr[i]\)为区间\([mid+1,i]\)的最小值,\(maxr[i]\)为区间\([mid+1,i]\)的最大值。

那么,我们可以讨论跨越的情况:

  1. 最值都在左、右同一个区间内

  2. 最值分别在两个不同的区间

第一种情况比较好解决,在左区间的情况下:枚举一个左端点\(i\),可以根据最值之差算出右端点,进行检查并计数。

第二种稍稍麻烦一点:跨区间要考虑最值的两种分布方式,我们以最小值在左侧,最大值在右侧为例,假设有个点符合条件:

\[ maxr[j]-minl[i] = j-i \\ \text{移项得} \\ maxr[j]-j=minl[i]-i \]

可以枚举断点,把计算内容放到桶里去(注意负数,加上数域偏移),然后用两个指针判断合法区间,左端指针减一,右指针加一。

代码

// C.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 50200, NUM_DOMAIN = 6e5;
pair<int, int> prs[MAX_N];
int arr[MAX_N], n, maxl[MAX_N], maxr[MAX_N], minl[MAX_N], minr[MAX_N], bucket[2 * NUM_DOMAIN + 1];
long long answer = 0;
void dq(int l, int r)
{
    if (l == r)
    {
        answer++;
        return;
    }
    int mid = (l + r) >> 1;
    // preprocessing;
    minl[mid] = arr[mid], maxl[mid] = arr[mid];
    maxr[mid + 1] = arr[mid + 1], minr[mid + 1] = arr[mid + 1];
    for (int i = mid - 1; i >= l; i--)
        minl[i] = min(minl[i + 1], arr[i]), maxl[i] = max(maxl[i + 1], arr[i]);
    for (int i = mid + 2; i <= r; i++)
        maxr[i] = max(maxr[i - 1], arr[i]), minr[i] = min(minr[i - 1], arr[i]);
    // make judges;
    // at the left:
    for (int i = mid; i >= l; i--)
    {
        int j = i + (maxl[i] - minl[i]);
        if (j > mid && j <= r && minr[j] > minl[i] && maxr[j] < maxl[i])
            answer++;
    }
    // at the right;
    for (int i = mid + 1; i <= r; i++)
    {
        int j = i - (maxr[i] - minr[i]);
        if (j <= mid && j >= l && minl[j] > minr[i] && maxl[j] < maxr[i])
            answer++;
    }
    // in the middle;
    // min|max:
    int ptr1 = mid + 1, ptr2 = mid;
    for (int i = mid; i >= l; i--)
    {
        while (minr[ptr2 + 1] > minl[i] && ptr2 < r)
            ptr2++, bucket[maxr[ptr2] - ptr2 + NUM_DOMAIN]++;
        while (maxl[i] > maxr[ptr1])
        {
            bucket[maxr[ptr1] - ptr1 + NUM_DOMAIN]--, ptr1++;
            if (ptr1 > r)
                break;
        }
        if (ptr1 > r)
            break;
        if (ptr1 <= ptr2)
            answer += bucket[minl[i] - i + NUM_DOMAIN];
    }
    for (int i = mid; i >= l; i--)
        bucket[minl[i] - i + NUM_DOMAIN] = 0;
    for (int i = mid + 1; i <= r; i++)
        bucket[maxr[i] - i + NUM_DOMAIN] = 0;
    // max|min:
    ptr1 = mid,
    ptr2 = mid + 1;
    for (int i = mid + 1; i <= r; i++)
    {
        while (minl[ptr2 - 1] > minr[i] && ptr2 > l)
            ptr2--, bucket[maxl[ptr2] + ptr2 + NUM_DOMAIN]++;
        while (maxr[i] > maxl[ptr1])
        {
            bucket[maxl[ptr1] + ptr1 + NUM_DOMAIN]--, ptr1--;
            if (ptr1 < l)
                break;
        }
        if (ptr1 < l)
            break;
        if (ptr2 <= ptr1)
            answer += bucket[minr[i] + i + NUM_DOMAIN];
    }
    for (int i = mid + 1; i <= r; i++)
        bucket[minr[i] + i + NUM_DOMAIN] = 0;
    for (int i = mid; i >= l; i--)
        bucket[maxl[i] + i + NUM_DOMAIN] = 0;
    dq(l, mid), dq(mid + 1, r);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &prs[i].first, &prs[i].second);
    for (int i = 1; i <= n; i++)
        arr[prs[i].first] = prs[i].second;
    dq(1, n);
    printf("%lld", answer);
    return 0;
}