传送门 t1 圆形赛道上经过次数最多的扇区 有一个圆形区域，被分成n块扇区，给出一系列起点与终点，问跑到最后经过次数最多的扇区是哪些。 赛时居然没过这题... 当时写了一个模拟，因为没处理好边界问题，死活过不去。赛后下来看了发现确实想复杂了。 我们要发现一个事实，因为赛道是圆形的，所以除了结尾的那一圈“不完整”的赛程，之前若干圈赛程都是没有意义的，因为每个扇区都同时累加了经过次数，“同时”在本题中是没有讨论意义的。所以我们的答案只用关注最后那不完整的赛程经过了哪些扇区。 值得注意的是，起点不一定是第一块扇区，所以要处理越界问题。同时，观察样例不难发现答案是有序的，所以还要对最终答案数组做一个排序。 ```cpp class Solution { public: vector mostVisited(int n, vector& rounds) { vectorans; int l = rounds[0]; int r = rounds[rounds.size()-1]; while(l != r) { if(l == n+1) { l %= n; continue; } ans.push_back(l++); } ans.push_back(r); …
传送门 t1 千位分隔数 给定一个整型数，给它每三位加上一个分隔符。 做法有很多，憨一点可以用取出每一位数字来做，但看这个范围估计是要炸的，所以我这里选择转成string来做。 转成string，计数，每三位加上一个"."最后翻转一下就行了，记得处理一下前缀“.”。 ```cpp class Solution { public: string thousandSeparator(int n) { string str = to_string(n); if(n < 1000) return str; int m = str.size(); string ans = ""; int cnt = 0; for(int i = m-1; i >= 0; i--) { …
传送门 t1 存在连续三个奇数的数组 签到题，直接O(n²)遍历就能过。 ```cpp class Solution { public: bool threeConsecutiveOdds(vector& arr) { const int n = arr.size(); if(n < 3) return false; for(int i = 2; i < n; i++) { int cnt = 0; for(int j = i-2; j <= i; j++) …
传送门 题目大意 现在有四种随从： 圣盾亡语圣盾亡语白板 如果对方随从没有免疫，以上随从都能做到一击必杀。 词缀的效果如下： 圣盾：免疫一次伤害，免疫后圣盾消失。亡语：死亡时召唤一只1/1的藤蔓。 每回合只能发动一次攻击，游戏结束时你还有随从存活就算你获胜。你很会玩，所以你一定能找到制胜策略，哪怕只有一点可能。 给你双方随从信息，请告诉我你能否获胜。 思路 贪心处理。 藤蔓没法拿来解场，只能破圣盾，因为每个随从的血量都是1e9。没有藤蔓时只能硬解，为了亏得少一些，优先用有亡语的随从解。上述条件都满足不了了，用圣盾亡语的随从。 ```cpp #include using namespace std; int t; int a[5], b[5]; void battle() { if(b[3]) { b[3]--; b[5]++; } else if(b[4]) b[4]--; else if(b[1]) { b[1]--; b[3]++; } else { b[2]--; b[4]++; } …
传送门 题目大意 有n个球队，每个球队都和其它所有球队比一场，即一共有 [图片缺失] 原图：https://www.nowcoder.com/equation?tex=%5Cfrac%7Bn(n-1)%7D%7B2%7D&preview=true 场比赛，每天只有一场比赛。每个球队会在第一场比赛开始时到，最后一场比赛后走。请安排一个日程表，使所有球队停留的天数之和最小。输出这个日程表。 思路 样例害人啊，出题人编了一个长得很像全排列的样例... 其实仔细一想会发现全排列不仅不是通解，而且大多数情况下都不是答案。当队伍多起来时，全排列会优先满足第一个队伍，这时候其他队伍只能一个一个挨着上场，浪费了大量的等待时间。 所以最优的方案可能会是一种“折中”的方案，即不去强调每一个队的最优。 ```cpp #include using namespace std; const int INF = 0X7F7F7F7F; int t, n; int main() { cin >> t; while(t--) { cin >> n; for(int i = 2; i <= n/2; i++) …
传送门 题目大意 定义S(x)为x数位和，给出N,满足S(A)>S(B),1≤A≤B≤N的A,B组数。 ```cpp #include using namespace std; typedef long long ll; const ll mod = 1e9 + 7; ll dp[110][1810][2][2]; char c[910]; int l; ll dfs( int x, int y, int u, int v ) { ll res = 0, a, …
传送门 题目大意 定义矩阵压强=F/S，其中压力F=矩阵所有项之和，面积S=矩阵最后一行的所有项之和，求出最大压强的子矩阵，并输出这个压强。 思路 根据题设老老实实算就行了，因为面积由最后一行的元素和决定，所以倒过来去枚举每一列的所有子列求最大值就行了。 ```cpp #include using namespace std; int t; double a[205][205]; int main() { scanf("%d", &t;); while(t--) { int n, m; scanf("%d%d", &n;, &m;); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) scanf("%lf",&a;[i][j]); …
传送门 题目大意 给定n,k，构造一个1-n的排列P，满足对于1-n中的每个i，P都存在一个长为i的子序列，并且每个子序列的和模n都余k。有解则输出任意P，无解输出-1。 思路 首先考虑判断解存在的问题。根据题意，因为P也是自己的子集，所以一定也应该满足“所有元素的和模n余k”的题设，也就是sum(1~n)%n==k，如果不满足，那自然无解。 假设k满足上述条件，接下来的命题就是判断k了。 这种看似要进行复杂的动态处理的问题大多都有规律，这题也不例外。多写两行数据会发现，当n为奇数时，sum(1~n)一定是n的整数倍，即k==0；n为偶数时，k==n/2。 根据这个写代码就好了。 ```cpp #include using namespace std; int n, k; int main() { scanf( "%d%d", &n;, &k; ); if ( n % 2 ) { if ( !k ) { for ( int i = 1; …
传送门 题目大意 有一个n 维向量空间，从这里面拿出n个01向量，设fn为选出的这n个01向量相互线性独立的概率，求 f1^ f2^...^ fn 的值。 思路 有n个向量，它们都线性无关，所以它们的空间秩也是n。每次随机的向量都会加入之前的向量空间，那么每一个向量都一定不属于之前的空间，则一共有2n个向量。 观察规律不难得到对于每个i，都有2i个向量线性相关，那么反之则有2n-2i个向量线性无关。那么有： [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/07/image-1.png 递推计算出每个f就行了。 ```cpp #include using namespace std; typedef long long ll; const int N = 2e7 + 10; const ll MOD = 1e9 + 7; const ll INF = 500000004; …
传送门 题目大意 游戏地图可以解释为一个无穷大的矩形网格。在每个格子里，你可以安放一台金矿，或者是一部圣水采集器，又或者是大本营。你也可以把一些格子留成绿色，充满生机。然而，存在一个限制：一个大本营必须紧挨着至少一个金矿和至少一个圣水采集器。请让你地图中的大本营数量尽可能地多，并输出它在地图中的占比。 思路 赛时这题卡了很久，最后队友的答案因为精度问题就差了0.000001，属实倒霉。 情况其实挺好想的。让金矿与圣水采集器相间排布，任意的一台金矿与一部圣水采集器都不相邻，大本营插在它们之间。 ```cpp #include using namespace std; int main() { printf("%.6f", 2.0 / 3); return 0; } ```
传送门 题目大意 有t(t<1e5)次查询，每次查询给出两个数a,b(a,b<2e6)。输出一组满足下列要求的四个正整数cdef作为答案。若不存在满足条件的cdef，则输出"-1 -1 -1 -1" [图片缺失] 原图：https://uploadfiles.nowcoder.com/images/20200719/272741694_1595159660992_6C354C0B6A13C2EFCC877EBE585BFDD3 ```cpp #include using namespace std; typedef long long ll; int a, b, g, t; ll c, d, e, f; int gcd( int a, int b ) { if ( b == 0 ) return(a); return(gcd( …
传送门 题目大意 按顺时针或逆时针顺序给出n个端点的平面坐标，它们组成一个形如下图的二维几何图形， [图片缺失] 原图：https://uploadfiles.nowcoder.com/images/20200709/329336_1594306194154_C59ABE339F9E82759BF07A316C74BFF6 判断这个图形是右手形还是左手形。图形可以被旋转但不能被缩放。 思路 题设中提到图形的大小不会被改变，也就是说即使所给出的点不同，但他们之间的相对大小是绝对地，可以从这个关系入手。 可以看见，图示中最长边就是底边，它的长度是9，而大拇指是一条紧挨着它且长度为6的边，小拇指则为8。 那么可以去找相邻的3个点，如果找到长度为9的边，就去验证是否存在长度为6或8的相邻边。因为方向不确定，所以使用向量积来判断，向量积大于0时验证大拇指，反之验证小拇指。 具体地，因为题中数据均为浮点数，所以计算距离时存在小数点的精度问题。而例图中的长度均是整数。这里采用忽略小数位的方法来近似判等，即用计算所得的距离值-目标距离值，如果所得差小于一个极小数e，那么则判二者相等。 ```cpp #include using namespace std; const double E = 1e-5; const int LIM = 20; struct node { double x, y; } a[30]; int t; bool isLeft; double dis( node x, node …
传送门 题目大意 一个游戏包含n个阶段，每个阶段有四种类型： 类型0：没有鱼也没有蛤。类型1：只有一只蛤。类型2：只有一条鱼。类型3：有一条鱼和一只蛤。 在每个阶段都可以执行四种操作之一： 用一只蛤换一包鱼饵。如果有一条鱼，可以无需鱼饵抓到这条鱼。无论在此阶段有没有鱼，都可以使用一包鱼饵捕获一条鱼。跳过阶段。 要求求出每局游戏中能抓到鱼的最大条数。 思路 采用贪心的思想。首先，对于类型2、3，显然直接抓鱼是最优的，即有鱼抓鱼。但是类型0时只能用鱼饵抓鱼，类型1时只能做鱼饵或者用鱼饵抓鱼。 根据上面的分析，前导0是可以忽略的，因为我们什么都做不了。忽略后如果遇到类型2、3就直接答案++。其余情况下，优先用鱼饵抓鱼，其次用蛤来换鱼饵。在执行完整个过程后如果还有鱼饵，那么消耗两次类型1来换一条鱼。 值得注意的是，第一次遇见类型0时是没有鱼饵去捕鱼的，所以需要用一个bool来判断当前遇到类型0时是否有鱼饵。 ```cpp #include using namespace std; string s; int t, n, bait, ans; int main() { scanf( "%d", &t; ); while ( t-- ) { int i = 0; scanf( "%d", &n; ); …
传送门 题目大意 现有函数 [图片缺失] 原图：https://www.nowcoder.com/equation?tex=%5Cbegin%7Balign%7D%0Af_c(x)%26%3D%5Cmax_%7Bi%3D1%20%5Cdots%20x-1%7D%20c%20%5Ccdot%20f_c(%5Cgcd(i%2C%20x))%20%26%20x%20%3E%201%5C%5C%0Af_c(x)%26%3D1%20%26%20x%3D1%0A%5Cend%7Balign%7D 给定一些正整数对(ni, ci)，输出fci(ni)在模1e9+7意义下的函数值。 思路 观察公式不难看出fc(x)=ck，k与函数递归次数相关。要求到最大值，贪心的想法是尽可能多地递归，这样就能累乘到更多的c。最好的情况是每次递归都只消去一个 质因子，这样k=质因子的个数。 实现上，从x开始递归 ，找每个数除了自己外最大的因数，直到当前数是质数或1。记录这个过程中递归层数，这个层数就是k。可以先预存好值来提升效率。 ```cpp #include using namespace std; typedef long long ll; const int LIM = 1e6 + 10; const ll MOD = 1e9 + 7; //arr[i]中存i的质因子个数 int arr[LIM], t, n, …
传送门 题目大意 给定一个由小写字母组成的字符串S。你要执行一系列操作。有以下两种操作：1、修改：给定一个整数x，你需要根据x的值来修改S。如果x是正数，就把S中最左边的x个字母移到S的右边；否则，就把S中最右边的|x|个字母移到S的左边。2、查询：给定一个正整数x，输出字符串中第x个字符。 思路 题面很简单，朴实的字符串位移操作。上手十分钟写了个string模拟 ```cpp #include using namespace std; int q; string str; int main() { cin >> str; scanf("%d", &q;); while(q--) { int x; char op; scanf("%d", &op;); switch (op) { case 'A': scanf("%d", &x;); printf("%c\n", str[x-1]); break; case 'M': scanf("%d", &x;); …
传送门 题目大意 对于字符串s，定义s∞=ss...sss。给定字符串s,t，判断 s∞ 与 t∞ 的字典序大小关系。(|s|<1e5) 思路 两个字符串长度相等自然没话说，直接比较就行。这题的核心在处理字符串长度不等的情况。 最开始想到的朴素做法是延长两个字符串至长度为二者的最小公倍数，再来比较，但是会双超。参阅了大佬的题解后了解到了一种全新的做法：直接比较s+t与t+s。 这样做的正确性是显然地。设s的长度为lens，t的长度为lent，lens<lent。在前lens个字符进行比较时，s[i]与t[i]是一一对应的，不存在对齐问题，而进行到lens+1时，如果执行s+t操作，相当于把之前已经确认相等的子串接在s后面，即两个字符串做了等价放大。 ```cpp #include using namespace std; string x, y; int main() { while(cin >> x >> y) { if(x + y < y + x) puts("<"); else if(x + y > y + x) puts(">"); …
传送门 题目大意 给一个长度为n的序列A={1,2,3,...,n}以及置换的次数k，在对A使用k次置换P后得到新的排列B。 输入n,k和B，输出A，如果无解则输出-1。 思路 这种“给出原序列、目标序列与置换规则”的题一般都是置换群。 首先给你一个序列，假如： s = {1 2 3 4 5 6} 然后给你一个变换规则 t = {6 3 4 2 1 5} 就是每一次按照t规则变换下去 比如这样 第一次：6 3 4 2 1 5 第二次：5 4 2 3 6 1 第三次：1 2 3 4 5 …
传送门 题目大意： 给出n个点，圆心和半径任意取的情况下，要求这n个点尽可能多的点出现在圆上。该圆一定经过坐标原点(0,0)。求满足要求的圆上至多有多少个点。 思路很清晰，三点确定一个圆，题目中又给死了一个点，那么O(n²)枚举剩下的两个点，把找到的圆心放在集合里，然后再去找出现次数最多的圆心枚举圆上点就可以了。 三点共圆圆心的寻找公式如下： [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/07/IMG_392620200716-011621-1024x981.jpg 那么不难得到它的代码表达： ```cpp point findCenter(const point &p;, const point &q;, const point &r;) { double a = 2 * (p.x - q.x); double b = 2 * (p.y - q.y); double c = p.x * p.x + …
传送门 题目大意： [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/07/equation-1024x94.png 答案一定是一个有理数，以n=p·q-1的形式并模上998244353给出。 q-1 表示q的逆元，可以用扩欧或费马小定理来算。 如果p是一个质数，而整数a不是p的倍数，则有a(p-1)≡1(mod p) 费马小定理 有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是显然地。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解，它可以用来计算模反元素(也叫模逆元)。扩展欧几里得算法 [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/07/IMG_390520200714-224509-1024x931.jpg ```cpp #include using namespace std; typedef long long ll; int const LIM = 2e6 + 5; int const MOD = 998244353; ll n; ll fac[LIM]; ll qmod(ll …
传送门 T1去掉最低工资和最高工资后的工资平均值 签到题，直接写。 ```cpp class Solution { public: double average(vector& salary) { int n = salary.size(); double sum = 0; int ma = -INT_MAX, mi = INT_MAX; for(int i = 0; i < n; i++) { ma = max(ma, salary[i]); mi = min(mi, salary[i]); sum …
传送门 T1数组异或操作 签到题，直接翻译 ```cpp class Solution { public: int xorOperation(int n, int start) { vector nums; int ans; for(int i = 0; i < n; i++) nums.push_back(start + 2*i); ans = nums[0]; for(int i = 1; i < n; i++) ans ^= nums[i]; return ans; …
传送门 T1一位数组的动态和 维护一个nums数组的前缀和，直接写。 ```cpp class Solution { public: vector runningSum(vector& nums) { vector pre; int n = nums.size(); pre.push_back(nums[0]); for(int i = 1; i < n; i++) { int tmp = pre[i-1] + nums[i]; pre.push_back(tmp); } return pre; } }; ``` T2不同整数的最小数目 题意很直观：给出一组整数arr与一个整数k，要求删除k个元素并使剩下的元素尽可能地少。 思路也很清晰，其实就是一个贪心策略。统计每个元素出现的次数，优先从出现次数少的开始删，最后剩下的元素个数就是答案。 考虑到数组中的元素范围是[0,1e9]，所以用hash表来离散处理。将统计用的hash表以出现次数为关键字做排序然后从头开始删就可以了。 …
传送门→ T1： 商品折扣后的最终价格 签到题，挺简单的。按照题意直接写就行。 ```cpp class Solution { public: vector finalPrices(vector& prices) { vector ans; int n = prices.size(); for(int i = 0; i < n; i++) { bool flag = 0; int tmp; for(int j = i+1; j < n; j++) { if(prices[j] …
传送门→ T1重新排列数组 签到题，按题意模拟就行 ```cpp class Solution { public: vector shuffle(vector& nums, int n) { vector ans; for(int i = 0; i < n; i++) { ans.push_back(nums[i]); ans.push_back(nums[n+i]); } return ans; } }; ``` T2 数组中的 k 个最强值 就是根据题目要求重新定义排序规则，在排序后取前k项即是答案 ```cpp int m; bool cmp(int a, …
传送门→ T1 数组中两元素的最大乘积 签到题，两个for。 ```cpp class Solution { public: int maxProduct(vector& nums) { int n = nums.size(); int maxn = -1; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(i != j) maxn = max((nums[i]-1) * (nums[j]-1), …
传送门→ T1:通过翻转子数组使两个数组相等 这题挺水的。题目允许任意次的变换，所以理论上只要两个数组的长度和组成元素一样那么一定可以在有限次变换后变为等价数组。统计一下两个数组的sum和length然后判断就好。 其实排序后判断每一个元素是否相同也可以，但是用一遍循环求和会更快一点点。 ```cpp class Solution { public: bool canBeEqual(vector& target, vector& arr) { int n = target.size(); int m = arr.size(); if(n != m) return false; int sum1 = 0, sum2 = 0; for(int i = 0 ; i < n; i++) { …
传送门→ A猴子摘桃 小学奥数，掰手指都能数出来是22. B平方和 也没啥好说的，填空题暴力就完事了。 ```cpp #include #include using namespace std; bool check(int x) { while(x > 0) { int t = x % 10; if(t == 2 || t == 0) return true; x /= 10; } return false; } int main() …
传送门→ 这双周赛改成贪心赛算了，fo了。 A拥有糖果最多的孩子 贪心+暴力。两重循环外层枚举每一个小朋友，内层去找当前的最大糖果数量。如果当前小朋友的糖加上额外给的能大于等于这个最大值就push一个1进去，否则push一个0。 ```cpp class Solution { public: vector kidsWithCandies(vector& candies, int extraCandies) { vector ans; int n = candies.size(); for(int i = 0; i < n; i++) { int maxn = 0; for(int j = 0; j < n; j++) if(i == j) …
日常爆零，平生夙愿是不要再爆了。比赛传送门→ A大吉大利 题目给定n(<1e5)个整数a1,a2,...,an，计算 [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/03/2020032714292561.png“&”为位与运算符 输入第一行一个整数n.第二行n个整数ai. 输出一个整数表示上述求和式的答案. 样例 样例输入 5 1 2 3 4 5 样例输出 33 赛时写了一个很老实的循环，果不其然T了。这时候基础不牢就地动山摇啊，硬是没想出来巧解，还是赛后去研究的，哎。 考虑到位与运算的特性，将样例化为二进制来分析： 0 0 10 1 00 1 11 0 01 0 1 根据题意计算，以右起第一列为例，第一个1与所有的1位与得到3，第二个1与所有的1位与也得到3....就这样得到了3个3也就是9。显然，对于数据中所有整数的第i位，运算结果就是1的个数的平方。 即，设有t[i]个数在二进制下的第i位为1，那么答案就会累加t2[i]个二进制下的1。所以就转化为了求： [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/03/2020032715275392.png 因为答案以十进制输出，所以最后还要按位权乘2的i次幂转回10进制。 #include <cmath> #include <cstdio> #include …
这么水的校内赛居然能卡掉五道，真是人间奇葩，能给自己气死。 D-矩阵 题面体育老师觉得继续刁难小R不太好，所以他对小R发起了“扣平时分”威胁！这一次他和之前不一样了，让所有同学站成一个矩形，然后他会随机点一个人，被点中的人的那一行和那一列上的所有人都会加上一个值，经过若干次点名之后，老师想让小R告诉他，数值最大的和最小的相差多少？ 输入第一行输入三个整数n（表示矩阵的行数），m（表示矩阵的列数）和q（表示老师点名的次数）。之后q行，每行三个整数（x，y，val），x和y表示被点名同学的坐标，val表示加上的值。 输出输出一行，表示最大和最小相差的值。 样例 样例输入 3 3 3 1 1 1 2 2 2 3 3 3 样例输出 4 数据范围 1 <= x <= n <= 2000 1 <= y <= m <= 2000 -1000000 <= val <= 10000000 <= q <= 10000 基础模拟题，没什么好说的。需要注意的点是对于每一个被查询的点(x,y)需要预先减去一个v值，不然会重复计算，赛时就死在这，fo了。 #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define get(x) scanf("%d", &x) #define lget(x) scanf("%lld", &x) #define set(a,b) …
A-小乔与小灰灰 题面：小乔和小灰灰是好朋友，现在如果一个字符串中同时出现子序列“XiaoQiao”和“XiaoHuiHui”，那么小乔和小灰灰都会感到开心。 输入：输入包含一行一个字符串S字符串中仅包含大写字母和小写字母 输出：如果这个串会让小乔和小灰灰都感到开心，那么输出“Happy”，否则输出“emm”。 样例数据 样例输入1： XiaoQiaoheHuiHui 样例输出1： Happy 样例输入2： Xiaohuihuihexiaoqiao 样例输出2： emm 签到题，按下标匹配。 #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define get(x) scanf("%d", &x) #define set(a,b) memset(a, b, sizeof(a)) #define rep(a, b, c) for …