「LGOJ」逆序对

发表于 2021-02-08 |

字数统计: | 阅读时长 ≈

概述

猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。

最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 ai>aj且 i<j 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

一眼题，归并法求逆序对

记录下模版

阅读全文 »

CF

发表于 2021-02-08 |

字数统计: | 阅读时长 ≈

概述

CF #700 A-D2

27min切 A 1:26切B C做出来了，然后因为某个非常非常非常弱智的错误

2C WA5 了4发改了就过了（我直呼氧化钙

A

对于给定的字符串，分别对于奇数和偶数位置的字符串进行修改，字符串的位置从0开始，故而偶数位置的字符尽可能小，奇数位置的字符串尽可能大

显然一眼贪心，对于一个位置K，我们分类讨论一下

1.如果这个位置为奇数，且$k \ne z$ ,那么此时的最优解是$k = z$

2.如果这个位置为奇数，且$k = z$ ,那么此时的最优解是$k = y$

3.如果这个位置为偶数，且$k \ne a$ ,那么此时的最优解是$k = a$

4.如果这个位置为奇数，且$k = a$ ,那么此时的最优解是$k = $b

然后噼里啪啦一顿码就完事了

阅读全文 »

「LGOJ」数楼梯

发表于 2021-02-07 |

字数统计: | 阅读时长 ≈

题意

楼梯有 N 阶，上楼可以一步上一阶，也可以一步上二阶。

编一个程序，计算共有多少种不同的走法

link

题解

手玩一下样例和推推式子，很容易发现这是个斐波那契数列
$$
f[k]=f[k-1]+f[k-2]
$$
但是要高精度打一下，故此记录一下哈哈哈qwq

阅读全文 »

「LGOJ」2.6模拟赛

发表于 2021-02-06 |

字数统计: | 阅读时长 ≈

概述

LG冬眠营的模拟赛 sorce：90 + 50 + 0 + 0 = 140 Rank 14

还是菜了同群聚聚210 Orz

A

欧稳欧有若干不同种类的水果，用正整数来编号大小，两个大小为t的水果可以用来合成一个大小为t+1的水果。
现在给出初始的水果，欧稳欧可以任意合成，来让最大的水果尽可能大，你需要计算出这个最大的大小。

我们考虑用一个桶来存入数据（题目中的 t <= 100 可以存得下来

然后遍历一遍桶，大于2的就下一个桶++，记得%（好像这里无所谓

但是！我90！，因为我输出时是从n…1的，但是又极端情况是全部可以加起来

所以应该从n+1….1 这样子就100了qwq

阅读全文 »

「LGOJ」车站

发表于 2021-02-05 |

字数统计: | 阅读时长 ≈

题意

火车从始发站（称为第 $1$ 站）开出，在始发站上车的人数为 $a$，然后到达第 $2$ 站，在第 $2$ 站有人上、下车，但上、下车的人数相同，因此在第 $2$ 站开出时（即在到达第 $3$ 站之前）车上的人数保持为 $a$ 人。从第 $3$ 站起（包括第 $3$ 站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第 $(n-1)$ 站），都满足此规律。现给出的条件是：共有 $n$ 个车站，始发站上车的人数为 $a$ ，最后一站下车的人数是 $m$（全部下车）。试问 $x$ 站开出时车上的人数是多少？

Link

题解

第一眼考虑可以找规律推公式的

我们不妨设a为本来是人数，b为增加的人数

站台数N	1	2	3	4	5	6	…
上客数	a	b	a+b	a+2b	2a+3b	3a+5b	…
下客数	0	b	b	a+b	a+2b	2a+3b	…
总数	a	a	2a	2a+b	3a+2b	4a+4b	…

设a系数为p_{i},b系数为q_{i}

阅读全文 »

「LGOJ」信封问题／错排／放棋子

发表于 2021-02-05 |

字数统计: | 阅读时长 ≈

题意

某人写了n封信和n个信封，如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况

link

题解

我们记$D(i)$为当有i个信封的总共情况数量

特别的：
$$
D_{1}=0,D_{2}=1,D_{3}=2
$$
现在多了一个信封，那么为了错开，这个信$n$，除了他本身第$n$个信封不能放

其他都可以放，那么有$n-1$个位置可以放.那么剩下就有$D_{i-1}$种可能，所以

$$
D_{i}=(i-1)\times D_{i-1}
$$

巴特！还没完！对于一个信k,我们可以分为两种情况

阅读全文 »

hello-world

发表于 2021-02-03 |

字数统计: | 阅读时长 ≈

#include <bits/stdc++.h>
using namespace std;

int main(){ 
    printf("hello world!");
    return 0;
}

常用STL及其使用方法

发表于 2021-02-03 |

字数统计: | 阅读时长 ≈

STL

本文描述了基本的STL容器及其用法qwq

栈

#include <stack> //头文件
std::stack<int> S;
S.top()//访问顶部元素
S.pop()//弹出栈顶元素
//这里记得检测是否为empty 否则RE
S.push(x)//扔x进栈
S.size()//查询stack的大小
S.empty()//检查stack是否为空

手写

1
2
3

int S[maxn],tot;
push:S[++tot]=x;
pop:tot--;

阅读全文 »

「模板」快速排序

发表于 2021-02-03 |

字数统计: | 阅读时长 ≈

【模板】快速排序

快速排序（Quicksort）是对冒泡排序算法的一种改进。快速排序由C. A. R. Hoare在1960年提出

阅读全文 »

CSP 2020游记

发表于 2020-11-15 |

字数统计: | 阅读时长 ≈

Day - 10086

又是一年CSP，NOIP又复活了 CCF又双可以吸钱了

但是！作为一个TG初赛都过不去的

对于CCF又少收了400多块钱

Day 0

灰常紧张，然而还要搞WHK