首页 > 其他分享 >2024年CodeStar年度综合评估-提高进阶组

2024年CodeStar年度综合评估-提高进阶组

时间:2024-05-18 18:19:19浏览次数:27  
标签:CodeStar const 进阶 int 2024 operator return mint mod

T3. 挑剔的美食家

作为一名挑剔的美食家,小猴对食物是很讲究的,哪怕摆在面前的只有若干香蕉和苹果,小猴依然有他的讲究。
已知目前已有 \(n\) 根香蕉和 \(m\) 个苹果,小猴制定了以下规则来决定自己的食用顺序:

  1. 每个香蕉都被认为是独特的个体,可以理解为编号为 \(1 \sim n\) 的香蕉各不同
  2. 每个苹果之间没有区别
  3. 每个时刻小猴只食用一个水果

由于小猴更喜欢香蕉,因此要求在吃第 \(i\) 个苹果之前必须已经至少吃了 \(i+k\) 个香蕉。(\(k\) 可能是负数)并对结果模 \(10^9 + 7\)。

小猴现在希望知道,满足条件的前提下,有多少种不同的食用顺序方案。
(注:两个方案是不同的,当且仅当有至少一个时刻食用了不同的水果或者不同编号的香蕉)

限制:

  • 对于 \(10\%\) 的数据:\(1 \leqslant n, m \leqslant 6\)
  • 对于 \(20\%\) 的数据:\(1 \leqslant n, m \leqslant 10\)
  • \(1 \leqslant n, m \leqslant 1000\)
  • \(-n \leqslant k \leqslant n\)

算法分析

部分分1:暴搜,用回溯法得到每个香蕉的排列

代码实现
#include <bits/stdc++.h>

using namespace std;

int n, m, k, ans;
bool vis[15];

void dfs(int a, int b) {
    if (a > n or b > m) return;
    if (a == n and b == m) {
        ans++;
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (vis[i]) continue;
        vis[i] = 1;
        dfs(a+1, b);
        vis[i] = 0;
    }
    if (a > b+k) dfs(a, b+1);
}

int main() {
    cin >> n >> m >> k;
    
    dfs(0, 0);
    
    cout << ans << '\n';
    
    return 0;
}

部分分2:计数原理
香蕉排列顺序:1. 无序版方案 2. 内部排列:分步计数,乘法原理
那么答案就是无序列版方案的 \(ans \times n!\)

代码实现
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
    ll x;
    mint(ll x=0):x((x%mod+mod)%mod) {}
    mint operator-() const {
        return mint(-x);
    }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const {
        return mint(*this) += a;
    }
    mint operator-(const mint a) const {
        return mint(*this) -= a;
    }
    mint operator*(const mint a) const {
        return mint(*this) *= a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint a) {
        return *this *= a.inv();
    }
    mint operator/(const mint a) const {
        return mint(*this) /= a;
    }
};
istream& operator>>(istream& is, mint& a) {
    return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
    return os << a.x;
}

int n, m, k;
mint ans;
bool vis[15];

void dfs(int a, int b) {
    if (a > n or b > m) return;
    if (a == n and b == m) {
        ans += 1;
        return;
    }
    dfs(a+1, b);
    if (a > b+k) dfs(a, b+1);
}

int main() {
    cin >> n >> m >> k;
    
    dfs(0, 0);
    
    for (int i = 1; i <= n; ++i) {
        ans *= i;
    }
    
    cout << ans << '\n';
    
    return 0;
}

满分做法:

dp[i][j] 表示吃了 \(i\) 个香蕉,\(j\) 个苹果的方案数(无序)

转移方程:

\( dp[i][j] = dp[i-1][j] + dp[i][j-1] \)

初值:

  • \(dp[i][0] = 1\)
  • \(dp[0][j] = 1\), 当 \(0-j \geqslant k\)

最后的答案为 \(dp[n][m] \times n!\)

代码实现
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
    ll x;
    mint(ll x=0):x((x%mod+mod)%mod) {}
    mint operator-() const {
        return mint(-x);
    }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const {
        return mint(*this) += a;
    }
    mint operator-(const mint a) const {
        return mint(*this) -= a;
    }
    mint operator*(const mint a) const {
        return mint(*this) *= a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint a) {
        return *this *= a.inv();
    }
    mint operator/(const mint a) const {
        return mint(*this) /= a;
    }
};
istream& operator>>(istream& is, mint& a) {
    return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
    return os << a.x;
}

int n, m, k;
mint dp[1005][1005];
mint ans;

int main() {
    cin >> n >> m >> k;
    
    for (int i = 0; i <= n; ++i) dp[i][0] = 1;
    for (int j = 0; j <= m and 0-j >= k; ++j) dp[0][j] = 1;
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m and i-j >= k; ++j) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    
    ans = dp[n][m];
    for (int i = 1; i <= n; ++i) {
        ans *= i;
    }
    
    cout << ans << '\n';
    
    return 0;
}

标签:CodeStar,const,进阶,int,2024,operator,return,mint,mod
From: https://www.cnblogs.com/Melville/p/18199621

相关文章

  • 20240518模拟赛
    C240518A.传送门(portal)构造一个图使得点\(1\)到\(2\)的最短路正好有\(k\)条,使构造出的图点的个数\(N\len_5\)考虑\(k=2^t\)那么可以轻松构造出如下的图对于其他的情况可以考虑二进制拆分,如\(k=10\)时为了,使最短路长度固定加入点\(9\)对\(k=10^9\),只需构造\(80\)个点,可以......
  • 【专题】2024小红书餐饮行业方法论报告合集PDF分享(附原数据表)
    原文链接:https://tecdat.cn/?p=36199原文出处:拓端数据部落公众号报告合集显示,消费者对餐饮的需求正从单一的口味体验转变为追求更高层次的情绪价值和文化价值。餐饮不仅是生活的小确幸,更成为社交、休闲和探索的重要场景。小红书凭借其真实、利他、生动、丰富的内容,成为餐饮消费......
  • 2024 年 3 月月考游记
    先咕着。2024.3.20(Day0)众所周知,某校有一种班型叫做广延班。初一的时候竞赛广延(当时就是因为这个学的信竞)没选上,所以到了初二来比whk的广延。于是乎,广延的选拔有整整\(4\)场考试\(\dots\)然后,明天是第一场。但是,如此重要的考试前,为什么还要培优上课而不是正常晚自习啊???......
  • 2024-05-17 闲话
    昨天去听了一个宣讲,晚上和5wcitation的老师吃了一个饭,收获了一个合影。吃饭的时候和刘夏雷老师交流了一个工作,通俗语言表达如下。连续学习的setting下有一个灾难性遗忘的问题。举一个具体一点的例子:现在我们有一个图片分类的任务,原先有10类,现在要扩充至20类。原先我们建......
  • 鲜花 #2 2024 年春游吐槽
    说是春游,还不如说是夏游。去的安的童话森林公园,说是童话,实际上就是种菜的。饭难吃的要死,而且工作人员的态度相当恶劣。说是下河摸鱼,实际上就是在浑水里面乱撞,而且水深的要死,根本看不到有鱼,说是放了\(300\)条鱼,实际上就没几条。水底除了泥巴就是石头,一会鞋陷进去了,一会就是磕......
  • 「游记」2024 吉林省赛和 2024 东北四省赛
    Before本文是\(2024\)中国大学生程序设计竞赛全国邀请赛(长春)暨第\(17\)届吉林省大学生设计竞赛和新建比赛的游记写的很烂写的很烂写的很烂Day0省赛报到及热身赛。\(14:00\)前报到。\(12:00\)和一名队员在校门口集合了,但另一名队员才起床。会合后打车前往东师净月校区......
  • PKUSC 2024 最短路径
    本文首发于QOJhttps://qoj.ac/blog/skip2004/blog/866大家好,我是钱哥,我来写一下PKUSC2024最短路径的题解。没有做过这个题的同学可以先自行做一做。我们下面来讲解一下如何一步步解决这个题目。subtask4首先,我们来解决第一个具有挑战性的子任务:\(m\leq2.5n\),这个点具......
  • NOIP2024模拟赛7:纯粹当下
    NOIP2024模拟赛7:纯粹当下今日挂分:95pts......T2\(T\)组数据,每组给定\(n,k,f,a_i\),一个序列\(b\)满足\(b_i\in[a_i-k,a_i]\),记\(g\)表示至多删去序列中\(f\)个数后,使得剩余所有数的\(\gcd\),求\(g\)的集合并输出.标签:转化,调和级数,前缀和.其实也有......
  • 2024.5.17
    2024.5.17【这个世界早已无法拯救,可我们还必须成为英雄。】Friday四月初十继续水数据结构。。。P3045[USACO12FEB]CowCouponsG//2024.5.17//bywhite_ice//P3045[USACO12FEB]CowCouponsG#include<bits/stdc++.h>#include<typeindex>usingnamespacestd;......
  • 2024 年春节集训 _ 第四课 - 网络流
    考虑\(EK\)算法求解最大流。每次找一条最小剩余流量\(d>0\)的\(s\rightsquigarrowt\)的路径。然后对之流下\(d\)的水。这个操作我们称之为增广,所找到的这条路径叫做增广路。一直增广到不存在任何增广路为止。发现这样的贪心策略有时是错误的。考虑反悔。连一条反边,反......