题意 一套牌有四种属性，每种属性都有三种特征，shapes (one, two, or three), shape (diamond, squiggle, or oval), shading (solid, striped, or open),  color (red, green, or purple)，如果是*，可以选任意一种。给出n套牌，每套牌给出[<number>][<shape>][<shading>][<color>]，问有没有三张牌符合同一属性的特征要么全都相同，要么全都不同。 题解 暴力瞎搞就好了，这应...

题意 给出n对数，你可以操作n次，每次操作只能在下面三种中选择一种，问最多可以选多少个不同的数字。 什么都不做 如果a[i]以前没选过，那么可以选择a[i] 如果b[i]以前没选过，那么可以选择b[i] 题解 想法很简单，就是一个并查集。 如果a[i]和b[i]的父亲一样，那么用一个数组记录一下这个父亲，说明这个堆里有环，否则把a[i]和b[i]合并，然后用map离散化（菜鸡懒惰的做法），计算每个堆里有多少不同的数字，如果这个堆里有环，就加上不同数字的个数，否则加上不同数字的个数-1。自己写几个数就看出...

题意 有n道菜，1≤n≤105，a[i]是每道菜可以赚的钱，−109≤ ai ≤109，b[i]是这道菜的个数，1≤bi≤105，你每次只能选从1开始连续的菜，然后问最多有多少顾客，并且顾客最多的前提下赚的钱最多是多少。 题解 这个题的重点在于会用__int128，我都没见过，好菜呜呜。 从数据可以看出，爆long long了，一开始没发现，和队友疯狂wa，然后还是不会负数的大数，赛后发现可以用__int128，__int128的用法见：https://blog.csdn.net/shadandeajian/article/details/818...

BDH B. Mask Allocation 题意 题目读了半天才读懂.... 有n*m个口罩，把他们装到盒子里，然后必须满足既可以把这些口罩分成n组，一组m个；也可以将它们分成m组，一组n个。要求分的组数最少，并且字典序最大。 题解 比赛的时候没敢写，没造出来样例，怕演了队友... 就是类似于gcd一样的dfs，如果 n<m 的话，交换n和m，每次取n/m*m个m，然后剩下的n%m个m就继续往下递归，直到口罩分配完。这样写代码有点不美观，可以直接变成类似于辗转相除法一样的。具体看代码。 代码 #include<bits/stdc...

题意 给定n个字符串 s[i]，再给出m个查询的字符串 t[i]，问 t[i] 是否为某个 s[i] 循环无限次的子串。 题解 分成两种情况 ① t[i] 比 s[j] 短， 这个时候可以用后缀自动机，把每个 s[j] 重复一次，然后放到SAM中，这样直接每次直接查询就好了。当然，因为是有t（t<=1e5）组数据，全部初始化肯定会超时的，所以下一个要用到哪部分哪部分就初始化，这样最多初始化1e6次，因为所有的长度不会超过1e6。 ② t[i] 比 s[j] 长，这样的话就不能用后缀自动机了，因为并不知道 t[i] 到底是 s[j] 重复了几次的子串。考虑到 ...

题意 有一个n*m的地毯，aij表示地毯每格的元素，bij表示地毯每格的价格，要求选取一块价格最大值最小的地毯，并且这块地毯无限铺开之后，原地毯是其子矩阵。 题解 先找到这个矩阵的最小循环节子矩阵，求一下每行的循环节长度用map记录，取出现次数为m并且循环节长度最小的；每列也求一下循环节长度用map记录，取出现次数为m并且循环节长度最小的；这样就得到了最小的循环节子矩阵。然后问题就变成了求一个p*q的子矩阵最大值的最小值，可以参考这个题 Fake Maxpooling （求得是k*k子矩阵的最大值的和）稍加修改变成求p*q子矩阵的最大值的最小值就好了。这里...

BCEGK B. Binary Vector 题意 大概是说有一个A={0,1}，每天可以在An (n维空间) 中生成一个新的二进制向量，n天中生成的向量线性无关的概率是，求。 题解 由于这N个向量线性无关,则这N个向量张成的空间秩为N,考虑将每次随机的向量加入之前向量的空间，那么最后N个向量秩为N当且仅当每次加入的向量都不属于之前的空间。 线性无关的意思是一组向量中任意一个向量都不能由其它几个向量线性表示. 假设第一天生成了向量a，那么和它线性有关的向量有2个：0，a。 第二天生成的向量是b，那...

DEFI D. Drop Voicing 题意： 给你一个数列，你可以进行两种操作。 Drop-2: 将n-1位置的数移到第一个位置，变成 pn−1, p1, p2, …, pn−3, pn−2, pn。 Invert: 将第一个数移动到最后一个位置，变成  p2, …, pn−3, pn−2, pn−1,pn, p1。 每次操作可以选择一种不限次数的移动，问Drop-2操作最少几次。 题解：...

前几天打牛客的多校，今天写这个题发现是基本一样的题，改成多组输入，map改成unordered_map（不然会t），最后的乘平方改成乘一次就好了，不要取模。 先对所有的字符串后缀hash，用unordered_map记录每个hash值（后缀）有多少个一样的。这个地方后缀的 hash 值可以将字符串倒过来求，每次乘以base^ i ，这和字符串正着求每次 t=t *base + s 是一样的，可以想象一下，前后缀相同位置乘base的次数是一样的。然后遍历所有的前缀的hash，在unordered_map里找当前 hash 值出现的次数的记录下来，最后把符合条件的长度平方乘以个数加起来，即a...

H. Haeder Gcd Problem 题意 集合A和B都是{1,2,.....,n}的子集，A∩B≠∅。问A和B最多有多少对数GCD(Ap，Bq)>1。 题解 所有gcd>1的两个数肯定是倍数关系，最小肯定是本身和2倍。越大的数能和他匹配的就会越少，为了简单，从大的数往小的数匹配。先用线性筛O(n)预处理出1-n之间的质数，然后找到小于n的质数最大，并且要有至少一个数可以和他配对。从这个质数开始往下计算，如果有偶数个可以和该质数配对的，那就直接记录下来；如果是奇数个，最简单的方法是将这个数的二倍放弃，剩下的记录下来。因为是2的倍数，肯定存在，并且方便计算。 代码 #inclu...

BCFH B. Basic God Problem 题意 给出c和n，求fc（n）。 题解 递归到最后 fc 函数肯定等于1，那么就变成了求c被乘了几次，只要找到 x 最多能被分解成多少个数相乘就好了。预处理用线性筛求出每个数最多能被分解成多少个数相乘，快速幂求出解。 代码 #include<bits/stdc++.h> #define ll long long #define pb push_back #define ft first #define sd second #define pii pair<int,int>...

ABCFL A. Clam and Fish 题意 一个游戏有n次，每次有四种类型： 0：没有鱼也没有蛤蜊 1：没有鱼有一个蛤蜊 2：有一个鱼没有蛤蜊 3：有一个鱼和一个蛤蜊 游戏每次可以执行下面4中操作中的一种： 1：用蛤蜊换一报鱼饵 2：直接抓一条鱼 3：用鱼饵钓一条鱼 4：不做任何操作 问n次之后最多可以拥有鱼。 题解 如果有鱼的话肯定要优先选择2直接抓鱼，这样不需要鱼饵。如果没有鱼的话有蛤蜊的话，就先换鱼饵，因为如果遇到没有鱼也没有蛤蜊的时候就可以钓鱼了。如果鱼饵多出来了，可以在最后的时候两个鱼饵变成一条鱼，相当于换一次鱼饵钓一次鱼。如果没有蛤蜊也没有鱼，如果有鱼饵的话就钓鱼，否则就跳...

题意：t组测试，每次测试按顺时针或逆时针给20个点，是一个手的形状，问是左手还是右手。 题解：这个题可以用凸包解，板子求出凸包的所有点记录下来，然后求一下长度为6的边（即大拇指）的下一条边是不是底下长度为9的边。是的话就是右手，否则为左手。但是，这个题他卡精度，两个边长相等判断的时候要用fabs(d1,d2)<1e-5，比1e-5更大一些也可以，小的话会wa，wa到哭。 #include<bits/stdc++.h> using namespace std; struct node { double x,y; }p[100],s[100]; double xx,y...

题意：给你n个点的坐标，问最多有多少个点可以在同一个圆上，（0,0）必须在这个圆上。 题解：三个点确定一个圆，所以暴力枚举两个点和（0,0）组成的圆，如果三个点不共线的话，用圆心公式求出圆心，然后用map记录以当前点为圆心的点圆的个数，边记录边判断有多少个圆圆心是同一个点，取最大值就好了。 #include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=2e6+10; struct Point{ &n...