牛客小白月赛36_卷王之王 题解-程序员宅基地

技术标签: 算法  c++  数据结构  竞赛 题解  

E. 皇城PK(签到)

题意:

定义,有可能获得冠军:没输过的人

题解:遍历一遍所有输赢情况,只要输过就标记一下,最后查找没有被标记的都是有可能获得冠军的人。

Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 100050;
int a[N];
void init() {
    
    for (int i = 0; i < N; i++) {
    
        a[i] = 1;
    }
}
int main()
{
    
    int n, m;
    scanf("%d%d", &n, &m);
    init();
    while (m--) {
    
        int x, y;
        cin >> x >> y;
        a[y] = 0;
    }
    int count = 0;
    for (int i = 1; i <= n; i++) {
    
        if (a[i]) count++;
    }
    cout << count << endl;
    return 0;
}

F. 象棋(签到)

跑是隔一个能吃(这应该都知道吧~~~)

如果说只有一行,只要这一行超过了3个,就存在 “跑隔一个能吃” 的情况,所以一行最少能剩余2个跑。

那么同理,一列最少能剩余2个跑。所以最少能剩余4个跑。

特殊情况:

x == 1 且 y == 1,剩余1个炮

x == 1 且 y > 1,剩余2个炮

其他情况都是剩余4个炮,注意一下n, m的数据范围,记得开long long

Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    
    int _;
    cin >> _;
    while (_--) {
    
        int x, y;
        cin >> x >> y;
        if (x > y) swap(x, y);
        if (x == 1 && y == 1) cout << 1 << endl;
        else if (x == 1 && y > 1) cout << 2 << endl;
        else cout << 4 << endl;
    }
    return 0;
}

I. 四面楚歌(DFS 和 BFS 都可以)

经典DFS和BFS迷宫问题

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
char g[N][N];
bool st[N][N];

int dx[4] = {
    -1, 0, 1, 0}, dy[4] = {
    0, 1, 0, -1};
int n, m;
int cnt;
void dfs(int x, int y) {
    
    for (int i = 0; i < 4; i++) {
    
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a <= n + 1 && b >= 0 && b <= m + 1 && g[a][b] != '1') {
    
            if (g[a][b] == '0') cnt++;
            g[a][b] = '1';
            dfs(a, b);
        }
    }
}
int main()
{
    
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
    
        for (int j = 1; j <= m; j++) {
    
            cin >> g[i][j];
        }
    }
    dfs(0, 0);
    cout << cnt << endl;
    return 0;
}

H. 卷王之王

太卷了吧 …

经典线段树模板题

重点在:所有值小于等于x的数字都加上x,区间修改。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
//#define int ll
#define inf 0x3f3f3f3f
using namespace std;
int gcd(int x,int y) {
    
    if(x<y) swap(x,y);//很多人会遗忘,大数在前小数在后
    //递归终止条件千万不要漏了,辗转相除法
    return x % y ? gcd(y, x % y) : y;
}
int lcm(int x,int y) {
     return x * y / gcd(x, y); }
//------------------------ 以上是我常用模板与刷题几乎无关 ------------------------//
const int N = 100010;
int num[N << 2];

struct Node{
    
    int l, r;//左端点,右端点
    int val;//区间[l, r]的最大值
}tr[N << 2];

int n, m, x;
//由子节点的信息来计算父节点的信息
void pushup(int cur){
    
    //父节点是两个子节点的和,一直往上传值,就能使根节点是所有人的个数
    tr[cur].val = min(tr[cur << 1].val, tr[cur << 1 | 1].val);
}

//cur代表当前节点,
void build(int cur, int l, int r){
    
    //建树的初始值
    tr[cur].l = l, tr[cur].r = r;
    //如果已经是叶结点return
    if(l == r) {
    
        tr[cur].val = num[l];//如果到达叶节点就把人数赋给该节点
        return;
    }
    //否则求一下当前区间的中点
    int mid = l + r >> 1;
    //递归建立左边区间
    build(cur << 1, l, mid);
    //递归建立右边区间
    build(cur << 1 | 1, mid + 1, r);
    //将子节点的人数进行汇总,给父节点
    pushup(cur);
}

//[l, r]查询区间   cur代表当前线段树里面的端点。
int query(int cur, int ql, int qr)  {
    
    int l = tr[cur].l, r = tr[cur].r;
    if (ql > r || qr < l) return 0;
    if(ql <= l && qr >= r) return tr[cur].val;
    int mid = l + r >> 1;
    int val = 0;
    
    //判断与左边有交集
    if (ql <= mid) val += query(cur << 1, ql, qr);//求和
    //这里为什么是 qr > mid,因为划分的区间是[l, mid][mid + 1, r],所以要用>而不能=
    //判断与右边有交集
    if (qr > mid) val += query(cur << 1 | 1, ql, qr);//求和
    //返回结果
    return val;
}

//cur代表当前线段树里面的端点。tar代表要修改的位置,即目标位置
void modify(int l, int r, int cur, int val) {
    
    if (l > tr[cur].r || tr[cur].l > r) return;
    if (tr[cur].l == tr[cur].r) {
    
        tr[cur].val += val;
        return;
    }
    if (val >= tr[cur << 1].val) modify(l, r, cur << 1, val);
    if (val >= tr[cur << 1 | 1].val) modify(l, r, cur << 1 | 1, val);
    //递归完之后,要更新到父节点。
    //pushup就是更新父节点的信息
    pushup(cur);    
}

int main()
{
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> num[i];
    build(1, 1, n);
    while (m--) {
    
        cin >> x;
        if (x == 0) continue;
        modify(1, n, 1, x);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
    
        ans = query(1, i, i);
        cout << ans << ' ';
    }
    cout << endl;
    return 0;
}

C. 杨辉三角(排列组合)

a [ i ] = = C n − 1 i 即 ∑ i = 0 n − 1 i 2 × a [ i ] = = ∑ i = 0 n − 1 i 2 × C n − 1 i a[i] == C_{n-1}^i 即 \sum_{i = 0}^{n - 1} i^2 × a[i] == \sum_{i = 0}^{n - 1} i^2 × C_{n-1}^i a[i]==Cn1ii=0n1i2×a[i]==i=0n1i2×Cn1i

已知: ∑ i = 0 n C n i = 2 n \sum_{i=0}^{n}C_n^i = 2^n i=0nCni=2n k C n k = n C n − 1 k − 1 kC_n^k = nC_{n-1}^{k-1} kCnk=nCn1k1

∑ i = 0 n − 1 i 2 × C n − 1 i \sum_{i = 0}^{n - 1} i^2 × C_{n-1}^i i=0n1i2×Cn1i

= ∑ i = 0 n − 1 i × i × C n − 1 i =\sum_{i = 0}^{n - 1} i × i × C_{n-1}^i =i=0n1i×i×Cn1i

= ∑ i = 0 n − 1 i × ( n − 1 ) × C n − 2 i − 1 = \sum_{i=0}^{n-1} i × (n-1) × C_{n-2}^{i-1} =i=0n1i×(n1)×Cn2i1

= ( n − 1 ) × ∑ i = 0 n − 1 ( i − 1 + 1 ) × C n − 2 i − 1 =(n-1) × \sum_{i=0}^{n-1}(i-1+1)×C_{n-2}^{i-1} =(n1)×i=0n1(i1+1)×Cn2i1

= ( n − 1 ) × ∑ i = 1 n = 1 C n − 2 i − 1 + ( n − 1 ) × ∑ i = 1 n − 1 ( i − 1 ) C n − 2 i − 1 =(n-1) × \sum_{i=1}^{n=1}C_{n-2}^{i-1}+(n-1)×\sum_{i=1}^{n-1}(i-1)C_{n-2}^{i-1} =(n1)×i=1n=1Cn2i1+(n1)×i=1n1(i1)Cn2i1

= ( n − 1 ) ( C n − 2 0 + C n − 2 1 + C n − 2 2 + . . . + C n − 2 n − 1 + C n − 2 n − 2 ) + ( n − 1 ) [ ( n − 2 ) C n − 3 0 + ( n − 2 ) C n − 3 1 + . . . + ( n − 2 ) C n − 3 n − 3 ] =(n-1)(C_{n-2}^0+C_{n-2}^1+C_{n-2}^2+...+C_{n-2}^{n-1}+C_{n-2}^{n-2}) + (n-1)[(n-2)C_{n-3}^0+(n-2)C_{n-3}^1+...+(n-2)C_{n-3}^{n-3}] =(n1)(Cn20+Cn21+Cn22+...+Cn2n1+Cn2n2)+(n1)[(n2)Cn30+(n2)Cn31+...+(n2)Cn3n3]

= ( n − 1 ) ∑ i = 0 n − 2 C n − 2 i + ( n − 1 ) ( n − 2 ) ∑ i = 0 n − 3 C n − 3 i =(n-1)\sum_{i=0}^{n-2}C_{n-2}^{i} + (n-1)(n-2)\sum_{i=0}^{n-3}C_{n-3}^i =(n1)i=0n2Cn2i+(n1)(n2)i=0n3Cn3i

= ( n − 1 ) 2 n − 2 + ( n − 1 ) ( n − 2 ) 2 n − 3 =(n-1)2^{n-2} + (n-1)(n-2)2^{n-3} =(n1)2n2+(n1)(n2)2n3

= ( n − 1 ) ( 2 n − 2 + ( n − 2 ) 2 n − 3 ) =(n-1)(2^{n-2}+(n-2)2^{n-3}) =(n1)(2n2+(n2)2n3)

= ( n − 1 ) ( 2 n − 2 + n 2 n − 3 − 2 n − 2 ) =(n-1)(2^{n-2}+n2^{n-3}-2^{n-2}) =(n1)(2n2+n2n32n2)

= n ( n − 1 ) 2 n − 3 n(n-1)2^{n-3} n(n1)2n3

#include<bits/stdc++.h>
#define int ll
typedef long long ll;
using namespace std;
const int MOD = 99824353;
// a^k
int qmi(int a, int k) {
    
   //注意k的取值范围,如果k能取到0,这行就要,如果取不到0,这行就不需要
//     if (!k) return 0;//1^0 mod 1=0
   int res = 1;
   while (k) {
    
       if (k & 1) res = res * a % MOD;
       a = a * a % MOD;
       k >>= 1;
   }
   return res;
}
signed main()
{
    
   ios::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   
   int n;
   cin >> n;
   int ans = 0;
   if (n == 1) ans = 0;
   else if (n == 2) ans = 1;
   else ans = ((n % MOD) * ((n - 1) % MOD)) % MOD * qmi(2, n - 3) % MOD;
   cout << ans << endl;
   return 0;
}

B. 最短串

思路:

先看字符串a和b的长度,定义字符串长度长的为大串,字符串长度短的为小串。

① 判断小串是否是大串的子字符串,如果是则返回大串的长度

② 找出以字符串a为前缀,字符串b为后缀公共子串 l 1 l_1 l1,找出以字符串b为前缀,字符串a为后缀的公共子串 l 2 l_2 l2

比较公共子串的长度

ans = 字符串a长度+字符串b长度-max(公共子串 l 1 l_1 l1 长度,公共子串 l 2 l_2 l2 长度)

#include<bits/stdc++.h>
#define int ll
typedef long long ll;
using namespace std;
const int N = 1010;
string a, b;
bool eq(char a, char b) {
    
    if (a == b || a == '?' || b == '?') return true;
    else return false;
}
int mlen(string a, string b) {
    
    int len = 10010;//最坏情况是10000,a和b拼起来
    int lena = a.size(), lenb = b.size();
    for (int i = 0; i < lena; i++) {
    
        int f = 1;
        for (int j = 0; j < lenb && i + j < lena; j++) {
    
            if (!eq(a[i + j], b[j])) {
    
                f = 0;
                break;
            }
        }
        if (f) len = min(len, max(i + lenb, lena));
    }
    return len;
}
signed main()
{
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> a >> b;
    int lena = a.size(), lenb = b.size();
    //最坏的情况,二者没有公共子串
    int ans = lena + lenb;
    ans = min(ans, min(mlen(a, b), mlen(b, a)));
    cout << ans << endl;
    return 0;
}

A. 好哥哥

待更

D. 哥三好(三维DP)

f [ i ] [ j ] [ k ] : 表 示 a 有 i 元 , b 有 j 元 , c 有 k 元 时 , 他 们 请 客 的 方 案 数 f[i][j][k]:表示a有i元,b有j元,c有k元时,他们请客的方案数 f[i][j][k]aibjck
通过观察:一人一次性买三个人的单,即每个人每次给的钱:300,450,750,且均是150的倍数,所以,可以做一个预处理,都 /150。
那么分别对应,2,3,5;
下面就一顿操作,纯朴素的三维DP做法。

#include<bits/stdc++.h>
#define int ll
typedef long long ll;
using namespace std;
const int MOD = 1000000007;
const int N = 110;
int f[N][N][N];
signed main()
{
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int a, b, c;
    cin >> a >> b >> c;
    a /= 150;
    b /= 150;
    c /= 150;
    for (int i = 0; i <= 1; i++) {
    
        for (int j = 0; j <= 1; j++) {
    
            for (int k = 0; k <= 1; k++) {
    
                f[i][j][k] = 1;
            }
        }
    }
    for (int i = 0; i <= a; i++) {
    
        for (int j = 0; j <= b; j++) {
    
            for (int k = 0; k <= c; k++) {
    
                //300,450,750
                if (i >= 2) f[i][j][k] = (f[i][j][k] + f[i - 2][j][k]) % MOD;
                if (i >= 3) f[i][j][k] = (f[i][j][k] + f[i - 3][j][k]) % MOD;
                if (i >= 5) f[i][j][k] = (f[i][j][k] + f[i - 5][j][k]) % MOD;
                
                if (j >= 2) f[i][j][k] = (f[i][j][k] + f[i][j - 2][k]) % MOD;
                if (j >= 3) f[i][j][k] = (f[i][j][k] + f[i][j - 3][k]) % MOD;
                if (j >= 5) f[i][j][k] = (f[i][j][k] + f[i][j - 5][k]) % MOD;
                
                if (k >= 2) f[i][j][k] = (f[i][j][k] + f[i][j][k - 2]) % MOD;
                if (k >= 3) f[i][j][k] = (f[i][j][k] + f[i][j][k - 3]) % MOD;
                if (k >= 5) f[i][j][k] = (f[i][j][k] + f[i][j][k - 5]) % MOD;
            }
        }
    }
    cout << f[a][b][c] % MOD << endl;
    return 0;
}

G. 永不言弃(图论)

待更

J. 科学幻想(线段树)

不会

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/m0_46272108/article/details/118887226

智能推荐

Android aab打包报错(持续更新中~)_the android aab installation package error = = / l-程序员宅基地

文章浏览阅读2k次,点赞3次,收藏2次。打包aab的时候遇到一些神奇的问题:jarsigner.exefailed with exit code 1;Execution failed for task ':app:transformClassesWithDexBuilderForRelease'.;Cause: failed to decrypt safe contents entry: java.io.IOException: getSecretKey failed: Password is not ASCII_the android aab installation package error = = / lib/arm64 libpython. zip. s

使用Bootstrap框架制作响应式移动网页_根据效果图,利用boostrap完成响应式页面的设计与实现-程序员宅基地

文章浏览阅读7.5k次,点赞2次,收藏26次。Bootstrap在开发响应式移动页面方面是最流行的HTML,CSS,和JS框架。在官方网站上分别展示在CSS,Componts,还有JS的相关组件。本文详细介绍通过bootstrap框架制作一个精美的网页(内容方面参考慕课网的相关资料) 其中顶部页面的导航栏部分点击“特点”可以实现小标兰,点击“关于可以弹出介绍性的文字”图片可以实现滚动效果。最主要的功能是当页面缩放时,网页中所有的元素都能自适应_根据效果图,利用boostrap完成响应式页面的设计与实现

记共享模式的随感_共享村长经营模式-程序员宅基地

文章浏览阅读1k次。每年互联网总会有个新模式出现,从BBS,LBS,GROUP,O2O,再到现在的共享,大部分都是抄,对,就是一个抄,国外发展的不错,那就抄到国内,拿来主义嘛。 然后迅速找风投,狂补贴烧钱,反正不是自己的钱,随便砸了。 只有迅速抢占市场,跑马圈地,才能更多的融资。 做不了老大,可以做老二, 反正刷了存在感,号称有多少多少用户,就可以上市了! 上不市没关系,等合并! 没人一起合体也没关系,等收_共享村长经营模式

IE10开发中会遇到的_ie10中.catch-程序员宅基地

文章浏览阅读1k次。2012年微软做的最有诚意的一件事就是对HTML5的支持了:a) IE10对HTML5很好的支持,彻底洗刷了IE9稚嫩残缺的形象,绝大多数为Webkit优化的网页都可以完美的在IE10上运行,且性能非常的好,直接秒杀其他浏览器。做web应用,最担心的就是性能问题,特别是游戏类型的应用。在js性能被人四处诟病时,IE的表现给开发者打了一剂强心针。b) 把js提升到原生语言的地位,可以直接调用_ie10中.catch

GitHub&nbsp;使用教程图文详解_github 使用 指导图-程序员宅基地

文章浏览阅读360次。大纲:一、前言二、GitHub简介三、注册GitHub账号四、配置GitHub五、使用GitHub六、参与GitHub中其它开源项目七、总结注,GitHub官网:https://github.com/,客户端版本:gitversion 1.9.2.msysgit.0。所有软件请到这里下载:http://msysgit.github.io/。 一、前言在前面_github 使用 指导图

邻接表(链式向前星)_链式向前星的优点-程序员宅基地

文章浏览阅读892次,点赞13次,收藏6次。邻接表(链式向前星)链式向前星:用来储存边的信息的以中方法。优点:速度快,节省空间,很常用如果我们用 Vector 来建边,相当于开的是一个动态的二维数组,较数组模拟来说比较慢。有时候还卡空间(被某一道题卡崩的YMF学长:我再用Vector建边我是_链式向前星的优点

随便推点

微信小程序第二周学习博客--JS计时器,开启、暂停、继续_js 中计时器成功游戏后如何停止计时-程序员宅基地

文章浏览阅读2.6k次,点赞2次,收藏7次。目前已经是微信小程序的第二周学习,有很多知识点需要巩固、消化、记忆。js的计时器这个东西想必前端学者并不陌生,它在生产生活中也经常出现,也非常实用,今天在小程序里用它来做一个短信获取倒计时的功能、其中涉及到定时器的开启、暂停、继续html》其中设置了按钮的大小,按钮的样式和是否禁用采用数据绑定的形式来动态设置,绑定了js的事件,用来触发计时器。js》count用来动态调整倒计时数值,timerId用来当作计时器的id,因为我们要做继续计时器的功能,所以会跨函数调用计时器,直接将其设置为全_js 中计时器成功游戏后如何停止计时

CentOS 7 u盘安装_centos7获取插入的u盘序列号-程序员宅基地

文章浏览阅读362次。http://www.augsky.com/599.htmlhttp://blog.csdn.net/gaohuaid/article/details/38750283/http://www.111cn.net/sys/CentOS/63645.htm_centos7获取插入的u盘序列号

Silvaco_Atlas_LED_ledex01学习笔记_silvaco能仿真量子阱-程序员宅基地

文章浏览阅读7.3k次,点赞21次,收藏68次。# (c) Silvaco Inc., 2018go atlas ## GaN LED Device Simulation## Blue single-quantum well LED## Parameter used for this blue SQW LED#############################################################..._silvaco能仿真量子阱

深蓝学院【视觉SLAM十四讲】汇总_深蓝学院课程合集百度网盘-程序员宅基地

文章浏览阅读3.9k次,点赞4次,收藏42次。SLAM14讲汇总1、安装包及其所在位置:安装包:clion-2021.1.1、eigen-3.2.10、OpenCV、ORB_SLAM2、Pangolin、g2o、所在位置:/home/zhe/1/orb-slam和/home/zhe/Software学习记录:代码_深蓝学院课程合集百度网盘

Linux常用命令_linux 常用命令-程序员宅基地

文章浏览阅读4k次,点赞3次,收藏13次。摘要:采用命令行模式操控Linux系统非常重要。本文总结Linux常用的命令,包括命令的含义,命令的用法以及命令的拓展。关键词:命令行模式 Linux常用命令给Linux系统下达命令,即写Linux命令操控Linux系统做事情,是重要的手段之一。Linux的命令很多,不同类型或版本的Linux系统,Linux命令 在数量上和具体命令上会存在些许差异。但是,Linux常用命_linux 常用命令

layui设置table的各种背景色-程序员宅基地

文章浏览阅读1.2w次,点赞4次,收藏14次。添加以下内容到指定CSS文件,并引入项目即可生效/* 偶数行背景色 */.layui-table[lay-even] tr:nth-child(even) { /* background-color: #aaffaa; */ background-color: #eeffee;}/* 鼠标指向表格时,奇数行背景颜色 */.layui-table tbody tr:h..._layui table 背景色