首页 > 其他分享 >AtCoder Beginner Contest 387 赛后复盘

AtCoder Beginner Contest 387 赛后复盘

时间：2025-01-04 22:24:21浏览次数：1  
标签：AtCoder Beginner Contest int res read maxn mod define

省流：A，B，C，D，F

image

A - B

模拟即可。

C

数位 dp。

首先我们先将问题转换为 \([1,R]\) 中蛇数的个数减去 \([1,L-1]\) 中蛇数的个数。
设 \(num_i\) 为数字的第 \(i\) 位（从左往右数）。
我们设 \(f_{dep,mx,lim,ze}\) 表示当前第 \(dep\) 位，首位为 \(mx\)，有没有达到上限，有没有前导零。

那么每一次向下搜索，当枚举当前位是 \(i\) 时，我们分类讨论。

要么就是有前导零，此时这一位为首位，那么 \(f_{dep,mx,lim,ze} \leftarrow f_{dep-1,i,lim\operatorname{and} [i=num_{dep}],ze \operatorname{and} [i=0]}\)。
要么就是没有前导零，此时只有 \(i<mx\) 才可以向下搜。那么 \(f_{dep,mx,lim,ze} \leftarrow f_{dep-1,mx,lim\operatorname{and} [i=num_{dep}],0}\)。

要记忆化搜索，数位 dp 的时间复杂度才是对的。

点击查看代码 
#include<bits/stdc++.h>

#define int ll
#define ll long long
#define i128 __int128

#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define m1(a) memset(a,-1,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define fst first 
#define scd second 
#define dbg puts("IAKIOI")

using namespace std;

int read() {
	int x=0,f=1; char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) f=(c=='-'?-1:1); 
	for(;c<='9'&&c>='0';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	return x*f;
}
void write(int x) { if(x>=10) write(x/10); putchar('0'+x%10); }

const int mod = 998244353;
int qpo(int a,int b) {int res=1; for(;b;b>>=1,a=(a*a)%mod) if(b&1) res=res*a%mod; return res; }
int inv(int a) {return qpo(a,mod-2); }

#define maxn 200050

int l,r;

int f[21][11][2][2];//位数，首位数，上限，前导零
int num[21],top;

int dfs(int dep,int mx,int lim,int ze) {
	if(!dep) return 1;
	if(f[dep][mx][lim][ze]!=-1) return f[dep][mx][lim][ze];
	int res=0;
	For(i,0,9) if((!lim)||i<=num[dep]) {
		if(ze) res+=dfs(dep-1,i,((i==num[dep])&&lim),((i==0)&&ze));
		else if(i<mx) res+=dfs(dep-1,mx,((i==num[dep])&&lim),0);
	}
	return f[dep][mx][lim][ze]=res;
}

int work(int x) {
	m1(f);
	m0(num);
	top=0;
	while(x) {
		num[++top]=x%10;
		x/=10;
	}
	if(top<=1) return num[1]+1;
	return dfs(top,10,1,1);
}

signed main() {
//	ios::sync_with_stdio(false); 
//	cin.tie(0); cout.tie(0);
//	int _=1;
//	_=read();
	cin>>l>>r;
	cout<<work(r)-work(l-1);
	return 0;
}

D

简单搜索。

我们对于每一个点额外记录一维表示转移过来是竖着还是横着，剩下就是 bfs 了。

点击查看代码 
#include<bits/stdc++.h>

#define ll long long
#define i128 __int128

#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define m1(a) memset(a,-1,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define fst first 
#define scd second 
#define dbg puts("IAKIOI")

using namespace std;

int read() {
	int x=0,f=1; char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) f=(c=='-'?-1:1); 
	for(;c<='9'&&c>='0';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	return x*f;
}
void write(int x) { if(x>=10) write(x/10); putchar('0'+x%10); }

const int mod = 998244353;
int qpo(int a,int b) {int res=1; for(;b;b>>=1,a=(a*a)%mod) if(b&1) res=res*a%mod; return res; }
int inv(int a) {return qpo(a,mod-2); }

#define maxn 1050

bool vis[2][maxn][maxn];

int h,w;
char mp[maxn][maxn];
int sx,sy,ex,ey;

int dx[5]={0,1,-1,0,0},dy[5]={0,0,0,1,-1};

struct node {
	int a,b,c,d;
};

void work() {
	cin>>h>>w;
	For(i,1,h) For(j,1,w) {
		cin>>mp[i][j];
		if(mp[i][j]=='S')
			sx=i,sy=j;
		if(mp[i][j]=='G')
			ex=i,ey=j;
	}
	queue<node>q;
	q.push({sx,sy,0,1});
	q.push({sx,sy,0,2});
	while(!q.empty()) {
		auto [x,y,cnt,flg]=q.front();
		q.pop();
		if(vis[flg-1][x][y]) continue;
		vis[flg-1][x][y]=1;
		if(x==ex&&y==ey) return cout<<cnt,void();
		For(i,1,4) if((i+1)/2!=flg) {
			int X=x+dx[i],Y=y+dy[i];
			if(X>0&&X<=h&&Y>0&&Y<=w&&mp[X][Y]!='#'&&!vis[((i+1)/2)-1][X][Y]) 
				q.push({X,Y,cnt+1,(i+1)/2});
		}
	}
	cout<<-1;
}

signed main() {
	ios::sync_with_stdio(false); 
	cin.tie(0); cout.tie(0);
	int _=1;
//	_=read();
	For(i,1,_) {
		work();
	}
	return 0;
}

F

你是一名 OIer。你在打 abc387 的时候看到了这道题。
你并不会 E，所以你打算死磕 F。

你发现这个大小关系可以转换成图论的连边，然后再跑 dp 就好了。
你发现如果图上有环的话，那么环上的数都相等。于是你立马想到了缩点。
你立马敲完了 Tarjan 缩点，虽然你随后发现这张图一定是基环树森林，所以只需要跑拓扑就可以缩点了。

然后就是 dp。
你设 \(f_{i,j}\) 表示第 \(i\) 个点的值为 \(j\) 时的情况总数，那么初始情况就是 \(f_{i,j}=1(i\in[1,n],j\in[1,m])\)。
然后你列出了转移方程，当 \(u,v\) 想连时：\(f_{u,i}=\sum_{j=1}^{m} f_{u,j}\)。
你发现这个 dp 是 \(O(nm^2)\) 的，过不了。
就在你要丧失信心时，你突然发现 dp 的 \(\sum_{j=1}^{m} f_{u,j}\) 可以用前缀和优化。

你迅速的打完了这个优化，又突然发现你不会统计方案。
你发现由于每个点只有一条出边，所以这个图形最后只会是一条条链，那么你需要的答案就是链的终点的所有值之和，用乘法原理计算即可。

这是你的代码：

点击查看代码 
#include<bits/stdc++.h>

#define int ll
#define ll long long
#define i128 __int128

#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define m1(a) memset(a,-1,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define fst first 
#define scd second 
#define dbg puts("IAKIOI")

using namespace std;

int read() {
	int x=0,f=1; char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) f=(c=='-'?-1:1); 
	for(;c<='9'&&c>='0';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	return x*f;
}
void write(int x) { if(x>=10) write(x/10); putchar('0'+x%10); }

const int mod = 998244353;
int qpo(int a,int b) {int res=1; for(;b;b>>=1,a=(a*a)%mod) if(b&1) res=res*a%mod; return res; }
int inv(int a) {return qpo(a,mod-2); }

#define maxn 2250

int n,m;
int a[maxn];

vector<int> G[maxn];
int dfn[maxn],dfncnt,low[maxn];
int stk[maxn],stktop;
bool instk[maxn];

int bel[maxn],belcnt;

void Tarjan(int u) {
	low[u]=dfn[u]=++dfncnt;
	instk[(stk[++stktop]=u)]=1;
	for(auto v:G[u]) {
		if(!dfn[v]) Tarjan(v),low[u]=min(low[u],low[v]);
		else if(instk[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]) {
		belcnt++;
		while(1) {
			int v=stk[stktop--];
			instk[v]=0;
			bel[v]=belcnt;
			if(u==v) break;
		}
	}
}

int deg[maxn];
int f[maxn][maxn];

void work() {
	in2(n,m);
	For(i,1,n) {
		in1(a[i]);
		G[i].push_back(a[i]);
	}
	For(i,1,n) if(!dfn[i]) Tarjan(i);
	For(i,1,n) G[i].clear();
	For(i,1,n) if(bel[i]!=bel[a[i]]) G[bel[i]].push_back(bel[a[i]]),deg[bel[a[i]]]++;
	queue<int> q;
	For(i,1,belcnt) if(!deg[i]) q.push(i);
	For(i,1,belcnt) For(j,1,m) f[i][j]=1;
	int ans=1;
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		For(i,1,m) (f[u][i]+=f[u][i-1])%=mod;
		if(G[u].size()==0) (ans*=f[u][m])%=mod;
		for(auto v:G[u]) {
			deg[v]--;
			For(i,1,m) (f[v][i]*=f[u][i])%=mod;
			if(deg[v]==0) q.push(v);
		}
	}
	cout<<ans;
}

signed main() {
//	ios::sync_with_stdio(false); 
//	cin.tie(0); cout.tie(0);
	int _=1;
//	_=read();
	For(i,1,_) {
		work();
	}
	return 0;
}

你交了上去，并获得了 550pts，这使得你的排名暴涨。

你笑了出来，笑着笑着，你感觉眼前一阵眩晕。同时有一个熟悉的声音呼唤着你：“起床了”。
你醒了，看到了旁边把你摇醒的同学，指了指台上的道法老师。
原来这一切都只是上道法课时的睡觉的幻想罢了。

标签：AtCoder,Beginner,Contest,int,res,read,maxn,mod,define
From： https://www.cnblogs.com/CodingGoat/p/18652570

相关文章

  • AtCoder Regular Contest 065
    \(AT\_arc065\_a\)https://www.luogu.com.cn/problem/solution/AT_arc065_a题解：在读到\(d\)或\(e\)时判断是不是\(dream,dreamer,erase,eraser\)即可。注意\(dreamer\)和\(erase,eraser\)有重叠，于是在\(d\)时要特判，具体见代码。#include<bits/stdc++.h>usingnamespacestd......
  • 题解：AtCoder [ARC176D] Swap Permutation
    题意原题链接给定一个长度为\(n\)的排列\(p\)，并执行以下操作\(m\)次：选择\(1\leqi<j\leqn\)，交换\(p_i\)和\(p_j\)。定义一个序列\(p\)的权值为\(\sum_{i=1}^{n-1}|p_i-p_{i-1}|\)。求在\(\binom{n}{2}^m\)种可能的操作后，\(p\)的价值之和。答案对\(998244353\)......
  • AtCoder Beginner Contest 386 补题
    E-MaximizeXOR题目大意给出\(n\)个数，要选\(k\)个使异或和最大。\(n\leq2\times10^5,k\leqn\)\(C_n^k\leq10^6\)思路由于那个组合数的性质，发现应该是直接深搜就可以的。可是发现T了。发现如果\(k\)很大那么还是不好处理。但是发现搜\(k\)个数和搜\(n-k\)个......
  • 关于此题E - Maximize XOR（Atcoder ABC 386）搜索技巧的一些总结
    传送门题目要求n个数中选k个数异或起来最大，我们想到字典树中最大异或和这一经典问题，但是很明显字典树只能解决任选两个数的最大异或，而此题是任选k个，那我们走投无路只能考虑爆搜。首先可以很容易写出一个暴力的搜索：voiddfs1(longlongpos,longlongsum,longlongkk){i......
  • AtCoder Beginner Contest 386（补题）
    AtCoderBeginnerContest386C-Operate1https://atcoder.jp/contests/abc386/tasks/abc386_c思路简单的条件判断题代码#include<bits/stdc++.h>typedefstd::pair<int,int>pii;#defineINF0x3f3f3f3f#defineMOD998244353usingi64=longlong;cons......
  • atcoder ABC385 部分题解
    G-CountingBuildings简要题义一个排列的\(L(P)\)为\(\sum_{i=1}^n[premax(i)=P_i]\)，即前缀最大值为自身的位置数，\(R(P)\)同理为后缀最大值。有多少个排列使得\(L(P)-R(P)=k\)题解假设\(n,k\)是同阶的。我们从\(n\)到\(1\)依次插入数，考虑朴素的DP：设\(f_{i,k......
  • AtCoder Beginner Contest 386 赛后总结
    赛时A-D。菜。A-C模拟即可。D先检查一下竖着的一列有没有出现：白黑或者黑白黑的情况。有的话一定不行。因为每个白点的右下角一定都得是白的，就相当于对下面的行数取后缀最小值，这个可以使用差分实现。点击查看代码#include<bits/stdc++.h>#definelllonglong#def......
  • [题解]（更新中）AtCoder Beginner Contest 386(ABC386) A~E
    A-FullHouse2容易发现，答案为Yes\(\iff\)输入中恰好出现了\(2\)种不同的数，可以用set等数据结构来计算不同元素的个数。点击查看代码#include<bits/stdc++.h>usingnamespacestd;set<int>se;signedmain(){ for(inti=1,a;i<=4;i++){ cin>>a; se.insert(a); } c......
  • AtCoder DP Contest(刷题记录)
    A-Frog1题意:给定\(n\)个石头，第\(i\)个石头的高度为\(h_i\).现在要求小青蛙从\(1\)号石头跳到\(n\)号石头，每次小青蛙可以选择从\(i\)号石头跳到\(i+1\)或\(i+2\)号石头，代价是起跳点与落点的高度差的绝对值。询问你最小代价。解法:\(dp[i]\)表示小青蛙跳到第号石头时的最小代......
  • AtCoder Regular Contests
    \[\begin{matrix}\color{#d9d9d9}\blacksquare\color{#D9C5B2}\blacksquare\color{#B2D9B2}\blacksquare\color{#B2ECEC}\blacksquare\color{#B2B2FF}\blacksquare\color{#ECECB2}\blacksquare\color{#FFD9B2}\blacksquare\color{#FFB2B2}\blacksqu......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99