头像

xnuohz

?


访客:25549

离线:3小时前



xnuohz
3小时前

T1[坚强的小昆虫]

题目描述

由于新冠肺炎疫情的爆发,小明养在宿舍的小昆虫已经很久都没有人管了。小昆虫已经饿的不行了,必须出来找东西吃,可是出来之后需要走出一个迷宫。小昆虫每次可以朝上、下、左、右四个方向之一走一步,且只要走出任意一条边界线即可逃出迷宫。这只小昆虫曾感染过X星的一种奇异病毒,目前还没有发现任何副作用,但是却拥有了一项特异功能,破坏障碍物。假设小昆虫在$N * M$的迷宫中,“@”代表小昆虫的初始位置,“.”代表可以通过的空地,“*”代表可以破坏的障碍物,“#”代表不可破坏的障碍物。请问小昆虫最少需要使用多少次特异功能才可以逃出迷宫?

输入描述

多组数据,第1行有1个正整数T,表示有T组数据。($T \leq 100$)
对于每组数据,第1行有两个整数$N$和$M$。($1 \leq N, M \leq 1000$)
接着$N$行,每行有一个长度为$M$的字符串,表示$N * M$的迷宫。

输出描述

输出一个整数,表示使用特异功能的最少次数。如果小昆虫不能走出迷宫,则输出-1。

示例1

样例输入

3
3 3
###
#@*
***
3 4
####
#@.*
**.*
3 3
.#.
#@#
.#.

样例输出

1
0
-1

算法

() $O()$

C++ 代码


T2[祖先]

题目描述

你的实验室中诞生了一种新的无性繁殖生物,这种生物每一个都有且仅有一个父亲(注意,其中有且仅有1号生物的父亲无法追踪到了)。为了研究方便,你定义一个生物的1级祖先即为其父亲,而其K级祖先为K-1级祖先的父亲($K \leq 2$)。例如,2级祖先即为父亲的父亲。现在你想知道一些生物的若干级父亲。

输入描述

第一行两个以空格给开的正整数$n$和$q$,表示生物总和询问次数
第二行有$n-1$个由空格隔开的正整数,$a_2, a_3, \dots, a_n$依次表示2号生物的父亲、3号生物的父亲…i号生物的父亲的编号为$a_i$。其中1号生物的父亲已经无法追踪到了。
接下来$q$行,每行两个由空格隔开的正整数$x, k$,表示询问第$x$号生物的$k$级祖先。
$n, q \leq 50000, 1 \leq a_i < i, 1 \leq x, k \leq n$

输出描述

输出$q$行,每行依次对应一个询问的答案,即第$x$号生物的$k$级祖先。如果无法追踪到该祖先,则输出0。

示例1

样例输入

5 3
1 2 3 4
5 1
1 1
5 3

样例输出

4
0
2

算法

() $O()$

C++ 代码





xnuohz
3小时前

T1[不同二叉搜索树]

题目描述

给定整型数组,用数组中的所有元素重建一颗二叉搜索树,总共能构造出多少种不同的二叉搜索树。二叉搜索树是指一棵空树或者具有下列性质的二叉树:
1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点值;
2. 若任意节点的右子树不空,则右子树上所有节点的值均大于或等于它的根节点值;
3. 若任意节点的左、右子树也分别为二叉搜索树。
提示:数组中可能有重复元素。

输入描述

第一行是一个整数$n$,表示数组长度
第二是空格分开的$n$个整数,表示数组中的元素
输入范围$0 < n \leq 800$

输出描述

一个整数,表示能构造出不同二叉搜索树的数目。若结果超过1000000007,则返回对1000000007取模的结果。

示例1

样例输入

3
1 2 1

样例输出

3

T2[最大的PK结果]

题目描述

有$n$($1 \leq n \leq 100000$)个葫芦娃,每个葫芦娃每个月都可以从其他葫芦娃那里得到不数量的hudos(葫芦王国特有的货币,hudos每月最多为1000000),每个葫芦娃去年$k$个有收到hudos可以用一个长度为$k$($3 \leq k \leq 12$)的整数数组保存,现在共有$n$个葫芦娃,任何两个葫芦娃都可以两两PK(同一个葫芦娃也可以自己与自己PK),PK时选出每月更多hudos数值组成一个新的数组,这个新数组中的最小值为$u$,求所有PK的结果$u$的最大值。

输入描述

第一行两个整数,代表葫芦娃个数$n$($1 \leq n \leq 100000$)和月数$k$($3 \leq k \leq 12$)
从第二行开始,输入$n$行长度为$k$的自然数数组(数组内每个数字均大于等于0且小于等于1000000),以空格分隔

输出描述

PK结果$u$的最大值

示例1

样例输入

6 5
5 0 3 1 2
1 8 9 1 3
1 2 3 4 5
9 1 0 3 7
2 3 0 6 3
6 4 1 7 0

样例输出

3

T3[迷宫寻宝]

题目描述

一个$N * M * L$的3D迷宫,其中藏有若干稀世宝石,迷宫中的每一格可以是道路、陷阱或者宝石,进入陷阱游戏失败(宝石清零)。每颗宝石有不同的价值,拿到宝石并返回到迷宫的起点则可以获取对应的宝石。给定一个起点,每次可以选择往相邻上、下、东、西、南、北6个方向移动一格,判断可以获取的总的宝石价值最多为多少,以及拿回这些宝石(即返回到起点)所需要的最小步数。

输入描述

第一行为三个空格分开的正整数$N$,$M$,$L$
接下来会依次展示$L$层迷宫,每层迷宫包含$N$行$M$列,每行都是以空格分开的数字。其中-2表示陷阱,-1表示迷宫起点,0表示道路,其他正整数表示宝石价值V。

数据范围:$1 \leq N, M, L \leq 30,1 \leq 宝石总颗数 \leq 10,1 \leq 单个宝石的价值V \leq 100000$

输出描述

输出两个以空格分开的整数,分别表示最多可以获取的宝石价值以及拿回这些宝石所需要的最小步数。

示例1

样例输入

2 2 2
0 3
4 -2
0 0
1 -1

样例输出

8 6

T4

题目描述

葫芦娃们正在参加一个趣味赛跑比赛,大家的出发点位于坐标第的原点$(0, 0)$,终点位于$(k, 0)$,$k$为正整数。假设小Hu现在们于坐标点$(x, y)$,他一下步只能移动到$(x+1, y+1)$或$(x+1, y)$或$(x+1, y-1)$。比赛有个与众不同的点是跑道由宽窄不一样的$n$段平行于$x$轴的道路并接而成。第$i$段跑道有两条边界,上界的两个端点为$(a[i], c[i])$和$(b[i], c[i])$,下界紧贴$x$轴,其中$a[i] < b[i], c[i] > 0$,并且对于$i > 0$,始终有$b[i-1] = a[i]$。小Hu想知道从起点到终点到底有多少种跑法,可是苦于体力脑力有限,得不出一个准确的答案,你能帮他一把吗?
Hulu-2020-9-16-T4.png

输入描述

第一行为两个空格分开的正整数$n$和$k$
接下来$n$行每行包含三个空格分隔的自然数$a[i]$,$b[i]$和$c[i]$
数据范围:
$1 \leq n \leq 100, 1 \leq k \leq 10^{18}$
$0 \leq a[i] < b[i] \leq 10^{18}$,并且$a[0] = 0, a[i] = b[i-1], a[n-1] \leq k \leq b[n-1]$
$0 \leq c[i] \leq 20$

输出描述

输出一个自然数,代表所有跑法的可能性,结果需要对$10^9+7$取余。

示例1

样例输入

4 5
0 2 3
2 3 4
3 4 0
4 6 1

样例输出

4



活动打卡代码 AcWing 1310. 数三角形

xnuohz
12小时前
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;

int n, m;

LL C(int n) {
    return (LL)n * (n - 1) * (n - 2) / 6;
}

int main() {
    cin >> n >> m;

    n ++ , m ++ ;
    LL ret = C(n * m) - m * C(n) - n * C(m);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            ret -= 2 * (LL)(__gcd(i, j) - 1) * (n - i) * (m - j);

    cout << ret;

    return 0;
}


活动打卡代码 AcWing 1309. 车的放置

xnuohz
13小时前
#include <iostream>
using namespace std;

const int N = 2010, mod = 100003;
typedef long long LL;

int a, b, c, d, k, ret;
int fact[N], infact[N];

int qmi(int a, int k) {
    int ret = 1;
    while (k) {
        if (k & 1) ret = (LL)ret * a % mod;
        k >>= 1;
        a = (LL)a * a % mod;
    }
    return ret;
}

void init() {
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i ++ ) {
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2) % mod;
    }
}

int C(int a, int b) {
    if (b > a) return 0;
    return (LL)fact[a] * infact[b] % mod * infact[a - b] % mod;
}

int P(int a, int b) {
    if (b > a) return 0;
    return (LL)fact[a] * infact[a - b] % mod;
}

int main() {
    cin >> a >> b >> c >> d >> k;

    init();

    for (int i = 0; i <= k; i ++ )
        ret = (ret + (LL)C(b, i) * P(a, i) % mod * C(d, k - i) % mod * P(a + c - i, k - i) % mod) % mod;

    cout << ret;

    return 0;
}



xnuohz
1天前
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int ret = 0;
        for (int i = 30; i >= 0; i -- ) {
            if ((m >> i & 1) != (n >> i & 1)) break;
            if (m >> i & 1) ret += 1 << i;
        }
        return ret;
    }
};


活动打卡代码 LeetCode 365. 水壶问题

xnuohz
1天前
class Solution {
public:
    bool canMeasureWater(int x, int y, int z) {
        int d = __gcd(x, y);
        return (x + y) >= z && (!z || z % d == 0);
    }
};



xnuohz
1天前
class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if (!n) return 1;
        n = min(n, 10);
        vector<int> f(n + 1);
        f[1] = 9;
        for (int i = 2; i <= n; i ++ ) f[i] = f[i - 1] * (11 - i);
        int ret = 1;
        for (int i = 1; i <= n; i ++ ) ret += f[i];
        return ret; 
    }
};


活动打卡代码 AcWing 355. 设计推特

xnuohz
1天前
#define x first
#define y second

typedef pair<int, int> PII;

class Twitter {
private:
    unordered_map<int, unordered_set<int>> user2follow;
    vector<PII> posts;
public:
    /** Initialize your data structure here. */
    Twitter() {

    }

    /** Compose a new tweet. */
    void postTweet(int userId, int tweetId) {
        posts.push_back({userId, tweetId});
    }

    /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
    vector<int> getNewsFeed(int userId) {
        vector<int> ret;
        int i = posts.size() - 1;
        while (i >= 0 && ret.size() < 10) {
            auto t = posts[i];
            if (t.x == userId || user2follow[userId].count(t.x))
                ret.push_back(t.y);
            i -- ;
        }
        return ret;
    }

    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    void follow(int followerId, int followeeId) {
        user2follow[followerId].insert(followeeId);
    }

    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    void unfollow(int followerId, int followeeId) {
        user2follow[followerId].erase(followeeId);
    }
};

/**
 * Your Twitter object will be instantiated and called as such:
 * Twitter* obj = new Twitter();
 * obj->postTweet(userId,tweetId);
 * vector<int> param_2 = obj->getNewsFeed(userId);
 * obj->follow(followerId,followeeId);
 * obj->unfollow(followerId,followeeId);
 */



xnuohz
1天前
const int INF = INT_MAX;
typedef pair<int, int> PII;

#define x first
#define y second

class SummaryRanges {
public:
    set<PII> S;

    /** Initialize your data structure here. */
    SummaryRanges() {
        S.insert({-INF, -INF}), S.insert({INF, INF});
    }

    void addNum(int x) {
        auto r = S.upper_bound({x, INF});
        auto l = r; l -- ;
        if (l->y >= x) return;
        else if (l->y == x - 1 && r->x == x + 1) {
            S.insert({l->x, r->y});
            S.erase(l), S.erase(r);
        } else if (l->y == x - 1) {
            S.insert({l->x, x});
            S.erase(l);
        } else if (r->x == x + 1) {
            S.insert({x, r->y});
            S.erase(r);
        } else {
            S.insert({x, x});
        }
    }

    vector<vector<int>> getIntervals() {
        vector<vector<int>> ret;
        for (auto c: S)
            if (c.x != -INF && c.x != INF)
                ret.push_back({c.x, c.y});
        return ret;
    }
};

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges* obj = new SummaryRanges();
 * obj->addNum(val);
 * vector<vector<int>> param_2 = obj->getIntervals();
 */



xnuohz
2天前
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        for (auto &x: nums) cnt[x] ++ ;
        int n = nums.size();
        vector<int> s(n + 1, 0);
        for (auto [x, c]: cnt) s[c] ++ ;
        int i = n, t = 0;
        while (t < k) t += s[i -- ];
        vector<int> ret;
        for (auto [x, c]: cnt) if (c > i) ret.push_back(x);
        return ret;
    }
};