A.DFS搜索
1签
题意
题目字面意思,问能不能在长度为 的字符串 中找到子序列”DFS”和”dfs”;
解题思路
直接暴力搜索
时间复杂度
参考程序
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| void solve() { string s,s1,s2; ll n;cin >> n; cin >> s; s1="DFS";s2="dfs"; int cnt1,cnt2;cnt1=cnt2=0; for(auto c:s){ if(cnt1<3&&c==s1[cnt1]) cnt1++; if(cnt2<3&&c==s2[cnt2]) cnt2++; } if(cnt1>=3) cout << 1; else cout << 0; cout << ' '; if(cnt2>=3) cout << 1; else cout << 0; cout << endl; }
|
B.关鸡
模拟
题意
有一条宽为,长为的管道,每个格子的坐标标记为,
管道内有个障碍,给定障碍的坐标
鸡哥在处,可以上下左右移动,但不能穿过障碍
求最少还需多少个障碍物才能使鸡哥被困在管道内无法到达管道两端
解题思路
将管道两排看作两侧,如果某处有障碍(下图红),只要它的另一侧相邻的位置中有一个有障碍(下图黄)即可堵住管道:

换个角度,从管道左端到右端,对于每个障碍,check它对面且与它的距离不大于的位置是否有障碍,即可确定是否堵住管道。
要把鸡哥困在管道内,需要把鸡哥两侧管道全都堵住。
对于鸡哥的一侧管道,如果:
没有堵住,没有障碍,则需放置个障碍;
没有堵住,至少有个障碍,则需放置个障碍;
已经堵住,则不需要放置障碍。
特别的,和鸡哥直接相邻的3个位置如果都有障碍,鸡哥就直接被困住了。
参考程序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
| void solve() { ll n;cin >> n; vector<pll> v(n); int f,fl,fr; f=fl=fr=0; for(auto &x:v){ cin >> x.second >> x.first; if(x.first==-1&&x.second==1) f++; if(x.first==0&&x.second==2) f++; if(x.first==1&&x.second==1) f++; if(x.first<=0) fl=1; if(x.first>=0) fr=1; } SORT(v); int ffl,ffr;ffl=ffr=0; deque<pll> dq; FORLL(i,0,n-1){ while(dq.size()&&v[i].first-dq.front().first>1) dq.pop_front(); for(auto x:dq){ if(x.second!=v[i].second){ if(v[i].first<=0) ffl=1; else ffr=1; } }dq.push_back(v[i]); } ll ans=3-f; if(ffl&&ffr) ans=min(ans,0ll); else if(ffl&&fr||fl&ffr) ans=min(ans,1ll); else if(ffl||ffr) ans=min(ans,2ll); else if(fl&&fr) ans=min(ans,2ll); cout << ans << endl; }
|
C.按闹分配
贪心
题意
个人在个窗口前排队办事,第个人办事需要时间
开始为时刻,每个人的不满意度为其办完事的时刻
工作人员安排队伍顺序使得所有人的不满意度之和 最小
你也来办事,需要时间。你可以插队,但是因此增加的不满意度之和不能超过
问你最早什么时候能办完事
解题思路
根据贪心的思想,初始使得不满意度之和最小的排序是按照从小到大排序
你插队导致的不满意度之和的增量为:你插队的位置之后的人数*你的办事时间
因此你后面的人数不得超过 个
在这个约束下计算前缀和即可
参考程序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| void solve() { ll n,Q,tc,M; cin >> n >> Q >> tc; create_vec(t,n); SORT(t); vector<ll> St; St.pb(0); FORLL(i,0,n-1) St.pb(St.back()+t[i]); while(Q--){ cin >> M; ll x=M/tc; ll pl=max(0ll,n-x); cout << St[pl]+tc << endl; } }
|
D.数组成鸡
思维
题意
给定一个长度为的整数数组,每次操作可以使所有元素都或都。
次询问,问任意次操作后能否使数组所有元素的乘积等于给定的数()。
解题思路
询问的范围不大,所以数组稍微长一点儿,就很可能溢出的范围。
由于元素都是整数,若数组中绝对值大于的元素的个数超过个,那么乘积的绝对值最小为,超过。
枚举出现过的数字,再向两边枚举它附近的数字,使全数组,然后直接计算数组的乘积进行。
当乘积的绝对值已经超过,即出现最多个绝对值大于的元素时,直接判不合法,枚举的元素个数是比较少的。
若最终乘积的绝对值不大于,则加入答案集合。
询问时在答案中二分查找即可。
参考程序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| void solve() { ll n,Q,t;cin >> n >> Q; vector<ll> a(n); set<ll> ans; ans.insert(0); set<ll> exi; for(auto &x:a){ cin >> x; exi.insert(x); } auto check = [&](ll x) -> bool{ ll tt=1; for(auto &y:a){ tt*=y+x; if(tt==0) return true; if(abs(tt)>1e9) return false; }ans.insert(tt); return true; }; for(auto &x:exi){ t=-x-1; while(check(t)) t--; t=-x+1; while(check(t)) t++; } while(Q--){ cin >> t; if(ans.count(t)) cout << "Yes\n"; else cout << "No\n"; } }
|
E.本题又主要考察了贪心
DFS、诈骗
题意
个人参加比赛,当前第个人已经得到了分,接下来还有轮比赛
每轮两个人PK,赢的人分;平局则每人分
给定轮比赛的名单,问号选手能取得的最高名次
解题思路
直接贪心很难贪(反正我是贪不出来)
由于人数和局数很少,直接DFS到每种结局,找到最优解即可
时间复杂度:
参考程序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| vector<pll> q; ll n,m,ans; void DFS(vector<ll> a,ll i){ if(i==m){ ll cnt=0; for(auto x:a) if(x>a[0]) cnt++; ans=min(ans,cnt); return ; } vector<ll> aa=a,ab=a,ac=a; aa[q[i].first-1]+=3; DFS(aa,i+1); ab[q[i].second-1]+=3; DFS(ab,i+1); ac[q[i].first-1]+=1; ac[q[i].second-1]+=1; DFS(ac,i+1); } void solve() { cin >> n >> m; ans=INF; vector<ll> a(n); for(auto &x:a) cin >> x; q.clear(); ll u,v; FORLL(i,1,m){ cin >> u >> v; if(u>v) swap(u,v); q.pb({u,v}); } DFS(a,0); cout << ans+1 << endl; }
|
F.鸡数题!
概率论-排列组合
题意
将位的最大二进制数(n个1)的每一位分配给个数,且每个数都不为,问有多少种分配方案
解题思路
个不同的球放入个不同的盒子,每个盒子至少一个球,有多少种放法
答案为第二类斯特林数
通项公式:
参考程序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| ll pown[N]={0}; void solve() { ll m,n;cin >> n >> m; if(n<m) {cout << 0 << endl;return;} FORLL(i,0,m){ pown[i]=qcpow(i,n); } Prepare_Factorium(m); ll ans=0; FORLL(i,0,m){ ll t=mul(pown[i],mul(Fac_inv[i],Fac_inv[m-i])); if((m-i)&1) t=MOD-t; addto(ans,t); }cout << ans << endl; }
|
G.why买外卖
贪心
题意
有张外卖券,第张满减,为餐品原价。
所有券可以叠加使用,你手上有元,问你最多可以购买到原价为多少的餐品
解题思路
假设餐品原价为,则所有的券都可以使用。
根据使用门槛对券排序,对减免部分做前缀和。
在每个门槛处计算:该门槛需支付的价格(或溢出的优惠)=当前门槛-减免金额
如果小于,则更新答案,当前门槛下最高餐品价格为
参考程序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| void solve() { ll n,m;cin >> n >> m; vector<pll> vp(n); for(auto &x:vp) cin >> x.first >> x.second; SORT(vp); vector<ll> S(n+1);S[0]=0; FORLL(i,1,n) S[i]=S[i-1]+vp[i-1].second; ll ans=m; FORLL(i,1,n){ if(vp[i-1].first-S[i]<=m){ ans=max(ans,S[i]+m); } }cout << ans << endl; }
|
H.01背包,但是bit
位运算
题意
有个物品,第个物品的价值为,重量为,每个物品只有一个。
选定物品的重量之和定义为这些物品各自重量的“或”和,即;价值之和定义为这些物品各自重量的初等代数和:
问选定物品的重量之和不超过的情况下,价值之和的最大值
解题思路
或运算的性质:有出,全出。
把所有“重量”看作二进制。
假设选定物品后结果为,那么的每个的位置,一定有某个被选中的物品的重量在该位上是。
枚举所有允许出现的位置的所有情况。
将的某一置,则该位的低位可以任意取值,高位不变。
如,将第二个置,则的合法位置变为。
确定了的合法位置,那每个物品只能是选或不选。
遍历的所有,计算将其置的情况:遍历所有物品,应选尽选。
取所有情况的最大值。
参考程序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| vector<ll> v,w; ll n,m,ans; void Update(ll x){ ll t=0; FORLL(i,0,n-1) if((w[i]&x)==w[i]) t+=v[i]; ans=max(ans,t); } void solve() { cin >> n >> m; ans=0; v.resize(n); w.resize(n); FORLL(i,0,n-1) cin >> v[i] >> w[i]; FORLL(i,0,29) if(m&(1<<i)){ Update((m^(1<<i))|((1<<i)-1)); }Update(m); cout << ans << endl; }
|
I.It’s bertrand paradox. Again!
概率论
题意
现在有两种在平面范围内生成(圆心在整点上且半径为整数的)圆形的算法(仅第3步不同):
- 均匀随机生成一个 内的整点
- 均匀随机生成一个 内的整数半径
bit的检验:不满足在范围内,返回第2步,即仅重新生成
buaa的检验:不满足在范围内,返回第1步,即重新生成一个圆
现在给出其中某个算法的生成 个圆的结果,问是由哪个算法生成的
解题思路
两种算法下,生成结果的圆心和半径的分布是不同的。
明显bit的方法圆心是均匀分布在平面内的,而buaa的方法不是。
根据抽样分布原理,大量独立同分布随机变量和的极限分布是正态分布。
因此对样本建立统计量,使得两种算法下,该统计量有显著不同即可。
此处建立的统计量为:圆心到原点的距离的均值。
用两种算法生成样本,暴算得到$U{buaa}\approx56,U{bit}\approx 75$。
参考程序
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| void solve() { ll n;cin >> n; double sum=0; ll x,y; FORLL(i,1,n) { cin >> x >> y; sum+=sqrt(x*x+y*y); cin >> x; }sum/=n; if(sum<65) cout << "buaa-noob" << endl; else cout << "bit-noob" << endl; }
|
J.又鸟之亦心
思维
题意
两个人分别在数轴的位置。
接下来天,第天必须从两人中选择一人到的位置。
记这天内两人最远的距离为,决策使得最小,求这个最小的
解题思路
二分答案,判断是否存在一种决策使得两人最远距离不超过。
忽略两人的身份,第天一定有一个人的位置在,记录另一个人可能的位置集合。
对于二分点,遍历每个,更新,使得中的点与的距离不超过。
如果为空,说明不存在一种决策使得两人最远距离不超过。
参考程序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| const ll N = 200005; void solve() { ll n,x,y;cin >> n >> x >> y; create_vec(a,n); auto check = [&](ll d) -> bool{ set<ll> s; ll lst=y; if(abs(x-y)>d) return false; s.insert(x); for(auto t:a){ if(s.empty()) return false; if(abs(t-lst)<=d) s.insert(lst); while(!s.empty()&&*s.begin()<t-d) s.erase(s.begin()); while(!s.empty()&&*s.rbegin()>t+d) s.erase(*s.rbegin()); lst=t; }return !s.empty(); }; ll l=0,r=1e9; while(l<r){ ll mid=(l+r)/2; if(check(mid)) r=mid; else l=mid+1; }cout << l << endl; }
|
K.牛镇公务员考试
图论
题意
有道题,每道题的题目为:“第题的答案是()?”
每题有A B C D E
五个选项,选项的内容是字符串ABCDE
的一个排列,记为字符串
例如第题的题目为:
第题的答案是()?
A. B. C. D. E.
求答对所有题目的方案数
解题思路
将题目看作节点。
第道题决定了第道题的答案,视为一条从到的有向边。
同时,每个节点的出度为,这意味着每个连通分量都是一个内向基环树。
(内向基环树:每个节点的出度为的弱连通图)
反过来看,一旦确定了第道题的答案,第道题的答案也就确定了。
因此对于一条链,只要确定了一个节点的答案,整条链的答案也就唯一确定了。
显然在内向基环树中,链一定是挂在某个环上,链的答案随环的选择而唯一确定,因此可以忽略链。
对于环,先确定一个节点的答案(5种),然后递推确定整个环的答案,判断是否合法。
每个环的方案数在之间
最终答案为每个连通分量方案数的乘积
参考程序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
| void solve() { ll n;cin >> n ; vector<ll> a(n); vector<string> s(n); FORLL(i,0,n-1){ cin >> a[i] >> s[i]; a[i]--; } ll ans=1; vector<int> vis(n,-1); FORLL(i,0,n-1){ ll j=i; while(vis[j]==-1){ vis[j]=i; j=a[j]; } if(vis[j]!=i) continue; vector<ll> cycle; ll k=j; do{ cycle.push_back(k); k=a[k]; }while(k!=j); ll res=0,t; FORLL(i,0,4){ t=i; for(auto x:cycle) t=s[x][t]-'A'; if(t==i) res++; } multo(ans,res); }cout << ans << endl; }
|
L.要有光
诈骗题
题意
给了一些几何形状的方程,求在地面()上的最大阴影面积
解题思路
题目拐弯抹角吓唬人///
保证符合题意的状态是光源处于平面上()。
目的是求一个平面上的梯形阴影的面积。
上底长,下底长,高为,面积为。
参考程序
1 2 3 4 5 6
| void solve() { ll c,d,h,w; cin >> c >> d >> h >> w; cout << w*3*c << endl; }
|
M.牛客老粉才知道的秘密
2签
题意
某场比赛一共有道题目,但每面只能显示道。
点击下一页
时,如果后面的题目足够题,则显示下面的题,否则显示最后6题。
点击上一页
时,如果前面的题目足够题,则显示上面的题,否则显示最前6题。
求比赛中可能出现在第一题位置的题目数量。
解题思路
如果题目数量是的倍数,那页面可能的题目排布为。
如果题目数量不是的倍数,
从第一页到最后一页,可能的题目排布为;
从最后一页到第一页,可能的题目排布为。
去除首页尾页,可能的题目排布为。
参考程序
1 2 3 4 5 6 7
| #define N 200005 void solve() { ll n;cin >> n; if(n%6==0) cout << n/6 << endl; else cout << n/6*2 << endl; }
|