题目大意 指针分析旨在确定在执行过程中可以通过程序中的特定指针变量访问哪些对象，这是静态程序分析的基本部分之一。 现在，我们希望您对测试数据执行上下文无关的指针分析。 一个程序包含26个用小写字母表示的object，每个object也有26个用小写字母表示的成员变量（也称fields，是指向某个object的指针），和26个用大写字母表示的全局指针。 程序有4种语句，用[Variable]表示指针的名称，[Field]表示成员变量的名称，[Object]表示对象。 说人话 一个程序中有26个对象，每个对象有26个成员指针变量，同时还有26个普通的指针变量，给定n条赋值语句，询问在以任意顺序执...

题目大意 原题长的一批的翻译： 有一种有向图，被称为排列的DRG图，其包含组节点，第组包含个节点：。 DRG上有2种边：组内边和组间边。第组内的组内边可以表示为：（应该都能看懂）组间边可以表示为： 现在我们想知道排列的DRG图的拓扑序列的数量。有向图的拓扑序列可以表示为： 。所有节点来自且对于任意, 。答案对素数取模。 简单的说 给定一个有向无环图-晒肉架图DRG(n)，求DRG(n)有多少种拓扑序列。 拓扑序列：1.从图中选择一个没有前驱（即入度为0）的顶点并输出。2.从图中删除该顶点（即加入拓扑序列）和所有以它为起点的有向边。3.重复1,2，直到图为空或图中不存在无前驱的顶点为止。后一...

题目大意 在半径为的圆内放个人，使得相互之间距离尽可能远，即使得尽可能大，表示第i个人与第j个人的欧几里得距离。 解题思路 这道题我们考虑用dp来做。很容易得出，我们的n个点的距离和为： 将其化为加法，可以推出这样的式子： 每次直接求出前面一项，而后面用勾股定理求即可。 AC代码 #include<bits/stdc++.h> using namespace std; int dp[10][610][610],ans[40][40]; vector<pair<int,pair<int,int> > > v; int main() { in...

题目大意 我们将无根树T的价值定义为 ，其中V(T)是T的所有顶点的集合，而d(u)是T的度数。（即内部每个节点度数的平方和） 我们将森林的价值定义为森林中所有树木的价值之和。求所有包含N个节点的森林的价值总和，答案对素数M取模。 解题思路 这题需要用到prufer序列的结论： 初识prufer序列：https://www.cnblogs.com/chenxiaoran666/p/prufer.html 引用文中的证明： 因为n个点的无根树可以形成个不同的树，我们设他的值为，设n个点的森林个数为。在第n个点加入时，我们选择i个点和他形成一棵树，那么就可以列出dp式： 接着我们...

题目大意 （这道题的原版真的有太多槽点了xswl）简单地说，给定n，判断 是否为一个平方数。就是判断是不是完全平方数。 解题思路 这道题队友打了一会表，就猜到了以下第一种操作（大佬带飞tql） 最简单的做法，直接特判n是否为1或24即可。证明比较复杂，可以参考： https://www.zhihu.com/question/363661682 还有一种官方题解里很迷的做法： n(n+1)(2n+1)/6，三个乘数分别先两两除下gcd，然后分别判定sqrt是否等于自己就好。 AC代码 #include<bits/stdc++.h> using namespace std; l...

题目大意 定义传奇元组：● (1,k)始终是传奇元组。● 如果(n,k)是传奇元组，(n+k,k)与(nk,k)也是传奇元组。我们想知道1≤n≤N,1≤k≤K时传奇元组(n,k)的数目。答案取模10^9+7。 解题思路 官方题解的思路写的很清晰（出题人宁太棒了） 通过题目条件，可以发现：一旦通过(n,k)->(nk,k)的操作来推出新的元组, n必定是k的倍数；而如果没有, 那么肯定是(xk+1,k)的形式。所以，推出第一条结论：只有在满足n=1，n是k的倍数，或者n-1是k的倍数时，(n,k)是传奇元组。 因此，我们可以认为(n,k)是传奇元组，当且仅当n可以-k或/k，最后变成1。得...

题目大意 将n∗m个口罩分成k份分给医院，使得从中挑出n组，每组口罩数量一样多，也可以从中挑出m组，每组一样多，最后输出字典序最大的。 解题思路 我们可以先将n,m互换（如果m<n），使得n<m。由于要求字典序最大，装口罩最多的盒子不超过n。 医院数量为n的时候，需要给每个医院安排m个口罩，至多给每个医院(m/n)个（向下取整）盒子，每个装着n个，总的就是(m/n)×n个盒子，每个医院还要再拿m%n个口罩。这时候我们考虑医院数量为m的情况，此时需要给每个医院分配n个口罩，那显然已经有(m/n)×n个医院满足条件了，还有m%n个医院没拿到。 所以，这实现上就是个类似gcd的dfs么？...

虚树入门 前置知识 掌握求lca，dfs序，每个点的深度，两点之间的距离等操作 什么是虚树 虚树的核心思想，就是保留一棵树上有用的&关键的点，重新构建一棵“虚”树，更加快速地跑带关键点的树形dp。 怎么用虚树 这里就需要用到上面提到的求lca(最近公共祖先)技术。我们对一棵虚树的要求是，节点总数最小（没有多余的累赘），包含题目指定的节点，以及它们的lca。稍加思索即可明白，在这种情况下节点会被最小化。（因为比较易懂，就不画图了懒得画） 首先我们要在树上跑dfs，求出前缀的dfs序，再以dfs序来从小到大排序；同时我们维护一个栈，表示从树根到栈顶元素的这条链。得到关键点的时，按照dfn值...

题目大意 定义为n的最小质因子，构造一棵无限的树，树上每个n(n>1)与相连。定义为到间的边的数量（距离），给出与数组，求出 。 解题思路 一 本题因为树上节点过多，用虚树来优化树形dp是一种方法。所以，我们可以虚树二次扫描换根，求解树的带权重心来得到答案。 带权重心介绍：https://baike.baidu.com/item/树的重心/20416316?fr=aladdin本人关于虚树的博客：https://blog.nowcoder.net/n/721cb2bb714e44e59796e713d3c1420e 二 为什么可以用到虚树呢？ 推荐参考，讲解很详细：https://...

题目大意 若一个数列是由一些1∼k的排列组成，那么就被称作一个k-bag。例如，数列1,2,3,2,3,1,1,3,2是一个3−bag（由1,2,3 2,3,1 1,3,2三个排列组成）。判断一个数列是不是一个k−bag的一部分。 解题思路 以样例2,3,2,1,3,3,2,1为例，可以发现，在前面补一个1，就可以构成正确的k−bag，所以这是k-bag的一部分。 可以先考虑最暴力的方式。如果有两个连续的相同数字（如上方3,3），那么这里就一定是一个分隔点。我们枚举每个分割点，每隔k位再设置一个分割点，挨个子区间枚举。但是这种方法显然还不够快。我们可以直接扫描，遇到端点相同的区间，就判断是否...

题目大意 给定一个n×n的正方形（如下图），有k种不同颜色，给每条边染色，使其满足以下条件，输出一种方案：(1) 所有颜色的边数应该相同；(2) 不存在一个单色环；(3) 一行或一列至少存在两种颜色。 解题思路 图片转载自：https://www.cnblogs.com/st1vdy/p/13387806.html 最开始，我们要排除出掉没有解决方案的三种情况: （边数mod颜色数） 接着，我们按这样的方式给每条边标号： 对于一个1×1的环（图中橙色框），它的两条纵边序号相邻，颜色应该不同； 对于一个A×B,A<B的环（图中绿色框），它必定有相邻的横边，因此染的颜色不同；同理可以...

题目大意 定义S(x)为x数位和，给出N,满足的A,B组数。 解题思路 阅读题面，很容易想到这是一道数位DP能做的题。 我们先决定dp数组几个参数。可以列出dp[x][a][b][u][v]；其中x是现在搜到的位置，ab分别表示当前的A与B，u表示当前位之前B是否等于N(B<=N)，而v表示当前位之前A是否等于B(A<=B)。 但是a,b这两个还需要再进一步简化。所以我们可以改成dp[x][y][u][v]，其中y表示A前面位数和−B前面位数和（防负数偏移1000）。 AC代码 #include<bits/stdc++.h> using namespace std; c...

题目大意 设A={0,1}，每天Roundgod从（即维度为n，每一位由01组成的所有向量的集合）中随机选择一个二进制向量。现在他想知道n天中选取n个线性独立向量的概率。设表示n的答案，最后输出 ， 表示异或。 线性独立是什么？（其实就是任意一个向量不能通过其他两个的“加减”运算得到）https://baike.baidu.com/item/%E7%BA%BF%E6%80%A7%E7%8B%AC%E7%AB%8B 解题思路 由于这n个向量线性独立，所以张成了(N维)满秩空间，每一个向量都不属于之前的空间，总共有个向量。 我们先设有这些向量。当n=1时，有与这2个向量与线性相关；当n=2时，...

题目大意 给定n,k，构造一个1-n的排列P，使得对于1-n中的每个i，P都存在一个长为i的子序列，而每个子序列的和模n都余k。有解则输出任意P，无解输出-1。 解题思路 （做题的时候我和队友花了好久，试图凑出一种看起来靠谱的通用方案，没想到还真能歪打正着）因为长度为n的子区间只有P本身，而所有的子区间和都各自模n余k，等量代换，所以所有数的总和模n必须余k。如果1-n的总和(n(n+1)/2)%n==k，那么就一定有解决方案。 但是n确定了，不确定的k也会带来麻烦，我们似乎需要针对每对n,k指定动态的解决方案。看起来这题很困难啊。但是，稍微列几组数据就会发现，当n为奇数时，1-n的和必定是n...