对我而言相当失败的一次考试呢。
(昨天失了智一晚上没睡觉还好意思说)T1: 看到数据范围与值域有关,是不是想到了一些有趣的事情呢?两两gcd为1,显然我们把同时选出的数分解质因子后,每个质数出现最多一次。是不是能状压DP呢?(然后我发现2000内的质数有将近200个,没法状压,然后写了30分暴力)这里有一个很显然的性质,数字x>=sqrt(x)的质因子最多只有1个,所以我们只需要状压<=sqrt(2000)的质因数,即{2-43},只有14个。其余的,我们能按照大质因子分组,然后每组最多选1个数字。我们令f[i][sta]表示前i组,质因数状态为sta的方案数。转移的话可以枚举这组选择哪个数字,然后进行转移。注意没有>43质因子的数字要各自一组,因为它们不存在互斥状态。代码:1 #include2 #include 3 #include 4 typedef long long int lli; 5 const int maxn=2e3+1e2,maxs=(1<<14)+5; 6 const int prime[]={ 2,3,5,7,11,13,17,19,23,29,31,37,41,43},pl=14,full=1<<14; 7 const int mod=1e9+7; 8 9 struct Node {10 int sta,mx;11 friend bool operator < (const Node &a,const Node &b) { return a.mx > b.mx; }12 }ns[maxn];13 14 std::vector grp[maxn];15 lli f[maxn][maxs],ans;16 int n,cnt;17 18 inline Node cut(int x) {19 int ret = 0;20 for(int i=0;i
1 #include2 #include 3 #include 4 #include 5 #define debug cout 6 using namespace std; 7 const int maxn=2e6+1e2,maxl=23; 8 9 char in[maxn>>1];10 int Log[maxn>>1],li,ans;11 12 struct SuffixAutomatic {13 int ch[maxn][26],tc[maxn][26],fa[maxn],len[maxn],rit[maxn],root,last,cnt;14 int stk[maxn],sa[maxn>>1],rnk[maxn>>1],h[maxn>>1],rmq[maxn>>1][maxl],top,sal;15 SuffixAutomatic() { last = root = cnt = 1; }16 inline int NewNode(int ll) {17 return len[++cnt] = ll , cnt;18 }19 inline void extend(int x,int r) {20 int p = last , np = NewNode(len[p]+1); rit[np] = r;21 while( p && !ch[p][x] ) ch[p][x] = np , p = fa[p];22 if( !p ) fa[np] = root;23 else {24 int q = ch[p][x];25 if( len[q] == len[p] + 1 ) fa[np] = q;26 else {27 int nq = NewNode(len[p]+1);28 memcpy(ch[nq],ch[q],sizeof(ch[q])) , fa[nq] = fa[q] , fa[np] = fa[q] = nq;29 while( p && ch[p][x] == q ) ch[p][x] = nq , p = fa[p];30 }31 }32 last = np;33 }34 inline void pre(int pos) {35 for(int i=0,t;i<26;i++) if( ( t = ch[pos][i] ) && len[t] == len[pos] + 1 ) {36 stk[++top] = i , tc[fa[t]][stk[len[t]-len[fa[t]]]] = t , pre(t) , stk[top--] = '\0';37 }38 }39 inline void dfs(int pos) {40 if( rit[pos] ) sa[++sal] = rit[pos];41 for(int i=0;i<26;i++) if( tc[pos][i] ) dfs(tc[pos][i]);42 }43 inline void geth(char* in,int li) {44 for(int i=1;i<=sal;i++) rnk[sa[i]] = i;45 reverse(in+1,in+1+li);46 for(int i=1,k=0;i<=sal;i++) {47 k -= (bool)k;48 const int p = sa[rnk[i]-1];49 while( in[i+k] == in[p+k] ) ++k;50 h[rnk[i]-1] = k;51 }52 reverse(in+1,in+1+li);53 }54 inline void initrmq() {55 for(int i=1;i r ) swap(l,r);61 --r;62 int L = Log[r-l+1];63 return min( rmq[l][L] , rmq[r-(1< = len ) {82 ans = max( ans , len * 2 );83 }84 }85 }86 87 int main() {88 scanf("%s",in+1) , li = strlen(in+1);89 for(int i=2;i<=li;i++) Log[i] = Log[i>>1] + 1;90 suf.work(in,li) , reverse(in+1,in+1+li) , prf.work(in,li) , reverse(in+1,in+1+li);91 for(int i=1;i<=li;i++) calc(i);92 printf("%d\n",ans);93 return 0;94 }
倍增:
1 #include2 #include 3 #include 4 #include 5 #define debug cout 6 using namespace std; 7 const int maxn=2e6+1e2,maxl=23; 8 9 char in[maxn>>1];10 int Log[maxn>>1],li,ans;11 12 struct SuffixArray {13 int sa[maxn],rnk[maxn],h[maxn],tax[maxn],tp[maxn],rmq[maxn][maxl],n,m;14 inline void Resort() {15 for(int i=0;i<=m;i++) tax[i] = 0;16 for(int i=1;i<=n;i++) tax[rnk[i]]++;17 for(int i=1;i<=m;i++) tax[i] += tax[i-1];18 for(int i=n;i;i--) sa[tax[rnk[tp[i]]]--] = tp[i];19 }20 inline bool judge(int* s,int a,int b,int l) {21 return s[a] == s[b] && s[a+l] == s[b+l];22 }23 inline void buildh() {24 for(int i=1,k=0,j;i<=n;i++) {25 k = k ? k - 1 : 0 , j = sa[rnk[i]-1];26 while( in[i+k] == in[j+k] ) ++k;27 h[rnk[i]-1] = k;28 }29 }30 inline void get(char* in,int nn) {31 n = nn;32 for(int i=1;i<=n;i++) rnk[i] = in[i] , tp[i] = i;33 m = 127 , Resort();34 for(int w=1,p=1;p w ) tp[++p] = sa[i] - w;38 Resort(); swap(tp,rnk); rnk[sa[1]] = p = 1;39 for(int i=2;i<=n;i++)40 rnk[sa[i]] = judge(tp,sa[i],sa[i-1],w) ? p : ++p;41 }42 buildh() , initrmq();43 }44 inline void initrmq() {45 for(int i=1;i r ) swap(l,r);51 --r;52 int L = Log[r-l+1];53 return min( rmq[l][L] , rmq[r-(1< = len ) {67 ans = max( ans , len * 2 );68 }69 }70 }71 72 int main() {73 scanf("%s",in+1) , li = strlen(in+1);74 for(int i=2;i<=li;i++) Log[i] = Log[i>>1] + 1;75 prf.get(in,li) , reverse(in+1,in+1+li) , suf.get(in,li);76 for(int i=1;i<=li;i++) calc(i);77 printf("%d\n",ans);78 return 0;79 }
Update 20180509:
然而现在我还不会倍增......不过我可以后缀平衡树求后缀数组是吧。复杂度也是nlogn。由于这题测试点1718的特殊性,后缀平衡树的log跑不满,可以随便AC。而测试点24也能过,只有25跑2s+......代码:1 #pragma GCC optimize("Ofast") 2 #pragma GCC optimize("no-stack-protector") 3 #pragma GCC target("avx") 4 #include5 #include 6 #include 7 const int maxn=1e6+1e2,maxl=23; 8 const double alpha=0.95; 9 10 char in[maxn]; 11 int Log[maxn],li,ans; 12 13 struct SuffixArray { 14 int sa[maxn],rnk[maxn],h[maxn],rmq[maxn][maxl],n,m,sal; 15 16 int at[maxn],lson[maxn],rson[maxn],siz[maxn],sf[maxn],root,cnt; 17 int seq[maxn],sql; 18 int fail,failfa; 19 double v[maxn],vfl,vfr; 20 21 inline bool cmp(int x,int y) { 22 if( !x || !y ) return !x; 23 if( in[x] != in[y] ) return in[x] < in[y]; 24 else return v[at[x-1]] < v[at[y-1]]; 25 } 26 inline void upgrade(int pos,double l,double r) { 27 siz[pos] = siz[lson[pos]] + siz[rson[pos]] + 1; 28 if( std::max( siz[lson[pos]] , siz[rson[pos]] ) > siz[pos] * alpha ) fail = pos , failfa = -1 , vfl = l , vfr = r; 29 else if( fail == lson[pos] || fail == rson[pos] ) failfa = pos; 30 } 31 inline void insert(int &pos,double l,double r,const int &id) { 32 if( !pos ) { 33 v[at[id]=pos=++cnt]= ( l + r ) / 2.0 , siz[pos] = 1 , sf[pos] = id; 34 return; 35 } const double vmid = ( l + r ) / 2.0; 36 if( cmp(sf[pos],id) ) insert(rson[pos],vmid,r,id) , upgrade(pos,l,r); // id > sf[pos] . 37 else insert(lson[pos],l,vmid,id) , upgrade(pos,l,r); 38 } 39 inline int rebuild(int ll,int rr,double l,double r) { 40 const int mid = ( ll + rr ) >> 1 , pos = seq[mid]; 41 const double vmid = ( l + r ) / 2.0; v[pos] = vmid , siz[pos] = rr - ll + 1; 42 if( ll < mid ) lson[pos] = rebuild(ll,mid-1,l,vmid); 43 if( mid < rr ) rson[pos] = rebuild(mid+1,rr,vmid,r); 44 return pos; 45 } 46 inline void dfs(int pos) { 47 if(lson[pos]) dfs(lson[pos]); 48 seq[++sql] = pos; 49 if(rson[pos]) dfs(rson[pos]); 50 lson[pos] = rson[pos] = siz[pos] = 0; 51 } 52 inline void insert(const int &id) { 53 fail = 0 , failfa = -1 , insert(root,0,1,id); 54 if(fail) { 55 sql = 0 , dfs(fail); 56 if( ~failfa ) { 57 if( fail == lson[failfa] ) lson[failfa] = rebuild(1,sql,vfl,vfr); 58 else rson[failfa] = rebuild(1,sql,vfl,vfr); 59 } else root = rebuild(1,sql,0,1); 60 } 61 } 62 inline void getsa(int pos) { 63 if(lson[pos]) getsa(lson[pos]); 64 sa[++sal] = n - sf[pos] + 1; 65 if(rson[pos]) getsa(rson[pos]); 66 } 67 68 inline void work(char* in,int li) { 69 n = li , std::reverse(in+1,in+1+n) , in[n+1] = '#'; 70 insert(0); 71 for(int i=1;i<=li;i++) insert(i); 72 getsa(root) , std::reverse(in+1,in+1+n) , geth() , initrmq(); 73 } 74 75 inline void geth() { 76 for(int i=1;i<=n;i++) rnk[sa[i]] =i; 77 for(int i=1,k=0,j;i<=n;i++) { 78 k = k ? k - 1 : 0 , j = sa[rnk[i]-1]; 79 while( in[i+k] == in[j+k] ) ++k; 80 h[rnk[i]-1] = k; 81 } 82 } 83 inline void initrmq() { 84 for(int i=1;i r ) std::swap(l,r); 90 --r; 91 int L = Log[r-l+1]; 92 return std::min( rmq[l][L] , rmq[r-(1< = len ) ans = len * 2;106 }107 }108 109 int main() {110 fread(in+1,1,maxn,stdin) , li = strlen(in+1);111 for(int i=2;i<=li;i++) Log[i] = Log[i>>1] + 1;112 prf.work(in,li) , std::reverse(in+1,in+1+li) , suf.work(in,li);113 for(int i=li;i&&!ans;i--) calc(i);114 printf("%d\n",ans);115 return 0;116 }
T3:
考试的时候根本没时间看这题了(其实是前两题不会就心态爆炸弃疗了)。正解是一个神奇的构造:代码:1 #include2 #include 3 const int maxn=2e5+1e2; 4 5 int a[maxn],b[maxn],sou[maxn],tar[maxn],swa[maxn][2],swb[maxn][2],n,al,bl; 6 7 int main() { 8 scanf("%d",&n); 9 for(int i=1;i<=n;i++) scanf("%d",a+i) , sou[a[i]] = i;10 for(int i=1;i<=n;i++) scanf("%d",b+i) , tar[b[i]] = i;11 for(int i=1,t;i<=n;i++) if( a[i] != b[i] ) {12 if( tar[a[i]] >= sou[b[i]] ) std::swap(a[i],a[t=sou[b[i]]]) , sou[a[t]] = t , sou[a[i]] = i , swa[++al][0] = i , swa[al][1] = t;13 else std::swap(b[i],b[t=tar[a[i]]]) , tar[b[t]] = t , tar[b[i]] = i , swb[++bl][0] = i , swb[bl][1] = t;14 }15 printf("%d\n",al+bl);16 for(int i=1;i<=al;i++) printf("%d %d\n",swa[i][0],swa[i][1]);17 for(int i=bl;i;i--) printf("%d %d\n",swb[i][0],swb[i][1]);18 return 0;19 }