构造

c++--类型行为控制

1.c的类 1.1.c的类关键点 c类型的关键点在于类存在继承。在此基础上，类存在构造，赋值，析构三类通用的关键行为。类型提供了构造函数，赋值运算符，析构函数来让我们控制三类通用行为的具体表现。为了清楚的说明类的构…

【GDOI2018模拟9.17】永远的三日天下

Description 给出一个字符串，求解一个括号序，使得每对匹配的括号所在位置的字符都相等。使答案字典序最小。 n<4*1e6 Solution 了上克下行一这得使量力的邪正人鬼栋栋搬的吼题首先我们考虑先构造出一组可行解，这个显然可以用单调…

[CC Snack Down Final]STRSUM

Description 有n个非空字符串s1~sn，现将其两两连接在一起得到了n*(n-1)个字符串L1 ~Ln*(n-1) 给你L1~Ln*(n-1)，要你还原s1 ~ sn，有多解随便造一组即可 n<50,∑|Li|<10000 Solution 考虑将所有的Li和Si按长度为第一关键字&#xff0c…

牛客寒假算法基础集训营2_H处女座的测验（一）（数学、质数、构造）

题目链接：https://ac.nowcoder.com/acm/contest/327/H 题目描述： 处女座进行了一场c语言的考试，要求很简单，输出2000个正整数，并且满足以下条件： 1.任意两个数互质 2.任意两个数x,y，满足&am…

博弈论：gym104065j

https://vjudge.net/contest/587311#problem/J 我也不知道我在此题中学到了什么套路结论：你选的数必须尽量接近 s u m 3 \frac {sum} 3 3sum，然后这个就是解因为另外两人选的是和你的数相比不可能更接近，所以必然一个大一个小唯一的…

Codeforces Round 908 (Div. 1) D. Colorful Constructive(构造贪心)

题目 t(t<1e4)组样例， 每次给定一个数n(n<2e5)，代表有n个魔方，第i个魔方的颜色是ai(1<ai<n) n个魔方需要放在m(m<n)个架子上，使得第j个架子上恰好放了sj个魔方(sum sjn) 第i个架子的彩色度，定义为最…

洛谷 [AGC032B] Balanced Neighbors

分析首先明确图的定义，图点集边集，其中点必须要有一个，图不可以是空图。（虽然和这道题没关系） 正着想不明白那就反着来（正难则反）。假设目前所有边都是连上的，可以发现每个点的…

牛客练习赛51，C（思维/构造）

贴题解： 对小范围数据进行打表，即可发现存在以下规律： 1.当n>2时总有方法可以构造 2.当n是奇数总存在两条边b,c使得c-b1并且n2b2c^2 3.当n是偶数总存在两条边b,c使得c-b2并且n2b2c^2 因此我们可以设边cx,分n是奇数和偶数的情况&#xff0c…

【每日一题】补档 AGC015D A or...or B Problem | 构造 | 困难

题目内容原题链接给定一个区间 [ A , B ] [A,B] [A,B] ，从中选出两个数 x x x 和 y y y ， x x x 可以等于 y y y ，问 x x x 或 y y y 的结果可以得到多少个不同的数。数据范围 0 ≤ A ≤ B < 2 60 0\leq A\leq B<2^{60} 0≤A…

Codeforces Round 761 (Div. 2) D2. Too Many Impostors (hard version)(交互+构造最小次数)

题目 n(6<n<1e4，n是3的倍数)个人，其中k个人是好人，n-k个人是坏人 k是未知的，但保证1/3n<k<2/3n，你可以询问若干次， 每次你可以选择三个不同的人a,b,c，系统告诉你这三个人中好人更…

Avito Cool Challenge 2018 F. Tricky Interactor(交互构造)

题目长为n(n<300)的01串，初始情况下总共有t(t<n)个1 你可以询问若干次， 当你询问的区间为[L,R]时，系统会等概率地从[L,n]和[1,R]里选取一个， 将区间的01翻转，翻转操作是可持久化的，即第i次的翻转…

codeforces 1475 F Unusual Matrix （构造）

题面题意给你 a , b 两个矩阵，问通过翻转（0变1，1变0）能否使a变成b翻转必须是整行或者整列翻转思路像这种翻转题，一般先看规律，我们会发现，每行或每列只需要翻转0或者1次，因为翻转…

1400*C. Element Extermination（贪心规律）

Problem - 1375C - Codeforces 解析： 可以发现，最左端的数字，无论删除自己还是下一个，这个位置的值都不会变小。同理，最右端位置的值都不会变大。所以当最后剩余两个数字的时候，只有左端小于右端数字&…

排列置换环上构造：1025T3

http://cplusoj.com/d/senior/p/SS231025C 排列构造的新知识：上置换环！ 我们发现朴素做法是 n 2 n^2 n2 级别的，但数据范围希望我们是 n 2 2 \frac {n^2}2 2n2 级别的。我们发现我们暴力复制序列显得非常蠢，因为很多序列前后…

CodeForces 906B Seating of Students【dfs】

题解给出了一个比较巧妙的构造的方法，但是这个题也可以直接dfs去做，只考虑不与前面的安排好的左边以及上面的数有相邻，那么就可以往下一直dfs，但是我们感觉这样的复杂度可能有一点问题，但是能够过，但是大数…

codeforces 1485 D Multiples and Power Differences （构造）

题面题意题解 A矩阵中元素最大是16，那么我们直接找一个小于1e6，而且是它的因子包含A中所有元素，这样就可以满足前两个条件，直接 16 ！是会超出1e6 的，所以我们要找lcm{1,2,3,4,5,…16}, 算出的最小公倍数满…

2019牛客暑期多校训练营（第六场）E Androgynos（构造+思维+图的同构）

链接：https://ac.nowcoder.com/acm/contest/886/E 题意：T组样例。每组样例给一个n，问能否构造一个图，使得其和其补图同构。能就输出“Yes”，并输出图的邻接矩阵和同构的映射函数，不能就输出“No”。思路…

Educational Codeforces Round 163 (Rated for Div. 2)（A,B,C,D,E）

比赛链接好忙好忙好忙，慢慢补老比赛的题解了。这场没啥算法，全是思维。有也是BFS，屎。 A. Special Characters 题意： 您将得到一个整数 n n n 。您的任务是构建一串大写的拉丁字母。此字符串中必须正好有 n n n 个特殊字…

AcWing第81 82 83场周赛总结

第81场周赛希望我下次不用再写这种东西这次比赛被国强打爆，希望下次可以有所进步。 T2：等差数列这其实是一个暴力，但是由于参加CSP与NOIp，对于题目的难度想象过高，想的过于复杂，用了个差分的方法&#x…

[AGC018F]Two Trees

Description 给出两棵有根树，需要给每个点确定点权，使得两棵树中每个子树的权值和的绝对值为1 n<100000 Solution 构造好题，本来打算讲杂题但是出到模拟赛就直接写了设第一棵树为1~n，第二棵树为n1 ~ 2n 首先我们可以确定每…

1400*C. Team（模拟构造）

Problem - 401C - Codeforces 解析： 因为0不能相邻，所以0之间最少 n-1 个位置，最多 n1 个位置，如果 m<n-1显然不符题意。并且1最多连续两个，所以 m>2*n2 同样不符题意。其余情况构造即可 #include<bits/st…

[bzoj2528][POI2011]Periodicity

Description 给出一个字符串S，定义pre(S)为S的所有周期的集合。求一个字典序最小的01串，使得这个01串的周期集合和pre(S)相同。 n<200000 Solution 神仙构造题，波兰题怎么都这么仙啊给出结论：周期<>border&#…

[51nod1479]小Y的数论题

Description 给出a,b,c，在区间(0,m)中间选择三个整数x,y,z，使得xayb≡zc(modm)a,b,c<10^9 数据组数<10^5Solution 一些神奇的算法。既然我们只需要构造出一组解，那不妨往最特殊的方面去想。众所周知2a2a2a1然后，2abk2…

2019牛客暑期多校训练营（第四场）D triples I（构造+思维）

链接：https://ac.nowcoder.com/acm/contest/884/D 题意：T组样例。每组样例给出一个a（1<a<1e18），让用尽可能少的3的倍数，使这些数按位或起来的值为a。题目保证输入的a一定有答案。思路：…

2019牛客暑期多校训练营（第八场）C CDMA（构造）

链接：https://ac.nowcoder.com/acm/contest/888/C 题意：给出一个数m（m是2的多少次方）。构造一个m*m的矩阵，元素只能取{-1,1}，使得任意两行的同列的数的乘积的和为0。思路：样例给出2*2的矩阵&…

石油大 Contest1789 - 2019年第二阶段我要变强个人训练赛第十二场 B: Balanced Neighbors（构造）

问题 B: Balanced Neighbors 时间限制: 1 Sec 内存限制: 128 MB 提交: 83 解决: 43 [提交] [状态] [命题人:admin] 题目描述 You are given an integer N. Build an undirected graph with N vertices with indices 1 to N that satisfies the following two conditions: …

杭电2019多校第四场 HDU-6616 Divide the Stones （构造+思维）

链接：http://acm.hdu.edu.cn/showproblem.php?pid6616 题意：T组样例，每组样例给出n和k（保证k是n的因子）。有n堆石子，第i堆有i个石子。问能否把这n堆石子分成k组，并且每组的石子和相等。&#…

c++11 标准模板（STL）（std::priority_queue）（二）

适配一个容器以提供优先级队列 std::priority_queue 定义于头文件 <queue> template< class T, class Container std::vector<T>, class Compare std::less<typename Container::value_type> > class priority_queue; priority_queu…

$AtCoder Regular Contest 163 C. Harmonic Mean(构造补写法)$

AtCoder Regular Contest 163 C. Harmonic Mean(构造补写法)

题目 t(t<500)组case， 给定一个数n(n<500)，构造一个长为n的数组思路来源官方题解题解注意到 ... 所以， 1. 当n没有在前面的序列里出现过时，可以用(2,6,12,...,n)来构造一组解 2. 当出现过时，例如当n…

23.8.14 牛客暑期多校9部分题解

G - Non-Puzzle: Game 题目大意一开始有 n n n 个数，Alice和Bob轮流操作，每次操作可以选择任意两个数（可以是同一个数）进行异或并添加到数组中，谁在一次操作后得到的数为 k k k 谁就获胜，问最后谁赢或…

用欧拉路径判断图同构推出reverse合法性：1116T4

http://cplusoj.com/d/senior/p/SS231116D 假设我们要把 a a a 变成 b b b，我们在 a i a_i ai 和 a i 1 a_{i1} ai1 之间连边， b b b 同理，则 a a a 能变成 b b b 的充要条件是两图 A , B A,B A,B 同构。必要性显然&#xff0…

【NOI2018模拟3.10】子序列

Description 求一个序列的所有2^n-1个子序列的字典序前k小的哈希值。 n,k<1e5 Solution 这道题专门狙杀我这种老年菜鸡我们考虑一种从旧的子序列扩展出新的子序列的方法。对于一个子序列，我们肯定是找到它后面第一个比它小的位置来扩展。我们把一样的子…

分治构造：P9384

https://www.luogu.com.cn/problem/P9384 分治构造是很常见的一种构造不能有三元环和五元环，考虑推广出去，也就是不能有奇环那如果我们让每种颜色都为二分图，那么必然满足考虑 0-9 总共10个数字，数据范围1000，考…

牛客寒假算法基础集训营4_B-Applese 走方格(构造)

题目链接：https://ac.nowcoder.com/acm/contest/330/B题目描述精通程序设计的 Applese 又写了一个游戏。在这个游戏中，它位于一个 n 行 m 列的方阵中的左上角（坐标为(0, 0)，行的序号为0∼n−10∼n−1，列的序号为0∼m…

1000*A. Little Artem（构造）

Problem - 1333A - Codeforces 解析： 只需要在左上角放一个白色，其余都放黑色即可满足条件。 #include<bits/stdc.h> using namespace std; int t,n,m; signed main(){scanf("%d",&t);while(t--){scanf("%d%d",&n,&…

限制条件加入构造范围：Gym - 102832L

https://vjudge.net/contest/587311#problem/D 场上列方程求首项，假设是全部加1，然后一部分（后缀）减去 k 1 k1 k1，就用到了以下两个条件： 但在这两种情况符合情况下，这个条件不一定满足然后…

$Codeforces Round 788 (Div. 2) E. Hemose on the Tree（树上构造）$

Codeforces Round 788 (Div. 2) E. Hemose on the Tree（树上构造）

题目 t(t<5e4)组样例，每次给定一个数p， 表示一棵节点数为的树， 以下n-1条边，读入树边对于n个点和n-1条边，每个点需要赋权，每条边需要赋权， 权值需要恰好构成[1,2n-1]的排列并且当你赋…

1300*C. Social Distance（贪心构造）

Problem - 1367C - Codeforces 解析： 统计出所有连续0序列，并且记录其左右两侧有没有1，然后对于四种情况分别判断即可。 #include<bits/stdc.h> using namespace std; int t,n,k; signed main(){scanf("%d",&t);while(…

$AGC056A - Three Cells per Row and Column$

AGC056A - Three Cells per Row and Column

【题意】给定一个n*n的矩阵，请构造出一种黑白染色方式，使得每行每列均恰好有3个黑色，且总共的黑色连通块数是n 【分析】这是一个不是很好想的构造方式，首先考虑n是3的整数倍的情况直接按照如下方式即可： 当其不…

hdu 5916 Harmonic Value Description 2016ACM/CCPC长春赛区现场赛F

Problem DescriptionThe harmonic value of the permutation p1,p2,⋯pnis∑i1n−1gcd(pi.pi1)Mr. Frog is wondering about the permutation whose harmonic value is the strictly k-th smallest among all the permutations of [n].InputThe first line contains only one i…