20181015队内ACM赛 Part.2

T4题意

求一个数在二进制意义下1的个数

Solution


Code

#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define digit 4
#define maxn 70
#define base 10000
#define reg register
#define ll long long
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
#define swap(a,b) ((a)==(b)?(a)=(b):((a)^=(b)^=(a)^=(b)))
using namespace std;
template<typename T> inline void read(T&x){T f=1;x=0;char c;
    for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
    for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
    int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
int d,q,n,k,Ans,K;
char s[maxn*digit];
struct Bignum2{
    int v[maxn*20],len;
    Bignum2(){memset(v,0,sizeof(v)),len=1;}
    inline void init(){v[0]=1;}
    inline void read(){
        scanf("%s",s);int t=strlen(s),tim=1;
        len=(t-1)/digit+1,memset(v,0,sizeof(v));
        for (int i=0,j=t-1;i<j;i++,j--) swap(s[i],s[j]);
        for (int i=0;i<t;i++){
            v[i/digit]+=(s[i]-'0')*tim,tim*=10;
            if (tim==base) tim=1;
        }
    }
    inline void write(){
        printf("%d",v[len-1]);
        for (int i=len-2;~i;i--) printf("%0*d",digit,v[i]);
        putchar('\n');
    }
}Two,ans;
inline Bignum2 operator *(const Bignum2&x,const Bignum2&y){
    Bignum2 z;z.len=x.len+y.len;
    for (int i=0;i<=x.len;i++) for (int j=0;j<=y.len;j++)
        z.v[i+j]+=x.v[i]*y.v[j],z.v[i+j+1]+=z.v[i+j]/base,z.v[i+j]%=base;
    while (!z.v[z.len]&&z.len>1) z.len--;
    while (z.v[z.len]) z.v[z.len+1]+=z.v[z.len]/base,z.v[z.len]%=base,z.len++;
    return z;
}
inline bool operator <(const Bignum2&x,const Bignum2&y){
    if (x.len!=y.len) return x.len<y.len;
    for (int i=x.len;~i;i--) if (x.v[i]!=y.v[i]) return x.v[i]<y.v[i];
    return 0;
}
inline bool operator ==(const Bignum2&x,const Bignum2&y){
    if (x.len!=y.len) return 0;
    for (int i=0;i<=x.len;i++) if (x.v[i]!=y.v[i]) return 0;
    return 1;
}
inline bool operator <=(const Bignum2&x,const Bignum2&y){return x<y||x==y;}
struct Bignum{
    int v[maxn],len;
    Bignum(){memset(v,0,sizeof(v)),len=1;}
    inline void init(){v[0]=1;}
    inline void read(){
        scanf("%s",s);
        int t=strlen(s),tim=1;
        len=(t-1)/digit+1,memset(v,0,sizeof(v));
        for (int i=0,j=t-1;i<j;i++,j--) swap(s[i],s[j]);
        for (int i=0;i<t;i++){
            v[i/digit]+=(s[i]-'0')*tim,tim*=10;
            if (tim==base) tim=1;
        }
    }
    inline void write(){
        printf("%d",v[len-1]);
        for (int i=len-2;~i;i--) printf("%0*d",digit,v[i]);
        putchar('\n');
    }
}f[2][256][110],res,Zero;
inline Bignum operator +(const Bignum&x,const Bignum&y){
    Bignum z;
    z.len=max(x.len,y.len);
    for (int i=0;i<=z.len;i++) z.v[i]+=x.v[i]+y.v[i],z.v[i+1]+=z.v[i]/base,z.v[i]%=base;
    while (z.v[z.len]) z.v[z.len+1]+=z.v[z.len]/base,z.v[z.len]%=base,z.len++;
    return z;
}
inline Bignum2 mlt(Bignum2 a,int b){
    Bignum2 res; res.init();
    for (;b;b>>=1,a=a*a) if (b&1) res=res*a;
    return res;
}
inline int _log(Bignum2 a){
    int l=0,r=8010;
    while (l<=r){
        int mid=(l+r)>>1;
        Bignum2 x=mlt(Two,mid),y=mlt(Two,mid+1);
        if (x<=a&&a<=y) return mid;
        if (y<a) l=mid+1;else r=mid-1;
    }
    return 0;
}
int main(){
    Two.v[0]=2;read(d),read(q),read(n),read(k);
    for(int i=0;i<d;i++)f[1][i][0].v[0]=f[1][i][1].v[0]=1;
    for(int i=2;i<=n;i++){
        for(int j=0;j<d;j++) for(int k=0;k<d;k++)
            if(j!=k)f[i&1][j][1]=f[i&1][j][1]+f[(i-1)&1][k][0],f[i&1][j][0]=f[i&1][j][0]+f[(i-1)&1][k][0];
        for(int j=0;j<d;j++) for(int k=2;k<K;k++)
            f[i&1][j][k]=f[(i-1)&1][j][k-1],f[i&1][j][0]=f[i&1][j][0]+f[i&1][j][k];
        for (int j=0;j<d;j++) for (int k=0;k<K;k++) f[(i-1)&1][j][k]=Zero;
    }
    for(int i=0;i<d;i++)for(int j=1;j<K;j++)res=res+f[n&1][i][j];
    memcpy(ans.v,res.v,sizeof(res.v));ans.len=res.len;
    ans=mlt(ans,q);Ans=_log(ans);wt(Ans,'\n');return 0;
}

T5题意


求两字符串的最长公共子序列的长度、本质不同的非空公共子序列的个数、各种长度的本质不同的非空公共子序列的个数。


Solution


首先考虑第二问,设dp(i,j)表示s串的前i位和t串的前j位,分两种情况讨论
若s[i]=s[j],则直接把这个字符接在后面,有接和不接两种则dp(i,j)=dp(i-1,j-1)∗2,但是我们需要将此结果减去dp(u-1,v-1)其中uv是ij最近相同字符, 考虑dp[u-1][v-1]对应集合中的串x,记S[i]=c,则x,xc∈dp[u][v],则x,xc∈dp[i-1][j-1]。串xc就会在dp[i][j]的集合中出现两遍。
若是s[i]!=s[j],则dp(i,j)=dp(i,j-1)+dp(i-1,j)-dp(i-1,j-1)
这样就解决了第二问,而第三问就是在第二问上加一维,k为长度,dp方程则是一模一样。


Code
#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define MOD 1048576
#define reg register
#define ll long long
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
#define swap(a,b) ((a)==(b)?(a)=(b):((a)^=(b)^=(a)^=(b)))
using namespace std;
template<typename T> inline void read(T&x){T f=1;x=0;char c;
    for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
    for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
    int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
string a,b;
int f[305][305],g[305][305][305],prea[305],preb[305],ans,SIE=0xFFFFF,n,m,ss;
int main() {
    cin>>a,n=a.size(),a='0'+a;
    cin>>b,m=b.size(),b='0'+b;
    for(int i=1; i<=n; i++)  {
        for(int j=1; j<=m; j++) {
            if(a[i]==b[j])f[i][j]=f[i-1][j-1]+1;
            f[i][j]=max(f[i][j],f[i-1][j]);
            f[i][j]=max(f[i][j],f[i][j-1]);
        }
    }
    wt(f[n][m],'\n');
    ss=f[n][m];
    for(int i=1; i<=n; i++) {
        int j=i-1;
        while(j>0 && a[j]!=a[i])j--;
        prea[i]=j;
    }
    for(int i=1; i<=m; i++) {
        int j=i-1;
        while(j>0 && b[j]!=b[i])j--;
        preb[i]=j;
    }
    for(int i=0; i<=n; i++)for(int j=0; j<=m; j++) g[i][j][0]=1;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(a[i]==b[j]) {
                for(int k=1; k<=ss; k++)
                    g[i][j][k]=(g[i-1][j-1][k]+g[i-1][j-1][k-1])&SIE;
                if(prea[i] && preb[j]) for(int k=1; k<=ss; k++)
                    g[i][j][k]=(g[i][j][k]-g[prea[i]-1][preb[j]-1][k-1])&SIE;
            } else for(int k=1; k<=ss; k++)
                g[i][j][k]=(g[i-1][j][k]+g[i][j-1][k]-g[i-1][j-1][k])&SIE;
    int sum=0;
    for(int i=1; i<=ss; i++)sum=(sum+g[n][m][i])%MOD;
    wt(sum,'\n');
    for(int i=1; i<=ss; i++)wt(g[n][m][i],'\n');
    return 0;
}

T6题意


定义特征三元组(sum0,sum1,sum2),sump表示子序列中的Ai=p的个数,且满足不存在Pi≥2∗Pj.
给你一个长度为N的序列,求这个序列中特征三元组的个数。


Solution


以y为下标建权值线段树,叶子节点的值是y能匹配到的最大的z。
可以发现z是严格不上升的。
每扫到一个z就找到大于z的第一个数的位置,设其为tmp,并且把y到n提成一个平面。
贡献为(n-y)∗tmp-querysum(y,n)


Code
#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define maxn 200100
#define reg register
#define ll long long
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
#define swap(a,b) ((a)==(b)?(a)=(b):((a)^=(b)^=(a)^=(b)))
using namespace std;
template<typename T> inline void read(T&x){T f=1;x=0;char c;
    for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
    for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
    int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
ll tmp,Ans;
int n,ans,sum[3],st[maxn];
struct node {int a,p;} q[maxn];
inline bool cmp1(node x,node y) {return x.p<=y.p;}
struct Triad {int x,y,z;} p[maxn];
inline bool cmp2(Triad a,Triad b) {return a.x!=b.x?a.x>b.x:a.y!=b.y?a.y>b.y:a.z>b.z;}
struct Segment_Tree {
    ll tree[maxn*4+8];int mx[maxn*4+8],lazy[maxn*4+8];
    inline void mark(int p,int l,int r,int x) {mx[p]=x,lazy[p]=x,tree[p]=1ll*(r-l+1)*x;}
    inline void pushdown(int p,int l,int mid,int r) {
        if (lazy[p]) {
            mark(p<<1,l,mid,lazy[p]);
            mark(p<<1|1,mid+1,r,lazy[p]);
            lazy[p]=0;
        }
    }
    inline void insert(int p,int l,int r,int L,int R,int x) {
        if (L<=l&&r<=R) return mark(p,l,r,x),void();
        int mid=(l+r)>>1;pushdown(p,l,mid,r);
        if (L<=mid)insert(p<<1,l,mid,L,R,x);
        if (R>mid) insert(p<<1|1,mid+1,r,L,R,x);
        mx[p]=max(mx[p],x);
        tree[p]=tree[p<<1]+tree[p<<1|1];
    }
    inline void query(int p,int l,int r,int R,int x) {
        if (r<=R&&mx[p]<x) return tmp+=tree[p],void();
        if (l==r) return ans=l,void();
        int mid=(l+r)>>1;pushdown(p,l,mid,r);
        if (R>mid) query(p<<1|1,mid+1,r,R,x);
        if (ans) return;query(p<<1,l,mid,R,x);
    }
} S;
int main() {
    read(n);
    for (int i=1; i<=n; i++) read(q[i].a),read(q[i].p);
    sort(q+1,q+n+1,cmp1);
    int head=1,tail=0;
    for (int i=1; i<=n; i++) {
        st[++tail]=i;sum[q[i].a]++;
        while(head<tail&&q[st[head]].p*2<=q[st[tail]].p) sum[q[st[head++]].a]--;
        p[i].x=sum[0]+1,p[i].y=sum[1]+1,p[i].z=sum[2]+1;
    }
    sort(p+1,p+n+1,cmp2);
    for (int i=1; i<=n; i++) {
        ans=tmp=0;
        S.query(1,1,n,p[i].y,p[i].z);
        Ans+=1ll*p[i].x*(1ll*(p[i].y-ans)*p[i].z-tmp);
        S.insert(1,1,n,ans+1,p[i].y,p[i].z);
    }
    wt(Ans,'\n');
    return 0;
}

点我回到主页

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s