脚本宝典收集整理的这篇文章主要介绍了模拟题大集合(2)，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
2021-09-27 21:01:49 星期一
exx的题，24遍还不让复制黏贴...（%ycxjulao）
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorIThm>
#include<assert.h>
namespace EMT{
tyPEdef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf PRintf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("c.in","r",stdin);freopen("c.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(ll x){pf("%lld ",x);}inline void pn(){pf("n");}
const int N=2005;
int a[5],b[N],rt[N],n;ll ans;
struct seg{
int sum[N*40],tot,ls[N*40],rs[N*40];
inline void insert(int x,int &y,int l,int r,int v){
y=++tot;ls[y]=ls[x],rs[y]=rs[x];
sum[y]=sum[x]+1;
if(l==r)return;
int mid=(l+r)>>1;
if(v<=mid)insert(ls[x],ls[y],l,mid,v);
else insert(rs[x],rs[y],mid+1,r,v);
}
inline int ask(int x,int y,int l,int r,int ql,int qr){
if(ql>qr)return 0;
if(!(sum[y]-sum[x]))return 0;
if(l>=ql&&r<=qr)return sum[y]-sum[x];
int mid=(l+r)>>1;
if(qr<=mid)return ask(ls[x],ls[y],l,mid,ql,qr);
if(ql>;mid)return ask(rs[x],rs[y],mid+1,r,ql,qr);
return ask(ls[x],ls[y],l,mid,ql,mid)+ask(rs[x],rs[y],mid+1,r,mid+1,qr);
}
inline void clear(){
F(i,1,tot)sum[i]=ls[i]=rs[i]=0;
F(i,1,n)rt[i]=0;
tot=0;
}
}segm;
inline void solve1(){
F(i,2,n-2)F(j,i+1,n-1)if(b[j]>b[i]){
int v1=segm.ask(rt[0],rt[i-1],1,n,1,b[i]-1),v2=segm.ask(rt[j],rt[n],1,n,b[j]+1,n);
ans+=1ll*v1*v2;
}pi(ans);
}
inline void solve2(){
F(i,2,n-2)F(j,i+1,n-1)if(b[j]-b[i]>1){
int v1=segm.ask(rt[0],rt[i-1],1,n,1,b[i]-1),v2=segm.ask(rt[j],rt[n],1,n,b[i]+1,b[j]-1);
ans+=1ll*v1*v2;
}pi(ans);
}
inline void solve3(){
F(i,2,n-2)F(j,i+1,n-1)if(b[i]>b[j]){
int v1=segm.ask(rt[0],rt[i-1],1,n,1,b[j]-1),v2=segm.ask(rt[j],rt[n],1,n,b[i]+1,n);
ans+=1ll*v1*v2;
}pi(ans);
}
inline void solve4(){
F(i,2,n-2)F(j,i+2,n)if(b[i]>b[j]){
int v1=segm.ask(rt[0],rt[i-1],1,n,1,b[j]-1),v2=segm.ask(rt[i],rt[j-1],1,n,b[i]+1,n);
ans+=1ll*v1*v2;
}pi(ans);
}
inline void solve5(){
F(i,2,n-2)F(j,i+1,n)if(b[i]-b[j]>1){
int v1=segm.ask(rt[0],rt[i-1],1,n,1,b[j]-1),v2=segm.ask(rt[j],rt[n],1,n,b[j]+1,b[i]-1);
ans+=1ll*v1*v2;
}pi(ans);
}
inline void solve6(){
F(i,2,n-2)F(j,i+2,n)if(b[i]-b[j]>1){
int v1=segm.ask(rt[0],rt[i-1],1,n,1,b[j]-1),v2=segm.ask(rt[i],rt[j-1],1,n,b[j]+1,b[i]-1);
ans+=1ll*v1*v2;
}pi(ans);
}
inline void solve7(){
F(i,2,n-2)F(j,i+1,n-1)if(b[j]-b[i]>1){
int v1=segm.ask(rt[0],rt[i-1],1,n,b[i]+1,b[j]-1),v2=segm.ask(rt[j],rt[n],1,n,b[j]+1,n);
ans+=1ll*v1*v2;
}pi(ans);
}
inline void solve8(){
F(i,2,n-2)F(j,i+2,n)if(b[j]-b[i]>1){
int v1=segm.ask(rt[0],rt[i-1],1,n,b[i]+1,b[j]-1),v2=segm.ask(rt[i],rt[j-1],1,n,b[j]+1,n);
ans+=1ll*v1*v2;
}pi(ans);
}
inline void solve9(){
F(i,2,n-2)F(j,i+1,n-1)if(b[i]-b[j]>1){
int v1=segm.ask(rt[0],rt[i-1],1,n,b[j]+1,b[i]-1),v2=segm.ask(rt[j],rt[n],1,n,b[i]+1,n);
ans+=1ll*v1*v2;
}pi(ans);
}
inline void solve10(){
F(i,2,n-2)F(j,i+2,n)if(b[i]-b[j]>1){
int v1=segm.ask(rt[0],rt[i-1],1,n,b[j]+1,b[i]-1),v2=segm.ask(rt[i],rt[j-1],1,n,b[i]+1,n);
ans+=1ll*v1*v2;
}pi(ans);
}
inline void solve11(){
F(i,4,n){
int sum=0,key=1;
while(key<i){
if(b[key]>b[i])ans+=sum;
else{
sum-=segm.ask(rt[0],rt[key-1],1,n,b[key]+1,b[i]-1);
sum+=segm.ask(rt[key],rt[i-1],1,n,1,b[key]-1);
}key++;
}
}pi(ans);
}
inline void solve12(){
F(i,1,n-3)F(j,i+2,n-1)if(b[i]<b[j]){
int v1=segm.ask(rt[i],rt[j-1],1,n,b[j]+1,n),v2=segm.ask(rt[j],rt[n],1,n,1,b[i]-1);
ans+=1ll*v1*v2;
}pi(ans);
}
inline void solve13(){
F(i,1,n-3)F(j,i+2,n-1)if(b[i]>b[j]){
int v1=segm.ask(rt[i],rt[j-1],1,n,1,b[j]-1),v2=segm.ask(rt[j],rt[n],1,n,b[i]+1,n);
ans+=1ll*v1*v2;
}pi(ans);
}
inline void solve14(){
std::reverse(b+1,b+n+1);
segm.clear();
F(i,1,n)segm.insert(rt[i-1],rt[i],1,n,b[i]);
solve11();
}
inline void solve15(){
F(i,1,n-3)F(j,i+2,n-1)if(b[i]-b[j]>1){
int v1=segm.ask(rt[i],rt[j-1],1,n,b[j]+1,b[i]-1),v2=segm.ask(rt[j],rt[n],1,n,b[i]+1,n);
ans+=1ll*v1*v2;
}pi(ans);
}
inline void solve16(){
F(i,2,n-2)F(j,i+1,n-1)if(b[j]-b[i]>1){
int v1=segm.ask(rt[0],rt[i-1],1,n,b[i]+1,b[j]-1),v2=segm.ask(rt[j],rt[n],1,n,1,b[i]-1);
ans+=1ll*v1*v2;
}pi(ans);
}
inline void solve17(){
F(i,1,n-3)F(j,i+2,n-1)if(b[i]-b[j]>1){
int v1=segm.ask(rt[i],rt[j-1],1,n,b[i]+1,n),v2=segm.ask(rt[j],rt[n],1,n,b[j]+1,b[i]-1);
ans+=1ll*v1*v2;
}pi(ans);
}
inline void solve18(){
F(i,1,n-3)F(j,i+2,n-1)if(b[i]>b[j]){
int v1=segm.ask(rt[i],rt[j-1],1,n,b[i]+1,n),v2=segm.ask(rt[j],rt[n],1,n,1,b[j]-1);
ans+=1ll*v1*v2;
}pi(ans);
}
inline void solve19(){
F(i,1,n-3)F(j,i+2,n-1)if(b[i]-b[j]>1){
int v1=segm.ask(rt[i],rt[j-1],1,n,1,b[j]-1),v2=segm.ask(rt[j],rt[n],1,n,b[j]+1,b[i]-1);
ans+=1ll*v1*v2;
}pi(ans);
}
inline void solve20(){
F(i,2,n-2)F(j,i+1,n-1)if(b[j]-b[i]>1){
int v1=segm.ask(rt[0],rt[i-1],1,n,b[j]+1,n),v2=segm.ask(rt[j],rt[n],1,n,b[i]+1,b[j]-1);
ans+=1ll*v1*v2;
}pi(ans);
}
inline void solve21(){
F(i,2,n-2)F(j,i+2,n)if(b[j]>b[i]){
int v1=segm.ask(rt[0],rt[i-1],1,n,b[j]+1,n),v2=segm.ask(rt[i],rt[j-1],1,n,1,b[i]-1);
ans+=1ll*v1*v2;
}pi(ans);
}
inline void solve22(){
F(i,2,n-2)F(j,i+1,n-1)if(b[j]>b[i]){
int v1=segm.ask(rt[0],rt[i-1],1,n,b[j]+1,n),v2=segm.ask(rt[j],rt[n],1,n,1,b[i]-1);
ans+=1ll*v1*v2;
}pi(ans);
}
inline void solve23(){
F(i,2,n-2)F(j,i+1,n-1)if(b[i]-b[j]>1){
int v1=segm.ask(rt[0],rt[i-1],1,n,b[i]+1,n),v2=segm.ask(rt[j],rt[n],1,n,b[j]+1,b[i]-1);
ans+=1ll*v1*v2;
}pi(ans);
}
inline void solve24(){
F(i,2,n-2)F(j,i+1,n-1)if(b[i]>b[j]){
int v1=segm.ask(rt[0],rt[i-1],1,n,b[i]+1,n),v2=segm.ask(rt[j],rt[n],1,n,1,b[j]-1);
ans+=1ll*v1*v2;
}pi(ans);
}
inline short main(){
file();
n=read();
F(i,1,4)a[i]=read();
F(i,1,n)b[i]=read(),segm.insert(rt[i-1],rt[i],1,n,b[i]);
if(a[1]==1&&a[2]==2&&a[3]==3&&a[4]==4)solve1();
if(a[1]==1&&a[2]==2&&a[3]==4&&a[4]==3)solve2();
if(a[1]==1&&a[2]==3&&a[3]==2&&a[4]==4)solve3();
if(a[1]==1&&a[2]==3&&a[3]==4&&a[4]==2)solve4();
if(a[1]==1&&a[2]==4&&a[3]==2&&a[4]==3)solve5();
if(a[1]==1&&a[2]==4&&a[3]==3&&a[4]==2)solve6();
if(a[1]==2&&a[2]==1&&a[3]==3&&a[4]==4)solve7();
if(a[1]==2&&a[2]==1&&a[3]==4&&a[4]==3)solve8();
if(a[1]==2&&a[2]==3&&a[3]==1&&a[4]==4)solve9();
if(a[1]==2&&a[2]==3&&a[3]==4&&a[4]==1)solve10();
if(a[1]==2&&a[2]==4&&a[3]==1&&a[4]==3)solve11();
if(a[1]==2&&a[2]==4&&a[3]==3&&a[4]==1)solve12();
if(a[1]==3&&a[2]==1&&a[3]==2&&a[4]==4)solve13();
if(a[1]==3&&a[2]==1&&a[3]==4&&a[4]==2)solve14();
if(a[1]==3&&a[2]==2&&a[3]==1&&a[4]==4)solve15();
if(a[1]==3&&a[2]==2&&a[3]==4&&a[4]==1)solve16();
if(a[1]==3&&a[2]==4&&a[3]==1&&a[4]==2)solve17();
if(a[1]==3&&a[2]==4&&a[3]==2&&a[4]==1)solve18();
if(a[1]==4&&a[2]==1&&a[3]==2&&a[4]==3)solve19();
if(a[1]==4&&a[2]==1&&a[3]==3&&a[4]==2)solve20();
if(a[1]==4&&a[2]==2&&a[3]==1&&a[4]==3)solve21();
if(a[1]==4&&a[2]==2&&a[3]==3&&a[4]==1)solve22();
if(a[1]==4&&a[2]==3&&a[3]==1&&a[4]==2)solve23();
if(a[1]==4&&a[2]==3&&a[3]==2&&a[4]==1)solve24();
return 0;
}
}
signed main(){return EMT::main();}
发现如果有大于等于2个奇环那么所有返祖边都不合法，否则一定合法，判一下哪些边被所有奇环所包括即可。
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("a.in","r",stdin);freopen("a.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("n");}
const int N=1e5+10,inf=1e9;
int co=1,head[N],sum[N];
struct node{int From,next,to,w;}e[N<<2];
inline void add(int next,int to){e[++co]=(node){next,head[next],to,0};head[next]=co;}
int n,m,deep[N],tot;bool vis[N];ll odd[N];
inline void DFs1(int k){
vis[k]=1;
for(register int i=head[k],j;i;i=e[i].next)if(!vis[j=e[i].to]){
e[i].w=e[i^1].w=1;
deep[j]=deep[k]+1;vis[j]=1;
dfs1(j);
}
}
inline void dfs2(int k,int fa){
for(register int i=head[k],j;i;i=e[i].next)if(e[i].w){
if(e[i].to==fa)continue;
j=e[i].to;dfs2(j,k);
}else{
j=e[i].to;
if(deep[j]>deep[k])continue;
if((deep[k]-deep[j])&1){
odd[k]-=inf;
odd[j]+=inf;
}else odd[k]++,odd[j]--,tot++;
}
}int ans;
inline void dfs3(int k,int fa){
for(register int i=head[k],j;i;i=e[i].next)if(e[i].w){
j=e[i].to;
if(deep[j]<deep[k])continue;
dfs3(j,k);odd[k]+=odd[j];
}sum[k]+=odd[k];if(sum[k]==tot&&k!=1)ans++;
}
inline short main(){
file();
n=read(),m=read();
F(i,1,m){
int x=read(),y=read();
add(x,y),add(y,x);
}
dfs1(1);
dfs2(1,0);
dfs3(1,0);
pi(tot==1?ans+1:ans);
return 0;
}
}
signed main(){return EMT::main();}
模拟题，就是求中位数有点麻烦，所以建两棵权值线段树分别代表现役和预备役即可。
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("d.in","r",stdin);freopen("d.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("n");}
const int N=1e5+10;int rt[5],n,a[N];
struct seg{
int tot,siz[N*40],ls[N*40],rs[N*40],maxval[N*40];//1预备役 2现役
inline void change(int &p,int l,int r,int x,int v){
if(!p)p=++tot;
siz[p]+=v;
if(l==r){if(siz[p])maxval[p]=l;else maxval[p]=0;return;}int mid=(l+r)>>1;
if(x<=mid)change(ls[p],l,mid,x,v);
else change(rs[p],mid+1,r,x,v);
maxval[p]=max(maxval[ls[p]],maxval[rs[p]]);
}
inline int kth(int p,int l,int r,int x){
if(!p)return 0;
if(l==r)return l;
int mid=(l+r)>>1;
if(x>siz[ls[p]])return kth(rs[p],mid+1,r,x-siz[ls[p]]);
else return kth(ls[p],l,mid,x);
}
inline int findst(int p,int l,int r,int x,int now){
if(l==r)return siz[p]?now:now+1;
int mid=(l+r)>>1;
if(x>mid)return findst(rs[p],mid+1,r,x,now+siz[ls[p]]);
else return findst(ls[p],l,mid,x,now);
}
inline int finded(int p,int l,int r,int x,int now){
if(l==r)return siz[p]?now+siz[p]-1:now;
int mid=(l+r)>>1;
if(x>mid)return finded(rs[p],mid+1,r,x,now+siz[ls[p]]);
else return finded(ls[p],l,mid,x,now);
}
inline int getmax(int p,int l,int r,int ql,int qr){
if(!p)return 0;
if(l>=ql&&r<=qr)return maxval[p];
int mid=(l+r)>>1;
if(qr<=mid)return getmax(ls[p],l,mid,ql,qr);
if(ql>mid)return getmax(rs[p],mid+1,r,ql,qr);
return max(getmax(ls[p],l,mid,ql,mid),getmax(rs[p],mid+1,r,mid+1,qr));
}
}segm;
int mid;
inline void move(int x){
pi(x);
segm.change(rt[2],1,1e9,x,1);
segm.change(rt[1],1,1e9,x,-1);
}
inline void solve1(){
F(i,1,n)segm.change(rt[1],1,1e9,a[i],1);
int x=segm.kth(1,1,1e9,1);mid=x;
move(x);
while(segm.siz[rt[1]]>1){
mid=segm.kth(rt[2],1,1e9,segm.siz[rt[2]]/2+1);
int k=segm.kth(rt[1],1,1e9,segm.finded(rt[1],1,1e9,mid,0)+1);
if(mid+1>k-1||!segm.getmax(rt[2],1,1e9,mid+1,k-1)){
int R=2*k-mid;
if(!segm.getmax(rt[2],1,1e9,mid+1,R))move(segm.getmax(rt[1],1,1e9,mid+1,R));
else move(segm.maxval[rt[1]]);
}else move(segm.maxval[rt[1]]);
db M=(db)(segm.kth(rt[2],1,1e9,segm.siz[rt[2]]/2)+segm.kth(rt[2],1,1e9,segm.siz[rt[2]]/2+1))/2.0;
bool fl=0;
if(M-floor(M)>=0.4&&M-floor(M)<=0.6)fl=1;//fl表示.5
int L;
if(fl){
mid=ceil(M);int kth=segm.findst(1,1,1e9,mid,0);
L=segm.kth(rt[1],1,1e9,kth);
if(L<M)L=segm.kth(rt[1],1,1e9,kth+1);
}else{
mid=M;
int kth=segm.findst(1,1,1e9,mid,0);
L=segm.kth(rt[1],1,1e9,kth);
if(L<M)L=segm.kth(rt[1],1,1e9,kth+1);
}if(fl)mid--;
if(mid+1>L-1||!segm.getmax(rt[2],1,1e9,mid+1,L-1))move(L);
else move(segm.maxval[rt[1]]);
}if(segm.siz[rt[1]])move(segm.maxval[rt[1]]);
}
int last=-1,CF=0;
inline void solve2(){
F(i,1,n)segm.change(rt[1],1,1e9,a[i],1);
move(cf);move(cf);
while(segm.siz[rt[1]]>1){
int x=segm.getmax(rt[1],1,1e9,1,cf);
if(!x)break;
move(segm.maxval[rt[1]]);
x=segm.getmax(rt[1],1,1e9,1,cf);
move(x);
}
if(!segm.siz[rt[1]])return;
move(segm.maxval[rt[1]]);
while(segm.siz[rt[1]]>1){
mid=segm.kth(rt[2],1,1e9,segm.siz[rt[2]]/2+1);
int k=segm.kth(rt[1],1,1e9,segm.finded(rt[1],1,1e9,mid,0)+1);
if(mid+1>k-1||!segm.getmax(rt[2],1,1e9,mid+1,k-1)){
int R=2*k-mid;
if(!segm.getmax(rt[2],1,1e9,mid+1,R))move(segm.getmax(rt[1],1,1e9,mid+1,R));
else move(segm.maxval[rt[1]]);
}else move(segm.maxval[rt[1]]);
db M=(db)(segm.kth(rt[2],1,1e9,segm.siz[rt[2]]/2)+segm.kth(rt[2],1,1e9,segm.siz[rt[2]]/2+1))/2.0;
bool fl=0;
if(M-floor(M)>=0.4&&M-floor(M)<=0.6)fl=1;//fl表示.5
int L;
if(fl){
mid=ceil(M);int kth=segm.findst(1,1,1e9,mid,0);
L=segm.kth(rt[1],1,1e9,kth);
if(L<M)L=segm.kth(rt[1],1,1e9,kth+1);
}else{
mid=M;
int kth=segm.findst(1,1,1e9,mid,0);
L=segm.kth(rt[1],1,1e9,kth);
if(L<M)L=segm.kth(rt[1],1,1e9,kth+1);
}if(fl)mid--;
if(mid+1>L-1||!segm.getmax(rt[2],1,1e9,mid+1,L-1))move(L);
else move(segm.maxval[rt[1]]);
}if(segm.siz[rt[1]])move(segm.maxval[rt[1]]);
}
inline short main(){
file();
n=read();
F(i,1,n)a[i]=read();
std::sort(a+1,a+n+1);
if(n&1){
D(i,n,1){
if(last==a[i]&&i<=n/2+1){
cf=a[i];
break;
}last=a[i];
}
}else{
D(i,n,1){
if(last==a[i]&&i<=n/2){
cf=a[i];
break;
}last=a[i];
}
}
if(!cf)solve1();
else solve2();
return 0;
}
}
signed main(){return EMT::main();}
发现d=0的路径将整张图连成了几个团，于是用并查集判一下将答案乘起来即可。
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define int long long
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("c.in","r",stdin);freopen("c.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("n");}
const int N=410,mod=998244353;
int d[N][N],n,k,jc[N],inv[N],f[N],g[N],fa[N],cnt[N][N],dis[N][N],ans=1,siz[N];bool vis[N][N],vi[N];
inline int ksm(int a,int b){int ans=1;while(b){if(b&1)ans=1ll*a*ans%mod;a=1ll*a*a%mod;b>>=1;}return ans;}
inline int C(int n,int m){return 1ll*jc[n]*inv[m]%mod*inv[n-m]%mod;}
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline short main(){
file();
n=read(),k=read();jc[0]=inv[0]=inv[1]=1;
F(i,1,n)F(j,1,n)d[i][j]=read();
F(i,1,n)F(j,1,n){if(d[i][j]>k||d[i][j]!=d[j][i])puts("0"),exit(0);
F(k,1,n)if(d[i][j]>d[i][k]+d[k][j])puts("0"),exit(0);}
F(i,1,n)jc[i]=1ll*jc[i-1]*i%mod;
inv[n]=ksm(jc[n],mod-2);
D(i,n-1,2)inv[i]=1ll*(i+1)*inv[i+1]%mod;
g[1]=f[1]=1;
F(i,2,n)g[i]=ksm(k+1,C(i,2));
F(i,2,n){f[i]=g[i];F(j,1,i-1)f[i]-=1ll*f[j]*g[i-j]%mod*C(i-1,j-1)%mod*ksm(k,j*(i-j))%mod,f[i]+=f[i]<0?mod:0;}
F(i,1,n)fa[i]=i,siz[i]=1;
F(i,1,n)F(j,i+1,n){
if(!d[i][j]){
int fx=find(i),fy=find(j);
if(fx!=fy)fa[fy]=fx,siz[fx]+=siz[fy];
}
}
F(i,1,n){
int fx=find(i);
if(vi[fx])continue;vi[fx]=1;
ans=1ll*ans*f[siz[fx]]%mod;
}
F(i,1,n)F(j,i+1,n){int fx=find(i),fy=find(j);cnt[fx][fy]++;cnt[fy][fx]++;dis[fx][fy]=dis[fy][fx]=d[i][j];}
F(i,1,n)F(j,i+1,n){
int fx=find(i),fy=find(j);
if(vis[fx][fy]||fx==fy)continue;
vis[fx][fy]=vis[fy][fx]=1;bool fl=0;
F(k,1,n)if(k!=fx&&k!=fy&&dis[fx][fy]==dis[fx][k]+dis[k][fy]){fl=1;break;}
if(fl)ans=1ll*ans*ksm(k-dis[fx][fy]+1,cnt[fx][fy])%mod;
else ans=1ll*ans*((ksm(k-dis[fx][fy]+1,cnt[fx][fy])-ksm(k-dis[fx][fy],cnt[fx][fy])+mod)%mod)%mod;
}pi(ans);
return 0;
}
}
signed main(){return EMT::main();}
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("b.in","r",stdin);freopen("b.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("n");}
int x[1100],y[1100],z[1100],count[1100],m,k,now=-1,cnt,n;
std::map<int,int>mp;
inline bool com(int i,int j){return i>j;}
inline short main(){
file();
m=read(),k=read();
F(i,1,m)count[i]=read(),n+=count[i];
F(i,1,m)x[i]=read();
F(i,1,m)y[i]=read();
F(i,1,m)z[i]=read();
int s=(1<<k)-1,dp;
F(i,1,m){
dp=x[i];
if(!cnt)now=dp,cnt=1;
else if(now==dp)cnt++;
else cnt--;
ll last=dp;
F(j,1,count[i]-1){
last=(last*y[i]+z[i])&s;
dp=last;
if(!cnt)now=dp,cnt=1;
else if(now==dp)cnt++;
else cnt--;
}
}
cnt=0;
F(i,1,m){
dp=x[i];
if(now==dp)cnt++;
ll last=dp;
F(j,1,count[i]-1){
last=(last*y[i]+z[i])&s;
dp=last;
if(now==dp)cnt++;
}
}
if(cnt<=(n+1)/2)pi(0);
else{
int rest=n-cnt;
n-=rest*2+1;
pi(n);
}
return 0;
}
}
signed main(){return EMT::main();}
发现如果序列中没有零一定有重复的前缀和，一减就行。
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("a.in","r",stdin);freopen("a.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("n");}
const int N=1e6+10;
int n,last[N],pre[N];
inline short main(){
file();
n=read();
F(i,1,n){
pre[i]=(read()%n+pre[i-1])%n;
if(last[pre[i]]){
pi(i-last[pre[i]]);
F(j,last[pre[i]]+1,i)pi(j);
return 0;
}last[pre[i]]=i;
}
return 0;
}
}
signed main(){return EMT::main();}
2021-09-25 20:52:27 星期六
对点进行斜率优化，斜率是f数组之差与pre数组之差的比值，为了不爆精度移到两边相乘即可。
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("d.in","r",stdin);freopen("d.out","w",stdout);}
inline ll max(ll a,ll b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(ll x){pf("%lld ",x);}inline void pn(){pf("n");}
const int N=5100;
ll pre[N],f[N][N];int n,p[N],q[N],hd,tl,rec1[N],co1,rec2[N],co2;
inline bool com(int i,int j){return pre[i]>pre[j];}
inline db lop(int k,int kk,int j){return (db)(f[j][k]-f[j][kk])/(db)(pre[k]-pre[kk]);}
inline bool lopp(int k,int kk,int kkk,int j){
if(pre[k]-pre[kk]<0){
if(pre[kkk]-pre[kk]<0){
return 1ll*(f[j][k]-f[j][kk])*(pre[kkk]-pre[kk])<=1ll*(f[j][kkk]-f[j][kk])*(pre[k]-pre[kk]);
}else return 1ll*(f[j][k]-f[j][kk])*(pre[kkk]-pre[kk])>=1ll*(f[j][kkk]-f[j][kk])*(pre[k]-pre[kk]);
}else{
if(pre[kkk]-pre[kk]<0){
return 1ll*(f[j][k]-f[j][kk])*(pre[kkk]-pre[kk])>=1ll*(f[j][kkk]-f[j][kk])*(pre[k]-pre[kk]);
}else return 1ll*(f[j][k]-f[j][kk])*(pre[kkk]-pre[kk])<=1ll*(f[j][kkk]-f[j][kk])*(pre[k]-pre[kk]);
}
}
inline short main(){
file();
n=read();
F(i,1,n)pre[i]=pre[i-1]+read();
F(i,2,n)F(j,1,i-1)f[i][j]=-1e18;
F(i,1,n)p[i]=i;
std::sort(p+0,p+n+1,com);
F(i,1,n-1){
// pf("Case %d:n",i);
co1=co2=0;hd=1;tl=0;
D(j,n,0)if(p[j]<i)rec1[++co1]=p[j];
F(j,0,n)if(p[j]>i)rec2[++co2]=p[j];
F(j,1,co1){
while(hd<tl&&/*lop(q[tl],q[tl-1],i)<=lop(rec1[j],q[tl-1],i)*/lopp(q[tl],q[tl-1],rec1[j],i))tl--;
q[++tl]=rec1[j];
}
// F(j,hd,tl)pi(j-hd+1),pi(q[j]),pi(f[i][q[j]]),pi(pre[q[j]]),pn();
// pf("nnchange:n");
F(j,1,co2){
while(hd<tl&&((pre[q[hd+1]]==pre[q[hd]]&&f[i][q[hd]]<=f[i][q[hd+1]])||lop(q[hd+1],q[hd],i)>=pre[rec2[j]]-pre[i]))hd++;
f[rec2[j]][i]=f[i][q[hd]]+1ll*(pre[i]-pre[q[hd]])*(pre[rec2[j]]-pre[i]);
// pi(rec2[j]);pi(i);pi(q[hd]);pi(f[rec2[j]][i]);pi(f[i][q[hd]]);pn();
}//pn();pn();
}ll ans=0;
F(i,0,n)ans=max(ans,f[n][i]);
pi(ans);
return 0;
}
}
signed main(){return EMT::main();}
考虑到一个3x3的矩形中上左、中右、下中的和与上中、中左、右下的相反数之和不变，所以若有任意一个3x3矩形和不为0则不合法否则合法，判完模拟即可。
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("c.in","r",stdin);freopen("c.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(ll x){pf("%lld ",x);}inline void pn(){pf("n");}
int n,m;ll a[1100][1100],ans[6100][3];
inline short main(){
file();
n=read(),m=read();
F(i,1,n)F(j,1,m)a[i][j]=read();
F(i,1,n-2)F(j,1,m-2)if(a[i][j]-a[i][j+1]-a[i+1][j]+a[i+1][j+2]+a[i+2][j+1]-a[i+2][j+2]!=0){pi(-1);return 0;}
if(n==2){
pi(m*2);pn();
F(i,1,m){
pi(2);pi(i);pi(-a[2][i]);pn();
a[1][i]-=a[2][i];
pi(3);pi(i-1);pi(-a[1][i]);pn();
a[2][i+1]-=a[1][i];
}
return 0;
}else{
int cnt=0;
D(i,m,2){
ans[++cnt][0]=2;ans[cnt][1]=i;ans[cnt][2]=-a[1][i];
a[2][i]-=a[1][i];
ans[++cnt][0]=3;ans[cnt][1]=i-2;ans[cnt][2]=-a[2][i];
a[1][i-1]-=a[2][i];
}
D(i,n,1)a[i][2]-=a[1][2];
ans[++cnt][0]=2;ans[cnt][1]=1;ans[cnt][2]=-a[1][1];
D(i,n,1)a[i][1]-=a[1][1];
F(i,2,n-1){
ans[++cnt][0]=3;ans[cnt][1]=1-i;ans[cnt][2]=-a[i][1];
a[i+1][2]-=a[i][1];
ans[++cnt][0]=1;ans[cnt][1]=i+1;ans[cnt][2]=-a[i+1][2];
a[i+1][1]-=a[i+1][2];
}
ans[++cnt][0]=3;ans[cnt][1]=1-n;ans[cnt][2]=-a[n][1];
pi(cnt);
F(i,1,cnt){F(j,0,2)pi(ans[i][j]);pn();}
}
return 0;
}
}
signed main(){return EMT::main();}
最优策略一定只有一段或两段，用权值线段树维护即可。
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("b.in","r",stdin);freopen("b.out","w",stdout);}
inline ll max(ll a,ll b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(db x){pf("%.3lf ",x);}inline void pn(){pf("n");}
const int N=1e5+10;
struct seg{
ll val[N<<2];
inline void change(int p,int l,int r,int x,ll v){
if(l==r){val[p]=max(val[p],v);return;}
int mid=(l+r)>>1;
if(x<=mid)change(p<<1,l,mid,x,v);
else change(p<<1|1,mid+1,r,x,v);
val[p]=max(val[p<<1],val[p<<1|1]);
}
inline ll ask(int p,int l,int r,int ql,int qr){
if(l>=ql&&r<=qr)return val[p];
int mid=(l+r)>>1;
if(qr<=mid)return ask(p<<1,l,mid,ql,qr);
if(ql>mid)return ask(p<<1|1,mid+1,r,ql,qr);
return max(ask(p<<1,l,mid,ql,mid),ask(p<<1|1,mid+1,r,mid+1,qr));
}
}segm[2];//0上升，1下降。
int n,a[N],s[N];
inline short main(){
file();
n=read();
F(i,1,n)s[i]=a[i]=read();
std::sort(s+1,s+n+1);
int len=std::unique(s+1,s+n+1)-s-1;
F(i,1,n)a[i]=std::lower_bound(s+1,s+len+1,a[i])-s;
F(i,1,n){
if(a[i]>1){
ll v1=segm[0].ask(1,1,len,1,a[i]-1);
segm[0].change(1,1,len,a[i],v1+s[a[i]]);
if(a[i]<len){
ll v2=segm[0].ask(1,1,len,a[i]+1,len),v3=segm[1].ask(1,1,len,a[i]+1,len);
if(max(v2,v3))segm[1].change(1,1,len,a[i],max(v2,v3)+s[a[i]]);
}
}else{
ll v1=segm[0].ask(1,1,len,a[i]+1,len),v2=segm[1].ask(1,1,len,a[i]+1,len);
if(max(v1,v2))segm[1].change(1,1,len,a[i],max(v2,v1)+s[a[i]]);
segm[0].change(1,1,len,a[i],s[a[i]]);
}
}
db v1=segm[0].val[1],v2=1.0*segm[1].val[1]/2.0;
pi(v1>v2?v1:v2);
return 0;
}
}
signed main(){return EMT::main();}
将边化为点，点化为边，两个出边和两个入边连边，求图中环的个数即可。
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
namespace emt{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("in.in","r",stdin);freopen("my.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("n");}
const int mod=998244353,N=1e5+10;
inline int ksm(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*a*ans%mod;
a=1ll*a*a%mod;b>>=1;
}return ans;
}
int head[N<<1],co,fa[N<<1],n;
struct node{int next,to;}e[N<<2];
inline void add(int next,int to){e[++co]=(node){head[next],to};head[next]=co;}
int cnt;bool vis[N<<1];
inline void dfs(int k){
vis[k]=1;
for(register int i=head[k];i;i=e[i].next)
if(!vis[e[i].to])dfs(e[i].to);
}
inline void solve(){
F(i,1,n)if(!vis[i]){cnt++;dfs(i);}
pi(ksm(2,cnt));
}
inline short main(){
solve();
return 0;
}
}
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("a.in","r",stdin);freopen("a.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("n");}
const int mod=998244353,N=1e5+10;
inline int ksm(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*a*ans%mod;
a=1ll*a*a%mod;b>>=1;
}return ans;
}int in[N][3],out[N][3],n;
struct node{int from,to,id;}e[N<<1];
inline short main(){
file();
n=read();
F(i,1,n<<1){
e[i].from=read(),e[i].to=read(),e[i].id=i;
in[e[i].to][++in[e[i].to][0]]=i;
out[e[i].from][++out[e[i].from][0]]=i;
}
F(i,1,n)emt::add(out[i][1],out[i][2]),emt::add(out[i][2],out[i][1]);
F(i,1,n)emt::add(in[i][1],in[i][2]),emt::add(in[i][2],in[i][1]);
emt::n=n*2;emt::main();
return 0;
}
}
signed main(){return EMT::main();}
2021-09-23 19:49:01 星期四
考虑到矩阵快速幂做m次转移，初状态是(f_m=1)答案就是(f_0)
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("sugar.in","r",stdin);freopen("sugar.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("n");}
const int N=1e7+10,mod=998244353;
int w[110][110][110],b[110][110],c[110],d[110];
int m,val[N<<1],A,B,P,last[N],jc[110],inv[110];ll n,tim[110];
inline void mul(int a[110],int b[110][110]){
memset(d,0,sizeof(d));
F(i,0,m)F(j,0,m)(d[i]+=1ll*a[j]*b[j][i]%mod)%=mod;
F(i,0,m)a[i]=d[i];
}
inline void muls(int a[110][110]){
memset(b,0,sizeof(b));
F(i,0,m)F(k,0,m)F(j,0,m)(b[i][j]+=1ll*a[i][k]*a[k][j]%mod)%=mod;
F(i,0,m)F(j,0,m)a[i][j]=b[i][j];
}
inline int ksm(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*a*ans%mod;
b>>=1;a=1ll*a*a%mod;
}return ans;
}
inline int C(int n,int m){
return 1ll*jc[n]*inv[m]%mod*inv[n-m]%mod;
}
inline void init(){
jc[0]=1;
F(i,1,m)jc[i]=1ll*jc[i-1]*i%mod;
inv[0]=inv[1]=1;inv[m]=ksm(jc[m],mod-2);
D(i,m-1,2)inv[i]=1ll*(i+1)*inv[i+1]%mod;
c[m]=1;
F(i,1,m){
F(j,0,m){
D(k,j,0){
if(j-k>i)break;
w[i][j][k]=C(j,j-k);
}
}
while(tim[i]){
if(tim[i]&1)mul(c,w[i]);
muls(w[i]);tim[i]>>=1;
}
}
pi(c[0]);
}
inline short main(){
file();
n=read(),m=read();
val[1]=read();last[val[1]]=1;A=read(),B=read(),P=read();
int st=1,ed=n,len;
F(i,2,n){
val[i]=(1ll*val[i-1]*A%P+B)%P+1;
if(last[val[i]]){st=i;break;}
last[val[i]]=i;
}
memset(last,0,sizeof(last));
last[val[st]]=st;
F(i,st+1,n){
val[i]=(1ll*val[i-1]*A%P+B)%P+1;
if(last[val[i]]){ed=i-1;break;}
last[val[i]]=i;
}len=ed-st+1;
F(i,1,st-1){
if(val[i]>m)tim[m]++;
else tim[val[i]]++;
}n-=st-1;
F(i,st,ed){
if(val[i]>m)tim[m]+=n/len;
else tim[val[i]]+=n/len;
}
n-=1ll*(n/len)*len;
F(i,st,st+n-1){
if(val[i]>m)tim[m]++;
else tim[val[i]]++;
}
init();
return 0;
}
}
signed main(){return EMT::main();}
等价于求(x^mequiv x(mod c_i))于是可以积性筛出(x^m)求解即可。
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("division.in","r",stdin);freopen("division.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("n");}
const int N=1e4+10;
int pw[N],c,m,prime[N],co;bool vis[N];
inline int ksm(int a,int b,int mod){
int ans=1;
while(b){
if(b&1)ans=1ll*a*ans%mod;
a=1ll*a*a%mod;b>>=1;
}return ans;
}
inline void init(int x){
memset(vis,0,sizeof(vis));
pw[1]=1;co=0;
F(i,2,x){
if(!vis[i])pw[i]=ksm(i,m,x),prime[++co]=i;
F(j,1,co){
if(prime[j]*i>=x)break;
vis[prime[j]*i]=1;
pw[prime[j]*i]=1ll*pw[i]*pw[prime[j]]%x;
if(i%prime[j]==0)break;
}
}
}
const int md=998244353;
inline short main(){
file();
read();
int T=read();
while(T--){
c=read(),m=read();int ans=1;
F(i,1,c){
int p=read();
init(p);int cnt=0;
F(j,1,p)if(pw[j]%p==j%p)cnt++;
ans=1ll*ans*cnt%md;
}pi(ans);pn();
}
return 0;
}
}
signed main(){return EMT::main();}
2021-09-22 19:49:53 星期三
拓扑求出一个点作为终点的最长路和作为起点的最长路，用堆维护即可。
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
const int inf=1e9;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("johnny.in","r",stdin);freopen("johnny.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("n");}
const int N=1e5+10,M=1e6+10;
struct que{
std::priority_queue<int>a,b;
inline void push(int x){a.push(x);}
inline void pop(int x){b.push(x);}
inline int top(){while(!b.empty()&&a.top()==b.top())a.pop(),b.pop();return a.empty()?inf:a.top();}
inline void init(){while(!a.empty())a.pop();while(!b.empty())b.pop();}
}q;
struct queue{
int QQ[N],hd,tl;
inline void push(int x){qq[++tl]=x;}
inline void pop(){hd++;}
inline int front(){return qq[hd];}
inline bool empty(){return hd>tl;}
inline void init(){hd=1,tl=0;}
}Q;
int co,head[N],Head[N];
struct node{
int next,to,w;
}e[M];int n,m,in[N],a[N],tim,dt[N],ds[N],ans,w;
inline void add(int next,int to,int *head){e[++co]=(node){head[next],to};head[next]=co;}
inline short main(){
file();
int T=read();
while(T--){
co=0;F(i,1,n)head[i]=Head[i]=ds[i]=dt[i]=in[i]=a[i]=tim=0;
q.init();
n=read(),m=read();w=n;
F(i,1,m){
int x=read(),y=read();
add(x,y,head);add(y,x,Head);in[y]++;
}Q.init();
F(i,1,n)if(!in[i])Q.push(i);
while(!Q.empty()){
int x=Q.front();Q.pop();a[++tim]=x;
for(register int i=head[x];i;i=e[i].next){
in[e[i].to]--;if(!in[e[i].to])Q.push(e[i].to);
}
}
F(i,1,n)for(register int o=head[a[i]];o;o=e[o].next)dt[e[o].to]=max(dt[e[o].to],dt[a[i]]+1);
D(i,n,1)for(register int o=Head[a[i]];o;o=e[o].next)ds[e[o].to]=max(ds[e[o].to],ds[a[i]]+1);
F(i,1,n)q.push(ds[i]);
ans=q.top();
F(j,1,n){
int x=a[j];q.pop(ds[x]);
for(register int i=Head[x];i;i=e[i].next)q.pop(dt[e[i].to]+ds[x]+1);
if(q.top()<ans)ans=q.top(),w=x;
else if(q.top()==ans&&x<w)w=x;
q.push(dt[x]);
for(register int i=head[x];i;i=e[i].next)q.push(ds[e[i].to]+dt[x]+1);
}
pi(w);pi(ans);pn();
}
return 0;
}
}
signed main(){return EMT::main();}
考虑进行网络流之后在残量网络中求强连通分量即可。
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("night.in","r",stdin);freopen("night.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("n");}
const int N=1e5+10,inf=1e9;
int co=1,head[N],Hd[N],dis[N];
struct node{int next,to,w,from;}e[N<<3];
inline void add(int next,int to,int w){e[++co]=(node){head[next],to,w,next};head[next]=co;}
int n,m,t,bel1[N],bel2[N],cnt,S,T,dfn[N],low[N],tim;
struct queue{
int hd,tl,q[N];
inline void push(int x){q[++tl]=x;}
inline void pop(){hd++;}
inline int front(){return q[hd];}
inline bool empty(){return hd>tl;}
inline void init(){hd=1,tl=0;}
}q;
struct stack{
int tp,s[N];
inline int top(){return s[tp];}
inline void pop(){tp--;}
inline void push(int x){s[++tp]=x;}
}s;
int Edge[N];
inline bool bfs(){
q.init();
F(i,1,cnt)head[i]=Hd[i];
F(i,1,cnt)dis[i]=inf;
dis[S]=0;q.push(S);
while(!q.empty()){
int x=q.front();q.pop();
for(register int i=head[x];i;i=e[i].next)if(e[i].w){
if(dis[e[i].to]>dis[x]+1){
dis[e[i].to]=dis[x]+1;
q.push(e[i].to);
}
}if(x==T)return 1;
}return 0;
}
inline int dfs(int x,int in){
if(x==T)return in;
int rest=in,go;
for(register int i=head[x],j;i;head[x]=i=e[i].next)if(e[i].w){
if(dis[e[i].to]==dis[x]+1){
go=dfs(e[i].to,min(rest,e[i].w));
if(go)e[i].w-=go,e[i^1].w+=go,rest-=go;
else dis[e[i].to]=0;
}if(!rest)break;
}return in-rest;
}
bool vis[N];int part,bel[N];
inline void tj(int k){
dfn[k]=low[k]=++tim;s.push(k);vis[k]=1;
for(register int i=head[k],j;i;i=e[i].next)if(e[i].w){
j=e[i].to;
if(!dfn[j]){
tj(j);
low[k]=min(low[k],low[j]);
}else if(vis[j])low[k]=min(low[k],dfn[j]);
}
if(low[k]==dfn[k]){
++part;
while(s.top()!=k){
int x=s.top();s.pop();
bel[x]=part;vis[x]=0;
}s.pop();vis[k]=0;bel[k]=part;
}
}
std::vector<int>vec;
inline short main(){
file();
n=read(),m=read(),t=read();
S=++cnt,T=++cnt;
F(i,1,n)bel1[i]=++cnt;
F(i,1,m)bel2[i]=++cnt;
F(i,1,n)add(S,bel1[i],1),add(bel1[i],S,0);
F(i,1,m)add(bel2[i],T,1),add(T,bel2[i],0);
F(i,1,t){
int x=bel1[read()],y=bel2[read()];
add(x,y,inf),add(y,x,0);
edge[i]=co;
}
int ans=0;
F(i,1,cnt)Hd[i]=head[i];
while(bfs())ans+=dfs(S,inf);
// pi(ans);
F(i,1,cnt)if(!dfn[i])tj(i);
F(i,1,t){
if(e[edge[i]^1].w){
int u=e[edge[i]].from,v=e[edge[i]].to;
if(bel[u]!=bel[v])vec.push_back(i);
}
}
pi(vec.size());pn();
if(vec.size())F(i,0,vec.size()-1)pi(vec[i]);
return 0;
}
}
signed main(){return EMT::main();}
用AC自动机进行dp设(f_{i,j,k,l})表示总长度为i，有j个R，到AC自动机的k点匹配情况为l的方案数。
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("square.in","r",stdin);freopen("square.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("n");}
const int N=120,mod=1e9+7;
int n,m,ans,f[N<<1][N][N<<1][4];std::queue<int>q;
struct abc{
int tot,son[N<<1][2],fail[N<<1],end[N<<1];
inline void insert(char *s,int id){
int len=strlen(s),now=0;
F(i,0,len-1){
int x=(s[i]=='R');
if(!son[now][x])son[now][x]=++tot;
now=son[now][x];
}end[now]|=id;
}
inline void getfail(){
if(son[0][0])q.push(son[0][0]);
if(son[0][1])q.push(son[0][1]);
while(!q.empty()){
int x=q.front();q.pop();
if(son[x][1])fail[son[x][1]]=son[fail[x]][1],q.push(son[x][1]);
else son[x][1]=son[fail[x]][1];
if(son[x][0])fail[son[x][0]]=son[fail[x]][0],q.push(son[x][0]);
else son[x][0]=son[fail[x]][0];
end[son[x][1]]|=end[son[fail[x]][1]];
end[son[x][0]]|=end[son[fail[x]][0]];
}
}
inline void getans(){
f[0][0][0][0]=1;
F(i,0,n+m)
F(j,0,i){
if(j>m||i-j>n)continue;
F(k,0,tot)
F(l,0,3)
(f[i+1][j+1][son[k][1]][l|end[son[k][1]]]+=f[i][j][k][l])%=mod,
(f[i+1][j][son[k][0]][l|end[son[k][0]]]+=f[i][j][k][l])%=mod;
}
ans=0;
F(i,0,tot)ans+=f[n+m][m][i][3],ans-=ans>=mod?mod:0;
pi(ans);pn();
}
inline void init(){
memset(f,0,sizeof(f));
memset(son,0,sizeof(son));
memset(fail,0,sizeof(fail));
memset(end,0,sizeof(end));
tot=0;
}
}AC;
char s[N];
inline short main(){
file();
int T=read();
while(T--){
AC.init();
m=read(),n=read();
scanf("%s",s);AC.insert(s,1);
scanf("%s",s);AC.insert(s,2);
AC.getfail();
AC.getans();
}
return 0;
}
}
signed main(){return EMT::main();}
注意到模数=(31times 37times 41times 43times 47)，预处理出这几个模数以内的贝尔数再用矩阵快速幂优化递推再用CRT合并即可。
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
namespace lit{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("bell.in","r",stdin);freopen("bell.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("n");}
const int N=3e3+10,mod=95041567;
int bell[N]={1,1,2,5,15,52,203},C[N][N];
inline int ksm(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*a*ans%mod;
b>>=1;a=1ll*a*a%mod;
}return ans;
}
inline short main(){
C[0][0]=C[1][0]=C[1][1]=1;
F(i,2,2300){
C[i][0]=C[i][i]=1;
F(j,1,i-1)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
F(n,6,2300)
F(k,0,n)bell[n+1]+=1ll*C[n][k]*bell[k]%mod,bell[n+1]-=bell[n+1]>=mod?mod:0;
return 0;
}
}
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("bell.in","r",stdin);freopen("bell.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("n");}
struct S1{
const int mod=31;
int C[100][100];
int bell[100]={1,1,2,5,15,52,203};
inline void init(){
C[0][0]=C[1][1]=C[1][0]=1;
F(i,2,mod*2){
C[i][0]=C[i][i]=1;
F(j,1,i-1)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
F(n,6,mod*2)
F(k,0,n)
bell[n+1]+=1ll*C[n][k]*bell[k]%mod,bell[n+1]-=bell[n+1]>=mod?mod:0;
}
int b[55][55],c[55][55],f[55],w[55];
inline void muls(int a[55][55]){
memset(c,0,sizeof(c));
F(i,1,mod)F(j,1,mod)F(k,1,mod)(c[i][j]+=1ll*a[i][k]*a[k][j]%mod)%=mod;
F(i,1,mod)F(j,1,mod)a[i][j]=c[i][j];
}
inline void mul(int a[55],int b[55][55]){
memset(w,0,sizeof(w));
F(i,1,mod)F(j,1,mod)(w[i]+=1ll*a[j]*b[j][i]%mod)%=mod;
F(i,1,mod)a[i]=w[i];
}
inline int reset(int n){
memset(b,0,sizeof(b));
b[1][1]=1;
F(i,2,mod)b[i-1][i]=b[i][i]=1;
b[mod][1]=1;b[mod][2]=1;
int ceng=n-(mod-1)*mod;ceng/=mod;
F(i,1,mod)f[i]=C[mod-1][i-1];
while(ceng){
if(ceng&1)mul(f,b);
muls(b);
ceng>>=1;
}int begin=n%mod;
int ans=0;
F(i,1,mod)(ans+=1ll*bell[begin+i-1]*f[i]%mod)%=mod;
return ans;
}
}s1;
struct S2{
const int mod=37;
int C[100][100];
int bell[100]={1,1,2,5,15,52,203};
inline void init(){
C[0][0]=C[1][1]=C[1][0]=1;
F(i,2,mod*2){
C[i][0]=C[i][i]=1;
F(j,1,i-1)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
F(n,6,mod*2)
F(k,0,n)
bell[n+1]+=1ll*C[n][k]*bell[k]%mod,bell[n+1]-=bell[n+1]>=mod?mod:0;
}
int b[55][55],c[55][55],f[55],w[55];
inline void muls(int a[55][55]){
memset(c,0,sizeof(c));
F(i,1,mod)F(j,1,mod)F(k,1,mod)(c[i][j]+=1ll*a[i][k]*a[k][j]%mod)%=mod;
F(i,1,mod)F(j,1,mod)a[i][j]=c[i][j];
}
inline void mul(int a[55],int b[55][55]){
memset(w,0,sizeof(w));
F(i,1,mod)F(j,1,mod)(w[i]+=1ll*a[j]*b[j][i]%mod)%=mod;
F(i,1,mod)a[i]=w[i];
}
inline int reset(int n){
memset(b,0,sizeof(b));
b[1][1]=1;
F(i,2,mod)b[i-1][i]=b[i][i]=1;
b[mod][1]=1;b[mod][2]=1;
int ceng=n-(mod-1)*mod;
F(i,1,mod)f[i]=C[mod-1][i-1];ceng/=mod;
while(ceng){
if(ceng&1)mul(f,b);
muls(b);
ceng>>=1;
}int begin=n%mod;
int ans=0;
F(i,1,mod)(ans+=1ll*bell[begin+i-1]*f[i]%mod)%=mod;
return ans;
}
}s2;
struct S3{
const int mod=41;
int C[100][100];
int bell[100]={1,1,2,5,15,52,203};
inline void init(){
C[0][0]=C[1][1]=C[1][0]=1;
F(i,2,mod*2){
C[i][0]=C[i][i]=1;
F(j,1,i-1)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
F(n,6,mod*2)
F(k,0,n)
bell[n+1]+=1ll*C[n][k]*bell[k]%mod,bell[n+1]-=bell[n+1]>=mod?mod:0;
}
int b[55][55],c[55][55],f[55],w[55];
inline void muls(int a[55][55]){
memset(c,0,sizeof(c));
F(i,1,mod)F(j,1,mod)F(k,1,mod)(c[i][j]+=1ll*a[i][k]*a[k][j]%mod)%=mod;
F(i,1,mod)F(j,1,mod)a[i][j]=c[i][j];
}
inline void mul(int a[55],int b[55][55]){
memset(w,0,sizeof(w));
F(i,1,mod)F(j,1,mod)(w[i]+=1ll*a[j]*b[j][i]%mod)%=mod;
F(i,1,mod)a[i]=w[i];
}
inline int reset(int n){
memset(b,0,sizeof(b));
b[1][1]=1;
F(i,2,mod)b[i-1][i]=b[i][i]=1;
b[mod][1]=1;b[mod][2]=1;
int ceng=n-(mod-1)*mod;ceng/=mod;
F(i,1,mod)f[i]=C[mod-1][i-1];
while(ceng){
if(ceng&1)mul(f,b);
muls(b);
ceng>>=1;
}int begin=n%mod;
int ans=0;
F(i,1,mod)(ans+=1ll*bell[begin+i-1]*f[i]%mod)%=mod;
return ans;
}
}s3;
struct S4{
const int mod=43;
int C[100][100];
int bell[100]={1,1,2,5,15,52,203};
inline void init(){
C[0][0]=C[1][1]=C[1][0]=1;
F(i,2,mod*2){
C[i][0]=C[i][i]=1;
F(j,1,i-1)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
F(n,6,mod*2)
F(k,0,n)
bell[n+1]+=1ll*C[n][k]*bell[k]%mod,bell[n+1]-=bell[n+1]>=mod?mod:0;
}
int b[55][55],c[55][55],f[55],w[55];
inline void muls(int a[55][55]){
memset(c,0,sizeof(c));
F(i,1,mod)F(j,1,mod)F(k,1,mod)(c[i][j]+=1ll*a[i][k]*a[k][j]%mod)%=mod;
F(i,1,mod)F(j,1,mod)a[i][j]=c[i][j];
}
inline void mul(int a[55],int b[55][55]){
memset(w,0,sizeof(w));
F(i,1,mod)F(j,1,mod)(w[i]+=1ll*a[j]*b[j][i]%mod)%=mod;
F(i,1,mod)a[i]=w[i];
}
inline int reset(int n){
memset(b,0,sizeof(b));
b[1][1]=1;
F(i,2,mod)b[i-1][i]=b[i][i]=1;
b[mod][1]=1;b[mod][2]=1;
int ceng=n-(mod-1)*mod;ceng/=mod;
F(i,1,mod)f[i]=C[mod-1][i-1];
while(ceng){
if(ceng&1)mul(f,b);
muls(b);
ceng>>=1;
}int begin=n%mod;
int ans=0;
F(i,1,mod)(ans+=1ll*bell[begin+i-1]*f[i]%mod)%=mod;
return ans;
}
}s4;
struct S5{
const int mod=47;
int C[110][100];
int bell[100]={1,1,2,5,15,52,203};
inline void init(){
C[0][0]=C[1][1]=C[1][0]=1;
F(i,2,mod*2){
C[i][0]=C[i][i]=1;
F(j,1,i-1)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
F(n,6,mod*2){
F(k,0,n)
bell[n+1]+=1ll*C[n][k]*bell[k]%mod,bell[n+1]-=bell[n+1]>=mod?mod:0;
}
}
int b[55][55],c[55][55],f[55],w[55];
inline void muls(int a[55][55]){
memset(c,0,sizeof(c));
F(i,1,mod)F(j,1,mod)F(k,1,mod)(c[i][j]+=1ll*a[i][k]*a[k][j]%mod)%=mod;
F(i,1,mod)F(j,1,mod)a[i][j]=c[i][j];
}
inline void mul(int a[55],int b[55][55]){
memset(w,0,sizeof(w));
F(i,1,mod)F(j,1,mod)(w[i]+=1ll*a[j]*b[j][i]%mod)%=mod;
F(i,1,mod)a[i]=w[i];
}
inline int reset(int n){
memset(b,0,sizeof(b));
b[1][1]=1;
F(i,2,mod)b[i-1][i]=b[i][i]=1;
b[mod][1]=1;b[mod][2]=1;
int ceng=n-(mod-1)*mod;ceng/=mod;
F(i,1,mod)f[i]=C[mod-1][i-1];
while(ceng){
if(ceng&1)mul(f,b);
muls(b);
ceng>>=1;
}int begin=n%mod;
int ans=0;
F(i,1,mod)(ans+=1ll*bell[begin+i-1]*f[i]%mod)%=mod;
return ans;
}
}s5;
inline void exgcd(int a,int b,int &x,int &y){
if(!b){x=1;y=0;return;}
exgcd(b,a%b,x,y);
int z=x;x=y;y=z-y*(a/b);
}
int c[10],a[10]={0,31,37,41,43,47},b[10],tot=95041567;ll ans;
inline int CRT(){
ans=0;
F(i,1,5){
c[i]=tot/a[i];
int x=0,y=0;exgcd(c[i],a[i],x,y);
ans+=1ll*c[i]*b[i]*(x<0?x+a[i]:x)%95041567,ans-=ans>=95041567?95041567:0;
}return ans%95041567;
}
inline short main(){
file();
s1.init();s2.init();s3.init();s4.init();s5.init();
int T=read();
lit::main();
while(T--){
int n=read();
if(n<=2300){pi(lit::bell[n]),pn();continue;}
b[1]=s1.reset(n),b[2]=s2.reset(n),b[3]=s3.reset(n),b[4]=s4.reset(n),b[5]=s5.reset(n);
pi(CRT());pn();
}
return 0;
}
}
signed main(){return EMT::main();}
由于不会李超树，考虑测试点分治。
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("b.in","r",stdin);freopen("b.out","w",stdout);}
inline ll max(ll a,ll b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(ll x){pf("%lld ",x);}inline void pn(){pf("n");}
int rt[3100];
struct zxs{
int val[3100*20],ls[3100*20],rs[3100*20],tot;
inline void insert(int x,int &y,int l,int r,int v){
y=++tot;ls[y]=ls[x],rs[y]=rs[x];
val[y]=val[x]+1;
if(l==r)return;
int mid=(l+r)>>1;
if(v<=mid)insert(ls[x],ls[y],l,mid,v);
else insert(rs[x],rs[y],mid+1,r,v);
}
inline int ask(int x,int y,int l,int r,int ql,int qr){
if(l>=ql&&r<=qr)return val[y]-val[x];
int mid=(l+r)>>1;
if(qr<=mid)return ask(ls[x],ls[y],l,mid,ql,qr);
else if(ql>mid)return ask(rs[x],rs[y],mid+1,r,ql,qr);
else return ask(ls[x],ls[y],l,mid,ql,mid)+ask(rs[x],rs[y],mid+1,r,mid+1,qr);
}
}segm;
const int N=2e5+10;
int stack[N],tp;
ll dp[N];
int n,a[N],s[N],lmax[N],rmax[N],hd,tl,spj=1;
inline void solve(){
F(i,1,n){
dp[i]=dp[i-1];
bool fl=0;
while(tp&&a[stack[tp]]>=a[i])tp--,fl=1;
if(!fl)stack[++tp]=i;
else a[stack[++tp]]=a[i];
D(j,tp,1)
dp[i]=max(dp[i],1ll*a[stack[j]]*(i-stack[j]+1));
pi(dp[i]);
}
}
struct dp{int plc,val;}q[N];
inline db lop(int k,int j){return (db)(1.0*a[k]*k-1.0*a[j]*j+a[j]-a[k])/(db)(a[k]-a[j]);}
inline short main(){
file();
n=read();
F(i,1,n)s[i]=a[i]=read(),spj&=(a[i]>=a[i-1]);
if(n<=3000){
std::sort(s+1,s+n+1);
int len=std::unique(s+1,s+n+1)-s-1;
F(i,1,n)a[i]=std::lower_bound(s+1,s+len+1,a[i])-s;
F(i,1,n){
segm.insert(rt[i-1],rt[i],1,len,a[i]);
int l=1,r=i,an;
while(l<=r){
int mid=(l+r)>>1;
if(segm.ask(rt[mid-1],rt[i],1,len,a[i],len)==(i-mid+1))r=mid-1,an=mid;
else l=mid+1;
}lmax[i]=an;
ll ans=0;
F(j,1,i){
if(rmax[j]){ans=max(ans,1ll*(rmax[j]-lmax[j]+1)*s[a[j]]);continue;}
l=j,r=i;
while(l<=r){
int mid=(l+r)>>1;
if(segm.ask(rt[j-1],rt[mid],1,len,a[j],len)==(mid-j+1))l=mid+1,an=mid;
else r=mid-1;
}if(an!=i)rmax[j]=an;
ans=max(ans,(r-lmax[j]+1)*s[a[j]]);
}pi(ans);
}return 0;
}
if(spj){
F(i,1,n){
dp[i]=dp[i-1];
while(tl>1&&lop(stack[tl],stack[tl-1])>lop(i,stack[tl]))tl--;
stack[++tl]=i;
int now=tl;
while(now>1&&lop(stack[now],stack[now-1])>=i){
dp[i]=max(dp[i],1ll*a[stack[now]]*(i-stack[now]+1));now--;
}dp[i]=max(dp[i],1ll*a[stack[now]]*(i-stack[now]+1));
pi(dp[i]);
}
}else solve();
return 0;
}
}
signed main(){return EMT::main();}
对每个点三分出最优的答案，用树状数组记录权值和与个数维护即可。
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("c.in","r",stdin);freopen("c.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline ll min(ll a,ll b){return a<b?a:b;}
inline void pi(ll x){pf("%lld ",x);}inline void pn(){pf("n");}
const int N=1e5+10;
ll trv[N<<1],tlv[N<<1];int trc[N<<1],tlc[N<<1];
int len,s[N<<1],v1[N],v2[N],n;
inline void add(ll *t,int x,int v){while(x<=len)t[x]+=v,x+=x&-x;}
inline void add(int *t,int x,int v){while(x<=len)t[x]+=v,x+=x&-x;}
inline ll ask(ll *t,int x){ll ans=0;while(x)ans+=t[x],x-=x&-x;return ans;}
inline int ask(int *t,int x){int ans=0;while(x)ans+=t[x],x-=x&-x;return ans;}
inline ll check(int x,int val){
if(val-(x-1)<=0||val-(n-x)<=0)return 1e18;
int val1=val+x,val2=val-x;
val1=std::upper_bound(s+1,s+len+1,val1)-s-1;
val2=std::upper_bound(s+1,s+len+1,val2)-s-1;
int c1,c2;ll vv1,vv2;
c1=ask(trc,val1),c2=ask(trc,len)-c1;
vv1=ask(trv,val1),vv2=ask(trv,len)-vv1;
ll ans=0;
ans=1ll*c1*(val+x)-vv1+vv2-1ll*c2*(val+x);
c1=ask(tlc,val2),c2=ask(tlc,len)-c1;
vv1=ask(tlv,val2),vv2=ask(tlv,len)-vv1;
ans+=1ll*c1*(val-x)-vv1+vv2-1ll*c2*(val-x);
return ans;
}
inline short main(){
file();
n=read();
F(i,1,n){
int x=read();v1[i]=x+i,v2[i]=x-i;
s[++len]=v1[i],s[++len]=v2[i];
}
std::sort(s+1,s+len+1);
len=std::unique(s+1,s+len+1)-s-1;
F(i,1,n)v1[i]=std::lower_bound(s+1,s+len+1,v1[i])-s,v2[i]=std::lower_bound(s+1,s+len+1,v2[i])-s;
F(i,1,n)add(trv,v1[i],s[v1[i]]),add(trc,v1[i],1);
ll ans=1e18;
F(i,1,n){
int l=1,r=1e9;
while(r-l>=3){
int mid1=l+(r-l)/3,mid2=r-(r-l)/3;
if(check(i,mid1)<check(i,mid2))r=mid2;
else l=mid1;
}F(j,l,r)ans=min(ans,check(i,j));
add(trv,v1[i],-s[v1[i]]),add(trc,v1[i],-1);
add(tlv,v2[i],s[v2[i]]),add(tlc,v2[i],1);
}pi(ans);
return 0;
}
}
signed main(){return EMT::main();}
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("kdgraph.in","r",stdin);freopen("kdgraph.out","w",stdout);}
inline ll max(ll a,ll b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("n");}
const int N=1e6+10;
struct jws{ll n,m,b;}js;
struct jsw{ll point,edge,in;}ans;
bool vis[N],ban[N];
int n,m,co,head[N],deg[N],An;ll an=-1e18;
std::queue<int>q;
struct node{int next,to;}e[N<<1];
inline void add(int next,int to){e[++co]=(node){head[next],to},head[next]=co;}
inline void dfs(int k,int from){
vis[k]=1;ans.point++;
for(register int i=head[k],j;i;i=e[i].next){
j=e[i].to;
if(ban[j])ans.edge++;
else{ans.in++;if(!vis[j])dfs(j,k);}
}
}
inline short main(){
file();
n=read(),m=read();
js.m=read(),js.n=read(),js.b=read();
F(i,1,m){
int x=read(),y=read();
deg[x]++;deg[y]++;
add(x,y);add(y,x);
}
F(i,1,n)if(!deg[i])ban[i]=1;
F(k,1,n){
bool fl=1;
F(i,1,n)if(deg[i]>=k)vis[i]=0,fl=0;
if(fl)break;
F(i,1,n)if(!vis[i]&&!ban[i]){
ans.point=ans.in=ans.edge=0;
dfs(i,0);ans.in/=2;
if(an<-ans.point*js.n+ans.edge*js.b+ans.in*js.m){
an=-ans.point*js.n+ans.edge*js.b+ans.in*js.m;
An=k;
}else if(an==-ans.point*js.n+ans.edge*js.b+ans.in*js.m)An=k;
}
F(i,1,n)if(deg[i]==k)q.push(i);
while(!q.empty()){
int x=q.front();q.pop();ban[x]=1;
for(register int i=head[x],j;i;i=e[i].next){
j=e[i].to;if(ban[j])continue;
deg[j]--;
if(deg[j]==k)q.push(j);
}
}
}pf("%d %lld",An,an);
return 0;
}
}
signed main(){return EMT::main();}
用bitset n^3水过了，建议加强数据
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<bitset>
#include<unordered_map>
#include<algorithm>
#include<vector>
using std::cin;
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("class.in","r",stdin);freopen("class.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("n");}
const int N=1100;std::bitset<N>fa[N];
std::unordered_map<std::string,int>mp;
int co,n,dp[N],cnt,v[N];std::string s,base;
inline void no(){pf("greskan");}
inline void yes(){pf("okn");}
inline short main(){
file();
cin>>n;
while(n--){
cnt=0;
cin>>s;base=s;bool fl=1;
if(mp[s]){no();while(s[0]!=';')cin>>s;continue;}
while(s[0]!=':')cin>>s;
cin>>s;
while(s[0]!=';'){
int x=mp[s];if(!x){fl=0;while(s[0]!=';')cin>>s;break;}
v[++cnt]=x;cin>>s;
}
F(i,1,cnt){F(j,i+1,cnt)if((fa[v[i]]&fa[v[j]]).count())
{if(!fa[v[i]][v[j]]&&!fa[v[j]][v[i]]){fl=0;break;}}if(!fl)break;}
if(fl){
yes();mp[base]=++co;fa[co][co]=1;
F(i,1,cnt)fa[co]|=fa[v[i]];
}else no();
}
return 0;
}
}
signed main(){return EMT::main();}
开两个变量记录现在A和P的数量即可O(n)求解
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("apstr.in","r",stdin);freopen("apstr.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("n");}
char s[10005];
int n,suma,sumb,ans;
inline short main(){
file();
scanf("%s",s+1);
n=strlen(s+1);
F(i,1,n)if(s[i]=='A')suma++;else{
if(suma)suma--,ans++;
else sumb++;
}sumb%=2;
pi(sumb+suma);
return 0;
}
}
signed main(){return EMT::main();}
暴力模拟即可。
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("ip.in","r",stdin);freopen("ip.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(int x){pf("%d",x);}inline void pn(){pf("n");}
char s[35],S[35];int ans[5],slen;
inline short main(){
file();
scanf("%s",s+1);int len=strlen(s+1);s[len+1]='.';
int key=0;
F(i,1,4){
int x=0;bool fl=1;key++;char ch=s[key];
while(ch<'0'||ch>'9')key++,ch=s[key];
while(ch>='0'&&ch<='9'){
if(fl)x=x*10+ch-'0';key++;ch=s[key];
if(x>255)fl=0,ans[i]=255;
}if(!ans[i])ans[i]=x;
}
F(i,1,4){
if(ans[i]>=100){
int a100=ans[i]/100,a10=ans[i]/10-a100*10,a1=ans[i]-a10*10-a100*100;
S[++slen]=a100+'0',S[++slen]=a10+'0',S[++slen]=a1+'0';
}
else if(ans[i]>=10){
int a10=ans[i]/10,a1=ans[i]-a10*10;
S[++slen]=a10+'0',S[++slen]=a1+'0';
}else S[++slen]=ans[i]+'0';
if(i!=4)S[++slen]='.';
}bool fl=1;
if(len!=slen)fl=0;
F(i,1,len)if(s[i]!=S[i])fl=0;
puts(fl?"YES":"NO");
if(fl)return 0;
pf("%s",S+1);
return 0;
}
}
signed main(){return EMT::main();}
2021-09-19 19:22:25 星期日
考试时在1e9内暴力rand，稳定70pts，加上没脸qj数据点套得(s/t)，可不用数据点分治直接求出答案。
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<ctime>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define int long long
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("d.in","r",stdin);freopen("d.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("n");}
int n,ans=1e9;const int N=3e5+10;
inline int random(int x){return rand()*rand()%x;}
struct thing{int a,b,c,val;
friend bool operator <(thing a,thing b){return a.val<b.val;}}p[N<<1];
inline void check(int s,int t){
F(i,1,n)p[i].val=p[i].a*(db)s/(db)t+p[i].b;
std::sort(p+1,p+n+1);
int lv=p[1].val,lk=1,rv=p[n].val,rk=n,l=1,r=n;
while(!p[l].c){
l++;
if(p[l].val!=lv)lv=p[l].val,lk=l;
}l=lk;
while(!p[r].c){
r--;
if(p[r].val!=rv)rv=p[r].val,rk=r;
}r=rk;
ans=min(ans,r-l+1);
}
void begin();
inline short main(){
file();
srand(time(0));
n=read();
F(i,1,n)p[i].a=read(),p[i].b=read(),p[i].c=read();
begin();
while(1){
if(clock()>=950000)break;
int s=(random(2)&1?1:-1)*random(100000000);
int t=(random(2)&1?1:-1)*random(100000000);
check(s,t);
}pi(n<=2000?ans:ans-1);
return 0;
}
void begin(){
check(1,0);check(0,1);
check(1,1);check(1,2);check(1,-1);check(1,-2);
check(5226,1);check(-1324,1);check(67,1);check(15000,1);
check(5,10);check(-965,100);check(-18896,1);
}
}
signed main(){return EMT::main();}
首先得到每种结果的概率都相等，通过一种方案的概率乘上方案总数可以算到每种情况的概率相等
@H_469_304@[frac{prodlimits_{i=1}^{n}(a_i-1)!}{n(n+1)...(n+m-1)}times frac{m!}{prodlimits_{i=1}^{n}(a_i-1)!}=frac{1}{C_{n+m-1}^{n-1}} ]考虑到贡献乘概率，设(f_{i,j})表示至少i个数>=j的方案数，则对于一个r的答案为
因为每个数的贡献在这个式子中会通过重复部分巧妙地累加上去。 设(g_{i,j})表示恰好i个数>=j的方案数，则f是g的后缀和。 g可通过二项式反演容斥得到，设(h(i,j))表示至少i个数>=j的方案数，注意h和f定义不一样，h还考虑到到达结果的路径，而f只考虑结果。 考虑钦定i个数>=j,将剩下的m+n-jk分到n个数上，于是
于是就可做了.
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("c.in","r",stdin);freopen("c.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("n");}
const int N=5e3+10,M=100000,mod=1e9+7;
int jc[M],inv[M],n,m,g[N][N],f[N][N];
inline int ksm(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*ans*a%mod;
b>>=1;a=1ll*a*a%mod;
}return ans;
}
inline int C(int n,int m){if(m<0||m>n)return 0;return 1ll*jc[n]*inv[m]%mod*inv[n-m]%mod;}
inline short main(){
file();
n=read(),m=read();
jc[0]=1;inv[0]=inv[1]=1;
F(i,1,n+m)jc[i]=1ll*jc[i-1]*i%mod;
inv[n+m]=ksm(jc[n+m],mod-2);
D(i,n+m,3)inv[i-1]=1ll*inv[i]*i%mod;
F(i,1,n)F(j,1,m/i)F(k,i,min(m/j,n))
g[i][j]+=1ll*C(k,i)%mod*((k-i)&1?-1:1)*C(n,k)%mod*C(m+n-1-j*k,n-1)%mod,
g[i][j]-=g[i][j]>=mod?mod:(g[i][j]<0?-mod:0);
D(i,n,1)D(j,m/i,1)f[i][j]=f[i+1][j]+g[i][j],f[i][j]-=f[i][j]>=mod?mod:0;
int sum=0,Inv=ksm(C(n+m-1,n-1),mod-2);
F(r,1,n){
F(l,1,m)sum+=f[r][l],sum-=sum>=mod?mod:0;
pi(1ll*(1ll*sum*Inv%mod+r)%mod);pn();
}
return 0;
}
}
signed main(){return EMT::main();}
用珂朵莉树维护1-1e9上每个数现在被哪个点代表的区间所覆盖，将问题离线按r从小到大排序，当目前指针指到i时，若i原来覆盖的区间中长度为k的子区间被t所覆盖，那么对于左端点为[t+1,i]的问题有((i − l +1)(r − i + 1)k)的贡献（因为原来碰不到现在能碰到了)，相反对于[1,t]的问题就碰不到了，于是减去((i − t)(r − i + 1)k)的贡献，用树状数组分l,r,lr,c的系数维护即可。
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<set>
using std::set;
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("b.in","r",stdin);freopen("b.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("n");}
const int N=2e5+10,mod=1e9+7;
int n,m,l[N],r[N];
struct tzsz{
int val[N];
inline void add(int x,int v){while(x)val[x]+=v,val[x]-=val[x]>=mod?mod:0,x-=x&-x;}
inline int ask(int x){int ans=0;while(x<=n)ans+=val[x],ans-=ans>=mod?mod:0,x+=x&-x;return ans;}
}tl,tr,tlr,tc;
struct node{
int l,r;mutable int last;
node(int l,int r=0,int last=0):l(l),r(r),last(last){}
friend bool operator <(node a,node b){return a.l<b.l;}
};
struct qus{
int l,r,id;
friend bool operator<(qus a,qus b){return a.r<b.r;}
}q[N];
set<node>s;
typedef set<node>::iterator sit;
inline sit split(int pos){
sit it=s.lower_bound(node(pos));
if(it!=s.end()&&it->l==pos)return it;
it--;if(it->r<pos)return s.end();
int l=it->l,r=it->r,v=it->last;
s.erase(it);
s.insert(node(l,pos-1,v));
return s.insert(node(pos,r,v)).First;
}
inline void assign(int l,int r,int tim){
sit itr=split(r+1),now=split(l);sit itl=now;
while(now!=itr){
int len=now->r-now->l+1,lasttim=now->last;
tl.add(tim,1ll*(-1+tim)*len%mod);tl.add(lasttim,1ll*(1-tim+mod)*len%mod);
tr.add(tim,1ll*(tim+1)*len%mod);tr.add(lasttim,1ll*(-lasttim-1+mod)*len%mod);
tlr.add(tim,1ll*(-1+mod)*len%mod);tlr.add(lasttim,len);
tc.add(tim,1ll*(1-1ll*tim*tim%mod+mod)%mod*len%mod);
tc.add(lasttim,1ll*(((tim-lasttim)%mod+1ll*tim*lasttim%mod)%mod-1+mod)%mod*len%mod);
now++;
}s.erase(itl,itr);
s.insert(node(l,r,tim));
}
inline int ksm(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*a*ans%mod;
b>>=1;a=1ll*a*a%mod;
}return ans;
}
int Ans[N];
inline short main(){
file();
n=read(),m=read();
F(i,1,n)l[i]=read(),r[i]=read()-1;
F(i,1,m)q[i].l=read(),q[i].r=read(),q[i].id=i;
std::sort(q+1,q+m+1);
int key=0;
s.insert(node(1,1e9,0));
F(i,1,m){
while(key<q[i].r)key++,assign(l[key],r[key],key);
int len=q[i].r-q[i].l+1,inv=ksm(1ll*len*(len+1)/2%mod,mod-2);
int ans=1ll*tl.ask(q[i].l)*q[i].l%mod;
ans+=1ll*tr.ask(q[i].l)*q[i].r%mod,ans-=ans>=mod?mod:0;
ans+=1ll*tlr.ask(q[i].l)*q[i].l%mod*q[i].r%mod,ans-=ans>=mod?mod:0;
ans+=tc.ask(q[i].l),ans-=ans>=mod?mod:0;
ans=1ll*ans*inv%mod;
Ans[q[i].id]=ans;
}
F(i,1,m)pi(Ans[i]),pn();
return 0;
}
}
signed main(){return EMT::main();}
是道同学们都做过的原题(除了我)
但是当时场切就很多，我这场没做出来还是自己的原因。
设(f_i)表示处理完i的子树最少多少步，记录(mxdep_i)表示i子树中最深的点，当(mxdep_i<deep_i*2)时说明从这里走到别处比从1走更优，于是可以补一下差价，答案就是(f_1)
#include<bits/stdc++.h>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("a.in","r",stdin);freopen("a.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("n");}
const int N=1e6+10;
int deep[N],mxdep[N],n,head[N],co,f[N];
struct node{int next,to;}e[N];
std::vector<int>son[N];
inline bool com(int i,int j){return mxdep[i]<mxdep[j];}
inline void add(int next,int to){e[++co]=(node){head[next],to};head[next]=co;}
inline void dfs(int k){
mxdep[k]=deep[k];
for(register int i=head[k],j;i;i=e[i].next){
j=e[i].to;deep[j]=deep[k]+1;
son[k].push_back(j);
dfs(j);mxdep[k]=max(mxdep[k],mxdep[j]);
}std::sort(son[k].begin(),son[k].end(),com);
}
inline void Dfs(int k){
if(son[k].size()){Dfs(son[k][son[k].size()-1]),f[k]+=f[son[k][son[k].size()-1]];}
else {f[k]=deep[k];return;}
F(i,0,(int)son[k].size()-2){
int j=son[k][i];
Dfs(j);f[k]+=f[j];
if(mxdep[j]<=deep[k]*2)f[k]-=deep[k]*2,f[k]+=mxdep[j];
}
}
inline short main(){
file();
n=read();F(i,2,n)add(read(),i);
dfs(1);Dfs(1);pi(f[1]);
return 0;
}
}
signed main(){return EMT::main();}
2021-09-17 20:31:28 星期五
题解
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("perm.in","r",stdin);freopen("perm.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("n");}
const int N=1e6+10,mod=1e9+7;
int n,k,m,ans,jc[N],inv[N];
inline int C(int n,int m){
if(m>n||m<0||n<0)return 0;
return 1ll*jc[n]*inv[m]%mod*inv[n-m]%mod;
}
inline int ksm(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*a*ans%mod;
a=1ll*a*a%mod;
b>>=1;
}return ans;
}
inline short main(){
file();
n=read(),k=read(),m=read();jc[0]=1;
n=n-(k-m),k=m;
F(i,1,n)jc[i]=1ll*jc[i-1]*i%mod;
inv[n]=ksm(jc[n],mod-2);inv[0]=inv[1]=1;
D(i,n-1,2)inv[i]=1ll*inv[i+1]*(i+1)%mod;
if(k==1){pi(n-1);return 0;}
F(i,2,k)ans+=C(n-i,k-i+2),ans-=ans>=mod?mod:0;
F(i,2,n){
int num=C(n-i-1,k-2);
int tmp=i-1;
ans+=1ll*num*tmp%mod,ans-=ans>=mod?mod:0;
}pi(ans);
return 0;
}
}
signed main(){return EMT::main();}
考虑将每个向量之间夹的角形成的范围分割开，每个范围内取一个向量求相对大小再用克鲁斯卡尔求解。
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("mst.in","r",stdin);freopen("mst.out","w",stdout);}
inline db max(db a,db b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(db x){pf("%.6lf ",x);}inline void pn(){pf("n");}
const int N=55;
const db pai=3.1415926535;
int fa[N],co,head[N],n,m,cou;db ans,jiao[N*N*N*N];
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
struct node{int u,v,a,b;db val;friend bool operator <(node a,node b){return a.val>b.val;}}e[N*N];
inline void add(int next,int to,int a,int b){e[++co]=(node){next,to,a,b};}
inline void krus(){
std::sort(e+1,e+m+1);
F(i,1,n)fa[i]=i;
int cnt=0;
int ansa=0,ansb=0;
F(i,1,m){
int fx=find(e[i].u),fy=find(e[i].v);
if(fx!=fy){
fa[fy]=fx,cnt++;
ansa+=e[i].a;
ansb+=e[i].b;
if(cnt==n-1)break;
}
}ans=max(ans,sqrt(ansa*ansa+ansb*ansb));
}
inline short main(){
file();
n=read(),m=read();
F(i,1,m){
int u=read(),v=read(),a=read(),b=read();
add(u,v,a,b);
}
F(i,1,m)F(j,i+1,m){
if(e[i].b==e[j].b)continue;
jiao[++cou]=atan((db)(e[j].a-e[i].a)/(db)(e[i].b-e[j].b));
cou++;jiao[cou]=jiao[cou-1]+pai;
}jiao[++cou]=pai/2,jiao[++cou]=pai*1.5;
std::sort(jiao+1,jiao+cou+1);
F(i,1,cou-1){
db jia=(jiao[i]+jiao[i+1])/2.0;
F(j,1,m){
db aa=e[j].a*cos(jia),bb=e[j].b*sin(jia);
e[j].val=aa+bb;
}krus();
jia+=pai;
F(j,1,m){
db aa=e[j].a*cos(jia),bb=e[j].b*sin(jia);
e[j].val=aa+bb;
}krus();
}
db jia=(jiao[cou]+jiao[1])/2.0;
F(i,1,m){
db aa=e[i].a*cos(jia),bb=e[i].b*sin(jia);
e[i].val=aa+bb;
}krus();
pi(ans);
return 0;
}
}
signed main(){return EMT::main();}
CDQ分治维护单调栈，(数据)点分治
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define int long long
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("skip.in","r",stdin);freopen("skip.out","w",stdout);}
inline ll max(ll a,ll b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(ll x){pf("%lld ",x);}inline void pn(){pf("n");}
const int N=1e5+10;ll pre[N],f[N],a[N];
struct pt{int plc,a;ll f;}p[N],s[N];
inline bool com(pt a,pt b){return a.plc<b.plc;}
int n,hd,tl;
inline bool com1(pt a,pt b){return a.a==b.a?a.plc<b.plc:a.a<b.a;}
inline db lop(pt j,pt k){return (db)(k.f*2-k.plc*k.plc-k.plc+j.plc*j.plc+j.plc-2*j.f)/(db)(2*j.plc-2*k.plc);}
inline int len(int l,int r){return r-l+1;}
inline void cdq(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
cdq(l,mid);
std::sort(p+l,p+mid+1,com);std::sort(p+mid+1,p+r+1,com);
int j=l;hd=1;tl=0;
F(i,mid+1,r){
while(p[j].plc<p[i].plc&&j<=mid){
while(tl>1&&lop(s[tl],s[tl-1])>lop(p[j],s[tl]))tl--;
s[++tl]=p[j];j++;
}
int TTL=tl;
while(ttl>1&&lop(s[ttl],s[ttl-1])>i)ttl--;
p[i].f=max(p[i].f,s[ttl].f-pre[len(s[ttl].plc+1,p[i].plc-1)]+p[i].a);
}
std::sort(p+l,p+r+1,com1);
cdq(mid+1,r);
}
inline short main(){
file();
n=read();
F(i,1,n)p[i].a=a[i]=read(),p[i].plc=i;
F(i,1,n)pre[i]=pre[i-1]+i;
F(i,1,n)p[i].f=-1ll*(i-1)*i/2+1ll*p[i].a;
ll ans1=-1e18;
a[0]=-1e9-10;
F(i,1,n)f[i]=-1e18;
if(n>2150){F(i,1,2149)F(j,0,i-1)if(a[i]>=a[j])f[i]=max(f[i],f[j]-pre[len(j+1,i-1)]+a[i]);
F(i,2150,n)F(j,i-2150,i-1)if(a[i]>=a[j])f[i]=max(f[i],f[j]-pre[len(j+1,i-1)]+a[i]);
}else F(i,1,n)F(j,0,i-1)if(a[i]>=a[j])f[i]=max(f[i],f[j]-pre[len(j+1,i-1)]+a[i]);
F(i,0,n)ans1=max(ans1,f[i]-pre[len(i+1,n)]);
p[0].a=-1e9-10;
std::sort(p+0,p+n+1,com1);
cdq(0,n);
std::sort(p+0,p+n+1,com);
ll ans=-1e18;
F(i,0,n)ans=max(ans,p[i].f-pre[len(i+1,n)]);
pi(max(ans1,ans));
return 0;
}
}
signed main(){return EMT::main();}
2021-09-16 19:41:18 星期四 淦，上一个大集合卡展了，写博客写到一半就崩溃，崩溃了好几次了，于是新开了一个
打正解是不可能打正解的~~
这个是考完了用乱搞贪心水掉的，然后拿沈sir程序造hack数据hack自己结果把沈sir hack了...数据是XIN造的，把我也hack了，本来以为只有自己会无脸测试点分治结果沈sir也来了个if(n<=10)...虽然沈sir不偷懒改改就能过吧...
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("fittest.in","r",stdin);freopen("fittest.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline ll min(ll a,ll b){return a<b?a:b;}
inline void pi(ll x){pf("%lld ",x);}inline void pn(){pf("n");}
const int N=3e5+10;
struct pt{
int cheng;db chu;
int c,a,d,id;
}p[N];int n,b,sum;bool vis[N];ll ans=1e18;
inline bool com(pt a,pt b){return a.cheng==b.cheng?a.a>b.a:a.cheng>b.cheng;}
inline bool Com(pt a,pt b){return a.chu<b.chu;}
inline void solve(){
std::sort(p+1,p+n+1,Com);
F(i,1,n)F(j,i+1,n){
vis[i]=vis[j]=1;
int sum=0;ll aans=0;
F(k,1,n)if(!vis[k])sum+=p[k].a;
F(k,1,n)if(!vis[k]){
sum-=p[k].a;aans+=1ll*p[k].a*p[k].c;
aans+=1ll*sum*(p[k].c+1);
}
vis[i]=vis[j]=0;
ans=min(ans,aans);
}pi(ans);
}
inline short main(){
file();
n=read();b=read();
F(i,1,n){
p[i].id=i;
p[i].a=read(),p[i].d=read();
sum+=p[i].a;
p[i].c=(p[i].d-1)/b;
p[i].cheng=p[i].c*p[i].a;
p[i].chu=(db)1.0*(p[i].c+1)/(db)p[i].a;
}
if(n<=200){solve();return 0;}
std::sort(p+1,p+n+1,com);
vis[p[1].id]=vis[p[2].id]=1;
sum-=p[1].a,sum-=p[2].a;
std::sort(p+1,p+n+1,Com);ans=0;
F(i,1,n)if(!vis[p[i].id]){
sum-=p[i].a;ans+=1ll*p[i].a*p[i].c;
ans+=1ll*sum*(p[i].c+1);
}pi(ans);
return 0;
}
}
signed main(){return EMT::main();}
首先每个点连接的边<=10,n<=1e3于是可以状压dp，考试时想到了这个，但是不会处理经过根节点的路径和叶子节点的关系， 可以尝试状压表示经过根节点最多路径有几条，尝试删去某个子树，如果删掉之后答案没变，那么可以将这个子树对应的儿子的延伸结点复制过来，其他的就是普通树形dp统计上子树内的路径即可。
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("select.in","r",stdin);freopen("select.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("n");}
const int N=1e3+10;
int head[N],co,n,m,id[N];
int f[N][1<<10],dp[N];
struct pair{int a,b;};
bool graph[N][N];pair rec[N];int cnt,Rec[N],Cnt;
std::vector<int>son[N],touch[N];
struct node{
int next,to;
}e[N<<1];
inline void add(int next,int to){e[++co]=(node){head[next],to};head[next]=co;}
inline void dfs1(int k,int fa){
int tot=0;
for(register int i=head[k],j;i;i=e[i].next){
if((j=e[i].to)==fa)continue;
++tot;son[k].push_back(j);
id[j]=tot;
dfs1(j,k);
}
}
inline void dfs(int k){
touch[k].push_back(k);
for(auto j:son[k])dfs(j),dp[k]+=dp[j];
cnt=Cnt=0;
for(auto i:son[k])
for(auto j:son[k])if(id[i]<id[j]){
for(auto l:touch[i])
for(auto o:touch[j])
if(graph[l][o])
{rec[++cnt]=(pair){i,j};goto ed;}
ed:;
}
for(auto i:son[k])
for(auto j:touch[i])
if(graph[k][j])Rec[++Cnt]=i;
int maxn=0;
F(i,0,(1<<son[k].size())-1){
maxn=max(maxn,f[k][i]);
F(j,1,cnt){
int u=rec[j].a,v=rec[j].b;
if(i&(1<<(id[u]-1))||i&(1<<(id[v]-1)))continue;
f[k][i|(1<<(id[u]-1))|(1<<(id[v]-1))]=max(f[k][i|(1<<(id[u]-1))|(1<<(id[v]-1))],f[k][i]+1);
}
F(j,1,Cnt){
int u=Rec[j];
if(i&(1<<(id[u]-1)))continue;
f[k][i|(1<<(id[u]-1))]=max(f[k][i|(1<<(id[u]-1))],f[k][i]+1);
}
}dp[k]+=maxn;
for(auto x:son[k]){
int Maxn=0;
F(i,0,(1<<son[k].size())-1)f[k][i]=0;
F(i,0,(1<<son[k].size())-1){
Maxn=max(Maxn,f[k][i]);
F(j,1,cnt){
int u=rec[j].a,v=rec[j].b;
if(u==x||v==x)continue;
if(i&(1<<(id[u]-1))||i&(1<<(id[v]-1)))continue;
f[k][i|(1<<(id[u]-1))|(1<<(id[v]-1))]=max(f[k][i|(1<<(id[u]-1))|(1<<(id[v]-1))],f[k][i]+1);
}
F(j,1,Cnt){
int u=Rec[j];
if(u==x)continue;
if(i&(1<<(id[u]-1)))continue;
f[k][i|(1<<(id[u]-1))]=max(f[k][i|(1<<(id[u]-1))],f[k][i]+1);
}
}
if(Maxn==maxn)for(auto i:touch[x])touch[k].push_back(i);
}
}
inline short main(){
file();
n=read();
F(i,1,n-1){
int x=read(),y=read();
add(x,y);add(y,x);
}dfs1(1,0);
m=read();
F(i,1,m){
int u=read(),v=read();
graph[u][v]=graph[v][u]=1;
}dfs(1);
pi(dp[1]);
return 0;
}
}
signed main(){return EMT::main();}
以上是脚本宝典为你收集整理的模拟题大集合(2)全部内容，希望文章能够帮你解决模拟题大集合(2)所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。