【CSP-S2019模拟】题解

T1：

找点双就可以了

没注意空间$MLE$了

#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<<20|1;
inline char gc(){
    static char ibuf[RLEN],*ib,*ob;
    (ob==ib)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
    return (ob==ib)?EOF:*ib++;
}
inline int read(){
    char ch=gc();
    int res=0,f=1;
    while(!isdigit(ch))f^=ch=='-',ch=gc();
    while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
    return f?res:-res;
}
#define ll long long
#define re register
#define pii pair<int,int>
#define pic pair<int,char>
#define fi first
#define se second
#define pb push_back
#define cs const
#define bg begin
#define poly vector<int>
template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;}
template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;}
cs int N=1000005;
int adj[N],in[N],nxt[N<<1],to[N<<1],cnt=1;
inline void addedge(int u,int v){
	nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v;
}
int dfn[N],low[N],tim,bel[N],belnum,num[N],ee[N],ans[N];
int stk[N],top,n,m,vis[N];
pii E[N];
vector<int> cir[N];
void dfs(int u,int fa){
	dfn[u]=low[u]=++tim;
	stk[++top]=u;
	for(int e=adj[u];e;e=nxt[e]){
		int v=to[e];
		if(v==fa)continue;
		if(!dfn[v]){
			dfs(v,u),chemn(low[u],low[v]);
		}
		else {chemn(low[u],dfn[v]);continue;}
		if(low[v]>=dfn[u]){
			int tmp;
			belnum++;
			do{
				tmp=stk[top];
				cir[belnum].pb(tmp);
				num[belnum]++;
				top--;
			}while(tmp!=v);
			cir[belnum].pb(u);
			num[belnum]++;
		}		
	}

}
int main(){
int size=40<<20;//40M
    //__asm__ ("movl  %0, %%esp
"::"r"((char*)malloc(size)+size));//调试用这个 
    __asm__ ("movq %0,%%rsp
"::"r"((char*)malloc(size)+size));//提交用这个 

	n=read(),m=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		E[i].fi=u,E[i].se=v;
		addedge(u,v),addedge(v,u);
	}
	dfs(1,0);
	for(int i=1;i<=belnum;i++){
		for(int j=0;j<cir[i].size();j++){
			bel[cir[i][j]]=i;
		}
		for(int j=0;j<cir[i].size();j++){
			int u=cir[i][j];
			for(int e=adj[u];e;e=nxt[e]){
				int v=to[e];
				if(bel[v]==bel[u]&&dfn[u]>dfn[v]){
					ee[i]++;
					ans[i]^=e>>1;
				}
			}
		}
	}
	int res=0;
	for(int i=1;i<=belnum;i++){
		if(ee[i]==num[i])res^=ans[i];
	}
	cout<<res;exit(0);//必须用exit 
}

T2：

矩乘就完了
为了限制节点之间的不可达赋成$-inf$

#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<<20|1;
inline char gc(){
    static char ibuf[RLEN],*ib,*ob;
    (ob==ib)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
    return (ob==ib)?EOF:*ib++;
}
#define gc getchar
inline int read(){
    char ch=gc();
    int res=0,f=1;
    while(!isdigit(ch))f^=ch=='-',ch=gc();
    while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
    return f?res:-res;
}
#define ll long long
#define re register
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define cs const
#define bg begin
template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;}
template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;}
cs int N=205;
int tot;
cs ll inf=1e18;
struct mat{
	ll a[N][N];
	mat(){for(int i=0;i<N;i++)for(int j=0;j<N;j++)a[i][j]=-inf;}
	friend inline mat operator *(cs mat &a,cs mat &b){
		mat c;
		for(int i=0;i<=tot;i++)
		for(int k=0;k<=tot;k++)if(a.a[i][k]!=-inf)
		for(int j=0;j<=tot;j++)if(a.a[i][k]!=-inf)
		chemx(c.a[i][j],a.a[i][k]+b.a[k][j]);
		return c;
	}
}bas,res;
namespace Ac{
	int val[N],fail[N],nxt[N][26];
	inline void insert(char *s,int v){
		int p=0;
		for(int i=1,len=strlen(s+1);i<=len;i++){
			int c=s[i]-'a';
			if(!nxt[p][c])nxt[p][c]=++tot;
			p=nxt[p][c];
		}
		val[p]+=v;
	}
	inline void build(){
		queue<int> q;
		for(int i=0;i<26;i++)if(nxt[0][i])q.push(nxt[0][i]);
		while(!q.empty()){
			int u=q.front();q.pop();
			val[u]+=val[fail[u]];
			for(int i=0;i<26;i++){
				int v=nxt[u][i];
				if(v)fail[v]=nxt[fail[u]][i],q.push(v);
				else nxt[u][i]=nxt[fail[u]][i];
			}
		}
		for(int i=0;i<=tot;i++){
			for(int c=0;c<26;c++){
				int v=nxt[i][c];
				chemx(bas.a[i][v],(ll)val[v]);
			}
		}
	}
}
ll n;
int m,a[N];
char s[N];
int main(){
	cin>>n;
	m=read();
	for(int i=1;i<=m;i++){
		a[i]=read();
	}
	for(int i=1;i<=m;i++){
		scanf("%s",s+1);
		Ac::insert(s,a[i]);
	}
	Ac::build();
	n--;res=bas;
	for(;n;n>>=1,bas=bas*bas)if(n&1)res=res*bas;
	ll ans=0;
	for(int i=0;i<=tot;i++)chemx(ans,res.a[0][i]);
	cout<<ans;
}

T3：

裸的线段树建图做差分约束

不知道为什么$topsort$跑出来就对了$spfa$就错了

#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<<20|1;
inline char gc(){
    static char ibuf[RLEN],*ib,*ob;
    (ob==ib)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
    return (ob==ib)?EOF:*ib++;
}
#define gc getchar
inline int read(){
    char ch=gc();
    int res=0,f=1;
    while(!isdigit(ch))f^=ch=='-',ch=gc();
    while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
    return f?res:-res;
}
#define ll long long
#define re register
#define pii pair<int,int>
#define pic pair<int,char>
#define fi first
#define se second
#define pb push_back
#define cs const
#define bg begin
#define poly vector<int>
template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;}
template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;}
cs int N=1000005;
vector<pii> e[N];
int n,m,tot,pos[N],in[N];
inline void addedge(int u,int v,int  w){
	e[u].pb(pii(v,w));in[v]++;
}
namespace Seg{
	int tr[N<<2];
	#define lc (u<<1)
	#define rc ((u<<1)|1)
	#define mid ((l+r)>>1)
	void build(int u,int l,int r){
		tr[u]=++tot;
		if(l==r){pos[l]=tr[u];return;}
		build(lc,l,mid),build(rc,mid+1,r);
		addedge(tr[lc],tr[u],0),addedge(tr[rc],tr[u],0);
	}
	void update(int u,int l,int r,int st,int des,int p){
		if(st>des)return;
		if(st<=l&&r<=des)return addedge(tr[u],p,0);
		if(st<=mid)update(lc,l,mid,st,des,p);
		if(mid<des)update(rc,mid+1,r,st,des,p);
	}
}
int a[N],str,dis[N],vis[N];
int s,p[N],d[N],ms[N];
queue<int> q;
inline void topsort(){
	for(int i=1;i<=tot;i++)if(!in[i])q.push(i);
	while(!q.empty()){
		int u=q.front();q.pop();vis[u]=1;
		for(int i=0;i<e[u].size();i++){
			pii x=e[u][i];
			in[x.fi]--;
			chemx(dis[x.fi],dis[u]+x.se);
			if(!in[x.fi])q.push(x.fi);
		}
	}
}
int main(){
	n=read(),s=read(),m=read();
	Seg::build(1,1,n);
	str=++tot;
	for(int i=1;i<=s;i++){
		p[i]=read(),d[i]=read();
		dis[pos[p[i]]]=d[i];
	}
	for(int i=1;i<=m;i++){
		int l=read(),r=read(),k=read();
		tot++;a[0]=l-1,a[k+1]=r+1;
		for(int j=1;j<=k;j++)
		a[j]=read(),addedge(tot,pos[a[j]],1);
		for(int j=1;j<=k+1;j++)
		Seg::update(1,1,n,a[j-1]+1,a[j]-1,tot);
	}
	for(int i=1;i<=tot;i++)if(i!=str)addedge(str,i,1);
	topsort();
	for(int i=1;i<=n;i++)if(dis[pos[i]]>1e9)puts("Impossible"),exit(0);
	for(int i=1;i<=s;i++){
		if(dis[pos[p[i]]]!=d[i])puts("Impossible"),exit(0);
	}
	puts("Possible");
	for(int i=1;i<=n;i++)cout<<dis[pos[i]]<<" ";
}

总结：

犯了一堆$sb$错误
没注意空间
调试技巧太烂
不会写代码了

再出类似的问题剁头