【自家测试】2017-12-16　FJOI2016 d1-白红宇

【自家测试】2017-12-16　FJOI2016 d1

阅读量：5088 次

发布时间：2019-06-13

本文共 7399 字，大约阅读时间需要 24 分钟。

1. 所有公共子序列问题
(allcs.pas/c/cpp)
★问题描述:
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序
列X= x 1 x 2 ... x m ,则另一序列Z= z 1 z 2 ... z k 是X的子序列是指存在一个严格递增下标序列
i 1 , i 2 ,..., i k 使得对于所有j=1,2,...,k有 z j  x ij 。例如,序列Z=GACT是序列X= GCTACT的子
序列,相应的递增下标序列为1,4,5,6。给定2个序列X和Y,当另一序列Z既是X的子序列又是
Y的子序列时,称Z是序列X和Y的公共子序列。例如,若X= GCTACT,Y= GATCCT,序列
TT是X和Y的一个公共子序列,序列GACT也是X和Y的一个公共子序列。注意对于任何给定
的序列X和Y,空序列总是它们的一个公共子序列。
所有公共子序列问题是要求对于给定的2个序列X= x 1 x 2 ... x m 和Y= y 1 y 2 ... y n ,找出X
和Y的所有不同的公共子序列。
★编程任务:
对于给定的2个序列X= x 1 x 2 ... x m 和Y= y 1 y 2 ... y n ,根据输入数据的要求,找出它们所
有不同的公共子序列,或计算出它们有多少个不同的公共子序列。
★数据输入:
输入文件名为allcs.in。
文件的第一行有2个正整数m和n, (1<=m,n<=3010),分别表示2个输入序列X和Y的长度。
接下来的2行分别给出输入序列X= x 1 x 2 ... x m 和Y= y 1 y 2 ... y n 。其中序列中每个元素均为26
个英文大小写字母。文件的最后一行给出一个非负整数k。k的值为1时,表示计算结果要输
出X和Y的所有不同的公共子序列,以及X和Y有多少个不同的公共子序列。k的值为0时,表
示计算结果只要输出X和Y有多少个不同的公共子序列。
★结果输出:
输出文件名为allcs.out。
将计算出的X和Y的所有不同的公共子序列,或X和Y有多少个不同的公共子序列输出到
文件中。当k=1时,先输出X和Y的所有不同的公共子序列,每行输出1个公共子序列,按字
典序从小到大输出。最后输出不同的公共子序列的个数。当k=0时,只要输出不同的公共子
序列的个数。

输入示例1
6 6
GCTACT
GATCCT
1

输出示例1
26
A
AC
ACT
AT
C
CC
CCT
CT
G
GA
GAC
GACT
GAT
GC
GCC
GCCT
GCT
GT
GTC
GTCT
GTT
T
TC
TCT
TT
26

输入示例2
6 6
GCTACT
GATCCT
0

输出示例2
26

根连向每个字母第一次出现的位置，每个位置的儿子分别连向它之后每个字母第一次出现的位置．这貌似就是传说中的序列自动机．

在两个序列自动机同时dfs．需要输出序列则直接dfs并输出即可．

不需要输出序列时，记忆化搜索．但是由于答案很大，需要高精．

std又WA又T又RE，我也没有什么办法．

70分代码．

1 //Achen  2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
             7 #include
           
             8 #include
            
              9 #include
             
               10 #include
              
                11 #define For(i,a,b) for(int i=(a);i<=(b);i++) 12 #define Rep(i,a,b) for(int i=(a);i>=(b);i--) 13 const int N=3017; 14 typedef long long LL; 15 typedef double db; 16 using namespace std; 17 char a[N],b[N],prt[N]; 18 int n,m,K,ch1[N][52],ch2[N][52],ls[52]; 19 20 template
               
                 void read(T &x) { 21 char ch=getchar(); x=0; T f=1; 22 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); 23 if(ch=='-') f=-1,ch=getchar(); 24 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f; 25 } 26 27 void make_it(char s[],int n,int ch[][52]) { 28 memset(ls,0,sizeof(ls)); 29 For(i,1,n) { 30 int c=(s[i]>='a'&&s[i]<='z')?s[i]-'a':26+s[i]-'A'; 31 if(!ls[c]) ch[0][c]=i; 32 ls[c]=i; 33 } 34 memset(ls,0,sizeof(ls)); 35 Rep(i,n,1) { 36 int c=(s[i]>='a'&&s[i]<='z')?s[i]-'a':26+s[i]-'A'; 37 For(j,0,51) ch[i][j]=ls[j]; 38 ls[c]=i; 39 } 40 } 41 42 int dp[N][N],tot; 43 struct G { 44 int len; 45 LL d[26]; 46 }; 47 48 const LL bs=1e17; 49 G operator +(const G&A,const G&B) { 50 G rs; 51 For(i,0,25) rs.d[i]=0; 52 rs.len=max(A.len,B.len)+1; 53 LL pr=0; 54 For(i,1,rs.len) { 55 rs.d[i]=A.d[i]+B.d[i]+pr; 56 if(rs.d[i]>=bs) pr=1,rs.d[i]-=bs; 57 else pr=0; 58 } 59 while(rs.d[rs.len]==0) rs.len--; 60 return rs; 61 } 62 63 G ans,g[500007]; 64 65 G dfs(int x,int y) { 66 if(dp[x][y]!=-1) return g[dp[x][y]]; 67 dp[x][y]=++tot; 68 G rs; rs.len=1; 69 For(i,0,25) rs.d[i]=0; rs.d[1]=1; 70 For(i,0,51) if(ch1[x][i]&&ch2[y][i]) { 71 rs=rs+dfs(ch1[x][i],ch2[y][i]); 72 } 73 g[dp[x][y]]=rs; 74 return rs; 75 } 76 77 void PT(G a) { 78 printf("%lld",a.d[a.len]); 79 Rep(i,a.len-1,1) { 80 if(a.d[i]==0) printf("0000000000000000"); 81 else { 82 LL tp=a.d[i]; 83 while(tp*10

View Code

2. 建筑师
(building.pas/c/cpp)
★问题描述:
小Z是一个很有名的建筑师,有一天他接到了一个很奇怪的任务:在数轴上建n个建筑,
每个建筑的高度是1到n之间的一个整数。小Z有很严重的强迫症,他不喜欢有两个建筑的高
度相同。另外小Z觉得如果从最左边(所有建筑都在右边)看能看到A个建筑,从最右边(所
有建筑都在左边)看能看到B个建筑,这样的建筑群有着独特的美感。现在,小Z想知道满足
上述所有条件的建筑方案有多少种?
如果建筑i的左(右)边没有任何建造比它高,则建筑i可以从左(右)边看到。两种方案不
同,当且仅当存在某个建筑在两种方案下的高度不同。
★数据输入:
输入文件名为building.in。
第一行一个整数 T,代表 T 组数据。
接下来T行,每行三个整数n,A,B。
★结果输出:
输出文件名为building.out。
9
对于每组数据输出一行答案 mod ( 10 ＾9+ 7 ) 。

输入示例
2
3 2 2
3 1 2

输出示例
2
1

★数据范围:
10% : 1 <= n <= 10
20% : 1 <= n <= 100
40% : 1 <= n <= 50000,1 <= T <= 5
100% :1 <= n <= 50000,1 <= A, B <= 100,1 <= T <= 200000。

1 //Achen 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 const int N=5e4+7; 9 const int mod=1e9+7;10 typedef long long LL;11 using namespace std;12 LL dp[N][207],C[207][207];13 int T,n,a,b;14 15 template
            
              void read(T &x) {16 char ch=getchar(); T f=1; x=0;17 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();18 if(ch=='-') f=-1,ch=getchar();19 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;20 }21 22 #define DEBUG23 int main() {24 #ifdef DEBUG25 freopen("building.in","r",stdin);26 freopen("building.out","w",stdout);27 #endif28 dp[1][1]=1;29 for(int i=2;i<=50000;i++) 30 for(int k=1;k<=min(200,i);k++) 31 dp[i][k]=(dp[i-1][k]*(i-1)%mod+dp[i-1][k-1])%mod;32 for(int i=0;i<=200;i++) C[i][0]=1;33 for(int i=1;i<=200;i++)34 for(int j=1;j<=i;j++)35 C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;36 read(T);37 while(T--) {38 read(n); read(a); read(b);39 LL ans=dp[n-1][a+b-2];40 ans=(ans*C[a+b-2][a-1])%mod;41 printf("%lld\n",ans);42 }43 return 0;44 }45 /*46 3 2 247 2 148 */

View Code

3. 神秘数
(mystic.pas/c/cpp)
★问题描述:
一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。例如
S={1,1,1,4,13},
1 = 1
2 = 1+1
3 = 1+1+1
4 = 4
5 = 4+1
6 = 4+1+1
7 = 4+1+1+1
8无法表示为集合S的子集的和,故集合S的神秘数为8。
现给定n个正整数a[1]..a[n],m个询问,每次询问给定一个区间[l,r](l<=r),求由
a[l],a[l+1],...,a[r]所构成的可重复数字集合的神秘数。
★编程任务:
求出每个查询的结果。
★数据输入:
输入文件名为mystic.in。
第一行一个整数n,表示数字个数。
第二行n个整数,从1编号。
第三行一个整数m,表示询问个数。
以下m行,每行一对整数l,r,表示一个询问。
★结果输出:
输出文件名为mystic.out。
对于每个询问,输出一行对应的答案。

输入示例
5
1 2 4 9 10
5
1 1
1 2
1 3
1 4
1 5

输出示例
2
4
8
8
8

★数据范围:
对于 10%的数据点,n,m <= 10
对于 30%的数据点,n,m <= 1000
对于 60%的数据点,n,m <= 50000
对于 100%的数据点,n,m <= 100000,∑a[i] <= 10

十分奥妙的一道题．

求一段区间的神秘数，先把区间内的数从小到大排序．

依次加入每个数x，若当前神秘数为ans

若x>ans+1，神秘数仍为ans

否则神秘数变为ans+x

排序后，找到第一个大于它前面所有数的和＋１的数，它前面所有数的和＋１即为神秘数．

那么求区间l,r的神秘数，先将当前神秘数ans设为1，查询区间内小于等于ans的数的和sum，若sum>ans，则ans=sum+1

1 //Achen 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
               11 #define For(i,a,b) for(int i=(a);i<=(b);i++)12 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)13 const int N=100007;14 typedef long long LL; 15 typedef double db;16 using namespace std;17 int n,m,a[N],sz;18 19 template
               
                 void read(T &x) {20 char ch=getchar(); x=0; T f=1;21 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();22 if(ch=='-') f=-1,ch=getchar();23 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;24 }25 26 int tot,rt[N],sg[N*71],ls[N*71],rs[N*71];27 #define lc ls[x]28 #define rc rs[x]29 #define mid ((l+r)>>1)30 void update(int &x,int l,int r,int pos,int last) {31 x=++tot;32 sg[x]=sg[last]+pos;33 lc=ls[last];34 rc=rs[last];35 if(l==r) return;36 if(pos<=mid) update(lc,l,mid,pos,ls[last]);37 else update(rc,mid+1,r,pos,rs[last]);38 }39 40 int qry(int x,int l,int r,int ql,int qr) {41 if(!x) return 0;42 if(l>=ql&&r<=qr) return sg[x];43 if(qr<=mid) return qry(lc,l,mid,ql,qr);44 if(ql>mid) return qry(rc,mid+1,r,ql,qr);45 return qry(lc,l,mid,ql,qr)+qry(rc,mid+1,r,ql,qr);46 }47 48 #define DEBUG49 int main() {50 #ifdef DEBUG51 freopen("mysti.in","r",stdin);52 freopen("mysti.out","w",stdout);53 #endif54 read(n);55 For(i,1,n) { read(a[i]); sz=max(sz,a[i]); }56 For(i,1,n) update(rt[i],1,sz,a[i],rt[i-1]);57 read(m);58 For(i,1,m) {59 int l,r;60 read(l); read(r);61 int ans=1;62 for(;;) {63 int tp=qry(rt[r],1,sz,1,ans)-qry(rt[l-1],1,sz,1,ans);64 if(tp