#include<stdio.h> const int maxn=1100; double b[maxn],x[maxn],y[maxn]; double a[1100][1100]; double l[1100][1100]; double u[1100][1100]; int n; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%lf",&a[i][j]); for(int i=1;i<=n;i...

牛客6—— K-Bag （奇妙哈希或滑动窗口） 原题链接 题意： 定义一个特殊序列为多个1~k的排列顺序连接起来的序列，问给出的序列是不是特殊序列的连续子串。 思路： 思路一来源于铭宇巨巨，思路二来源于博客 首先可以知道，如果一个序列是特殊序列的连续子串，要么是序列是特殊序列的一部分，要么是一个特殊序列的前缀+一个特殊序列的后缀，要么就是在情况二里插入若干非零个完整的特殊序列。 那么对于一段序列我们如何判断这段序列属于特殊序列的一部分呢？比较容易想到的一种方法就是判断该序列不同数字的个数等于该序列的长度，因为特殊序列可以是1~k的任意全排列，所以这种情况一定说明该序列属于特殊序列的一部分。这种...

牛客6—— Combination of Physics and Maths （思维） 原题链接 题意： 矩形的底面积为最后一行数的和，压力为所有数的和，找一个压力/底面积（即压强）最大的可非连续子矩阵。 思路： 选择单列一定优于选择多列，证明： 所以只需要找到每列的最大即可。 代码： #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") #pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") ...

牛客6—— Easy Construction （思维+构造） 原题链接 题意： 能否构造一个1~n的排列，使得对于任意的 i (1<=i<=n) ，排列都存在一个长度为i的子区间的和%n==k。 思路： 先考虑无解的情况，当i==n时，子区间只有一种情况，元素的和为1+2+……+n，即sum=n*(n+1)/2。如果sum%n!=k的话，说明一定无解。 当n为奇数时，sum%n=0，这时候k=0，可以构造排列：n,1,n-1,2,n-2…… 这样除了首项，偶数项+下一个奇数项的和为n,所以就可以当i为奇数时，从首项开始选；当i为偶数时，从第二项开始选。 当n为偶数时，sum%n=...

【题型总结】给区间加等差数列求值问题 一、前言： 上一篇题型总结不知道扔哪去了，下午训练看到个很眼熟的题，感觉见过很多次了，就顺手总结下。 需要会的前置知识有：差分与前缀和，树状数组基础，线段树基础 二、UPC 2020年夏混合个人训练第八十场 问题 B: 序列 （二阶差分） 题意： 给定长度为n的数组和m次操作，每次操作都表示将区间[l,r]加上一个首项为s，末项为e的等差数列，求操作后序列每一项的异或和。 思路：  序列[l]+=首项;序列[l+1]+=公差-首项;序列[r+1]-=首项+(r-l+1)公差;//注意r+1处要减，其余的均为加。序列[r+2]+=首项+(r-l)公差;  代...

牛客多校2—— Boundary （计算几何） 题意：给出 n 个点，需要我们选择一个经过原点的圆，使得这个圆经过尽可能多的点，输出最多可以经过多少个点 思路： 三点不共线的点确定一个圆 O点已经确定，O（n）枚举另一个点P，O（n）枚举第三个点 ，这样三点就可以确定一个圆心，每次都取圆心出现最多的次数。 注意枚举的时候排除掉三点共线的情况。 代码： #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") #pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4...

牛客—— 红球进黑洞 （线段树+位运算） 铭宇巨巨推荐的题！ 原题链接 题意： 给定一个序列，两种操作，一是区间求和，二是将区间里的每个数都异或x。 思路： 一眼就线段树，关键是怎么维护第二个操作。 借助最小异或生成树的思想以及异或题的常见套路，我们可以把每个数都进行二进制拆分，用线段树分别维护每一位上的0和1。 对于操作二，我们只需要分别维护每一位的值即可；对于操作一，计算区间里1的个数乘以对应的位数，就相当于是二进制转化为十进制的过程。 代码： #pragma GCC optimize(3) #pragma GCC optimize("Ofast","unroll-loops","omit...

【牛客】 小A的最短路 （LCA） 原题链接 题意： 给定一棵树，除给定的特殊边边权为0外，其余边权均为1。求两点之间的最短距离。n为3e5 思路： 题目是一棵树这个条件有点隐蔽直接进行最短路可能并不可行，考虑树上求两点距离的方法，一般就是LCA。 因为存在特殊边，所以节点a和b之间的距离可能有三种情况，一是考虑不经过特殊边，直接从节点a到节点b；二是考虑经过特殊边，这时候就考虑顺序了，设特殊边的两个端点分别是q,w；要么是a-x-y-b,要么是b-x-y-a；三者取min就好了。 代码： #pragma GCC optimize(3) #pragma GCC optimize("Ofast"...

最小异或生成树 一、前置知识： 1.Trie树： 高效的存储和查找字符串集合的数据结构   int son[maxn][26],cnt[maxn],idx; void add(char *str){///将新的字符串插入到字典树里 int p=0,len=strlen(str); for(int i=0;i<len;i++){ ///遍历字符串的每一个字母 int tmp=str[i]-'a'; if(!son[p][tmp]) son[p][tmp]=++idx;///没有节点的时候就创建节点 p=son[p][tmp];///往下走 } cnt[p]++;///表示该地方有一个字符串...

牛客——点权和 （4个月前好像见过这个题？） 思路： 考虑每次修改后对答案的贡献，对于一个点来说，考虑这个点会影响到哪些点。 考虑只进行一次更新的情况：首先，就是本身，本身的节点值对答案的贡献是度数+1，因为本身的点权会更新，邻接点也会更新；再者，就是他的父节点，父节点对答案的贡献是2，因为在这个过程中本身和父节点的点权都+1了；最后就是他父节点的父节点，因为父节点的更新使得爷爷节点对答案的贡献为1；再考虑他的父节点的其他子节点对他的贡献，这时候要注意去重。 多次的话，我们只需要维护cnt1[x]表示x的操作次数，cnt2[x]表示x的父节点的子节点（即x的兄弟）的操作次数和res[x]表示答...

牛客—— [SCOI2009]生日快乐 （dfs）原题链接：https://ac.nowcoder.com/acm/problem/20272题意： 给定一个矩形蛋糕，只能平行x轴或y轴切n-1刀得到面积相等的n块蛋糕，求n块蛋糕的长边与短边比值的最大值最小的值。 思路： 被题意迷惑以为是二分。 因为数据范围很小，考虑状压dp或dfs。 我用的是dfs，因为感觉double类型的dp并不好转移。考虑切每一刀的时候是平行x轴切还是平行y轴切，然后再枚举一下切的位置，当只剩一块的时候返回答案。 #pragma GCC optimize(2) #pragma GCC optimize("Ofast"...

牛客—— 矩阵取数游戏 （DP+int128的黑科技） 题意： 给定一个n*m的矩阵，矩阵中的每个元素都有自己的值a[i] [j] ，对于每一行，每次都可以取走该行的行首或行尾的元素，其对得分的贡献是 被取走的元素值 *2^i，其中i表示第i次取数（从1开始编号）,求取完n行的最大得分。 思路： 首先要考虑的是，对于每一行而言，每次的取数方案对答案的影响都只会本行，而不会影响到其他行，也就是说，我们可以单独对每一行进行考虑。 接下来单独考虑每一行，因为题目中要求取数只能从行首或是行尾取，所以会发现某一行的状态是从一个区间转变成了另一个区间，这恰好符合区间DP的特点： 以区间作为“阶段”，以划分...

牛客—— 漂亮的公园 （离散化+LCA+结论） 原题链接 题意： 给定一棵树，每个节点都对应有一个颜色，问询问的两个颜色之间的最大距离（可两个颜色可以相同也可以不同）。 思路： 首先要知道一个结论是对于同一种颜色的直径端点a,b,另一个点c到达这种颜色的最大值，一定是dis(a,c)和dis（b,c）中的最大值maxx。所以对于两种颜色，只需要枚举两种颜色的直径端点，取最大值即可。 证明的话是看了tzc_zwj的博客，假设存在d点使得dis(d,c)大于maxx，当d在ab的路径上时，显然maxx更大，因为加上了路径上的一段；当d不在ab的路径上时，显然可以通过d到路径上，再到端点，也是max...

牛客——小A与小B （双向广搜） 题意： 迷宫，小A每次可以移动一个位置，而小B每次可以移动两次位置，小A移动的方向是上下左右左上左下右上右下8个方向，小B移动的方向是上下左右4个方向，请问他们最早什么时候能够找到对方，如果他们最终无法相遇，那么就输出”NO"。  思路： 双向广搜经典问题 将A和B的起始位置都加到队列里，同时跑BFS，判断走过的位置是否已经被对方走过，如果走过的话，说明已经相遇了，输出即可。 要注意A和B走的方向和步数不一样。 代码： #pragma GCC optimize(2) #include<bits/stdc++.h> using namespace s...