乐子atcoder日记day3

洛谷传送门 AtCoder 传送门 很不错的状压。 考虑先把最后作为答案的数聚到一起，再算它们的逆序对个数。 设 $f_S$ 为当前选的数集合为 $S$ 的答案。有转移： 选 $a_i$，答案加上之前选的比它大的数； 不选 $a_i$，此时需要把左边的数或者右边的数往中间挪一个，答案加上左右两端的最 ......

AtCoder Beginner Contest 159 https://atcoder.jp/contests/abc159 EF 是打基础的好题 D - Banned K #include <bits/stdc++.h> #define ll long long using namespace ......

4.24 虽说开始做瑞吉外卖了，但是做的基本没多少，也才配置了一下mysql的环境， idea今晚也不知道能不能装上，也才想起来周三有c++考试，要有大步的进展可能需要推迟几天了，背了一点单词，看了点数学网课……其实也没干啥事。开心点的是其实自己大一的目标已经完成了，偏科的英语四级也过了，蓝桥杯目标 ......

AtCoder Beginner Contest 158 https://atcoder.jp/contests/abc158 基础不牢，地动山摇 D - String Formation 一个小小的STL应用 #include <bits/stdc++.h> #define ll long lon ......

一、问题描述 一个正整数 N 的因子中可能存在若干连续的数字。例如 630 可以分解为 3×5×6×7，其中 5、6、7 就是 3 个连续的数字。给定任一正整数 N，要求编写程序求出最长连续因子的个数，并输出最小的连续因子序列。 二、流程设计 （1）使用循环 （2）循环要怎么用（求解因子；求解连续因 ......

ABC299 之前 . ......

A - Treasure Chest 题意 给定由 $\texttt{.}$、$\texttt{|}$、$\texttt{}$ 三种字符组成的长度为 $n$ 的字符串 $s$，保证 $\texttt{|}$ 的个数为 $2$，$\texttt{}$ 的个数为 $1$。 判断 $\texttt{*}$ ......

洛谷传送门 AtCoder 传送门 挺有意思的计数。 计数感觉很难做，不妨转成期望，期望又可以转成概率之和。 考虑枚举 $w \in [0,m-1]$，把 $> w$ 的数设为 $1$，$\le w$ 的数设为 $0$。那么期望就是所有 $w$，$a_i$ 为 $1$ 的概率之和。对于一个 $i$， ......

$$也想养老鼠捏$$ 先把当前要解决的点旋转到位置 $n$，问题不变。求 $n$ 次即可。 我们先来看两个没有结果的解法。 一就是一 我们先考虑暴力 $dp$，设 $dp_{i,mask}$ 表示当前已经安放了 $i$ 个奶酪，被喂饱的老鼠的集合为 $mask$ 的概率。容易发现 $i$ 其实就是 ......

前言 MAUI中Windows上，调用MediaPicker.Default.CapturePhotoAsync()并不能启动相机拍照。关于这个问题可以查看 https://github.com/dotnet/maui/issues/7660 ，https://github.com/dotnet/m ......

今天上来决定开始打 数颜色。 看算法标签，带个分块莫队，而且之前见的时候也是在分块专题。 看题，十分钟过去。。。。。 发现有 $O(n \log^2 n)$ 时间，$O(n)$ 空间的 CDQ 做法，显然严格优于带修莫队啊。 翻了翻题解，前面的有一个 $O(n \log n)$ 空间的树套树，然后几 ......

【MAUI Blazor踩坑日记】1.关于图标的处理 前言 本系列文章，默认你已经踏上了MAUI Blazor的贼船，并且对MAUI Blazor有了一些了解，知道MAUI是什么，知道Blazor是什么。 不会教你怎么写MAUI Blazor的项目，只是提出一些注意点，避免踩坑。 正文 先看官方资料 ......

对于要打印的 $B$，我们首先尝试确定 $B_1$。 让 $f(x) (1≤x≤M)$ 是最大的 $i$，使 $A_i = x$。 对于 $r:=\underset{{{1≤x≤M}}}{\min}f(x)$，我们可以证明 $B_1$ 是 $A_1 ,A_2 ,...,A_r$ 中的一个（否则，$B ......

用友U8出纳日记账查询后，窗口关闭不了，软件卡死解决办法 电脑环境：win10 、用友U8 13.0 现象：用友U8登录出纳管理，查询一次日记账后，重新在查询其他日记账窗口不能操作，任务管理器里面出纳管理显示未响应 尝试解决方案： 卸载U8重新安装，好了两天，问题重现； 修改U8兼容到win xp， ......

A - Treasure Chest (abc299 a) 题目大意 给定一个包含 |*.的字符串，其中|两个，*一个，问*是否在两个|之间。 解题思路 找到两个|的下标$l, r$以及 *的下标$mid$，看看是否满足 $l < mid < r$即可。 神奇的代码 ```cpp #include ......

洛谷传送门 AtCoder 传送门 记录一下这个神奇的套路。 首先有 $\operatorname{popcount}(n) = n - \sum\limits_{i=1}^{\infty} \left\lfloor\frac{n}{2^i}\right\rfloor$。证一下： $$\operat ......

洛谷传送门 AtCoder 传送门 若连通块是一棵树，考虑钦定 $k$ 个点为奇度点，方案数为 $\binom{n}{k}$。对于叶子，如果它是奇度点，那么连向它父亲的边要保留，否则不保留。这样自底向上考虑，任意一条边的保留情况都可以唯一确定，所以最后方案数就是 $\binom{n}{k}$。 若连 ......

一、问题描述 输入N个数组成的有序数列，在数组中查找某个数的位置，若找到，输出下标，否则输出not found 二、流程设计 1.取数组最大值最小值下标high和low 2.将待查找数与中值比较，若小于中值则查找前半段，否则查找后半段 3.输出结果 三、流程图设计 四、代码实现 #include < ......

洛谷传送门 AtCoder 传送门 这题居然是之前某场模拟赛（contest 701）的 T1……（@Vidoliga 场切但是被卡常/bx） 下面记 $m$ 为原题面中的 $K$，$a_i$ 为原题面中的 $P_i$。 不难发现后手的策略是把所有段按照段的第一个数从大到小排序接在一起。 考虑若 $ ......

洛谷传送门 AtCoder 传送门 挺有意思的题。 首先显然地，一个棋子不会走回头路。于是一个棋子沿着边走的效果就是区间异或。 更进一步，设 $s_i$ 为 $i-1 \to i$ 的边颜色与 $i \to i+1$ 的边颜色是否相同（差分），相当于对于每个 $i$ 都选择 $s_{a_i}$ 和 ......

一、问题描述 一对兔子从出生后三个月起每个月生一对兔子，小兔子三个月后每月生一对兔子，依次类推，假设所有兔子都不死，三十个月内每月兔子总量？ 二、设计流程 1.设置前两个月的初值a，b 2.将前两个月的总值赋给下个月c，并依次赋给a，b下个月的值，实现迭代 3.输出c 三、流程图设计 四、代码实现 ......

一、问题描述 冒泡排序 问题描述：键入N个整数进行升序排序。 二、设计流程 1.第一行输入N表示输入的数字的个数 2.用循环输入数字； 3.定义 i控制比较次数，定义j控制每次比较的次数； 4.如果后面的数小于前面的数，将两数位置交换。 三、流程图设计 四、代码实现 #include <iostre ......

题目：E - Unfair Sugoroku (atcoder.jp) 分析：这题状态转移方程挺好推的，但是用dp解是我没想到的 dp[i][j][0]表示T在i点，A在j点且轮到T走时赢的概率 dp[i][j][1]表示T在i点，A在j点且轮到A走时赢的概率 代码： #include <bits/ ......

首先观察这个奇怪的子树为 $1$ 或 $-1$ 的限制。 看不出来性质，润了。 我们不如直接把 $A$ 树和 $B$ 树拆开，变成两棵树，然后在树上留一下匹配的性质。 第一，我们对着样例构造一下，发现似乎有解的样例都有 $abs(X_i)\le 1$ 的解。 这就提示我们猜用 $-1,0,1$ 就够 ......

洛谷传送门 AtCoder 传送门 考虑判断一个终止态是否可达。如果只有一个棋子连续段那一定可达；否则就存在 $\ge 2$ 个连续段。此时把放棋子看成删除，那么限制就是如果删除一个孤立的棋子（两边没有棋子）且还有别的格子有棋子，这个棋子的颜色 异于其他连续段的两边棋子的颜色 。 设第一个被删的段（ ......

LinkedHashSet全面说明： LinkedHashSet是HashSet子类； 底层是一个LinkedHashMap，底层维护了一个数组和双向链表 根据元素的hashCode值来决定元素的位置，同时使用链表维护元素的次序，使得元素看起来是以插入的顺序保存的 不允许添加重复元素 维护了一个ha ......

题目 中国古代数学家张丘建在他的《算经》中提出了一个著名的“百钱百鸡问题”：一只公鸡值五钱，一只母鸡值三钱，三只小鸡值一钱，现在要用百钱买百鸡，请问公鸡、母鸡、小鸡各多少只? 流程图： 代码： 1 #include<iostream> 2 using namespace std; 3 int mai ......

A - Job Interview #include <bits/stdc++.h> using namespace std; int main(){ int n; string s; cin >> n >> s; if( s.find("x") != -1 ){ printf("No\n"); } ......

一、问题描述 二、设计流程 1.定义两个双精度浮点数a,b = 1000; 2.循环5次从后往前计算存款数； 3.循环内 a = b/(1 + 12 * 0.0063) b = a + 1000; 三、流程图设计 四、代码实现 #include <iostream> using namespace ......

挺套路的 DP。 第一步是显然的：转换贡献体，DP 一条从 $(0,0)$ 到 $(n+1,n+1)$ 的路径，然后计算有多少个排列满足这条路径不经过任何一个 $(i,p_i)$。 正着统计肯定不好求，考虑容斥。即我们钦定一些路径上的点，满足这些点必须对应某个 $(i,p_i)$，然后计算有多少个 ......