Day-3【游记】

T2有很多人见过原题，于是把这题换成了T4

开考先看T1，发现是傻逼题

发现似乎只有 \(27\) 种情况，写写就过了样例

然后看T3，发现不可做

然后看T4，发现国集论文中讲过

然后很快建模

卧槽今天要 \(200\text{pts}\)？

比较得意，然后没管，估分 \(100+0+100=200\)

然后就是下午出分，满怀期待的一看，发现 \(200\text{pts}\) 那块并没有我

害，日常FST，然后往下看

恐怖的事情发生了，\(100\sim 200\text{pts}\) 那块也没有我

卧槽我nm怎么了

然后发现自己 \(55+0+0=55\)

开数据，发现自己T1忽略了几种情况，喜挂 \(45\)

然后T2状态压缩错了，正解是压链，我直接全给压了...

\(100\) 也没了

wdnmd，大E了，不讲武德

Day-3【题解】

忘记的题面名称

状态：Accepted | 难度：Easy-

简单题，赛时只写了 \(27\) 个串而喜提 \(55\text{pts}\)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 1000001
#define M 5001
#define INF 1100000000
#define Kafuu return
#define Chino 0
#define R register
#define C const
#define U unsigned
#define fx(l,n) inline l n
#define set(l,n,ty,len) memset(l,n,sizeof(ty)*len)
#define cpy(f,t,ty,len) memcpy(t,f,sizeof(ty)*len)
#define int long long
using namespace std;
fx(int,gi)(){
	R char c=getchar();R int s=0,f=1;
	while(c>'9'||c<'0'){
		if(c=='-') f=-f;
		c=getchar();
	}
	while(c<='9'&&c>='0') s=(s<<3)+(s<<1)+(c-'0'),c=getchar();
	return s*f;
}
char s[N];
int T,n,scl[N]={0,1,1,1,2,2,2,2,2,2,3,3,3,3,3,3,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,6,6},MAX=34,ans;
string sc[N]={"","a","b","c","ab","ac","ba","bc","ca","cb","abc","acb","bac","bca","cab","cba","abcba","acbca","bacab","bcacb","cabac","cbabc","abccba","acbbca","bcaacb","baccab","cabbac","cbaabc","aabbcc","aaccbb","bbccaa","bbaacc","ccbbaa","ccaabb"};
fx(int,solve)(int now){
	int point=0,sum=0;
	for(R int i=0;i<n;i++){
		if(s[i]==sc[now][point]) point+=1;
		if(point>=scl[now]) sum+=1,point=0;
	}
	return sum;
}
signed main(){
	T=gi();int bf=0;
	while(T--){
		n=gi();scanf("%s",s);ans=0;
		for(R int i=1;i<=MAX;i++) bf=solve(i),ans=max(ans,bf*bf*scl[i]);
		printf("%lld\n",ans);
	}
	return 0;
}

忘记的题目名称

状态：Accepted | 难度：Medium

状态压缩错了喜提 \(0\text{pts}\)

事实上，我们可以考虑一个球能不能被换到 \(1\) 号点，也就是说，我们从源点向每个球所代表的点连边，容量为 \(1\)

中间不断交换的过程即为对应的两个点进行连边，每次可以交换一个，容量依然为 \(1\)

而每个时刻，每个位置的球不会大于，并且也不会小于原来的数，于是我们将上一个阶段向此阶段连边，容量为 \(d_i\)

\(d_i\) 即为每个位置有的球

于是最后从最后一个阶段的一号点向终点连边，容量为 \(\infty\)

但是这样的点数过多，会被卡掉

我们很容易发现原图有很多地方都是以链的形式存在，于是我们只需要将其缩掉即可

这是一个容易的工作，用一个数组记录上次的位置即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 100001
#define M 3050
#define ST 10001
#define INF 1100000000
#define Kafuu return
#define Chino 0
#define R register
#define C const
#define U unsigned
#define fx(l,n) inline l n
#define set(l,n,ty,len) memset(l,n,sizeof(ty)*len)
#define cpy(f,t,ty,len) memcpy(t,f,sizeof(ty)*len)
#define int long long
using namespace std;
fx(int,gi)(){
	R char c=getchar();R int s=0,f=1;
	while(c>'9'||c<'0'){
		if(c=='-') f=-f;
		c=getchar();
	}
	while(c<='9'&&c>='0') s=(s<<3)+(s<<1)+(c-'0'),c=getchar();
	return s*f;
}
int num=1,head[N],dep[N],depn[N],s,t,T,n,m,d[N],u,v,cur[N],ednm[M][M],ans,up[N],node;
struct Edge{
	int na,np,fl;
}e[N];
fx(void,add)(int f,int t,int fl){
	e[++num].na=head[f];
	e[num].np=t;e[num].fl=fl;
	head[f]=num;
}
fx(void,pad)(int f,int t,int fl){
	add(f,t,fl);add(t,f,0);
}
queue<int>q;
fx(void,layer)(){
	set(dep,-1,dep,1);
	dep[t]=0;depn[0]=1;
	int f;q.push(t);
	while(!q.empty()){
		f=q.front();q.pop();
		for(int i=head[f];i;i=e[i].na){
			if(dep[e[i].np]==-1){
				dep[e[i].np]=dep[f]+1;
				depn[dep[e[i].np]]+=1;
				q.push(e[i].np);
			}
		}
	}
}
fx(int,pasi)(int now,int rf){
	if(now==t) return rf;
	int af=0,tf=0;
	for(int i=cur[now];i;i=e[i].na){
		cur[now]=i;
		if(!e[i].fl) continue;
		if(dep[e[i].np]==dep[now]-1){
			af=pasi(e[i].np,min(e[i].fl,rf));
			if(af){
				e[i].fl-=af;e[i^1].fl+=af;
				rf-=af,tf+=af;
			}
			if(!rf) return tf;
		}
	}
	depn[dep[now]]-=1;
	if(!depn[dep[now]]) dep[s]=2*t+1;
	depn[++dep[now]]++;
	return tf;
}
signed main(){
	T=gi();
	while(T--){//1-n,n+1-2n,2n+1,2n+2
		set(head,0,head,1);set(depn,0,depn,1);ans=0;num=1;
		n=gi(),m=gi();s=ST*2+1;t=s+1;
		for(R int i=1;i<=n;i++) d[i]=gi(),up[i]=i;
		for(R int i=1;i<=n;i++) pad(s,up[i],1);
		for(R int i=1;i<=m;i++){
			u=gi(),v=gi();
			pad(up[u],n+i*2-1,d[u]);
			pad(up[v],n+i*2,d[v]);
			pad(n+i*2-1,n+i*2,1);
			pad(n+i*2,n+i*2-1,1);
			up[u]=n+i*2-1,up[v]=n+i*2;
		}
		
		pad(up[1],t,d[1]);
		layer();
		while(dep[s]<2*t+1){
			cpy(head,cur,head,1);
			ans+=pasi(s,INF);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

忘记的题目名称

状态：Unaccepted | 难度：Hard

对于连通块分基环树和普通树分别处理，需要闵和然后维护凸包，然后不会了

不可做

Day-3【补题】

补题的题解并不放在这里，具体来说，它放在了题目泛刷记录3