首页 > 其他分享 >北京一零一中2024年信息学迎新马拉松解题报告

北京一零一中2024年信息学迎新马拉松解题报告

时间：2024-07-08 18:42:03浏览次数：16  
标签：一零一 int ll 2024 MAXN ans 迎新 query id

A T469715 [2024迎新马拉松] 101

相当于选择一段长度为 \(3k\) 的区间使得变化的总值最小。维护每一个元素变化到 \(1\) 与 \(0\) 的要求数量，之后前缀和处理即可。

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
const ll MAXN=1e6+5;
ll t0[MAXN],t1[MAXN];
ll v0(ll l,ll r){
    return t0[r]-t0[l-1];
}
ll v1(ll l,ll r){
    return t1[r]-t1[l-1];
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll n,k;
    cin>>n>>k;
    for(int i=1;i<=n;++i){
        ll a;
        cin>>a;
        t0[i]+=t0[i-1]+min(10-a,a);
        t1[i]+=t1[i-1]+min(11-a,(a==0?1:a-1));
    }
    ll val=1e18;
    for(int i=1;i<=n-3*k+1;++i){
        val=min(val,v1(i,i+k-1)+v0(i+k,i+2*k-1)+v1(i+2*k,i+3*k-1));
    }
    cout<<n-3*k+val<<endl;
    return 0;
}

B T467650 [2024迎新马拉松] 排列

设 \(f_{i,j}\) 表示直到第 \(i\) 个变换时 \(x\) 要变到 \(j\) 最多的保留数量。

则有

  1. \(f_{i,j}=f_{i-1,j}+1 (j\neq a_i,j\neq b_i)\)
  2. \(f_{i,a_i}=\max(f_{i-1,a_i},f_{i-1,b_i}+1)\)
  3. \(f_{i,b_i}=\max(f_{i-1,b_i},f_{i-1,a_i}+1)\)

线段树优化动规解决。

#include <bits/stdc++.h>
#define endl "\n"
#define lc(u) u<<1
#define rc(u) u<<1|1
using namespace std;
typedef long long ll;
const ll MAXN=2e6+5;
ll n,m,x;
ll t[MAXN*4],tag[MAXN*4];
void push_down(ll u,ll l,ll r){
    ll mid=(l+r)>>1;
    t[lc(u)]+=(mid-l+1)*tag[u];
    tag[lc(u)]+=tag[u];
    t[rc(u)]+=(r-mid)*tag[u];
    tag[rc(u)]+=tag[u];
    tag[u]=0;
}
ll query(ll u,ll l,ll r,ll x){
    if(l==r){
        return t[u];
    }
    push_down(u,l,r);
    ll mid=(l+r)>>1;
    if(x<=mid){
        return query(lc(u),l,mid,x);
    }
    return query(rc(u),mid+1,r,x);
}
void change(ll u,ll l,ll r,ll x,ll val){
    if(l==r){
        t[u]=val;
        return;
    }
    push_down(u,l,r);
    ll mid=(l+r)>>1;
    if(x<=mid){
        change(lc(u),l,mid,x,val);
        return;
    }
    change(rc(u),mid+1,r,x,val);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>x;
    memset(t,~0x3f,sizeof(t));
    change(1,1,n,x,0);
    for(int i=1;i<=m;++i){
        ll a,b;
        cin>>a>>b;
        ll va=query(1,1,n,a),vb=query(1,1,n,b);
        tag[1]++;
        change(1,1,n,a,max(va,vb+1));
        change(1,1,n,b,max(vb,va+1));
    }
    for(int i=1;i<=n;++i){
        cout<<(query(1,1,n,i)<0?-1:query(1,1,n,i))<<" ";
    }
    return 0;
}

C

D T469844 [2024迎新马拉松] 质数

线性筛筛出所有 \([1,10^6]\) 内的质数然后枚举每一个点开始的子串累计即可。

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
const ll MAXN=1e7+5;
ll p[MAXN],tot;
bool np[MAXN];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    for(int i=2;i<1000000;++i){
        if(!np[i]){
            p[++tot]=i;
        }
        for(int j=1;j<=tot&&i*p[j]<1000000;++j){
            np[i*p[j]]=true;
            if(i%p[j]==0){
                break;
            }
        }
    }
    ll k;
    cin>>k;
    string s;
    cin>>s;
    s=" "+s;
    ll n=s.size()-1,ans=0;
    np[1]=true;
    for(int i=1;i<=n-k+1;++i){
        if(s[i]=='0'){
            continue;
        }
        ll val=0;
        for(int j=i;j<=i+k-1;++j){
            val=val*10+s[j]-'0';
        }
        ans+=!np[val];
    }
    cout<<ans<<endl;
    return 0;
}

E T469864 [2024迎新马拉松] 无限串

用vector维护每一个字母的所有出现位置，然后根据循环把两端的单独二分查找有几个数，中间的除一下看看能分出几段，拼合即可，但是需要高精度。

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
const ll MAXN=5e6;
const ll MOD=1e9+7;
unsigned to[55][MAXN];
ll s[MAXN];
ll query(ll x,ll l,ll r){
    return to[x][r]-to[x][l-1];
}
ll ksm(ll x,ll b){
    ll ans=1;
    while(b){
        if(b&1){
            ans=ans*x%MOD;
        }
        x=x*x%MOD;
        b>>=1;
    }
    return ans;
}
ll k[MAXN],o[MAXN];
string ms(string a,ll b){
    ll sz=0;
    for(int i=a.size()-1;i>=0;--i){
        k[++sz]=a[i]-'0';
    }
    ll i=0;
    while(b){
        ++i;
        k[i]-=b%10;
        if(k[i]<0){
            k[i]+=10;
            k[i+1]-=1;
        }
        b/=10;
    }
    string c;
    bool good=false;
    for(i=sz;i>=1;--i){
        if(good||k[i]!=0){
            good=true;
            c+=char(k[i]+'0');
        }
    }
    return c;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    string S,t;
    cin>>S>>t;
    bool isd=false;
    for(int i=0;i<t.size();++i){
        if(isdigit(t[i])){
            isd=true;
            break;
        }
    }
    ll n=S.size(),m=t.size();
    S=" "+S;
    t=" "+t;
    for(int i=1;i<=n;++i){
        if('a'<=S[i]&&S[i]<='z'){
            s[i]=S[i]-'a'+1;
        }else{
            s[i]=S[i]-'A'+27;
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=53;++j){
            to[j][i]=to[j][i-1];
        }
        to[s[i]][i]++;
    }
    ll ans=0;
    ll id=0;
    for(int i=1;i<=m;++i){
        ll c;
        if('a'<=t[i]&&t[i]<='z'){
            c=t[i]-'a'+1;
        }else{
            c=t[i]-'A'+27;
        }
        ll tot=0;
        string num;
        if(isdigit(t[i+1])){
            while(i+1<=m&&isdigit(t[i+1])){
                num+=t[i+1];
                ++i;
            }
        }
        if(num.empty()){
            num="1";
        }
        if(num.size()<=10){
            ll v=0;
            for(auto c:num){
                v=v*10+c-'0';
            }
            if(v>query(c,id+1,n)){
                v-=query(c,id+1,n);
                ans+=n-id;
                id=0;
                ans+=((v)/query(c,1,n))*n;
                v-=((v)/query(c,1,n))*query(c,1,n);
            }
            if(v==0){
                ans-=n;
                v+=query(c,1,n);
            }
            ll nid=lower_bound(to[c]+id+1,to[c]+n+1,to[c][id]+v)-to[c];
            ans+=nid-id;
            id=nid;
            if(id==n){
                id=0;
            }
        }else{
            num=ms(num,query(c,id+1,n));
            ans+=n-id;
            ans%=MOD;
            string nv=num;
            vector<ll>basic;
            ll left=0;
            for(auto ca:nv){
                left=left*10+ca-'0';
                basic.push_back(left/query(c,1,n));
                left%=query(c,1,n);
            }
            ll b=1;
            for(int j=basic.size()-1;j>=0;--j){
                ans+=basic[j]*b%MOD*n%MOD;
                b*=10;
                b%=MOD;
            }
            if(left==0){
                ans=((ans-n)%MOD+MOD)%MOD;
                left+=query(c,1,n);
            }
            id=0;
            ll nid=lower_bound(to[c]+id+1,to[c]+n+1,to[c][id]+left)-to[c];
            ans+=nid-id;
            id=nid;
            if(id==n){
                id=0;
            }
        }
    }
    cout<<unsigned(ans%MOD)<<endl;
    return 0;
}

F T467532 [2024迎新马拉松] 字典

先把所有东西离线下来处理好。

之后把字典的字符串按字典序排序，然后求出每个询问对应前缀的字符串的区间 \([l,r]\)，显然这个区间里的所有元素的前缀都是一样的。那么考虑后缀。

按顺序将每个元素倒过来加进可持久化字典树中，之后只要查询 \([l,r]\) 范围内的后缀元素数量即可。

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
const ll MAXN=1e6+5;
string s[MAXN];
map<string,ll>l,r;
set<string>sl,sr;
ll n,m;
struct query{
    string f,b;
}q[MAXN];
ll ans[MAXN];
ll trie[MAXN*4][26],tot;
ll sum[MAXN*4],rt[MAXN*4];
void insert(ll &u,string s){
    ++tot;
    for(int i='a';i<='z';++i){
        trie[tot][i-'a']=trie[u][i-'a'];
    }
    sum[tot]=sum[u]+1;
    u=tot;
    ll v=u;
    for(int i=0;i<s.size();++i){
        ll x=s[i]-'a';
        ++tot;
        ll on=trie[v][x];
        for(int j=0;j<26;++j){
            trie[tot][j]=trie[on][j];
        }
        sum[tot]=sum[on]+1;
        trie[v][x]=tot;
        v=trie[v][x];
    }
}
ll query(ll lu,ll ru,string s){
    for(int i=0;i<s.size();++i){
        ll c=s[i]-'a';
        lu=trie[lu][c];
        ru=trie[ru][c];
    }
    return sum[ru]-sum[lu];
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>s[i];
    }
    sort(s+1,s+n+1);
    for(int i=1;i<=m;++i){
        string c;
        cin>>c;
        int j=0;
        for(j=0;c[j]!='*';++j){
            q[i].f+=c[j];
        }
        j++;
        while(j<c.size()){
            q[i].b+=c[j];
            ++j;
        }
        reverse(q[i].b.begin(),q[i].b.end());
        sl.insert(q[i].f);
    }
    for(ll i=1;i<=n;++i){
        string val;
        if(sl.count(val)){
            if(!l.count(val)){
                l[val]=i;
            }
            r[val]=i;
        }
        for(int j=0;j<s[i].size();++j){
            val+=s[i][j];   
            if(sl.count(val)){
                if(!l.count(val)){
                    l[val]=i;
                }
                r[val]=i;
            }
        }
        reverse(s[i].begin(),s[i].end());
        rt[i]=rt[i-1];
        insert(rt[i],s[i]);
    }
    for(int i=1;i<=m;++i){
        cout<<query(rt[l[q[i].f]-1],rt[r[q[i].f]],q[i].b)<<endl;
    }
    return 0;
}

G T467526 [2024迎新马拉松] 回路

考虑二分中位数，对于二分的 \(x\)，将数组的元素抽象成：

  1. \(a_{i,j}=1(a_{i,j}\geq x)\)
  2. \(a_{i,j}=-1(a_{i,j}<x)\)
  3. \(a_{1,1}=0\)

然后我们要做的是在这个数组上找一条最大的回路使得这条回路的值大于 \(0\)。考虑费用流连边即可。

#include <bits/stdc++.h>
#define endl "\n"
#define int long long
using namespace std;
typedef long long ll;
const ll MAXN=300;
const ll MAXM=MAXN*MAXN;
const ll INF=1e18;
ll s, t;
struct edge {
    ll to, weight, cost, nxt;
} e[MAXN * MAXN* 20];
ll head[MAXN*MAXN*2], tot = 1;

void add(ll u, ll v, ll w, ll c) {
    e[++tot]={v,w,c,head[u]};
    head[u] = tot;
    e[++tot]={u,0,-c,head[v]};
    head[v]=tot;
}

ll cost;
ll dis[MAXN*MAXN*2];
bool inq[MAXN*MAXN*2];
struct path {
    ll edge, pre;
} p[MAXN*MAXN*2];
void clear(){
    memset(head,0,sizeof(head));
    tot=1;
    cost=0;
}
bool spfa() {
    memset(inq, false, sizeof(inq));
    for (int i = 0; i < MAXN*MAXN*2; ++i) {
        dis[i] = INF;
    }
    queue<ll> q;
    q.push(s);
    inq[s] = true;
    dis[s] = 0;
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        inq[u] = false;
        for (ll i = head[u]; i; i = e[i].nxt) {
            ll v = e[i].to, c = e[i].cost, w = e[i].weight;
            if (dis[u] + c < dis[v] && w) {
                dis[v] = dis[u] + c;
                p[v].edge = i;
                p[v].pre = u;
                if (!inq[v]) {
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return dis[t] != INF;
}

ll ek() {
    ll ans = 0;
    while (spfa()) {
        ll Min = INF;
        for (ll i = t; i != s; i = p[i].pre) {
            Min = min(Min, e[p[i].edge].weight);
        }
        ans += Min;
        for (ll i = t; i != s; i = p[i].pre) {
            e[p[i].edge].weight -= Min;
            e[p[i].edge ^ 1].weight += Min;
        }
        cost += Min * dis[t];
    }
    return ans;
}
ll n,m,a[MAXN][MAXN];
ll b[MAXN][MAXN];
ll gidi(ll x,ll y){
    return (x-1)*m+y;
}
ll gido(ll x,ll y){
    return n*m+gidi(x,y);
}
bool check(ll x){
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(a[i][j]>=x){
                b[i][j]=1;
            }else{
                b[i][j]=-1;
            }
        }
    }
    b[1][1]=0;
    clear();
    s=0,t=MAXN*MAXN-2000;
    add(s,gidi(1,1),2,0);
    add(gido(n,m),t,2,0);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            ll in=gidi(i,j),out=gido(i,j);
            if((i==1&&j==1)||(i==n&&j==m)){
                add(in,out,2,-b[i][j]);
            }else{
                add(in,out,1,-b[i][j]);
            }
            if(j<m){
                add(gido(i,j),gidi(i,j+1),1,0);
            }
            if(i<n){
                add(gido(i,j),gidi(i+1,j),1,0);
            }
        }
    }
    ll val=ek();
    ll ans=cost+b[n][m];
    //cout<<x<<" "<<val<<" "<<ans<<endl;
    return ans<=0;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            cin>>a[i][j];
        }
    }
    ll ans=0,l=1,r=1e9;
    while(l<=r){
        ll mid=(l+r)>>1;
        if(check(mid)){
            l=mid+1;
            ans=mid;
        }else{
            ans=mid-1;
            r=mid-1;
        }
    }
    cout<<ans<<endl;
    return 0;
}

H

标签：一零一,int,ll,2024,MAXN,ans,迎新,query,id
From： https://www.cnblogs.com/tanghg/p/18290530/2024yinxin

相关文章

  • Altair携手奇瑞汽车，荣获2024世界人工智能大会“AI赋能新型工业化创新应用优秀案例”
    2024年7月4-7日，2024世界人工智能大会（WAIC）在上海世博中心成功举办。4日下午，“AI赋工业，数智启未来—人工智能赋能新型工业化主题论坛”在上海世博中心召开。Altair携手奇瑞汽车股份有限公司申报的“基于AI的降阶建模实现新能源汽车高低温续航高效集成仿真”案例在本次大会中......
  • 跟《经济学人》学英文：2024年07月06日这期：How Starbucks caffeinates local economies
    HowStarbuckscaffeinateslocaleconomiesCallitthefrappuccinoeffectfrappuccino：星冰乐星巴克如何刺激当地经济：称之为星冰乐效应原文：Starbucksoffersendlessopportunitiesforinnovation.Partsofsocialmediadelightinhackingthechain’smenuto......
  • 2024全球数字经济大会：大模型时代下DataOps驱动企业数智化升级
    7月5日，以“开源生态筑基础，数字经济铸未来”为主题的2024全球数字经济大会在北京成功举办，来自全国各地的专家学者、企业代表、数据库行业从业人士及众多开源开发者，共聚一堂，共同探讨开源数据库技术的发展现状与未来趋势，助力构建开放、共赢的数据库生态体系，为开源生态的繁荣发展添砖......
  • P10359 [PA2024] Kolorowy las
    MyBlogsP10359[PA2024]Kolorowylas/tuu。写了三天。首先考虑树的形态不变怎么做，直接的想法是树分治这种东西可以做到一只或者两只\(\log\)。但是点分这种东西不太好扩展到动态树的问题。但是因为这是单点查询，所以可以不用真正的树上染色，只需要回答每个询问即可。考虑对于......
  • 2024春秋杯 stdout
    考点：文件，setvbuf缓冲区，ret2syscall，ret2csu题目给了libc文件。main函数和vlun函数存在明显的栈溢出int__cdeclmain(intargc,constchar**argv,constchar**envp){charbuf[80];//[rsp+0h][rbp-50h]BYREFinit(argc,argv,envp);puts("whereismystdout?......
  • SMU Summer 2024 Contest Round 1（7.8）
    A_DiceandCoin题目链接：abc126_c思路：分别求所有掷到的筛子数时赢得可能，进行求和voidsolve(){intn,k;cin>>n>>k;doubleans=0;for(inti=1;i<=n;++i){doublenow=1.0/n;if(i>=k)ans+=now;else{......
  • 2024最火的AI绘画软件——Stable Diffusion整合包安装教程，奶奶看了都会！
    2024年绘画圈最火的软件，那妥妥的就StableDiffutionV4升级版无需安装，直接解压就能用（在此要感谢秋葉aaaki大佬的分享！）比之前版本的更加智能、高效和易操作。V4加强版小白也能轻易上手！「无套路！添加下方即可领取」1.软件背景信息▍StableDiffusion是什么？StableDif......
  • SMU Summer 2024 Contest Round 1
    SMUSummer2024ContestRound1DiceandCoin题意给个n面骰子和一枚硬币，初始投骰子，若骰子的值在1到\(K-1\)之间则反复投硬币，硬币为正则该值翻倍，否则为0，当值为0输掉游戏或者大于等于\(K\)时赢得游戏结束，问你可以赢得游戏的概率为多少。思路以1到n为初始值......
  • 2024华为与IPD融合的质量研发体系设计，附设计案例
    （一）与IPD融合的治理研发体系设计大纲1.0IPD基础1.1IPD主业务流框架IPD（IntegratedProductDevelopment）是一种集成产品开发的方法，旨在通过跨部门协作和资源整合，提高产品开发效率和质量。其主业务流框架包括需求管理、产品规划、技术开发、产品验证和市场发布等关键环节.1.2......
  • 2024年文化研究与数字媒体国际会议 (CRDM 2024)
    2024年文化研究与数字媒体国际会议(CRDM2024)2024InternationalConferenceonCulturalResearchandDigitalMedia【重要信息】大会地点：珠海大会官网：http://www.iccrdm.com投稿邮箱：[email protected]【注意：稿将稿件Word+PDF上传至邮箱，邮件正文请备注“CRDM 2024......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99