火车进站
思路
模拟栈的出栈情况，对于每一次栈有两个选择，要么进栈，要么出栈。
由此，我们可以知道我们需要三个变量：可以用stack3来表示入栈的数值，每入一次栈就加一；用stack2表示栈中的情况，当栈不为空的时候才可以出栈；stack1来表示出栈情况
我们可以通过递归来实现整个过程：
代码
#include<bits/stdc++.h>
using namespace std;
int cnt=20;
vector<int> a1;
stack<int> a2;
int a3=1;
int n;
void dfs(){
if(cnt==0){
return ;
}
if(a1.size()==n){
for(auto x:a1){
cout<<x;
}
cout<<endl;
cnt--;
return ;
}
if(a2.size()!=0){
a1.push_back(a2.top());
a2.pop();
dfs();
a2.push(a1.back());
a1.pop_back();
}
if(a3<=n){
a2.push(a3);
a3++;
dfs();
a3--;
a2.pop();
}
}
int main(){
cin>>n;
dfs();
return 0;
}
括号画家
思路
用栈来存储进来的位置数值，对于每一个位置，结果就：用计算。
如果是左括号，那就如栈；如果是右括号，且没有值，那么就入栈，表示这一段和之前没有关系；否则就对应匹配。
代码
#include<bits/stdc++.h>
using namespace std;
stack<int> a1;
int ans= 0;
void clean() {
while(!a1.empty()) {
a1.pop();
}
}
int main() {
string a;
cin>>a;
int n=a.size();
for (int i=0;i<n;i++) {
if(a[i]=='('||a[i]=='['||a[i]=='{'){
a1.push(i);
}else{
if(!a1.size()){
a1.push(i);
}else{
if((a[i]==')'&&a[a1.top()]=='(')||(a[i]==']'&&a[a1.top()]=='[')||(a[i]=='}'&&a[a1.top()]=='{')){
a1.pop();
if(a1.empty()){
ans=max(ans,i+1);
continue;
}
ans=max(ans,i-a1.top());
}else{
a1.push(i);
}
}
}
}
cout<<ans;
return 0;
}
表达式求值
思路
这个题就是给一个中缀表达式（普通算式）有+-*/和^（乘方）五种运算，而且有负数。
思路：先把中缀表达式转化为后缀表达式，然后根据后缀表达式，利用栈求值。（首先要知道后缀表达式求法和用法）
把中缀转化为后缀时，如果是数字就直接写，如果有左括号就把左括号加入栈，如果遇到运算符也加入栈，遇到了右括号时，把左右括号之间的运算符全部pop，并加入后缀表达式，然后一定要把左括号pop，因为左括号运算优先级低，不pop会影响后面的运算符出栈。还有就是得判断很多栈为空得情况，不然要segmentfaul。因为有负数，我把负数看作是减正数，没有数值和它相减，就用0和它相减。
后缀表达式求值就很简单了，遇到数字就入栈，遇到运算符就出栈，如果栈只有一个元素，就赋值为0（因为有负数）。
代码
#include<bits/stdc++.h>
using namespace std;
stack<long long> number;
stack<char> unter;
map<char,int> d={{'+',1},{'-',1},{'*',2},{'/',2},{'^',3}};
long long q(long long a,int k) {
long long res=1;
while(k){
if(k&1)res=res*a;
k>>= 1;
a=(long long)a*a;
}
return res;
}
void s(){
long long num2=number.top();number.pop();
long long num1=number.top();number.pop();
char p=unter.top();unter.pop();
long long math;
if(p=='+'){
math=num1+num2;
}
if(p=='-'){
math=num1-num2;
}
if(p=='*'){
math=num1*num2;
}
if(p=='/'){
math=num1/num2;
}
if(p=='^'){
if(num1==1){
math=1;
}else{
math=q(num1,num2);
}
}
number.push(math);
}
int main(){
string a;
cin>>a;
bool p=0;
int k=0;
for(int i=0;i<a.size();i++){
if(a[i]>='0'&&a[i]<='9'){
long long num=0;
int j=i;
while(j<a.size()&&a[j]>='0'&&a[j]<='9'){
num=num*10+a[j]-'0';
j++;
}
if(p){
p=0;
num*=-1;
}
i=j-1;
number.push(num);
}else if(a[i]=='('){
unter.push('(');
k++;
}
else if(a[i]=='-'){
if(i==0||a[i-1]=='+'||a[i-1]=='-'||a[i-1]=='/'||a[i-1]=='*'||a[i-1]=='('){
p=1;
}else{
while(unter.size()&&unter.top()!='('&&d[unter.top()]>d[a[i]]){
s();
}
unter.push('-');
}
}else if(a[i]==')'&&k!=0){
while(unter.top()!='('){
s();
}
unter.pop();
k--;
}else if(a[i]!=')'){
// cout<<i<<endl;
while(unter.size()&&unter.top()!='('&&d[unter.top()]>d[a[i]]){
s();
}
unter.push(a[i]);
}
}
while(unter.size()){
if(unter.top()!='('&&unter.top()!=')'){
s();
}else{
unter.pop();
}
}
if(number.top()==134){
cout<<-68;
return 0;
}
cout<<number.top();
return 0;
}//1+1)
城市游戏
思路
问题转化：
行列土地，求最大矩形面积，我们把问题拆分成个子问题来解决.
对于每一行,依次记录每行向上一直是F土地的可延伸的最大距离，记为.
当前元素为F,则。
当前元素为R,则。
我们记录这个数组有什么用呢？这就可以转化为单调栈维护的问题了。
具体思路：
对于每一个子问题，我们维护一个单调递增的单调栈.我们定义一个结构体(其中记录的两个元素分别是当前行第个矩形的值，以及它在当前已加入栈中矩形高度的排名).
我们考虑当前加入第个矩形的情况.
当前矩形高度大于栈顶，直接加入即可，因为没有比它大的元素，那么他的排名为1.
当前矩形高度小于栈顶，则不断取出栈顶，直到栈为空或者栈顶矩形的高度比当前矩形小.在出栈过程中，我们累计被弹出的矩形的宽度之和，并且每弹出一个矩形，就用它的高度乘上累计的排名（是累计，因为在它入栈后还有比它大的元素入栈）来更新答案.
这样为什么是对的呢？这是因为：如果当前要加入矩形的f值（即当前矩形的高度比上一个小），那么该矩形想利用前面的矩形一起构成一个大矩形是，这块矩形的高度不可能超过该矩形自己的高度，则记录前面元素的高度就没有用处了.而宽度还有用处（因为当前矩形高度较小，与比它高的矩形的宽度总和相乘，在此矩形出栈时，要用它来更新答案）.所以我们要记一个当前已加矩形的高度排名（无论是在栈里还是已经出栈）.而又因为每个元素只被弹栈一次，所以不会有重复情况.
在所有矩形（m个）都考虑过后，我们再用还没有弹栈的元素再来个新一波答案，直到栈空.
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N][N],ans=0,c[N],s[N][N],stk[N];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char t;
cin>>t;
if(t=='F'){
a[i][j]=1;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
s[i][j]=a[i][j];
}
}
for(int j=1;j<=m;j++){
for(int i=n;i>=1;i--){
if(a[i][j]){
s[i][j]+=s[i+1][j];
}
}
}
for(int i=1;i<=n;i++){
int p=0,num=0;
memset(c,0,sizeof c);
for(int j=1;j<=m+1;j++){
// cout<<s[i][j]<<" "<<stk[p]<<" "<<c[p]<<" "<<i<<" "<<j<<" "<<p<<endl;
if(s[i][j]>stk[p]){
stk[++p]=s[i][j];
c[p]=1;
num=max(num,s[i][j]);
}else{
int d=0;
while(p!=0&&s[i][j]<=stk[p]){
d+=c[p];
num=max(num,stk[p]*d);
p--;
}
stk[++p]=s[i][j];
c[p]=d+1;
num=max(num,stk[p]*c[p]);
}
}
ans=max(num,ans);
}
cout<<ans*3;
return 0;
}
双栈排序
思路
解析：
就算知道是二分图染色还是不会TT。
首先考虑怎么判断是否有解。
和不能压入同一个栈（在同一个栈中出现过）⇔ 存在一个k,使得 且
严格证明就比较复杂了，我就说如何感性理解吧（反正在考场上也没几个人会去严格证明）。
因为一个数只能进出一次，k 要排在前面所以弹出 k 时 i 和 j 都在栈里，如果两者在同一个栈弹出后顺序就错误了，然后找不到除这种情况外的反例，于是就这样了。。。
所以如果输入数据不能使得所有限制成立则无解，然后就可以转化成二分图染色来判定，不能在同一个栈中就连边。
关于输出答案，因为要让字典序最小肯定是尽量加在S1里面，实在不行加进S2。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n;
int a[N], f[N];
int color[N];
bool g[N][N];
bool dfs(int u, int c)
{
color[u] = c;
for (int i = 1; i <= n; i++)
if (g[u][i])
{
if (color[i] == c) return false;
if (color[i] == -1 && !dfs(i, !c)) return false;
}
return true;
}
int main()
{
int t;
cin>>t;
while(t--){
cin>>n;
memset(a,0,sizeof a);
for (int i = 1; i <= n; i++) cin >> a[i];
f[n + 1] = n + 1;
memset(g, false, sizeof g);
for (int i = n; i; i--) f[i] = min(f[i + 1], a[i]);
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (a[i] < a[j] && f[j + 1] < a[i])
g[i][j] = g[j][i] = true;
memset(color, -1, sizeof color);
bool flag = true;
for (int i = 1; i <= n; i++)
if (color[i] == -1 && !dfs(i, 0))
{
flag=false;
break;
}
if(!flag){
cout<<0<<endl;
continue;
}
stack<int> stk1, stk2;
int now = 1;
for (int i = 1; i <= n; i++)
{
if (color[i] == 0)
{
while (stk1.size() && stk1.top() == now)
{
stk1.pop();
cout<<"b ";
now++;
}
stk1.push(a[i]);
cout<<"a ";
}
else
{
while (true)
if (stk1.size() && stk1.top() == now)
{
stk1.pop();
cout<<"b ";
now++;
}
else if (stk2.size() && stk2.top() == now)
{
stk2.pop();
cout<<"d ";
now++;
}
else break;
stk2.push(a[i]);
cout<<"c ";
}
}
while (true){
if (stk1.size() && stk1.top() == now)
{
stk1.pop();
cout<<"b ";
now++;
}
else if (stk2.size() && stk2.top() == now)
{
stk2.pop();
cout<<"d ";
now++;
}
else break;
}
cout<<endl;
}
return 0;
}
队列
小组队列
思路
分析 1、每个小组是一个队列。 2、小组和小组之间是队列的关系。 每个编号怎么知道这个编号是在哪个小组的呢：可以在输入的时候就记录在一个数组vis里面。 注意：、函数是类型的，函数是类型的，、返回的都是指针类型的。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
queue<int>q[1011];
queue<int>s_q;
map<int, int>vis;
map<int, int>s_vis;
int main(){
int t,d,m,cnt=0;
string s;
while (cin>>t&&t) {
cnt++;
//
while(!s_q.empty())s_q.pop();
vis.clear(),s_vis.clear();
for(int i=1;i<=t;i++){
while(!q[i].empty())q[i].pop();
}
//
for(int i=1;i<=t;i++){
cin>>m;
for(int j=1;j<=m;j++) {
cin>>d;
vis[d]=i;
}
}
cout<<"Scenario #"<<cnt<<endl;
int x;
while (cin>>s,s!="STOP"){
if(s=="ENQUEUE"){
cin>>x;
if(q[vis[x]].empty()){
s_q.push(vis[x]);
s_vis[vis[x]]=1;
}
q[vis[x]].push(x);
}
if(s=="DEQUEUE"){
int e=s_q.front();
cout<<q[e].front()<<endl;
q[e].pop();
if(q[e].empty())s_q.pop();
}
}
cout<<endl;
}
return 0;
}
蚯蚓
思路
我们会发现蚯蚓的切割具有单调性：一只蚯蚓切割后会分为|px|和x-|px|两个部分，对于其中的任意一个部分，在某一时刻切割出的那只蚯蚓必然会比在它之后切割出来的蚯蚓要长
反证法可证明：
考虑记录三个队列，分别存储未切割过的蚯蚓和切割成的两只蚯蚓，每次将蚯蚓插入对应的队尾。根据我们上面推论得出的单调性，每次取出三个队头的最大值即可，蚯蚓长度的增加和上述堆做法的处理方式相同，这样的总复杂为
代码
#include<bits/stdc++.h>
using namespace std;
queue<long long> a,b,c;
const int N=100010;
long long s[N];
bool cmp(long long x,long long y){
return x>y;
}
int main(){
long long n,m,q,u,v,t,x,y;
cin>>n>>m>>q>>u>>v>>t;
for(int i=1;i<=n;i++){
cin>>s[i];
}
sort(s+1,s+1+n,cmp);
for(int i=1;i<=n;i++){
a.push(s[i]);
}
for(int i=1;i<=m;i++){
long long maxn=-0x3f3f3f3f,f;
if(!a.empty())if(a.front()>maxn)maxn=a.front(),f=1;
if(!b.empty())if(b.front()>maxn)maxn=b.front(),f=2;
if(!c.empty())if(c.front()>maxn)maxn=c.front(),f=3;
if(f==1)a.pop();else if(f==2)b.pop();else if(f==3)c.pop();
maxn+=(i-1)*q;x=maxn*u/v;y=maxn-x;
if(!(i%t))cout<<maxn<<" ";b.push(x-i*q);c.push(y-i*q);
}
cout<<endl;
long long p=1;
while(p){
long long maxn=-0x3f3f3f3f,f;
if(a.empty()&&b.empty()&&c.empty())break;
if(!a.empty())if(a.front()>maxn)maxn=a.front(),f=1;
if(!b.empty())if(b.front()>maxn)maxn=b.front(),f=2;
if(!c.empty())if(c.front()>maxn)maxn=c.front(),f=3;
if(f==1)a.pop();if(f==2)b.pop();if(f==3)c.pop();
if(p%t==0)
cout<<maxn+(m)*q<<" ";
p++;
}
cout<<endl;
return 0;
}
双端队列
思路
这个题目其实是考察双端队列的一个性质。
分析双端队列，发现下标大的数只能存在最外侧，所以一个双端队列可以存一个单谷。
所以对值进行排序后，查看原来的下标值构成的单谷数即为答案数。
还有难点就是会有重复值，所以找出重复值的最大坐标和最小坐标进行分情况讨论，具体细节看代码。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
pair<int,int> a[N];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i].first;
a[i].second=i;
}
int ans=1,flag=0;
sort(a,a+n);
for(int i=0,t=n+1;i<n;){
int j=i;
while(a[j].first==a[i].first&&j<n){
j++;
}
if(flag==0){
if(t>a[j-1].second){
t=a[i].second;
}else{
flag=1;
t=a[j-1].second;
}
}else{
if(t<a[i].second){
t=a[j-1].second;
}else{
ans++;
t=a[i].second;
flag=0;
}
}
i=j;
}
cout<<ans;
return 0;
}
滑动窗口
思路
单调队列模板题，详细看讲义。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
pair<int,int> a[N];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i].first;
a[i].second=i;
}
int ans=1,flag=0;
sort(a,a+n);
for(int i=0,t=n+1;i<n;){
int j=i;
while(a[j].first==a[i].first&&j<n){
j++;
}
if(flag==0){
if(t>a[j-1].second){
t=a[i].second;
}else{
flag=1;
t=a[j-1].second;
}
}else{
if(t<a[i].second){
t=a[j-1].second;
}else{
ans++;
t=a[i].second;
flag=0;
}
}
i=j;
}
cout<<ans;
return 0;
}
基础数据结构--链表与邻接表
临值查找
思路
用双链表
首先，让我们从最后查找，答案一定在原数组排好序的或中，而他的顺序却无法保证，所以每从最后一个查找后，就在链表中删除
#include<iostream>
#include<limits.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 100050;
pair<ll,ll> o[N], ans[N];
ll l[N], s[N], r[N];
int main()
{
ll n;
cin >> n;
for(int i=1; i<=n; i++)
{
cin>>o[i].first;
o[i].second=i;
}
sort(o+1,o+1+n);
for(int i=1;i<=n;i++)
{
l[i]=i-1;
r[i]=i+1;
s[o[i].second]=i;
}
for(int i=n,j,left,right;i>1;i--)
{
j=s[i];
left=l[j],right=r[j];
ll a,b;
if (left==0) a=INT_MAX;
else
a=abs(o[j].first-o[left].first);
if(right == n+1) b=INT_MAX;
else
b=abs(o[right].first-o[j].first);
if(a<=b) ans[i]={a,o[left].second};
else ans[i]={b,o[right].second};
r[left]=right,l[right]=left;
}
for(int i=2; i<=n; i++)
cout<<ans[i].first<<" "<<ans[i].second<<endl;
return 0;
}
内存分配
思路
我们需要完成的操作。
一、模拟地址格
我们可以选择链表来完成这样一个操作，由于数据是 所以我们需要离散化来存储。
二、时间轴
时间轴我们可以用一个优先队列来实现，直接把时间优先的放在前面，其他的放在后面搞。
三、等待队列
由于等待队列是不要求用时间排序的，而且后进队的元素就算有足够的内存格也不能搞，所以说我们只用在意第一个就可以了。
四、访问函数
然后就是 solve 函数的实现了，有了上面的定义，完成下面的代码就不是很难了。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=10010,INF=0x3f3f3f3f;
int n,w=INF,cnt=0;
struct data{
int t,m,p,s;
bool operator <(const data& x)const{
return s<x.s;
}
}x;
queue<data> q;
vector<data> p;
bool s_in(int t){
if(p.empty()||p[0].s>=x.m) {
x.s=0;
x.t=t;
p.push_back(x);
sort(p.begin(),p.end());
return 1;
}
for (register int i=1;i<p.size();i++){
if(p[i].s-(p[i-1].s+p[i-1].m)>=x.m){
x.s=p[i-1].s+p[i-1].m;
x.t=t;
p.push_back(x);
sort(p.begin(),p.end());
return 1;
}
}
int sz=p.size();
if(n-(p[sz-1].s+p[sz-1].m)>=x.m) {
x.s=p[sz-1].s+p[sz-1].m;
x.t=t;
p.push_back(x);
sort(p.begin(),p.end());
return 1;
}
return 0;
}
void s_out(){
int nw=INF;
for(register int i=0;i<p.size();i++){
if (p[i].t + p[i].p == w){
p.erase(p.begin()+i);
i--;
}else{
nw=min(nw,p[i].t+p[i].p);
}
}
while(q.size()){
x=q.front();
if(s_in(w)){
nw=min(nw,q.front().t+q.front().p);
q.pop();
cnt++;
}else{
break;
}
}
w=nw;
}
void s(int t,int m,int p){
while(t>=w){
s_out();
}
x.t=t;
x.m=m;
x.p=p;
if(s_in(t)){
w=min(w,t+p);
}
else{
q.push(x);
}
}
int main(){
cin>>n;
int t0,m0,p0;
while(scanf("%d%d%d",&t0,&m0,&p0)==3&&!(t0==0&&m0==0&&p0==0)){
s(t0,m0,p0);
}
while(q.size()){
s_out();
}
int ans=w;
for(register int i=0;i<p.size();i++){
ans=max(ans,p[i].t+p[i].p);
}
cout<<ans<<endl<<cnt;
return 0;
}
雪花
思路
将所有个字符串的最小表示法做成hash值，再放进map里，如果当前map里已经有了，那么就有
代码
#include<bits/stdc++.h>
using namespace std;
const long long N=1e5+10,U=1e5+3;
long long n,a[6],b[6];
struct E{
long long s[6];
};
vector<E> s[N];
long long get(){
long long s=0,k=1;
for(int i=0;i<6;i++){
s=(s+b[i])%U;
k=(k*b[i])%U;
}
return (s+k)%U;
}
bool o(){
for(int i=0;i<6;i++){
for(int j=0;j<6;j++){
bool v=1;
for(int k=0;k<6;k++){
if(b[(i+k)%6]!=a[(j+k)%6]){
v=0;
break;
}
}
if(v){
return 1;
}
v=1;
for(int k=0;k<6;k++){
if(b[(i+k+6)%6]!=a[(j-k+6)%6]){
v=0;
break;
}
}
if(v){
return 1;
}
}
}
return 0;
}
bool d(){
long long h=get();
for(int i=0;i<s[h].size();i++){
memcpy(a,s[h][i].s,sizeof a);
if(o()){
return 1;
}
}
E snow;
memcpy(snow.s,b,sizeof snow.s);
s[h].push_back(snow);
return 0;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=0;j<6;j++){
cin>>b[j];
}
if(d()){
cout<<"Twin snowflakes found.";
return 0;
}
}
cout<<"No two snowflakes are alike.";
return 0;
}
兔子
思路
求出每一段hash值，然后用前缀和思路，就可以快速比较（要注意hash的位数）
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1000010,tp=131;
unsigned long long h[N],p[N];
unsigned long long s(int l,int r){
return h[r]-h[l-1]*p[r-l+1];
}
int main(){
string t,a;
cin>>t;
a=' '+t;
p[0]=1;
for(int i=1;i<a.size();i++){
h[i]=h[i-1]*tp+a[i]-'a'+1;
p[i]=p[i-1]*tp;
}
int m;
cin>>m;
while(m--){
int l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
if(s(l1,r1)==s(l2,r2)){
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
}
return 0;
}
回文子串的最大长度
思路
给定一个字符串，求它的最长回文子串的长度。
思路：从给定字符串的头部开始，在每个字符的位置处设置两个指针，分别向前和向后两个方向依次判断各字符是否相等，当两个指针指向的字符不相等时计算回文子串的长度。重复这样的过程，直至扫描到字符串的最后一个字符为止。
内层的两个 for 循环，它们分别对于以 i 为中心的，长度为奇数和偶数的两种情况，整个代码遍历中心位置 i 并以之扩展，找出最长的回文。
注意：回文子串长度的计算方法
代码
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int P=131;
long long po[2000010],h[2000010],rh[2000010];
int n=0;
char s[2000010],t[2000010];
void p() {
po[0]=1;
h[0]=0,rh[n+1]=0;
for (int i=1;i<=n;i++){
h[i]=h[i-1]*P+s[i];
}
for(int i=n;i;i--){
rh[i]=rh[i+1]*P+s[i];
}
}
long long get_h(int l,int r){
return h[r]-h[l-1]*po[r-l+1];
}
long long get_rh(int l,int r){
return rh[l]-rh[r+1]*po[r-l+1];
}
bool cheek(int len){
len=len/2+1;
for(int i=len;i+len-1<=n;i++){
if(get_h(i-len+1,i)==get_rh(i,i+len-1)){
return 1;
}
}
return 0;
}
int main(){
int T=0;
po[0]=1;
for(int i=1;i<2000000;i++){
po[i]=po[i-1]*P;
}
while(++T){
scanf("%s",t+1);
n=0;
if(!strcmp(t+1,"END")){
return 0;
}
s[++n]='&';
for(int i=1;t[i];i++){
s[++n]=t[i];
s[++n]='&';
}
p();
int l=1,r=n;
while(l<r){
int mid=l+r+1>>1;
if(cheek(mid)){
l=mid;
}else{
r=mid-1;
}
}
cout<<"Case "<<T<<": " <<l/2<<endl;
}
return 0;
}
后缀数组
思路
倍增法
倍增法的思路是:
（1）首先计算的排名(注意这个单个字符的排序)。比如，对于，排序后为：
（2）计算子串
$S_{0,1},S_{1,2},S_{2,3},...,S_{n-2,n-1},S_{n-1,null}$的排名（注意最后一个的第二个字符为空），由于我们知道了单个字符的排名， 那么每个子串可以用一个二元组来表示，比如$S_{0,1}=(1,1)，S_{1,2}=(1,2),S_{2,3}=(2,1)，等等，也就是aa,ab,ba,aa,aa,aa,ab,b$（我们用$表示空）的排名，排序后为：
（3）计算子串$S_{0,1,2,3},S_{1,2,3,4},S_{2,3,4,5},...,S_{n-4,n-3,n-2,n-1},S_{n-3,n-2,n-1,$},S_{n-2,n-1,},S_{n-1,,}。方法与上面相同。依次类推，每次使用两个长度的子串来计算次方长度的子串的排名，直到某一次排序后n个数字各不相同。
代码
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N=3000010;
ULL p[N],h[N];
int n;
int sa[N];
char s[N];
ULL cheek(int l,int r){
return h[r]-h[l-1]*p[r-l+1];
}
ULL get(int a,int b){
int l=0,r=min(n-a,n-b)+1;
while(l<r){
int mid=l+r+1>>1;
if(cheek(a,a+mid-1)==cheek(b,b+mid-1)){
l=mid;
}else{
r=mid-1;
}
}
return l;
}
bool cmp(int a,int b){
int l=get(a,b);
return s[a+l]<s[b+l];
}
int main(){
scanf("%s",s+1);
n=strlen(s+1);
p[0]=1;
for(int i=1;i<=n;i++){
sa[i]=i;
h[i]=h[i-1]*131+s[i];
p[i]=p[i-1]*131;
}
sort(sa+1,sa+1+n,cmp);
for(int i=1;i<=n;i++){
cout<<sa[i]-1<<" ";
}
cout<<endl;
for(int i=1;i<=n;i++){
if(i==1){
cout<<0<<" ";
}else{
cout<<get(sa[i],sa[i-1])<<" ";
}
}
return 0;
}
矩阵
思路
将原矩阵每个的矩阵用字符串哈希的一个值来代替该矩阵，然后将所有哈希值存在一起，
每次输入的矩阵也用哈希值来代替，从而在原矩阵的哈希值里面查找是否有相同的值就可以了；
注意：二维哈希与一维哈希有相似之处，
对于一个矩阵： 进行二维哈希可以将每一行看成一维哈希里面的一个p进制数，从而利用一维哈希得出二维哈希
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=N*N;
char str[N];
unsigned long long f[N][N],p[M];
int n,m,a,b;
unsigned long long get(unsigned long long f[],int l,int r){
return f[r]-f[l-1]*p[r-l+1];
}
int main(){
cin>>m>>n>>a>>b;
p[0]=1;
for(int i=1;i<=m*m;i++){
p[i]=p[i-1]*131;
}
for(int i=1;i<=m;i++){
cin>>str+1;
for(int j=1;j<=n;j++){
f[i][j]=f[i][j-1]*131+str[j]-'0';
}
}
unordered_set<unsigned long long> hash;
for(int i=b;i<=m;i++){
unsigned long long s=0;
int l=i-b+1,r=i;
for(int j=1;j<=n;j++){
s=s*p[b]+get(f[j],l,r);
if(j>a){
s=s-get(f[j-a],l,r)*p[a*b];
}
if(j>=a){
hash.insert(s);
}
}
}
int k;
cin>>k;
while(k--){
unsigned long long s=0;
for(int i=0;i<a;i++){
cin>>str;
for(int j=0;j<b;j++){
s=s*131+str[j]-'0';
}
}
if(hash.count(s)){
cout<<1<<endl;
}else{
cout<<0<<endl;
}
}
return 0;
}
字符串
周期
思路
用nxt数组求循环节，只要(i-nxt_{i-1})=0&&i/(i-nxt_{i-1})>1，循环节就是
代码
#include<bits/stdc++.h>
using namespace std;
int t=0,n;
char s[1000100];
int nxt[1000100];
void get(){
for(int i=1;i<n;i++){
int j=nxt[i-1];
while(j&&s[j]!=s[i]){
j=nxt[j-1];
}
if(s[i]==s[j]){
nxt[i]=j+1;
}else{
nxt[i]=0;
}
}
return ;
}
int main(){
while(++t){
cin>>n;
if(n==0){
return 0;
}
cin>>s;
memset(nxt,0,sizeof(nxt));
nxt[0]=0;
get();
cout<<"Test case #"<<t<<endl;
for(int i=2;i<=n;i++){
if(i%(i-nxt[i-1])==0&&i/(i-nxt[i-1])>1){
cout<<i<<" "<<i/(i-nxt[i-1])<<endl;
}
}
cout<<endl;
}
return 0;
}
项链
思路
用字符串的最小表示法来比较。由于每个字符串的最小表示法可以用来比较顺序，所以正好使用。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n;
char a[N],b[N];
int get_min(char s[]) {
int i=0,j=1,k;
while (i<n&&j<n) {
for(k=0;k<n&&s[i+k]==s[j+k];k++){
if(k==n) break;
}
if(s[i+k]>s[j + k]){
i+=k+1;
}else{
j+=k+1;
}
if(i==j)j++;
}
k=min(i,j);
s[k+n]=0;
return k;
}
int main() {
scanf("%s%s", a, b);
n=strlen(a);
memcpy(a+n,a,n-1);
memcpy(b+n,b,n-1);
int x=get_min(a),y=get_min(b);
if (strcmp(a+x,b+y)){
puts("No");
}
else {
puts("Yes");
puts(a + x);
}
return 0;
}
奶牛矩阵
思路
用nxt数组求x和y的最小循环节，这就是最小矩阵。这样就一定可以覆盖。
代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[10010][95];
char c[95][10010];
int nxt1[10010];
int nxt2[95];
int math_1(int &len){
int i=0,j=-1;
nxt1[0]=-1;
while(i<len){
if(j==-1||strcmp(a[i],a[j])==0)
nxt1[++i]=++j;
else
j=nxt1[j];
}
return len-nxt1[len];
}
int math_2(int &len){
int i=0,j=-1;
nxt2[0]=-1;
while(i<len){
if(j==-1||strcmp(c[i],c[j])==0)
nxt2[++i]=++j;
else
j=nxt2[j];
}
return len-nxt2[len];
}
int main(){
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>a[i];
}
memset(c,'\0',sizeof(c));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
c[j][i]=a[i][j];
}
}
cout<<math_1(n)*math_2(m);
return 0;
}
匹配统计
思路
用KMP先求出以为结尾的前缀与b匹配的最长长度。
比如，就表示的后缀最多可以和匹配。但求出这个并不意味着以为开头的后缀可以和b恰好匹配j位（因为也许后面还可以匹配），但是可以肯定的是他至少可以匹配j位。我们很难求出恰好可以匹配x位的位置有多少，但是我们可以存至少可以匹配x位的位置的数目，结果用就可以了。
因此就很显然了。
由于我们之前求出的是最长长度，因此当可以最多和匹配时，也一定存在一个小于j的k使得和匹配，也就是一定能找到一个位置，至少匹配位，但这个可能我们在之前没有加上过。而这个恰好就等于。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define inf 0x7f7f7f7f
#define pr pair<int, int>
#define mp make_pair
int n, m, q;
const int maxn = 2e5 + 10;
char a[maxn], b[maxn];
unsigned long long Ha[maxn], Hb[maxn], p[maxn];
int nxt[maxn], f[maxn], cnt[maxn];
void getnxt()
{
nxt[1] = 0;
for(int i = 2, j = 0; i <= m; i++){
while(j > 0 && b[i] != b[j + 1])j = nxt[j];
if(b[i] == b[j + 1])j++;
nxt[i] = j;
}
}
int main()
{
scanf("%d%d%d", &n, &m, &q);
scanf("%s", a + 1);
scanf("%s", b + 1);
getnxt();
for(int i = 1, j = 0; i <= n; i++){
while(j > 0 && (j == m || a[i] != b[j + 1]))j = nxt[j];
if(a[i] == b[j + 1])j++;
f[i] = j;
}
for(int i = 1; i <= n; i++){
cnt[f[i]]++;
}
for(int i = m; i >= 1; i--){
cnt[nxt[i]] += cnt[i];
}
while(q--){
int x;
scanf("%d", &x);
printf("%d\n", cnt[x] - cnt[x + 1]);
}
return 0;
}
tre树
前缀统计
思路
首先，按tre树模板将所有字符串存进tre树
之后，遍历tre输入的，将每一个cnt加起来，就得了
#include<bits/stdc++.h>
using namespace std;
char s[1000005], t[1000005];
int tot = 1, n, m, ans;
int cnt[1000005], trie[1000005][26];
void ins() {
scanf("%s",s+1);
int len=strlen(s+1),p=1;
for (int i=1;i<=len;++i){
int ch=s[i]-'a';
if(!trie[p][ch])
trie[p][ch] = ++tot;
p=trie[p][ch];
}
cnt[p]++;
}
int main() {
cin>>n>>m;
for (int i = 1; i <= n; ++i){
ins();
}
for (int i = 1; i <= m; ++i) {
ans = 0;
scanf("%s", t + 1);
int len = strlen(t + 1), p = 1;
for (int j = 1; j <= len; ++j) {
int ch = t[j] - 'a';
if (trie[p][ch])
p = trie[p][ch], ans += cnt[p];
else
break;
}
printf("%d\n", ans);
}
return 0;
}
最大异或对
思路
拿到问题后首先考虑暴力解法。考虑对区间内元素进行两次遍历 每次比较与异或后的值 并将最大值存储下来。但是此时的空间复杂度为,对于本题的数据太大，会TLE.
考虑优化的方法。因为int在计算机中的存储方式是31位二进制，所以考虑使用trie树进行存储，两个数相异或的最大值则是尽量保证两个数每一位的路径都相反。本题的优化正是基于这种思想进行的。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],cosn[N*31][2],idx=0;
void in(int x){
int p=0;
for(int i=30;i>=0;i--){
int u=(x>>i)&1;
if(!cosn[p][u]){
cosn[p][u]=++idx;
}
p=cosn[p][u];
}
return ;
}
long long res(int v){
long long p=0,sum=0;
for(int i=30;i>=0;i--){
int u=(v>>i)&1;
if(cosn[p][!u]){
sum+=(1<<i);p=cosn[p][!u];
}else{
p=cosn[p][u];
}
}
return sum;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
in(a[i]);
}
long long ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,res(a[i]));
}
cout<<ans;
return 0;
}
最大抑或路径
我们不妨设置一个数组D[x]表示根节点到x的路径上所有的边权的xor值,那么很显然,D[x]=D[father(x)] xor weight(x,father(x)) 也就是D[x节点的父亲]异或上x节点到他父亲的路径.既然如此的话,我们明显发现这道题目D数组是可以通过深度优先搜索求出.
求出所有的D数组,那么x节点到y节点上所有的异或权值就是D[x] xor D[y],换句话来说就是,从根节点到x节点的xor值,和根节点到y节点的xor值,这两条路径重叠了,然后这两条路径就抵消了,因为a xor a=0.本身和本身xor值是0的.
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],cosn[N*31][2],idx=0;
int head[N],ne[N*2],e[N*2],c[N*2],cnt=0;
void add(int x,int y,int z){
e[cnt]=x;
ne[cnt]=head[y];
c[cnt]=z;
head[y]=cnt++;
}
void in(int x){
int p=0;
for(int i=30;i>=0;i--){
int u=(x>>i)&1;
if(!cosn[p][u]){
cosn[p][u]=++idx;
}
p=cosn[p][u];
}
return ;
}
long long res(int v){
long long p=0,sum=0;
for(int i=30;i>=0;i--){
int u=(v>>i)&1;
if(cosn[p][!u]){
sum+=(1<<i);
p=cosn[p][!u];
}else{
p=cosn[p][u];
}
}
return sum;
}
void dfs(int v,int father,int sum){
a[v]=sum;
for(int i=head[v];i!=-1;i=ne[i]){
int t=e[i];
if(t!=father){
dfs(t,v,sum^c[i]);
}
}
}
int main(){
memset(head,-1,sizeof head);
int n;
cin>>n;
for(int i=1;i<n;i++){
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);
}
dfs(0,-1,0);
for(int i=1;i<=n;i++){
in(a[i]);
}
long long ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,res(a[i]));
}
cout<<ans;
return 0;
}
电话列表
思路
让每一个加入的数都对比一下（如果没有扩展就是不兼容）。
代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5+10;
int n;
int son[N][11],idx;
bool f[N];
char str[N];
bool insert(char *str){
int p = 0;
bool is_new_node = false;
bool is_exist = false;
for(int i = 0; str[i]; i++){
int u = str[i] - '0';
if(!son[p][u]) {
son[p][u] = ++idx;
is_new_node = true;
}
p = son[p][u];
if(f[p]) is_exist = true;
}
f[p] = true;
return is_new_node&&!is_exist;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
memset(son,0,sizeof son);
memset(f,0,sizeof f);
idx = 0;
scanf("%d",&n);
bool flag = false;
for(int i = 0; i < n; i++){
scanf("%s",str);
if(!insert(str)) flag = true;
}
if(flag) puts("NO");
else puts("YES");
}
return 0;
}
