【题解】牛客小白月赛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;
}