首先我们发现如果交换两个菜肴做的顺序，sum(ai)是不变的，也就是只剩下两个变量。此时容易想到可以通过代数运算得到做菜顺序。其实贪心思路也挺显然的，肯定是让减少的少的先做，并且同时和做这道菜的时间有关，所以我们此时通过代数运算得到当a.c/a.b < b.c/b.c的时候，先做a是优于先做b的。 然后就是一个标标准准的01背包。 #include <bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1...

标题 C题：给定a，b。q次询问，问l-r区间内满足x%a%b != x%b%a 的x的个数首先证明[1,ab]区间内的个数和[ab+1, 2a*b]内的x的个数相同，十分显然，因为(x+ab)%a%b = (x)%a%b所以预处理[1，ab]种所有，满足条件的x的个数，再用前缀和的思想。 #include using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define mp ...

https://ac.nowcoder.com/acm/problem/201400先看这道树学题如果有了解过树的重心，那么这道题就easy了，无非就是找树的重心。找树的重心就是一遍dfs。然后再一遍dfs求每个点的深度。相加即可。 代码 #include <iostream> #include <vector> #include <bits/stdc++.h> #include <cstdio> #include <cstring> using namespace std; typedef long long ll; const i...

题目大意 shy有一颗树，树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的，当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同。请统计方案数。 解答 千万不要被树迷惑了，仔细一想，这和树有什么关系呢？可以转换一下思路：题目的意思就是最多切k-1条边，切出来一些连通块，且联连通块里的所有边的颜色相同，所以答案就是就是从(n-1)条边种选i条边切，然后从k种颜色给这i+1个点染色，然后求和，最后+k就是所有点染一个颜色，其实可以被归类到一条边都不切。所以只要与处理一下C(n,m)就ok啦~ 代码 #include <bits/stdc++....

A题 普通的模拟就不多说了 放个代码 #include<bits/stdc++.h> using namespace std; int T; int main() { cin >> T; while(T --) { string str; cin >> str; bool flag = true; for (int i = 0; i < str.length() && flag; i = i+2){ if(str[i] ==...

题目描述 给定两个整数 l 和 r ，对于所有满足1 ≤ l ≤ x ≤ r ≤ 10^9 的 x ，把 x 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求1～9每个数码出现的次数。 预备知识：整数分块 具体证明请看这。https://www.cnblogs.com/0xfffe/p/9648943.html下面我们稍微理解一下这个知识。先从求如下式子说起。首先肯定想暴力枚举（肯定会t） 这里举个例子不妨让x = 15，我们打表以后的结果：15，7，5，3，3，2，2，1，1，1，1，1，1，1，1.由于这些数字肯定是递减的并且我们发现有些连续的区间的值是相同的！因此我们...

题目 模式串可以浮动的模式匹配问题 给出模式串的相对大小，需要找出模式串匹配次数和位置 比如说模式串：1，4，4，2，3，1 而主串：5,6,2,10,10,7,3,2,9 那么2,10,10,7,3,2就是匹配的 首先是kmp的next数组求法 void_getnext(char x[], int m, int next[]) { int i, j; i = 0; j = next[0] = -1; while(i < m) { while(j != -1 && x[i] != x[j]) j = ...

这道题其实是codeforces一道题的简化版本。这里放一下cf的题目链接：https://codeforces.ml/contest/1281/problem/E 思路与题解 由于是计算边的贡献，我们可以关注某一条边是否需要被计算在内。如何考虑呢？ 容易知道当某一条边的子树中如果有偶数个节点，那么这些点可以内部配对，也就是说不需要考虑这条边的贡献。反之，如果这条边的子树中有奇数个节点，那么必定有一个点会连出来，这条边的贡献就会+1。并且要最小的画，这条边的贡献就是1。(cf还要求算最大的贡献，可以思考） 代码 #include<iostream> #include<algo...

Solution 求树上的简单路径很明显是LCA的题目，那么：直接预处理父节点数组和深度数组直接暴力把 u 和 v 往上提 ？那就错了。其实题目里有保证 v 在 u 前往首都的最短路径上，所以只需要直接把 u 向上遍历就可以了。而珠宝购入的前提是当前城市的珠宝严格大于手中的所有珠宝，所以只需要再用两个变量维护珠宝的最大值和购入次数即可。显然在数据小的情况下以上暴力可以AC，但是数据量一大超时就必不可免了。可以优化的过程便是 u 找 v 这个过程，那么就要用到本文第一句话的LCA。由于出发节点的价值大的时候也会购入，所以可以处理询问的时候可以把每组询问离线，出发点作为新节点的父亲，带着的珠宝价值...

题目大意 给定在n*m的网格中，每个格子有一个高度，每次可以做如下两个操作： 使某个点的高度增加2 使两个相邻的格子的高度增加1问 满足可以经过这两个操作使得所有高度相同的初始矩阵有多少个？（所有格子内的数的范围在[L，R]区间。） 题解 Observation1: 原方格只有奇，偶对结果有影响。Proof： 发现可以先用操作1使某些数加一些2，其实就像等于让别的数减2（高度差不影响），所以最终所有数都是1或者0，即奇偶有关，且无需考虑操作1.（只要让所有数奇偶相等即可） Observation2: 可以任意改变矩阵中某两个格子的奇偶。Proof： 对两个格子的路径上的所有点都进行操作2，...

题解 类似于单调栈的思想（找右边满足某些性质的位置）所以这道题可以预处理出每个位置的字符的右边离他最近的26个字母的位置。（如果不存在则是-1） 但是要注意的是，要在原数组之前添加一个额外的位置用来找到目标数组的第一个位置。 nxt[i][j] = nxt[i + 1][j] 动态规划从后往前遍历即可。 代码 #include<iostream> #include<algorithm> #include<cstdio> #include<climits> #include<cstring> #include<cstdlib&gt...

题目大意： Rinne 一个 n 个节点 m 条边的无向连通图，每条边有一个边权 wi 选取一个 点 S，然后选择性删除一些边，使得原图中所有除 S 之外度为 1 的点都不能到达 S。问删除这些边的最小代价。 题解 由于m = n-1,所以该图是一棵树，以s为根节点，先找到度为一的 叶子 节点， 然后向上递推，递推过程如下。设 dp[u] 表示u节点的子树中所有度为1的点都已经不与s节点在同一连通块内的最小代价。 dp[u] += min(dp[j], edge[j][u].w)（j是u的子节点）不切连接u和j的边的最小代价就是dp[j]， 而切的最小代价是edge[j][u].w，即边权。还...

#include <iostream> #include <cstdio> #include <queue> #include <cstring> #define ll long long using namespace std; const int maxn=1e5+10; ll a,b,c,k,ans[4],dis[maxn],vis[maxn],nxt[maxn]; priority_queue<pair<int,int> >q; void Dijkstra(){ memset(dis,0x7f,sizeof...

数学考试的拓展题： 简单题意：将n个数的数列分为m个不相交的连续子序列，求这m个子段的最大值。 首先容易考虑用dp优化暴力做法。我们考虑dp[i][j] 表示以j结尾且前j项被分为i段的最大值那么有两种情况：1.dp[i][j] = dp[i - 1][k] + a[j] (表示的是第j个元素单独在一组)2.dp[i][j] = dp[i][j - 1] + a[j] (表示的是第j个元素与前面在同一组内)于是转移方程就是 dp[i][j] = max(dp[i - 1][k], dp[i][j - 1]) + a[j]; 其中k=i-1，i，...，j-1。复杂度是O(n^3), 显然对于...