【牛客练习赛62】
A、牛妹的游戏
题目描述：
在二维空间上有若干个点，有两队（蓝方和绿方），每队都可以占边。
而当有其中一队占的边有可能有三条首尾相连就输出"yes"，否则输出"no"。
思路：
1.拉姆塞结论--点数超过5的图或者对应补图必有度数为3的环.不会证明(只会举例子)
2.由1知当n大于5时输出“yes”，只要判断n<=5的情况，数据较小，可以直接爆搜，任取三条边判断是否成环。
3.成环的依据就是如果三条边都别蓝方占领，那么就会形成蓝色三角形，如果都没被蓝方占领，那么就有可能被绿方占领，形成绿边。
Code：
#include<bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &res) {
char c; T flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = -1;
res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
res *= flag;
}
inline void noread() {
char c;
while ((c = getchar()) < '0' || c > '9');
while ((c = getchar()) >= '0' && c <= '9');
}
int t,n,m,x,y;
int edge[10][10];
int main() {
read(t);
while(t--) {
read(n),read(m);
if(n>5) {
for(int i=0;i<m;++i) noread(),noread();
puts("yes");
continue;
}
memset(edge,0,sizeof edge);
for(int i=0;i<m;++i) {
read(x),read(y);
edge[x][y]=edge[y][x]=1;
}
bool flag=true;
for(int i=1;i<=n&&flag;++i)
for(int j=i+1;j<=n&&flag;++j)
for(int k=j+1;k<=n&&flag;++k) if(edge[i][j]==edge[j][k]&&edge[j][k]==edge[k][i])
flag=false;
if(flag) puts("no");
else puts("yes");
}
} B、病毒扩散
题目描述：
一个二维平面，从左下角开始病毒扩散，每一个时刻每个感染点可以传上右两个点，使其+1。
求某一点在某一时刻的感染数。
思路：
列举前4秒的表找规律（关键是当时我表都写不出来，虽然江大佬给我们看了表也说是杨辉三角，但是当时没感觉（江大佬tql））
第1秒： 第二秒：1x1
1 2x1 1x2
1 1 1x1 1x2 1x1
第三秒： 第四秒：1x1
1x1 4x1 1x4
3x1 1x3 6x1 3x4 1x6
3x1 2x3 1x3 4x1 3x4 2x6 1x4
1x1 1x3 1x3 1x1 1x1 1x4 1x6 1x4 1x1
观察 'x' 左边的数字，正确的阅读方式是从右往左看，你会发现这是个杨辉三角，比赛时江大佬一直说是杨辉三角，可能我太菜了没懂大佬意思，所以 'x' 左边的数字为 (x,y都是从0开始)。
然后 'x' 右边的数字就更简单了，列数相同 'x' 右边的数字就相同，每一列 'x' 右边的数字等于杨辉三角第t层第y列的数字，也就是 。
快速求组合数：知道公式 后，先预处理求出1 ~ n的阶乘
，再等需要的时候利用公式求直接求出，因为在做除法时是不能上下取余的，所以要改除一个数为乘一个数的逆元，可以用扩展欧几里得求逆元或者快速幂求逆元。快速幂求逆元码量小，如果a、mod互质，且mod为质数，那么a的逆元就是 。
Code：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
ll fact[100005];
template <class T>
inline void read(T &res) {
char c; T flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = -1;
res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
res *= flag;
}
ll qpow(ll a,ll b) {
ll ans=1;
while(b) {
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
ll n,x,y,t;
int main() {
fact[0]=fact[1]=1;
for(int i=2;i<=100000;++i) fact[i]=fact[i-1]*i%mod;
read(n);
while(n--) {
read(x),read(y),read(t);
if(x+y>t) {
puts("0");
continue;
}
ll l=fact[t-y]*qpow(fact[x]*fact[t-x-y]%mod,mod-2)%mod;
ll r=fact[t]*qpow(fact[y]*fact[t-y]%mod,mod-2)%mod;
printf("%lld\n",l*r%mod);
}
} C、牛牛染颜色
题意：
牛牛最近得到了一颗树，根是 1 号节点，他想要把这颗树染色。
每个节点可以染成白色和黑色，牛牛认为一种染色方案是好的当且仅当任意两个黑点的 lca（最近公共祖先）的颜色也是黑色的。
求一共有多少种好的染色的方案。
答案可能很大，请输出答案对1e9 + 7取模后的结果。
思路：
知道题意后不难发现这是一道树形dp题（但是我不会），dp[u][0/1]，0表示这个点涂黑色，1表示这个点涂白色。
分开来转移：
1.结点u涂黑，那无论子树是什么情况，尽管下面没有黑色都都是符合的，所以我们可以无所顾及地得到状态转移方程dp[u][0]= .
2.结点u涂白，所以我们单独把每个子节点是（黑/白）的情况加起来就好了，否则在 u 的子树内会存在两个点 x,y 使得 lca(x,y)=u，这样就不符合条件了。这个状态是包含空集的，所以在枚举子树统计的时候每颗子树贡献的答案要减 1，但最后也要把空集的情况算上，还要加个 1。
Code：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int maxn=1e6+7;
template <class T>
inline void read(T &res) {
char c; T flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = -1;
res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
res *= flag;
}
int head[maxn],Next[maxn<<1],to[maxn<<1],tot;
ll dp[maxn][2];
void add(int x,int y) {
to[++tot]=y;
Next[tot]=head[x];
head[x]=tot;
}
void dfs(int x,int fa) {
ll zero=1,one=1;
for(int i=head[x];i;i=Next[i]) {
int y=to[i];
if(y==fa) continue;
dfs(y,x);
zero=zero*(dp[y][0]+dp[y][1])%mod;
one=(one+dp[y][0]+dp[y][1]-1)%mod;
}
dp[x][0] = zero; dp[x][1] = one;
}
int n,u,v;
int main() {
read(n);
for(int i=2;i<=n;++i) {
read(u),read(v);
add(u,v);
add(v,u);
}
dfs(1,0);
printf("%lld\n",(dp[1][0]+dp[1][1])%mod);
return 0;
} 
网易有道公司氛围 38人发布