12.12闲话-526互联

推歌

梨花香

缠着衣角掠过熙攘

复悄入红帘深帐

听枝头黄鹂逗趣儿

细风绕指淌

坐船舫

兰桨拨开雾霭迷茫

不觉已一日过半

过眼的葱郁风光

悉数泛了黄

褪尽温度的风

无言牵引中

便清晰了在此的眉目

暮色的消融

隐约了晦朔葱茏

在这老街回眸

烟云中追溯我是谁

只消暮雨点滴

便足以粉饰这是非

待这月色涌起

谁人轻叩这门扉

苔绿青石板街

斑驳了流水般岁月

小酌三盏两杯

理不清缠绕的情结

在你淡漠眉间

瞥见离人的喜悲霜雪

楼阁现

尘飞雾散荧光翩跹

显露出斑驳石阶

入眼是落英纷然

芳草入深院

凭栏杆

小桌上置琼觞两盏

阖眼听清风疏叶

似曾有欢声笑言

萦绕这高轩

云动寂静鸣蝉

雨坠激漪涟

皴擦点染勾勒这世间

缘起的一眼

定格了三生千年

在这老街回眸

烟云中追溯我是谁

只消暮雨点滴

便足以粉饰这是非

待这月色涌起

谁人轻叩这门扉

苔绿青石板街

斑驳了流水般岁月

小酌三盏两杯

理不清缠绕的情结

在你淡漠眉间

瞥见离人的喜悲霜雪

三月梨花雪

几载开了又败

笔锋走黑白

丹青中穿插无奈

彼时那弯儿月

何时初现于江畔

而我又在待何人

在这亭台回眸

千年后忆起你是谁

只消月色隐约

便足以勾勒这是非

待这回忆涌起

恍惚之间已下泪

枫红十里长街

红帘后谁人蹙着眉

遥梦桑竹桃源

轮回中曾道别的地点

愿今生再相见

消融你眉间悲戚霜雪

今天只打了一道字符串，光给别人讲题了，输输输

Bovine Genomics

给定\(n\)个A串和\(n\)个B串，长度均为\(m\)，求一个最短的区间\([l,r]\)

使得不存在一个A串\(a\)和一个B串\(b\)，使得\(a[l,r]=b[l,r]\)

CODE

 #include<bits/stdc++.h>
   #define int long long
   #define maxm 0X66CCFF
   #define N 510
   namespace IO{
       inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);}
       inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
       inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s=(s<<3)+(s<<1)+ch-'0';ch = getchar();}return s*w;}
       inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}if(cnt==0)putchar('0');while(cnt>0)putchar(F[--cnt]);putchar(' ');}
   }
   using namespace IO;
   using namespace std;
   const int P1=315716251,P2=475262633;
   int a,b;
   struct Hash{
       int h1[N],h2[N],z1[N],z2[N];
       inline void Init(const char *s){
           int n=strlen(s+1);
           const int b=131;
           z1[0]=z2[0]=1;
           for(register int i=1;i<=n;i++){
               z1[i]=z1[i-1]*b%P1;
               z2[i]=z2[i-1]*b%P2;
               h1[i]=(h1[i-1]*b+(s[i]-'A'+1%P1))%P1;
               h2[i]=(h2[i-1]*b+(s[i]-'A'+1%P2))%P2;
           }
       }
       inline int Get1(int l,int r){
           return (h1[r]-h1[l-1]*z1[r-l+1]%P1+P1)%P1;
       }
       inline int Get2(int l,int r){
           return (h2[r]-h2[l-1]*z2[r-l+1]%P2+P2)%P2;
       }
   }aaa[N],bbb[N];
   map<long long,bool> mp1,mp2;
   inline bool Check(int n){
       for(register int i=n;i<=b;++i){
           bool f=1;
           mp1.clear(),mp2.clear();
           for(register int j=1;j<=a;++j){
               mp1[aaa[j].Get1(i-n+1,i)]=true;
               mp2[aaa[j].Get1(i-n+1,i)]=true;
           }
           for(register int j=1;j<=a;++j){
               if(mp1[bbb[j].Get1(i-n+1,i)]) f=0;
               if(mp2[bbb[j].Get1(i-n+1,i)]) f=0;
           }
           if(f) return true;
       }
       return false;
   }
   char aa[510][510];
   char bb[510][510];
   signed main(){
       #ifndef ONLINE_JUDGE
       freopen("1.in","r",stdin);
       freopen("1.out","w",stdout);
       #endif
       a=read(),b=read();
       for(register int i(1);i<=a;++i){
           scanf("%s",aa[i]+1);
           aaa[i].Init(aa[i]);
       }
       for(register int i(1);i<=a;++i){
           scanf("%s",bb[i]+1);
           bbb[i].Init(bb[i]);
       }
       int l(1),r(b);
       while(l<r){
           int mid((l+r)>>1);
           if(Check(mid))r=mid;
           else l=mid+1;
       }
       write(l);
   }

Trie，即字典树

这棵字典树用边来代表字母，而从根结点到树上某一结点的路径就代表了一个字符串

非常好理解，爱来自KMP和hash

From OI-wiki

From K8He

点击查看代码

#include<bits/stdc++.h>
#define int long long
#define MAXM 0X66CCFF
#define MAXN 0X6CF
const int INF=0X66CCFF0712;
namespace IO{
    inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);}
    inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
    inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s=(s<<3)+(s<<1)+ch-'0';ch = getchar();}return s*w;}
    inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}if(cnt==0)putchar('0');while(cnt>0)putchar(F[--cnt]);putchar(' ');}
}
using namespace IO;
using namespace std;
struct TRIE{
    struct TR{
        int nxt[26];
        bool end;
    }tr[MAXN];
    int tot=1;
    inline void ADD(char *s){
        int len(strlen(s+1)),p(1);
        for(int i=1;i<=len;++i){
            tr[p].nxt[s[i]-'a'] = !(tr[p].nxt[s[i]-'a']) ? ++tot : 0;
            p=tr[p].nxt[s[i]-'a'];
        }
        tr[p].end=1;
    }   
    inline bool FIND(char *s){
        int len(strlen(s)),p(1);
        for(int i=1;i<=len;++i){
            if(!tr[p].nxt[s[i]-'a']) return 0;
            p=tr[p].nxt[s[i]-'a'];
        }
        return(tr[p].end);
    }    
}Trie;
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif 
}

01-Trie 是指字符集为 \(\{0,1\}\) 的 Trie

把数字转为二进制塞到01-Tire里可以解决一些异或的问题

异或有着按位考虑的性质，每一位的贡献是分开的，而Trie正好是按照位来存深度的，这不吻合了吗然后乱搞就行