前缀codeforces design medium
codeforces比赛(1):codeforces 916_div3
我的第一篇博客,虽然发布的都是非常简单的算法题,也没人看。我希望未来当我算法水平提高一个档次来看或许会有新的感受。这次cf比赛第一次写出来div3的D题,并且还剩余1小时,非常开心,一定继续保持下去。 ......
CodeForces 331E2 Deja Vu
洛谷传送门 CF 传送门 考虑一条好的路径 \(x \to y\) 中一定至少存在一条边 \((u, v)\),满足这条边的序列 \(a\) 存在一个 \(j \in [1, |a| - 1]\),满足 \(a_j = u, a_{j + 1} = v\),就是说 \(a\) 包含一对相邻的 \(( ......
Codeforces Round 651 (Div. 2)C. Number Game(数学思维数论)
C. Number Game 我们考虑那些状态是必胜态 我的回合时n为奇数(除1外),直接除以n则必胜 下面偶数的情况稍复杂 偶数我们能进行的操作只有除以一个奇数,需要考虑怎么把当前状态变为对手的必败态 偶数一定含2的因子,\(n=2^k*q,q为奇数\) 当\(k=1时如果q\)是一个质数那么只能 ......
base64 常用的前缀
.doc——data:application/msword;base64, .docx——data:application/vnd.openxmlformats-officedocument.wordprocessingml.document;base64, .xls——data:applicati ......
Codeforces Round 638 (Div. 2)B. Phoenix and Beauty
B. Phoenix and Beauty 这道题目学到的东西: 从给出的数据范围观察,得到一些有用信息(峰哥教的) 考虑无解的情况‘ 其实这题考虑怎么操作是比较难的,如果能想出来满足条件的结果就比较好了(我在说什么我自己也不知道,算了直接看下面的图吧) 假设\(k=3\),下面是我们得到的结果数列 ......
前缀和
//求某个数组某一段的和 //s[i] = s[i-1]+a[i]; //同理:正方形矩阵求S[i,j]:S[i,j] = S[i-1,j]+S[i,j-1]-S[i-1,j-1]+a[i,j] //求子矩阵的和s[x2,y2]-s[x2,y1-1]-s[x1-1,y2]-s[x1-1,y1-1]; ......
[Codeforces] CF1579C Ticks
CF1579C Ticks 题意 \(n \times m\) 的棋盘,左上角和右下角坐标分别为 \((1, 1), (n, m)\),一开始每个格子为白色。 每次操作可以选择一个格子 \((x, y)\) 以及左上角和右上角方向的 \(d\) 个连续格子染成黑色,并将其称为一个大小为 \(d\) ......
离散化,前缀和,差分
离散化,前缀和,差分 一维前缀和和差分之前学过不再记录 二维情况 前缀和 多维前缀和的普通求解方法几乎都是基于容斥原理 例如有这样一个矩阵,可以视为二维数组: 1 2 4 3 5 1 2 4 6 3 5 9 定义一个矩阵\(sum\)使得\(sum_{x,y}=\sum_{i=1}^{x}\sum_ ......
[Codeforces] CF1817A Almost Increasing Subsequence
CF1817A Almost Increasing Subsequence 题意 给定长度为 \(n\) 一个序列 \(a\) 以及 \(q\) 次询问,每次询问给出 \(l\) 和 \(r\),找出序列 \(a\) 在 \([l,r]\) 内最长的几乎递增子序列。 对于几乎递增的定义:如果一个序列 ......
[Codeforces] CF1811E Living Sequence
CF1811E Living Sequence 这道题洛谷题解的思路比我的更好,可以参考一下题解,但是没人提到我这种做法 题意 给定一个正整数 \(k\) \((1\le k\le10^{12})\),请你输出第 \(k\) 个数字里没有 4 的正整数。 思路 设 \(f_i\) 表示前 \(10^ ......
CodeForces 1913E Matrix Problem
洛谷传送门 CF 传送门 考虑费用流,对于每一行建两个点 \(i_0, i_1\),分别代表这一行的所有 \(0, 1\)。同样每一列建两个点 \(j_0, j_1\)。源点分别向 \(i_0, i_1\) 连流量为这一行要求的 \(0\) 或 \(1\) 的个数,费用为 \(0\)。同理连汇点。 ......
【模版】前缀和
问题引入: 【洛谷P8218】 ## 题目描述 给定 $n$ 个正整数组成的数列 $a_1, a_2, \cdots, a_n$ 和 $m$ 个区间 $[l_i,r_i]$,分别求这 $m$ 个区间的区间和。 对于所有测试数据,$n,m\le10^5,a_i\le 10^4$ 最朴素的想法,就是对于 ......
题解 P9963【[THUPC 2024 初赛] 前缀和】
注意到,\(x_i\) 取 \(k\) 的概率是 \(p(1-p)^{k-1}\),是和为 \(1\) 的等比数列,下面考察数列前缀和的性质。 不难想到,概率每次乘以 \(1-p\) 像是概率的分步乘法,每一步正是加一的操作。于是可以得到如下转化:初始时 \(S=0\),每一时刻 \(S\) 先增加 ......
题解 P9963【[THUPC 2024 初赛] 前缀和】
注意到,\(x_i\) 取 \(k\) 的概率是 \(p(1-p)^{k-1}\),是和为 \(1\) 的等比数列,下面考察数列前缀和的性质。 不难想到,概率每次乘以 \(1-p\) 像是概率的分步乘法,每一步正是加一的操作。于是可以得到如下转化:初始时 \(S=0\),每一时刻 \(S\) 先增加 ......
Codeforces Round 916 (Div. 3)
目录写在前面ABCDE1/E2FG1G2写在最后 写在前面 比赛地址:https://codeforces.com/contest/1914。 第二天没早八打个 div3 休闲娱乐保持下手感,然而 div3 都 AK 不了了,纯纯废物一个,天天上大学导致的。 唉,一学期碰上好几个 byd 恼弹老师, ......
Educational Codeforces Round 160 (Rated for Div. 2)
A. Rating Increase 字符串处理 #include<bits/stdc++.h> using namespace std; void solve(){ string s; cin>>s; int n=s.size(); s=" "+s; for(int i=1;i<=n-1;i++) ......
字符串篇(leetcode—最长公共前缀)
字符串 百度百科:字符串或串(String)是由数字、字母、下划线组成的一串字符。一般记为 s="a1a2···an"(n>=0)。它是编程语言中表示文本的数据类型。 常用函数 比较函数 C++、Python等支持运算符重载的语言——可以使用 == 来比较两个字符串 JAVA等不支持运算符重载——可 ......
Codeforces Round 914 (Div. 2)A~D
A. Forked! 题意:有骑士,国王,王后,给出骑士的攻击方式,骑士的攻击方式类似象棋中的马,一个方向长度为1,一个方向长度为2,有8个位置,骑士的两方向攻击长度为a,b,当a,b不等的时候,有8个位置,相同则有4个位置,询问骑士能同时攻击到国王和王后的位置有几个(采用多组输入形式) 范围:给出 ......
Codeforces Round 916 (Div. 3)
A. Problemsolving Log map枚举字母 #include<bits/stdc++.h> using namespace std; void solve(){ int n; string s; cin>>n>>s; int ans=0; s=" "+s; map<char,int> ......
Codeforce Round 916(div3)
Codeforces Round 916(div3) [Problem - A - Codeforces]:Problemsolving Log A.题 直接看样例进行分析,发现每一次出现的字符代表着用了1分钟来看这道题,每道题都有固定的解题时间,只要达到了这个解题时间,就可以将这题解出来 , 答案 ......
Codeforces Round 916 (Div. 3)(A~E2)
A 统计一下每个字母的出现次数然后输出即可 #include <bits/stdc++.h> #define rep(i,a,b) for(register int i = (a); i <= (b); ++i) #define fep(i,a,b) for(register int i = (a) ......
CodeForces 1148H Holy Diver
洛谷传送门 CF 传送门 从套娃过来的。 首先考虑如何方便地描述所有子区间的 \(\text{mex}\)。这是一个经典套路,考虑扫描线,扫右端点 \(R\),维护一些极长的段 \([l, r]\) 表示 \([l, R], [l + 1, R], \ldots, [r, R]\) 的 \(\tex ......
Codeforces Round 916 (Div. 3) (A~E2)
A. Problemsolving Log 签到题,对于给出的字符串,用数组记录每个字母出现的次数,然后遍历一边记录数组,如果对应的字母出现次数大于它的位次,则说明该字母对应的题目被解出来了,最后输出解题数量即可 void solve() { int n; cin >> n; string s; c ......
[Codeforces] CF1795C Tea Tasting
CF1795C Tea Tasting 题意 有 \(n\) 个人和 \(n\) 杯茶,第 \(i\) 个人每次会喝 \(b_i\) 毫升的茶。第 \(i\) 杯茶有 \(a_i\) 毫升。总共会喝 \(n\) 轮茶,第 \(j\) 轮第 \(i\) 个人会尝试喝第 \(i+1-j\) 杯茶。喝的量 ......
Educational Codeforces Round 160 (Rated for Div. 2) 题解A~D
Educational Codeforces Round 160 (Rated for Div. 2) A. Rating Increase 纯暴力,分割字符串,如果n1<n2就输出,如果遍历完整个数组都不存在n1<n2就输出-1. const int N = 2e5 + 10; int toint ......
Gowin FPGA Designer 简介
高云 FPGA Designer 是高云 FPGA 开发的 IDE 软件,软件包不大,安装包 241M,解压Gowin_V1.9.8.07_vin 压缩包,后点击文件夹的 exe 安装包,直接一直按下一步,完成软件的安装,安装后在桌面会有如下图标 双击打开软件,进入主界面,如下 软件的使用,请参考软 ......
Ant Design + List + 滚动加载列表
<div> <InfiniteScroll dataLength={load.length} hasMore={load.length < datas.length+1} loader={null} endMessage={null} onScroll={(e) => { /* 屏幕发生滚动的执行方 ......
Educational Codeforces Round 160 (Rated for Div. 2) A~C
A. Rating Increase 题意: 将一个字符串分成两个整数a和b,要求没有前导0,且a < b 思路: 遍历字符串s,若当前位置不是0,则拆分字符串,比较大小 // #include <bits/stdc++.h> #include <iostream> #include <string ......
Educational Codeforces Round 160 (Rated for Div. 2)
基本情况 A题秒了。 B题卡了实在太久,BC题最后虽然都过了,但是耗时太久。感觉C对我来说更好写。 B. Swap and Delete 经典+3。 总是一条路偏要走到黑了才会想着换思路,早该换了。 一开始想了一大堆乱七八糟的思路,但都错了。 后面往简单了想,这题毕竟最后必须要左对齐的,直接从左往右 ......
莫比乌斯函数平方前缀和
考虑求\(\sum_{i=1}^n\mu(i)^2\) 结论是\(\mu(i)^2=\sum_{j^2|i}\mu(j)\) 考虑证明这个式子。 先证明若\(\mu(i)\neq 0\)此时\(\mu(i)^2=1\) 显然只有\(j=1\)在右式造成贡献\(1\)等式成立。 若存在\(j\neq ......