ABC317 总结

• A Potions
• B MissingNo
• C Remembering the Days
• D President
• E Avoid Eye Contact
• F Nim
• G Rearranging
• Ex Walk

#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;
} 

#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;
}

#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;
}

#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;
}

#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;
}

#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;
}

#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;
}

题面翻译：

现有一个点编号为 \(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\}\)。

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