首页 > 其他分享 >Edu Round 170 Review

Edu Round 170 Review

时间：2024-10-18 17:43:19浏览次数：1  
标签：int Review Round while ans MOD void dp 170

Edu Round 170 Review

A

分析

一个很显然的根据前缀划分的贪心，直接指针模拟就好了。

Code

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		string a,b;
		cin>>a>>b;
		int l1=a.length(),l2=b.length();
		int p=0;
		while(p<l1&&p<l2&&a[p]==b[p])p++;
		if(p>0)p--;
		cout<<l1+l2-p<<'\n';
	}

}

B

分析

打表就发现需要输出的就是 \(2^n\) ，然而这道题我卡了十多分钟，实在是有点sb了。

具体证明的话可以用数学归纳法，也可以直接证明，都是比较容易的。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=1e9+7;
inline int power(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1)ans=ans*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return ans%MOD; 
}
const int N=2e5+1;
int t,n[N],k[N];
inline void solve()
{
	cin>>t;
	for(int i=1;i<=t;++i)scanf("%d",&n[i]);
	for(int i=1;i<=t;++i)scanf("%d",&k[i]),printf("%lld\n",power(2,k[i]));
}
signed main()
{
	solve();
}

C

分析

其实思路上面很简单，只需要以每个数为开头贪心地连续去选择尽可能多的数字就可以了。

注意这样做是 \(O(n^2)\) 的，那么考虑如何在枚举的时候快速地从现在的答案推知下一个答案。

很容易想到一个简化的莫队，从 \([l,r]\) 到 \([l+1,r+1]\) ，实际上只是增加了一个数，去除了一个数而已，通过增量就可以计算出来。

边界写错了吃了两发罚时（实际上可以不需要去重的，所以说本人的找屎能力真的强）。

又成功地在模拟题上面写出了一道屎山代码。。。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>inline void re(T &x)
{
	x=0;int f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	x*=f;
}
template<typename T>inline void wr(T x)
{
	if(x>9)wr(x/10);
	putchar(x%10^48);
}
int t,n,k,a[200010];
pair<int,int>b[200010];
inline void solve()
{
	re(n),re(k);
	for(register int i=1;i<=n;++i)re(a[i]);
	sort(a+1,a+n+1);a[n+1]=0;
	int cnt=1,p=0;
	for(register int i=1;i<=n;++i)
	{
		if(a[i]!=a[i+1])
		{
			b[++p].first=a[i];
			b[p].second=cnt;
			cnt=1;
		}
		else cnt++;
	}
	int ans=-1,lasl=0,lasr=0;
	int lasans=0;
	for(register int i=1;i<=p;++i)
	{
		if(!lasans)
		{
			int p1=i+1;lasans=b[i].second;
			while(p1<=p&&p1-i+1<=k&&b[p1].first-b[p1-1].first==1)lasans+=b[p1++].second;
			ans=max(ans,lasans),lasl=i,lasr=p1-1;
		}
		else
		{
			int nowr=lasr+i-lasl;
			if(b[nowr].first-b[nowr-1].first!=1||nowr>p)
			{
				i=nowr-1;
				lasans=lasl=lasr=0;
				continue;
			}
			lasans-=b[i-1].second,lasans+=b[nowr].second;
			ans=max(ans,lasans);
		}
	}
	wr(ans),putchar('\n');
}
signed main()
{
	re(t);
	while(t--)
		solve();
	return 0;
}

D

分析

因为实现能力太差，C做了一个小时，导致D只有不到二十分钟的时间了，大概扫过去想了一个很骚的做法，就是倒叙枚举然后贪心地选择贡献即可，结果发现题看错了。。。

这种涉及到抉择的题发现贪心是假的，那肯定就是DP了。

那其实阶段和状态也很容易设计出来。

定义 \(dp[i][j]\) 为前 \(i\) 个数字 选择了 \(j\) 点智力加点能够获得的分数（注意此时体力的加点一定是唯一确定的，因此我们没有必要单独开一维来单独记录，前提是我们需要统计出来一个数组来记录任意某个位置 \(pos\) 之前一共出现了多少个 \(0\) ） 。

那么转移方程也非常的水到渠成：

如果 \(a_i=0\) ，那么所有的 \(dp[i][j]=\max(dp[i-1][j],dp[i-1][j-1])\)

如果 \(a_i>0\) ，那么所有的 \(dp[i][j](j\ge a_i)=dp[i-1][j]+1\)

如果 \(a_i<0\) ，那么所有的 \(dp[i][j](j\le sum0-(-a_i))=dp[i-1][j]+1\)

注意到我们会多次执行区间加的操作，实际上你可以写一个线段树，或者是树状数组，然而都太麻烦或者不好实现（对我来说）。

我们可以直接采用差分数组，但是缺陷就在于，虽然可以多次进行区间加法，但是一只能统计一次。观察到这道题 \(m\) 的数据范围非常小，所以每次遇到一个 \(0\) 之前，我们就暴力地统计一遍差分数组，然后加到 \(dp\) 数组里面，而后进行 \(0\) 处该进行的转移，再把差分数组清零，重新进行后续的区间加操作即可。

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void re(T &x)
{
	x=0;int f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	x*=f;
}
template<typename T>inline void wr(T x)
{
	if(x>9)wr(x/10);
	putchar(x%10^48);
} 
const int N=2e6+100;
int a[N],dp[5010];
int n,m;
int s[5010];
inline void add(int l,int r,int v)
{
	s[l]+=v,s[r+1]-=v;
}
inline void	calcsum()
{
	for(int i=1;i<=m;++i)
		s[i]+=s[i-1];
	for(int i=0;i<=m;++i)
		dp[i]+=s[i],s[i]=0;
}	
inline void pre()
{
	re(n),re(m);
	for(register int i=1;i<=n;++i)re(a[i]);
}
inline void solve()
{
	int sum0=0;
	for(register int i=1;i<=n;++i)
	{
		if(a[i]==0)
		{
			calcsum();
			for(register int j=++sum0;j>=1;--j)
				dp[j]=max(dp[j],dp[j-1]);	
		}
		else if(a[i]>0)
		{
			if(sum0<a[i])continue;
			add(a[i],sum0,1);
		}
		else
		{
			if(sum0<abs(a[i]))continue;
			add(0,sum0+a[i],1);					
		}
	}
	calcsum();
	int ans=-1;
	for(register int i=0;i<=m;++i)ans=max(ans,dp[i]);
	wr(ans);
}
int main()
{
	pre();
	solve();
	return 0;
}
/*
dp[i][j] 前i个数字  拥有 j 点智力可以获得的分数

all dp[i][j]=dp[i-1][j];
if(0)
	dp[i][j]=max dp[i][j],dp[i-1][j-1];
if(+)
	dp[i][j]=add(a[i],sum0[i],1);
if(-)  
	dp[i][j]=add(0,sum0[i]+a[i],1);
	
写的时候的问题：
	前缀和之后没有给dp 0加上去
	统计差分 和 进行 O(m) 转移的顺序搞反了  
*/

E

非常好的一道计数题，让我“温习“了一下在高二的时候学习过的卡特兰数。

前置知识

卡特兰数

定义背景

由于这一类组合数对于实际问题有意义，所以才会被单独讨论，它适用于如下情况：

  1. 有 \(n\) 个人排成一行进入剧场。入场费 5 元。其中只有个 \(n\) 人有一张 5 元钞票，另外人 \(n\) 只有 10 元钞票，剧院无其它钞票，问有多少种方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？
  2. 有一个大小为 \(n\times n\) 的方格图开始每次都只能向右或者向上走一单位，不走到对角线上方（但可以触碰）的情况下到达右上角有多少可能的路径？
  3. 在圆上选择 \(2n\) 个点，将这些点成对连接起来使得所得到的条 \(n\) 线段不相交的方法数？
  4. 对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数？
  5. 一个栈（无穷大）的进栈序列为 \(1-n\) 有多少个不同的出栈序列？
  6. \(n\) 个结点可构造多少个不同的二叉树？
  7. 由 \(n\) 个\(+-1\) 组成的序列，满足任意前缀和非负，有多少种构造方案?

公式

  1. \(H_n=\frac{C_{2n}^{n}}{n+1}\)

  2. \(H_n=C_{2n}^n-C_{2n}{n-1}\)

  3. \(H_n=H_{n-1}\times \frac{4n-2}{n+1}\)

  4. DP的方式求（卡特兰数实际上是一个匹配的过程）

    定义 \(f_{i,j}\) 为，前 \(i\) 个数，剩下了 \(j\) 个没有匹配的方案数，那么最后的答案就是 \(f_{2n,0}\)

    转移方程也很好写，

    ​ $$f_{i,j}+=f_{i-1,j-1}$$ 当前作为左括号。

    ​ $$f_{i,j}+=f_{i-1,j+1}$$ 当前作为右括号并和一个左括号匹配。

分析

我们钦定两个人分别为 \(A,B\) ，明显的是这道题中 \(1\) 是一个比较特殊的花色，对于其他普通的花色，我可以两个人选的一样，然后两个人内部进行分配使得 \(A\) 总是赢；也可以暂时让 \(B\) 的牌多于 \(A\) ，后面拿若干张的 \(1\) 来进行弥补性配对。

我们考虑如何进行这个计数DP。

对于 \(1\) 花色特殊考虑，我们先不处理它。

对于其他任意一种颜色，我们应用第一种分配策略时，把 \(m\) 张牌均分给两个人，首先假定这个 \(1-m\) 的序列已经降序排列好了。

那么我们从大到小以此给两人分配，发现如果任何时刻，我给 \(B\) 分配的牌都必须要小于等于给 \(A\) 分配的牌，才能够满足题设条件。

那么这实际上就是一个卡特兰数 \(H_{\frac{m}{2}}\)，可以比较性地发现。

我们应用第二种分配时，很容易想到先选出 \(k\) （偶数）个来不进行配对之后和 \(1\) 配，然后剩下的 \(m-k\) 个按照卡特兰数配对。

看起来没什么问题，实际上也确实没问题，但在这道题的计数规则下就是错误的，由于我选出来不配对的几个数实际上是归于 \(A\) 的，这就意味着分别属于 \(A\) 的参与匹配的集合 和 A的暂时不参与匹配集合 的两个数，可能会被重复计算。

反观我们用 DP 求卡特兰数的过程，实际上就已经把这里我们需要的答案给计算出来了，我们想要剔除 \(k\) 个，然后剩下的配对，那么方案数就是上面提到的 \(f_{i,k}\) ，那么我们转移起来也就相对来说很好想了。

\(dp_{i,j}\) 的定义是 前 \(i\) 个花色 （不包括 \(1\) ），一共剩下了 \(j\) 个的方案数。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=998244353,N=600;
int dp[N][N],n,m;
inline int power(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1)ans=ans*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return ans%MOD;
}
inline void garbage_bin()
{
	int C[N][N],catalan[N];
	for(register int i=0;i<=m;++i)
	{
		C[i][0]=1;
		for(register int j=1;j<=i;++j)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
	}
	catalan[0]=1;
	for(register int i=1;i<=m;i++)
		catalan[i]=catalan[i-1]*(4*i-2)%MOD*power(i+1,MOD-2)%MOD;
}
int cat[N][N]; 
void pre()
{
	cin>>n>>m;
	cat[0][0]=1;
	for(register int i=1;i<=m;++i)
		for(register int j=0;j<=m;++j)
		{
			if(j-1>=0)cat[i][j]+=cat[i-1][j-1],cat[i][j]%=MOD;
			cat[i][j]+=cat[i-1][j+1],cat[i][j]%=MOD;
		}
}
void solve()
{
	dp[0][0]=1;
	for(register int i=1;i<=n-1;++i)
	{
		for(register int j=0;j<=m;j+=2)
			for(register int k=0;k<=j;k+=2)
				dp[i][j]+=dp[i-1][j-k]*cat[m][k]%MOD,dp[i][j]%=MOD;	
	}

	int ans=0;
	for(register int j=0;j<=m;j+=2)
		ans+=cat[m][j]*dp[n-1][j]%MOD,ans%=MOD;
	cout<<ans;		
}
// 4  3 2 1
// 12A + 4A3B
// 13A + 4A2B
// 14A + 3A2B
// 23A + 4A1B
// 24A + 3A1B
// 34A + 2A1B 
//dp 4 2=dp 3 1 (2)+dp3 3 (1)
signed main()
{
	pre();
	solve();
	return 0;
}

好久没有写过题解了。。。。

标签：int,Review,Round,while,ans,MOD,void,dp,170
From： https://www.cnblogs.com/Hanggoash/p/18474771

相关文章

  • Codeforces Round 892 (Div. 2)题解记录
    题目链接：https://codeforces.com/contest/1859A.UnitedWeStand选最大的数即可注意题目输出格式 #include<iostream> #include<string.h> #include<map> #include<vector> #include<set> #include<unordered_set> #include<stack> #incl......
  • 打卡信奥刷题（069）用C++工具信奥P11076[普及组/提高] 「FSLOI Round I」单挑
    「FSLOIRoundI」单挑题目背景Englishstatement.YoumustsubmityourcodeattheChineseversionofthestatement.小F和小S经常进行篮球单挑，但小S总是被盖帽。题目描述每次单挑的结果一定是小F获胜或者小S获胜，不存在平局的情况。由于小F和小S实......
  • Codeforces Round 893 (Div. 2)题解记录
    题目链接：https://codeforces.com/contest/1858A.Buttons从自身角度出发,我想赢就得保证我的按钮尽可能多所以，大家都优先按\(c\)，然后分析先后顺序即可 #include<iostream> #include<string.h> #include<map> #include<vector> #include<set> #include<unordered_set> #......
  • Codeforces Round 924 (Div. 2) D. Lonely Mountain Dungeons（推式子，思维，差分，前缀和）
    题目链接CodeforcesRound924(Div.2)D.LonelyMountainDungeons思路令f(n,m......
  • Codeforces Beta Round 93 (Div. 1 Only) B. Password 一题三吃
    https://codeforces.com/problemset/problem/126/B学完Z函数，先用哈希做了一遍，再用Z函数做了一遍，然后搜其他人的题解发现用next数组也能做，就又做了一遍B.Password题意给一串字符串\(s\)，要求找一个最长的\(t\)\(t\)既是\(s\)的前缀串，也是后缀串，还是除了前缀后缀外的一个......
  • YCM中previewwindow显示函数类型信息如何实现
    intro在使用YCM的自动提示功能时，可以注意到选择complete提供的条目时，窗口的上面还有一个小窗口提示这个函数的声明信息，包括了函数的参数列表和类型信息。这个对写代码非常有用，对于一段时间不看的函数，很容易记不得函数的参数列表和各自的类型信息，以至于在官方issue中希望提供一个......
  • 打卡信奥刷题（056）用C++工具信奥P10566[普及组/提高] 「Daily OI Round 4」Analysis
    「DailyOIRound4」Analysis题目描述小C的信息技术老师给小C布置了一项作业，作业内容如下：有一个字符串，包含大小写字母和数字。你可以把任意一个字符变成另外一个字符，设变化之前字符的ASCII码为a......
  • Go语言中http.Transport的RoundTrip方法请求过滤与拦截技巧与应用
    go语言中http.transport的请求过滤与拦截技巧与应用1.引言在Go语言的http包中，http.Transport作为底层的HTTP传输层实现，提供了强大的功能，可以用于发起HTTP请求。本文将重点介绍如何使用http.Transport实现请求过滤和拦截的技巧及其应用。2.请求过滤2.1过滤请求方法我们可以使用h......
  • Educational Codeforces Round 170 (Rated for Div. 2)
    A.TwoScreens难点是读题，找到最长公共前缀即可。#include<bits/stdc++.h>usingnamespacestd;usingi32=int32_t;usingi64=longlong;#defineinti64usingvi=vector<int>;usingpii=pair<int,int>;consti32inf=INT_MAX/2;constintm......
  • 170页精品PPT | 制造业采购供应链及财务管控业务流程蓝图规划
    这份PPT是关于甲方集团数字化转型的详细规划，涵盖了采购供应链及财务管控的业务流程设计、用户体验调研、业务能力提升机会识别，以及总结与后续计划。它详细介绍了采购物控的业务管理愿景、行业发展趋势、采购发展目标、采购平台建设、业务流程框架、关键干系人画像、流程痛点及......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99