【csp-j】20191021【模拟】【搜索】【二分】【AC自动机】

传送门咕了。

特殊排序

数字交换就行。

（我竟然写挂了日）

代码不放了，，反正是错的。

部落卫队

强行dfs哈哈哈哈哈加个最优性剪枝

#include<bits/stdc++.h>
using namespace std;
#define in read()
int in{
	int cnt=0,f=1;char ch=0;
	while(!isdigit(ch)){
		ch=getchar();if(ch=='-')f=-1;
	}
	while(isdigit(ch)){
		cnt=cnt*10+ch-48;ch=getchar();
	}return cnt*f;
}
int n,m,is[103];
int a[103][103];
int ans,cnt[103],flag[103];
int now;
void dfs(int u){
	if(u==n+1){
		if(now>ans){
			ans=now;
			for(int i=1;i<=n;i++)is[i]=flag[i];
		}return;
	}
	if(now+n-u+1<ans)return;
	if(!cnt[u]){
		flag[u]=1;now++;
		for(int i=1;i<=n;i++)cnt[i]+=a[u][i];
		dfs(u+1);
		for(int i=1;i<=n;i++)cnt[i]-=a[u][i];
		now--;
	}
	flag[u]=0;
	dfs(u+1);
}
signed main(){
	freopen("guard.in","r",stdin);
	freopen("guard.out","w",stdout);
	n=in;m=in;
	for(int i=1;i<=m;i++){
		int x=in;int y=in;a[x][y]=a[y][x]=1;
	}dfs(1);
	cout<<ans<<'\n';
	for(int i=1;i<=n;i++)cout<<is[i]<<" ";
	return 0;
}

数字排序

先二分答案，然后二分数量。完了。

#include<bits/stdc++.h>
using namespace std;
#define in read()
int in{
	int cnt=0,f=1;char ch=0;
	while(!isdigit(ch)){
		ch=getchar();if(ch=='-')f=-1;
	}
	while(isdigit(ch)){
		cnt=cnt*10+ch-48;
		ch=getchar();
	}return cnt*f;
}
int a[10003],b[10003],n,ans,l,r,m,k;
int add(int now,int x){
	int L=0,R=m;int gu;
	while(L<=R){
		int mid=(L+R)>>1;
		if(now*b[mid]>x)R=mid-1;
		else L=mid+1,gu=mid;
	}return gu;
}
int check(int x){
	int sum=0;
	for(int i=1;i<=n;i++){
		sum+=add(a[i],x);
	}return sum;
}
signed main(){
	freopen("numsort.in","r",stdin);
	freopen("numsort.out","w",stdout);
	n=in;m=in;k=in;
	for(int i=1;i<=n;i++)a[i]=in;
	for(int i=1;i<=m;i++)b[i]=in;
	sort(a+1,a+n+1);sort(b+1,b+m+1);r=a[n]*b[m];
	while(l<=r){//cout<<l<<" "<<r<<endl;
		int mid=(l+r)>>1;//cout<<check(mid)<<endl;
		if(check(mid)>=k)r=mid-1,ans=mid;
		else l=mid+1;
	}cout<<ans;
	return 0;
}

单词

AC自动机建出来fail子树size和。或者从下往上更新也可以（其实跟dfs一样）

#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
	int ch[26],fail,key; 
}t[2000003];
int belong[2000003];int cnt;
int first[2000003],nxt[2000003],to[2000003],tot;
void add(int a,int b){
	nxt[++tot]=first[a];first[a]=tot;to[tot]=b;
}char ch[2333333];
int l[1000003],r[1000003],key[2000003];
int insert(char s[],int len){
	int rt=0;
	for(int i=1;i<=len;i++){
		if(!t[rt].ch[s[i]-'a']){
			t[rt].ch[s[i]-'a']=++cnt;
		}rt=t[rt].ch[s[i]-'a'];
		t[rt].key++;
	}return rt;
}queue<int> q;
void getfail(){
	for(int i=0;i<26;i++){
		if(t[0].ch[i])q.push(t[0].ch[i]);
	}
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=0;i<26;i++){
			if(t[u].ch[i]){
				t[t[u].ch[i]].fail=t[t[u].fail].ch[i];q.push(t[u].ch[i]);
			}else{
				t[u].ch[i]=t[t[u].fail].ch[i];
			}
		}
	}
}
void query(char s[],int st,int ed){
	int rt=0;
	for(int i=st;i<=ed;i++){
		rt=t[rt].ch[s[i]-'a'];
		t[rt].key++;
	}
}
void dfs(int u){
	key[u]=t[u].key;
	for(int i=first[u];i;i=nxt[i]){
		int v=to[i];dfs(v);key[u]+=key[v];
	}
}
signed main(){
	freopen("word.in","r",stdin);
	freopen("word.out","w",stdout);
	cin>>n;
	for(int i=1,L=1,R;i<=n;i++){
		scanf("%s",ch+1);int len=strlen(ch+1);belong[i]=insert(ch,len); 
	}
	
	getfail();
	//for(int i=1;i<=cnt;i++)cout<<t[i].fail<<" ";cout<<endl;
	//for(int i=1;i<=cnt;i++)cout<<t[i].key<<" ";cout<<endl;
	for(int i=1;i<=cnt;i++)add(t[i].fail,i);
	dfs(0);
	for(int i=1;i<=n;i++){
		cout<<key[belong[i]]<<'\n';
	}
	return 0;
}