A. Treasure time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Malek has recently found a treasure map. While he was looking for a treasure he found a locked door. There was a string s written on the door consistingof characters ‘(‘, ‘)‘ and ‘#‘.Below there was a manual on how to open the door. After spending a long time Malek manage...
题意：解法： 发现数位和与数的顺序无关,只和每种数位的个数有关.枚举a的个数i,判断i个a和(n-i)个b组合能否是极好的数, 如果是,那么答案累加C(n,i).code： #include <bits/stdc++.h> #define int long long using namespace std; const int maxm=2e6+5; const int mod=1e9+7; int fac[maxm],inv[maxm]; int ppow(int a,int b,int mod){int ans=1%mod;a%=mod;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans; } void in...
题目链接给出一个图， 每个节点只有三种情况， a，b, c。 a能和a, b连边， b能和a, b, c,连边， c能和b, c连边， 且无重边以及自环。给出初始的连边情况， 判断这个图是否满足条件。 由题意可以推出来b必然和其他的n-1个点都有连边， 所以初始将度数为n-1的点全都编号为b。 然后任选一个与b相连且无编号的点， 编号为1. 然后所有与1无连边的点都是3.然后O（n^2)检查一下是否合理。#include <iostream> #include <vector> #include ...
Recently Luba bought a monitor. Monitor is a rectangular matrix of size n?×?m. But then she started to notice that some pixels cease to work properly. Luba thinks that the monitor will become broken the first moment when it contains a square k?×?k consisting entirely of broken pixels. She knows that q pixels are already broken, and for each of them she knows the moment when it stopped working. Hel...
A. GCD Sum 题目描述 设 \(s(i)\) 为 \(i\) 的数位和，求第一个 \(\geq n\) 满足下式的 \(x\)： \[\gcd(x,s(x))>1 \]\(1\leq n\leq 10^{18}\)，数据组数不超过 \(10^4\) 组 解法 一开始没想法，然后打了个爆搜过掉了。 根据小学奥数可知若 \(x\) 为 \(3\) 的倍数则 \(\gcd(x,s(x))=3\)，所以就算是爆搜也只需要搜三次。 B. Box Fitting 题目描述 点此看题 解法 又猜了结论，就是能填大的就暴力填大的。 证明就考虑如果某次放弃了填...
题意略。思路：对于随机产生的一个数列，对于某个儿子，其兄弟在其前面的概率为 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...