A-小石的签到题 我们发现当 时先手（小石）总是赢。如何证明：一开始有 , 个数，假设先手必败，那么先手选 ，后手就进入了必败状态。所以假设错误，那么先手就不是必败，先手一定有一种方式能赢。 B-小雨的三角形 数据范围给的很小，可以 暴力构造三角形，预处理出每一行的总和，每个询问把 行的和加起来即可（若预处理出第 行的和，则可以做到 查询）。更快的做法？每一行的和其实是有规律的，分别为 ，除了第 行的和为 外，第 行的和为 ，那么第 行的和为 所以第 行的和就能用前缀和计算了，注意特判 的情况，这样就能够每次 查询。 C-小石的海岛之旅 我们按海岛的高度 从大到小排序。假设海岛在水位为 时被淹...

前言: 如果你不会线性基，希望能对你有点帮助。 作者较菜，请大佬轻表。 请大家多多支持，谢谢 <!--more-->  定义： 基：在线性代数中，基（也称为基底）是描述、刻画向量空间的基本工具。向量空间的基是它的一个特殊的子集，基的元素称为基向量。向量空间中任意一个元素，都可以唯一地表示成基向量的线性组合。如果基中元素个数有限，就称向量空间为有限维向量空间，将元素的个数称作向量空间的维数。 同样的，线性基是一种特殊的基，它通常会在异或运算中出现，它的意义是：通过原集合S的某一个最小子集S1使得S1内元素相互异或得到的值域与原集合S相互异或得到的值域相同。(摘自百度百科) 性质：  ...

三元环是什么？ 三元环是 求无向图的三元环有两种方法： 做法1： ①统计每个点的度数 ②入度$sqrt(m)$的分为第二类 ③对于第一类，暴力每个点，然后暴力这个点的任意两条边，再判断这两条边的另一个端点是否连接因为m条边最多每条边遍历一次，然后暴力的点的入度，所以复杂度约为  ④对于第二类，直接暴力任意三个点，判断这三个点是否构成环，因为这一类点的个数不会超过$sqrt(m)个，所以复杂度约为$$O(sqrt(m)^3)=O(msqrt(m))$ ⑤判断两个点是否连接可以用set，map和Hash都行,根据具体情况而行这种做法建的是双向边，常数很大  #include using names...

前言 希望大家看后都能学会，也请大家多多点赞，谢谢。 我真的很想获奖。 算法介绍 区间伸缩，是一种基于单调性的算法。 它往往可以用来解决查询满足条件的最大区间这类的问题。 大致结构是这样的: while(r<=n) { if(满足条件)l++; else r++; } 它经常是和单调队列一起使用的，也可以用其他数据结构维护。 时间复杂度是的。 我们先来看道例题让大家更深入的了解:逛画展  题意： 博物馆里有n幅画，每幅画都有一个作者，作者编号1-m。 问你最小的一个区间，使所有的画家都有画在这个区间里。 解题思路： 用两个变量和来枚举区间 如果到的区间不满足要求, 如果到的区间满足要求,...

A.幸运数字Ⅰ 这题很简单啊，能明显答案只有三种情况，-1或4或7。 想44,77,47......这些都没有4和7优（数量上和字典序上） 我们只要找出4和7的个数，判断一下是否为-1。如果4的个数>=7的个数就输出4，否则7 时间复杂度：O(n) #include<bits/stdc++.h> using namespace std; int a,b; char s[5005]; int main() { scanf("%s",s+1); int n=strlen(s+1); for(int i=1;i<=n;i++) if(s[i]=='4')a...

A.平面 这是道好题，考验的是我们的数学能力。 我们可以把X分成两条直线，这不就转化为了n条互不相交直线最多能把平面分成多少部分。 我们知道一个公式:n*(n+1)/2 时间复杂度O(1) #include<bits/stdc++.h> using namespace std; long long n; int main() { scanf("%lld",&n); n*=2; cout<<n*(n+1)/2+1; return 0; } B.烟花 好题，中等难度。 我一看题目就知道这是道期望dp题。 对于第1个问题，f[i]表示前i个烟花产生...

A.石子阵列 这不是和[HNOI2008]越狱 这题差不多吗（一个求合法方案，一个求不合法方案） 我们考虑第一个石头有m种选择，从第二个石头开始为了不重复，只有m-1种选择了 答案就是m * (m-1) ^ (n-1) 时间复杂度:O(log(n)) #include<bits/stdc++.h> using namespace std; #define int long long const int mod=1e9+7; int n,m; int kuai(int a,int b) { if(b==0)return 1ll; if(b==1)return a; int x=kua...

A.约数个数的和 我一眼看，还以为是用欧拉筛的方法线性求每个数的约数个数。 后来看了数据范围，好大1e8，又T又MLE怎么办。 换个方向，换个思路，发现考虑每个数作为因子对答案的贡献就可以轻易做出来了 时间复杂度O(n) #include<bits/stdc++.h> using namespace std; int n,ans; int main() { scanf("%d",&n); for(int i=1;i<=n;i++)ans=ans+n/i; cout<<ans; return 0; } B. 储物点的距离 思维难度不高，但...

A.骰⼦的游戏 水题，直接暴力枚举六个面再比较大小，完结散花。 时间复杂度O(6*6) #include<bits/stdc++.h> using namespace std; int T,x,y,a[7],b[7]; int main() { scanf("%d",&T); while(T--) { x=0;y=0; for(int i=1;i<=6;i++)scanf("%d",&a[i]); for(int i=1;i<=6;i++)scanf("%d",&b[i]); for(i...

A. Split      贪心，很明显分得要尽量均匀。     二分分成几段（即答案），可以$O(n)$判断，也可$O(1)$判。     时间复杂度O(log(n))      #include<bits/stdc++.h> using namespace std; #define int long long int s,m,l,r,ans,mid,a,b; bool pd(int x) {     a=s/x;b=s%x;     return(s*s-a*a*(x-b)-(a+1)*(a+1)*b)/2>=m; } signed main() {     scanf(...

A.反蝴蝶效应      水题，ans=max(ans,x+i-1);     时间复杂度O(n)      #include<bits/stdc++.h> using namespace std; int n,x,ans; int main() {     scanf("%d",&n);     for(int i=1;i<=n;i++)     {         scanf("%d",&x);         ans=max(ans,x+i-1);     }     cout<<ans;     re...

A.Contest  这题好（话说牛客的题目都很好） 我一眼看以为是到tarjan，后来发现可以转化为cdq分治求三维偏序问题 我们把三场比赛的名次设为a[i],b[i],c[i]. 答案可以转化为求多少对是a[i]>a[j],b[i]>b[j],c[i]>c[j] 可以发现这不就是cdq分治求三维偏序吗 cdq分治就是第一维排序，第二维归并排序，第三维树状数组 #include<bits/stdc++.h> using namespace std; #define int long long const int N=200005; int n,tot,ans,c...

A.矩阵 ​ hash好题啊，一眼看是二维hash，但我不会。怎么办？ ​ 我只好用洛谷子矩阵的思路，先求出每行的hash值， 再每列把行的hash值hash一下。 ​ 对于边长，我们采用二分，显然有单调性。矩阵越小越容易判匹配，越大越不容易匹配 ​ 时间复杂度n^2log(n)   #include<bits/stdc++.h> using namespace std; #define int long long const int N=1005; const int base=31; const int base2=127; int n,m,cnt,l,r,mid,hs3[N]...