一开始看成每个城市只能算一次，然后就愉快的wa了呢。然后才看到可以反复在两个城市间走。贪心的想如果m足够大那么最后一定是在两个城市间来回走。所以我们可以枚举是在哪两个城市间走。 #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<ll> vl; #define PB push_back #define INFL 0x3f3f3f3f3f3f3f3f void solve() { int n,m,p; scanf("%d%d%d",&n...

题目链接https://ac.nowcoder.com/acm/problem/20273 首先我们把这个问题分成两个子问题，然后分别对两个子问题求解，从而解决一个复杂的问题。 我们先来看第一个子问题：这个子问题比较简单，就是仿照题目的，但是这个子问题里只有一条木板，即给你一条木板，上面有连续的格子，你能涂次求，求涂次的情况下最多能粉刷正确多少个格子 然后我们来看第二个子问题我们可以把他想象成以下的模型，你要在个商店中买东西，每个商店只能买一件物品（可以不买），你有元的钱，每个商店有种商品，每一件商品的价格为，价值为，问你花费最多元，可以获得商品的价值最大为多少 我们来将两个问题结合一下，那么...

题解 莫队+值域分块把询问储存起来，然后套莫队的板子然后每次加和减这里如果采取线段树/树状数组进行操作会T可以改用值域分块 代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; struct Node { int l,r; int x; int id; }q[N]; int n,m,a[N]; int block,block2; int res[N]; int *cnt; int cnt2[N]; bool cmp(const No...

题意 给你一个数组让你在中间删去m个数问有多少种不同的结果，答案对(1e9+7)取模 思路 简单dp开一个三维dp，第一维表示当前是第几个数，第二维表示构成的序列最后一个数字是什么，第三维表示还可以删去几次 代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+7; const int N=1e5+5; int n,m,k; ll dp[N][15][15],a[N]; int main() { while(scanf("%d%d%d",&n,...

题意 求所有长度为n的01串中满足如下条件的二元组个数：设第i位和第j位分别位和（i<j），则。答案对1e9+7取模。 分析 我们选取两个位置和其中，然后另且，这样和就构成了一对逆序对，那么剩余个位置有种排列方法，所以就这两个位置对答案产生了个贡献那么我们选取两个位置有多少种选取方法呢？用组合数学的知识显然是种所以最后答案就是然后取模其中 java代码 在java中，提供了BigInteger大整数类和快速幂取模的库函数，所以我们直接调用就可以了 import java.math.BigInteger; import java.util.Scanner; public class M...

Tutorial If the root of a tree is fixed. Obvious, we can use tree dp to solve it. But the root are not fixed. Could we enumeration the roots, and do tree dp for every root? Obvious, the time complexity is . it will get TLE.What should we do?Let's first assume that the root of the tree is 1. Then we...

题意 定义一个数字为幸运数字当且仅当它的所有数位都是4或者7。比如说，47、744、4都是幸运数字而5、17、467都不是。定义next(x)为大于等于x的第一个幸运数字。给定l，r，请求出next(l) + next(l + 1) + ... + next(r - 1) + next(r)。 思路 暴力打表，二分查找打表代码见注释 代码 //#pragma GCC optimize(2) #include<iostream> #include<cstdio> #include<string> #include<algorithm> #inclu...

题目描述 给定两个整数 l 和 r ，对于所有满足1 ≤ l ≤ x ≤ r ≤ 10^9 的 x ，把 x 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求1～9每个数码出现的次数。 思路 我们设定一个函数calc(x)可以计算1-x中1-9每个数码出现的次数，那么我们只需计算两次，分别是calc(r)和calc(l-1)然后相减就行那么我们如何计算设计calc函数呢？那么我们要计算最高位为1-9肯定是要循环1-9，我这里就举例如何计算最高位为1的，其他位类似。我们先预处理一个数组存每一位的最小非0数即1位数最小是1, 2位数最小是10……下面对于不同的位数我们有两个思路...

我尽然把一道dp的题用线段树写nlogn的复杂度还被玄学的卡了一波常建一棵求区间最大的线段树（我下面的线段树模板支持求区间和，区间最小，区间最大）也可以自己传函数 用双指针法把每一个区间的值求出来扔进线段树中。 然后遍历每个区间，用当前区间的值加上后面区间的最大值看看能不能更新最大值。比如说总共有5个区间那就进行如下操作第1个区间的值+第2-5的区间最大值第2个区间的值+第3-5的区间最大值第3个区间的值+第4-5的区间最大值第4个区间的值+第5-5的区间最大值 这段代码如果T了就多交几发，玄学 //#pragma GCC optimize(2) #include<iostream&gt...