首页 > 其他分享 >AtCoder比赛记录(一)

AtCoder比赛记录(一)

时间:2023-04-30 11:13:08浏览次数:55  
标签:AtCoder Medium 比赛 记录 int Solution Solved ... dp

这里记录的是这个账号的比赛情况。

ARC157

2023-2-25

Solved:4/6

2189->2216

C(Medium,1802)

给定一个XY矩阵,一条左上角到右下角的路径的分值定义为路径上连续两个Y的组数。求所有可能路径的分值的平方和。

Solution:经典DP。递推两个量,一个是到(i,j)所有路径的分值和\(f_{i,j}\),一个是平方和\(dp_{i,j}\)。递推式为

\[f_{i,j}=f_{i-1,j}+f_{i,j-1}+C(i+j-3,i-2)+C(i+j-3,j-2) \]

\[dp_{i,j}=dp_{i-1,j}+dp_{i,j-1}+(2 \times f_{i,j-1}+C(i+j-3,i-2))+(2 \times f_{i-1,j}+C(i+j-3,j-2)) \]

其中倒数第二项在\(a_{i,j}==a_{i-1,j}==Y\)是有效,倒数第一项在\(a_{i,j}==a_{i,j-1}==Y\)时有效。

D(Medium+,2435)

给定一个XY矩阵,用横线和竖线将矩阵分为若干块,使得每块内恰有2个Y。求方案数。

Solution:说到底是暴力。先求二维前缀和,然后枚举第一条横线,它以上的Y的数目是总数的约数。接着求出后面每条横线的可能位置。再枚举竖线,要求在每条横线的位置的值一定。最后求积就得到了这个横线位置的解数。细节很多。

AGC060

2022-12-25

Solved:3/6

Rank47!

2031->2189

A(Easy+,1345)

补全一个字符串,使得其任意一个子串中不存在一个字母出现次数超过一半。

Solution:容易分析出只需要对长为3的子串满足,然后DP。

B(Medium+,1996)

在 \(n \times m\) 的方格表中填入一些不超过 \(2^k-1\) 的数。考虑所有从左上角到右下角的最短路径,要求其中满足路径上数异或和为 \(0\) 的路径只有给定的 \(S\) 一条,问是否有解。

Solution

C(Hard,2680)

称一个长为 \(2^n-1\) 的排列 \(P\) 像堆,如果 \(P_i \lt P_{2i}\),且 \(P_i \lt P_{2i+1}\)。给定 \(a,b,u=2^a,v=2^{b+1}-1\),在所有像堆的排列中任取一个,求 \(P_u \lt P_v\) 的概率。

Solution

组合计数还是好做

ABC264

2022-8-13

Solved:7/8

Rank79!

Unrated

E(Medium-,1229)

给定\(n+m\)个点的无向图,其中后\(m\)个点为源点。给定\(q\)次删边操作,求每次操作后与源点联通的非源点数。

Solution:其实是套路题。倒序处理,化删边为连边,并查集维护,合并时尽可能向后。

F(Medium+.1878)

给定01矩阵及翻转各行各列的代价,求使得从左上角到右下角有同色通路的最小代价,这里通路只能向右或向下。

Solution:考虑DP,用\(dp[i][j][p][q]\)表示从左上角到达\((i,j)\)的最小代价,且此时第\(i\)行反转了\(p\)次,第\(j\)列反转了\(q\)次。显然只用考虑\(p,q \in \{0,1\}\)。

每个位置可以从上方或左方转移而来,必须有两个位置相同才能转移。计算代价时只考虑所扩展的行(列)。

点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2005;
int h,w,r[N],c[N],a[N][N];
char s[N];
ll dp[N][N][2][2];
int main(){
	scanf("%d%d",&h,&w);
	for(int i=1;i<=h;i++)scanf("%d",r+i);
	for(int i=1;i<=w;i++)scanf("%d",c+i);
	for(int i=1;i<=h;i++){
		scanf("%s",s+1);
		for(int j=1;j<=w;j++)
			a[i][j]=s[j]-'0';
	}
	memset(dp,0x3f,sizeof(dp));
	dp[1][1][0][0]=0;
	dp[1][1][1][0]=r[1];
	dp[1][1][1][1]=r[1]+c[1];
	dp[1][1][0][1]=c[1];
	for(int i=1;i<=h;i++)
		for(int j=1;j<=w;j++)
			for(int st=0;st<=15;st++){
				int p1=st&1,p2=(st>>1)&1,q1=(st>>2)&1,q2=(st>>3)&1;
				if(i!=1&&(a[i][j]^p2^q2)==(a[i-1][j]^p1^q1)&&q1==q2)
					dp[i][j][p2][q2]=min(dp[i][j][p2][q2],
								dp[i-1][j][p1][q1]+r[i]*p2);
				if(j!=1&&(a[i][j]^p2^q2)==(a[i][j-1]^p1^q1)&&p1==p2)
					dp[i][j][p2][q2]=min(dp[i][j][p2][q2],
								dp[i][j-1][p1][q1]+c[j]*q2);
			}
	printf("%lld\n",min(min(dp[h][w][0][0],dp[h][w][0][1]),
						min(dp[h][w][1][0],dp[h][w][1][1])));
	return 0;
}
G(Medium,2348)

给出\(n\)个长度不超过\(3\)的字符串,每个字符串有一个代价。对于一个字符串,定义其价值为给出的字符串在其中出现的次数与代价的乘积之和。对所有字符串,求价值最大值,或判断不存在。

Solution:还是比较显然的吧。

直接建图,每个结点是一个长为\(2\)的字符串,在两结点AB与BC间连有向边,边权为C,BC,ABC的代价之和。另建一个源点,向每个结点AB连边,代价为A,B,AB的代价之和。

从源点出发跑单源最长路,若有正环就无解。SPFA没死。

(大不合理,F的DP显然比G的建图难想)

ARC145

2022-7-30

Solved:4/6

1973->2031

A(Medium-,596)

给定长为\(n\)的AB字符串,可以将相邻两个改为AB,问是否能将原字符串变为回文串。

Solution:分类讨论题还不难首先特讨\(n=2\)。然后:

若开头为B,可以将中间全部改为A,末尾改为B

若开头不为B,结尾为B,无解;

若开头,结尾均为A,可以将第\(2\)个和第\(n-1\)个改为B,中间全为A

B(Easy,767)

两人取石子,先手取\(A\)的正数倍,后手取\(B\)的整数倍,这里\(A,B\)给定。求\(1,2,...,n\)中使先手获胜的初始石子数的个数。

Solution:策略显然:先手往死里取。若\(A \le B\),只要先手能取就必胜;否则,先手取完后少于\(B\)个即获胜。

C(Easy+,1697)

对于一个\(1,2,...,2n\)的排列,定义其分数为:将排列划分为两个等长的子序列,对应项乘积和的最大值。给定\(n\),求使得分数取最大值的排列数。

Solution:调整法易得最大值在\(1 \times 2 + 3 \times 4 + ... + (2n-1)\times 2n\)时取到,只用考虑每一对数的位置。选定左侧,则右侧必须顺次排列,转化一下就是卡特兰数。故答案为\(\frac{(2n)!}{(n+1)!} \times 2^n\)。

D(Medium+,2297)

构造满足以下条件的集合:集合中含\(n\)个\([-10^7,10^7]\)的整数,其和为\(m\),且不含等差子列。

Solution:FVMO牛逼!

MO原题:求证:可以找出\(1983\)个不超过\(10^5\)的正整数,其中不含等差子列。

原题证明:取三进制下只含数码\(0,1\)的数即可。

本题思路类似,前\(n-1\)个顺次取这样的数,最后一个大于前一个的两倍,然后使得总和模\(n\)与\(m\)同余,最后补上一个偏移量。

点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
typedef long long ll;
ll n,m,cnt,sum,ans[N],del;
bool check(ll x){
	while(x){
		if(x%3==2)return false;
		x/=3;
	}
	return true;
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;cnt<n-1;i++)
		if(check(i)){ans[++cnt]=i;sum+=i;}
	ll r=(m-sum)%n;
	ans[n]=(ans[n-1]*3+n)/n*n+r;
	del=(m-ans[n]-sum)/n;
	for(int i=1;i<=n;i++)
		printf("%lld\n",ans[i]+del);
	return 0;
}

ABC260

2022-7-17

Solved:7/8

Rank98!

1908->1973

E(Medium-,1692)

给定\(n\)个二元组,值域为\([1,m]\),求长度为\(k\),包含每个二元组中至少一个数的区间数目,这里\(k\)需取遍\(1,...,m\)。

Solution:考虑每个左端点,求出使其满足条件的最小右端点,用双指针。双指针时有一个方法:将所有数塞到一个数组中,维护出现的二元组数目。

若\([l,r]\)可行,则\([l,t],r \le t \le m\)可行,从而差分。最后求一次前缀和。

F(Medium,1995)

给定一个二分图,求其中是否有长为\(4\)的环。特殊限制:右部点数\(t \le 3000\)。

Solution:对每个右部点,从它出发走两步,如果两次走到同一个点则得到解。若没有走到,则每次时间为\(O(t)\),总时间不超过\(O(t^2)\)。

G(Medium+,2339)

给定一个\(n \times n\) 的OX矩阵和\(m\),给出\(q\)个询问\((x,y)\),求满足\(s \le x \le n,t \le y \le n,(x-s)+\frac{y-t}{2} \lt m\)且填O的点\((s,t)\)数目。

Solution:一个裸的模板题:二维斜向差分,和P8228类似。首先对斜率为\(\frac{1}{2}\)方向差分,对这个差分数组,再从横向和斜率\(\frac{1}{2}\)方向差分。对每个\(O\)转化一下,再求前缀和就可以了。(为什么又是差分)

说着不难,实际上还是有一些细节要处理的。

ABC258

2022-7-2

Solved:6/8

1864->1908

E(Medium-,1545)

给定周期为\(n\)的序列的一个周期,从第一个开始加和,和超过\(x\)就计一段。求第\(k\)段的长。

Solution:考虑从每个位置出发会到达哪里。用双指针。再由此建立段开头的周期即可。

G(Medium,1944)

给定一张图,求三角形数目。

Solution:枚举一条边,计算其两个端点所连点的集合之交的大小。用 bitset

ARC142

2022-6-19

Solved:3/6

1880->1864

B(Medium+,692)

构造 \(n \times n\) 的矩阵,填入从 \(1\) 开始的连续整数,使得对任意一格,其周围(八连通)比它大的个数和比它小的个数不相同。

Solution:首先,边界的格子有奇数个邻格,不用考虑。

其次,如果能保证每个格周围有至少 \(5\) 个格与其大小关系相同,就解决了题目。由此可以想到按照圈来填,外圈所填一定大于内圈。

如果 \(n\) 为奇数,直接让每一圈大小相间即可。如果 \(n\) 为偶数,先让角落处为该圈最大,然后让边角处连续,其它地方大小相间。倒数第二圈单独构造,可以完成。

题解的做法简单:按行考虑,每行大小交替,各行递减。

C(Medium,1347)

\(n\) 个点的树,可以询问除 \(1\) 和 \(2\) 之外任意两点间距离,要求用不超过 \(2n\) 次询问确定 \(1\) 和 \(2\) 的距离。

Solution:先找出所有与 \(1\) 相距 \(1\) 的点。若一个没有,则答案为 \(1\)。若至少两个,询问这两个与 \(2\) 的距离即可判断。

若恰有一个,询问这个与 \(2\) 的距离。若不为 \(2\),则 \(1\) 为叶子结点,直接确定。否则,对 \(2\) 重复上述操作,假如也没有确定,询问两次得到的点的间距即可。

ABC256

2022-6-18

Solved:6/8

1839->1880

ABC251

2022-5-14

Solved:6/8

1816->1839

D(Easy+,1463)

构造长不超过\(300\)的数列,使得\(1\)到\(10^6\)中的整数都可以从该数列中取出不超过三个做和得到。

Solution:需要一点想法。我的做法是按照进制的思想,数列包含\(1,2,...,99\),\(100,200,...,9900\),\(10000,20000,...,990000\).

F(Easy+,1703)

求给出的图中两棵生成树,其一满足以\(1\)为根时,图中非树边的端点有祖先关系,另一恰好相反。

Solution:第一棵树最直接的情况是一条链,所以尝试构造链,贪心地连边。也就是直接dfs,看到未加入生成树的点就连边。

第二棵树最直接的情况是一个菊花,所以dfs时遇到一个点就把它所有的边都加入生成树。

ABC242

2022-3-5

Solved:7/8

Rank89!(第一次进前100)

1711->1816

D(Easy,1286)

给定字符串\(S\),只包含\(A\),\(B\),\(C\),一次变换将\(A\)变为\(BC\),\(B\)变为\(CA\),\(C\)变为\(AB\)。求\(t\)次变换后第\(l\)个位置的字符。多组询问,\(t\),\(l\)在$ \ long \ long $范围内。

Solution:还是挺有意思的。

可以在模\(3\)意义下考虑。每一个位置变为它加\(1\)和它加\(2\)。二进制转一下就搞完了。

E(Easy,1365)

给定整数\(n\)及长为\(n\)的字符串\(S\),求满足\(X \le S\)的回文串\(X\)个数。

Solution:按位考虑,前\([\dfrac{n+1}{2}]\)位直接贪心,然后特判前一半全部一样的情况。

F(Medium+,2268)

在\(n \times m\)的棋盘上放置\(b\)个黑車和\(w\)个白車,求使得黑白之间互不攻击的放法数。

Solution:先考虑黑棋,设\(k\)个黑棋占据\(i\)行\(j\)列的方案数为\(dp[k][i][j]\)。这里把\(k\)作为阶段进行递推。

状态转移方程为

\[dp[k][i][j]=\dfrac{1}{k}((dp[k-1][i-1][j-1]+dp[k-1][i-1][j]+dp[k-1][i][j-1]) \times i \times j+dp[k-1][i][j] \times (i \times j-k+1)) \]

然后枚举黑棋占领的行列数,剩下的行列都可以放白棋。

预处理阶乘,阶乘逆元,逆元等。

点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,N=55,M=2505;
int n,m,b,w,fac[M],fac_inv[M],inv[M],dp[M][N][N],ans;
int power(int a,int b){
	int c=1;
	for(;b;b>>=1){
		if(b&1)c=1ll*c*a%mod;
		a=1ll*a*a%mod;
	}
	return c;
}
int C(int n,int m){
	if(n<m||n<0||m<0)return 0;
	return 1ll*fac[n]*fac_inv[m]%mod*fac_inv[n-m]%mod;
}
int main(){
	fac[0]=1;
	for(int i=1;i<=M-5;i++)fac[i]=1ll*i*fac[i-1]%mod;
	for(int i=0;i<=M-5;i++)fac_inv[i]=power(fac[i],mod-2);
	for(int i=1;i<=M-5;i++)inv[i]=power(i,mod-2);
	scanf("%d%d%d%d",&n,&m,&b,&w);
	dp[1][1][1]=1;
	for(int k=2;k<=n*m;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
				//if(i*j<=k)continue;
				dp[k][i][j]=(1ll*dp[k-1][i-1][j-1]*i*j%mod+1ll*dp[k-1][i-1][j]*i*j%mod+
							1ll*dp[k-1][i][j-1]*i*j%mod+1ll*dp[k-1][i][j]*(i*j-k+1)%mod)*inv[k]%mod;
			}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			ans=(ans+1ll*dp[b][i][j]*C(n,i)%mod*C(m,j)%mod*C((n-i)*(m-j),w)%mod)%mod;
	printf("%d\n",ans);
	return 0;
}

(闲话:该代码正好1024Byte)

G(Medium+,1828)

给出长为\(n\)的数组,求\([l,r]\)中的数能配成几对。多组询问。

Solution:没想出什么常规做法,于是写了莫队。

(其实是一开始把题目看成了P1494)

ABC240

2022-02-20

Solved:6/8

1691->1711

F(Easy+,1589)

以\(x_i\)个\(y_i\)的形式给出长为\(m\)的数列\(C\),数列\(B\)满足\(B_i=\sum_{k=1}^{i}C_k\),数列\(A\)满足\(A_i=\sum_{k=1}^{i}B_k\),求\(A\)中的最大项。

Solution:注意到\(B\)的每一段是单调的,那么可以找出每一段中正负交界出的点,考虑这些位置的\(A\)值即可。

G(Hard,2462)

从\((0,0,0)\)出发,每一步沿坐标轴方向移动一个单位长度,求用\(n\)步走到\((x,y,z)\)的方案数。

Solution:(搬运题解)

一维的情况非常简单,但这是此后的基础。记\(n\)步走到\(x\)的方案数为\(f_1{(n,x)}\)。

二维需要一点想法:将\((x,y)\)变换为\((x+y,x-y)\),那么移动就是从\((x,y)\)到\((x+1,y+1)\),\((x-1,y+1)\),\((x+1,y-1)\),\((x-1,y-1)\),这时就可以将横纵分开考虑,方案数为\(f_2{(n,x,y)}=f_1{(n,x+y)}\times f_1{(n,x-y)}\)。

三维时,枚举一下\(z\)方向就可以了。

ABC237

2022-01-30

Solved:6/8

1669->1691

F(Medium-,1857)

求长为\(n\),值域\([1,m]\),\(LIS\)长为\(3\)的整数列数目。

Solution:把\(LIS\)问题\(O(nlogn)\)算法中的另一个数组记录在状态中,直接推就可以了。

点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,m,dp[1005][12][12][12],ans;
int main(){
	scanf("%d%d",&n,&m);
	dp[0][m+1][m+1][m+1]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m+1;j++)
		for(int k=1;k<=m+1;k++)
		for(int l=1;l<=m+1;l++){
			if(j>k||k>l||j>l)continue;
			if(j==k&&k!=m+1)continue;
			if(k==l&&k!=m+1)continue;
			for(int c=1;c<=m;c++){
				if(c<=j)dp[i][c][k][l]=(dp[i][c][k][l]+dp[i-1][j][k][l])%mod;
		   		else if(c<=k)dp[i][j][c][l]=(dp[i][j][c][l]+dp[i-1][j][k][l])%mod;
		   		else if(c<=l)dp[i][j][k][c]=(dp[i][j][k][c]+dp[i-1][j][k][l])%mod;
			}
		}
	for(int j=1;j<=m;j++)
		for(int k=j+1;k<=m;k++)
			for(int l=k+1;l<=m;l++){
				ans=(ans+dp[n][j][k][l])%mod;
			}
	printf("%d\n",ans);
	return 0;
}

ARC134

2022-01-29

Solved:3/6

1646->1669

ABC234

2022-01-08

Solved:6/8

1636->1646

F(Medium-,1596)

给定字符串\(S\),求由\(S\)中字符的子集组成的字符串数。

Solution:用\(dp[i][j]\)表示用前\(i\)个字母组成长为\(j\)的字符串的方案数。

条件相当于是对每种字符使用次数做出了限制。

状态转移方程为

\[dp[i][j]=\sum_{k=0}^{min(cnt_i,j)}\frac{dp[i-1][j-k]}{k!} \]

直接推就好了。

G(Hard-,2306)

给定一个数列\(a\),将其分成若干段,求所有分法各段极差的积之和。

Solution:用\(dp[i]\)表示以\(i\)结尾的所有分法各段极差的积之和。

状态转移方程为

\[dp[i]=\sum_{j=0}^{i-1}dp[j] \times (max(j+1...i)-min(j+1...i)) \]

这样会T飞起来。考虑一下怎么优化它。

大致思路如下:先把乘积式拆成两块,以最大值为例。\(j+1...i\)的最大值就是\(max(max(j+1...i-1),i)\),加上最大值数组的单调性,可以使用一个栈去维护。每一次更新最大值序列时,该段的\(dp\)值所乘的系数加上同一个值,这样就可以用前缀和优化。那么就做到了线性复杂度。

这题的确是挺难的,赛时没做出来。

点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,mod=998244353,INF=1<<30;
struct rec{int l,r,val;};
int n,a[N],dp[N],s[N],sum,tmp,maxn,minn=INF;
stack<rec> MX,MN;
int main(){
	scanf("%d",&n);
	for(int i=2;i<=n+1;i++)scanf("%d",a+i);
	maxn=minn=a[2];
	s[1]=dp[1]=1;
	for(int i=2;i<=n+1;i++){
		maxn=max(maxn,a[i]);minn=min(minn,a[i]);
		tmp=i-1;
		while(!MX.empty()&&MX.top().val<=a[i]){
			rec tt=MX.top();tmp=tt.l;
			sum=(sum+1ll*(s[tt.r]-s[tt.l-1]+mod)%mod*(a[i]-tt.val))%mod;
			MX.pop();
		}
		MX.push(rec{tmp,i-1,a[i]});
		tmp=i-1;
		while(!MN.empty()&&MN.top().val>=a[i]){
			rec tt=MN.top();tmp=tt.l;
			sum=(sum+1ll*(s[tt.r]-s[tt.l-1]+mod)%mod*(tt.val-a[i]))%mod;
			MN.pop();
		}
		MN.push(rec{tmp,i-1,a[i]});
		dp[i]=sum;
		s[i]=(s[i-1]+dp[i])%mod;
	}
	printf("%d\n",dp[n+1]);
	return 0;
}

ABC233

2021-12-25

Solved:5/8

1677->1636

AGC056

2021-12-04

Solved:1/6

1589->1677

ABC230

2021-12-03

Solved:6/8

1406->1589

F(Medium+,2113)

给定数列\(a\),可以将相邻两项求和合并,求若干次操作后可能的结果数。

Solution:相当于在前缀和数列中删数。而前缀和数列与原数列是一一对应的。

于是就变成了只用求一个数列的不同子序列数。

使用动态规划,令\(dp[i]\)表示以第\(i\)个数开头的不同子序列数。

倒序扫描,遇到一个数时看一下它下一次在哪里出现,只用对两个位置之间的数在前面加前缀。

实时维护后缀和即可。

点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10,mod=998244353;
ll n,a,s[N],dp[N],b[N];
map<ll,vector<ll> > M;
map<ll,ll> pos;
int main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a);
		s[i]=s[i-1]+a;
		if(i!=n)M[s[i]].push_back(i);
	}
	for(int i=1;i<n;i++)pos[s[i]]++;
	b[n-1]=dp[n-1]=1;pos[s[n-1]]--;
	for(int i=n-2;i>=1;i--){
		int x=--pos[s[i]],y=n-1,f=1;
		if(x+1!=M[s[i]].size())y=M[s[i]][x+1],f=0;
		dp[i]=(b[i+1]-b[y+1]+f+mod)%mod;
		b[i]=(b[i+1]+dp[i])%mod;
	}
	printf("%lld\n",(b[1]+1)%mod);
	return 0;
}

(麻了,好神仙啊,我怎么想出来的)

ABC228

2021-11-20

Solved:4/8

1379->1406

ABC226

2021-11-07

Solved:6/8

1198->1379

F(Medium,2086)

一个\(1...n\)的排列\((p_1,p_2,...,p_n)\)的分数定义为:

开始时,第\(i\)个人拿着\(i\)号球。每一次操作,第\(i\)个人把手中的球传给第\(p_i\)个人。则分数就是所有人重新拿到自己的球的操作次数。

求\(1...n\)所有排列的分数的\(k\)次幂之和。

Solution:首先要明确所谓的“分数”。

对于一个排列\((p_1,p_2,...,p_n)\),构建一张图,从\(i\)向\(p_i\)连边。最后图中会形成若干个环,所有环长的最小公倍数就是这个排列的分数。这一点通过感性理解不难发现。

此时就可以考虑将\(n\)分拆为若干个数代表环长。注意到\(n \le 50\),所以可以执行一个dfs,从大到小分拆即可。

然后就是一些细节,比如平均分配,具体不细讲了。

G(Hard-,2373)

五种物品五种人,物品重量分1,2,3,4,5,人的力量分1,2,3,4,5,当人的力量不小于物品重量和时,人可以搬起这些物品。给定各种人数和物品数,问能否搬完。

Solution:(搬运题解)

贪心。先让人5搬物5,再让人4,5搬物4,然后让人3,4,5搬物3。接下来能搬2的人都再搬一个2。最后把1处理掉就可以了。

贪心的正确性证明比较麻烦,可以感性理解一下:1不用考虑,最后能放哪儿放哪儿;3,4,5每个人至多搬1个。于是就应该这么做。

还是挺需要想法的。

ABC225

2021-10-30

900->1198

Solved:5/8

E(Easy+,1678)

选择\(n\)个7中的一些放入坐标系内,要求从原点能看到所有选择的7。求最大数目。

Solution:就是区间合并,考虑每个7占用的斜率区间即可。

F(Hard,2612)

在\(n\)个字符串中选择\(k\)个首尾相连,求字典序最小的方案。

Solution:(搬运题解)

将给出的字符串记为\(S_1...S_n\),按照\(S_i+S_j<=S_j+S_i\)排序。

然后进行DP:用dp[i][j]表示从\(S_i...S_n\)中选出j个的最小字典序。则状态转移方程为:

\[dp[i][j]=min(dp[i+1][j],dp[i+1][j-1]+S_i) \]

此处省略一系列正确性证明。

ABC219

2021-09-18

944->900

Solved:3/8

ABC216

2021-08-29

317->944

Solved:7/8

F(Medium-,1541)

给定数列\(\{a_n\}\),\(\{b_n\}\),求集合$S \subseteq {1,2,...,n} \(的个数,使得\)\max_{i \in S}{a_i} \ge \sum_{i \in S}{b_i}$。

Solution:先将\(a\)排序,从小到大枚举\(\max_{i \in S}{a_i}\)。设这是排序后第\(k\)个。

假设已经确定了这个值,那么问题变为在\(b_1,b_2,...,b_k\)中选出若干个,其和不超过\(\max_{i \in S}{a_i}\)。这只需要记忆化搜索就可以了。

G(Medium-,1963)

构造01数列,使得在给定区间内至少有给定数目的1,且1的个数最少。

Solution:对于每一个区间,将需要安放的1尽可能向后放,用贪心算法容易知道这是正确的。

详言之,先将所有区间以右端点为第一关键字排序,用树状数组维护01序列,依次扫描每个区间,算出它还需要几个1,全部放在最末尾即可。

ABC215

2021-08-21

24->317

Solved:4/8

ABC204

2021-06-06

0->24

Solved:2/6

标签:AtCoder,Medium,比赛,记录,int,Solution,Solved,...,dp
From: https://www.cnblogs.com/by-chance/p/17365031.html

相关文章

  • AtCoder比赛记录(二)
    这里记录的是这个账号的比赛情况。ABC3002023-4-29Solved:7/80->1200F(Medium-,1846)给定由o和x组成的字符串\(S\)。将\(S\)复制\(m\)遍,然后将其中\(k\)个x改成o,求改完之后连续的o最多可能有多少个。Solution:贪心。设最多能改完\(t\)个完整的\(S\),考虑三类情况:最长连续......
  • SAP 简单采购会计凭证记录
    ME21NMIROMIGO清帐 查看会凭证        ......
  • 记录一下MAX在动画制作中遇到文件大小无限膨胀的BUG
    最新在用MAX的biped骨骼做动画,一个简单的角色动画,用到了运动混合器,随着项目的推进,诡异的事情开始出现,文件变得无比庞大,但文件内都是链接,模型面数也不到1w,但文件大小却膨胀到了300多MB这使得打开和保存变得无比慢,但是用首选项里的“压缩保存的文件”选项却可以把工程文件压缩到4MB......
  • SAP 简单采购会计凭证记录
     ME21NMIGOMIRO    ......
  • 记录一下想法而已
    数据驱动下的图书馆服务变化1、个人认知下基本背景图书馆的基本数据为图书,读者和借还日志,在1995年开始,图书馆开始部署自动化图书管理系统,2000年左右,随着计算机和网络的普及,大多数图书馆完成了此项工作。由于ILAS底层不是通用数据库,在统计方面有不足,基本的采编典流期刊业务处......
  • [练习记录] 《算法竞赛进阶指南》打卡活动
    89.a^b题目大意给\(a,b,p\)求\(a^b\modp\)。思路可以直接快速幂。当模数\(p\)为\(1\)的时候特判一下。代码lla,b,mod;llqpow(lla,llb){ llres=1; while(b){ if(b&1)res=res*a%mod; a=a*a%mod,b>>=1; } returnres;}in......
  • AtCoder Regular Contest 116 F Deque Game
    洛谷传送门AtCoder传送门很强的博弈+性质题。下文令A为Takahashi,B为Aoki。发现单独考虑一个序列\(a_1,a_2,...,a_n\):若\(n\bmod2=0\):若A为先手,答案为\(\max(a_{\frac{n}{2}},a_{\frac{n}{2}+1})\);若B为先手,答案为\(\min(a_{\frac{n}{2}},a_{\frac......
  • AtCoder Regular Contest 123 E Training
    洛谷传送门AtCoder传送门不妨假设\(B_X\leB_Y\)。设\(f(x)=A_X+\frac{x}{B_X},g(x)=A_Y+\frac{x}{B_Y},F(x)=\left\lfloor{f(x)}\right\rfloor,G(x)=\left\lfloor{g(x)}\right\rfloor\),题目即求\(\sum\limits_{x=1}^n[F(x)=G(x)]\)。我一开始尝试化简......
  • 记录-做一个文件拖动到文件夹的效果
    这里给大家分享我在网上总结出来的一些知识,希望对大家有所帮助在我的电脑中,回想一下我们想要把一个文件拖动到另一个文件夹是什么样子的呢1:鼠标抓起文件2:拖动文件到文件夹上方3:文件夹高亮,表示到达指定位置4:松开鼠标将文件夹放入文件下面就来一步步实现它吧......
  • 记录一下linux-kafka命令
    使用工具:puTTY下载地址:DownloadPuTTY-afreeSSHandtelnetclientforWindowsloginas:rootroot@*******'spassword:Lastlogin:FriApr2814:54:262023from10.10.16.80[root@kafka272c41~]#cd..[root@kafka272c41/]#ls-a....autorelabelbinboot......