首页 > 其他分享 >UNIQUE VISION Programming Contest 2022(AtCoder Beginner Contest 248)C~D 题解

UNIQUE VISION Programming Contest 2022(AtCoder Beginner Contest 248)C~D 题解

时间:2024-09-08 21:13:57浏览次数:11  
标签:dots AtCoder le Contest int 题解 text dp mathrm

C - Dice Sum

题目大意

有多少个整数序列\(A=(A_1,\dots,A_N)\)符合如下条件:

  • \(1\le A_i\le M\)
  • \(\sum\limits_{i=1}^NA_i\le K\)

输出答案,对\(998244353\)取模。

\(1\le N,M\le 50\)
\(N\le K\le NM\)

输入格式

\(N~M~K\)

输出格式

输出答案,对\(998244353\)取模。

分析

艹C题又要dp
考虑\(\text{DP}\)思想,令\(\text{dp}(i,j):=A\)的前\(i\)个元素中和为\(j\)的总可能数(\(1\le A_x\le M\)),则可得伪代码:

dp[0][0] = 1
for i = 0 to N-1 // 逐个位置考虑
	for j = 0 to K-1 // 考虑所有和的情况,无需考虑K
		for k = 1 to M // 1-M的每个选择
			if j + k <= K: // 限制条件
				dp[i + 1][j + k] += dp[i][j] // 更新dp[i+1]

时间复杂度为\(\mathcal O(NMK)\),可以通过

其实还可以利用前缀和优化
不难发现\(\mathrm{dp}(i,j)=\displaystyle\sum_{k=L}^R\text{dp}(i-1,k)\),
其中\(L\le R\),具体的值请自行推导。
因此,我们可以记录\(\mathrm{dp}[i-1]\)的前缀和\(\mathrm{pre}\):

  • \(\mathrm{pre}_j=\displaystyle\sum_{k=1}^j\mathrm{dp}(i-1,k)\)

则\(\mathrm{dp}(i,j)=\mathrm{pre}_R-\mathrm{pre}_{L-1}\)。
因此,时间复杂度为\(\mathcal O(NK)\)。
强烈建议读者独立推导并实现该方法。 前缀和优化\(\text{DP}\)的算法在E、F题中很常见。

代码

#include <cstdio>
#define MOD 998244353
#define maxn 200005
using namespace std;

inline void mod(int& x) { if(x >= MOD) x -= MOD; }
int dp[2][maxn];

int main()
{
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	dp[0][0] = 1;
	for(int i=0; i<n; i++)
	{
		int c = i & 1, p = c ^ 1;
		for(int j=0; j<=k; j++)
			dp[p][j] = 0;
		for(int j=0; j<k; j++)
			for(int d=1; d<=m && d<=k-j; d++)
				mod(dp[p][j + d] += dp[c][j]);
	}
	int ans = 0;
	for(int i=1; i<=k; i++)
		mod(ans += dp[n & 1][i]);
	printf("%d\n", ans);
	return 0;
}

D - Range Count Query

题目大意

给定整数序列\(A=(A_1,\dots,A_N)\)。
有\(Q\)个查询。每个查询的格式如下:

  • 给定三个整数\(L,R,X\),求\(A_L,\dots,A_R\)中\(X\)的出现次数。

\(1\le A_i,X\le N\le 2\times10^5\)
\(1\le L\le R\le N\)

输入格式

\(N\)
\(A_1~\dots~A_N\)
\(Q\)
\(L_1~R_1~X_1\)
\(\vdots\)
\(L_Q~R_Q~X_Q\)

输出格式

输出\(Q\)行,第\(i\)行是第\(i\)个查询的答案。

分析

题目换句话说就是:求\(X\)出现的位置中,在\([L,R]\)区间内的有多少个?
因此,我们很容易想到先预处理\(1,\dots,N\)中每个数出现的位置,存入vector,查询时二分即可。

代码

注意二分边界。

#include <cstdio>
#include <vector>
#include <algorithm>
#define maxn 200005
using namespace std;

vector<int> pos[maxn];

int main()
{
	int n, q;
	scanf("%d", &n);
	for(int i=0; i<n; i++)
	{
		int a; scanf("%d", &a);
		pos[a].push_back(i);
	}
	scanf("%d", &q);
	while(q--)
	{
		int l, r, x;
		scanf("%d%d%d", &l, &r, &x);
		printf("%d\n", int(
			lower_bound(pos[x].begin(), pos[x].end(), r) -
			lower_bound(pos[x].begin(), pos[x].end(), --l)
		));
	}
	return 0;
}

标签:dots,AtCoder,le,Contest,int,题解,text,dp,mathrm
From: https://www.cnblogs.com/stanleys/p/18403495/abc248

相关文章

  • AtCoder Beginner Contest 252 A~G 题解
    前言这是我第一次写7题(A~G)的ABC题解,若有写得不好或者不到位的地方请多多指教,我将万分感激,感谢大家的支持!A-ASCIIcode题目大意给定正整数\(N\),输出ASCII码是\(N\)的字母。\(97\leN\le122\)输入格式\(N\)输出格式输出ASCII码是\(N\)的字母。分析注意a对应\(97\)......
  • AtCoder Beginner Contest 192 A~D 题解
    A-Star题目大意下一个大于\(X\)的\(100\)的倍数与\(X\)的差是多少?\(1\leX\le10^5\)输入格式\(X\)输出格式输出答案。样例\(X\)输出\(140\)\(60\)\(1000\)\(100\)分析下一个大于\(X\)的\(100\)的倍数是\((\lfloorX/100\rfloor+1)\times100\)。所......
  • AtCoder Beginner Contest 191 A~D 题解
    A-VanishingPitch题目大意一个球的速度是\(V~\text{m/s}\),它飞了\(T\)秒后会隐形,飞了\(S\)秒时会接触隐形。球在飞了\(D\)米后,人能看见它吗?输出Yes或者No。\(1\leV\le1000\)\(1\leT<S\le1000\)\(1\leD\le1000\)输入格式\(V~T~S~D\)输出格式输出答案。样例......
  • AtCoder Beginner Contest 190 A~D 题解
    A-VeryVeryPrimitiveGame题目大意Takahashi和Aoki在玩一个游戏。游戏规则是这样的:最开始,Takahashi和Aoki分别有\(A\)和\(B\)颗糖。他们将轮流吃一颗糖,第一个无法吃糖的人算输。如果\(C=0\),那么Takahashi先吃;如果\(C=1\),那么Aoki先吃。请输出最终胜者的名字。\(0\le......
  • AtCoder Beginner Contest 194 A~E 题解
    A-IScream题目大意在日本,有如下四种冰淇淋产品:至少有\(15\%\)的milksolids和\(8\%\)的milkfat的产品称为“冰淇淋”;至少有\(10\%\)的milksolids和\(3\%\)的milkfat且不是冰淇淋的产品称为“冰奶”;至少有\(3\%\)的milksolids且不是冰淇淋或冰奶的产品称为“乳冰**”;......
  • AtCoder Beginner Contest 198 A~E 题解
    A-Div题目大意两个男孩要分\(N\)颗糖。问一共有几种分法(每个男孩都必须分到糖)?\(1\leN\le15\)输入格式\(N\)输出格式将答案输出为一个整数。样例\(N\)输出\(2\)\(1\)\(1\)\(0\)\(3\)\(2\)分析这题说白了就是将\(N\)分成\(A\)和\(B\)两个正整数......
  • AtCoder Beginner Contest 196 A~E 题解
    A-DifferenceMax题目大意给定四个整数\(a,b,c\)和\(d\)。我们要选择两个整数\(x\)和\(y\)(\(a\lex\leb\);\(c\ley\led\))。输出最大的\(x-y\)。\(-100\lea\leb\le100\)\(-100\lec\led\le100\)输入格式\(a~~b\)\(c~~d\)输出格式输出最大的\(x-y\)。样例\(......
  • Mynavi Programming Contest 2021 (AtCoder Beginner Contest 201) A~E 题解
    A-TinyArithmeticSequence题目大意给定序列\(A=(A_1,A_2,A_3)\)。能否将\(A\)重新排列,使得\(A_3-A_2=A_2-A_1\)?\(1\leA_i\le100\)输入格式\(A_1~A_2~A_3\)输出格式如果能将\(A\)重新排列使得\(A_3-A_2=A_2-A_1\),输出Yes;如果不能,输出No。样例\(A\)输出\((5......
  • AtCoder Beginner Contest 204 A~E 题解
    A-Rock-paper-scissors三个人玩石头剪刀布平局,其中两个出的分别是\(x,y\),求另一个人出的。\(0\lex,y\le2\)(\(0,1,2\)分别表示石头,剪刀,布)输入格式\(x,y\)输出格式用整数格式输出答案。样例\(x\)\(y\)输出\(0\)\(1\)\(2\)\(0\)\(0\)\(0\)分析石头......
  • AISing Programming Contest 2021 (AtCoder Beginner Contest 202) A~E 题解
    A-ThreeDice一个人抛了三个骰子,它们的顶面分别是\(a,b,c\)。求它们的底面之和。这里用的骰子是标准骰子,即两个相对的面之和为\(7\)。\(1\lea,b,c\le6\)输入格式\(a~b~c\)输出格式输出答案。样例\(a\)\(b\)\(c\)答案\(1\)\(4\)\(3\)\(13\)\(5\)\(6......