中缀表达式求值 对于表达式求值，我们通常用栈来操作。 常用的做法是先转换为后缀表达式，再利用栈来求值。 步骤如下：
开一个栈一个储存运算符，再开一个结构存后缀表达式，可以选择string数组 每遇到一个数字，将其加入到后缀表达式种 遇到左括号，加入到符号栈种 遇到右括号，不断将栈顶元素添加到后缀表达式中，直到遇到左括号，然后弹出左括号 遇到普通运算符，只要栈顶符号的优先级不低于新符号，就不断取出栈顶元素存到后缀表达式，然后将新符号入栈，优先级顺序为乘除>加减>左括号 依次取出符号栈中剩余元素，加入到后缀表达式中 将得到的后缀表达式求值 Note 代码在取栈顶元素时容易出错，需要注意对栈为空时的判断
Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <queue> #include <cmath> #include <stack> #include <map> #include <set> #define mem(a,b) memset(a,b,sizeof(a)) #define debug cout<<0<<endl #define ll long long const int MAXN = 1e4 + 10; const int MOD = 1e9 + 7; using namespace std; stack<int> stnumber; stack<char> stsign; stack<int> ans; struct node { string s=""; } a[MAXN]; int oder(char c) { if (c == '+' || c == '-') return 1; else if (c == '*' || c == '/') return 2; return 0; } int toInt(string ss) { int res = 0; for (int i = 0; i < ss.
Description 给出整数$n,k$,计算$G(n,k)=\sum\limits_{i=1}^n=k \ mod \ i$,$1<=n,k<=1e9$
Solution 将k mod i展开可以得到$k - i*\lfloor \frac{k}{i} \rfloor$ 将求和式子展开可以得到$ \sum\limits_{i=1}^n = nk-\sum\limits_{i=1}^n i * \lfloor\frac{k}{i} \rfloor $ 利用整除分块，可以发现，对于相同的$\lfloor\frac{k}{i} \rfloor$，即每个区间$l 到 r$，每次只需要再对i求和即可 即每次计算$(r-l+1)\lfloor \frac{k}{i} \rfloor * (l+r)/2$
Note 在分块的时候误写为r=N/(N/i)导致调试耽误大量时间，而且交了四发才发现
1 2 3 4 5 6 7 for (ll l = 1, r; l <= N; l = r + 1) { if (l > K) { break; } r = min(N, K/(K/l)); ans -= (r - l + 1)*(K/l)*(l + r)/2; } Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 //https://www.
Description 求平面上n个点构成的平行四边形个数。 输入 一行一个数n。 接下来n行，每行两个数x,y，表示这个点的坐标为(x,y)。 保证任意两点不重合，任意三点不共线。 输出 一行一个整数表示平行四边形个数。
Solution 按照平行四边形的性质，两组顶点的中点重合，可以统计出每组顶点的中点，再统计每个顶点的个数，排列组合一下
Note 第一发对于顶点的统计出锅了，排序条件写错，提交都要检查排序
Description 请输出$Fib(n) mod 10000$ $n \leq 1000000000$
Solution 由于$n$的范围在$1e9$直接递推铁TLE，考虑矩阵快速幂 Fibonacci数列有如下性质 通过多次迭代 算是个板子题吧，记得在WUST新生赛做过一道想矩阵快速幂的题，然而正解是找规律QAQ，在此贴个板子。
Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 #include <cstdio> #include <queue> #include <algorithm> #include <iostream> #include <queue> #include <cstring> #include <string> typedef long long LL; const int MOD = 1e4; using namespace std; struct Matrix{ LL m[2][2]; void print(){ for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) cout << m[i][j] << ' '; cout << endl; } } } base, ans; Matrix times(Matrix a, Matrix b) { Matrix ans; ans.
Description 有$n$个木棍，长度为$1,2,3…n$，现在要从中删掉一些木棍，使得剩下的木棍不能构成三角形，使删掉木棍的数量最少。T组数组，$T \leq 20$ $n \leq 20$
Solution 由于数据范围很小，可以直接暴力求解，依次选取两个数$a,b(a<b)$相加，要知道不能有任何一个数小于这个值，直接删掉$(a,a+b)$范围中的数即可 如果$n$的范围是$1e9$呢？ 通过找规律发现我们剩下的数是这样的 $1,2,3,5,8,13,21…$ 这是Fibonacci数列!!!! 所以我们只需要找到$\leq n$的Fibonacci数有几个，减去就是答案 可以直接lower_bound注意处理极限数据！！！即$n==1||n==2$的情况 也可手写二分，但是二分貌似常数有点大，又考虑到第$88$个Fibonacci数就爆掉$1e9$了，所以直接便利也完全没问题
Code 暴力版本 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <cstring> #include <queue> using namespace std; bool vis[23]; int main() { int T; cin >> T; for (int i = 1; i <= T; i++) { int N, ans = 0; cin >> N; memset(vis, false, sizeof(vis)); for (int j = 1; j <= N - 1; j++) if (!
Description 在杨辉三角中，从第一行第一列$(0,0)$开始，每次可选择向正下方走或向右下方走，走到第$n$行时不能超过第$n$行第$k$个元素，询问所经过路径的值的和的最小值$mod(p)$，一共有T组询问，$T \leq 100000$， $0 \leq k \leq n \leq 1e9$, 保证$p$是质数， 其中$p < 1e4$
Solution 名字虽然是DP，但是可以找出最优方案。 优先考虑$k \leq \frac{n}{2}$的情况，先向下走$n-k$步到达$(n-k-1,0)$ 再一路沿着右下方走，直到到达底部，即有$C_{n-k}^{0}+C_{n-k+1}^{1}+C_{n-k+2}^{2}+…+C_{n}^{k}=C_{n+1}^{k}$ 通过变换$C_{n-k}^{0} = C_{n-k+1}{0}$ 再通过公式$C_{n}^{m}=C_{n-1}^{m}+C_{n-1}^{m-1}$可将上述公式合并 得到$C_{n+1}^{k}$ 所以答案为$C_{n+1}^{k}+n-k$ 当$k > \frac{n}{2}$时，根据对称性，令$k=n-k$即可转化成上一种情况 又发现题目涉及组合数取模，所以要用到费马小定理
费马小定理: 假如$a$是一个整数，$p$是一个质数，且$gcd(a,p)=1$，即$a,p$互质，那么有$a^{p−1}≡1(modp)$
已知$a^{p-1}≡1$，可以得到$a \cdot a^{p-2}≡1$，我们称$a$和$a^{p-2}$为在$mod(p)$意义下的乘法逆元 然而这只解决了除法取模的问题，注意到$n$的范围在$1e9$直接计算组合数又是铁套老鹅(TLE)，于是借助Lucas定理
对于质数$p$,有$C_n^m\ mod \ p = C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{m}{p} \rfloor} \cdot C_{n\ mod\ p}^{m\ mod\ p} \ mod \ p$
可知$n\ mod\ p$和$m\ mod\ p$一定是小于$p$的数，可直接求解，其余部分继续用Lucas定理求解，当$m=0$的时候返回$1$
1 2 3 4 long long Lucas(long long n, long long m, long long p) { if (m == 0) return 1; return (C(n % p, m % p, p) * Lucas(n / p, m / p, p)) % p; } 有了这些工具之后就可以预处理阶乘和逆元了
