Loading...
墨滴

小胖邵振轩

2021/08/30  阅读:48  主题:前端之巅同款

Dotcpp8月月赛题解

题解

T1 交点

这个用初中学到的一次函数的知识就可以 解决

给你两条直线,交点坐标:

这个是我的 python 的标准程序:

k1, b1 = map(float, input().split(" "))
k2, b2 = map(float, input().split(" "))

x = (b1 - b2) / (k2 - k1)
y = k1 * x + b1
print("%.2f %.2f" % (x, y))


# ----------------------------以下为数据生成器--------------------------

import random

def r():
    return random.uniform(-100100)

def data_maker(t):
    import os
    for i in range(1, t + 1):
        f = open("%i.in" % i, "w")
        f.write("%.1f %.1f\n%.1f %.1f" % (r(), r(), r(), r()))
        f.close()
        os.system("python std.py < %i.in > %i.out" % (i, i))

T2 扫雷

扫雷其实是一道四川省省选用过的题,大家可以在百度搜索[SCOI2005] 扫雷

主要是这道题也不是我选的

T3 跳舞的线

为什么这道题 ?因为 时答案超过了INT_MAX所以这道题把暴力放过去了

80分做法(暴力)

dfs从左上角到右下角,对于每一种走法都走一遍,走到终点如果拐点个数正好为 那么计数器加一(res += 1)。

全dfs后输出计数器就可以(输出res)。

python的暴力是可以得80分,但是python普遍常数大,所以有几位同学的C++/Java代码成功卡了过去。

只有一位同学用暴力卡过得了100分。

100分的假做法(打表)

考虑到 都很小,我们可以用暴力跑出一张表,这张表里记录了 时答案是多少。

因为这张表是提前算好的,所以时间复杂度为

这么说可能不直观,我放两个人的代码:

#include<stdio.h>
int main(){
 int h,w,k,r;
 scanf("%d%d%d",&h,&w,&k);
 if(h==3&&w==3&&k==2) r=2;
 else if(h==15&&w==15&&k==13) r=5889312;
 else if(h==7&&w==7&&k==3) r=50;
 else if(h==6&&w==6&&k==5) r=72;
 else if(h==2&&w==2&&k==1) r=2;
 printf("%d",r);
 return 0;
}
上面是dfs,就不放了。
int main() {
 memset(dp,-1,sizeof(dp));
 dp[15][15][20]=408980;
 dp[15][15][21]=163592;
 dp[15][15][22]=44616;
 dp[15][15][23]=12168;
 dp[15][15][24]=2028;
 dp[15][15][25]=338;
 dp[15][15][26]=26;
 dp[15][15][27]=2;
 scanf("%d%d%d",&n,&m,&k);
 if(dp[n][m][k]!=-1)    printf("%d",dp[n][m][k]);
 else    printf("%d",dfs(0,0,0));
 return 0;
}

这两位同学的代码都得到了100分,非常机智。

打表是不算作弊的,所以这两位同学的成绩有效。

100分的做法(正解)

这道题其实是一道排列组合题目。

大家先回忆一个公式:


我们先思考一个子问题:给你 个苹果, 个篮子,苹果没有编号但是篮子有编号,每一个篮子里都至少要放一个苹果,问一共有多少种放法。

这道题可以用隔板法来理解。
我们用 个隔板将苹果都隔起来,其中不允许隔板重叠(这样能保证每一个篮子里至少有一个苹果)

现在我们有 个凹槽, 个隔板,其中隔板是没有编号的。

个板子安排在 凹槽里有多少种放法?
答案是: 种放法。


我们把横着走叫0,竖着走叫1,那么走过的路径就可以用01来表示。因为整个图是 的,所以你只能横着走 步,竖着走 步。

那么拐点是什么呢?拐点就是前一个和后一个方向不一样,那么拐点为 的路径就应该是这样的:

或者:

这两种不同之处在于起始点一个是0(也就是开始就横着走),一个是1(开始就竖着走),我们按照开头是0的来举例子。

在0为开头的情况下,0的堆有 个,1个堆有 。( 表示向下取整)
大家可以分类讨论 为奇数的情况和 为偶数的情况,最后得到上面那个公式。

现在我们就有了两个问题:

  • 步放在 0的堆 里有多少种放法。
  • 步放在 1的堆 里有多少种放法。

这个我们可以通过放苹果的公式来解决这两个问题,然后用乘法原理将这两个的答案相乘。

1开头的也如法炮制,我直接放最终公式了:

python中已经实现了阶乘,所以用python实现会很简单:

import math

def c(n, m): # n 取 m 个
    return math.factorial(n) / (math.factorial(m) * math.factorial(n - m))
    
def g(a, b):
    if b > a:
        return 0
    return c(a - 1, b - 1)

def f(w, h, k):
    return g(w - 1, (k + 2) // 2) * g(h - 1, (k + 1) // 2) + g(w - 1, (k + 1) // 2) * g(h - 1, (k + 2) // 2)

print(int(f(*list(map(int, input().split(" "))))))

T4 罗马游戏

这道题难度系数太高了,我就跟大家简单说一下。

这道题 ,所以错误解能够跑过去。

100分 正解

这道题就是可并堆的模板题,大家可以看 https://oi-wiki.org/ds/pairing-heap/,这篇文章讲的是配对堆,配对堆的实现要比左偏树简单。

//
// Created by Cat-shao on 2021/8/13.
//
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 50100;


class disjointSet {
public:
    int parent[MAX_N];

    disjointSet() {
        for (int i = 0; i < MAX_N; ++i) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] == x) {
            return x;
        } else {
            return parent[x] = find(parent[x]);
        }
    }

    bool unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return false;
        }
        parent[rootY] = rootX;
        return true;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }
};


class pairingHeap {
public:
    typedef pair<intint> PII;
    class node {
    public:
        PII value;
        node *child, *brother;
        node(PII _value) {
            value = _value;
            child = brother = NULL;
        }
    };

    node *root[MAX_N];
    disjointSet s;
    bool mark[MAX_N];

    pairingHeap() {
        for (int i = 0; i < MAX_N; ++i) {
            root[i] = NULL;
        }
        memset(mark, 0sizeof(mark));
    }

    ~pairingHeap() {
//        for (int i = 0; i < MAX_N; ++i) {
//            destroy(root[i]);
//        }
    }

    void destroy(node *current) {
        if (current == NULL) {
            return;
        }
        destroy(current->child);
        destroy(current->brother);
        delete current;
    }

    node * merge(node *a, node *b) {
        if (a == NULL) {
            return b;
        }
        if (b == NULL) {
            return a;
        }
        if (a->value > b->value) { // a 小 b 大
            swap(a, b);
        }
        b->brother = a->child;
        a->child = b;
        return a;
    }

    node * mergeBrothers(node *current) {
        if (current == NULL || current->brother == NULL) {
            return current; // 只有它自己,合并个寂寞
        }
        node *a = current->brother, *b = a->brother;
        return merge(merge(current, a), mergeBrothers(b));
    }

    void mergeRoot(int x, int y) {
        if (mark[x] || mark[y]) {
            return;
        }
        int rootX = s.find(x);
        int rootY = s.find(y);
        if (rootX == rootY) {
            return;
        }
        root[rootX] = merge(root[rootX], root[rootY]);
        root[rootY] = NULL;
        s.parent[rootY] = rootX;
    }

    int pop(int index) {
        if (mark[index]) {
            return 0;
        }
        index = s.find(index);
        node *rt = root[index];
        if (rt == NULL) {
            return 0;
        }
        root[index] = mergeBrothers(rt->child);
        int res = rt->value.first;
        mark[rt->value.second] = true;
        delete rt;
        return res;
    }

};

int main()
{
    int n, m, x, y;
    char op[3];
    pairingHeap tree;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x;
        tree.root[i] = new pairingHeap::node(make_pair(x, i));
    }
    cin >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> op;
//        cout << "[DEBUG " << i << "] ";
        if (op[0] == 'M') {
            cin >> x >> y;
            tree.mergeRoot(x, y);
        } else {
            cin >> x;
            cout << tree.pop(x) << endl;
        }
    }
    return 0;
}

100分 错误解

题目看一遍就知道是并查集(不知道并查集和堆的同学可以不看这道题),其中对于每一个操作都要判断 是不是死人。

对于每一个结点都建一棵小根堆(可以用stl的priority_queue),并查集合并的时候可以跟着合并到集合的根节点(所以只有并查集的根节点有数据)。

盲目合并是会TLE的,所以我们可以随机合并或者启发式合并(小的向大的合并)。

小胖邵振轩

2021/08/30  阅读:48  主题:前端之巅同款

作者介绍

小胖邵振轩