题解1249 div cf
[ARC106E] Medals 题解
题目链接 题目链接 题目解法 感觉不难啊,怎么想到网络流和 \(hall\) 定理后面就屁都没想到呢 首先一眼网络流 先二分答案 考虑一个朴素的建图方法是:把每个人拆成 \(k\) 个点,然后往在的天连边,跑最大流,满流即合法 可以发现,跑网络流对这道题还说没有必要,因为只要判是否有完美匹配 不难想 ......
CF1605E Array Equalizer
Array Equalizer 题面描述 Jeevan 有两个长度为 \(n\) 的数组:\(a\) 和 \(b\)。他有以下两种操作: 选择一个 \(k\)(\(1 \le k \le n\)),对所有满足 \(1 \leq i \leq n\) 并且 \(1 \le i \times k \le ......
Educational Codeforces Round 158 (Rated for Div. 2)
Preface 补题,妈的现在Edu E都做不来这搞毛啊 A. Line Trip 签到 #include<cstdio> #include<iostream> #include<utility> #include<vector> #include<cstring> #include<cmath> ......
CF785D Anton and School - 2
题意 给定一个长度为 \(n\) 的括号序列,求该括号序列满足下列条件的子序列个数。 长度为偶数 设长度为 \(2m\),则 \(s_{1 \ldots m} =\) (,\(s_{m + 1 \ldots 2m} =\) )。 Sol 设 \(i\) 为最后一个 (,\(a\) 表示 \(\sum ......
Codeforces Round 913 (Div. 3)(A~F)
A. Rook 题意:在一个国际象棋棋盘中,横坐标为a-h,纵坐标为1-8,字母在前,数字在后,输入一个棋子的位置,输出该棋子所在的行与列中非棋子本身位置的所有位置。 分析:模拟。 代码: #include <iostream> #include <algorithm> using namespac ......
CF1907F 高中数学
https://codeforces.com/contest/1907/problem/E 有一种情况是一定合法的,就是将x分成0,0,x。我们发现如果将x分出去,导致x退位了,一定会是变化位数和的,比如将26的个位分出去7,变成19, 7,那位数和就是17。 所以,这题的关键点是我们对于一个数应该 ......
CF1031题解
CF1031 Codeforces Round 517 (Div. 1, based on Technocup 2019 Elimination Round 2) CF1031A link CF1031A题意 现在你有两天的时间备考NOI,两天各有 \(a\) 小时,\(b\) 小时(时空扭曲)。 ......
CF 1881 G
调到了天亮。。。。 很一眼 就是线段树区间加 然后回文串只有两种类型 aa aba 所以我们维护的信息就是 l r 最左边两个字母ls[2] 最右边两个字母rs[2] 是否发现回文串st 最重要的来了 我们不能初始化次左 次右 为当前字母 我们应该初始化为-1 然后注意pushdown不要影响他们 ......
[CF83E] Two Subsequences 题解
[CF83E] Two Subsequences 题解 思路 定义 \(overlap(a, b)\) 为字符串 \(a\) 的后缀与 \(b\) 的前缀的最大相等的长度,有 \(|f(a, b)| = |a| + |b| - overlap(a, b)\),下文称匹配为相邻两串的 \(overla ......
CF1900B题解
原题 思路 略微思考不难得到,三个数字的数量之差的奇偶性是不会变的。因为一个数的数量减少了 $1$,另一个数无论是增加 $1$ 或是减少 $1$,两者的差要么不变,要么增加 / 减少 $2$,对奇偶性无影响。 同时,如果另外两个数的数量变为 $0$,它们数目的差一定是 $0$。那么,我们只需要判断另 ......
【题解】CodeForces 686E Optimal Point
传送门:https://codeforces.com/contest/686/problem/E 前言:本题解来源于作者某天晚上和一位朋友的发电内容(没错,这个作者直接把自己和朋友发电时发的话用markdown排了一下,传上来了),当时本来就比较口语化,加上作者的做法又实在太过离谱,因此可能语言表述 ......
【题解】LibreOJ #3051「十二省联考 2019」皮配
传送门:https://loj.ac/p/3051 首先,对于这样“少部分个体有特殊要求”的题目,我们先考虑,如果没有任何个体有特殊要求怎么做,然后再考虑怎么加上特殊要求; 对于这道题,如果 $k=0$,即没有学校有不喜欢的导师,那么,设总人数为 $al$,城市 $i$ 的人数和为 $cit_i$、 ......
P8773 [蓝桥杯 2022 省 A] 选数异或 题解
P8773 [蓝桥杯 2022 省 A] 选数异或 题解 题目链接 P8773 [蓝桥杯 2022 省 A] 选数异或 简要思路 题目让我们查询是否有两个数 \(a,b\) 满足 \(a \oplus b = x\),根据异或的性质,我们可以将上式转换为 \(b = a \oplus x\),因此对 ......
UVA1395 Slim Span 题解
Link UVA1395 Slim Span Question 求所有生成树中最大边权与最小边权差最小的,输出他们的差值 Solution 因为 \(n \le 100\) 非常小,先把边从小到大排序,那么生成树的边肯定是排序后上的边连续的一块 所以,可以枚举连续一块的起点 \(L\),\(R\) ......
UVA753 A Plug for UNIX 题解
Link UVA753 A Plug for UNIX Question 有 \(n\) 个插座,\(m\) 个设备和 \(k\) 种转换器,每种转换器有无限多个。转换器可以插着转换器用,每个插座或插头的类型可能不同,求最少剩多少个不匹配的设备 Sulotion 先考虑转换器连用的情况,用边表 \( ......
Codeforces Round 912 (Div. 2)
Preface 这场题莫名很对我胃口,因为F是个究极套路题,还是我最拿手的2-SAT,想+写不到半小时就搞定了 然后E的核心思想和上周末VP的一场省赛的题一样,因此看一眼就会了 唯一抽象的是D2要用对超集的sosdp,由于之前没写过就不知道还能这么搞 A. Halloumi Boxes 当\(k\g ......
CF1850E Cardboard for Pictures 题解
题意: 思路: 问题转化为:求解满足 $ \sum_{i = 1}^n (a_i + 2w)^2 = c $ 的 $ w $ 。 观察,等式左侧 $ \sum_{i = 1}^n (a_i + 2w)^2 $ 随 $ w $ 的增大而增大,而 $ c $ 不变,因此考虑二分 $ w $ 的值。 ......
CF1809D Binary String Sorting 题解
题意: 思路: 贪心: 单调不降的 $ 01 $ 字符串,一定是一串连续的 $ 0 $ 再加上一串连续的 $ 1 $ 。由于每次操作的代价很大,所以需要在操作次数尽可能少的情况下,尽可能多地使用交换操作。 由于 $ 1 $ 次交换操作,只能减少 $ 1 $ 个逆序对,当存在多个逆序对时,优先通过删除 ......
ucup hefei 题解
比赛链接 B 很有意思的题 首先题目的要求为可以拆分成 \(2\) 个不相交的不降子序列 根据 \(dilworth\) 定理,最小链覆盖 \(=\) 最长反链,所以要求最长反链 \(\le 2\) 即原序列的逆序列的最长不降子序列长度 \(\le 2\) 不难得到一个 \(dp\) 做法为: 令 ......
Educational Codeforces Round 154 (Rated for Div. 2)
Educational Codeforces Round 154 (Rated for Div. 2) # Name A Prime Deletion x14422 B Two Binary Strings x10743 C Queries for the Array x3639 D Sorting ......
Codeforces Round 913 (Div. 3)
A. Rook #include <bits/stdc++.h> using namespace std; #define int long long using pii = pair<int, int>; using node = pii; using i32 = int32_t; void so ......
线性代数题解
前言 写完了这道题我好想刚明白一点最小割???UU好闪,拜谢UU。 题解 首先,我们可以发现若第 \(i\) 行的 \(B\) 没选,那么第 \(i\) 列的 \(B\) 也不选,所以此时对于行和列是等价的。 若 \(A_i\) 是 \(0\),则会减少贡献 \(\sum_{j}B_{i, j}\) ......
Codeforces Round 913 (Div. 3)
Codeforces Round 913 (Div. 3) 基本情况 A、B题秒了。 C题找了好几个规律,一开始一直找错,但是最后终于对的。 因为C题耗时太久,D、E题看都没看。准备先做一下再补题。 ......
P8594 「KDOI-02」一个仇的复 题解
我会组合数! 首先发现同一列只有被不同的横块填或被一个相同的竖块填,且用竖块填完1列之后,会分成两个封闭的长方形,而长方形内部则用横块来填充。 先考虑一个子问题,某个 \(2 \times n\) 长方形内只用 \(k\) 个 \(1 \times x\) 的横块填的方案数,显然有 \(\sum\l ......
CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
Preface 补题,经典不会F,看了会题解发现看不懂,索性直接开摆 A. Jagged Swaps 判断\(a_1\)是否为\(1\)即可 #include<cstdio> #include<iostream> #include<utility> #include<vector> #include ......
CF603题解
CF603 Codeforces Round 334 (Div. 1) CF603A link CF603A题意 现有一个长度为 \(n\) 的 01 串, 可以进行一次区间翻转 ( 起点终点随意, 并且区间里的值 1 变 0, 0 变 1 ), 得到一个新的 01 串, 使得得到的新的 01 串中 ......
Codeforces Round 913 (Div. 3)B(预处理)
[Codeforces Round 913 (Div. 3)B]{https://codeforces.com/contest/1907} 预处理: 如果说一个数据是静态的,那可用预处理来减少运行时间。 在这里,我们对字符串的大小写字母做一个预处理,提前用数组记录下他们的位置,然后再根据题目要求对对 ......
[NOI Online #1 入门组] 跑步 题解
[NOI Online #1 入门组] 跑步 题解 突然发现之前打过 NOI Online,啥都不会的情况下这题竟然拿了 70pts。 思路 题意就是统计对于 \(n\le 10^5\),把它进行无序正整数划分的方案数。 对于 70pts,我们考虑 DP:\(f_{i, j}\) 表示对于 \(1\ ......
CF1824B1 LuoTianyi and the Floating Islands (Easy Version) 题解
题意: 思路: 由于 $ k ∈ [1,3] $ ,分类讨论: 当 $ k = 1 $ 时,有人结点自身即为好结点,每种情况的期望为 $ \frac{1}{n} $ , $ n $ 种情况的期望和为 $ 1 $ 。最终答案即为 $ 1 $ 。 当 $ k = 2 $ 时,$ 2 $ 个有人结点之间的 ......