题意：牛牛最近得到了一颗树，根是 1 号节点，他想要把这颗树染色。每个节点可以染成白色和黑色，牛牛认为一种染色方案是好的当且仅当任意两个黑点的 lca（最近公共祖先）的颜色也是黑色的。求一共有多少种好的染色的方案。答案 mod(1e9+7).分析：  树形dp.考虑当前节点为根节点的子树方案数，dp[u][0]为选择当前点进入集合的方案,dp[u][1]为不选择当前点进入集合的方案. 那么考虑转移.对于当前节点dp[u][0]方案，当前节点为黑色的方案，那么子节点方案都合法.转移方程：    对于dp[u][1]方案数,当前节点为白色，那么子节点不能同时选，那么转移方程：减一是因为子节点方案中...

大致题意:自行看题.分析:打表前10秒的情况，发现就是n次多项式系数问题.手推规律 t秒合法答案: C[t-x][y]*C[t][x]. 然后再判断一下没有感染的情况---( x+y>t ). #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+10; const int mod=998244353; ll qpow(ll a, ll b)// 快速幂 { ll ans = 1; a = a % mod; while (b) { if(b & 1) ...

题目大意:给定n个点m无向边，求该图和图的补图是否有度数为3的环.分析：比赛时疯狂讨论边情况...wa自闭了正确题解:  拉姆塞结论--点数超过5的图和对应补图必有度数为3的环.不会证明(只会举例子) 那么点数少于6的图直接暴力找环即可.  #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=20; const int mod=998244353; bool mp[maxn][maxn]; int main() { int t; cin>>t; while( ...

题面  #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 inv_2=mod-mod/2; int n; int a[maxn]; int q,op,x,y,z,v; struct seg{ #define ls cur<<1 #define rs cur<<1|1 int sum[maxn<<2],lx[maxn<&lt...

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 如例子一样迭代k次.求p最小长度满足p集合内点成一个环并且颜色相同.( a数组的元素是1~n的全排列 ) (n<=1e5 )分析:可以从a数组元素得知，图最终是某m个不相交的环(简单证明可得)，那么我们只需要枚举所有的环，然后假设第i个环的长度是k,根据迭代关系，我们只要枚举k的因子进行che...

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<=n<=500,k<=min{ |S(n)|,1e12} )  分析:  我们可以处理出长度<=1e12的字符串一共57个 我们可以直接对长度进行dfs分治求pos位置.需要注意的是n>56时，前缀字符串跟n的奇偶性有关.  #include<bits/stdc++.h...

矩阵消除游戏  https://ac.nowcoder.com/acm/contest/4784/Ahttps://ac.nowcoder.com/acm/contest/4090/Chttps://ac.nowcoder.com/acm/contest/890/F

C.Ehab and Path-etic MEXs 题意：给定一n个结点的树，请将0-n-2标在n-1条边上，定义MEX(u,v)为u到v路径没有出现数字的最小值,求一个最优的标号方案满足MEX(u,v)和为最小(n<=1e5).分析：取一个度数最大的点，将该点所有的边以0开始依次标号，可以证明所有不经过该点的MEX的值为0，经过该点的MEX值可能为0,1,2. #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+10; vector<int> ...

A.The power of Fibonacci 大致题意：给定n,m,求斐波那契数列前n项m次幂 和.分析：本来有三种做法，题解做法不会.第一种找循环节.  对于线性递推式本来可以根据求通项求得,但是5在1e9下不存在二次剩余. 换一种思路,易知在模意义下斐波那契数列的循环节和次幂的循环节是一样的，原数是循环的那这个数的次幂也是循环. 但是模数为1e9,如果直接找1e9的循环节,发现循环节大小为1e9+5e8,显然不可行. 我们将1e9进行素数拆分成2^9和5^9,两个模数,可以列出关于答案在模512和 1953125 下的同余方程组.{ x===a1%512, y===a2%1953125...

本场总结： A.单调栈B.区间贡献C.构造D.三维树状数组----维护曼哈顿距离E.线段树区间维护dfs并查集撤销G.签到I.树上差分和树状数组区间差分J.组合数学和dp  小结：---矩阵中子矩阵问题 单调栈继续练---构造先蒙---学习三维树状数组如何维护，后缀最小值转前缀最大值---学习线段树维护区间交，dfs并查集撤销---树上dfs序差分和区间交贡献差分---组合数学复习经典不定方程解个数C(n+m-1,n-1) 和容斥运用  A.All-one Matrices 大致题意：n×m的01矩阵中求极大全1子矩阵的个数.极大全1子矩阵的定义:不被其他全1矩阵所包含.分析：  首先我们可以...

A. City 大致题意:n*m的网格，求有多少线段----线段满足两端点在网格点上，并且线段中点在网格点上.分析:暴力统计，偶数边的数量。 #include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { int n,m; scanf("%d%d",&n,&m); ll ans=0; n++; m++; for( int i=1;i<=n;i++ ) { for( int j=1;j<=m;j++ ) { ans+=((j-1)/2)*((n-i)/2); a...

本场总结: A.模拟暴力B.猜结论C.贪心D.签到E.离散化+树状数组+二分 ----插入区间元素找中位数H.数位dpJ.签到  小结:----多项式可约问题，三次多项式实数范围内可约.二次多项式根判别式.----注意数据范围再贪心，一般比较小的值作为索引进行贪心.----插入区间元素可以用两个树状数组维护，查找中位数一般就是二分----练习数位dp  A. String 大致题意:给定一个01串，请把它划分为尽量少的子串，每个子串是该子串循环移位的字典序最小的串.分析：暴力找就行，check判断. #include<bits/stdc++.h> using namespace s...

总结： B.字典树和暴力D.构造题E.建最大生成树F.树链剖分H.二分答案和树上dfsK.二分图和二进制枚举  小结：----构造难顶，还要多搞搞----练习最大生成树----终于遇到一道icpc树链剖分，熟悉了一下线段树推标记----二分答案----二分图练得少，运用好多啊，还能判奇偶环....  B. Prefix Code 大致题意:给n个字符串，判断是否可以根据字符串前缀进行识别所有字符串。分析：字典树和map暴力都行,给的字符串长度最多10,首先所有字符串有相同的肯定输出 No, map暴力处理出每个字符串的前缀判断是否出现过. #include<bits/stdc++.h&g...

本场总结： A.签到B.模拟C.回文树D.猜结论checkE.构造G.全排列和蔡勒公式check----O(1) 判断星期几J.前缀和dp  小结----练构造----回文树就是个**板子选手，还要再学----构造想法----学到了蔡勒公式----练dp  A. Garbage Classification 大致题意：就不分析了，签到题. #include<bits/stdc++.h> using namespace std; int vis[27]; char s1[2005],s2[27]; int main() { int t,opt=1; cin>>t; whi...