2020-01-21 12:02 已编辑前端工程师

关注

【题解】牛客小白月赛21

牛客小白月赛21解题报告

正式详细题解将在稍后更新！（施工中……）

首先非常抱歉，由于牛客的UI问题导致H题的标点符号显示错误，影响大家体验心情。

题目分类（解题报告按此顺序编写）：

签到题：H
前期题：A、C、F、G、I
中期题：E、J
后期题：B、D

H —— "Happy New Year!"

考点：手速和冷静。

输出题目即可。

赛时紧急添加了Special Judge以扭转出锅局面，再次对因该问题影响心情的选手道歉。

PS：使用PHP写据说会有奇效？

点我看标程！

A —— Audio

考点：计算几何基础。

由平方反比定律，发现响度相同时只与距离有关，所以我们只需要求一点，使得该点到三角形三个顶点距离相同，即求三角形的外心。

推导过程即联立任意两边的垂直平分线，求垂直平分线的交点即可。

点我看标程！

C —— Channels

考点：前缀和思想，容斥的思想。

计算 $[1,r]$ 的答案减去 $[1,l-1]$ 的答案即可，不过需要注意其端点可能在广告的时刻哦！

具体计算方法：即只需要考虑如何计算 $[1,x]$ 的答案。

点我看标程！

F —— Fool Problem

考点：找规律与公式推导。

不难寻得 $f_{n+1}f_{n-1}-f_n^2=(-1)^n$ ，可以利用斐波那契的递推公式证明该式，此处留给读者思考。

点我看标程！

G —— Game

考点：题意转换。

不难发现某一个数字的质因子个数是一定的，计算其质因子个数来探究可分解的步数进行博弈即可。

其实最后只需要考虑质因子个数的奇偶性。

或者通过sg函数来进行计算：

点我看标程！

I —— I love you

考点：动态规划。

请参看小白月赛3的B题，只不过这里的字符串变长了一些QwQ，道理是一样的（记 $f_i$ 表示匹配到iloveyou第 $i$ 位的方案数，遇到一个字符从其前序字符转移过来即可），简单DP。

点我看标程！

E —— Exams

考点：模拟。

按照题目意思计算学分绩即可。

注意题目中提到“计算且仅计算必修和限选课程”，故任选学分不算在学分绩的总学分里面。

点我看标程！

J —— Jelly

考点：Bfs搜索。

三维迷宫？求从(1,1,1)到(n,n,n)的最短路。

搜索的时候一改二维搜索的四连通，改为三维搜索的六连通，上下左右前后6个方向进行Bfs。

点我看标程！

B —— Bits

考点：模拟，二进制的神奇应用（计算图形学？？？）

请参看这里，也可以通过Dfs来写，不过注意一下奇偶的位置。

点我看标程！

D —— DDoS

考点：题意转化，拓扑图路径计数

不易观察、挺难发现、较难得到攻击者可以通过调整发送数据包的时间来使得所有数据包同时到达服务器，故原题意转化为求1到n的路径条数，拓扑图上DP即可。

注意定向的含义是规定路线及经过的中继节点，所以重边的时候格外小心（需要算两倍）。

边权无用（其实这里给了个奇怪的数据范围是在暗示呢QwQ）。

点我看标程！

全部评论

推荐最新楼层

云中翻月

C++

求问D为什么建返图就会WA，建正图才能AC。正图代码 #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<set> #include<map> #include<queue> #include<stack> #include<vector> #include<cstring> #include<cstdlib> #include<iomanip> #include<ctime> #include<string> #include<bitset> #define D(x) cout<<#x<<" = "<<x<<" " #define E cout<<endl using namespace std; typedef long long ll; typedef pair<int,int>pii; const int maxn=100000+5; const int maxm=200000+5; const int INF=0x3f3f3f3f; const ll mod=20010905; int n,m; int head[maxn],tot=1; int in[maxn]; ll d[maxn]; queue<int>q; struct node{ int from,to,c; }edge[maxm]; void add(int from,int to){ edge[++tot].from=head[from],head[from]=tot,edge[tot].to=to; } void dp(){ d[1]=1; q.push(1); while(q.size()){ int x=q.front();q.pop(); for(int i=head[x];i;i=edge[i].from){ int y=edge[i].to; d[y]=(d[y]+d[x])%mod; if(--in[y]==0){ q.push(y); } } } printf("%lld",d[n]%mod); } int main() { // ios::sync_with_stdio(false); freopen("DDoS.in","r",stdin); scanf("%d%d",&n,&m); int from,to,c; for(int i=1;i<=m;i++){ scanf("%d%d%d",&from,&to,&c); add(from,to); in[to]++; } dp(); return 0; } 反图代码 #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<set> #include<map> #include<queue> #include<stack> #include<vector> #include<cstring> #include<cstdlib> #include<iomanip> #include<ctime> #include<string> #include<bitset> #define D(x) cout<<#x<<" = "<<x<<" " #define E cout<<endl using namespace std; typedef long long ll; typedef pair<int,int>pii; const int maxn=100000+5; const int maxm=200000+5; const int INF=0x3f3f3f3f; const ll mod=20010905; int n,m; int head[maxn],tot=1; int in[maxn]; ll d[maxn]; queue<int>q; struct node{ int from,to,c; }edge[maxm]; void add(int from,int to){ edge[++tot].from=head[from],head[from]=tot,edge[tot].to=to; } void dp(){ d[n]=1; q.push(n); while(q.size()){ int x=q.front();q.pop(); for(int i=head[x];i;i=edge[i].from){ int y=edge[i].to; d[y]=(d[y]+d[x])%mod; if(--in[y]==0){ q.push(y); } } } printf("%lld",d[1]%mod); } int main() { // ios::sync_with_stdio(false); // freopen("DDoS.in","r",stdin); scanf("%d%d",&n,&m); int from,to,c; for(int i=1;i<=m;i++){ scanf("%d%d%d",&from,&to,&c); add(to,from); //反图 in[from]++; } dp(); return 0; }

1 回复

发布于 2020-01-18 22:26

Livven

C++

所以，D题 3 4 1 2 1 1 2 1 2 3 1 2 3 1 答案是多少

点赞回复

发布于 2020-01-18 22:13