学生出勤记录II 可以用字符串表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符： 'A'：Absent，缺勤 'L'：Late，迟到 'P'：Present，到场 如果学生能够 同时 满足下面两个条件，则可以获得出勤奖励： 按 总出勤 计，学生缺勤（'A'）严格 少于两天。 学生 不会 存在 连续 3 天或 连续 3 天以上的迟到（'L'）记录。 给你一个整数 n ，表示出勤记录的长度（次数）。请你返回记录长度为 n 时，可能获得出勤奖励的记录情况 数量 。答案可能很大，所以返回对 取余 的结果。 输入样例： 2 1 10101 ...

根据每个数的二进制当成字符串，建字典树，每次查询是，转成二进制的每一位，根据异或的性质，要尽可能的与当前的为不同，异或后为 1 ； 代码： #include<bits/stdc++.h> using namespace std; const int N=100010,M=31*N; int son[M][2],a[N],idx; void insert(int x){ int p=0; for(int i=30;i>=0;i--){ int u=(x>>i)&1; if(!son[p][u]) son[p...

最高的牛 有 N 头牛站成一行，被编队为 1、2、3…N，每头牛的身高都为整数。 当且仅当两头牛中间的牛身高都比它们矮时，两头牛方可看到对方。 现在，我们只知道其中最高的牛是第 P 头，它的身高是 H ，剩余牛的身高未知。 但是，我们还知道这群牛之中存在着 M 对关系，每对关系都指明了某两头牛 A 和 B 可以相互看见。 求每头牛的身高的最大可能值是多少。 注意： 此题中给出的关系对可能存在重复 思路 题目要保证每头牛尽可能的高，同时又要满足题目给的m对关系，让他们相互之间能够看得见，两头牛要相互看得见，那么两头牛之间的其他牛的高度就必须小于两头牛，不能相等。既要尽可能的高，又要小于，那么...

增减序列 题意： 给定一个长度为 n 的数列 a1,a2,…,an，每次可以选择一个区间 [l,r] ，使下标在这个区间内的数都加一或者都减一。 求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。 数据范围： 思路： 我们都知道，在一段区间加上一个数，减一个数可以用差分来做，假设差分数组 ; 在a的区间加上一个数 d ,就是​;其他位置保持不变。 题目最后要让所有的数最后都相等，那么也就是差分数组全部都等于0；那么我们只需要尽可能的使差分数组整数减少，负数增加。 所以我们就可以转成统计正有多少，负数有多少，正数-1，负数+1，那么多出...

引入：用数组模拟树形结构，可以解决一些区间更新，求和的问题。比线段树更简单一些的数据结构，树状数组能够解决的问题，线段树（还没学）都可以解决。 原理啥的，我也讲不明白，看大佬博客 构建树状数组 单点更新，区间查询 int n,a[1000010],c[1000010]; int lowbit(int x){ return x&-x;//返回二进制最后一位1 } void updata(int i,int k){//在i的位置上加上k for(;i<=n;i+=lowbit(i)) c[i]+=k; } int getsum(int i){//求a[1]-a...

A 给你一个序列是a1a3a5...a6a4a2 a_{1}a_{3}a_{5}...a_{6}a_{4}a_{2}a1​a3​a5​...a6​a4​a2​;你要输出a1a2a3a4a5a6...a_{1}a_{2}a_{3}a_{4}a_{5}a_{6}...a1​a2​a3​a4​a5​a6​... 代码： #include <bits/stdc++.h> using namespace std; #define bug(x) cerr<<#x<<" : "<<x<<endl; const int N=2e...

引入：ST算法（Sparse Table），以求最大值为例，设表示这个区间内的最大值，那么在询问到区间的最大值时答案就是其中是满足(即长度)的最大的即。 具体关于的推导，看这个文章，Pecco 动态规划预处理 for (int i = 1; i <= 21; ++i) for (int j = 1; j + (1 << i) - 1 <= n; ++j) { Min[j][i] = min(Min[j][i - 1], Min[j + (1 << (i - 1))][i - 1]); ...

A 题意：给n个整数 . 找到在所有对的最大值。 思路： 区间的最大值，最小值，很容易发现每个值他的左边，或者右边的相乘才是答案。 代码： #include <bits/stdc++.h> using namespace std; #define bug(x) cerr<<#x<<" : "<<x<<endl; const int N=2e6+10; const int mod=1e9+7; typedef long long ll; ll a[N]; int main(){ int T; ...

A 题意：有一个n*m个牢房的监狱，（r,c）处有一个逃生通道，每一个人一秒可以上下左右移动一格，问最短多少秒所有人可以到逃生通道。 思路：地图四个角一定有一个离（r,c）最远的，取时间最长的那个就是答案。 代码： #include <bits/stdc++.h> using namespace std; #define bug(x) cerr<<#x<<" : "<<x<<endl; #define x first #define y second const int N=2e4+10; const int m...

F 博弈，A和B轮流操作，不能操作者输。双方都想对方输，所以都会做出最优选择。 1.删除图G中的一条边 2.删除不成环的连通分量 给定n个点，m条边，没有自环、重边。 连通分量：无向图的极大联通子图； 观察左边这个图，如果A一来就删除整个连通分量，A直接赢了，如果按一条边一条边，一个点一个删最后结果还是一样的，所以删除连通分量的效果其实和删除点、边效果是一样的，所以只需要考虑删除边的情况。所以我们只需要考虑点和边的个数一共有多少个就行了，奇数一定就是A赢，偶数B赢。 右边的图就是样例，无论你是删除这个连通分量，还是删除这条边，最后结果是一样的。 总结：操作1会使边数减1，操作2会使边减少...

送外卖 输入样例： 7 5 -3 6 5 -5 -1 6 -6 1 4 -2 0 -2 0输出样例： abbbb代码： #include<bits/stdc++.h> using namespace std; #define x first #define y second #define endl '\n' #define bug(x) cerr<<#x<<" : "<<x<<endl; typedef long long ll; const int N=1000010; char ans[N]; int fl...

E 题目意思：n之前有多少对是满足的。 打表找规律，可以发现一定是一组答案，令,式子就变成了,倍，可以证得。 原式子 移项 把看成常数的话，那么两个解由韦达定理就有： ,即;这个就是递推关系式如果是第一组答案的话，那么下一组答案就为; 第一组答案，由递推式，下面依次是：,,, 枚举x，直到答案超过了1e18,停止。只保留更大的那个答案，然后，二分查询。 代码： #include<bits/stdc++.h> using namespace std; #define bug(x) cerr<<#x<<" : "<<x&lt...

#A 思路： 很容易想到，小猫在墙角，如果你的x,y轴只要有任意一个墙没有桩，小猫都会跑出来，当小猫不会跑出来的时候，答案最小肯定是离原点最近的两个坐标轴上的点，求距离。 代码： #include<iostream> #include<cstdio> #include<cmath> using namespace std; const double INF=1e9+9; int main() { double nx=INF,ny=INF,x,y; int n,i; scanf("%d",&n); for(i=1;i&...

栈和排序 给你一个1~n的排列和一个栈，入栈顺序给定你要在不打乱入栈顺序的情况下，对数组进行从大到小排序当无法完全排序时，请输出字典序最大的出栈序列 输入样例： 5 2 1 5 3 4输出样例： 5 4 3 1 2思路 如果要字典序最大，那么我们肯定要尽可能的按n~1的顺序输出，但是入栈，出栈顺序不可能是随意的，看样例，我们开始找到最大的那个数，出栈，出栈之后栈顶的元素依然比后面的所有元素还要大时，应该继续出栈，如果小于则入栈。再来看一组数据 10 1 2 3 4 5 6 8 9 10 7这组数据我们可以发现，10出栈之后9,8也要继续出栈，直到栈顶的元素比后面所有的还要小时继续入栈。大于等于...