C-子段乘积 思路： 前缀积 费马小定理 逆元 当p为质数时可以用快速幂求逆元 当p不是质数时，可以用扩展欧几里得算法求逆元 因为a有逆元的充要条件是a与p互质，所以     g   c   d   (   a   ,   p   )   =   1    gcd(a, p) = 1   gcd(a,p)=1 由费马小定理：      ∵    b    p   −   1     ≡   1   (   m   o   d    ∵b^{p-1}\equiv1(mod   ∵bp−1≡1(mod      p   )    p)   p)      ∴    b    p   −   2  ...

B.Count Subrectangles 思路： 存因子到数组中 遍历因子算满足该因子个数的行和另一因子个数的列分别为多少相乘即可。 #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int>P; const double eps = 1e-8; const int NINF = 0xc0c0c0c0; const int INF = 0x3f3f3f3f; const ll mod = 1e9 + 7; const ll maxn = 1e5 + 5...

D - Count the Arrays 题意： m个数排成先严格单调递增再严格单调递减 求有多少种排列方式，答案对      998244353    998244353   998244353 取模 思路： 组合数学      l   u   c   a   s    lucas   lucas定理 从     m    m   m个数中取出     n   −   1    n-1   n−1个数，其中一个数为最大的数，他是不能有2个的，所以能从剩下的     n   −   2    n-2   n−2个数中选一个数放到最大数的另一边。 我做的时候想不通如何表达顺序，这个     q ...

1312E Array Shrinking 题意： 给你      n   (   1   ≤   n   ≤   500   )    n(1\leq n\leq 500)   n(1≤n≤500) 长的数组，你可以任意次操作使得满足      a   [   n   ]   =   a   [   n   +   1   ]    a[n]=a[n+1]   a[n]=a[n+1] 的两个数被替换为      a   [   n   ]   +   1    a[n]+1   a[n]+1 ，求数组最小长为多少。 思路： 区间      d   p    dp   dp 观察      n...

C. Frog Jumps 题意：  一只青蛙站在x轴0点，想要跳到第n+1个点。 青蛙可以跳任意次数，跳到L点只能向左跳，跳到R点只能向右跳，问所有跳跃中最大的值最小为多少？  思路： 贪心 青蛙跳到n+1个点之前一定在R或者原点处（没有R），青蛙如果去L再去R只会增大距离，所以青蛙只跳R的点并记录最大距离为多少即可。 代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int>P; const double eps = 1e-8; const ...

C 装备合成 题意：  牛牛有{x}x件材料{a}a和{y}y件材料{b}b，用{2}2件材料{a}a和{3}3件材料{b}b可以合成一件装备，用{4}4件材料{a}a和{1}1件材料{b}b也可以合成一件装备。牛牛想要最大化合成的装备的数量，于是牛牛找来了你帮忙。  思路： 1.线性规划 O(1) 这个高中知识裸题没啥好说的画个图求两直线交点，特判一下交点不在第一象限的时候取两直线和x轴、y轴的交点的最小值即可。 坑点：线性规划得到的最佳答案为浮点值，浮点运算精度可能出现问题，然后还要考虑下取整，所以可以求计算得到的值取整上下范围的一个值，这里取1即可，不过为了保险起见开大点开个10也是没问...

D - String Equivalence 题意  本来是求字母的序列转化为求数字的序列，最后可以再转化为字母。 转化为求一个序列，如果这个位置是 p[i]，那么 1~i-1 内一定出现过所有 1~p[i]-1 的数字,且第i个位置能取的最大数字为之前所用到的最大数字+1。  思路 序列要想到DFS 字母序列可以转化为数字序列 最后输出的时候再转换回来即可 代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int>P; const double ...

C. Ehab and Path-etic MEXs 题意 给两两节点放一个数字（0~n-2 唯一） 给你一棵树，求所有任意两节点相连的路以外的路上的数字的最小值最小 思路 构造 若一个点连了三条边及以上，则这个点的边从最小值开始赋值。其他边从最大点开始赋值。 证明：一个点连了三条边及以上，那么任取uv所在路一定不可能经过该点的所有边，那么显然最大值为这个点所连边的第三小值2。 代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int>P; con...

E. Rock Is Push 题意 出发点(1,1)到终点(n,m)，只能向右和向下走，路上有障碍物用’R’表示，空地用’.'表示，你的力气巨大无比可以推动所有箱子，只要箱子不贴墙。求有多少种走法？  思路 棋盘dp 前缀和（优化计算降低复杂度） DP题一般都会满足三个条件：子问题重叠、无后效性、最优子结构性质。 这道题满足以上三点。      d   p   [   i   ]   [   j   ]    dp[i][j]   dp[i][j]的方案数可由     d   p   [   i   ]   [   j   −   1   ]    dp[i][j-1]   dp[i][j−...

Aizu0121 题意  t(<1000)组数据 0可以和上下左右四个位置交换 求最少多少步能变成图d这种情况 思路 BFS求最短路径 难点 正难则反：以往我BFS都是正着求，从输入状态到达理想状态，然而这道题这么做却很麻烦，我们应该考虑从理想状态到达输入状态，这完全不影响结果，反而有利于我们求解。 利用数据结构：这里的输入量很大，每次求一次BFS很麻烦，这种情况考虑BFS求所有情况，然后保存到map当中，直接输出结果。 选用合理数据类型保存：我思考了很久该如何去保存这样的数组，看到别人的解法是用string来表示整个数组的状态，实在是秒。 新遇到的stl函数： getline(cin,...

D2 - Prefix-Suffix Palindrome (Hard version) 题意      给   你   一   个   字   符   串   S   ，   找   出   最   长   的   满   足   以   下   条   件   的   字   符   串   T   ：   长   度   不   超   过   ∣   S   ∣   T   为   回   文   字   符   串   存   在   两   个   字   符   串   a   和   b   （   可   能   为   空   ）   ，   T   =   p   r  ...

A - Range Flip Find Route 题意 从(1,1)到(n,m)(只能走’.’)最小翻转次数。 翻转： 可以翻转任意矩形块 思路 棋盘dp 答案为连续的’#个数 #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int>P; const double eps = 1e-8; const int NINF = 0xc0c0c0c0; const int INF = 0x3f3f3f3f; const ll mod = 1e9 + 7; c...

A 多边形与圆 题意  任意凸多边形在圆内滚动，由1号点开始离开到1号点再次滚动到圆内1号点所滚动的弧长是多少？ 思路 计算几何       ∠   k   1   =   a   c   o   s     x   [   i   ]   [   i   −   1   ]     2   R     ∠   k   2   =   a   c   o   s     x   [   i   ]   [   i   +   1   ]     2   R     ∠   i   =   a   c   o   s     x   [   i   ]   [   i   −   1    ] ...

环境变量 C:\MinGW\bin;D:\C++\MinGW64\bin\g++.exe;D:\Java\jdk-14\bin;D:\Python;D:\Python\Scripts;D:\Python\chromedriver.exe;C:\Users\Meul\Desktop\All\云班课打包(2)\源代码;C:\windows\system32;"%SystemRoot%\system32;";"%SystemRoot%;";"%SystemRoot%\System32\Wbem;";%JAVA_HOME%\bin;%JAVA...