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

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

时间：2024-07-19 19:52:17浏览次数：16  
标签：arr ch return int 多校 2024 牛客 ans define

A-A Bit Common
通过该题的性质可以知道
偶数的关系不影响能够成立的序列
我们只讨论最后一位为1的数 这些数才能对该序列造成影响
又因为对于每个特殊序列中 每位必定有一个0
所以特殊序列的个数为C(n,k)*2((m-1)*(m-n))*(2(m-1)-1)^(n-k)

点击查看代码 
#include<bits/stdc++.h>

#define int long long
#define max(a, b) ((a)>(b)? (a):(b))
#define min(a, b) ((a)<(b)? (a):(b))
#define all(x) (x).begin(),(x).end()
#define lowbit(x) ((x)&(-x))
using namespace std;
const int N = 5e5 + 10;
const int M = 1e9 + 10;
const int INF = 0x3f3f3f;
//const int mod = 1e9+7;

int mod;

int qp(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 exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int x1, y1, d;
    d = exgcd(b, a % b, x1, y1);
    x = y1, y = x1 - a / b * y1;
    return d;
}

int norm(int x, int MOD = mod) { return (x % MOD + MOD) % MOD; }

int inv(int a, int b = mod) {
    int x, y;
    exgcd(a, b, x, y);
    return norm(x, b);
}

int jie(int x) {
    int ans = 1;
    for (int i = 1; i <= x; i++) {
        ans = ans * i % mod;
    }
    return ans % mod;
}
namespace CNM
{
    const int N = 5e3 + 7;
    int c[N][N];
    void init(int n)
    {
    for (int i = 0; i <= n; i++)
    for (int j = 0; j <= i; j++)
    c[i][j] = 0 < j && j < i ? (c[i - 1][j - 1] + c[i - 1][j]) % mod : 1;
    }
int getc(int n, int m)
{
if (n == m && m == -1)
return 1;
if (n < m || m < 0)
return 0;
return c[n][m];
}
}
//int C(int n, int m) {
//    return  norm(  norm (jie(m) *  inv(jie(n)) )  *  inv(jie(m - n))  %  mod );
//}

void solve() {                  //2 3 17;2 4 43;2 5 113;
    int n, m, ans = 0;
    cin >> n >> m >> mod;
    CNM::init(n);
    for (int i = 1; i <= n; i++) {
        int res=1;
        res=res*norm( CNM::getc(n,i))%mod;
        res=res*norm(qp( norm( qp(2, i) - 1 ), (m - 1) ))%mod;
        res=res*norm(qp(norm(qp(2,n-i)%mod),m-1))%mod;
        ans=(ans+res)%mod;
        ans=norm(ans);

//         ans = norm(an)
        //        ans += C(i, n)
//                * (qp((( + mod) % mod) % mod, (m - 1)) % mod
//                * qp(qp(2, n - i), (m - 1))) % mod;
//        ans %= mod;
    }
    cout << ans;
}


signed main() {
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    int _ = 1;
    //cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

B-A Bit More Common

对于每位假设其为特殊位
对于每个特殊位 我们可以从小到大的进行递推
因为上一位如果加入一个新的特殊位
会造成当前序列多出i个
我们得出递推方程 dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])*i
再将A题算出的序列数减去特殊位的序列数即为答案数

点击查看代码 
#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;
int mod,n,m;
int c[5050][5050],dp[5050][5050],fc[5050],s[5050][5050];
int pw2[5050];
int qpw(int x,int y){
    int res=1;for(;y;y>>=1,x=x*x%mod){
        if(y&1)res=res*x%mod;
    }
    return res;
}
void solve(){
    cin>>n>>m>>mod;
    pw2[0]=1;
    for(int i=1;i<=5000;i++)pw2[i]=pw2[i-1]*2%mod;
    fc[0]=1;
    for(int i=1;i<=5000;i++)fc[i]=fc[i-1]*i%mod;
    c[0][0]=1;
    for(int i=1;i<=5000;i++){
        c[i][0]=1;
        for(int j=1;j<=i;j++){
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
        }
    }
    dp[0][0]=1;
    for(int i=1;i<=5000;i++){
        for(int j=1;j<=i;j++){
            dp[i][j]=(dp[i-1][j-1]*j%mod+dp[i-1][j]*j%mod)%mod;
        }
    }
    int ans=0;
    if(m==1){
        ans=0;
        ans=((pw2[n]-n-1)%mod+mod)%mod;
        cout<<ans<<'\n';return;
    }
    for(int i=1;i<=n;i++){
        int zrocnt=1;
        zrocnt=qpw(qpw(2,n-i),m-1);
        int onecnt=1;
        onecnt=qpw((qpw(2,i)-1+mod)%mod,m-1)%mod;
        int sg=0;
        int lfonebitcnt=1;
        int tmp=(pw2[i]-c[i][1]-c[i][0]+mod+mod)%mod;
        for(int k=m-1;k;k--){
            int lf=m-1-k;
            sg=(sg+c[m-1][k]*dp[k][i]%mod*lfonebitcnt)%mod;
            lfonebitcnt=lfonebitcnt*tmp%mod;
        }
        ans=(ans+c[n][i]*(onecnt-sg+mod)%mod*zrocnt)%mod;
    }
    cout<<ans;
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int _=1;
//    cin>>_;
    while(_--)solve();
}
C-Sum of Suffix Sums 简单前缀和
点击查看代码 
#include<bits/stdc++.h>

#define int long long
#define max(a, b) ((a)>(b)? (a):(b))
#define min(a, b) ((a)<(b)? (a):(b))
#define all(x) (x).begin(),(x).end()
#define lowbit(x) ((x)&(-x))
using namespace std;
const int N = 5e5 + 10;
const int M = 1e9 + 10;
const int INF = 0x3f3f3f;
const int mod = 1e9+7;

int qp(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 qp(x, mod - 2); }

vector<int>a(N);
vector<int>ans(N);

void solve() {
    int  q,len=0;
    cin >> q;
    for(int i=0;i<q;i++){
        int t,v;
        cin >> t >> v;
        len=len-t+1;
        a[len]=((len*v)%mod+(a[len-1])%mod)%mod;
        ans[i]=a[len];
    }
    for(int i=0;i<q;i++) cout << ans[i] <<'\n';
}


signed main() {
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    int _ = 1;
    //cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

D-XOR of Suffix Sums
对于每个数 枚举它的二进制位的影响
考虑到这是个计算后缀的方式
又因为会不断地修改末尾的数
那我们维护一个前缀和
每个后缀和i相当于pre[n]-pre[i-1];
创造一个树状数组
对于每位2^i %(2^(i+1))并且分类讨论能否使其成立

点击查看代码 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2097152;
struct BIT{
    int tr[N+50];
    int lowbit(int x){return (x&(-x));}
    void real_add(int x,int val){
        for(int i=x;i<=N;i+=lowbit(i))tr[i]+=val;
    }
    int real_query(int x){
        int ans=0;
        for(int i=x;i>=1;i-=lowbit(i))ans+=tr[i];
        return ans;
    }
    void add(int x,int val){
        x++;
        real_add(x,val);
    }
    int query(int l,int r){
        l++,r++;
        return real_query(r)- real_query(l-1);
    }
};
BIT bit[30];
const int maxL=20;
const int mod=(1<<(maxL+1));
const int maxn=5e5;
int sz=0;
int stk[maxn+50];
int sum[maxn+50];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int q;cin>>q;
    while(q--){
        int t,v;cin>>t>>v;
        v%=mod;
        for(int cc=1;cc<=t;cc++){
            for(int len=0;len<=maxL;len++){
                bit[len].add((sum[sz-1])%(1ll<<(len+1)),-1);
            }
            sz--;
        }
        sz++;
        stk[sz]=v;
        sum[sz]=(sum[sz-1]+v)%mod;
        for(int len=0;len<=maxL;len++){
            bit[len].add(sum[sz-1]%(1ll<<(len+1)),1);
        }
        int ans=0;
        for(int len=0;len<=maxL;len++){
            int S=sum[sz]%(1LL<<(len+1));
            int tmp=0;
            if (S<(1LL<<len)){
                tmp=bit[len].query(S+1,S+(1LL<<len));
            }
            else if(S==((1ll<<(len+1))-1)){
                tmp=bit[len].query(0,(1ll<<(len))-1);
//                    tmp=sz-1;
            }
            else {
                tmp+=bit[len].query(0,S-(1ll<<len));
                tmp+=bit[len].query(S+1,((1ll<<(len+1))-1));
            }
            if(tmp%2==1)ans|=(1ll<<len);
        }
        cout<<ans<<'\n';
    }
}
H World Finals 签到分类讨论排序
点击查看代码 
//@author: i_wish_a_girlfriend
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define rep(a,b,c) for(int a=b; a<=c; a++)
#define YES cout << "Yes\n" 
#define NO cout << "No\n" 
#define ar2 array<int,2>
int dx[] = { 0,1,-1,0,0,1,1,-1,1 };
int dy[] = { 0,0,0,1,-1,1,-1,1,1 };
//---------------------------//
#define debug_(x) cerr << #x << " = " << (x) << ' '
#define debug(x) cerr << #x << " = " << (x) << '\n'
#define debugsq(x) \
    cerr << #x << ": ["; \
    for (auto i : x) cerr << i << ' '; \
    cerr << "]\n";
#define debugmp(x) cerr << #x << ": [ "; for (auto [i, j] : x) cerr << '[' << i << "," << j << "] "; cerr << "]\n";
//---------------------------//
struct node {
    string s;
    int ac, time;
    // bool operator < (node& oth) {
    //     if (ac != oth.ac) return ac < oth.ac;
    //     else if (oth.time != time) time > oth.time;
    // }
};
bool cmp(node a,node b) {
    if(a.ac != b.ac) return a.ac < b.ac;
    else return a.time > b.time;
}
void solve() {
    int n, m, ans = 1e18;
    map<string, int> cnt;

    cin >> n;
    vector<node> arr(n + 1);
    
    for (int i = 1; i <= n; i++) {
        cin >> arr[i].s >> arr[i].ac >> arr[i].time;
        cnt[arr[i].s]++;
    }
    // debug(1);
    sort(arr.begin() + 1, arr.end(), cmp);
    // debug(1);
    cin >> m;
    vector<node> brr(m + 1);

    for (int i = 1; i <= m; i++) {
        cin >> brr[i].s >> brr[i].ac >> brr[i].time;
        cnt[brr[i].s]++;
    }
    sort(brr.begin() + 1, brr.end(), cmp);
    
    int res = 0;
    for (int i = n; i > 0; --i) {
        
        // debug(arr[i].s);
        if (arr[i].s == "lzr010506") {
            res++;
            ans = min(res, ans);
            break;
        }
        else {
            if (cnt[arr[i].s] == 2) {
                continue;
            }
            else {
                // debug(arr[i].s);
                res++;
            }
        }
    }
    // debug(ans);
    
    res = 0;
    for (int i = m; i > 0; --i) {

        if (brr[i].s == "lzr010506") {
            res++;
            ans = min(res, ans);
            break;
        }
        else {
            if (cnt[brr[i].s] == 2) {
                continue;
            }
            else {
                res++;
            }
        }
    }
    cout << ans << endl;
    // rep(i, 1, n) {
    //     string s;
    //     cin >> s >> arr[i].ac >> arr[i].time;
    //     if (s == "lzr010506") {
    //         AC = arr[i].ac;
    //         TIME = arr[i].time;
    //     }
    // }
    // sort(arr.begin() + 1, arr.end());
    // int idx = n;

    // while(arr[idx].ac > AC ||(arr[idx].ac == AC &&  arr[idx].time < TIME) ) {
    //     idx--;
    // }

    // ans = min(ans, (n - idx + 1));
    // // debug(idx);
    // debug(ans);
    // cin >> m;
    // vector<node> brr(m + 1);
    // rep(i, 1, m) {
    //     string s;
    //     cin >> s >> brr[i].ac >> brr[i].time;
    //     if (s == "lzr010506 ") {
    //         AC = arr[i].ac;
    //         TIME = arr[i].time;
    //     }
    // }
    // sort(brr.begin() + 1, brr.end());
    // idx = m;
    // for(int i = m; i > 0; --i) {
    //     if( arr[i].ac > AC || arr[i].time < TIME) continue;
    //     else {
    //         idx = i;
    //         break;
    //     }
    // }
    // ans = min(ans, (m - idx + 1));

    // cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    int _ = 1;
    // cin >> _;
    while (_--) {
        solve();
    }
}

I-Mirror Maze
我们通过观察发现对于每个图形
如果它是环那么只用计算反射次数
如果他是链那么我们通过一个预处理即可

点击查看代码 
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
// fir 0:above,1:below,2:left,3:right
int to[8000005], deg[8000005], vis[8000005], cntt[8000005], ans[8000005], q[8000005], fl[1000005];
int get_id(int x, int y, int fir) {
    return 4 * ((x - 1) * m + y) + fir;
}
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };
pair<int, int> ch[205][4];
char s[1010][1010];
void solve(){
    cin>>n>>m;
    {
        ch['|'][0]={0,0};
        ch['|'][1]={1,0};
        ch['|'][2]={3,1};
        ch['|'][3]={2,1};

        ch['-'][0]={1,1};
        ch['-'][1]={0,1};
        ch['-'][2]={2,0};
        ch['-'][3]={3,0};

        ch['/'][0]={3,1};
        ch['/'][3]={0,1};
        ch['/'][1]={2,1};
        ch['/'][2]={1,1};

        ch['\\'][0]={2,1};
        ch['\\'][2]={0,1};
        ch['\\'][1]={3,1};
        ch['\\'][3]={1,1};
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>s[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int dir=0;dir<4;dir++){
                int nx=i+dx[dir],ny=j+dy[dir];
                if(nx<1||nx>n||ny<1||ny>m)continue;
                int now=get_id(i,j,dir);
                auto [nk,w]=ch[s[nx][ny]][dir];
                cntt[now]=w;
                to[now]=get_id(nx,ny,nk);
                ++deg[to[now]];
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int dir=0;dir<4;dir++){
                if(deg[get_id(i,j,dir)])continue;
                int now=get_id(i,j,dir);
                int top=0;
                while(now){
                    q[++top]=now;
                    now=to[now];
                }
                int res=0;
                vector<int>pos;
                for(int c=top;c>=1;c--){
                    int x=q[c];
                    vis[x]=1;
                    if(cntt[x]){
                        int id=to[x]/4;
                        if(!fl[id])fl[id]=1,res++,pos.push_back(id);
                    }
                    ans[x]=res;
                }
                for(auto &x:pos)fl[x]=0;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int dir=0;dir<4;dir++){
                if(vis[get_id(i,j,dir)])continue;
                int now=get_id(i,j,dir);
                int res=0;
                vector<int>pos;
                while(!vis[now]){
                    vis[now]=1;
                    if(cntt[now]){
                        int id=to[now]/4;
                        if(!fl[id])fl[id]=1,res++,pos.push_back(id);
                    }
                    now=to[now];
                }
                for(auto x:pos){
                    fl[x]=0;
                }
                while(1){
                    ans[now]=res;
                    now=to[now];
                    if(now== get_id(i,j,dir))break;
                }
            }
        }
    }
    int que;cin>>que;
    while(que--){
        int x,y,k;
        string op;
        cin>>x>>y>>op;
        if(op[0]=='a')k=0;
        if(op[0]=='b')k=1;
        if(op[0]=='l')k=2;
        if(op[0]=='r')k=3;
        cout<<ans[get_id(x,y,k)]<<'\n';
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int _=1;
//    cin>>_;
    while(_--)solve();
}

标签：arr,ch,return,int,多校,2024,牛客,ans,define
From： https://www.cnblogs.com/archer233/p/18312276

相关文章

  • 杭电多校补题
    1001.循环位移#include<bits/stdc++.h>usingnamespacestd;typedefunsignedlonglongull;constintN=1048580*2;constintP=131;ullp[N],h1[N],h2[N];voidsolve(){stringa,b;cin>>a>>b;intn=a.size()......
  • 20240719数据库关联查询、条件查询
    mysql关联外键查询商品表和图片表是分开的，用一张商品图片表关联起来了。查询商品表所有字段和图片信息。其余的，商人id、区域id、分类id都是直接关联，没有中间表SELECTp.id,p.name,p.price,p.unit,f.file,p.description,p.is_on_sale,p.......
  • 【开源分享】2024PHP在线客服系统源码(全新UI+终身使用+安装教程)
    PHP在线客服系统核心功能用户留言协同工作：留言后，用户能够享受在线咨询、订单查询等服务；登录状态也用于权限控制，确保不同用户访问合适的资源。咨询处理作用：提供实时或异步的客服咨询功能，允许用户向客服发送问题并接收回复。重要性：是客服系统的核心功能，直接影响用户体验和满意......
  • 2024.7.19 近期练习
    CF623B考虑枚举\(\gcd=d\)，我们先假设没有\(a\)操作，所有数都需要\(b\)操作来实现。那么，形如\(kd\pm1\)的数需要代价为\(b\)，\(kd\)的数无需代价，然而可能存在没法通过\(b\)操作被\(d\)整除的数。若没有上述数呢，我们现在加入\(a\)操作，这是一个最大子段和问题，求出一......
  • 【2024】SpringBoot+Vue.js协同过滤算法美食推荐小程序
     博主介绍：✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌技术范围：SpringBoot、Vue、SSM、HTML、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大......
  • 2024年牛客暑期多校训练营1 A题 A Bit Common题解
    题目的大意：首先，给你一个长度为n的序列A，A序列中每一个元素全都小于2m，并且大于等于0。A序列要满足存在一个非空子序列的与运算(&)和为1；输出这样的A序列有几个，最后对正整数q取模。（1<=n,m<=5000,1<=q<=109)输入只有一行n,m,q，输出包含一个整数。 题解：要满......
  • 2024 电动汽车辅助驾驶系统算力天梯图 All In One
    2024电动汽车辅助驾驶系统算力天梯图AllInOne电动车算力天梯图demosTeslaModelYHW4.0(......
  • Windows 10 on ARM, version 22H2 (updated Jul 2024) ARM64 AArch64 中文版、英文版
    Windows10onARM,version22H2(updatedJul2024)ARM64AArch64中文版、英文版下载基于ARM的Windows10请访问原文链接：https://sysin.org/blog/windows-10-arm/，查看最新版。原创作品，转载请保留出处。作者主页：sysin.orgWindows10,version22H2(releasedNov2021)......
  • Windows 11 version 23H2 中文版、英文版 (x64、ARM64) 下载 (updated Jul 2024)
    Windows11version23H2中文版、英文版(x64、ARM64)下载(updatedJul2024)Windows11,version23H2，企业版arm64x64请访问原文链接：https://sysin.org/blog/windows-11/，查看最新版。原创作品，转载请保留出处。作者主页：sysin.orgWindows11目前版本所有的日期都按照I......
  • Windows 11 version 22H2 中文版、英文版 (x64、ARM64) 下载 (updated Jul 2024)
    Windows11version22H2中文版、英文版(x64、ARM64)下载(updatedJul2024)Windows11,version22H2，企业版arm64x64请访问原文链接：https://sysin.org/blog/windows-11/，查看最新版。原创作品，转载请保留出处。作者主页：sysin.orgWindows11目前版本所有的日期都按照I......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99