题意略。思路:对于随机产生的一个数列,对于某个儿子,其兄弟在其前面的概率为 1 / 2。所以这个兄弟对期望的贡献为son[v] / 2,所有兄弟加起来即为(tot - 1) / 2。 详见代码:#include<bits/stdc++.h>
usingnamespace std;
constint maxn = 1e5 + 5;int son[maxn],n,fa;
vector<int> graph[maxn];
double ans[maxn];void dfs(int cur){son[cur] = 1;for(int i = 0;i < graph[cur].size();++i){int v = graph[cur][i];dfs(v);son[c...
心得:打这个比赛的时候由于读题,自己变成一个大傻逼了,反思了一晚上 ,确实还是自己做的不够好,下面我口胡一篇自己的对于这几个题的解答。
比赛地址传送门
开始了: A题意:给出长度为N 的数组和可以操作的最大次数,然后要求你找出 非负的最小的数组字典序,然后有一个操作,选择一个数组+1,一个数组-1,直到找到最小字典序,或者操作做完。
题解:直接就是把所有的数字[1–n-1]这个范围的数字依次减 然后+到第N个数上,特别...
847E - Packmen思路:二分时间。代码: #include<bits/stdc++.h>
usingnamespace std;
#define ll long long
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
int n;
string s;bool check(int t)
{int now=-1,bean=-2;//now是上一个P覆盖到的位置,bean是没有被上一个P覆盖到的第一个星星 for(int i=0;i<n;i++){if(s[i]==‘*‘){if(bean<=now)bean=i;}elseif(s[i]==‘P‘){if(now<bean){if(i-bean>t)returnfalse;el...
题目大意:给定一个区间[l,r]/**/,你需要在这个区间中选择最多k/**/个不同的数,使得异或和最小当r?l+1≤4/**/时,暴力枚举集合即可
当r?l+1≥5/**/时,讨论:
若k≥4/**/,则[l,r]/**/中一定存在一组数为2k,2k+1,2k+2,2k+3/**/,故答案为0
若k=1/**/,则只能取l/**/
若k=2/**/,则只能取2k,2k+1/**/,异或值为1
若k=3/**/,由于我们可以只取2k,2k+1/**/,因此答案上界不会超过1
我们只需要判断能否在[l,r]/**/区间内找到3个...
DescriptionPolycarpus loves hamburgers very much. He especially adores the hamburgers he makes with his own hands. Polycarpus thinks that there are only three decent ingredients to make hamburgers from: a bread, sausage and cheese. He writes down the recipe of his favorite "Le Hamburger de Polycarpus" as a string of letters ‘B‘ (bread), ‘S‘ (sausage) и ‘C‘ (cheese). The ingredients in the r...
题目链接: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-...