文文的构造游戏
P8468 [Aya Round 1 C] 文文的构造游戏题目描述对于一个长度为 $l$ 的数列 $p$，定义 $S(p)$ 为所有元素的异或和，其中 $\oplus$ 指按位异或运算。 给定整数 $s,m$，判断能否构造一个长度为 $n$（$n$ 值自定）的数列 $a$，满足： $1 \le n \le m$。 $1 \le a_i \le s$。 $S(a)=0$。 $a_1+a_2+\cdots+a_n=s$。 试构造任意一组合法解或报告无解。 做法构造题一般代码都是非常简单的，基本都是可以在 $O(1)$ 的情况下找寻答案的 所以我们要通过找寻反例情况造案例去寻找答案。反例情况很有可能出现在极端情况身上。因为不会有题目让你找出的几百的规律找规律。并且答案很容易拥有非常普遍的情况 以本题为例子：题目要求我们找寻异或和为 0 的情况, 根据异或性质，如果出现偶数类的和异或在一起,异或和为0;而考虑最一般的情况，那肯定是异$ s/2+s/2==s$ 的情况。 ...
树的重心问题
P1364 医院设置题目描述设有一棵二叉树，如图： 其中，圈中的数字表示结点中居民的人口。圈边上数字表示结点编号，现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻接点之间的距离为 $1$。如上图中，若医院建在 $1$ 处，则距离和 $=4+12+2\times20+2\times40=136$；若医院建在 $3$ 处，则距离和 $=4\times2+13+20+40=81$。 说明/提示数据规模与约定对于 $100%$ 的数据，保证 $1 \leq n \leq 100$，$0 \leq u, v \leq n$，$1 \leq w \leq 10^5$。 解题思路初步分析题目的意思是，圈中的数字表示节点中的人口，相邻接点之间的距离为 $1$。而寻求所有人口到达医院的最小距离之和。 思考问题我们可以任意调整医院的位置，而医院的位置调整后，距离之和都会改变，而这种改变是有规律的。比如以图中医院节点由 $1$ 改成 $3$ 为例子，显而易见可以观察到，将会是...
T561273 共同兴趣
共同兴趣 T561273 那么模拟题目，我们可以分析出以下我们要实现的步骤： 1.对于任意一个学生，寻找除自己以外的学生与自己之间的公共感兴趣有多少项 2.只有公共感兴趣的最多的学生可以得到邀请， 所以我们用一个数组保留最大值。 3.如果小O≥任意一人的公共感兴趣活动，则答案加一; 4.只有将0改成1，才能有更优的答案。（反之如果全是1，则无需修改）。遍历每一个把0改成1的可能，寻找最大的答案。 将步骤以代码呈现出来：1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include<bits/stdc++.h>using namespace std ;using ll = long long ; //const int N = 100000 + 10 ; //500 * 500 5e4 * 500const int N = 500 + 10 ;int...
Bellman-ford求最短路
Bellman-ford求最短路问题 今天来学习一下Bellman-ford求最短路，Bellman-ford是一个解决负权值的最短路问题的算法。不过时间复杂度很高(O(nm)) Bellman-ford的步骤为： 1.存图 2.进行初始化为无穷大,并将dist[初始] = 0 ； 3.循环k次(k是最多经过几条边，没有特殊要求就是n-1了) 4.在循环中使用新的数组来取代dist[^这个的原因是，如果使用dist，容易一次性更新多条边 ] 5.遍历每一个点，如果点不是无穷大，那就遍历这个点的相邻线路，并且如果有最短路就更新相邻线路 6.输出答案 接下来就是代码辣~ 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include <bits/stdc++.h>using namespace std;const int N = 550 ; struct Dim{ int v...
DP从入门到入土
DP 我将通过几个我做过的dp题型，来全方面的重新介绍题意和重新介绍解法。以此来为DP最一份总结。过于简单的不予介绍，此总结只适合有基础的人。 因为我也没基础，所以需要有基础的人才能看懂 DP求最长方案与方案路径 P2196 [NOIP 1996 提高组] 挖地雷 题意：在一个 $ N\le20 $ 的图里面，可以从任意一点出发，只能移动到一个编号比当前节点大且联通的节点，求最长路径之节点之和与路径 解法：将问题给拆分出两个部分，一个部分是如何求出最长路径，第二部分是如何求出路径。 最长路径之和 由题意可知，一点出发，只会移动到一个比当前节点大且联通的一个节点。故而我们可以通过画图得知（图请脑补），一个节点的选择只有要么从 本节点开始,要么 从之前节点转移 所以轻易可得状态转移方程 123if(dist[j][i] && dp[i] < dp[j]+a[i] ){ dp[i] = max(dp[i], dp[j]+a[i]);} 记录路径 ...
