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