题目大意：给一个点阵，其中有的地方没有点，操作是去掉某个点，并询问当前点阵中最大的正方形若没有修改的话，裸dp加上修改，可以考虑时光倒流，这样答案就是递增的可以用并查集维护点的连通性，O^2的#include<bits/stdc++.h> usingnamespace std; #define maxn 2010 inline void MIN(int &a,int b){if(a>b)a=b;} inline void MAX(int &a,int b){if(a<b)a=b;} int n,m,q,sz; int f[maxn][maxn],u[maxn][maxn],lg[maxn],rg[maxn],q...
【题目】B. Restoration of string【题意】当一个字符串在字符串S中的出现次数不小于任意子串的出现次数时，定义这个字符串是高频字符串。给定n个字符串，求构造出最短的字符串S满足着n个字符串都是高频字符串，若不存在输出NO，若存在多个输出字典序最小的一个。n<=10^5，Σ|si|<=10^5。【算法】模拟（图论？字符串？）【题解】首先出现频率都是1次，多次没有意义，所以每个字母至多出现一次。那么对于出现在n个字符串中的子串ab，...
<题目链接>题目大意：给定一棵树，给每条边染色，如果一个结点的两条边是相同颜色的，那么这个结点就是不满意的。现在要求颜色最少的染色数，使得不满意结点数量<=k。解题分析：首先，贪心地想，因为题目允许有最多k个不满意的点，所以我们将所有点的度数从大到小排个序，度数第k+1大的点的度数就是最少的染色数。然后，主要就是给出染色的方案了，我们可以用DFS对整棵树的所有边进行染色，同时，染色的过程中，还要尽可能地保证所...
A题：由题意可知，最多翻10次就可以（其实8次就够了），那么我们就用状态压缩表示状态。对于某种状态，如果某一位为0，那么代表这一位不翻，否则代表这一位翻。对于某一种翻的状态：如果牌中有G3，那么就把G和3进行连边。其他的连边类似，不要重边。对于任意一条边的两个端点，分三种情况讨论：1，两个端点都翻了，那么很明显，这张牌被表示出来了。2，两个端点中只有一个端点被翻，那么这个对应的num加1.3，两个端点都没有被翻，计...
题面传送门分析考虑DP设\(dp[i][j]\)表示前i个数选出的序列长度为j的方案数状态转移方程为:\[ dp[i][j]= \begin{cases}dp\left[ i-1\right] \left[ j-1\right] +dp\left[ i-1\right] \left[ j-1\right] ,j \equiv 0 (\mod i) \\ dp\left[ i-1\right] \left[ j-1\right],otherwise \end{cases} \]如果二维DP，直接从1~n枚举i,j,显然会MLE发现第一维状态i只和i-1有关，考虑用类似01背包的方法去掉一维设dp[j]表示长度为j时的状态第i-...
D. Cutting Out题目链接：https://codeforces.com/contest/1077/problem/D题意：给你n个数，现在要你选k个数出来，并且能够从这n个数种选取尽量多的这k个数。 题解：一开始想的贪心+模拟，然后写崩了...其实这个题二分一下选几组就好了，因为要选几个数是固定了的，所以我们可以用二分来判断可行性（根据二分的x和每个数出现的次数来判断），即是否可以选够k个数，这个很容易办到。然后最后统计一下每个数出现的个数，最后无脑选输...
题目网址：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++...