526互联

ABC317 总结

发布时间 2023-09-07 21:21:05作者: Sonnety
点击查看目录

目录

ABC317

赛时总结：

A，好题，切了。

B，好题，切了。

C，我脑子有坑吧，我为什么不把 \(sum\) 传参，对着回溯 \(sum-=e[i].w\) 纠结还没调对，临考试结束 10min 切了。

D，看出来是背包 dp 了，不知道多少年没打背包了，妹切。

百度翻译就是歌姬吧
百度翻译就是歌姬吧
百度翻译就是歌姬吧
百度翻译就是歌姬吧
百度翻译就是歌姬吧
百度翻译就是歌姬吧
百度翻译就是歌姬吧
百度翻译就是歌姬吧
百度翻译就是歌姬吧
百度翻译就是歌姬吧
百度翻译就是歌姬吧
百度翻译就是歌姬吧
百度翻译就是歌姬吧
百度翻译就是歌姬吧

赛后总结：寄。

A Potions

luogu题链

Miku's Code 
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register int
typedef long long ll;
int Max(int x,int y)<%if(x<y)	return y;return x;%>
int Min(int x,int y)<%if(x<y)	return x;return y;%>
int Abs(int x)<%if(x<0)	return x*(-1);return x;%>
const int maxn=105;

int n,h,x,p[maxn];
int sum=0,cnt;

int main(){
	scanf("%d %d %d",&n,&h,&x);
	sum=h;
	for(rg i=1;i<=n;++i)	scanf("%d",&p[i]);
	for(rg i=1;i<=n;++i){
		sum+=p[i];
		if(sum>=x) <% cnt=i;break; %>
		else	sum-=p[i];
	} 
	printf("%d\n",cnt);
	return 0;
}

B MissingNo

luogu题链

Miku's Code 
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register int
typedef long long ll;
int Max(int x,int y)<%if(x<y)	return y;return x;%>
int Min(int x,int y)<%if(x<y)	return x;return y;%>
int Abs(int x)<%if(x<0)	return x*(-1);return x;%>
const int maxn=105;

int n,num[maxn],pos=-1;

int main(){
	scanf("%d",&n);
	for(rg i=1;i<=n;++i){
		scanf("%d",&num[i]);
	}
	sort(num+1,num+1+n);
	for(rg i=2;i<=n;++i){
		if(num[i]!=num[i-1]+1)	pos=num[i-1]+1;
	}
	printf("%d\n",pos);
	return 0;
}

C Remembering the Days

luogu题链

\(n\leq 10\)，DFS 搜索最大权值。

Miku's Code 
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register int
typedef long long ll;
int Max(int x,int y)<%if(x<y)	return y;return x;%>
int Min(int x,int y)<%if(x<y)	return x;return y;%>
int Abs(int x)<%if(x<0)	return x*(-1);return x;%>
const int maxn=15,maxm=50;

int n,m,dis,maxx;
bool vis[maxn],mj[maxn];
int head[maxm<<1],t;
#define next Miku
struct edge{
	int v,w;
	int next;
};edge e[maxm<<1];
il void add_edge(int u,int v,int w){
	e[++t].v=v;
	e[t].w=w;
	e[t].next=head[u];
	head[u]=t;
}

il void clear(){
	for(rg i=0;i<=maxn-1;++i){
		vis[i]=false;
	}
	maxx=Max(maxx,dis);
	dis=0;
}

il void dfs(int now,int sum){
	vis[now]=true;
	maxx=Max(maxx,sum);
	for(rg i=head[now];i;i=e[i].next){
		int to=e[i].v;
		if(vis[to]==true)	continue;
		dfs(to,sum+e[i].w);
	}
	vis[now]=false;
}

il void input(){
	scanf("%d %d",&n,&m);
	int a,b,c;
	for(rg i=1;i<=m;++i){
		scanf("%d %d %d",&a,&b,&c);
		add_edge(a,b,c);
		add_edge(b,a,c);
	}
}

int main(){
	input();
	for(rg i=1;i<=n;++i){
		dfs(i,0);
	}
	printf("%d\n",maxx);
	return 0;
}

D President

luogu题链

以席位为背包容量，其值在 \(\frac{\sum z_i}{2}+1\) 到 \(\sum z_i\) 时，高桥获胜，以转换支持者的选民为代价，做背包 dp 求最小代价即可。

Miku's Code 
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register int
typedef long long ll;
ll Max(ll x,ll y)<%if(x<y)	return y;return x;%>
ll Min(ll x,ll y)<%if(x<y)	return x;return y;%>
int Abs(int x)<%if(x<0)	return x*(-1);return x;%>
const int maxn=105;
const ll inf=200708310393939;

int n,x[maxn],y[maxn],z[maxn],maxtemp;
ll sum;
ll f[100050];

void work(){
	for(rg i=1;i<=sum;++i)	f[i]=inf;
	for(rg i=1;i<=n;++i){
		
		int w=Max(0,(x[i]+y[i])/2+1-x[i]);
		for(int j=sum;j>=z[i];--j){
			f[j]=Min(f[j],f[j-z[i]]+w);
		}
	}
}

il void input(){
	scanf("%d",&n);
	for(rg i=1;i<=n;++i)	scanf("%d %d %d",&x[i],&y[i],&z[i]),sum+=z[i];
}

int main(){
	input();
	work();
	ll ans=inf;
	for(rg i=sum/2+1;i<=sum;++i)	ans=Min(ans,f[i]);
	printf("%lld\n",ans);
	return 0;
}

E Avoid Eye Contact

luogu题链

将守卫能看到的位置标记，BFS 搜索即可。

Miku's Code 
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register int
typedef long long ll;
typedef pair<int,int> PII;
ll Max(ll x,ll y)<%if(x<y)	return y;return x;%>
ll Min(ll x,ll y)<%if(x<y)	return x;return y;%>
int Abs(int x)<%if(x<0)	return x*(-1);return x;%>
const int maxn=2050;

int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int h,w,stx,sty,tox,toy;
char s[maxn][maxn];
int ans[maxn][maxn];
bool vis[maxn][maxn];

il void bfs(){
	queue<PII> q;
	while(!q.empty())	q.pop();
	q.push(make_pair(stx,sty));
	while(!q.empty()){
		PII save=q.front();
		q.pop();
		for(rg i=0;i<4;++i){
			int xx=save.first+dx[i],yy=save.second+dy[i];
			if(xx>=1 && xx<=h && yy>=1 && yy<=w && s[xx][yy]!='#' && s[xx][yy]!='<' && s[xx][yy]!='>' && s[xx][yy]!='^' && s[xx][yy]!='v' && vis[xx][yy]==false && ans[xx][yy]==0){
				q.push(make_pair(xx,yy));
				ans[xx][yy]=ans[save.first][save.second]+1;
			}
		}
	}
}

il void work(){
	for(rg i=1;i<=h;++i){
		for(rg j=1;j<=w;++j){
			if(s[i][j]=='>'){
				int y=j+1;
				while((s[i][y]=='.' || vis[i][y]) && y<=w)	vis[i][y++]=true;
			}
			if(s[i][j]=='<'){
				int y=j-1;
				while((s[i][y]=='.' || vis[i][y]) && y>=1)	vis[i][y--]=true;
			}
			if(s[i][j]=='v'){
				int x=i+1;
				while((s[x][j]=='.' || vis[x][j]) && x<=h)	vis[x++][j]=true; 
			}
			if(s[i][j]=='^'){
				int x=i-1;
				while((s[x][j]=='.' || vis[x][j]) && x>=1)	vis[x--][j]=true;
			}
		}
	}
}

il void input(){
	scanf("%d %d",&h,&w);
	for(rg i=1;i<=h;++i){
		for(rg j=1;j<=w;++j){
			cin>>s[i][j];
			if(s[i][j]=='S')	stx=i,sty=j;
			if(s[i][j]=='G')	tox=i,toy=j;
		}
	}
}

int main(){
	input();
	work();
	bfs();
	if(ans[tox][toy])	printf("%d\n",ans[tox][toy]);
	else	printf("-1\n");
	return 0;
}

F Nim

luogu题链

（哈哈，你爹 10 维数位dp来咯）

亦或可以想二进制，所以数位 dp 填二进制数，或许这道题可以给一些启发：

XOR Triangle

对于亦或和为 \(0\)，这一位只有四种可能：\(000\)，\(110\)，\(011\)，\(101\)。

能填这些数的就直接转移过去，然后就得到答案了。

Miku's Code 
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define int long long
#define rg register int
typedef long double llf;
typedef long long ll;
typedef pair<int,int> PII;
const double eps=1e-8;
namespace io{
	#if ONLINE_JUDGE
	char in[1<<20],*p1=in,*p2=in;
	#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,1<<20,stdin),p1==p2)?EOF:*p1++)
	#endif
	il ll read(){
   		char c=getchar();
    	ll x=0,f=1;
   		while(c<48)<%if(c=='-')f=-1;c=getchar();%>
    	while(c>47)x=(x*10)+(c^48),c=getchar();
    	return x*f;
	}
	il void write(int x){
    	if(x<0)<%putchar('-');x=~x+1;%>
    	if(x>9) write(x/10);
   		putchar(x%10+'0');
	}
	il int ins(char *str){
	 	int len=0;
	  	while(1){
			char c=getchar();
			if(c!='\n' && c!='\0' && c!='\r')	str[++len]=c;
			else{
		    	break;
			}
	  	}
		return len;
	}
}

using namespace io;
int N,a1,a2,a3;
ll f[63][20][20][20][2][2][2][2][2][2];
vector<int> num;

il void pre(){
	N=read(),a1=read(),a2=read(),a3=read();
	while(N)	<% num.push_back(N&1);N=N>>1; %>
		for(rg A=0;A<=num.size();++A)
		for(rg P=0;P<=19;++P)
			for(rg j=0;j<=19;++j)
				for(rg F=0;F<=19;++F)
					for(rg e=0;e<=1;++e)
						for(rg n=0;n<=1;++n)
							for(rg g=0;g<=1;++g)
								for(rg c=0;c<=1;++c)
									for(rg _=0;_<=1;++_)
										for(rg __=0;__<=1;++__)
											f[A][P][j][F][e][n][g][c][_][__]=-1;
} 

ll dfs(int pos,int x,int y,int z,bool flag1,bool flag2,bool flag3,bool mj1,bool mj2,bool mj3){
//pos是当前进行至二进制第几位,x,y,z是当前数%a1,a2,a3,flag1,2,3是当前位是否贴上界,mj1,2,3是其二进制位上的数是否为1
	if(pos==-1){
		if(x==0 && y==0 && z==0 && mj1==true && mj2==true && mj3==true)	return 1;
		else	return 0;
	}
	if(~f[pos][x][y][z][flag1][flag2][flag3][mj1][mj2][mj3])	return f[pos][x][y][z][flag1][flag2][flag3][mj1][mj2][mj3]; 
	int res=dfs(pos-1,(x<<1)%a1,(y<<1)%a2,(z<<1)%a3,(flag1==true && (num[pos]==0)),(flag2==true && (num[pos]==0)),(flag3==true && (num[pos]==0)),mj1,mj2,mj3)%mod;
//	//新的一位上的二进制数数全取0 
	if((flag1==false || num[pos]==1) && (flag2==false || num[pos]==1))	res=(res+dfs(pos-1,(x<<1|1)%a1,(y<<1|1)%a2,(z<<1)%a3,flag1,flag2,(flag3==true && (num[pos]==0)),1,1,mj3))%mod;
	if((flag1==false || num[pos]==1) && (flag3==false || num[pos]==1))	res=(res+dfs(pos-1,(x<<1|1)%a1,(y<<1)%a2,(z<<1|1)%a3,flag1,(flag2==true && (num[pos]==0)),flag3,1,mj2,1))%mod;
	if((flag2==false || num[pos]==1) && (flag3==false || num[pos]==1))	res=(res+dfs(pos-1,(x<<1)%a1,(y<<1|1)%a2,(z<<1|1)%a3,(flag1==true && (num[pos]==0)),flag2,flag3,mj1,1,1))%mod;
	return f[pos][x][y][z][flag1][flag2][flag3][mj1][mj2][mj3]=res;
}

signed main(){
	pre();
	printf("%lld\n",dfs(num.size()-1,0,0,0,1,1,1,0,0,0));
	return 0;
}

G Rearranging

luogu题链

初学网络流。

网络流最大流

看了官方题解。

我们建立二分图的子集，左边的子集代表 \(1,\ldots,n\) 行，右边的子集代表 \(1,\ldots,n\) 个数，共 \(2n\) 个点，显然子集内点没有连边，它是二分图。

而该行内有哪些数就从左子集的代表行的点连向右子集代表数的点连边，有几个连几次。

如样例 #1：

input:

3 2
1 1
2 3
2 3

因此可以找一个图的最大匹配，对于某一列，我们就得到了其数，如#9999ff 色边，其为一列：

1
2
3

然后再删去已经找到过的边，继续找最大匹配，即可。

output:

Yes
1 1
3 2
2 3
Miku's code 
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register int
#define MYMAX 20070831
typedef long double llf;
typedef long long ll;
typedef pair<int,int> PII;
const double eps=1e-8;
#if ONLINE_JUDGE
char in[1<<20],*p1=in,*p2=in;
#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#endif
inline int read(){
	char c=getchar();
    int x=0,f=1;
    while(c<48)<%if(c=='-')f=-1;c=getchar();%>
    while(c>47)x=(x*10)+(c^48),c=getchar();
    return x*f;
}const int maxn=205,maxm=40050;

int now[maxm<<1],head[maxm<<1],tt=1;
#define next Miku
struct edge{
	int v,w,next;
};edge e[maxm<<1];
il void add_edge(int u,int v,int w){
	e[++tt].v=v;e[tt].w=w;e[tt].next=head[u];head[u]=tt;
	e[++tt].v=u;e[tt].w=0;e[tt].next=head[v];head[v]=tt;
}

int s,t,savt;
int n,m,dep[maxn],ans[maxn][maxn];

il void clear(){
	for(rg i=1;i<=(n<<1|1);++i)	dep[i]=0;
}

il bool bfs(){
	clear();
	queue<int> q;
	while(!q.empty())	q.pop();
	q.push(s);
	dep[s]=1;
	now[s]=head[s];
	while(!q.empty()){
		int x=q.front();q.pop();
		for(rg i=head[x];i;i=e[i].next){
			int to=e[i].v;
			if(e[i].w>0 && dep[to]==0){
				q.push(to);
				now[to]=head[to];
				dep[to]=dep[x]+1;
				if(to==t)	return true;
			}
		}
	}
	return false;
}

int dfs(int x,int flow){
	if(x==t)	return flow;
	int rest,res=0;
	for(rg i=head[x];i;i=e[i].next){
		int to=e[i].v;
		if(e[i].w>0 && dep[to]==dep[x]+1){
			rest=dfs(to,min(flow,e[i].w));
			if(rest==0)	dep[to]=0;
			e[i].w-=rest;
			e[i^1].w+=rest;
			res+=rest;
			flow-=rest;
		}
	}
	return res;
}

il int get_maxflow(){
	int ans=0;
	while(bfs())<% ans+=dfs(s,MYMAX); %>
	return ans;
}

il void input(){
	n=read(),m=read();
	t=(n<<1|1);
	int num;
	for(rg i=1;i<=n;++i){
		for(rg j=1;j<=m;++j){
			num=read();
			add_edge(i,n+num,1);
		}
	}
	savt=tt;
	for(rg i=1;i<=n;++i)<% add_edge(s,i,1);add_edge(n+i,t,1); %>
}

int main(){
	input();
	for(rg j=1;j<=m;++j){
		int flow=get_maxflow();
		if(flow!=n)	<% puts("No");return 0; %>
		for(rg i=3;i<=savt;i+=2){
		//网络流将匹配转为反边,枚举反边	
			if(e[i].w){
				int u=e[i].v,to=e[i^1].v;
//				cout<<"i="<<i<<"; u="<<u<<"; j="<<j<<"; to="<<to<<endl;
				ans[u][j]=to-n;
				e[i].w=0;
			}
		}
		for(rg i=savt+2;i<=tt;i+=2){
			if(e[i].w){
				e[i^1].w=1;
				e[i].w=0;
			}
		}
	}
	puts("Yes");
	for(rg i=1;i<=n;++i){
		for(rg j=1;j<=m;++j)	printf("%d ",ans[i][j]);
		putchar('\n');
	}
	return 0;
}

Ex Walk

luogu题链

洛谷没有翻译，我来胡一个（

翻译

题面翻译：

现有一个点编号为 \(1\) 到 \(N\) 的图，图中每条边满足：

  • 设这条边端点分别为 \(s\) 和 \(t\)，则 \(s\) 和 \(t\) 满足 \(0\leq t-s\leq 2\) 或者 \(t=1\)。

图中的一条边由 \(A,B,C,D\) 四个长度为 \(N\) 的序列表示，设 \(A_i\) 表示序列 \(A\) 的第 \(i\) 个元素，序列 \(B,C,D\) 同，有以下的含义：

  • 如果 \(A_i=1\)，则有点 \(i\) 有一条边连向它本身。

  • 如果 \(B_i=1\)，则有点 \(i\) 有一条边连向点 \(i+1\)。（保证 \(B_N=0\)）

  • 如果 \(C_i=1\)，则有点 \(i\) 有一条边连向点 \(i+2\)。（保证 \(C_{N-1}=C_N=0\)）

  • 如果 \(D_i=1\)，则有点 \(i\) 有一条边连向点 \(1\)。（保证 \(D_1=A_1\)）

对于给出的图，请输出长度为 \(K\) 的以 \(1\) 为起点，\(N\) 为终点的路径数量，答案对 \(998244353\) 取模。

\(2\leq N\leq 5\times 10^4,1\leq K\leq 5\times10^5\)。

\(A_i,B_i,C_i,D_i \in\{0,1\}\)。

给出的图中没有重边，但可能存在自环。

不会，求教教。