题目网址：http://codeforces.com/contest/1151/problem/D题目大意：给出n组数对,(ai , bi)，调整这n组数对的位置，最小化 ∑（ai*( i -1)+bi*(n - i)）并输出结果。<msub><mi>a</mi><mi>i</mi></msub><mo>⋅</mo><mo stretchy="false">(</mo><mi>j</mi><mo>−</mo><mn>1</mn><mo stretchy="false">)</mo><mo>+</mo><msub><mi>b</mi><mi>i</mi></msub><mo>⋅</mo><mo stretchy="false">(</mo><mi>n</mi><mo>...
·不论难度，A,C,D自己都有收获！ [A. Kirill And The Game]·全是英文题,述大意： 给出两组区间端点：l,r,x,y和一个k。(都是正整数，保证区间不为空),询问是否在[x,y]区间内存在一个整数p,使得p*k属于[l,r],如果存在，则输出‘YES‘，否则输出‘NO‘。(1<=l,r,x,y<=107)·分析： 首先看见了107,发现可以直接O(n)暴力枚举：枚举区间[x,y]的所有数，判断它与k的乘积是否在[l,r]中就可以了。从容AC: 其实在这之前大米饼首先...
Codeforces Round #715 (Div. 2)
C. The Sports Festival DP
题目大意：
给你一个序列 \(s\) ，你可以重新排列这个序列，成为一个新序列 \(a\) 。设 \(d_i=max(a_1,..,a_i)-min(a_1,...,a_i)\) ，求最小的 \(d_1+d_2+...+d_n\)
题解：
倒过来想，就是对于一个已经排好的序列，每次选择删掉最大值还是最小值，因为删掉中间的值是不会有影响的。
定义 \(dp[i][j]\) 表示从 \(i\) 到 \(j\) 的最小的值。
然后转移每次只能从 \(dp[i+...
Contest 2050 and Codeforces Round #718 (Div. 1 + Div. 2)
也就会写写模拟了
A - Sum of 2050
数位和
int main() {IOS;for (cin >> _; _; --_) {ll n, x; cin >> n;if (n % 2050) { cout << "-1\n"; continue; }x = n / 2050; n = 0;while (x) n += x % 10, x /= 10;cout << n << '\n';}return 0;
}B - Morning Jogging
int s[105][105], a[105][105], b[105], d[105];int main() {IOS;for (cin >> _; _; --_) {cin >> n >> m;re...
Codeforces Round #715 (Div. 2)
A - Average Height
int main() {IOS;for (cin >> _; _; --_) {cin >> n; VI a[2];rep (i, 1, n) cin >> m, a[m & 1].pb(m);if (a[0].size() < a[1].size()) swap(a[1], a[0]);for (auto &i : a[0]) cout << i << ' ';for (auto &i : a[1]) cout << i << ' '; cout << '\n';}return 0;
}B - TMT Document
int main() {IOS;for (cin >> _; _; --_) {cin >> n >> s + 1; int x = 0, y = 0, z = 0;rep...
接近于死亡的选手没有水平更博客，所以现在每五个月更一篇。这道题呢，首先如果已经有权限升级了，那么后面肯定全部选的是 \(p_ib_i\) 最高的。设这个值为 \(M=\max \limits_i p_ib_i\)。主要的问题在于前面怎么选。假设剩下的时间还有 \(t\) 秒。那么我们很容易得到一个这样的式子。\[
dp[t+1] = \max_i \{p_i \cdot (a_i+tM) + (1-p_i) \cdot dp[t]\}
\]
把 \(\max\)里面的内容整理一下。\[
dp[t+1] = dp[t] + \max_i\{p_i\cdot(...
题目大意：
给一个串sss(下标从111到nnn),和一个变量ititit,初始为000.要你执行xxx次操作,求最后的串长度对109+710^9+7109+7取模的结果. 操作如下:
将it+1it+1it+1将剪贴板的内容替换为[it,n][it,n][it,n](nnn是当前的串的长度),并在原串中删除[it,n][it,n][it,n]在串的末尾把剪贴板内容粘贴sits_{it}sit? 次
题目思路：
靠。。。写的不能再傻逼了。
靠。。。我做法也太傻逼了。
看下正解：
考虑只会执行xxx次，所以先把前x长度的串...
传送门
题目大意
你会得到一个数组a，并且会有q个查询，给定两个数字i和x，将a[i]乘以x，输出每次查询后的数组a的gcd
题解
牛客的寒假训练营有一道比这个简单的同类型题，这里上个牛客的传送门，我们先考虑如果数组a没有被修改，应该怎么求他们的gcd，很显然，我们可以将每个数字进行质因子分解，这样数组a中所有数都有的质因子，一定就是他们的gcd的质因子。再考虑如果有修改会怎么样，如果a[i]乘x，将x也质因子分解，如果分解出的...
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5+10;
typedef long long ll;
ll t, n1, n2, n3;
ll a[N], b[N], c[N];
//分别固定一个数 设为a[i]
//然后从 b 和 c 中找一个小于等于他的 和 一个大于等于他的
//然后枚举每个数字的每个数
ll solve(ll a[], ll n1, ll b[], ll n2, ll c[] , ll n3)
{ll ans = 2e18, x, y, z;for(int i = 1; i <= n1; i++...
题意：首先定义了一种类数（标志数）1：1到9都是标志数。2：若x / 10是标志数，并且x的个位数小于x % 11, 那么x也是标志数。现在给你一个字符串，问有多少个子串代表的数字是标志数？思路：我们先假设已经求出的所有的标志数，并且知道每个标志数的rank(rank已经对11取模)。设dp[i][j]是第i个数字和第 i - 1位数字构成的2位数的rank为j，并且最高2位为这两位数字的合法数字的数目。可能有点拗口，我们举一个例子。假设字符串是321,...
题目大意
给定一棵 \(n(2\leq n\leq 5000)\) 个点的树，求一共有多少种方案，删去若干条边后，分裂出的所有树的直径都不超过 \(K\)，答案模 \(998244353\)。
题解
设 \(dp[u][i]\) 表示把以 \(u\) 为根的子树分裂成若干棵直径不超过 \(K\) 的树，且以 \(u\) 为根的树的高度为 \(i\) 的方案数。令 \(buf[u][i]\) 表示转移后的 \(dp[u][i]\)，则每遇到一个 \(u\) 的孩子 \(v\) 就有：
\[buf[u][i]+=dp[u][i]\times\sum_{j=0}^{k}dp[v...
题目链接：C. Swap Adjacent Elements题意：给你一个1~n的序列，然后一个n-1长的01串,为一代表可以和后面一个位置的数交换。问你能否通过交换是序列从小到大；题解：统计每个数字的位置p[i]，我们想要一个数字现能够回到原来的位置i必须max(i,p[i])-1到min(i,p[i])全部为一。我们用线段树或者前缀和。就可以快速判断一段是否全部为一（我用的是线段树），对于每一个不在原来位置上的数判断一次就好了，#include<bits/stdc++.h>
#in...
http://codeforces.com/problemset/problem/5/E众所周知，在很久以前，在今天的 Berland 地区，居住着 Bindian 部落。他们的首都被 n 座山所环绕，形成了一个圆形。在每座山上，有一名看守人，昼夜看守着相邻的山。万一出现了任何危险，看守人可以在山上点燃烽火。如果连接两座山的圆弧上，没有任何山高于这两座山中的任何一座，那么这两座山的一个看守人可以看见另一个看守人的信号。对于任意两座山，由于存在两条不同的圆弧连接着...
CodeForces-1178F1 Short Colorful Strip 区间DP
题意
给定\(0-n\) 一共 \(n+1\)种颜色，现有\(m\)段初始时刻颜色都是0的纸，对这张纸的段进行操作，第\(i\)次操作会选择第\(l\)段到第\(r\)段纸进行区间染色，条件是这段此时必须为同种颜色，染为\(i\)。给出最终的每一段的颜色，问共有多少种染色方案，注意本题中\(n = m\)且每种颜色都会在最终的段中出现
\[1 \leq n\leq500,n = m\1 \leq c_i \leq n
\]分析
做\(CF\)题自然要先挖...
很有趣的一道题，题解戳这。 1 #include <iostream>2 #include <cstdio>3 #include <cstring>4 #include <algorithm>5usingnamespace std;6 7constint maxn = 200000 + 10;8constint maxm = 1000000 + 10;910int a[maxn], f[maxm];
1112int main()
13{
14int n; scanf("%d", &n);
15for(int i = 0; i < n; i++) scanf("%d", a + i);
16 sort(a, a + n);
17 n = unique(a, a + n) - a;
1819int M = a[n-1];
20for(int i = 0...
