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; }