18duangduang

题解

未归档(23) 计算几何(1)

/ 注册

全部文章 / 题解（共71篇）

牛客练习赛62 C.牛牛染颜色

题意：牛牛最近得到了一颗树，根是 1 号节点，他想要把这颗树染色。每个节点可以染成白色和黑色，牛牛认为一种染色方案是好的当且仅当任意两个黑点的 lca（最近公共祖先）的颜色也是黑色的。求一共有多少种好的染色的方案。答案 mod(1e9+7).分析：树形dp.考虑当前节点为根节点的子树方案数，dp...

树形dp lca

2020-04-25

0 860

牛客练习赛62 B. 病毒扩散

大致题意:自行看题.分析:打表前10秒的情况，发现就是n次多项式系数问题.手推规律 t秒合法答案: C[t-x][y]*C[t][x]. 然后再判断一下没有感染的情况---( x+y>t ). #include<bits/stdc++.h> using namespace std;...

打表找规律 n次多项式系数

2020-04-25

1 1201

牛客练习赛62 A.牛妹的游戏

题目大意:给定n个点m无向边，求该图和图的补图是否有度数为3的环.分析：比赛时疯狂讨论边情况...wa自闭了正确题解: 拉姆塞结论--点数超过5的图和对应补图必有度数为3的环.不会证明(只会举例子) 那么点数少于6的图直接暴力找环即可. #include<bits/stdc++.h>...

2020-04-25

0 560

线段树维护等差数列

题面 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+10; const int mod=3*5*7*11*13*17*19*23; const int i...

线段树维护等差数列标记

2020-04-20

1 613

Educational Codeforces Round 84 (Rated for Div. 2) 来自专栏

D - Infinite Path 题意：给定n个点,a数组，b数组.a[i]表示点 i - > 点a[i] 有一条有向边,b[i]表示边的颜色.定义：p^1=[ a[1],a[2],a[3]...a[n] ],p^2=[ a[a[1]],a[a[2]],....,a[a[n]] ],p^k ...

差分数组 dp 最小环

2020-03-25

0 665

牛客多校赛第十场总结来自专栏

B. Coffee Chicken 大致题意： S(1)="COFFEE"; S(2)="CHICKEN"; S(n)=S(n-2):S(n-1)----即第n-2个字符串作为前缀，第n-1个字符串作为后缀.T组询问,求第n个字符串中第k个位置的字符.(1<=T<=1000,1&...

字符串hash 二分check CRT板子贪心计算几何斜率暴力

2020-03-23

0 911

Codeforces Round #628 (Div. 2) 来自专栏

C.Ehab and Path-etic MEXs 题意：给定一n个结点的树，请将0-n-2标在n-1条边上，定义MEX(u,v)为u到v路径没有出现数字的最小值,求一个最优的标号方案满足MEX(u,v)和为最小(n<=1e5).分析：取一个度数最大的点，将该点所有的边以0开始依次标号，可以证...

xor 二分图最独立集最小环

2020-03-15

1 778

牛客多校赛第九场总结来自专栏

A.The power of Fibonacci 大致题意：给定n,m,求斐波那契数列前n项m次幂和.分析：本来有三种做法，题解做法不会.第一种找循环节. 对于线性递推式本来可以根据求通项求得,但是5在1e9下不存在二次剩余. 换一种思路,易知在模意义下斐波那契数列的循环节和次幂的循环节是一样的...

斐波那契数列杜教BM 并查集折半搜索二进制枚举主席树边界标记小技巧扫描线

2020-03-03

0 655

牛客多校赛第八场总结来自专栏

本场总结： A.单调栈B.区间贡献C.构造D.三维树状数组----维护曼哈顿距离E.线段树区间维护dfs并查集撤销G.签到I.树上差分和树状数组区间差分J.组合数学和dp 小结：---矩阵中子矩阵问题单调栈继续练---构造先蒙---学习三维树状数组如何维护，后缀最小值转前缀最大值---学习线段树...

树上差分线段树单调栈构造三维树状数组区间交贡献并查集组合数容斥 dp

2020-02-24

0 708

The 2019 ICPC Asia-East Continent Final 补题总结

A. City 大致题意:n*m的网格，求有多少线段----线段满足两端点在网格点上，并且线段中点在网格点上.分析:暴力统计，偶数边的数量。 #include<bits/stdc++.h> using namespace std; typedef long long ll; ...

楼梯灌水问题二分答案check 二进制枚举

2020-02-19

0 1036