p1896 2005 scoi

点击查看代码 #include<bits/stdc++.h> using namespace std; int n,m; long long f[10][1024][100]; int v[1024]; void init() { for(int i=1;i<1<<n;++i) { int c=0; ......

P3422 一道有点意思的题。 看到是一个环，先破环为链，即 \(a_{n+i}=a_i, b_{n+i}=b_i\)，此时就只需要跳到 \(x+n\) 而无需判环了。 如果顺时针走： 令 \(sum_i = \sum\limits_{j=1}^{i}{a_j-b_j}\)，当能从 \(x\) 跳到 ......

P1054 [NOIP2005 提高组] 等价表达式 这个题在计算表达式时可能会出现高次方，比如在某一数据中就出现了 2^7^10 也就是 \(2^{70}\) 自然溢出会寄，所以要取模 自然溢出 \(80\) 分 ull quick_pow (ull x, ull p) { ull res = 1 ......

洛谷上是可以过掉的。NFLSOJ上加强数据，还卡常，所以 90pts。 首先倒着做很好想。对于最终的图，我们可以 tarjan 缩点然后建树，边权为 \(1\)，表示一条割边。然后每次连两个点的时候就把树上这一段路径赋值为 \(0\)。查询就是树上路径和。这些操作都可以点赋边权然后树剖来做。所以你就 ......

此题是极其恶心的大分类讨论。 结论 首先我们可以发现一个重要的结论，在用两镖只打数字的情况下，可以拼出 \(0\) 到 \(5k\) 中除了 \(5k-1\) 的所有值，以及 \(0\) 到 \(6k\) 中一些不连续的 \(3\) 的倍数。 证明： \(0\) 到 \(5k\) 中 \(5k-1= ......

题意 给定长为 \(n\) 的序列，\(q\) 次询问区间 \([l, r]\) 的最短区间 \([l', r']\), 满足所有在 \([l, r]\) 中出现的数也在 \([l', r']\) 中出现，你只需要输出 \([l', r']\) 的长度即可。 Sol 离线，然后枚举 \(r\)。 考 ......

首先每次选择的区间结尾都可以换成 \(n\)，仍然保持单调不降，我们就按这个策略拔高玉米。 令 \(f_{i,j}\) 表示 \(1\sim i\) 这段前缀进行了 \(j\) 次操作，第 \(i\) 株玉米不被拔掉，所能剩下最多的玉米数量： \[f_{i,j}=\max\{f_{p,q}|p<i, ......

思路 应该很容易想到使用树形 dp。 令 \(f_{u,i}\) 代表，只考虑 \(u\) 为根的子树，\(u\) 的编号为 \(i\) 的情况下，最小的编号总和。 那么我们可以用 \(u\) 的儿子 \(v\) 来更新 \(f_{u,i}\)。 转移方程 \(f_{u,i}=\sum_{v\in ......

`2023-07-26 14:58:54 solution` ## 简化题意： 给你一个 $n\times n$ 的只有黑白两种颜色的棋盘，每次修改把某格的黑白互换，求每次修改后黑白各自的连通块个数。 ## 解法 将棋盘转化成 $n$ 行，每行单独处理，处理出黑色和白色分别的连通块个数(可用并查集) ......

`2023-07-18 20:48:35` ## 简化题意： 给你一个n*n的只有黑白两种颜色的棋盘，每次修改把某格的黑白互换，求每次修改后黑白各自的连通块个数。 ## 解法 将棋盘转化成n行，每行单独处理，处理出黑色和白色分别的连通块个数（可用并查集）。 开一个n的线段树，每个叶子节点表示一行。 ......

## [$SCOI2010$ $P2572$ 序列操作](https://www.luogu.com.cn/problem/P2572) ### 一、题目描述 $lxhgww$ 最近收到了一个 $01$ 序列，序列里面包含了 $n$ 个数，下标从 $0$ 开始。这些数要么是 $0$，要么是 $1$， ......

# P4216 [SCOI2015] 情报传递 题解 来一篇常数不大的[最优解](https://www.luogu.com.cn/record/list?pid=P4216&orderBy=1&status=&page=1)题解。 ## Link [洛谷题目](https://www.luogu. ......

[题目链接](https://ac.nowcoder.com/acm/problem/20277) # 题目 **题目描述** lxhgww最近接到了一个生成字符串的任务，任务需要他把n个1和m个0组成字符串，但是任务还要求在组成的字符串中，在任意的前k个字符中，1的个数不能少于0的个数。现在lxh ......

[传送门](https://www.luogu.com.cn/problem/P4159) 先思考$C_{i,j}$要么只有0和1两种值的情况，那么这种情况就是求矩阵$C^k$中的$C_{1,n}$的值。 证明：令矩阵$G=C^2=\sum\limits_{k=1}^nC(i,k)*C(k,j)$， ......

[题目链接](https://ac.nowcoder.com/acm/problem/19872) # 题目 **题目描述** 为了表彰小联为Samuel星球的探险所做出的贡献，小联被邀请参加Samuel星球近距离载人探险活动。 由于Samuel星球相当遥远，科学家们要在飞船中度过相当长的一段时间， ......

# 题目大意 给定一个带权无向图与距离 $t$，问有多少条从 $1$ 到 $n$ 路径长度为 $T$。 # 思路 ### 从特殊情况出发 先考虑权值只有 $0,1$ 的情况，我们设 $f_t[i][j]=k$ 代表从 $i$ 到 $j$ 经过的路径权值综合为 $t$ 的方案数共 $k$ 种。 那么我 ......

感觉这道题难点全在计算几何的细节，调了几天qwq。 # 思路 观察到 $p$ 最大也只有 $8$，作为蒟蒻的我第一时间就想到了暴力搜索，每次选一条没算过的边计算加进去的切割线长度。 有了核心思想，我们就要处理细节了，搜索很好写，重点是如何求出切割线。 在这里介绍两种方法： 第一种，我们暴力找到这条边 ......

### 前言 [传送门](https://www.luogu.com.cn/problem/P2573) 调了一个下午终于弄出来了！！！ ### 卡题的事情 上图： ![](https://cdn.fzoi.top/upload/user/st20250310/23072704416058.jpeg ......

1、书籍基本信息 书名：电脑上网(附CD-ROM一张)——一学就会魔法书 定价：29.00元 作者：张凤群,李燕,马忻 出版社：清华大学出版社 出版日期：2005-08-01 ISBN：9787302110286 2、网络用语 ......

##**题目描述** 给你一个$n$元一次方程，判断是否有解，方程给出的格式为 $a-b=c$ ##**思路** 这道题看上去是一道题目看上去就是判断给出条件是否有矛盾，所以就自然而然的可以使用带权并查集 但是因为~~我太懒了并且~~这道题目要求使用**差分约束系统**进行求解，于是就需要将题目转化 ......

##**题目描述** 给你一个$n$元一次方程，判断是否有解，方程给出的格式为 $a-b=c$ ##**思路** 这道题看上去是一道题目看上去就是判断给出条件是否有矛盾，所以就自然而然的可以使用带权并查集 但是因为~~我太懒了并且~~这道题目要求使用**差分约束系统**进行求解，于是就需要将题目转化 ......

[题目链接](https://www.luogu.com.cn/problem/P3426) 充分暴露出对 $border$ 结合 $dp$ 理解的不足。 先来推结论，一个字符串的印章一定是其 $border$，因为只有这样才可能兼顾首尾，但是他的 $border$ 不一定是其印章，两个条件不能互推 ......

1、Verilog 不同版本的差异 下图是Verilog各个阶段的关键字列表： 2、Verilog-1995 VS Verilog-2001 1、模块声明的扩展 （1） Verilog‐2001允许将端口声明和数据类型声明放在同一条语句中，例子如下： （2）Verilog‐2001中增加了ANSIC ......

题目传送门：[luogu P2324 [SCOI2005] 骑士精神](https://www.luogu.com.cn/problem/P2324) # 题意  # 分析 数据范围比较小，适合搜索 ......

设每只怪物经过环境影响后的攻击力和防守力分别为 $x_i, y_i$，则有： $y_i = dnf_i - \dfrac ba(x_i -atk_i)$。 设 $k = -\dfrac ba$，则有 $y_i= kx_i + dnf_i - k \cdot atk_i$。 设直线 $l_i : y_ ......

P3275 [SCOI2011] 糖果 - 洛谷 没有注意到的点： 求解的解是最小值，所以用差分约束最长路求解，那么出现了正环就无解，所以如果答案合法tarjan缩点后每个强连通分量中的点（得到的糖果数）只能是相等的 拓扑排序每个入度为0的的 f [ i ] = 1,因为每个人至少要有一颗糖 最后计 ......

[题目链接](https://www.luogu.com.cn/problem/P2567 "题目链接") 题目中询问数据范围达到了1e10，且要求找符合要求数的个数，很容易让我想到数位dp，但其实每必要，发现幸运数字只有 $2^{10}$ 个，答案就是近似幸运数+幸运数-两者交集，考虑容斥，每个 ......

## 思路 01背包模版题 转移方程为：```dp[j]=max(dp[j],dp[j-ti]+wi);//滚动数组优化``` # 代码 ```cpp #include #define ll long long #define ld long double using namespace std; ......

这东西在线不太能做，考虑离线扫描。扫描右端点 $r$，我们对每个位置 $l$ 维护一个 $p_l$ 表示最小的 $p$ 使得 $[l,p]$ 是 $[l,r]$ 的合法子区间。 考虑如何维护 $p_l$。考虑新加入的右端点 $r$，加入一个数 $a_r$，上一次出现的位置为 $lst_{a_r}=c ......

posted on 2022-10-22 15:46:31 | under 题解 | [source](https://www.luogu.com.cn/blog/_post/494786) ## problem 字符串 $S$ 长为 $n$，对于每个前缀，求能盖出这个前缀的最小的印章长度。 ## ......