头像

Aaron_wch

NKOJ




离线:52分钟前


最近来访(262)
用户头像
梦若浮生
用户头像
浩海无边
用户头像
StarLi9ht
用户头像
yxc
用户头像
chtld
用户头像
XChara
用户头像
爱算法爱生活
用户头像
故渊.
用户头像
小胖妈
用户头像
zpqzpq
用户头像
sweet_tea
用户头像
辣鸡号航母
用户头像
爱大米
用户头像
AcWing2AK
用户头像
Lucas〆
用户头像
李.嘉图
用户头像
学C的萌新
用户头像
acwing_陨石
用户头像
一切皆有解
用户头像
zeng9999jian

活动打卡代码 AcWing 1312. 序列统计

#include <iostream>
#include <cstdio>
using namespace std;
const int P=1e6+3;
int infact[P],fact[P],inf[P];
int C(int n,int m){
    return 1ll*fact[n]*infact[m]%P*infact[n-m]%P;
}
int lucas(int n,int m){
    if(n<0||m<0||n<m)return 0;
    if(n<P&&m<P)return C(n,m);
    return 1ll*lucas(n%P,m%P)*lucas(n/P,m/P)%P;
}
int main(){
    for(int i=0;i<2;i++)
        infact[i]=fact[i]=inf[i]=1;
    for(int i=2;i<P;i++){
        inf[i]=1ll*inf[P%i]*(P-P/i)%P;
        infact[i]=1ll*infact[i-1]*inf[i]%P;
        fact[i]=1ll*fact[i-1]*i%P;
    }
    int test;
    scanf("%d",&test);
    for(;test--;){
        int n,l,r;
        scanf("%d%d%d",&n,&l,&r);
        int m=r-l+1;
        printf("%d\n",(lucas(n+m,n)+P-1)%P);
    }
    return 0;
}


活动打卡代码 AcWing 1285. 单词

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=210,M=1e6+10;
int tr[M][26],f[M];
int id[N],idx;
char str[M];
void insert(int x){
    int p=0,k,n=strlen(str);
    for(int i=0;i<n;i++){
        k=str[i]-'a';
        f[p]++;
        if(!tr[p][k])tr[p][k]=++idx;
        p=tr[p][k];
    }
    f[p]++;
    id[x]=p;
}
int u[M],hh,tt;
int nt[M];
void build(){
    hh=0,tt=-1;
    for(int i=0;i<26;i++)
        if(tr[0][i])
            u[++tt]=tr[0][i];
    int t;
    for(;hh<=tt;){
        t=u[hh++];
        for(int i=0;i<26;i++){
            int &p=tr[t][i];
            if(!p)p=tr[nt[t]][i];
            else{
                nt[p]=tr[nt[t]][i];
                u[++tt]=p;
            }
        }
    }
}
int n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",str);
        insert(i);
    }
    build();
    for(int i=tt;i>=0;i--)
        f[nt[u[i]]]+=f[u[i]];
    for(int i=1;i<=n;i++)
        printf("%d\n",f[id[i]]);
    return 0;
}


活动打卡代码 AcWing 1053. 修复DNA

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1010;
int tr[N][4],idx;
bool dag[N];
int get(char a){
    if(a=='A')return 0;
    if(a=='G')return 1;
    if(a=='T')return 2;
    return 3;
}
char str[N];
void insert(){
    int n=strlen(str),u=0,j;
    for(int i=0;i<n;i++){
        j=get(str[i]);
        if(!tr[u][j])tr[u][j]=++idx;
        u=tr[u][j];
    }
    dag[u]=true;
}
struct queue{
    int c[N],l,r;
    void clear(){l=0,r=-1;}
    void push(int x){c[++r]=x;}
    void pop(){l++;}
    int front(){return c[l];}
    bool empty(){return l>r;}
}u;
int nt[N];
void build(){
    u.clear();
    for(int i=0;i<4;i++)
        if(tr[0][i])
            u.push(tr[0][i]);
    int t,p;
    for(;!u.empty();){
        t=u.front(),u.pop();
        for(int i=0;i<4;i++){
            p=tr[t][i];
            if(!p)tr[t][i]=tr[nt[t]][i];
            else{
                u.push(p);
                nt[p]=tr[nt[t]][i];
                dag[p]|=dag[nt[p]];
            }
        }
    }
}
int f[N][N];
int main(){
    int n,cnt=0;
    for(;scanf("%d",&n)==1&&n;){
        memset(tr,0,sizeof tr);
        memset(dag,0,sizeof dag);
        memset(nt,0,sizeof nt);
        idx=0;
        for(;n--;){
            scanf("%s",str);
            insert();
        }
        build();
        scanf("%s",str+1);
        int m=strlen(str+1);
        memset(f,0x3f,sizeof f);
        f[0][0]=0;
        for(int i=0;i<m;i++)
            for(int j=0;j<=idx;j++)
                for(int k=0;k<4;k++){
                    int t=k!=get(str[i+1]);
                    int u=tr[j][k];
                    if(!dag[u])
                        f[i+1][u]=min(f[i+1][u],f[i][j]+t);
                }
        int res=2e9;
        for(int i=0;i<=idx;i++)
            res=min(res,f[m][i]);
        if(res>1000)res=-1;
        printf("Case %d: %d\n",++cnt,res);

    }
    return 0;
}


活动打卡代码 AcWing 1282. 搜索关键词

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e4+10,S=55,M=1e6+10,K=26;
int tr[N*S][K],cnt[N*S],idx;
int nt[N*S];
char str[M];
void insert(){
    int n=strlen(str),u=0,k;
    for(int i=0;i<n;i++){
        k=str[i]-'a';
        if(!tr[u][k])tr[u][k]=++idx;
        u=tr[u][k];
    }
    cnt[u]++;
}
struct queue{
    int l,r,c[N*S];
    void clear(){l=0,r=-1;}
    void push(int x){c[++r]=x;}
    void pop(){l++;}
    int front(){return c[l];}
    bool empty(){return l>r;}
}u;
void build(){
    u.clear();
    for(int i=0;i<K;i++)
        if(tr[0][i])
            u.push(tr[0][i]);
    for(;!u.empty();){
        int t=u.front();
        u.pop();
        for(int i=0;i<26;i++){
            int c=tr[t][i];
            if(!c)continue;
            int j=nt[t];
            for(;j&&!tr[j][i];)j=nt[j];
            if(tr[j][i])j=tr[j][i];
            nt[c]=j;
            u.push(c);
        }
    }
}
int n;
int main(){
    int test;
    scanf("%d",&test);
    for(;test--;){
        memset(cnt,0,sizeof cnt);
        memset(tr,0,sizeof tr);
        memset(nt,0,sizeof nt);
        idx=0;
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%s",str);
            insert();
        }
        build();
        scanf("%s",str);
        int len=strlen(str),id=0,c;
        int ans=0;
        for(int i=0;i<len;i++){
            c=str[i]-'a';
            for(;id&&!tr[id][c];)id=nt[id];
            if(tr[id][c])id=tr[id][c];
            for(int p=id;p;p=nt[p]){
                ans+=cnt[p];
                cnt[p]=0;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}


活动打卡代码 AcWing 426. 开心的金明

;




Description:

给定一个正整数数列 a1,a2,…,an,每一个数都在 0∼p−1 之间。

可以对这列数进行两种操作:

添加操作:向序列后添加一个数,序列长度变成 n+1;
询问操作:询问这个序列中最后 L 个数中最大的数是多少。
程序运行的最开始,整数序列为空。

一共要对整数序列进行 m 次操作。

写一个程序,读入操作的序列,并输出询问操作的答案。

Solution:

大部分大佬用的是线段树(我第一次也用的线段树)
现在发现用st超级容易
每次插入只需要修改与最后一个点有关的值即可
典型的空间换时间;
线段树空间复杂度O(4N),查询插入都是O(NlogN),不过时间里面还有许多浪费的成分
st空间复杂度O(NlogN),查询O(1),插入O(NlogN),比线段树快至少一半


代码如下

Code:

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=2e5+10,M=log2(N)+10;
int f[N][M];
int query(int l,int r){
    int k=log2(r-l+1);
    return max(f[l][k],f[r-(1<<k)+1][k]);
}
int n;
int insert(int a){
    f[++n][0]=a;
    for(int i=1;1<<i<=n;i++)
        f[n-(1<<i)+1][i]=max(f[n-(1<<i)+1][i-1],f[n-(1<<i-1)+1][i-1]);
}
int q,p,a;
char op[2];
int x;
int main(){
    scanf("%d%d",&q,&p);
    for(;q--;){
        scanf("%s%d",op,&x);
        if(op[0]=='A')
            insert((ll(x)+a)%p);
        else{
            printf("%d\n",a=query(n-x+1,n));
        }
    }
    return 0;
}



Description:

依次读入一个整数序列,每当已经读入的整数个数为奇数时,输出已读入的整数构成的序列的中位数。

Solution:

大部分大佬用的是对顶堆,好写且好想。
可是这道题完全可以当成平衡树(Treap)的模板题来做啊(逃
时间复杂度O(TNlogN)


代码如下

Code:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e5+10,INF=1e9;
struct BST{
    int l,r;
    int key,val;
    int cnt,size;
}base[N],tr[N];
int idx,root;
int get_tr(int key){
    tr[++idx]={0,0,key,rand(),1,1};
    return idx;
}
void pushup(int &p){
    tr[p].size=tr[p].cnt+tr[tr[p].l].size+tr[tr[p].r].size;
}
void zig(int &p){
    int q=tr[p].l;
    tr[p].l=tr[q].r,tr[q].r=p,p=q;
    pushup(tr[p].r),pushup(p);
}
void zay(int &p){
    int q=tr[p].r;
    tr[p].r=tr[q].l,tr[q].l=p,p=q;
    pushup(tr[p].l),pushup(p);
}
void insert(int &p,int key){
    if(!p)p=get_tr(key);
    else if(tr[p].key==key){
        tr[p].cnt++;
    }
    else if(tr[p].key>key){
        insert(tr[p].l,key);
        if(tr[tr[p].l].val>tr[p].val)zig(p);
    }
    else{
        insert(tr[p].r,key);
        if(tr[tr[p].r].val>tr[p].val)zay(p);
    }
    pushup(p);
}
int get_key_by_rank(int p,int rank){
    if(tr[tr[p].l].size>=rank)return get_key_by_rank(tr[p].l,rank);
    if(tr[p].cnt+tr[tr[p].l].size>=rank)return tr[p].key;
    return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);
}
void clear(){
    memcpy(tr,base,sizeof base);
    idx=0;
    get_tr(INF),get_tr(-INF);
    tr[root=1].l=2;
    pushup(root);
}
int main(){
    int test;
    scanf("%d",&test);
    for(;test--;){
        int n,m,a;
        scanf("%d%d",&m,&n);
        printf("%d %d\n",m,(n+1)>>1);
        clear();
        int sum=1;
        scanf("%d",&a);
        insert(root,a);
        printf("%d ",a);
        for(int i=3;i<=n;i+=2){
            scanf("%d",&a),insert(root,a);
            scanf("%d",&a),insert(root,a);
            printf("%d ",get_key_by_rank(root,(i>>1)+2));
            sum++;
            if(sum==10)puts(""),sum=0;
        }
        if(sum)puts("");
    }
    return 0;
}


活动打卡代码 AcWing 1088. 旅行问题

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=2e6+10;
struct deque{
    int l,r,c[N];
    int front(){return c[l];}
    int back(){return c[r];}
    void clear(){l=0,r=-1;}
    void push_back(int x){c[++r]=x;}
    void pop_back(){r--;}
    void pop_front(){l++;}
    bool empty(){return l>r;}
}u;
bool ans[N];
int n;
int o[N],d[N];
ll s[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",o+i,d+i);

    for(int i=1;i<=n;i++)
        s[i]=s[i+n]=o[i]-d[i];

    for(int i=1;i<=n<<1;i++)
        s[i]+=s[i-1];

    u.clear();
    for(int i=n<<1;i>=0;i--){
        if(!u.empty()&&u.front()>i+n)
            u.pop_front();
        for(;!u.empty()&&s[u.back()]>=s[i];)
            u.pop_back();
        u.push_back(i);
        if(i<n){
            if(s[u.front()]>=s[i])
                ans[i+1]=true;
        }
    }
    d[0]=d[n];
    for(int i=1;i<=n;i++)
        s[i]=s[i+n]=o[i]-d[i-1];

    for(int i=n<<1;i;i--)
        s[i]+=s[i+1];

    u.clear();
    for(int i=1;i<=n<<1;i++){
        if(!u.empty()&&u.front()<i-n)
            u.pop_front();
        for(;!u.empty()&&s[u.back()]>=s[i];)
            u.pop_back();
        u.push_back(i);
        if(i>n){
            if(s[u.front()]>=s[i])
                ans[i-n-1]=true;
        }
    }
    for(int i=1;i<=n-1;i++)
        puts(ans[i]?"TAK":"NIE");
    puts(ans[n]||ans[0]?"TAK":"NIE");
    return 0;
}



#include <iostream>
#include <cstdio>
using namespace std;
const int N=1010;
int f[N][N],v[N],w[N];
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d%d",v+i,w+i);
    for(int i=n;i>=1;i--){
        for(int j=0;j<=m;j++){
            f[i][j]=f[i+1][j];
            if(j>=v[i])
                f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]);
        }
    }
    int tot=m;
    for(int i=1;i<=n;i++){
        if(i==n&&tot>=v[i]){
            printf("%d ",i);
            break;
        }
        if(tot>=v[i]&&f[i+1][tot-v[i]]+w[i]==f[i][tot]){
            tot-=v[i];
            printf("%d ",i);
            if(!tot)break;
        }
    }
    puts("");
    return 0;
}


活动打卡代码 AcWing 202. 最幸运的数字

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int gcd(int a,int b){
    if(!b)return a;
    return gcd(b,a%b);
}
int phi(int n){
    int ans=n;
    for(int i=2;i<=n/i;i++)
        if(n%i==0){
            ans-=ans/i;
            for(;n%i==0;){
                n/=i;
            }
        }
    if(n>1)ans-=ans/n;
    return ans;
}
int Kpro(int a,int b,int p){
    int res=0;
    a%=p;
    for(;b;){
        if(b&1){
            res+=a;
            if(res>=p)res-=p;
        }
        a+=a,b>>=1;
        if(a>=p)a-=p;
    }
    return res;
}
int KSM(int a,int b,int p){
    int res=1;
    for(;b;){
        if(b&1)res=Kpro(res,a,p);
        b>>=1,a=Kpro(a,a,p);
    }
    return res;
}
int n;
signed main(){
    int cnt=0;
    for(;scanf("%lld",&n)==1&&n;){
        int t=9*n/gcd(n,8);
        if(gcd(t,10)!=1){
            printf("Case %lld: 0\n",++cnt);
            continue;
        }
        int d=phi(t),ans=d;
        for(int i=1;i<=d/i;i++){
            if(d%i==0){
                if(KSM(10,i,t)==1){
                    ans=min(ans,i);
                }
                if(KSM(10,d/i,t)==1){
                    ans=min(ans,d/i);
                }
            }
        }
        printf("Case %lld: %lld\n",++cnt,ans);
    }
    return 0;
}