2024牛客多校第二场

B MST

类似根号分治的思路，点数少的跑Prim，点数大的跑Kruscal

有个坑点是分界点调100过不了，90能卡过去

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
const ll inf = 1e16;
int n,m,Q;
struct ed{
    int u,v,w;
}edge[N<<1];
bool cmp(ed a,ed b){
    return a.w<b.w;
}


map<int,int>e[N];
struct S {
    int u;
    int d;
};
bool operator<(const S &x, const S &y) { return x.d > y.d; }
priority_queue<S> q;
int a[N];
bool vis[N];
void Prim(int n){
//    cout<<"Prim\n";
    for(int i=1;i<=n;i++) cin>>a[i],vis[a[i]]=0;
    
    q.push({a[1], 0});
    int cnt = 0;
    ll res=0;
    while (!q.empty() && cnt<=n ) {
        int u = q.top().u, d = q.top().d;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        ++cnt;
        res += d;
        //cout<<u<<" : "<<d<<"\n";
        for (int i = 1; i <= n ; i++ ) {
            int v = a[i];ll w = e[u][v];
            if (!vis[v] && w ) {
                q.push({v, w});
            }
        }
    }
    for(int i=1;i<=n;i++) vis[a[i]]=0;
    if(cnt>=n) cout<<res<<"\n";
    else cout<<-1<<"\n";
}

int pa[N];
int find(int x){
    if(pa[x]!=x) return pa[x]=find(pa[x]);
    return x;
}
void kruscal(int n){
//    cout<<"kruscal"<<"\n";
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) pa[a[i]]=a[i],vis[a[i]]=1;
    ll tot=0;
    int use=0;
    for(int i=1;i<=m;i++){
        if(!vis[edge[i].v] || !vis[edge[i].u] ) continue;
        int f1=find(edge[i].u),f2=find(edge[i].v);
        if(f1!=f2){
            tot+=edge[i].w;
            pa[f1]=f2;
            use++;
        }
    }
    if(use==n-1) cout<<tot<<"\n";
    else cout<<-1<<"\n";
    for(int i=1;i<=n;i++) pa[a[i]]=a[i],vis[a[i]]=0;
}

int main(){
//    freopen("3.in","r",stdin);
//    freopen("lys.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>Q;
    int cnt=0;
    for(int i=1;i<=m;i++){
        int u,v,w;cin>>u>>v>>w;
        cnt++;
        edge[cnt]=(ed){u,v,w};
        e[u][v]=w;
        e[v][u]=w;
    }
    sort(edge+1,edge+1+m,cmp);
    int base=90;
    while(Q--){
        //TODO
        int k;cin>>k;
        if(k<=base){ // prim
            Prim(k);
        }
        else kruscal(k);
    }
}

C

发现从左上角开始走是最优的，确定了起点就和普通递推没什么区别了

#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e6+505;
int n,res;
string c[2];
int f[N][2],s[N][2];
int main(){
    cin >> n;
    cin >> c[0] >> c[1];
    for (int i=1;i<=n;i++)
        for (int j=0;j<2;j++)
            if (c[j][i-1]=='R') s[i][j]=1;
    for (int i=1;i<=n;i++){
        for (int j=0;j<2;j++){
            if (s[i][j]){
                f[i][j]=f[i-1][j]+1;
                if (s[i][j^1])
                    f[i][j]=max(f[i][j],f[i-1][j^1]+2);
            }    
            res=max(res,f[i][j]);        
        }
    }
    
    if (res!=0) cout << res-1 << endl;
        else cout << 0 << endl;
    return 0;
}

E

#include<cstdio>
#include<iostream>
#define int long long
using namespace std;
int T,x;
int lowbit(int x){
    return x&(-x);
}
void work(){
    cin >> x;
    int res=x-lowbit(x);
    if (res) cout << res << endl;
        else cout << -1 << endl;
}
signed main(){
    cin >> T;
    while(T--) work();
    return 0;
}

H

考虑拆成两维转化成前缀和，能经过点（x,y)首先要能走到(x,y)

对于固定的右端点r，相当于问有多少个点i满足

sumx[r]-sumx[i-1]=x

sumy[r]-sumy[i-1]=y

问题变成求这些点的后缀和，正着求不好求还可能算重，倒叙枚举i=n;i>=1;i--

对于当前枚举到的i，可能有很多的 j 比 i 大且都符合上面两个式子

只计算最小的那个 j ，显然只要加上这个 j 对应的后缀，所有的 j 都能不重不漏地考虑到

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5,dx[]={1,-1,0,0},dy[]={0,0,-1,1};
int n,x,y,ans=0;
char s[N+5];
map< pair<int,int>,int> sum;
int Mov(char ch)
{
    if(ch=='W') return 3;
    else if(ch=='S') return 2;
    else if(ch=='A') return 1;
    else return 0;
}
void Kafka()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>x>>y;
    cin>>s+1;
    if(x==0&&y==0)
    {
        cout<<n*(n+1)/2<<endl;
        return;
    }
    sum[make_pair(0,0)]=n;
    int Sx=0,Sy=0;
    for(int i=n;i;--i)
    {
        int now=Mov(s[i]);
        Sx+=dx[now],Sy+=dy[now];
//        printf("i=%d x=%d y=%d\n",i,Sx,Sy);
        int Nx=Sx-x,Ny=Sy-y;
        if(sum.find(make_pair(Nx,Ny))!=sum.end()) ans+=n-sum[make_pair(Nx,Ny)]+1;
        sum[make_pair(Sx,Sy)]=i-1;
//        printf("i=%d ans=%d\n",i,ans);
    }
    cout<<ans<<endl;    
}
signed main()
{
    Kafka();
    return 0;
}