题目大意 存在n对情侣，一共2 * n个人，现在要求每对情侣都不能相邻而坐，有多少种排序的方案。 Solution 首先这是一个环，所以1234与2341是同样的方案，那么从n对情侣中先把男生挑出来共n个人先去坐位子，共(n-1)!个方案。 接下来就是把剩下n个人插入进去了。定义dp[i]代表安排完前i个人的时候的方案数。 1、dp[i-1] * (n+i-3) 上面的式子是直接插入方式，安排第i个人的时候，一共有n+i-1个人，那么就有n-i+1个位置可以选，但是又不能和自己情侣相邻，减掉她左右的两个位置即可。 2、dp[i-2] * (i-1) * 2 这个式子是间接插入，就是说现在在安排...

题目意思： 给你1 - n的一个序列，你可以随便定义一个长度形成环，过了一段时间会回到1 - n这个状态，问这个时间的集合大小是多少？ Solution 显然这个回到起点的时间就是LCM全部环的长度，问题就变成了，n分隔成若干个数，求他们LCM的种类数。枚举全部的可能一定会T掉，所以转换一下，LCM的种类数，也就是LCM不变的情况算一次即可，当你又枚举了不是一个不是素因子的数，一定会和之后的枚举重复，所以这类枚举是不必要的 使用筛法选出全部的素数，使用dp[i][j]代表前i个素因子总和为j的情况，那么可以得到转移方程观察这个式子，和完全背包问题是原模原样的，使用滚动数组 or 直接压掉第一维...

Solution 中文的题意说的比较清楚，说下膜拜的大佬做法，大佬题解传送门 我们需要让整体学生等候时间最短，那么就要遵循几个原则。首先我们对到来时刻升序排序，依次处理。我们暴力搜索下去需要两个函数参数，搭载的人员数量和当前汽车回到起点所在时刻1、如果回来之后没有一个学生在等车，直接跳转到下一个需要搭载的同学时刻。2、回到起点之后，在等车的全体同学一定是上车的。3、考虑是否等待下一个同学再发车，合并取min即可 如此一来框架就有了，使用记忆化搜索数组dp[i][j] 表示运送完成i个人 并且第i个人等了j分钟下的整体最短时间一共只有500个学生，等待时间最长为发出空隙m，为100，所以数组开到...

题目描述 给出一维线段长度n，客栈装修颜色k，咖啡店最高的花费p。再给出n个点的装修颜色和咖啡店花费，问你在装修颜色相同的两家店，左右闭区间的情况下，区间咖啡店最小值小于等于p的集合有几个？ Solution 因为咖啡店是顺序给出的，我们直接对着先录取颜色和咖啡店花费，如果当前点的花费小于等于p，那么和当前节点相同颜色的在它左边的咖啡店都可以去了。按着这个思想编程就可以了，还有一个注意的就是它左边的咖啡店不需要开个for去遍历了，运用pre前驱数组，判断可以去的最右边的点有没有大于等于当前颜色的前一个出现位置，如果大于了说明左边出现的同颜色点都可以选择。吧答案累加上去即可。  #pragma ...

A、数字计数 直接排序，注意要去掉重复，样例坑了一手。其他根据题意翻译就行了  #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #include <bits/stdc++.h> using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) #define all(__vv__) (__vv...

题目描述 给出长度为n 的序列，这个序列得出公式也给出，各个系数以及模数依次给出，自己递推出全部的序列。在得到这个序列基础之上，询问你，是否可以构造一个新的数列，在原数列原来位置的数值只做加减法。得到的新数列需要保证不递减，即后一项不比前一项小。，每两项之间都要符合这个要求，问你符合要求的最小的改变量是多少？ Solution 找到关键MAX中最小，考虑二分解法。通过递推得到这个序列，之后直接二分答案。我们知道这个新序列需要单调不递减，第一项先让他尽可能小，后面才更有机会，后面我们只做一个要求。如果当前项之前本来就大于新构造的前一项，就用max求到新的制高点。否则如果当前项加上了mid，仍然不...

题目意思 给出n个二维坐标点，n<3001，下面依次n行，问最大的圆半径是多少可以保证三个圆心下构成的三个圆最多相切但是不相交。 Solution 纯暴力解法，On^3，枚举点坐标，复杂度太大，一定是超时的，但是思路是三个点距离求最小的，最后外层循环找最大直接枚举点不行，那就换个思路，通过n<3001，发现可以放下n*n个线段，既然我们要找最长的可行线段，我们就把这些线段保存起来。通过一次排序，从大到小排好序，接下来依次从大到小枚举线段两端点。如果枚举到的这条线段两端都在之前和另外一个点有过连接，说明当前线段就是可选的最大值。假设当前枚举的是点A和点B，如果存在一个点C，CA和CB...

Solution 给你一些父子关系，判断这个些点构成的集合是否是一棵树，内存给的很小。使用并查集维护，如果集合内部合并说明形成了环，不是一棵树，多个根节点，也不是一棵树。最后注意特判一下空树的情况就可以过了。 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #include <iostream> using namespace std; #define js ios::sync_with_st...

题目描述 给出n个数，n<5000第二行给出n个数的权值分别是多少，给出f函数的定义，是依次相邻的异或，直到最终函数参数只有一个，得到的值就是参数的值。下面给出q次询问，每次询问给出l，r，问在这个区间中最大的f是什么？ Solution 异或可以抵消，所以枚举起来不是很复杂，我枚举了长度为3，长度为4，长度为5的。下意识根据下面代码的注释，我根据片面的最后一步，以为区间长度奇数就是a[l]^a[r]，区间长度偶数就是区间异或和。写完之后发现样例二的第一组输入过不去。再枚举6的情况，我发现BUG了，我发现最后一步异或是规律比较困难，但是回到倒数第二步会发现。异或都是f(l,r-1) ^ ...

赛后叨逼叨，这场校赛难度适中，适合编程能力适中的同学，一些常见的知识点就可以AK。没有专门的难题可能是第一次出题，之前校内也没组织过，导致题面大多数据范围缺失，题意不明…… A、不一样的食物链 第一行给出一个整数N，代表下面存在N对关系。每对关系前为A，后为B，代表A吃B。问N对关系输入完成之后是否每个人都有吃它的人。使用一个set吧全部的B插入即可，再遍历出全部的字符串。一一模拟判断即可。  #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-l...

A、Permutation 给你一个质数p，p<1e6，是否存在一个序列，当前项是前一项的两倍或者三倍，把1~(p-1)全部刚好只选取一遍。如果不存在输出-1，如果存在输出这个序列。 赛后补的题目，看了看其他人的题解没什么人说为什么1要放在最前面。。好像有人提到2x模p成一些环，3x模p又成另外一些环，这样把1放在最前面成立就代表有解？不成立就代表无解？我的结论是猜的，有待改进，默认把1放在最前面。接着就是建图跑边的操作了，根据题目的需求，可以去到的点进行连边，跑一边DFS把去过的点打上标记，或者放进数组。最后统计是不是p-1个点在统计的数里面就行了。  #pragma GCC targ...

A、Groundhog and 2-Power Representation Python的签到题，会Python就很简单，直接替换加eval就行了 s = input() s = s.replace('(', '**(') print(eval(s))  F、Groundhog Looking Dowdy 一共有n天，我们要选择其中m天。每天必须穿一件衣服，没有上限控制，后面有n行，第一个数代表当天衣服数目，紧接着就是每件衣服的权值。我们要选出m天中，最大减掉最小权值的最小值是多少？最小值，考虑二分答案求解。首先使用二元组，第一元是衣服的权值，第二元是第几天能穿。按照sort默认的二元组进行...

参考题解 题目意思 第一行一个T，代表总操作数T，T<4e5后面有T行，分三种情况。第一个数是1，生成一个新的节点挂在第二个数的子节点位置，编号为第几次操作1就是几。第二种情况是第一个数为2，把第二个数以及全部子树权值都增加第三个数大小。第三种情况是第一个数是3，直接输出第二个数的权值。 Solution 动态建树，以及区间改动，并不好实现。我们采取一种离线的做法。在输入的时候，保存好操作信息，主要就是保存好下面代码中的b[i]数组。用vector模拟建树，用DFS序表示每个节点掌控的数字下标范围。操作2就是常规的树状数组区间改变。在每次操作1中用另外的一个数组，初始化值为负的父节点权值...

Solution 题意：给你n个物品，n<21，再给你最多装w的箱子，箱子有x个。第二行给出n个物品的重量，问能不能用x个箱子把这n个物品全部放进去，物品不能够分隔。 暴力DFS，数据范围w,x,以及单个物品重量都达到了1e9的大小，但是看到物品只有21个，并且不能拆分，就知道最多也就安排21个箱子，可以暴力求解。初始化每个箱子大小都是w，能放就放，新来的物品就额外最多安排一个新的箱子就行了不用安排到x个箱子。在通过sort对全部的物品降序排序，减少回溯次数。时间来到5MS...  #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #prag...