首页 > 其他分享 >AT_abc321_f 题解

AT_abc321_f 题解

时间:2023-10-03 10:23:39浏览次数:33  
标签:题解 scanf long 998244353 abc321 dp lld

# 思路

简单动态规划,$dp_i$ 指当前操作后取和为 $i$ 的球的方案数,每次输出 $dp_K$ 即可。

需要注意的是对于每次 `+ x` 操作,计算 $dp$ 数组时要倒着循环。

时间复杂度:$O(QK)$。

# 代码

```cpp
#include<bits/stdc++.h>
using namespace std;
long long dp[5010];
int main(){
long long q,k; scanf("%lld %lld",&q,&k);
dp[0]=1;
for(int i=1;i<=q;i++){
char c;
long long x;
scanf("%c",&c);
while(c!='+'&&c!='-')scanf("%c",&c);
scanf("%lld",&x);
if(c=='+')
for(long long j=5004;j>=x;j--)
dp[j]=(dp[j]+dp[j-x]+998244353)%998244353;
else
for(long long j=x;j<=5004;j++)
dp[j]=(dp[j]-dp[j-x]+998244353)%998244353;
printf("%lld\n",dp[k]);
}
return 0;
}
```

标签:题解,scanf,long,998244353,abc321,dp,lld
From: https://www.cnblogs.com/joe-zxq/p/17740838.html

相关文章

  • RDP远程登录后全屏,本地的任务栏始终显示的问题解决
    文章目录问题解决参考问题RDP远程登录后全屏,本地的任务栏(TaskBar)始终在下面,遮住了远程桌面的最下面,进行了解决。解决BestsolutionhowtohidelocalTaskbarwhenRDPtoaremotedesktopLaunchTaskManagerRight-click“WindowsExplorer”Select“Restart”Itworkson......
  • CodeForces-1276#B 题解
    正文这是样例1第1组数据的图。让我们观察一下,路径1->6、1->7、2->6、2->7是可行的,所以答案为4。上述路径中好像点4没有贡献?再看看样例1第2组数据的图。发现点1和点4相互之间存在其他路径,无需经过点\(a\)和点\(b\)。综上,我们可以知道:在\(a\)和\(b\)......
  • AT_abc279_g [ABC279G] At Most 2 Colors 题解
    题解\(dp[i]\)表示长度为i的格子的合法涂色数,考虑第\(i\)个怎么放第\(i\)个前面\(k-1\)个位置有2种颜色,则第\(i\)个位置只能放这两种颜色中的一种用合法方案减只有一种的方法,即得两种颜色的方案数而只有一种颜色的方案数,等于\(f[i-k+1]\),此时,让中间的\(k-2\)个......
  • P4839 P 哥的桶 题解
    题目大意有\(n\)个桶,\(m\)次操作。在\(pos\)桶中加入一个\(val\)值,求\([l,r]\)中选任意个桶使得异或和最大,求最大的异或和,注意每个节点是一个桶可以放多个值\(n,m≤5×104\)。题目思路单点修改,区间查询,异或最大值很显然是线段树维护线性基然后这样的复杂度是......
  • CF906C题解
    可能更好的阅读体验大家好,我和DP有仇,所以我用猜结论的方法过了这道题。可能是这道题的一个全新思路,可能人自闭久了什么都能想出来(((upd:好像这也是官方题解思路,看来大家做题不太喜欢看CF官方题解(((首先考虑一个问题:如果这是一道构造题,怎么构造一组合法的解?在草稿纸上画了很久......
  • P2230 Tinux系统 题解
    传送门题目大意:一个\(n\)个叶子节点,一个节点最多可以有\(k\)条边连向子节点,每个节点\(i\)有一个权值\(P_{i}\)。记每个节点子树内点的个数(不包括它自己)为\(son_{i}\),那么每个节点对答案的贡献就是\(son_{i}^2\timesP_{i}\)。特别的,根节点贡献为\(0\),求总贡献。两......
  • P1045 麦森数 题解
    传送门前排提醒:本篇题解没有使用压位和快速幂,运用了一种预处理的思想,希望能提供一种新的思路。首先将\(2^{p}-1(d)\)转换为\(1111…111(b)\)。关于第一问:我们先考虑\(2\)进制转\(8\)进制,将每\(3\)位转为\(1\)位,即每\(\log{8}\)位转为\(1\)位。\(2\)进制转......
  • UVA1471 防线 Defense Lines 题解
    传送门首先可以将题意大概可以简化为:取两端不重复的连续子序列,组成一个最长的连续递增子序列。我们先dp预处理出以\(i\)为结尾的连续递增子序列长度\(dpr_{i}\)。同样预处理出以\(i\)为开头的连续递增子序列长度\(dpl_{i}\)。考虑对于每个\(dpr_{i}\),找到满足\(a_{......
  • P5503 灯塔 题解
    决策单调性二分传送门数据加强版:P3515前置知识:二分,决策单调性首先很容易写出答案式子:\[ans_{i}=\max_{j=i}^{n}{(a_{j}-a_{i}+\lceil\sqrt{\left|i-j\right|}\rceil)}\]先将向上取整符号拆掉,只要在输出时处理就行。再将绝对值符号拆掉,分\(j<i\)和\(j>i\)的情况......
  • 题解 Codeforces Round 901 (Div. 1) / CF1874A~E
    题解CodeforcesRound901(Div.1)/CF1874A~E比赛情况:过了AB。赛后发现B是假复杂度。https://codeforc.es/contest/1874A.JellyfishandGameProblemAlice&Bob又在博弈,Alice手上有\(n\)个苹果,第\(i\)个苹果的价值是\(a_i\);Bob手上有\(m\)个苹果,第\(i\)......