首页 > 其他分享 >2024牛客暑期多校训练营2 解题报告

2024牛客暑期多校训练营2 解题报告

时间：2024-07-20 19:31:13浏览次数：11  
标签：return ifac int 多校 2024 牛客 ans mod define

B-MST
对于整个序列进行一次kruskal
对于序列中 如果需要访问的点数小于300
那么将所有的点的边存入序列中进行kruskal
如果大于300
那么直接对于所有的点进行kruskal

点击查看代码 
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int mod=998244353;
int qpw(int a,int b){int ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
int inv(int x){return qpw(x,mod-2);}
int fac[100005],ifac[100005];
const int N=1e5+10;
int f[N];
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}
unordered_map<int,int>mp[N];
bool merge(int x,int y){
    int fx=find(x),fy=find(y);
    if(fx==fy)return false;
    f[fy]=fx;
    return true;
}
struct Link{
    int x,y,w;
}L[N];
int n,m,q;
int h,vis[N];
void Solve(){
    cin>>h;
    vector<int>a(h);
    for(int i=0;i<h;i++)cin>>a[i],f[a[i]]=a[i];
    int ans=0;
    int sz=h;
    if(h>=300){
        for(auto x:a)vis[x]=1;
        for(int i=1;i<=m;i++){
            if(vis[L[i].x]&&vis[L[i].y]){
                if(merge(L[i].x,L[i].y)){
                    ans+=L[i].w;
                    sz--;
                }
            }
        }
        for(auto x:a)vis[x]=0;
    }else {
        sort(a.begin(),a.end());
        vector<int>e;
        for(int i=0;i<h;i++){
            int x=a[i];
            for(int j=i+1;j<h;j++){
                int y=a[j];
                if(mp[x].count(y))e.pb(mp[x][y]);
            }
        }
        sort(all(e));
        for(auto i:e){
            if(merge(L[i].x,L[i].y)){
                ans+=L[i].w;
                sz--;
            }
        }
    }
    if(sz==1){
        cout<<ans<<'\n';
    }else cout<<-1<<'\n';


}
void solve(){

    cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        cin>>L[i].x>>L[i].y>>L[i].w;
        if(L[i].x>L[i].y)swap(L[i].x,L[i].y);
    }
    sort(L+1,L+m+1,[&](Link a,Link b){return a.w<b.w;});
    for(int i=1;i<=m;i++){
        if(!mp[L[i].x].count(L[i].y)){
            mp[L[i].x][L[i].y]=i;
        }
    }
    while(q--)Solve();
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int _=1;
//    cin>>_;
    while(_--)solve();
}
C-Red Walking on Grid 通过观察可以得知对于前一个点 如果前两个点为R 那么当前节点 直接考虑前缀最优 如果只有当前一个点为R 那么选择继承前一个点的最优 如果全为W 则不用继承
点击查看代码 
#include<bits/stdc++.h>

#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
const int N=1e6+10;
using namespace std;
const int mod = 998244353;
vector<vector<char> >a(N,vector<char>(2));
vector<vector<int> >dp(N,vector<int>(2));
void solve() {
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i][0];
    }
    for(int i=1;i<=n;i++){
        cin >> a[i][1];
    }
    a[0]={'W','W'};
    a[n+1]={'W','W'};
    int mx=0;
    for(int i=1;i<=n;i++){
        int w0=dp[i-1][0];
        int w1=dp[i-1][1];
        if(a[i][0]=='R'&&a[i][1]=='R'){
            dp[i][0]=max(w0+1,w1+2);
            dp[i][1]=max(w1+1,w0+2);
        }else if(a[i][0]=='R'){
            dp[i][0]=w0+1;
        }else if(a[i][1]=='R'){
            dp[i][1]=w1+1;
        }

        mx=max({mx,dp[i][0],dp[i][1]});
    }
    int ans=0;
    cout <<max(mx-1,ans);
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int _ = 1;
//    cin>>_;
    while (_--)solve();
}
E-GCD VS XOR 通过观察得知直接lowbit即可
点击查看代码 
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int mod=1e9+7;
int qpw(int a,int b){int ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
int inv(int x){return qpw(x,mod-2);}
int fac[100005],ifac[100005];
void qjc(int n){
    fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
    ifac[n]=inv(fac[n]);
    for(int i=n-1;i>=1;i--)ifac[i]=ifac[i+1]*(i+1)%mod;
    ifac[0]=1;
}
int C(int m,int n){return fac[m]*ifac[m-n]%mod*ifac[n]%mod;}
void solve(){
    int x;cin>>x;
    int res=x&-x;
    if(x-res==0){
        cout<<-1<<'\n';
    }else cout<<x-res<<'\n';
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int _=1;
    cin>>_;
    while(_--)solve();
}

H-Instructions Substring
通过观察得知
每个序列能否满足情况
即为对于前缀和pre[i]
pre[i]-pre[j]==x
这时即可满足情况
对于前面每组满足情况的经过
后面所有的情况都可以满足
所有乘完只会需要清空map中存储的状态

点击查看代码 
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int mod=998244353;
int qpw(int a,int b){int ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
int inv(int x){return qpw(x,mod-2);}
int fac[100005],ifac[100005];
void qjc(int n){
    fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
    ifac[n]=inv(fac[n]);
    for(int i=n-1;i>=1;i--)ifac[i]=ifac[i+1]*(i+1)%mod;
    ifac[0]=1;
}
int C(int m,int n){return fac[m]*ifac[m-n]%mod*ifac[n]%mod;}
int prex[200005]={0};int prey[200005]={0};
map<pii,int>mp;map<pii,int>cnt;map<pii,int>mins;
void solve(){
    int n,x,y;cin>>n>>x>>y;
    string s;cin>>s;
    for(int i=1;i<=n;i++){
        if(s[i-1]=='D'){
            prex[i]=prex[i-1]+1;
            prey[i]=prey[i-1];
        }
        else if(s[i-1]=='A'){
            prex[i]=prex[i-1]-1;
            prey[i]=prey[i-1];
        }
        else if(s[i-1]=='S'){
            prex[i]=prex[i-1];
            prey[i]=prey[i-1]-1;
        }else if(s[i-1]=='W'){
            prex[i]=prex[i-1];
            prey[i]=prey[i-1]+1;
        }
    }
    int ans=0;
    if(x==0&&y==0){
        cout<<n*(n+1)/2<<'\n';return;
    }
    for(int i=0;i<=n;i++){
        cnt[{x+prex[i] ,y+prey[i]}]++;
//        if(x==0&&y==0&&i>0){
//            ans+=n-i+1;
//            continue;
//        }
        if(i>0)ans+=(cnt[{prex[i],prey[i]}])*(n-i+1),cnt[{prex[i],prey[i]}]=0;
//        cout<<ans<<'\n';
    }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int _=1;
//    cin>>_;
    while(_--)solve();
}
H-Red Playing Cards 按照数字从大到小进行删除 其中对于每个区间取最大 赛时未想出如何将首尾进行合并 其实只需要将首位加0 在进行一次操作即可
点击查看代码 
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int mod=998244353;
int qpw(int a,int b){int ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
int inv(int x){return qpw(x,mod-2);}
int fac[100005],ifac[100005];
void qjc(int n){
    fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
    ifac[n]=inv(fac[n]);
    for(int i=n-1;i>=1;i--)ifac[i]=ifac[i+1]*(i+1)%mod;
    ifac[0]=1;
}
int C(int m,int n){return fac[m]*ifac[m-n]%mod*ifac[n]%mod;}
const int N=3e3+10;
const int M=1e5+10;
int tr[M];
int query(int x){
    int ans=0;
    while(x){
        ans+=tr[x];
        x-=x&-x;
    }
    return ans;
}
void add(int x,int v){
    while(x<=M-10){
        tr[x]+=v;
        x+=x&-x;
    }
}
int dp[N];
int l[N],r[N];
int len[N];
int vis[N*2];
int g[M];
int f[M];
void solve(){
    int n;cin>>n;
    vector<int>a(2*n+10);
    memset(dp,0,sizeof(dp));
    int m=n;
    n=n*2+2;
    for(int i=2;i<=n-1;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        if(!l[a[i]])l[a[i]]=i;
        else r[a[i]]=i;
    }
    for(int i=m;i>=0;i--){
        int L=l[i],R=r[i];
        for(int j=L-1;j<=R;j++)g[j]=0;
        for(int j=L;j<=R;j++){
            g[j]=g[j-1]+i;
            if(a[j]>i&&j==r[a[j]]){
                int k=l[a[j]];
                if(k>=L){
                    g[j]=max(g[j],g[k-1]+f[a[j]]);
                }
            }
        }
        f[i]=g[R];
    }
    cout<<f[0];
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int _=1;
//    cin>>_;
    while(_--)solve();
}

标签：return,ifac,int,多校,2024,牛客,ans,mod,define
From： https://www.cnblogs.com/archer233/p/18313633

相关文章

  • 国开大学2024《企业法律实务（省开课）》
    5.当事人互负债务，没有先后履行顺序的，应当（）A.同时履行B.法院判决C.去法院起诉D.申请仲裁答案：A6.商务谈判法律实务是指企业法务人员在民商事谈判活动中运用（）知识，按照商业规则，促成商业交易成就或阻止商业交易成就的行为活动。A.法律   B.商业C.专业D.谈判答案：A7.根据......
  • 2024年IDEA&IntelliJ系列最新激活码(2088)！
    蛋疼ing，仅供学习使用。K384HW36OB-eyJsaWNlbnNlSWQiOiJLMzg0SFczNk9CIiwibGljZW5zZWVOYW1lIjoibWFvIHplZG9uZyIsImxpY2Vuc2VlVHlwZSI6IlBFUlNPTkFMIiwiYXNzaWduZWVOYW1lIjoiIiwiYXNzaWduZWVFbWFpbCI6IiIsImxpY2Vuc2VSZXN0cmljdGlvbiI6IiIsImNoZWNrQ29uY3VycmVudFVzZSI6ZmFsc2U......
  • 2024年 Intellij IDEA | idea&IDEA系列激活码（持续更新）
       声明：仅供学习使用：K384HW36OB-eyJsaWNlbnNlSWQiOiJLMzg0SFczNk9CIiwibGljZW5zZWVOYW1lIjoibWFvIHplZG9uZyIsImxpY2Vuc2VlVHlwZSI6IlBFUlNPTkFMIiwiYXNzaWduZWVOYW1lIjoiIiwiYXNzaWduZWVFbWFpbCI6IiIsImxpY2Vuc2VSZXN0cmljdGlvbiI6IiIsImNoZWNrQ29uY3VycmVudFVzZSI6ZmFsc......
  • 2024年Intellij IDEA&& idea系列激活码（持续更新）
    声明：仅供学习使用声明：仅供学习使用：K384HW36OB-eyJsaWNlbnNlSWQiOiJLMzg0SFczNk9CIiwibGljZW5zZWVOYW1lIjoibWFvIHplZG9uZyIsImxpY2Vuc2VlVHlwZSI6IlBFUlNPTkFMIiwiYXNzaWduZWVOYW1lIjoiIiwiYXNzaWduZWVFbWFpbCI6IiIsImxpY2Vuc2VSZXN0cmljdGlvbiI6IiIsImNoZWNrQ29uY3VycmVudF......
  • NOID2024 游记
    流水账。Day-13中考7.2考完，7.4就被gj叫过来集训了。和同学讨论了一下，发现自己语文作文很可能会偏题，很可能考不上JellyFish中学。Day-12背笔试，比较简单，很快就背完了。mx这几天每天都有模拟赛，比较累。Day-6丢失了一场模拟赛。中午去吃饭去晚了，被迫吃屎。Day-4......
  • ACL 2024 | 对25个开闭源模型数学评测，GPT-3.5-Turbo才勉强及格
    大型语言模型（LLMs）在解决问题方面的非凡能力日益显现。最近，一个值得关注的现象是，这些模型在多项数学推理的基准测试中获得了惊人的成绩。以GPT-4为例，在高难度小学应用题测试集GSM8K[1]中表现优异，准确率高达90%以上。同时，许多开源模型也展现出了不俗的实力，准确率超过80%......
  • 2024“钉耙编程”中国大学生算法设计超级联赛（1）
    发挥相当差，最好笑的是1h没写出一个三维偏序、30min没写出一个字符串哈希。甚至1h没意识到组合数式子推错了。A我写了点阴间东西。假设模式串为ABC，考虑一个形如ABCABCABC的东西，如果长度是\(x\)，会贡献\(x-n+1\)个子串。枚举\(i\)，从\(i\)把\(T\)分成两部分，一部分......
  • 2024牛客暑期多校训练营2 HI
    2024牛客暑期多校训练营2H.InstructionsSubstring题意：有一个字符串序列，有WSAD四种操作，可以上下左右移动。可以选取一段连续的子序列，从（0,0）出发，经过连续子序列操作后可以经过点(x,y)，问这样的子序列有多少个思路：若一个子序列能够实现到达点（x,y），那么在这个子序列后面加任意字符都......
  • 2024 暑假友谊赛 2
    B.TilingChallenge1.我的方法是按顺序遍历，遇到'.'时就检查一下它的上下左右是不是都是点，如果都是点的话，标记这个点，把这个点和他上下左右都标记为‘？’，但是要加一个条件，如果‘.’的个数不是5的倍数就不符合题意，不加这个会wa37，我也不知道为什么#include<bits/stdc++.h>#defin......
  • NOI 2024 退役记
    NOI2024结束了，我的OI生涯也告一段落了。怎么说呢，今年变动挺大的，Day1之前确实完全没有做好准备，考场策略全乱套了，最后Day1考151分，直接垫底了，T1是个小难写的ds，我做法反正很难写且常数大，最后调完了也没卡常卡过去，拿了80，还浪费了巨大长时间，场上看到有了pretest我也很......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99