首页 > 分享 > 牛客网的国庆自闭7天乐：一些好题

牛客网的国庆自闭7天乐：一些好题

花匠小妙招
2024-11-26 22:06

day1:

J Princess Principal
链接：https://www.nowcoder.com/acm/contest/201/J
来源：牛客网

阿尔比恩王国（the Albion Kingdom）潜伏着一群代号“白鸽队（Team White Pigeon）”的间谍。在没有任务的时候，她们会进行各种各样的训练，比如快速判断一个文档有没有语法错误，这有助于她们鉴别写文档的人受教育程度。
这次用于训练的是一个含有n个括号的文档。括号一共有m种，每种括号都有左括号和右括号两种形式。我们定义用如下的方式定义一个合法的文档:
1.一个空的字符串是一个合法的文档。
2.如果A,B都是合法的文档，那么AB也是合法的文档。
3.如果S是合法的文档，那么aSb也是合法的文档，其中a,b是同一种括号，并且a是左括号，b是右括号。
现在给出q个询问，每次询问只考虑文档第l至r个字符的情况下，文档是不是合法的。

这道题明显是一个括号序列的裸题，但是场上不知道怎么搞就没写出来
假设只有一种括号，要想解决这个问题，我们需要用栈来实现添加括号，我们可以记录添加过每个位置之后，当前栈顶元素的标号，如果标号相同的话，说明在添加过程中，括号的入栈序列是匹配的。这样就实现了O（1）判断，预处理只需要O(n)。即使括号的种类有很多，不影响最后结果的正确性。

#include <bits/stdc++.h> #define ll long long using namespace std; const int MAXN = 2e6 + 6; int a[MAXN],l[MAXN],st[MAXN]; int main() { int n,m,q; cin>>n>>m>>q; int top = 0; for(int i = 1;i<=n;i++) { cin>>a[i]; } for(int i =1;i<=n;i++) { if(top) { if(a[i]/2 == a[st[top]] /2 && a[i] == a[st[top]] + 1) top--; else st[++top] = i; } else { st[++top] = i; } l[i] = st[top]; } for(int i =0;i<q;i++) { int x,y; cin>>x>>y; if( (y - x) % 2 == 0) cout<<"No"<<endl; else { if(l[x-1] == l[y]) cout<<"Yes"<<endl; else cout<<"No"<<endl; } } return 0; } 1234567891011121314151617181920212223242526272829303132333435363738394041

1234567891011121314151617181920212223242526272829303132333435363738394041 day2：

H 卡牌游戏
链接：https://www.nowcoder.com/acm/contest/202/H
来源：牛客网

小贝喜欢玩卡牌游戏。某个游戏体系中共有N种卡牌，其中M种是稀有的。小贝每次和电脑对决获胜之后都会有一个抽卡机会，这时系统会随机从N种卡中选择一张给小贝。普通卡可能多次出现，而稀有卡牌不会被重复抽到。小贝希望收集到K种稀有卡牌，她想知道期望需要多少次获胜才能实现这个目标。

其实相当于先求一个概率，每次抽到卡片的概率相当于是 k − 1 n − 1 k - 1over n-1 n−1k−1 ,结合相关的概率公式（博主太菜不知道怎么推）知道期望等于概率分之一，最后的答案就是
∑ i = 1 k n − i m − i sum_{i =1}^{k} {n - iover m-i} i=1∑km−in−i

#include <bits/stdc++.h> #include <cstring> #define ll long long using namespace std; const int INF = 0x3f3f3f3f; const ll INFLL = 0x3f3f3f3f3f3f3f; const ll mod = 998244353; const int MAXN = 2e4 + 10; int main() { int ca,cat = 1; scanf("%d",&ca); while(ca--) { int n,m,k; scanf("%d%d%d",&n,&m,&k); double ans = 0.0; for(int i = 0;i<k;i++) { ans += 1.0*(1.0*n - i)/(1.0*m - i); } printf("Case #%d: %.8fn",cat++,ans); } return 0; } 12345678910111213141516171819202122232425262728

12345678910111213141516171819202122232425262728 day3 :

还没补……

day4：

链接：https://www.nowcoder.com/acm/contest/204/I
来源：牛客网

小 A 有一棵长的很奇怪的树，他由 n 条链和 1 个点作为根构成，第 i 条链有 ai 个点，每一条链的一端都与根结点相连。
现在小 A 想知道，这棵长得奇怪的树有多少非空的连通子树，你只需要输出答案对 998244353 取模的值即可

我们把一条链分成两种情况来考虑，首先我们不包括根节点，那么联通快的数量就是 C ( n + 1 , 2 ) C(n+1,2) C(n+1,2),然后考虑不在一个链的情况，每个链对真题答案的贡献就是（n+1）因为不仅要考虑和其他链，还要考虑单独和根节点的个数。

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 998244353; int main() { int n,t; cin>>n; ll sum = 0,sum2 = 1; for(int i = 0;i<n;i++) { cin>>t; sum = (sum + 1LL*t*(t+1)/2) % mod; sum2 = (sum2 * (t+1)) % mod; } cout<<(sum + sum2) % mod<<endl; return 0; } 12345678910111213141516171819

12345678910111213141516171819

链接：https://www.nowcoder.com/acm/contest/204/G
来源：牛客网

小 Bo 有 n 个正整数 a1…an，以及一个权值序列 w1…wn，现在他定义
f ( l , r ) = ( ∑ i = l r a i ) ∗ w r − l + 1 f(l,r) = (sum_{i=l}^{r}{a_i}) * w_{r-l+1} f(l,r)=(i=l∑rai)∗wr−l+1
现在他想知道 ∑ l = 1 n ∑ r = l n f ( l , r ) sum_{l=1}^{n}sum_{r=l}^{n}f(l,r) ∑l=1n∑r=lnf(l,r) 的值，需要你来帮帮他
你只需要输出答案对 1e9+7 取模后的值

我们先来找个规律，根据画的矩阵（垃圾博主的草稿纸丢了），我们发现只需要计算每个长度做的贡献，进一步启发式猜想可知，每一段区间和，对整体答案的w值贡献恰好和本身的值没有关系，也就是一段区间和相当于为答案贡献了区间和个数的权值区间和。于是只需要求出两个前缀和，注意好取模就ok。

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 1e9+7; const int MAXN = 3e5 + 5; ll sum[MAXN],sumw[MAXN]; ll w[MAXN]; ll plain(int n) { ll res = 0; for(int i = 1;i<=n;i++) { for(int j = i;j<=n;j++) { res += w[j-i +1]*(sum[j] - sum[i-1]); } } return res; } int main() { int n; cin>>n; for(int i =1;i<=n;i++) { cin>>sum[i]; sum[i] += sum[i-1]; sum[i] %= mod; } for(int i = 1;i<=n;i++) { cin>>w[i]; //w[i] += w[i-1]; sumw[i] = sumw[i-1] + w[i] % mod; } ll ans = 0; for(int i = 1;i<=n;i++) { int l = i,r = n - i +1; //if(l > r) break; if(l <= r) ans = (ans + ((sum[r]- sum[l-1] + mod) % mod)*((sumw[r]-sumw[l-1] + mod) % mod)) % mod; } cout<<ans<<endl; return 0; } 12345678910111213141516171819202122232425262728293031323334353637383940414243444546

12345678910111213141516171819202122232425262728293031323334353637383940414243444546

H 树链博弈
链接：https://www.nowcoder.com/acm/contest/204/H
来源：牛客网

给定一棵 n 个点的树，其中 1 号结点是根，每个结点要么是黑色要么是白色
现在小 Bo 和小 Biao 要进行博弈，他们两轮流操作，每次选择一个黑色的结点将它变白，之后可以选择任意多个(可以不选)该点的祖先(不包含自己)，然后将这些点的颜色翻转，不能进行操作的人输
由于小 Bo 猜拳经常输给小 Biao，他想在这个游戏上扳回一城，现在他想问你给定了一个初始局面，是先手必胜还是后手必胜

结论很简单，如果每一层都有偶数个黑色节点的话，为先手必败，否则的话为先手必胜

我们尝试来理解一下，首先如果每层都是白色的，满足我们的题目要求，如果通过一步从必败态转移到必胜态，那么同样可以让任意的黑点翻转达到要求
代码不贴了……

day5:

链接：https://www.nowcoder.com/acm/contest/205/G
来源：牛客网

终于活成了自己讨厌的样子。
充钱能让你变得更强。
在暖婊这个游戏里面，如果你充了x元钱，那么你能获得10x个钻石。同时暖婊也有m档VIP，如果你往暖婊里面充了ai个钻石，那么你能成为第i档贵族用户。当你成为第i档贵族用户之后，那么你可以获得的优惠。
你需要k件材料合成衣服，其中第i件材料原价为di个钻石，你一共需要ci件这种材料。当你获得p的优惠时，这个材料的真实价格为。
请问栗子米最少需要氪多少钱，这里我们规定只能氪整数的钱。

发现数据量真的很少，所以直接暴力也是个可行的办法，垃圾博主使用的是二分最后花多少钱。强行卡精度过了。

#include <bits/stdc++.h> #include <cstring> #define ll long long using namespace std; int a[100],d[100],p[100],c[100]; int m,k; bool check(int mid) { mid *= 10; int rk = 0; while(a[rk] <= mid) rk++; rk -=1; //cout<<mid<<' '<<rk<<endl; for(int i = 1;i<=k;i++) { int di = (int)ceil( (long double)d[i]*(100 - (long double)p[rk])/(long double)100.0) ; int now = c[i]*di; //cout<<now<<endl; if(mid >= now) mid -= now; else return 0; } return 1; } int main() { int ca; cin>>ca; while(ca--) { cin>>m>>k; a[0] = 0; for(int i = 1;i<=m;i++) cin>>a[i]>>p[i]; a[m+1] = 1e9; for(int i = 1;i<=k;i++) { cin>>c[i]>>d[i]; } int l = 0,r = 1e7 + 10,ans; while(l <= r) { int mid = (l + r) >> 1; if(check(mid)) { ans = mid; r = mid - 1; } else l = mid + 1; } cout<<ans<<endl; } return 0; } 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455

https://blog.csdn.net/hxxjxw/article/details/82943722 放一个队友写的博客，是L题的，数论之神wq书记吗，太强了。
B 电音之王
dls出的神题呀，链接：https://www.nowcoder.com/acm/contest/205/B
来源：牛客网

终于活成了自己讨厌的样子。
听说多听电音能加快程序运行的速度。
定义一个数列，告诉你a0,a1,m0,m1,c，定义an=m0an-1+m1an-2+c对所有n≥ 2。求 ∑ i = 1 k a i sum_{i=1}^{k}a_i ∑i=1kai

这个其实递推会各种爆long long，大数会T，dls介绍了一位日本选手的快速乘法：蒙哥马利乘法的一种实现。由于本人真的垃圾只能先贴个板子了
这位选手的ID是：min_25

#include <bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef long long ll; typedef pair<int,int> PII; const ll mod=1000000007; ll powmod(ll a,ll b) { ll res=1; a%=mod; assert(b>=0); for(; b; b>>=1) { if(b&1) res=res*a%mod; a=a*a%mod; } return res; } ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }// head typedef unsigned long long u64; typedef __int128_t i128; typedef __uint128_t u128; int _,k; u64 A0,A1,M0,M1,C,M; struct Mod64 { Mod64():n_(0) {}Mod64(u64 n):n_(init(n)) {}static u64 init(u64 w) { return reduce(u128(w) * r2); }static void set_mod(u64 m) { mod=m; assert(mod&1); inv=m; rep(i,0,5) inv*=2-inv*m; r2=-u128(m)%m; }static u64 reduce(u128 x) { u64 y=u64(x>>64)-u64((u128(u64(x)*inv)*mod)>>64); return ll(y)<0?y+mod:y; }Mod64& operator += (Mod64 rhs) { n_+=rhs.n_-mod; if (ll(n_)<0) n_+=mod; return *this; }Mod64 operator + (Mod64 rhs) const { return Mod64(*this)+=rhs; }Mod64& operator -= (Mod64 rhs) { n_-=rhs.n_; if (ll(n_)<0) n_+=mod; return *this; }Mod64 operator - (Mod64 rhs) const { return Mod64(*this)-=rhs; }Mod64& operator *= (Mod64 rhs) { n_=reduce(u128(n_)*rhs.n_); return *this; }Mod64 operator * (Mod64 rhs) const { return Mod64(*this)*=rhs; }u64 get() const { return reduce(n_); }static u64 mod,inv,r2; u64 n_; }; u64 Mod64::mod,Mod64::inv,Mod64::r2; u64 pmod(u64 a,u64 b,u64 p) { u64 d=(u64)floor(a*(long double)b/p+0.5); ll ret=a*b-d*p; if (ret<0) ret+=p; return ret; } void bruteforce() { u64 ans=1; for (int i=0; i<=k; i++) { ans=pmod(ans,A0,M); u64 A2=pmod(M0,A1,M)+pmod(M1,A0,M)+C; while (A2>=M) A2-=M; A0=A1; A1=A2; } printf("%llun",ans); } int main() { for (scanf("%d",&_); _; _--) { scanf("%llu%llu%llu%llu%llu%llu%d",&A0,&A1,&M0,&M1,&C,&M,&k); Mod64::set_mod(M); Mod64 a0(A0),a1(A1),m0(M0),m1(M1),c(C),ans(1),a2(0); for (int i=0; i<=k; i++) { ans=ans*a0; a2=m0*a1+m1*a0+c; a0=a1; a1=a2; } printf("%llun",ans.get()); } return 0; } 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125 day6:

链接：https://www.nowcoder.com/acm/contest/206/A
来源：牛客网

恬恬的生日临近了。宇扬给她准备了一个蛋糕。
正如往常一样，宇扬在蛋糕上插了n支蜡烛，并把蛋糕分为m个区域。因为某种原因，他必须把第i根蜡烛插在第ai个区域或第bi个区域。区域之间是不相交的。宇扬在一个区域内同时摆放x支蜡烛就要花费x2的时间。宇扬布置蛋糕所用的总时间是他在每个区域花的时间的和。
宇扬想快些见到恬恬，你能告诉他布置蛋糕最少需要多少时间吗？

一开始暴力了几发，发现是个费用流问题，于是尝试建模型……最后失败
这道题的模型建立很是巧妙，我们考虑两个蜡烛放置的时间花费的差： i 2 − ( i − 1 ) 2 = 2 i + 1 i^2 - (i-1)^2 = 2i +1 i2−(i−1)2=2i+1,我们可以考虑拆点来做，首先将源点连接每个蜡烛，流量1费用0，将每个区域拆成对应的50个点，每个点之间连接一条边流量1费用 i 2 − ( i − 1 2 ) i^2 - (i-1^2) i2−(i−12)，最后一个点连接汇点，每个蜡烛点连接到对应的每个拆出来的点。联想一下费用流的过程就知道算法会选择小的边流向汇点，费用相加就是我们想要的答案。
然后我们可以进一步优化，首先我们知道最后拆点之间的连边的费用，根据《网络流建模汇总》，我们可以将拆出来的点直接缩成一个点，连边直接连向汇点，容量1，费用为1…100之间的奇数。

#include <iostream> #include <cstdio> #include <bits/stdc++.h> using namespace std; #define ll long long const int MAXN = 10000; const int MAXM = 100000; const int INF = 0x3f3f3f3f; struct Edge { int to,next,cap,flow,cost,from; } edge[MAXM]; int head[MAXN],tol; int pre[MAXN],dis[MAXN]; bool vis[MAXN]; int N;//节点总个数，节点编号从0~N-1 void init(int n) { N = n; tol = 0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int cap,int cost) { edge[tol].to = v; edge[tol].from = u; edge[tol].cap = cap; edge[tol].cost = cost; edge[tol].flow = 0; edge[tol].next = head[u]; head[u] = tol++; edge[tol].to = u; edge[tol].from = v; edge[tol].cap = 0; edge[tol].cost = -cost; edge[tol].flow = 0; edge[tol].next = head[v]; head[v] = tol++; } bool spfa(int s,int t) { queue<int>q; for(int i = 0; i < N; i++) { dis[i] = INF; vis[i] = false; pre[i] = -1; } dis[s] = 0; vis[s] = true; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost ) { dis[v] = dis[u] + edge[i].cost; pre[v] = i; if(!vis[v]) { vis[v] = true; q.push(v); } } } } if(pre[t] == -1) return false; else return true; } //返回的是最大流，cost存的是最小费用 int minCostMaxflow(int s,int t,int &cost) { int flow = 0; cost = 0; while(spfa(s,t)) { int Min = INF; for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]) { if(Min > edge[i].cap - edge[i].flow) Min = edge[i].cap - edge[i].flow; } for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]) { edge[i].flow += Min; edge[i^1].flow -= Min; cost += edge[i].cost * Min; } flow += Min; } return flow; } void debug() { for(int i = 0;i<tol;i+=2) printf("%d->%d cap = %d flow = %d cost = %dn",edge[i].from,edge[i].to,edge[i].cap,edge[i].flow,edge[i].cost); } int n,m,k,W; int a[MAXN],b[MAXN]; int main() { cin>>n>>m; init(n+m+2); int st = 0,en = n+m+1; for(int i = 1;i<=n;i++) { cin>>a[i]>>b[i]; } for(int i = 1;i<=n;i++) { addedge(st,i,1,0); addedge(i,a[i] + n,1,0); addedge(i,b[i] + n,1,0); } for(int i = 1;i<=m;i++) { for(int c = 1;c<100;c+=2) { addedge(i+n,en,1,c); } } int cost = 0; minCostMaxflow(st,en,cost); //debug(); cout<<cost<<endl; return 0; } /* 2 2 1 2 3 5 3 4 8 */