题目链接：https://codeforces.com/contest/999/problem/E题意：在有向图中加边，让$S$点可以到达所有点数据范围：$ 1 \leq n \leq 5000$分析： 先从$S$点出发，所有不可达点标记一下如果某个不可达点可以被另一个不可达点到达，那么把这个不可达点标记为可达最后计算不可达点的数量去年做过的题目，今年反而不会写了ac代码：#include <bits/stdc++.h> #define ll long long using namespace std; const int maxn = 5e3 + 5; ll mo...
用lucas定理， p必须是素数 对于单独的C(n, m) mod p，已知C(n, m) mod p = n!/(m!(n - m)!) mod p。显然除法取模，这里要用到m!(n-m)!的逆元。根据费马小定理：已知(a, p) = 1，则 ap-1 ≡ 1 (mod p), 所以 a*ap-2 ≡ 1 (mod p)。也就是 (m!(n-m)!)的逆元为 (m!(n-m)!)p-2 ；所以C(n, m) mod p = n! * (m! * (n - m)! )^(p-2)%mod中间用快速幂取余#include<map> #include<set> #include<cmath> #include<queue> #include<stack> ...
DescriptionBeing a programmer, you like arrays a lot. For your birthday, your friends have given you an array a consisting of n distinct integers.Unfortunately, the size of a is too small. You want a bigger array! Your friends agree to give you a bigger array, but only if you are able to answer the following question correctly: is it possible to sort the array a (in increasing order) by reversing ...
Codeforces Round #354 (Div. 2)Problems #Name ANicholas and Permutationstandard input/output 1 s, 256 MB x3384BPyramid of Glassesstandard input/output 1 s, 256 MB x1462CVasya and Stringstandard input/output 1 s, 256 MB x1393DTheseus and labyrinthstandard input/output 3 s, 256 MB x375EThe Last Fight Between Human and AIstandard input/output 1 s, 256 MB x58Complete problemset A Nicholas and P...
A. Crazy Town time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Crazy Town is a plane on which there are n infinite line roads. Each road is defined by the equation aix?+?biy?+?ci?=?0,where ai andbi arenot both equal to the zero. The roads divide the plane into connected regions, possibly of infinite space. Let‘s call each such region a b...
题目大意：给一个点阵，其中有的地方没有点，操作是去掉某个点，并询问当前点阵中最大的正方形若没有修改的话，裸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...