【题解】牛客小白月赛28
题目难度不是很大，但是后面有些题比较麻烦
很多题目表示不是很清楚，努力修改（求轻喷）
个人认为题目难度：
简单题：A/B/D
中等题：C/G/H/I/J
困难题：E/F
然后感谢给我验题的大佬们：
henry_y,JQK2020,ZZUPeanut,lifehappy,issue是云哥的小迷×呀,王清楚（清楚姐姐TQL）
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-8;
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
const int maxn=1e5+10;
const double pi=acos(-1.0);
ll Pow(ll a, ll b){
ll ans = 1;
while(b > 0){
if(b & 1){
ans = ans * a % mod;
}
a = a * a % mod;
b >>= 1;
}
return ans;
}
ll inv(ll b){
return Pow(b,mod-2)%mod;
}
int main(){
int _;
scanf("%d",&_);
while(_--){
ll n,m;
scanf("%lld%lld",&n,&m);
ll x=inv(n);
printf("%lld\n",(mod+1-Pow(x,m))%mod);
}
return 0;
}
这样发现其实就是两个等差数列，设t=abs(x-y), 如果t=3n-1或者t=3n-2那么就可以成立，所以直接t%3==1或者t%3==2即是必胜态
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define SZ(x) (int)x.size()
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int maxn = 1e6 + 10;
const int N = 3e2 + 5;
const ll inf = 0x3f3f3f3f;
const ll oo = 8e18;
const int dir[][2]={{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
int main()
{
int _;
cin >> _;
while (_--) {
int x, y;
cin >> x >> y;
ll t = abs(x - y);
if (1 == t % 3 || 2 == t % 3) cout << "yyds" << endl;
else cout << "awsl" << endl;
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define SZ(x) (int)x.size()
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod = 1e9 + 7;
const int mod = 998244353;
const double eps = 1e-6;
const double pi = acos(-1.0);
const int maxn = 1e6 + 10;
const int N = 5e3 + 5;
const ll inf = 0x3f3f3f3f;
const int dir[][2]={{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
int n, match[maxn];
string s;
int getv(char c) {
return c - 'A' + 1;
}
ll solve(int l, int r) {
ll res = 0, num = 0;
for (int i = l; i <= r; i++) {
if (s[i] == '(') {
ll tmp = solve(i + 1, match[i] - 1);
i = match[i] + 1;
while (i <= r && isdigit(s[i])) num = num * 10 + s[i] - '0', i++;
i--;
if (num)
res += num * tmp;
else res += tmp;
num = 0;
}
else {
if (i + 1 <= r && isdigit(s[i + 1])) {
int x = i + 1;
while (x <= r && isdigit(s[x])) num = num * 10 + s[x] - '0', x++;
res += num * getv(s[i]);
i = x - 1;
num = 0;
}
else res += getv(s[i]);
}
}
return res;
}
int main()
{
cin >> s;
n = s.length();
s = '.' + s;
stack<int> st;
for (int i = 1; i <= n; i++) {
if (s[i] == '(') st.push(i);
else if (s[i] == ')') match[st.top()] = i, st.pop();
}
cout << solve(1, n);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-8;
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
const int maxn=1e5+10;
const double pi=acos(-1.0);
int main(){
int _;
scanf("%d",&_);
while(_--){
ll x,y;
scanf("%lld%lld",&x,&y);
ll z=x-2*y;
if(z<0||z&y)puts("-1");
else printf("%lld\n",z);
}
return 0;
}
对于右边的山峰，用线段树直接维护最大最小值，以及最小值的位置即可，然后直接进行单点修改即可
对于左边的山峰，先用线段树判断是否存在比当前值大的值，如果存在考虑找第一个最大的，直接暴力找第一个大的可能会超时，那么考虑二分
我们现在需要找的是区间的第一个比当前数大的值，因为已经确定了右端点，左端点应该是整个数轴的最左端，但是这个左端点，可以是那个第一个比当前数的数的位置
并且，这个左端点越往左，这个区间的最大值就越大，所以，这就找到了一个二分的条件，直接去枚举那个左端点，使得尽量靠右但又能大于当前值，每次更新
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-8;
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
const int maxn=2e5+10;
const double pi=acos(-1.0);
struct tree{
int l,r,mx,mi,pos;
}t[maxn<<2];
struct node{
int x,h,id;
bool operator<(const node &p){
return x<p.x;
}
}a[maxn];
bool cmp(node a,node b){
return a.id<b.id;
}
int b[maxn];
void pushup(int p){
t[p].mx=max(t[p<<1].mx,t[p<<1|1].mx);
if(t[p<<1].mi<=t[p<<1|1].mi){
t[p].mi=t[p<<1].mi;
t[p].pos=t[p<<1].pos;
}
else{
t[p].mi=t[p<<1|1].mi;
t[p].pos=t[p<<1|1].pos;
}
}
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
if(l==r){
t[p].mx=t[p].mi=a[l].h;
t[p].pos=l;
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
}
void modify(int p,int pos,int v){
if(t[p].l==t[p].r){
t[p].mx=t[p].mi=v;
return;
}
int mid=t[p].l+t[p].r>>1;
if(pos<=mid)modify(p<<1,pos,v);
else modify(p<<1|1,pos,v);
pushup(p);
}
int querymax(int p,int l,int r){
if(l<=t[p].l&&r>=t[p].r){
return t[p].mx;
}
if(l>t[p].r||r<t[p].l)return 0;
int ans = 0;
int mid = t[p].l+t[p].r>>1;
ans=max(ans,querymax(p<<1,l,r));
ans=max(ans,querymax(p<<1|1,l,r));
return ans;
}
int querymin(int p,int l,int r,int &pos){
if(l<=t[p].l&&r>=t[p].r){
pos=t[p].pos;
return t[p].mi;
}
if(l>t[p].r||r<t[p].l)return inf;
int ans = inf,pl,pr;
int t1=querymin(p<<1,l,r,pl);
int t2=querymin(p<<1|1,l,r,pr);
if(t1<=t2)ans=t1,pos=pl;
else ans=t2,pos=pr;
return ans;
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].x,&a[i].h);
b[i]=a[i].x;
a[i].id=i;
}
sort(a+1,a+1+n);
build(1,1,n);
for(int i=1;i<=n;i++){
int p=lower_bound(a+1,a+1+n,(node){b[i],0,0})-a;
if(p<n&&querymax(1,p+1,n)<=a[p].h){
int pos;
querymin(1,p+1,n,pos);
a[pos].h=a[p].h;
modify(1,pos,a[p].h);
}
if(p==1||querymax(1,1,p-1)<=a[p].h)continue;
int l=1,r=p-1,pos;
while(l<=r){
int mid=l+r>>1;
if(querymax(1,mid,p-1)>a[p].h)l=mid+1,pos=mid;
else r=mid-1;
}
a[pos].h=a[p].h;
modify(1,pos,a[p].h);
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
printf("%d ",a[i].h);
return 0;
}
三分
每个健身器材的力量增加值都是，也就是不管哪一天来，牛牛都会用当天两种力量增加最小的器材进行锻炼，当天的力量增加为
由于和0的关系是不确定的，所以让所有曲线两两组合，画出新的曲线，曲线的斜率有大于0和小于0的，把所有曲线画在一张图上，在每天取当天所有直线的最小值，可以发现，最终取到的将会是一个类似凸函数的形状，这样就可以确定了用的三分算法，三分天数，看当天锻炼力量增加最小的两种器材，这就是当天的值
通过三分算出这凸函数的顶点即可
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
const int inf=0x3f3f3f3f;
const int mod=1e4+7;
const double eps=1e-8;
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
const int maxn=1e5+10;
const double pi=acos(-1.0);
ll a[2010],b[2010],n,m;
ll check(ll x){
ll res=8e18;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
res=min(res,(a[i]+a[j])*x+(b[i]+b[j]));
return res;
}
int main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld%lld",a+i,b+i);
ll l=1,r=m,ans=-8e18;
while(l+10<r){
ll lm=l+(r-l)/3,rm=r-(r-l)/3;
if(check(lm)>check(rm))r=rm;
else l=lm;
}
for(int i=l;i<=r;i++){
ans=max(ans,check(i));
}
printf("%lld",ans);
return 0;
}
题目的最终意思就是用最开始给的字符串作为模式串，剩下每次给出的串作为被匹配的串进行匹配，每次记录一下模式串最多能匹配多少即可，直接套一下KMP的模版，里面加更新一下模式串的最大匹配长度
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-8;
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
const int maxn=1e5+10;
const double pi=acos(-1.0);
string pa,str;
int nx[maxn];
inline void GetNext()
{
int i = 0, j = -1, len = pa.length();
nx[i] = j;
while(i < len){
while( j != -1 && pa[i] != pa[j]) j = nx[j];
nx[++i] = ++j;
}
}
int Kmp()
{
int res=0;
int i =0, j = 0, lens=str.length(),lenp=pa.length();
while(i < lens && j < lenp){
while( j != -1 && str[i] != pa[j]) j = nx[j];
i++, j++;
res=max(res,j);
if(res==lenp)return res;
}
return res;
}
int main(){
cin>>pa;
GetNext();
int n,ans=0;
scanf("%d",&n);
while(n--){
cin>>str;
ans+=Kmp();
}
printf("%d\n",ans);
return 0;
}
单源最短路问题
已经确定了起点和终点，只需要建图即可，因为车站是一个单向行驶，两两建一条单向边，两个相邻点可以互相走，建一个双向边，最后跑一个单源最短路就是答案了。
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-8;
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
const int maxn=1e5+10;
const double pi=acos(-1.0);
int n,m,s,t,T;
int ti[maxn],last[maxn],dis[maxn];
vector<pii> g[maxn];
void dij(){
memset(dis,inf,sizeof dis);
dis[s]=0;
priority_queue<pii,vector<pii>,greater<pii> >q;
q.push(mp(0,s));
while(!q.empty()){
pii p=q.top();
q.pop();
int u=p.se;
if(dis[u]<p.fi)continue;
for(int i=0;i<g[u].size();i++){
int v=g[u][i].fi,w=g[u][i].se;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push(mp(dis[v],v));
}
}
}
}
int main(){
scanf("%d%d%d%d%d",&n,&m,&s,&t,&T);
for(int i=1;i<=m;i++)
scanf("%d",ti+i);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
if(last[x])g[last[x]].pb(mp(i,ti[x]));
last[x]=i;
if(i){
g[i].pb(mp(i-1,T));
g[i-1].pb(mp(i,T));
}
}
dij();
printf("%d\n",dis[t]);
return 0;
}
最经典的问题就是，从只能往右和往下走，走到
有多少种方案数，如果用DP去写，状态转移就是
那么这道题问的是有多少种和，并且发现他的和是取余的，不会超过，所以加一维，用一个背包维护一下每个位置可以得到的和，分别从上和左转移过来。
数组就成了在从
到
是否能组成
这个数
注意转移的时候有取余的情况，所以可能会出现相减小于0的时候，需要加mod
最终计算一下里有多少个能组成的数
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
const int inf=0x3f3f3f3f;
const int mod=1e4+7;
const double eps=1e-8;
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
const int maxn=1e5+10;
const double pi=acos(-1.0);
bool dp[110][110][10010];
ll a[110][110];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
a[i][j]%=mod;
}
dp[1][1][a[1][1]]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=mod-1;k>=0;k--){
dp[i][j][k]|=dp[i-1][j][(k-a[i][j]+mod)%mod];
dp[i][j][k]|=dp[i][j-1][(k-a[i][j]+mod)%mod];
}
int ans=0;
for(int i=0;i<mod;i++)
if(dp[n][m][i])ans++;
printf("%d\n",ans);
return 0;
}
并查集
对于每个点来说，能到达的点就是和他直接或间接相连的同类型点，间接到达就是可以从当前点直接相连点的能够到达的点，所以可以考虑用并查集。
把两个有边并且类型相同的点放入一个集合，最终找出集合个数最大的集合，并输出这些点，可能有多个集合最大，需要一并统计。
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-8;
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
const int maxn=2e5+10;
const double pi=acos(-1.0);
int fa[maxn],sz[maxn],col[maxn];
int find(int x){
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",col+i);
fa[i]=i;
}
for(int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
if(col[u]==col[v])fa[find(u)]=find(v);
}
set<int> ans;
int mx=0;
for(int i=1;i<=n;i++){
sz[find(i)]++;
mx=max(mx,sz[find(i)]);
}
for(int i=1;i<=n;i++)
if(sz[find(i)]==mx)ans.insert(i);
printf("%d\n",ans.size());
for(auto i:ans)printf("%d ",i);
return 0;
}
yyds
投递小米集团等公司10个岗位 >
