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...
补题链接：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.
类似筛素数的方法……求出前缀和。然后直接O(1)回答即可。 1 #include <bits/stdc++.h>2 3usingnamespace std;4 5#define rep(i,a,b) for(int i(a); i <= (b); ++i)6 7constint N = 10000000 + 10;8 9int num[N]; 10bool p[N]; 11int T, n, m; 1213int main(){ 1415 memset(p, true, sizeof p); 16 memset(num, 0, sizeof num); 1718 p[1] = false; 19 rep(i, 2, N - 6) if (p[i]...
题意：解法： lc=lcm(1,2,3,...16)<1e6.由于限制条件是对相邻格子设立的, 对矩阵黑白染色,那么相同颜色就不会互相影响了, 之后将黑色位置设为lc,白色位置设为lc+a[i][j]^4即可, 显然这样一定满足条件.code： #include <bits/stdc++.h> #define int long long using namespace std; const int maxm=500+5; int a[maxm][maxm]; int n,m; int lcm(int a,int b){return a/__gcd(a,b)*b; } int cal(int x){return x*x*x*x; } inline voi...