Solution
The solution of P5339
problem 容斥好题,结果题解里面一堆 \(\text{NTT}\)。 如果我们去掉有多少个人喜欢什么东西的条件,那么这个题就直接枚举有 \(i\) 组同学会一起讨论蔡徐坤。这一个问题十分容易。 使用容斥原理来做,然后容斥的系数是 \((-1)^i\) 想必这个东西对于大家来说是十分简单的。 如 ......
CF390B Inna, Dima and Song Solution
转裁自我的洛谷博客 :https://www.luogu.com.cn/blog/653832/solution-cf390b 题目传送门 思路: 如果 $b_i \le 1$ 则无解。 如果 ceil((double)b[i]/2)>a[i],即最好情况下,两个人的音量平均,但是较大的音量还是大于 ......
Viper —— configuration solution for Go
1. support several formats of configuration config.yaml name: 'bobby' port: 12334 main.go to quick start package main import ( "fmt" "github.com/spf13 ......
Solution to OpenSSL Connection Problems With Github
Problems Uploading Files with Git Sometimes we can use git tool to successfully upload projects to Github, but in other time especially after a period ......
Practice Assessment for Exam AZ-400: Designing and Implementing Microsoft DevOps Solution
https://learn.microsoft.com/en-us/credentials/certifications/exams/az-400/practice/assessment?assessment-type=practice&assessmentId=56 The most secure ......
Solution Set 2
集合之和 Attachments - 2022 CCPC Henan Provincial Collegiate Programming Contest - Codeforces 题意 构造一个集合,使得集合中每两个数相加,得到的数再组成的一个集合,使得新集合的大小为\(n\)。 思路 当\(n\) ......
P4481 [BJWC2018] 序列合并 Solution
orz zhy,又被爆杀了。 首先四方 DP 是 trivial 的,我们设 \(f_{l,r,d}\) 表示 \([l,r]\) 的区间内被合并成 \(d\) 个石子的最小代价,对于 \(d>1\) 的位置 DP 完后可以贡献到 \(d=1\) 的位置。 其实这个做法可以直接通过本题(跑得飞快)可 ......
solution set#1
The Very Beautiful Blanket Problem - A - Codeforces 题意 构造一个\(n\times m\)的矩阵,使其中每个\(4\times 4\)子矩阵中,右上角的\(2\times 2\)异或和与左下角的\(2\times 2\)异或和相等,左上角和右下角 ......
Solution
谁共一杯芳酒 按 \(l\) 从大到小为第一关键字,\(r\) 从小到大为第二关键字排序,以 \(r\) 为权值求最长不下降子序列即可。 代码 #include<cstdio> #include<vector> #include<queue> #include<cstring> #include<i ......
The solution of P9194
10黑寄。 problem & blog 考虑到处理加边并不简单,所以我们可以考虑一个黑点 \(p\),连边\((u,p)(p,v)\)。 考虑在现在这棵树上连个点在原图中有变相连相当于有一个公共的 \(p\) 是它们的邻居。 于是删边操作等价于将一个点的儿子黑点并到父亲黑点上。 为了统计答案我们设 ......
CF1854C Solution
题目链接 题意 给定大小为 \(n\) 的正整数集合 \(S\),\(S\) 中的每个数在 \(1\sim m\) 之间。 每一秒进行如下操作: 从 \(S\) 中等概率随机选择一个数 \(x\)。 将 \(x\) 从 \(S\) 中删去。 若 \(x + 1\leq m\) 且 \(x + 1\n ......
Perkins 1106D Generation CID 0003 FMI 05 Trouble Code Solution
This illustration give the solution for Perkins 1106D electric power generation (EPG) CID 0003 FMI 05 trouble code. Related Contents:Perkins EST Compa ......
Solution of 牛客集训提高组第三场2023B 摆渡车
\(\text{Description}\) 有 \(n\) 个乘客要依次经过检票口等待摆渡车,其中第 \(i\) 个人的重量为 \(a_i\),摆渡车载重为 \(M\)。 当乘客 \(i\) 通过检票口时摆渡车来了则他能优先登上摆渡车。 剩下的 \(1 \sim i - 1\) 则尽可能多上人到摆 ......
Solution-AGC018F
对于全幺模阵刻画限制的一般方法。 先写出限制:\(\sum_{v\in \text{sub}(u)} a_v=\{1,-1\}\)。 嘛虽然你可以通过奇偶性(大概)把限制改成 \(|\sum_{v\in sub(u)}a_u|\leq 1\),但是我们还是别这么做吧。考虑转化一下限制。 设 \(a_ ......
Solution -「ARC 106E」Medals
Desc. Link. 你有 \(n\) 个朋友,他们会来你家玩,第 \(i\) 个人 \(1...A_i\) 天来玩,然后 \(A_i+1...2A_i\) 天不来,然后 \(2A_i+1...3A_i\) 又会来,以此类推; 每天你会选一个来玩的人,给他颁个奖,如果没人来玩,你就不颁奖。 你要给 ......
The solution of P3012
problem & blog 很明显是个 DP。 于是我们定义 \(dp_{i,j,k}\) 为末尾的字符的 ASCII 码为 \(i\),有 \(j\) 个大写字母,\(k\) 个小写字母。 然后在枚举能接在 \(i\) 之后所有字母即可。 然后考虑 \(dp_{i,j,k}\) 给后面的 DP ......
The solution of ABC144F
都不知道什么时候做的题了 problem & blog 一开始很容易想到枚举断边然后 DP 算代价。 于是很容易想到 DP 状态定义:设 \(dp_u\) 为从 \(u\) 出发到 \(n\) 的期望步数。 那么显然有 \(dp_u = \sum^{v_n}_{v_1} \dfrac{dp_{v_{ ......
Solution -「JOISC 2020」建筑装饰 4
朴素的 DP 形式是定义 \(f_{i, j, A/B}\) 表示前 \(i\) 个元素选择了 \(j\) 个 \(A\) 的可达性. \(\mathcal O(n^2)\). 交换状态与值域, 定义 \(f_{i, A/B, A/B}\) 表示前 \(i\) 个元素中的最后一个元素 (即 \(i\ ......
Solution of 洛谷-P1896
并不会有更好的阅读体验 \(\text{Sol}\) 我们先看一眼数据范围: \(1 \le N \le 9\) 没关系,DFS 会出手。 好吧,正经的说,如果暴搜的话复杂度会涨到 \(\text O(2^{n^2})\),\(\text T\) 到飞起。 此时我们发现有个东西叫状压 \(\text ......
Solution -「模拟赛」草莓蛋糕
\(\max(a_x + a_y, b_y + b_x)\) 的贡献形式不是独立的,并不好进行分析。考虑通过分类讨论将 \(\max\) 拆开。若令 \(h_i = a_i - b_i\),\(h'_i = b_i - a_i\),可以发现若 \(h_x \geqslant h'_y\) 取值则为 ......
Solution Set - 图上问题
CF360E Link&Submission. 首先显然可以选择的边的权值一定会取端点值。事实上,第一个人经过的边选最小,第一个人不经过的边选最大,这样一定不劣。进一步,如果 \(s_1\) 到点 \(u\) 的距离小于等于 \(s_2\),则 \((u,v)\) 这条边应该取最小值。所以可以初始全 ......
the solution of Mining Your Own Business
the description of problem (我看的是 PDF 里面的原题所以这里描述会和题目不一样,但是大意一致) 给定一个未必连通的无向图,问最少在几个点设置出口,可以保证任意一个点坍塌后,工人们仍然可以从出口逃生,同时问设置最少出口的方案数量。 thoughts & solution ......
solution-at-abc321-c
题意 将所有每位满足递减的整数排序,问第 \(k\) 大的是多少,不包括 \(0\)。 思路 我们发现最大的满足要求的整数是 \(9876543210\) ,只有 \(1e10\) 的大小,\(k\) 只有不到 \(3000\) 的大小,可以从小到大枚举所有的数,从 T1 粘来判断函数打一个表就解决 ......
Solution -「HDU」Ridiculous Netizens
Desc. 给定一棵 \(N\) 个节点无根树,找出满足以下条件的集合 \(S\) 的数量: \(S \subseteq \{1,\dots,n\}\); \(S\) 的导出子图联通; \(\displaystyle\prod_{v \in S} a_v \leqslant M\)。 Sol. 点分 ......
Solution -「LOJ #3310」丁香之路
首先有两个前置技巧:1) 两点间的最短距离就是直接连接两点的边的长度;2) 遍历一个子图的最小花费是最小生成树的边权之和乘二。原问题让我们找出一条最短且必经过钦定边的 \(( s, i )\) 路径,那么我们先将 \(\lang s , i \rang\) 连上,问题就变成了找出一条最短且必经过钦定 ......
Solution Set - 贪心和数据结构
感觉自己好菜啊,这个专题真的不太会。 CF1439C Greedy Shopping Link&Submission. 容易发现,当此人连续买了一段物品之后,他的钱数至少减半。所以他最多只会买 \(O(\log V)\) 段物品。那么就可以直接模拟每次询问,不断往后轮流找最多能买到的位置和下一个能买 ......
Solution Set before NOIP2023
香蕉公司 题意:维护 \(n\) 的排列 \(a_0\) 与 \(p\)。\(q\) 次操作,交换 \(a_0\) 中两个值或 \(p\) 中两个值,或者比较 \(a_x\) 与 \(a_y\) 的字典序大小,其中 \(a_{k,i}=a_{k-1,p_i}\)。 \(n,q\le10^5\),\( ......
Solution Set - DP
CF101E Candies and Stones Link&Submission. DP 的状态设计和转移都是显然的,唯一的问题在于需要输出方案,而这题卡空间。会发现如果用 bitset 存下所有位置的转移,空间刚好多了一点点。所以考虑分两次,第一次只存后 10000 行的转移,然后从最终状态倒退 ......
Solution Set - 组合计数
### CF40E Number Table [Link](https://codeforces.com/contest/40/problem/E)&[Submission](https://codeforces.com/contest/40/submission/221783054). 显然 $n ......
CF1615F O(n) solution
$O(n)$ 做法,目前 CF 最优解。 首先,考虑如何计算两个串的答案。 把奇数位置的值取反,那每次操作相当于 $01\to10$ 或 $10\to 01$。于是当两个串 $1$ 的个数相等时可以达成。 可以看作若干个 $1$ 在一条链上移动到新的位置。答案为距离之和,把移动贡献均摊到每条边上,那 ......