1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 500+10014 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 100000000723 using namespace std;24 inline int read()25 {26     int x=0,f=1;char ch=getchar();27     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}28     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}29     return x*f;30 }31 string a[200],b[200];32 inline bool find(int x,int y)33 {34     int l1=a[x].length(),l2=b[y].length();35     for0(i,l2-l1)36      {37          int j=i,k=0;38          while(a[x][k]==b[y][j])k++,j++;39          if(k<l1-1)continue;40          return 1;41      }42     return 0;43 }44 int main()45 {46     freopen("input.txt","r",stdin);47     freopen("output.txt","w",stdout);48     int n=read();49     for1(i,n+1)50     {51         getline(cin,a[i]);52         int l=a[i].length();53         for0(j,l-1)if(a[i][j]>=‘A‘&&a[i][j]<=‘Z‘)a[i][j]+=‘a‘-‘A‘;54     }    55     int m=1;56     for0(i,a[n+1].length()-1)57     {58         if(a[n+1][i]==‘.‘)m++;59         b[m]=b[m]+a[n+1][i];60     }61     m--;62     int ans=0;63     for1(i,n)64      for1(j,m)65       if(find(i,j))ans++; 66     printf("%d\n",ans);67     return 0;68 }

 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 50014 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 1000023 using namespace std;24 inline int read()25 {26     int x=0,f=1;char ch=getchar();27     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}28     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}29     return x*f;30 }31 class bigg32 {33 public:34     int num[maxn],len;35     bigg(){memset(num,0,sizeof(num));len=0;}36     bigg operator =(const bigg &b)37     {38         memset(num,0,sizeof(num));39         len=b.len;40         for1(i,len)num[i]=b.num[i];41         return (*this);42     }43     bigg operator =(int b)44     {45         memset(num,0,sizeof(num));len=0;46         while(b)num[++len]=b%mod,b/=mod;47         return (*this);48     }49     bigg operator *(int b)50     {51         bigg ans;52         ans.len=len;53         for1(i,len)ans.num[i]=num[i];54         int x=0;55         for1(i,len)56         {57             x+=ans.num[i]*b;58             ans.num[i]=x%mod;59             x/=mod;60         }61         if(x)ans.num[++ans.len]=x;62         return ans;63     }64     bigg operator +(const bigg &b)65     {66         bigg ans;ans=0;67         ans.len=max(len,b.len);68         for1(i,ans.len)69         {70             ans.num[i]+=num[i]+b.num[i];71             ans.num[i+1]=ans.num[i]/mod;72             ans.num[i]%=mod;73         }74         if(ans.num[ans.len+1])ans.len++;75         return ans;76     }77     void print()78     {79         printf("%d",num[len]);80         for3(i,len-1,1)printf("%04d",num[i]);printf("\n");81     }82 };83 bigg f[120][120];    84 int main()85 {86     freopen("input.txt","r",stdin);87     freopen("output.txt","w",stdout);88     for1(i,100)f[i][1]=1;89     for2(i,2,100)90      for2(j,2,i)91       f[i][j]=f[i-1][j]*j+f[i-1][j-1];92     int n,m;  93     while(cin>>n>>m)f[n][m].print();94     return 0;95 }

  1 #include<cstdio>  2 #include<cstdlib>  3 #include<cmath>  4 #include<cstring>  5 #include<algorithm>  6 #include<iostream>  7 #include<vector>  8 #include<map>  9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000000000ll 13 #define maxn 1500000 14 #define eps 1e-10 15 #define ll long long 16 #define pa pair<int,int> 17 #define for0(i,n) for(int i=0;i<=n;i++) 18 #define for1(i,n) for(int i=1;i<=n;i++) 19 #define for2(i,x,y) for(int i=x;i<=y;i++) 20 using namespace std; 21 inline ll read() 22 { 23     ll x=0,f=1;char ch=getchar(); 24     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 25     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 26     return x*f; 27 } 28 int fa[maxn],c[maxn][2],n,k,tot=0,rt=0; 29 ll sum[maxn],s[maxn],v[maxn],a[maxn]; 30 inline void pushup(int x) 31 { 32     int l=c[x][0],r=c[x][1]; 33     s[x]=s[l]+s[r]+1; 34     sum[x]=sum[l]+sum[r]+v[x]; 35 } 36 inline void rotate(int x,int &k) 37 { 38     int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1; 39     if(y==k)k=x;else c[z][c[z][1]==y]=x; 40     fa[x]=z;fa[y]=x;fa[c[x][r]]=y; 41     c[y][l]=c[x][r];c[x][r]=y; 42     pushup(y);pushup(x); 43 } 44 inline void splay(int x,int &k) 45 { 46     while(x!=k) 47      { 48         int y=fa[x],z=fa[y]; 49         if(y!=k) 50          { 51             if(c[z][0]==y^c[y][0]==x)rotate(x,k);else rotate(y,k); 52          } 53         rotate(x,k);  54      } 55 } 56 inline void ins(int &k,int kk,ll x) 57 { 58     if(!k) 59     { 60         k=++tot;s[tot]=1;fa[tot]=kk;v[tot]=sum[tot]=x;return; 61     } 62     s[k]++; 63     if(x<=v[k])ins(c[k][0],k,x);else ins(c[k][1],k,x); 64     pushup(k); 65 } 66 inline int find(int k,int x) 67 { 68     int l=c[k][0],r=c[k][1]; 69     if(s[l]+1==x)return k; 70     else if(s[l]>=x)return find(l,x); 71     else return find(r,x-s[l]-1);  72 } 73 inline int pos(int k,ll val) 74 { 75     if(v[k]==val)return k; 76     else if(val<v[k])return pos(c[k][0],val); 77     else return pos(c[k][1],val); 78 } 79 inline void del(ll val) 80 { 81     splay(pos(rt,val),rt); 82     int x=c[rt][0],y=c[rt][1]; 83     while(c[x][1])x=c[x][1]; 84     while(c[y][0])y=c[y][0]; 85     splay(x,rt);splay(y,c[x][1]); 86     fa[c[y][0]]=c[y][0]=0; 87     pushup(y);pushup(x); 88 } 89 int main() 90 { 91     freopen("input.txt","r",stdin); 92     freopen("output.txt","w",stdout); 93     n=read();k=read(); 94     for1(i,n)a[i]=read();  95     ins(rt,0,-1);ins(rt,0,1000000000001ll); 96     for1(i,k-1)ins(rt,0,a[i]),splay(i+2,rt); 97     ll ans=inf,x,y; 98     for1(i,n-k+1) 99      {100         ins(rt,0,a[i+k-1]);splay(i+k+1,rt);101         x=find(rt,(s[rt]>>1)+1);y=v[x];102         splay(x,rt);103         ans=min(ans,s[c[x][0]]*y-sum[c[x][0]]+sum[c[x][1]]-s[c[x][1]]*y);104         del(a[i]);105         if(ans==1000000000002ll)break;106      }107     cout<<ans-1000000000002ll<<endl;    108     return 0;109 }