题解codeforces round 891
CSP2023 题解
Junior A - apple 算是简单题,不需要什么脑子,用函数可以直接更简单。 #include <bits/stdc++.h> using namespace std; int n; int F (int x){ if (x == 1) return 1; if (x < 1) return ......
Codeforces Pinely Round 2 (D~G)
D - Two-Colored Dominoes by yzt E - Speedrun 题意 给定 \(n,m,k\) 。你需要考虑一个序列 \(t\)。 \(n\) 个要求:\(t_i \equiv h_i\mod k\)。 \(m\) 个要求:\(t_{u_i} \le t_{v_i}\)。 ......
Codeforces Edu 154 (A-E)
Codeforces Edu154 (Rated for Div2) (A-E) A.Prime Deletion 可以发现只要存在一个两位数(两位不相同),其正着看和反着看都是质数,则原问题有解。这时我们可以把除了这两位上的数之外的其他数从 \(s\) 中剔除,就有答案。上述两位数不少,如:13, ......
2023.08.07模拟赛题解
2023.08.07 模拟赛题解 A.[USACO21OPEN] Balanced Subsets P 思路 本场比赛第一道计数。 分析原条件,发现不管是横着从上往下看、还是竖着从左往右看,同一行或者同一列的 \(l\) 端一定满足先单调不升,再单调不降;\(r\) 端相反,满足先单调不降,再单调不 ......
CF821题解
CF821 Codeforces Round 420 (Div. 2) CF821A link CF821A题意 Okabe要改进他的实验室。实验室用一个 \(n\times n\) 的正方形网格表示(\(n\) 为正整数)。他认为,一个“好实验室”的网格内每一个不等于 \(1\) 的数字都可以用同 ......
ICPC2022Xian B Cells Coloring 题解
Link [ICPC2022Xian B Cells Coloring](ICPC2022Xian B Cells Coloring) Question 感觉这种解法会被Hack,欢迎讨论 给出一个 \(n\times m\) 的网格,有些格子堵住了,有些格子空着,要选 \(k+1\) 种颜色给空着 ......
Emiya今天的饭 题解
题目 考虑条件主要食材最大的不超过总菜数的一半,不好处理,但存在主要食材最大的超过总菜数的一半是好处理的,容斥即可。 首先计算所有情况,由于题目要求每个烹饪方式最多使用一次,很明显可以记 \(g_i\) 表示前 \(i\) 种烹饪方式的方案数。 \[g_i = g_{i-1}+g_{i-1} \ti ......
Codeforces Round 894 G
玩一下样例就能知道 这个是和 每个seg的最大间隔相关 为了好写我们可以直接写成元素间隔 这样我们用两个multiset维护元素间隔以及元素即可 注意删除的时候我们只删一个值 需要删指针 还有考虑长度为1的情况 multiset<int>st,st1; void Erase(int x){ auto ......
Codeforces Round 913 (Div. 3)
Codeforces Round 913 (Div. 3) 比赛链接 ROOK 题目 思路: 我没有下过国际象棋,但这个题跟国际象棋真是没有一点关系,就是一个简单的输出 代码: #include<bits/stdc++.h> using namespace std; #define int long ......
CodeForces 1901F Landscaping
洛谷传送门 CF 传送门 还是很有趣的一道题。场上直接暴拆式子,要维护动态凸包,本来以为是 \(\log^2\) 的,写着写着发现是 \(\log^3\),遂弃。 显然梯形面积最小等价于 \(y_0 + y_1\) 最小,而 \(y_0 + y_1\) 最小等价于梯形在 \(m = \frac{n} ......
CF1071题解
CF1071 Codeforces Round 517 (Div. 1, based on Technocup 2019 Elimination Round 2) CF1071A link CF1071A题意 现在你有两天的时间备考NOI,两天各有 \(a\) 小时,\(b\) 小时(时空扭曲)。 ......
【luogu题解】U388218 数数
数数 题目描述 给定 n 个不超过 1.5×10⁹ 的自然数。求这些自然数各自出现的次数,并按照自然数从小到大的顺序输出统计结果。 输入格式 输入的第 1 行是整数 n ,表示自然数的个数。 第 2 行到 第 n+1 行每行一个自然数。 输出格式 输出文件包含 m 行( m 为 n 个自然数中不相同 ......
T403510 平面划分(Hard) 题解
Link T403510 平面划分(Hard) Question 平面上由 \(n\) 条这样的折线所界定区域的最大的个数 \(Z_n\) 是多少。 Solution 先思考一个简单的问题 平面上 \(n\) 条直线所界定的区域最大个数 \(L_n\) 是多少? 我们考虑假设已经有\(n-1\) 条 ......
[ARC121F] Logical Operations on Tree 题解
题目链接 点击打开链接 题目解法 比较好的题 首先要发现一个性质是:先删 AND 边,再删 OR 边最优 小证一下:分类讨论 AND 边两端的数字情况 \(0 \& 0\) 左右两端虽然可能可以把 \(1\) OR 过来,但这种情况先做 \(\&\),也一定可以 OR 得到 \(1\) \(0 \& ......
Codeforces Round 913 (Div. 3)
Codeforces Round 913 (Div. 3) div3 两题 新纪录.. 我再也不喝完酒打cf了 A. Rook #include <bits/stdc++.h> //#define int long long #define endl '\n' using namespace std ......
【题解】CodeForces 1902F Trees and XOR Queries Again
传送门:https://codeforces.com/contest/1902/problem/F 数据结构题,这里讲两种思路。 $ST$ 表思路: 判定“从若干个数中能否取出其中一些,使得异或和为 $x$”的问题,第一时间想到线性基,本题要做的显然就是快速求出询问路径上所有数的线性基。两组数的线性 ......
[ARC106E] Medals 题解
题目链接 题目链接 题目解法 感觉不难啊,怎么想到网络流和 \(hall\) 定理后面就屁都没想到呢 首先一眼网络流 先二分答案 考虑一个朴素的建图方法是:把每个人拆成 \(k\) 个点,然后往在的天连边,跑最大流,满流即合法 可以发现,跑网络流对这道题还说没有必要,因为只要判是否有完美匹配 不难想 ......
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> ......
Codeforces Round 913 (Div. 3)(A~F)
A. Rook 题意:在一个国际象棋棋盘中,横坐标为a-h,纵坐标为1-8,字母在前,数字在后,输入一个棋子的位置,输出该棋子所在的行与列中非棋子本身位置的所有位置。 分析:模拟。 代码: #include <iostream> #include <algorithm> using namespac ......
CF1031题解
CF1031 Codeforces Round 517 (Div. 1, based on Technocup 2019 Elimination Round 2) CF1031A link CF1031A题意 现在你有两天的时间备考NOI,两天各有 \(a\) 小时,\(b\) 小时(时空扭曲)。 ......
Codeforces Round 908 C
111 发现要是所有的l r求和 L R 的差距>n 我们总可以找到一个x不在n个不同的aij里 然后我们知道L R 的差距不大于1e5 我们枚举这个最终的个数为now 我们钦定选满所有的非now的元素 看是否差一些元素达到now 当然维护过程中我们要注意l[i] r[i]的限制 但是我们枚举now ......
[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 ......