题目网址：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(...
传送门 题目大意 你会得到一个数组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++...
题目链接：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...
补题链接：Here 1512A - Spy Detected! 题意：找到唯一不同数的下标 复制数组然后比较 \(a_1\) int main() {ios_base::sync_with_stdio(false), cin.tie(0);int _;for (cin >> _; _--;) {int n;cin >> n;vector<int> v(n);for (int &e : v) {cin >> e;}vector<int> a = v;sort(a.begin(), a.end());for (int i = 0; i < n; i++) {if (v[i] != a[1]) {cout << i + 1 << "\n";}}}return 0; }1512B - Almost Rectangle 题意：给定 \(n...
Assume that the array of speeds is sorted, i.e.
题目： 思路： 这个题很像之前做过一个向篮子里面丢方块看最少能丢几层的题 我们分析样例模拟入塔过程 每次放进去一个块都想让所有塔的极差在一定范围内 所以我们建一个堆存放所有的塔高 走h数组 每次把当前方块丢到最低的塔中来稳固极差并记录当前丢到了哪个塔里面 如果丢进去极差>k，就NO 否则走完后按顺序输出每个方块丢到了哪个塔 代码： #include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #inclu...
A. Average Height 题意：设定两个相邻的整数相加之和能被2整除的数为“上镜”，求最多连续的“上镜”数。 思路：把奇和偶分开输出即可，相邻的奇数或者偶数一定是上镜。 #include <bits/stdc++.h> #define llt long long using namespace std;bool cmp(int p,int q) {return p%2<q%2; } int te,n,a[2010];int main() {cin.tie(0);ios::sync_with_stdio(false);cin>>te;while(te--){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];sort(a+...
题意：已知 n 所城市（从 1 至 n 编号）及其美丽值，选取一条旅行路线，满足路线中两两城市美丽值之差等于编号之差，求所有旅行路线中美丽值的最大值。思路：美丽值与编号作差，差值为键，映射累加 。 #include <bits/stdc++.h> usingnamespace std; int main() {int n;cin>>n;int b[n];for(int &i:b) cin>>i;map<int,longlong> _map;for(int i=0;i<n;i++)_map[b[i]-i]+=b[i];longlong mx=0;for(auto &i:_map)mx=max(mx,i.second);...
https://codeforces.com/contest/1153/problem/D题意一颗有n个点的数,每个点a[i]为0代表取子节点的最小,1代表取最大,然后假设树上存在k个叶子,问你如何将1~k分配给叶子节点使得根节点最大题解实际上最后只有一个值能到达根,我们需要计算没用的叶子节点数量min:相当于将子节点叶子数量相加max:相当于将子节点叶子数量取最小ans=叶子数-sz[1]+1代码#include<bits/stdc++.h> #define MAXN 300005 using namespace std; vector<int>G[M...