题解1249 div cf

CF1681D

CF1681D Required Length 题解 Codeforces 不一样的解法。 写完一看,标签里不是有 dp 吗,居然没人写。来提供一个动规做法。 本文中的 \(x\) 和 \(n\) 都是指输入的 \(x\) 和 \(n\)。\(\operatorname{set}_i\) 表示 \( ......
1681D 1681 CF

CF543D

CF543D 题解 CodeForces 独立做出来了,开心。 考虑从 \(x\) 出发、到叶子的一条链,中间有了一条“不良的路”后,后面的边一定都是“改善的路”。 设 \(f_i\) 表示 \(i\) 的子树内的方案数,\(ans_i\) 表点 \(i\) 的答案。 \(f\) 利用乘法原理转移( ......
543D 543 CF

CF1851G

诸位大佬把思路讲的很清晰了,我主要补充一下实现。 思路 考虑:如果一个询问的答案是肯定的,它对路径上所有点的要求。 询问为 a b e。 因为只有 \(e\) 点能量,所以能走到的最大高度只有 \(h_a + e\),没有最小高度。若路径上所有点的点权都在这个范围内,这个询问成立。 问题转化成:\( ......
1851G 1851 CF

CF915F

Codeforces Round 915 F 题解 定义 \(f(u, v)\) 表示 \(u\) 到 \(v\) 路径上的最大与最小点权之差,求: \[\sum_{i=1}^{n}\sum_{j=i}^{n}f(i,j) \] 定义 \(\max(u,v)\),\(\min(u,v)\) 为路径最 ......
915F 915 CF

概率生成函数([CTSC2006] 歌唱王国 题解)

如果数列 {p_n} 满足 P(X=i)=p_i(即 {p_n } 为 X 的概率质量函数 PMF 所构成的数列),那么有概率生成函数:F_X(x)=\sum^{+\infty}_{i=0}P(X=i)x^i,概率生成函数具有一些性质,这些性质可以简化我们做题时的一些推导…… ......
题解 概率 函数 CTSC 2006

P9549 「PHOI-1」路虽远 题解

题目链接:路虽远 带限制的 dijkstra,优先考虑有哪些限制条件,当做类似 dp 去写。闯黄灯次数有要求,限制速度的边数量有要求。 我们注意到,如果选择哪些边限速不易于基于贪心选择,可以考虑转换下,边数 \(-\) 限制数即为可以不限速的边,选择不限速的贪心优于限速的,这样一来,我们在有机会选择 ......
题解 P9549 9549 PHOI

P3741题解

题目分析 给出一个字符串 \(s\),允许改变 \(0\) 或 \(1\) 个字符,求其中 VK 的出现次数。 变量/数组/函数解析 int n 字符串 \(s\) 的长度 string s 字符串 \(s\) int count(string s,string key) 自定义函数:求字符串 \( ......
题解 P3741 3741

CF Beta Round 93-D.Fibonacci Sums-齐肯多夫分解、DP

CF Beta Round 93-D.Fibonacci Sums-齐肯多夫分解、DP https://codeforces.com/contest/126/problem/D 定义Fibonacci序列:\(F_1=1,F_2=2,F_k=F_{k-1}+F_{k-2}(\forall k\geq ......
Fibonacci Round Beta Sums CF

CF1550F Jumping Around

更好的阅读体验 CF1550F Jumping Around 提供一个不用动脑子的方法。 首先题目可以看成是求一个点到 \(s\) 的最小瓶颈路,设这个值为 \(v_i\),自然想到最小生成树,但是边数是 \(\mathcal O(n^2)\) 的,不可接受。 考虑使用 prim,一开始联通块力只有 ......
Jumping Around 1550F 1550 CF

P4093 [HEOI2016/TJOI2016] 序列 题解

题目链接:序列 对于 LIS 问题,很显而易见的有 dp方程为: \[dp_i=\max{dp_j}+1 \ (j<i,a_j \le a_i) \text{ dp表示以某个位置结尾的最长 LIS} \]本题考虑到对于转移的两位置,如果能从 \(j \rightarrow i\),那么在以上条件成立 ......
题解 2016 序列 P4093 4093

《算法竞赛》题解---三分

三分法 模板三分法 #include<bits/stdc++.h> #define eps 1e-8//或者 const double eps=1e-8;--主要是double using namespace std; int n; double a[15],l,r; double check(do ......
题解 算法

2023 百度之星决赛题解

T4 传信游戏 建反向边,从入度为 \(0\) 的结点开始搜 T5 喵喵卫士,全靠你了\(\star\) 考虑暴力枚举每个点的深度,发现只要知道相邻两层的深度就能用组合数算方案数,自然想到按层 DP,把上一层的点数记到状态里 赛时做法 按深度从小到大 DP 的话想要记录每个点是否被用过,以保证深度达 ......
题解 2023

vp Codeforces Round 915 (Div. 2)

vp还是比正式打舒服一些。。AB很顺畅,A题。。我只能说玩MC的都一眼秒了好吧 C题,我卡住了,结论非常好推,我直接退出来了,但是,问题是我对特例的判断不是很熟悉,或者说不是很敏感。这是一个大问题,我在wa on test 2的时候,第一反应是去看看这个算法整个有没有什么问题,事实上是没有的那么问题 ......
Codeforces Round 915 Div vp

P3203 弹飞绵羊 题解

Question P3203 [HNOI2010] 弹飞绵羊 一条直线上摆着 \(n\) 个弹簧,每个弹簧有一个弹力系数 \(k_i\),当绵羊走到第 \(i\) 个弹簧时,会被弹到第 \(i+k_i\) 个弹簧,如果 \(i+k_i>n\) 则会被弹飞,有两个操作 1 x 查询 \(x\) 处的绵 ......
题解 绵羊 P3203 3203

P1085题解

思路 1.定义校内时间/校外时间/最大值 (记录不高兴值) /记录星期 int n,m,maxx=-1,tmp; 2.使用循环输入并判断 for(int i=1;i<=7;i++){//循环一周的日期 cin>>n>>m; if(n+m>8 && maxx<n+m){//如果津津不高兴了且它比以往的 ......
题解 P1085 1085

P5722题解

说两句哈,等差数列求和公式是\((A_1+A_n)\times d \over 2\),所以其实可以一行代码解决,但是我没高斯聪明,于是我不打算用等差数列求和公式。 //(等差数列求和公式) int n; cin>>n; cout<<(1+n)*1/2; 思路 1.定义及输入截止的数/计数器 int ......
题解 P5722 5722

P5718题解

思路 1.定义及输入最小值的变量/输入个数/每个数 int n,m,minn=1001; cin>>n; 2.循环输入每个数并找最小值 while(n--){ cin>>m; minn=min(minn,m); } (用for循环也可以) for(int i=1;i<=n;i++){ cin>>m; ......
题解 P5718 5718

P1307题解

思路 1.定义及输入原数/反转后的数 int n,cnt=0;//反转后的数一定要归零! cin>>n; 2.用while循环反转 while(n!=0){//只要n还没有被分解完,就继续分解 cnt=cnt*10+n%10;//cnt每次*10再加上分离出的数位(*10为了防0) n/=10;// ......
题解 P1307 1307

CF1523H Hopping Around the Array

首先考虑 \(k = 0\) 的情况。 贪心,最后一步之前每个 \(i\) 只会跳到 \(j \in [i, i + a_i]\) 且 \(j + a_j\) 最大的点 \(j\),这个信息或许可以线性处理?但是我没脑子,我用线段树维护,时间复杂度 \(\mathcal O(n \log n)\)。 ......
Hopping Around 1523H Array 1523

ABC335E题解

洛谷题面 感觉有点毒瘤,不过还是有些 trick 在的。 题意翻译(复制于洛谷题面): 给定一个 \(N\) 个点 \(M\) 条无向边的图,图上每个点都有其颜色。求所有经过点权单调不降的路径中,出现的不同颜色的个数最多是多少。 由于是单调不降的路径,所以可以点权大的点到点权小的点的路径对结果没有影 ......
题解 335E ABC 335

P3730 曼哈顿交易题解

题目链接:曼哈顿交易 比较容易想的题,观察下首先不带修改,考虑维护的东西:次数作为权值,这玩意很显然很难在线维护,考虑下离线算法。看到这种和次数有关的权值,典型的单点加入和删除是非常好找到变化的,那么就莫队离线算法吧。 考虑下莫队如何来做,涉及到权值第 \(k\) 大,解决方法挺多的,但时限容易知道 ......
题解 P3730 3730

CF1687C Sanae and Giant Robot 题解

题目链接:https://codeforces.com/contest/1687/problem/C 题意简述 有两个长为 \(n\) 的数列 \(a\) 和 \(b\)。有 \(m\) 条线段,你可以进行任意次以下操作: 选择一条线段 \([l, r]\),若 \(\sum\limits_{i = ......
题解 1687C Sanae Giant Robot

P2801 教主的魔法 题解

Question P2801 教主的魔法 有一个 \(n\) 个元素的序列 \(a\),有两种操作 M L R W 对区间 \([L,R]\) 内每个数都加 \(W\) A L R C 询问区间内有多少数字大于或等于 \(C\) Solution 一个比较经典的分块题 暴力分成 \(t\) 个块,对 ......
题解 教主 魔法 P2801 2801

2023 CCPC 桂林题解

gym H. Sweet Sugar 一个经典贪心是从下到上,如果子树 \(u\) 剩下的部分(一定包含 \(u\))包含合法连通块,那么这个连通块给答案贡献 \(1\),切断 \(u\) 与 \(fa[u]\) 的边 key observation:如果一个连通块权值和为 \(x\),那么一定可以 ......
题解 2023 CCPC

(补题)CF1348B. Phoenix and Beauty

CF1348B. Phoenix and Beauty 思路 最后输出的一定是一个周期为k的数值。我们只需要查看输入进来的数组中的元素的种类和k的关系即可。元素种类大于k输出-1;小于等于k,输出每个不同的元素,不够k个的话就用1补齐 ac代码 #include <bits/stdc++.h> us ......
Phoenix Beauty 1348 and CF

P1980题解

自定义函数 定义一个自定义函数find_num用来记录数字x在该数里的个数。 int find_num(int n,int m){ int cnt=0; while(n!=0){ if(n%10=m){ cnt++; } n/=10; } return cnt; } 思路 1.定义及输入截止数/含有 ......
题解 P1980 1980

P1923题解

博文T3航站楼 ✈ P1923【深基9.例4】求第 k 小的数 预先准备 排序用函数 sort,不会用着参看文章sort用法 头文件 #include<algorithm> 及一个数组 a[5000005] 为了保证输入效率,我们用 scanf 进行输入。不会者可参看文章scanf用法 思路 1.定 ......
题解 P1923 1923

P1271题解

博文T4航站楼 ✈ P1271【深基9.例1】选举学生会 预先准备 本题需要用到排序函数 sort,不会者参看文章sort用法 头文件 #include<algorithm> 还需用到一个数组 a[2000005] 思路 1.定义及输入 n,m :选举人数/投票人数 int n,m; cin>>n> ......
题解 P1271 1271

P5015题解

博文T2航站楼 ✈ P5015标题统计 数组及变量准备 变量 string n 输入的标题 int cnt=0 计数器 预先准备 getline函数: 可用于输入带空格的字符串,格式如下 getline(cin,字符串名,结束字符); 思路 getline输入字符串\(n\) getline(cin ......
题解 P5015 5015

1.9模拟赛 T3题解

简要题意 求一个抽象函数,满足 \(∀𝑥 ∈ ℤ, 𝑓(𝑥) + 𝐶 = 𝑓(2𝑓(𝑥) − 𝑥 + 1)\),给定 \(n\) 个点,使得 \(\sum |f(x_i)-y_i|\) 最小,输出最小值 思路 对这个函数进行一次迭代,可以得到 \(f(x+2C)=f(x)+2C\) ......
模拟赛 题解 1.9
共6900篇  :3/230页 首页上一页3下一页尾页