Merci's notes

「仲夏夜茫,七月未央」


  • 首页

  • 关于

  • 标签

  • 归档

  • 搜索

「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 |
字数统计: | 阅读时长 ≈
1
2
3
4
5
6
7
#include <bits/stdc++.h>
using namespace std;

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

常用STL及其使用方法

发表于 2021-02-03 |
字数统计: | 阅读时长 ≈

STL

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

栈

  • STL
1
2
3
4
5
6
7
8
#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

12…4>

34 日志
25 标签
RSS
GitHub E-Mail Google QQ
Creative Commons
友链
  • Manci
  • SDLTF
© 2021 Merci
由 Hexo 强力驱动
|
主题 — NexT.Pisces v5.1.4
0%