牛客CSP-S提高组赛前集训营1解题报告
本次比赛题解————>戳这里
写在前面
说实话，T1 我花的时间略多了一些，一直想证明但是却没有注意到终态的规律，最终才堪堪想出了正确性。
T2中的树形DP本来很有把握，但是由于我在换根的时候算DP2数组时，中间求的某一个逆元没有加DP1的值，所以就写挂了，不过感谢上苍我还有30分。下一次记得将各个数组变量的意义弄清楚，时时提醒自己，免得就写挂了还有就是，DP的转移方程要打草稿，检查也方便。
关于T3，他死了
数据过水引发惨案，被人民群众的唾沫星子淹死了（同机房大佬用二分图骗了80昏）。不过加强数据后，也是一道妙题。不过考场上没能做出来
T1 仓鼠的石子游戏
题目链接：仓鼠的石子游戏
题目描述
仓鼠和兔子被禁止玩电脑，无聊的他们跑到一块空地上，空地上有许多小石子。兔子捡了很多石子，然后将石子摆成n个圈，每个圈由a[i]个石子组成。然后兔子有两根彩色笔，一支红色一支蓝色。兔子和仓鼠轮流选择一个没有上色的石子涂上颜色，兔子每次可以选择一个还未染色的石子将其染成红色，而仓鼠每次可以选择一个还未染色的石子将其染成蓝色，并且仓鼠和兔子约定，轮流染色的过程中不能出现相邻石子同色，谁不能操作他就输了。假设他们两个都使用了最优策略来玩这个游戏，并且兔子先手，最终谁会赢得游戏？
输入描述:
第一行输入一个正整数T，表示有T组测试案例。
每组测试案例的第一行输入一个n，表示有n圈石子。 第二行输入n个正整数a[i]，表示每个圈的石
子数量。
输出描述:
对于每组测试案例，如果兔子赢了，输出”rabbit“(不含引号)如果仓鼠赢了，输出"hamster"(不含引号)。
样例
输入
4
1
3
1
1
2
1 3
3
999 1000 1000000000
输出
hamster
rabbit
rabbit
hamster
分析
考试的时候我手画了几组样例，发现除了1的情况，其余都是后手赢，于是大胆猜想。
其实这题从题目可以推出，最终的状态一定是颜色交替出现，不然的话相邻的两个同色的石子之间必定有一个空位，这样一来，最终的石子一定有偶数个，也就是后手必赢。
所以关键就在1，1就是一个输赢的转机。只要你占了一个1，如果没有其他的1了，那么你必定就成了后手赢家（后来就一直跟着先手走，保持自己后手的地位），所以统计1的个数便好。
代码
/***********************
User:Mandy
Language:
Problem:
Algorithm:
***********************/
//红蓝必然交替
//除1以外，后手必赢
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;
int t,n;
int a[maxn];
template<class T>inline void read(T &x){
x = 0;bool flag = 0;char ch = getchar();
while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
if(flag) x = -x;
}
template<class T>void putch(const T x){if(x > 9) putch(x / 10);putchar(x % 10 | 48);}
template<class T>void put(const T x){if(x < 0) putchar('-'),putch(-x);else putch(x);}
void readdata(){
read(n);
for(int i = 1;i <= n; ++ i) read(a[i]);
}
void work(){
if(a[1] == 1) printf("rabbit");
else printf("hamster");
}
void work1(){
int cnt = 0;
for(int i = 1;i <= n; ++ i) {
if(a[i] == 1) ++cnt;
}
if(cnt & 1) printf("rabbit") ;
else printf("hamster");
}
int main(){
read(t);
for(int i = 1;i <= t; ++ i){
readdata();
if(n == 1) work();//考场上怕挂分开打
else work1();
if(i != t) putchar('\n');
}
return 0;
} T2 乃爱与城市拥挤程度
题目链接：乃爱与城市拥挤程度
题目描述
乃爱天下第一可爱！
乃爱居住的国家有n座城市，这些城市与城市之间有n-1条公路相连接，并且保证这些城市两两之间直接或者间接相连。
我们定义两座城市之间的距离为这两座城市之间唯一简单路径上公路的总条数。
当乃爱位于第x座城市时，距离城市x距离不大于k的城市中的人都会认为乃爱天下第一可爱！
认为乃爱天下第一可爱的人们决定到乃爱所在的城市去拜访可爱的乃爱。我们定义这些城市的拥挤程度为：
距离城市x距离不大于k的城市中的人到达城市x时经过该城市的次数。例如：
假设k=2，乃爱所在的城市是1号城市，树结构如上图所示时，受到影响的城市为1,2,3,4,5，因为五个城市距离1号城市的距离分别为：0,1,2,2,2，所以这五个城市都会认为乃爱天下第一。
1号城市到1号城市经过了1号城市。
2号城市到1号城市经过了1号、2号城市。
3号城市到1号城市经过了1号、2号、3号城市。
4号城市到1号城市经过了1号、2号、4号城市。
5号城市到1号城市经过了1号、2号、5号城市。
所以1号城市的拥挤程度是5，2号城市的拥挤程度是4，3号、4号、5号城市的拥挤程度都是1。
现在小w想要问你当乃爱依次位于第1、2、3、4、5...n座城市时，有多少座城市中的人会认为乃爱天下第一，以及受到影响城市的拥挤程度的乘积，由于这个数字会很大，所以要求你输出认为乃爱天下第一的城市拥挤程度乘积mod 后的结果。
输入描述:
第一行是两个正整数n,k表示城市数目，以及距离乃爱所在城市距离不大于k的城市中的人认为乃爱天下第一！
接下来n-1行，每行两个正整数u,v，表示树上一条连接两个节点的边。
输出描述:
输出两行。
第一行n个整数，表示当乃爱依次位于第1、2、3、4、5...n座城市时，有多少座城市中的人会认为乃爱天下第一。
第二行n个整数，表示当乃爱依次位于第1、2、3、4、5...n座城市时，受影响的城市拥挤程度乘积mod 后的结果。
示例1
输入
7 2
1 2
2 3
2 4
2 5
5 6
5 7
输出
5 7 5 5 7 4 4
20 21 20 20 28 12 12
分析
很明显的一个树形DP + 二次扫描换根法。
dp1[u][i]表示离u的距离不超过i的节点的个数
dp2[u][i]表示离u的距离不超过i的节点的乘积（不包括自己，换根的时候再算）
第一问很好做，主要是第二问处理起来有些麻烦，由于换根时要用到除法，所以还要求逆元。
除此之外没什么好说的，注意细节，弄清方程由哪些元素组成，分别对应哪些变量，变量的意义与范围，这些往往就是决定成败的细节
代码
/***********************
User:Mandy
Language:
Problem:
Algorithm:
***********************/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int maxk = 12;
const int mod = 1e9 + 7;
int n,k,size,first[maxn];
int dp1[maxn][maxk],ans1[maxn];
long long dp2[maxn][maxk],ans2[maxn];
struct Edge{
int v,nt;
}edge[maxn << 1];
template<class T>inline void read(T &x){
x = 0;bool flag = 0;char ch = getchar();
while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
if(flag) x = -x;
}
template<class T>void putch(const T x){if(x > 9) putch(x / 10);putchar(x % 10 | 48);}
template<class T>void put(const T x){if(x < 0) putchar('-'),putch(-x);else putch(x);}
void eadd(int u,int v){
edge[++size].v = v;
edge[size].nt = first[u];
first[u] = size;
}
void readdata(){
read(n);read(k);
for(int i = 1;i < n; ++ i){
int u,v;read(u);read(v);eadd(u,v);eadd(v,u);
}
}
void dfs1(int u,int f){
for(int i = 0;i <= k; ++ i) dp2[u][i] = 1,dp1[u][i] = 1;
for(int i = first[u];i;i = edge[i].nt){
int v = edge[i].v;if(v == f) continue;
dfs1(v,u);
for(int j = 1;j <= k; ++ j) {
dp1[u][j] += dp1[v][j-1];
dp2[u][j] = dp2[u][j] * dp2[v][j-1] % mod * dp1[v][j - 1] % mod;//取模
}//这里的DP2没乘本身u节点的值 ，所以v这里要把v的乘进去
}
// for(int i = 1;i < k; ++ i) dp2[u][i] = dp2[u][i] * dp1[u][i] % mod;
}
long long ksm(long long x,long long p){
long long ans = 1;
while(p){
if(p & 1) ans = ans * x % mod;
p >>= 1;
x = x * x % mod;
}
return ans;
}
long long inv(long long x){
return ksm(x,mod-2);
}
void dfs2(int u,int f){
for(int i = first[u];i;i = edge[i].nt){
int v = edge[i].v;if(v == f) continue;
for(int j = k;j >= 1; -- j) {//倒序，因为要用到子树 的状态
dp1[v][j] += (dp1[u][j-1] - (j >= 2 ? dp1[v][j-2] : 0));
dp2[v][j] = dp2[v][j] * dp1[v][j] % mod *
//dp2是子树的乘积（不包括自己），所以乘以自己的值
dp2[u][j - 1] % mod * inv(dp1[u][j - 1]) % mod
* (j >= 2 ? inv(dp2[v][j - 2] * dp1[v][j -2 ] % mod) : 1) % mod *
//注意 dp2[v][j - 2] * dp1[v][j -2 ] % mod，这里因为倒序所以dp2[v][j-2]还没有乘以自己
(dp1[u][j - 1] - (j >= 2 ? dp1[v][j - 2] : 0)) % mod;
}
dfs2(v,u);
}
}
void work(){
dfs1(1,0);
for(int i = 1;i <= k; ++ i) dp2[1][i] = dp2[1][i] * dp1[1][i] % mod;
dfs2(1,0);
for(int i = 1;i <= n; ++ i){
put(dp1[i][k]);
if (i != n) putchar(' ');
else putchar('\n');
}
for(int i = 1;i <= n; ++ i){
put(dp2[i][k]);
if(i != n) putchar(' ');
}
}
int main(){
// freopen("ex.in","r",stdin);
// freopen("out.out","w",stdout);
readdata();
work();
return 0;
} T3 小w的魔术扑克
题目链接：小w的魔术扑克
题目描述
小w喜欢打牌，某天小w与dogenya在一起玩扑克牌，这种扑克牌的面值都在1到n，原本扑克牌只有一面，而小w手中的扑克牌是双面的魔术扑克（正反两面均有数字，可以随时进行切换），小w这个人就准备用它来出老千作弊。小w想要打出一些顺子，我们定义打出一个l到r的顺子需要面值为从l到r的卡牌各一张。小w想问问你，他能否利用手中的魔术卡牌打出这些顺子呢？
输入描述:
首先输入一行2个正整数n，k，表示牌面为1~n，小w手中有k张魔术扑克牌。
然后输入k行，每行两个数字，表示卡牌的正面和反面的面值。
接下来输入一行一个正整数q，表示q组查询，然后每组占一行查询输入两个整数l,r。表示查询小w能否打出这么一个l到r的顺子。
输出描述:
对于输出"Yes"表示可以，"No"表示不可以。（不含引号）
每个查询都是独立的，查询之间互不影响。
示例1
输入
5 3
1 2
2 3
4 4
3
1 2
2 4
1 4
输出
Yes
Yes
No
说明
对于顺子1~2，可以选择第一张卡牌作为'1'使用，选择第二张卡牌作为'2'使用。
对于顺子2~4，可以选择第一张卡牌作为'2'使用，选择第二张卡牌作为'3'使用，选择第三张卡牌作为'4'使用。
对于顺子1~4，由于牌的数目都不够，显然无法打出。
示例2
输入
4 3
1 1
2 2
4 4
3
1 2
1 4
4 4
输出
Yes
No
Yes
说明
该样例具有测试点4的特殊性质。
分析
一张牌有两面，但只能打出一面只能使用一次，可以将其抽象成一条边，有两个端点，但却只能走一次，从一个端点进。
抽象出这个模型，题目就好做了。对于一个n点连通图，但凡有n条及以上的边数，那么就可以将点遍历完，而若是只有n-1条边，就不可以。若是询问的区间正好完全包含这样的区间，就不可表。而对于一棵树，想要知道其是否被完全包含，需记录它的最大或最小值，看询问区间是否完全包含。
我们可以采用离线算法，将树与查询都按右端点排序，询问到的区间的右端点如果大于等于目前的数的右端点，则将树的左端点赋1加入树状数组，然后查询，看询问的左端点是否包含某一个左端点（看询问的区间的和是否为0）。
代码
/***********************
User:Mandy
Language:
Problem:
Algorithm:
***********************/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n,k,q,size,cnt;
int father[maxn],mi[maxn],ma[maxn],tree[maxn],ans[maxn];
bool vis[maxn];
struct Line_Segment{
int l,r,id;
}ask[maxn],tr[maxn];
template<class T>inline void read(T &x){
x = 0;bool flag = 0;char ch = getchar();
while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
if(flag) x = -x;
}
template<class T>void putch(const T x){if(x > 9) putch(x / 10);putchar(x % 10 | 48);}
template<class T>void put(const T x){if(x < 0) putchar('-'),putch(-x);else putch(x);}
int find(int x){return father[x] == x ? x : father[x] = find(father[x]);}
void merge(int x,int y){
int fx = find(x),fy = find(y);
if(fx == fy) {vis[fx] = 1;return;}
if(vis[fx] | vis[fy]) {vis[fx]=1;vis[fy]=1;}
father[fx] = fy;
mi[fy] = min(mi[fy],mi[fx]);ma[fy] = max(ma[fy],ma[fx]);
}
void readdata(){
read(n);read(k);
for(int i = 1;i <= n; ++ i) father[i] = i,mi[i] = ma[i] = i;
for(int i = 1;i <= k; ++ i) {
int x,y;read(x);read(y);
merge(x,y);
}
read(q);
}
bool cmp(const Line_Segment &x,const Line_Segment &y){
return x.r < y.r;
}
int lowbit(int x) {return x&(-x);}
void modify(int pos){
for(int i = pos;i <= n; i += lowbit(i)) tree[i]++;
}
int query(int pos){
int sum = 0;
for(int i = pos;i;i -= lowbit(i)) sum += tree[i];
return sum;
}
void work(){
for(int i = 1;i <= n; ++ i) if(father[i] == i && vis[i] == 0) tr[++cnt].l = mi[i],tr[cnt].r = ma[i];
for(int i = 1;i <= q; ++ i) read(ask[i].l),read(ask[i].r),ask[i].id = i;
sort(tr + 1,tr + cnt + 1,cmp);sort(ask + 1,ask + 1 + q,cmp);
int now = 1;
for(int i = 1;i <= q; ++ i) {
while(now <= cnt && ask[i].r >= tr[now].r) {//>=
modify(tr[now].l);
now++;
}
int R = query(ask[i].r);int L = query(ask[i].l - 1);
if(R - L) ans[ask[i].id] = 0;
else ans[ask[i].id] = 1;
}
for(int i = 1;i <= q; ++ i) if(ans[i]) puts("Yes");else puts("No");//离线算法
}
int main(){
// freopen("ex.in","r",stdin);
// freopen("out.out","w",stdout);
readdata();
work();
return 0;
} 
投递美团等公司10个岗位 >