今天上午比利给初三的小朋友们讲网络流
我也去听了 提出了各种正qi常pa的问题 然而比利每次都233过去
怎么会有这种不负责任的讲课人
不开森
今天上午献给了比利的讲课和昨天的LCT _(:зゝ∠)_
一开始很傻比地觉得是N2枚举首尾
然而发现只要全部OR起来就行了233
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
using namespace std;
inline int IN(){
int x=0,ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void Out(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) Out(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
int main(){
int x,x1=0,x2=0,n=IN();
Rep(i,1,n) x=IN(),x1|=x;
Rep(i,1,n) x=IN(),x2|=x;
Out(x1+x2);
}
记录一下每行每列最后一次被修改的颜色和时间
然后输出的时候把时间较晚的输出来就行
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
using namespace std;
inline int IN(){
int x=0,ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void Out(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) Out(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
int n,m,k;
struct Ope{
int col,tim;
}r[5005],c[5005];
int main(){
n=IN(),m=IN(),k=IN();
Rep(i,1,k){
int op=IN(),x=IN(),y=IN();
if (op==1) r[x]=(Ope){y,i};
else c[x]=(Ope){y,i};
}
Rep(i,1,n) Rep(j,1,m){
int col=r[i].col;
if (c[j].tim>r[i].tim) col=c[j].col;
Out(col);
if (j!=m) putchar(' ');else putchar('\n');
}
}
读入时维护一个单调栈，里面的操作的长度从大到小
读完以后把序列从后往前处理答案就行
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<set>
#include<cmath>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
using namespace std;
inline int IN(){
int x=0,ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void Out(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) Out(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
const int N=200005,M=200005;
int n,m,a[N],Ans[N],top;
struct Ope{
int t,r;
}s[M];
int main(){
n=IN(),m=IN();
Rep(i,1,n) a[i]=IN();
Rep(i,1,m){
int t=IN(),r=IN();
while (top&&r>=s[top].r) top--;
s[++top]=(Ope){t,r};
}
s[top+1]=(Ope){0,0};
Rep(i,s[1].r+1,n) Ans[i]=a[i];
sort(a+1,a+s[1].r+1);
int head=1,tail=s[1].r;
Rep(i,1,top){
if (s[i].t==1) Drp(j,s[i].r,s[i+1].r+1) Ans[j]=a[tail--];
else Drp(j,s[i].r,s[i+1].r+1) Ans[j]=a[head++];
}
Rep(i,1,n) Out(Ans[i]),putchar(' ');
}
这题可以用KMP做。
首先把读进来的A串和B串相邻且相同的块合并
然后观察可以发现A的某个子串等于B的条件是除边上两块外，
中间的几块完全吻合
并且那个子串的左右两块必须与B的左右两块字符相同，且长度不小于它
这样就可以用KMP了，在$[A_2,A_{Lena-1}]$中匹配$[B_2,B_{Lenb-1}]$，
如果匹配成功就判断一下加到答案中
还有就是如果$Lenb<=2$的话就特判一下好了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
using namespace std;
inline int IN(){
int x=0,ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void Out(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) Out(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
const int N=200005;
int la,lb,n,m;
struct str{
ll l;char c;
bool operator ==(const str&x)const{return l==x.l&&c==x.c;}
}a[N],b[N];
int next[N];
ll Ans=0;
void GetNext(){
int i=2,j=1;
next[2]=1;
while (i<lb){
if (j==1||b[i]==b[j]) i++,j++,next[i]=j;
else j=next[j];
}
}
int main(){
n=IN(),m=IN();
a[1].l=IN(),a[1].c=getchar();la=1;
Rep(i,2,n){
int l=IN(),c=getchar();
if (c==a[la].c) a[la].l+=l;
else a[++la]=(str){l,c};
}
b[1].l=IN(),b[1].c=getchar();lb=1;
Rep(i,2,m){
int l=IN(),c=getchar();
if (c==b[lb].c) b[lb].l+=l;
else b[++lb]=(str){l,c};
}
if (lb==1){
Rep(i,1,la) if (a[i].c==b[1].c&&a[i].l>=b[1].l) Ans+=a[i].l-b[1].l+1;
return Out(Ans),0;
}
if (lb==2){
Rep(i,1,la-1) if (a[i].c==b[1].c&&a[i].l>=b[1].l&&a[i+1].c==b[2].c&&a[i+1].l>=b[2].l) Ans++;
return Out(Ans),0;
}
GetNext();
int i=2,j=2;
while (i<la){
if (a[i]==b[j]) i++,j++;
else{
if (j>2) j=next[j];else i++;
}
if (j==lb){
if (a[i].c==b[lb].c&&a[i].l>=b[lb].l&&a[i-lb+1].c==b[1].c&&a[i-lb+1].l>=b[1].l) Ans++;
j=next[j];
}
}
Out(Ans);
}
Jan 25, 2024 02:52:07 PM
JNANABHUMI AP provides all latest educational updates and many more. The main concept or our aim behind this website has been the will to provide resources full information on each topic which can be accessed through Internet. To ensure that every readers get’s what important and worthy about the topic they search and link to hear from us. jnanabhumiap.in Jnanabhumi AP is a startup by passionate webmasters and bloggers who have passion to provide engaging content which is accurate, interesting and worthy to read. We are mope like a web community where you can find different information’s, resources, topics on day to day incidents or news. We provide you the finest of web content on each and every topics possible with help of editorial and content team.