描述 给定一个长度为nnn的数组，一共有qqq个询问，每次询问区间[l,r][l,r][l,r]的和 思路 前缀和的模板题，设sum[n]sum[n]sum[n]表示区间[1,n][1,n][1,n]的和，则每次询问输出sum[r]−sum[l−1]sum[r]-sum[l-1]sum[r]−sum[l−1]即可 代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=1e5+5; ll sum[MAXN]; int main() { int n,q; ...

描述 给定三个字符串"nico","niconi","niconiconi",分别对应价值a,b,ca,b,ca,b,c，同时给定一个长度为nnn的字符串，选择该字符串中部分子串使得选择的子串的价值最大，每个字符仅能被选一次 思路 动态规划问题，设dp[n]dp[n]dp[n]为子串[1,n][1,n][1,n]的最大价值，当前字符串为sss，则有 dp[i]={<mstyle displaystyle="false" scriptlevel="0">dp[i−3]+a</...

描述 给定一个长度为nnn的数组，选取一些不相邻的数，使得取出的数最大。 思路 动态规划的入门题目，设dp[n]dp[n]dp[n]表示仅考虑区间[1,n][1,n][1,n]所能得到的最大结果，对于某个数iii，它可以做的选择为 合入区间[1,i−1][1,i-1][1,i−1]的最优结果当中 仅仅选择它自己 一个数都不选 则最终的转移公式为dp[i]=max({dp[i−2]+a[i],a[i],dp[i−1]});dp[i]=max(\{dp[i-2]+a[i],a[i],dp[i-1]\});dp[i]=max({dp[i−2]+a[i],a[i],dp[i−1]});，最终答...

描述 给定一个长度为nnn的数组，输出加和最大的非空子数组的和。 思路 首先考虑数组中的最大值，如果为负数，则最大子数组为该值，否则答案一定大于0 当最大值为正时，则最大的子数组肯定不为空，则有以下的解法 暴力，直接O(n2n^2n2)暴力枚举各个子数组的和，然后输出最大值即可 DP，设dp[i]dp[i]dp[i]表示以第iii个元素为结尾的最大子数组的值，则转移公式为dp[i]=max({dp[i−1]+a[i],0})dp[i]=max(\{dp[i-1]+a[i],0\})dp[i]=max({dp[i−1]+a[i],0}),分别代表选这个数和不选这个数的情况 代码 #in...

题目陈述 简介：给定一个数组，每次选择一个区间 染色，保证区间不存在相交，只有相离和包含两种关系，问将整个数组染色的期望，答案对取模。 前置知识 逆元 求某个数在某个模数下的逆元，即求，使得，因此，取模意义下的除法等价于乘该数的逆元 一般在题目当中是一个素数，常见的算法是费马小定理，费马小定理内容是，如果是一个质数，且不是的倍数，则，因此在为质数的情况下，的逆元为，使用快速幂进行求解，时间复杂度为，快速幂代码示例为// x^y % MOD int qpow(int x,int y) { int ret=1; for(int i=y;i;i>>=1) { i...

萌新出题人第一次出题，没把握好难度，被A穿了，十分抱歉 B题题面出了一些小锅，我已经帮大家喷过出题人了= =,如果大家有啥想喷的，欢迎私信我，我一定转达（雾 B会把之前wa的代码按原错题rejudge A.聚会 显然一个传送门放在 ，另一个传送门放在位置 非 0 的位置是最优的，否则我们将一个传送门挪到 一定可以使得使用传送门的朋友们更快到达聚会地点。 剩下能放传送门只有一个，只能放在 或者 位置才有收益。 当所有朋友的家都在 （或 ）时，我们可以发现，假设传送门放在位置 ，对于所有 的朋友，走传送门比不走传送门速度更快，而 的朋友则需要讨论走到传送门更快还是直接奔向原点更快（因为...