链接：https://ac.nowcoder.com/acm/contest/5945/A 来源：牛客网
题目描述 “这波啊，这波是肉蛋葱鸡！” 打出口令即可领取签到奖励。
输入描述: 没有输入。
输出描述: 见样例输出。
示例1
输入 non
输出 roudancongji
说明 如果你不知道题目在讲什么也没关系，你只需要输出样例即可通过本题。
思路： 签到题，看懂提就行
代码：
链接：https://ac.nowcoder.com/acm/contest/5945/B 来源：牛客网
题目描述 我们要做一个旋转木马！ 输入一个n imes nn×n的字符矩阵，将其顺时针旋转90度后输出。 输入描述: 每个测试点仅包含一组输入数据。 第一行一个整数n(1 leq n leq 1000)n(1≤n≤1000)，表示矩阵大小。 接下来n行，每行一个长度为n的字符串，仅包含小写字母，表示这个矩阵。 输出描述: 输出顺时针旋转90度后的矩阵，行末不要出现多余空格。
示例1 输入 3 aaa bbb ccc
输出 cba cba cba 思路： 也是个签到题，不需要任何算法知识背景，不多说了
代码：
链接：https://ac.nowcoder.com/acm/contest/5945/C 来源：牛客网
题目描述 大司马绰号“电竞希金斯”，所以他的几何非常好。他发明的“马氏几何”多次挑战牛顿和爱因斯坦的理论，连奥沙利文都直呼内行。 本题就是一道关于计算几何的题目。 给定一条直线ax+by+c=0，请以编号从小到大的顺序输出这条直线经过的象限。 注意，x轴和y轴不属于任何一个象限，第一象限为x,y>0的区域，第二象限为x<0,y>0的区域，第三象限为x,y<0的区域，第四象限为x>0,y<0的区域。 输入描述: 每个测试点仅包含一组输入数据。 仅一行空格隔开的三个整数a,b,c(-100 leq a,b,c leq 100)a,b,c(−100≤a,b,c≤100) 其中a和b不会同时等于0 输出描述: 一行，按照顺序输出经过的象限。 如果直线不经过任何象限，请输出"non"。
示例1 输入 1 2 3
输出 2 3 4
思路： 简单的数学题，没啥好说的…
代码：
链接：https://ac.nowcoder.com/acm/contest/5945/D 来源：牛客网
题目描述 “我们厦大的ACM实在是太厉害了” 在我校无数的菜鸡中，这句话打开了财富之门，因此被称为财富密码。 事实上，关于密码学的研究里面有很多涉及到数论的知识，以下就是一道例题。 求有多少整数n(1 leq n leq x)n(1≤n≤x)满足na^{n} equiv b (mod p)na n≡b(mod p)，其中p是一个质数。 看到这里你可能认为我会解释上述符号的意思，然而如果你看不懂上面的式子，那么我不建议你尝试这道题目，所以这里没有解释。
输入描述: 每个测试点仅包含一组输入数据。 第一行，四个以空格隔开的正整数，分别表示a,b,p,x(2 leq p leq 10^6,1 leq x leq 10^{12},1 leq a,b < p)a,b,p,x(2≤p≤10 6,1≤x≤10 12,1≤a,b<p)
输出描述: 一个正整数，符合条件的n的个数。
示例1 输入 2 3 5 8
输出 2
思路： 需要一些简单的数论知识：
然后在范围内的计入答案就可以了。 代码：
链接：https://ac.nowcoder.com/acm/contest/5945/E 来源：牛客网
题目描述 安徽芜湖有n个机场，一共有m条线路在空管部门报备。 每条线路单向连接两个机场，并且需要的通行时间每天都可能不一样。 具体来说，设目前是第x天，那么第i条线路所需要的通行时间为k_ix+b_ik i x+b i。 一年一共有H天，也就是说，x取[0,H]中的整数。 现在大司马想从1号机场在一天内换乘任意多次航班前往n号机场，他总是选择用时最短的方式，现在他想知道哪一天需要花最长的时间。 输入描述: 每个测试点仅包含一组输入数据。 第一行三个整数n,m,H(1 leq n,m leq 114514,1 leq H leq 10^9)n,m,H(1≤n,m≤114514,1≤H≤10 9)，表示机场的数量，线路的数量和x的取值范围。 接下来m行，每行四个整数u_i,v_i,k_i,b_i(1 leq u_i,v_i leq n,-10^9 leq k_i,b_i leq 10^9)u i,v i,k i ,b i(1≤u i ,v i ≤n,−10 9 ≤k i,b i≤10 9)，表示一条线路从u_iu i机场单向前往v_iv i机场，并且第x天需要k_ix+b_ik ix+b i的时间来通行。 同一对机场之间可能有多条航线，一条航线的起点和终点可能相同。 保证在[0,H]中的任意一天，每条航线的长度非负且不超过10^910 9，且从1号机场可以到达n号机场。
输出描述: 输出一行一个整数，表示最长的用时。
示例1 输入 4 6 2 1 2 -2 6 1 3 3 3 1 4 -1 4 3 2 1 5 3 4 -3 7 2 4 0 5
输出 4
思路： 这个题目的路径是变化的，因为bi和ki是确定的，所以路径长度随着天数的变化而变化。题目要求的是0-h天里花费时间最长的那一天。因为路径变化并没有规律。考虑到bi和ai都是固定的，最短的情况应该就是第0天或者第h天。那么答案应该在0-h中间，0-h的最短路可以看作是一个向上凸的二次函数曲线，可以用三分的方法求出最高点。三分设左边界为l，右边界为r，ml=（l+r)>>1，mr=（r+ml）>>1;如果ml天的最短路大于mr天的最短路，那么答案可能的区间可以缩小到[l,mr]，反之区间缩小为[ml,r]。mr-ml<10后，直接暴力把答案精确的求出来就行了
代码：
链接：https://ac.nowcoder.com/acm/contest/5945/F 来源：牛客网
题目描述 给定一个正整数n，请求出所有满足如下两个条件的正整数集合x[1],x[2]…x[n]:
- x[1]+x[2]+…+x[n]=2n
- 不存在一个划分将集合划分成和相等的两部分，也就是说，集合的任意子集和均不为n。 请按照集合中元素升序排序后字典序从小到大的顺序输出答案，若不存在这样的集合请不要输出任何字符。
输入描述: 每个测试点仅包含一组测试数据。 第一行一个正整数n(1 leq n leq 1000)n(1≤n≤1000)。
输出描述: 多行，每行代表一个可能的答案序列。 同一个序列内所有数从小到大排序，相邻两个数之间用一个空格隔开，行首尾不要添加多余空格。
示例1 输入 3
输出 1 1 4
思路：
我们先拿一些具体的例子试一试吧，看能不能找到突破口。 n == 1 :[2] n == 2 :[1,3] n == 3 :[1,1,4] 、[2,2,2] n == 4 :[1,1,1,5] n == 5 :[1,1,1,1,6] 、 [2,2,2,2,2] 。。。。。。。。。 我们似乎得到了什么规律了 首先对任意n，[1,1,1,1,1,1,…,n+1]一定是正确的(n-1个1，1个n+1) 而当n为奇数时[2,2,2,2,2,2,2…]也是正确的(n个2) n==1时两者重合了 这两点都不难理解，重要的是接下来的一个归纳： 除了这两种其他的任何集合都会有和为n的子集，不满足情况！！！！！！！！！！！
下面我们来证明这个归纳！！ 我们从这开始[1,1,1,1,1,1,…,n+1] 这是我们目前的序列 我们有n-1个1，1个n+1 我们从n+1向前扔k个1, n>=k>=1 这k个1一共落在了b个位置上， k>=b>=1 那么我们现在还拥有： A、n-1-b 个 1 B、一个 n+1-k C、b个总和为k+b，单个最小为2的数 我们要证明这些数一定能凑成n 首先我们有了n-1-b个1了那么这意味着什么？ 意味着如果我们用B和C中的元素凑成 [b+1,b+2,b+3,b+4,…,n-1,n] 中的任意一个数值游戏结束！！！！！ 而有趣的是，我们A，B，C中所有元素的数值总和为2n 那么B和C的元素的总和为2n - (n-1-b) 为n+1+b !!!(看上面的区间) 正好为：(b+1) + n、(b+2) + (n-1)、(b+3) + (n-2) 、(b+4) + (n-3) 。。。。。。。 而B和C中至少也有两个元素，那么只要区间[b+1,b+2,b+3,b+4，。。。。n-1,n] 保持对称性的情况下，一定能找到n即一定不成立！！！！！！ 那么什么时候不保持对称性呢？b+1 == n即b == n-1 也就是说，[1,1,1,1,1,…,n+1]最后一位向前n-1位都发了一个1 大家都变为了[2,2,2,2,2,2,2,2,2,2,…] n位奇数时true，为偶数时false 证明完毕！！！！！！！！！！
证明并不严谨，可能会有漏洞，，，，如果发现希望指出，谢谢
代码：
链接：https://ac.nowcoder.com/acm/contest/5945/G 来源：牛客网
题目描述 大司马的重要理论成果之一即所谓正方形打野，本题恰好与正方形相关。 大司马的家的地板可以看成有n imes mn×m个格子的矩形。现在他需要用一些颜色的瓷砖来铺满这个房间，每种颜色的瓷砖摆放数量不受限制，但不能在同一个格子上覆盖多块瓷砖，更不能有空格子。 所有的瓷砖都是正方形的，然而这些瓷砖的边长却不一定相等，如:1 imes 11×1的瓷砖可以覆盖一个格子，2 imes 22×2的瓷砖可以覆盖4个格子。每一种不同的瓷砖的颜色分别为大写字母A,B,C,D,E等以此类推，本题数据保证所需颜色不会超过26种。 大司马是一个有强迫症的人，他不能忍受地板上出现一个非正方形的色块，即所有同色连通块必须为正方形，这里的连通指上下左右四连通。 当大司马的房子为4 imes 34×3时那么他的地板可以覆盖成这样: AAA AAA AAA BCB 不能覆盖成这样: AAA AAA AAA ACB 因为A对应的同色连通块不是正方形，多了一块角。 大司马希望按照从上到下，从左到右的顺序他房子地板颜色的字典序最小。 即将第一行，第二行……第n行从左到右对应的字母序列串成一个字符串，其字典序最小。 对于给定的n,m，请你输出对应的方案。 输入描述: 每个测试点仅包含一组输入数据。 第一行两个空格隔开的正整数n,m(n,m<=100) 输出描述: n行，每行一个长度为m的字符串，表示最终的摆放方案。 示例1 输入 复制 13 15 输出 复制 AAAAAAAAAAAAABA AAAAAAAAAAAAACB AAAAAAAAAAAAABA AAAAAAAAAAAAACB AAAAAAAAAAAAABA AAAAAAAAAAAAACB AAAAAAAAAAAAABA AAAAAAAAAAAAACB AAAAAAAAAAAAABA AAAAAAAAAAAAACB AAAAAAAAAAAAABA AAAAAAAAAAAAACB AAAAAAAAAAAAABA
思路： 我们仔细看这道题的要求： 1.保证所有连通块是正方形 2.尽量让这个地板从上到小，从左到右最小 那么我们想想，首相对于第一个格子我们首先肯定会铺A之后向右看尽量铺设A直到这一行铺满 或者说是列数不足以让我们维持正方形了。 这里我们只要贪心的考虑让右边的格子尽量小就可以了，无需考虑下方。 那关键是接下来倘若行数没有铺完列数铺完的情况下怎么考虑？ 例： AAAABA AAAACB AAAABA AAAACB 我们是怎样得出右边的 BA CB BA CB 的呢？ 我们在上面的分析中有一句话： 这里我们只要贪心的考虑让右边的格子尽量小就可以了 也就是说我们只用考虑右方。 假设我们现在开始铺设瓷砖B，我们判断下一个即第一行最后一列该铺设什么 我们有两种选择： 1.铺设瓷砖B同时形成正方形(这里要保证不超过列数与行数) 2.铺设其他瓷砖，瓷砖B的正方形到头，新的时***启。(这里的其他瓷砖是可铺设的) 那我们的问题主要是接下来铺设的时刻如何正确选择操作1，2 我们会在两种情况下使用操作2 (1):铺设B无法形成正方形 (2):在可铺设的瓷砖中有比B要小的瓷砖 满足这两个条件的任意一个，我们就不得不选择操作2而非操作1 其实上述的两种情况我们可以归为一种：在可铺设的瓷砖中最小的瓷砖不是B 那么我们就会采取操作2
如此我们从上到下，从左到右的遍历矩阵，正方形的填充矩阵。
代码：
链接：https://ac.nowcoder.com/acm/contest/5945/H 来源：牛客网
题目描述 大司马每天日程太多，需要一个高效的数据结构进行时间管理。经过研究，他认为这个问题可以被归结如下： 给定一个长度为n的序列，第i个元素为a_ia i ，请支持如下两种操作： 1 l r x(1 leq l leq r leq n,1 leq x leq 10^9)1 l r x(1≤l≤r≤n,1≤x≤10 9 )，表示将a_l sim a_ra l ∼a r 的值都与x取最大公约数，即对于l leq i leq rl≤i≤r，将a_ia i 替换为gcd(a_i,x)gcd(a i ,x)，两个数的最大公约数是能够同时整除两个数的最大数。 2 l r(1 leq l leq r leq n)2 l r(1≤l≤r≤n)，询问此时a_l sim a_ra l ∼a r 的和。 请注意，操作有时间顺序，2类操作输出的是进行询问时对应区间的和。 输入描述: 每个测试点仅包含一组输入数据。 第一行两个整数n,m(1 leq n,m leq 114514)n,m(1≤n,m≤114514)，表示序列长度和操作个数。 第二行n个整数，第i个整数表示a_ia i 的初始值(1 leq a_i leq 10^9)(1≤a i ≤10 9 )。 接下来m行，每行为题目描述提到的的两种格式之一，表示一次操作，操作按照时间顺序给出。 输出描述: 按照输入顺序，对于每个2类操作，输出一行一个整数表示对应的和。
示例1 输入 6 4 9 9 6 2 5 1 1 1 3 6 2 2 5 1 2 5 4 2 1 6
输出 16 10
思路： 这道题跟区间开方思路类似。 每次对一个区间进行gcd的话一般会有大部分会变成1，可以用一些小技巧来保证复杂度不会太差，用一个tag变量去标记一下这个区间是不是全都相等，再用一个sam变量去标记区间全相等的时候的元素大小，这样修改的时候对于区间元素都相等的直接对sam进行gcd即可。最后用一个线段树维护标记。
代码：