Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

P7003 [NEERC2013]Hack Protection 题意 给定一个序列 \(a\) ,求有多少个区间满足区间内的数的异或和等于与的和的值。 思路 首先我们求一个异或前缀和 \(s\),对于每一个区间 \([l,r]\) ,它的贡献为区间内按位与的和等于 \(s_r \bigoplus s_{l-1}\) 的段的个数。 设 \(x\) 为某个区间的按位与的和,...

P6982 [NEERC2015]Jump 题意 给你一个未知的 01 串,每次可以输出询问一个 01 串,如果该串中正确的个数刚好等于 \(n\) 或者 \(n/2\) ,将会返回相应的答案,否则会返回 0 。求出这个串。(询问次数不大于 \(n+500\),\(n\leq 1000\)) 思路 先无视询问次数,我们来想一下确定性算法怎么做。 第一步,我们来试着找出 \(...

P7473 [NOI Online 2021 入门组] 重力球 题意 给你一个正方形平面,某些位置有障碍,对于平面上两个球,每次你可以改变重力方向使两个球下落到最底端,求使两个球位置重合的最小改变重力次数。障碍固定,多次询问两个球的位置。 思路 考虑最暴力的想法,总共有 \(n^4\) 种状态,即两个球的坐标。 考虑优化状态数,发现只有障碍物(边界)旁边(四联通)的位置才有用。...

P7362 [eJOI 2020 Day2] XOR Sort 题意 给你一个长度为 \(n\) 的序列,每次操作可以将一个数异或上相邻的一个数,求将序列改为严格单调递增序列或严格单调不降序列的操作次数的操作序列。 注意,改为严格单调递增序列的数据 \(n\leq 200\) 且每个数不相同,改为严格单调不降序列的数据 \(n\leq 1000\)。 不要求操作次数最小,次数需...

poj1944 一道我不会做的贪心题。 (思维才是OI的重点) 但是if您也不会,那就来听我瞎扯吧。 首先,这个图是一个圈,只能连接邻点,使所有求的点联通。 我们先不考虑环,那么就可以想出一个假的做法:用一个a数组记录入度和出度,出度为正,入度为负,用一个sum=0从0遍历每个点记录当前出入度,每次加ai,若sum大于0给答案加上1就行了。 然后,我们来考虑环。我们发现。不管怎么...

因为是单向边,牛儿来回的路径长度并不相同,所以需要用两次 dijkstra,一次正向从 \(x\) 开始 dijkstra,再将边全部反向存再来一次。 因为是板子题比较良心 \(n\) 比较小,我们就可以用矩阵来存储啦。如果 \(n\) 比较大的话,我的想法是再造一个图,同时反向存边。内存可能占用比较大但是想起来简单。 代码很短。 12345678910111213141516...

对树状数组的理解加深了! 转化题意 动态维护一个单调不降和一个单调不增序列,每次修改后输出两序列取最小值后的最大值和其最大位置。 思路 首先,阅读原题,知道最后答案一定是某个战士的温度,所以我们将温度离散化。 再次阅读,发现冰系是一个(以温度为自变量的)单调不降序列,每次修改一个战士就是修改一段后缀。火系相反,修改前缀。 深度阅读,发现题目其实就是求两个序列的交点。于是转化成上述...

Description 墨墨突然对等式很感兴趣,他正在研究 \(a_1x_1+a_2x_2+...+a_nx_n=B\) 存在非负整数解的条件,他要求你编写一个程序,给定 \(N\)、\(\{a_n\}\)、以及 \(B\) 的取值范围,求出有多少 \(B\) 可以使等式存在非负整数解。 Input 输入的第一行包含 3 个正整数,分别表示 \(N\)、\(B_{Min}\)、\(B...

POJ3187 Backward Digit Sums 好熟悉的题目……但是忘了是怎么做的……好像是随机排列? 反正都是暴力,看了下网上的题解,好像也没有更好的正解了。有想法的告诉我一下蟹蟹~ 题意 我们可以用1~n这n个数字用类似杨辉三角的方法加起来,我们就可以把他们拆回去。这样的排列可能有多种,我们要它字典序最小的一种。 思路 \(n\) 比较小,考虑排列所有可能一个个试...

矩阵树定理 定义 邻接矩阵:\(A=(a_{ij})\),其中 \(a_{ij}\) 表示 \(i\) 到 \(j\) 有几条边相连。 度数矩阵:\(C=(c_{ij})\),为对角矩阵,其中 \(c_{ii}\) 表示 \(i\) 的度数。 基尔霍夫矩阵:\(D=C-A\)。 余子式:\(M_{ij}\) 表示去掉第 \(i\) 行第 \(j\) 列后得到矩阵的行列式。 ...