Codeforces Round #694 Div. 2CodeForces 1471A Strange PartitionCodeForces 1471B Strange ListCodeForces 1471C Strange Birthday Party签到 有难度CodeForces 1471D Strange DefinitionCodeForces 1471E Strange ShuffleCodeForces 1471F Strange Housing

Strange Birthday Party CodeForces - 1471C 题意： 我有n个朋友，商店有m种商品，这m种商品按序号价格从小到大排列，对于每一个朋友我给出一个序号k，我可以直接给朋友序号k的商品价格的金钱或给朋友买一个序号小于k的商品，且每种商品最多只能买一次，问我需要花费的最少金钱？ 题解： 简单的贪心我们将朋友的序号从大到小排序因为商品价值从小往大，由题意序号大的商品花费的金钱一定大于等于序号小的，所以我们只需要让序号大的朋友优先选用前面序号小的商品替代使花费金钱减少，直到前面的商品都已经被买了一次，然后后面的朋友直接给出对应序号金钱即可。 代码： #include...

题意： 对于长度为n的数组a，从第一位开始如果可以整除x，就将x个a/x的结果加到数组最后，然后对下一位进行一样的操作，直到第x位不可以整除x，到此结束，然后计算此时数组的总和 题解： 最直接的方法就是按照题意模拟即可然后稍微优化优化就行（不优化好像问题也不大） 代码： #include <bits/stdc++.h> using namespace std; #define qc std::ios::sync_with_stdio(0); int a[100001]; int b[100001]; int main() { qc; cin.tie(0); ...

Strange Partition CodeForces - 1471A 题意： 对于数组b可以两两合并其中的相连元素，beauty值就是对于数组b中的b[i]除以k向上取整的和，求出beauty值的范围。 题解： 题目给的是向上取整，也就是越合并值有可能越低，因为原本两个数分别向上取整（相当于多加2），合成一个数后最多加1这样就可以知道不做操作就是取到最大值，全部合并就是取到最小值。 代码： #include<bits/stdc++.h> typedef long long ll; using namespace std; inline int read(){ int s=...

题意： 有 n 个点和 m 条边，对点进行染色。要求一条边的两个点不能都染色，并且删除两端都没有染色的边之后，图连通。请给出一种染色方案。 题解： 第一反应就是01染色，但是题目是有可能存在奇环的，那怎么办？01染色是保证1和1,0和0都不能相邻，如果把1当做染色，根据本题，0是可以相邻的，那我们把01染色的dfs改成bfs的形式，也就是与1相邻的点都是0，然后对于每个0，所能到的下一个点就是1，然后对1操作，1的周围都是0，这样循环进行就可以BFS遍历所有的点。 如果当前节点没有染色，且相邻的所有节点没有染色，就染色，否则不染色。 如果当前节点已经染色，那么把相邻的所有节点标记不染色。证...

交互题 这类型不同于普通的题。可以理解为有个问题需要你解决，你通过输入某些东西表示你要问系统的问题，这时系统会回答你的问题。在代码中的回答方式就是会输入某个东西就是系统给你的答案，通过这些信息你可以得到问题的解你是不可以自己测试的，只能提交给系统测试。有个东西需要用到C++中的fflush(stdout);，这个东西是用来清空输出缓存区的因为你一直提问，一直输出，就需要清空输出缓存区。不然就有一些异常。简单的理解成你在和出题人交互，你问一个问题，他回一个问题，最终你根据他的回答确定答案 题意： 一个环，初始每个数都是k ，每一秒结束每个数会将自己一半给右边（向上取整），另外一半（向下取整）给左...

题意： 定义数字 x 和 y 是“相邻”的当且仅当 lcm(x,y)/gcd(x,y) 是一个平方数。给定一个长度为 n 的数组 a。每过一秒，数组 a 会发生变化：ai 会变成数组 a 中与其“相邻”的所有数字的乘积。定义 di 为数组 a 中与 ai “相邻” 的数字个数。定义数组 a 的美丽值为 max1≤i≤ndi给出 q 个询问，每次询问给出当前时间 w，问当前数组 a 的美丽值。 题解： 参考题解不会做。。emmm。。。看完题解恍然大悟题目中w的范围0≤w≤10^18^,那说明不可能真的一轮一轮进行，因为w太大了，可能会存在a数组发生优先次变化后，答案就固定了题目所定义的“相邻”经...

题意： 给你一个数组R，包含N个元素，求有多少满足条件的序列A使得 0 ≤ A[i] ≤ R [ i ]A[0]+A[1]+…+A[N−1] =A[0] | ]A[1]… | A [ N − 1 ]输出答案对1e9+9取模 题解： 参考博客数位dp问题如果和等于或的话，说明两种情况： 多个数的该二进制位只有一个1 多个数该二进制位的都没有1说明要满足等式，每一位数的二进制只能出现在这个n个数中的某一位上 因为加法是把每个二进制位上的数字加起 而或是最多只能有1 如果有一个二进制位有两个数都是1 那么一定会导致这个位往上一位进1 那就影响其他位了 一定不可能相等的 101和10 = = 11...

题目描述 设一个n个节点的二叉树tree的中序遍历为（1,2,3,…,n），其中数字1,2,3,…,n为节点编号。 每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：      subtree的左子树的加分 × subtree的右子树的加分 ＋ subtree的根的分数  若某个子树为空，规定其加分为1。叶子的加分就是叶节点本身的分数，不考虑它的空子树。 试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。 要求输出：  （1）tree的最高加分  （2）tre...

AcWing 1402. 星空之夜 1月28 题意： 一个星群是指一组非空的在水平，垂直或对角线方向相邻的星星的集合。一个星群不能是一个更大星群的一部分。星群可能是相似的。如果两个星群的形状、包含星星的数目相同，那么无论它们的朝向如何，都认为它们是相似的。给定一个夜空二维矩阵，请你将其中的所有星群用小写字母进行标记，标记时相似星群用同一字母，不相似星群用不同字母。 题解： 本题的关键在于如何判断两个星群是否相似，也就是如何分配字母的问题。题目说了相似说明两个星群形状一样，与方向无关，形状这一特征我们可以从每个星星与其他星星的距离和来表示对于每一个星群，计算其内部距离和，然后看之前是否出现过，出...

题意： 曾经有一道叫做迷雾森林的题目，然而牛牛认为地图中的障碍太多，实在是太难了，所以删去了很多点，出了这道题。 牛牛给出了一个n行m列的网格图初始牛牛处在最左下角的格点上(n+1,1)，终点在右上角的格点(1,m+1)现在它想知道，从起点走到终点，只能向上或向右走，一共有多少种走法呢？ 需要注意的是，除了起点和终点外，其它的每个格点都有可能有障碍，无法通过。 请注意格子与格点的区别 题解： 参考博客对于 n,m<=1000 的点：DP对于 n,m<=100000 的点，因为k很小，考虑使用容斥原理，我们定义一个work函数，work是指右移a次上移b次有多少种移法假设只有一个点(...

题意： 题目给出两个矩阵X,Y,现在有两种操作Z = X × YD = X⊙Y问是否存在一个矩阵C，使得A×C=B⊙C式子成立，问矩阵C能有多少个 题解： 这个式子在模2意义下的加法就等于异或也就相当于那现在有将BC移到左边然后将Ci,j的系数进行合并得到：aik =Aik A i,i = = B i,j时，A i,i xor B i,j = 0,ai,i = 0​A i,i != B i,j时，ai,i = 1矩阵C是列独立的，所以我们每次对Ci,j列出的向量只涉及第j列中未知数Cij2^自由元总数即为答案个数。 代码： #include <bits/stdc++.h> usi...

P3389 【模板】高斯消元法 题目： 给定一个线性方程组，对其求解 题解： 还没接触高斯消元时以为是什么神仙算法，接触后发现。。。就是把我们手算线性方程组的方法，写成了代码emm。。。比如： x-2y+3z=6 4x-5y+6z=12 7x-8y+10z=21 化为矩阵 1 -2 3 6 4 -5 6 12 7 -8 10 21 如果矩阵是这种形式，那么答案就显而易见了x=a,y=b,z=cx=a,y=b,z=c 1 0 0 a 0 1 0 b 0 0 1 c 我们一般手算时其实就是朝着这个方向做，高斯消元就是一步步这样走首先我们将第一列系数绝对值最大的数作为被减数因为这个系数绝对值最大的方...

题目： 给定一个X和Y，对于X每次可以选择一个A（0<=A<X），使得X = X xor A，现在要求在5步内将X变为Y，请输出操作数目，以及每步的A 题解： 我一开始被题目给的样例个迷惑了，以为将Y分解开，然后再加一步X就可以了，但发现想复杂了对于W = (X ^ Y)，也就是W，X，Y任意两个xor等于第三如果W 等于 X，说明Y是0，但因为Y>=1,所以该情况不存在如果W小于X，那么我们第一步直接选W不就完事了，X ^ W = Y如果W大于X，那就不能直接选W了，为了得到Y，我们可以先xorY，再xorX，因为第一步得到W，W大于X，所以可以选X，再选X相当于把一开始的...