DZY 's BLOG

第i头牛，可以使用第j个防晒霜的，从j到i连一条容量1的边。

每个防晒霜从S给它连容量为cover[i]的边。

求一遍最大流就好了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10000,maxm=5000000,inf=1000000009;
int p[maxm],c[maxm],n1[maxm],q[maxn],h1[maxn],d[maxn],h[maxn],g[maxn];
int l[3000],r[3000],S,T,n,m,k,tot=0,cnt=0,N=0;  char buf[2000000],*pt=buf;
inline int getint(){    int r=0; while(*pt<48||*pt>57)pt++; 
    while(*pt>47&&*pt<58)r=r*10+*pt++-48; return r;
}inline void ae(int x,int y,int z){
    p[tot]=y;   c[tot]=z;   n1[tot]=h[x];   h[x]=tot++;
    p[tot]=x;   c[tot]=0;   n1[tot]=h[y];   h[y]=tot++;
}inline int bfs(){
    memset(d,0xff,sizeof(d));   int r=d[q[0]=S]=0;
    for(int l=0;l<=r;l++)
        for(int k=h[q[l]];~k;k=n1[k])
            if(c[k] && !~d[p[k]])   d[q[++r]=p[k]]=d[q[l]]+1;
    return ~d[T];
}int dfs(int x=S,int lmt=inf){
    if(x==T)    return lmt; int flow;
    for(int &k=g[x];~k;k=n1[k]){
        if(c[k] && d[p[k]]==d[x]+1 && (flow=dfs(p[k],min(lmt,c[k])))){
            c[k]-=flow; c[k^1]+=flow;   return flow;
        }
    }return 0;
}int main(){
    memset(h,-1,sizeof(h));
    fread(pt,1,2000000,stdin);  n=getint(); m=getint(); S=0; T=n+m+1;
    for(int i=1;i<=n;i++)   l[i]=getint(),r[i]=getint(),ae(m+i,T,1);
    for(int i=1;i<=m;i++){
        int u,v; u=getint(),v=getint();  ae(S,i,v);
        for(int j=1;j<=n;j++) if(l[j]<=u&&u<=r[j]) ae(i,m+j,1);
    }int An=0,f=0;   while(bfs()){   memcpy(g,h,sizeof(h));  while(f=dfs())  An+=f;}
    printf("%d\n",An);    return 0;
} 

观察到n的范围极小，m的范围也才1000000。那就可以枚举答案了。

枚举答案M。满足对于任何(i,j)，都满足C[i]+x*P[i]=C[j]+x*P[j](mod M)的最小正整数解x大于min(L[i],L[j])，或者不存在x。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;ll An=0,c[20],p[20],l[20]; int n;
ll ext_gcd(ll a,ll b,ll&x,ll&y){
    if(!b){ x=1; y=0; return a;}
    ll xx,yy,d=ext_gcd(b,a%b,xx,yy);
    x=yy; y=xx-a/b*yy; return d;
}ll equ(ll a,ll b,ll c){
    ll x,y,d=ext_gcd(a,c,x,y); if(b%d) return -1;
    x*=b/d; while(x>c/d)x-=c/d;
    while(x<0) x+=c/d; return x;
}int check(ll m){
    for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++){
        ll d; if(p[i]>=p[j])d=equ(p[i]-p[j],c[j]-c[i],m);
        else d=equ(p[j]-p[i],c[i]-c[j],m);
        if(d!=-1&&d<=min(l[i],l[j]))return 1;
    }return 0;
}int main(){
    scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&c[i],&p[i],&l[i]),An=max(An,c[i]);
    for(;check(An);An++); printf("%lld\n",An); return 0;
}

二分图。赤果果的费用流。其实是KM。但是不会写。只好写费用流替代了。

先O(n^2)判哪些数对(x,y)可行。然后连边，做最大费用流。

因为每个数只能取一次。那么我把(x,y)和(y,x)都连了一遍。那么结果除以二。

判断选了几对，只要看T点的流量有多少不是从TT流过来的就行了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxm=5000000,inf=1061109567;
int h[10005],p[maxm],c[maxm],cost[maxm],n1[maxm],q[maxm],sp[10005],inq[10005];
int sq[1000005]={0},S,T,TT,An=0,path[maxm],pre[10005],tot=0;
inline void ae(int a,int b,int cc,int co){
    p[tot]=b; c[tot]=cc; cost[tot]=co;  n1[tot]=h[a]; h[a]=tot++;
    p[tot]=a; c[tot]=0;  cost[tot]=-co; n1[tot]=h[b]; h[b]=tot++;
}inline int spfa(){
    memset(sp,63,sizeof(sp));   memset(inq,0,sizeof(inq));
    int head=0,tail=1; sp[S]=0; q[0]=S; inq[S]=1; pre[S]=-1;
    while(head!=tail){
        int u=q[head++]; if(head>=maxm) head-=maxm; inq[u]=0;
        for(int i=h[u];~i;i=n1[i])
            if(c[i]>0&&sp[p[i]]>sp[u]+cost[i]){
                path[p[i]]=i, pre[p[i]]=u, sp[p[i]]=sp[u]+cost[i];
                if(!inq[p[i]]){ inq[p[i]]=1, q[tail++]=p[i]; if(tail>=maxm) tail-=maxm;}
            }
    }return sp[T]!=inf;
}inline int aug(){
    int delta=inf,  flow=0;
    for(int i=T;pre[i]!=-1;i=pre[i]) delta=min(delta,c[path[i]]);
    for(int i=T;pre[i]!=-1;i=pre[i]){
        c[path[i]]-=delta, c[path[i]^1]+=delta;
        flow+=cost[path[i]]*delta;
    }return flow;
}inline int cf(){
    int ret=0; while(spfa()) ret+=aug(); return ret;
}int gcd(int a,int b){
    return (!b)?a:gcd(b,a%b);
}int main(){
    int a,b;    scanf("%d%d",&a,&b);    memset(h,-1,sizeof(h));
    for(int i=1;i<=1000;i++) sq[i*i]=i; S=0;TT=(b-a+1)<<1|1;T=TT+1;
    for(int i=a;i<=b;i++) for(int j=i+1;j<=b;j++)
        if(sq[j*j-i*i]&&gcd(sq[j*j-i*i],i)==1){
            ae(j-a+1,b-a+1+i-a+1,1,-i-j);
            ae(i-a+1,b-a+1+j-a+1,1,-i-j);
        }ae(TT,T,inf,0);
    for(int i=1;i<=b-a+1;i++) ae(S,i,1,0), ae(i,TT,1,0), ae(b-a+1+i,T,1,0);
    int An1,An2=-cf();
    for(int i=h[T];~i;i=n1[i]) if(p[i]==TT)An=b-a+1-c[i];
    printf("%d %d\n",An>>1,An2>>1);  return 0;    
}

正在纠结这类水题有没有写题解的必要？

暴露智商了。囧。我智商-∞岂会轻易告诉你们？

把所有1的点放进队列。bfs。没了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define mp make_pair 
#define qsize 2000000
typedef pair<int,int> pii; pii q[qsize];
int head=0,tail=0,n,m,d[1005][1005];    char s[1005];
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int main(){
    scanf("%d%d",&n,&m);    memset(d,63,sizeof(d));
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        for(int j=1;j<=m;j++) if(s[j]-'0') q[tail++]=mp(i,j), d[i][j]=0;
    }while(head!=tail){
        pii u=q[head++]; if(head>=qsize) head-=qsize;
        for(int k=0;k<4;k++){
            int xx=u.first+dx[k],yy=u.second+dy[k];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&d[u.first][u.second]+1<d[xx][yy]){
                d[xx][yy]=d[u.first][u.second]+1;
                q[tail++]=mp(xx,yy); if(tail>=qsize) tail-=qsize;
            }
        }
    }for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) printf("%d ",d[i][j]);
        printf("\n");
    }return 0;
}

题意：给一个字符串。输出在原串中出现次数大于1的子串的出现次数。这些本质不同的子串按字典序大小排序输出次数。

一眼题？嗯。、后缀数组就行了、根据sa数组和height数组扫一遍。前后扫height数组。

反正n≤3000，没必要二分了。还要写rmq啥的多麻烦啊是吧、、然后就行了、感觉跑的蛮快的？

第一次加了fread和fwrite还变慢了、、

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=2000005;
int tmp1[maxn],tmp2[maxn],cs[maxn],cv[maxn],rank[maxn],height[maxn],sa[maxn];
char s[maxn],str[maxn];
inline bool cmp(int *r,int a,int b,int l){
    return  r[a]==r[b] && r[a+l]==r[b+l];
}inline void da(char *r,int *sa,int n,int m){
    int i,j,p,*x=tmp1,*y=tmp2,*t;
    for(i=0;i<m;i++)cs[i]=0;
    for(i=0;i<n;i++)cs[x[i]=r[i]]++;
    for(i=1;i<m;i++)cs[i]+=cs[i-1];
    for(i=n-1;i>=0;i--)sa[--cs[x[i]]]=i;
    for(j=1,p=1;p<n;j<<=1,m=p){
        for(p=0,i=n-j;i<n;i++)y[p++]=i;
        for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
        for(i=0;i<n;i++)cv[i]=x[y[i]];
        for(i=0;i<m;i++)cs[i]=0;
        for(i=0;i<n;i++)cs[cv[i]]++;
        for(i=1;i<m;i++)cs[i]+=cs[i-1];
        for(i=n-1;i>=0;i--)sa[--cs[cv[i]]]=y[i];
        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
}inline void ch(char *r,int n){
    int i,j,k=0;
    for(i=0;i<n;i++)rank[sa[i]]=i;
    for(i=0;i<n;height[rank[i++]]=k)
        for(k=max(k-1,0),j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}int main(){
    int n;  scanf("%d%s",&n,str);
    for(int i=0;i<n;i++)str[i]++;   str[n++]=0;
    da(str,sa,n,256);   ch(str,n);
    for(int i=1;i<n;i++){
        for(int j=height[i]+1;sa[i]+j<n;j++){
            int l,r;
            for(l=i;l>=0 && height[l]>=j;l--);
            for(r=i+1;r<=n && height[r]>=j;r++);
            if(r-l<=1)continue;
            printf("%d\n",r-l);
        }
    }return 0;
}

煞笔的煞笔又来发水题题解了！

二分答案。先判一级公路然后判二级公路。没了。

1A什么的不必多说。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct E{ int u,v,c1,c2;}e[20005];
inline bool C(E a,E b){ return a.c1<b.c1;}
int F[10005],n,k,m; char buf[2000000],*pt=buf;
int GF(int x){  return x==F[x]?x:F[x]=GF(F[x]);}
inline int getint(){ 
    int r=0;while(*pt<'0'||*pt>'9')pt++;while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;return r;
}inline int ok(int lmt){
    int ck=0,ca=0;
    for(int i=1;i<=n;i++) F[i]=i;
    for(int i=1;i<=m;i++){
        if(e[i].c1<=lmt){
            int u=GF(e[i].u),v=GF(e[i].v);
            if(u!=v) F[u]=v,ck++,ca++;
            if(ca==n-1) return 1;
        }else{
            if(ck<k) return 0;
            if(min(e[i].c1,e[i].c2)>lmt) continue;
            int u=GF(e[i].u),v=GF(e[i].v);
            if(u!=v) F[u]=v,ca++;
            if(ca==n-1) return 1;
        }
    }return 0;
}int main(){
    fread(pt,1,2000000,stdin);  int i;
    for(n=getint(),k=getint(),m=getint(),i=1;i<m;i++)
        e[i].u=getint(),e[i].v=getint(),e[i].c1=getint(),e[i].c2=getint();
    sort(e+1,e+m+1,C);  int l=0,r=1000000009,mid;
    while(l<=r){
        mid=l+r>>1;
        if(ok(mid)) r=mid-1;    else    l=mid+1;
    }printf("%d\n",l);return 0;
}

题意：给你一个字符串。每次取出第一个字符或最后一个字符，放到新的字符串（初始为空）后面。求最小字典序的新字符串。

比如样例：ACDBCB。按这样的顺序拿：头尾尾尾头尾。这样得到ABCBCD。可以证明没有比它字典序更小的了。

一开始我先YY了个很傻比的贪心。第一个字符和最后一个字符比较。取小的。然后O(n)扫一遍。（画外音：你煞笔啊、gold的题目就给你这么水掉啊！、、）本着这种态度很快就发现样例都过不了。先取出A、B。然后是取队头的C还是队尾的C呢。这时就发现光比较这一个字符的大小是不够的。要比较整个字符串和整个字符串反转过来的字符串的字典序大小，才能决定取哪个。

那么想到了什么呢？很明显就是后缀数组。

把这个字符串反转一遍接在原字符串后面，中间加一个分隔符（最好是小于'A'的，比如'@'）。然后求出rank数组。

下标  0  1 2 3  4 5 6  7 8  9 10 11 12

字符  A C D B C B @ B C B D  C   A

那么维护两个指针，一个从0开始，一个从n+1（反转的字符串的起点）开始。比较rank的大小，每次取小的先输出。OK！

（fread、fwrite蛮好的、轻松rank3）

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=100000;
int tmp1[maxn],tmp2[maxn],cs[maxn],cv[maxn],rank[maxn],sa[maxn],str[maxn];
char s[maxn],buf[maxn],*p=buf,buf2[maxn],*o=buf2;
inline bool cmp(int *r,int a,int b,int l){
    return  r[a]==r[b] && r[a+l]==r[b+l];
}inline void da(char *r,int *sa,int n,int m){
    int i,j,p,*x=tmp1,*y=tmp2,*t;
    for(i=0;i<m;i++)cs[i]=0;
    for(i=0;i<n;i++)cs[x[i]=r[i]]++;
    for(i=1;i<m;i++)cs[i]+=cs[i-1];
    for(i=n-1;i>=0;i--)sa[--cs[x[i]]]=i;
    for(j=1,p=1;p<n;j<<=1,m=p){
        for(p=0,i=n-j;i<n;i++)y[p++]=i;
        for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
        for(i=0;i<n;i++)cv[i]=x[y[i]];
        for(i=0;i<m;i++)cs[i]=0;
        for(i=0;i<n;i++)cs[cv[i]]++;
        for(i=1;i<m;i++)cs[i]+=cs[i-1];
        for(i=n-1;i>=0;i--)sa[--cs[cv[i]]]=y[i];
        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }for(i=0;i<n;i++)rank[sa[i]]=i;
}int main(){
    fread(p,1,maxn,stdin);  int t=0,n=0;
    while(*p<'0'||*p>'9')p++;
    while(*p>='0'&&*p<='9')n=n*10+*p++-48;
    for(int i=1;i<=n;i++){ 
        while(*p<'A'||*p>'Z')p++;
        s[t++]=*p++; 
    }s[t++]='A'-1;
    for(int i=n-1;~i;i--)   s[t++]=s[i];    s[t++]='\0';
    da(s,sa,t,256);
    int j=0,k=n+1,c=0;
    for(int i=1;i<=n;i++)str[c++]=rank[j]>rank[k]?k++:j++;
    for(int i=0;i<n;i++){
        if(i&&i%80==0)*o++='\n';
        *o++=s[str[i]];
    }fwrite(buf2,1,o-buf2,stdout);
    return 0;
}

题意：修改区间内的数、询问区间内任意子段和的期望值。

然后我们尝试把每次的答案求出来。然后对这个式子乱搞。发现对于每个数a[i]，维护a[i],i*a[i],i*i*a[i]就好了、

那么线段树维护就行了。好了没了。（其实是我懒得写题解了、、、

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define lson l,mid,ls
#define rson mid+1,r,rs
#define root 1,n,1
typedef long long ll;
const int maxn=500005;
ll a[maxn]={0},b[maxn]={0},c[maxn]={0},add[maxn]={0};
char buf[5000000],*pt=buf,buf2[5000000],*o=buf2;
inline ll getint(){
    ll r=0,f=1; while((*pt!='-')&&(*pt<'0'||*pt>'9'))pt++; if(*pt=='-')f=-1, pt++;
    while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;   return r*f;
}inline char getop(){
    while(*pt!='C'&&*pt!='Q')pt++;  return *pt;
}inline void print(ll x){
    char str[30],*p=str; if(!x)*o++=48;
    else{ while(x) *p++=x%10+48,x/=10; while(p--!=str)*o++=*p;}
}inline void pushup(ll rt){
    a[rt]=a[ls]+a[rs], b[rt]=b[ls]+b[rs], c[rt]=c[ls]+c[rs];
}inline void pushdown(ll l,ll r,ll rt){
    ll lc=mid-l+1, rc=r-mid, rr=mid, ll=mid+1;  
    if(add[rt]){
        add[ls]+=add[rt];
        a[ls]+=lc*add[rt];
        b[ls]+=(l+rr)*lc*add[rt]>>1;
        c[ls]+=(rr*(rr+1)*(rr<<1|1)-(l-1)*l*(l-1<<1|1))/6*add[rt];
        add[rs]+=add[rt];
        a[rs]+=rc*add[rt];
        b[rs]+=(ll+r)*rc*add[rt]>>1;
        c[rs]+=(r*(r+1)*(r<<1|1)-(ll-1)*ll*(ll-1<<1|1))/6*add[rt];
        add[rt]=0;
    }
}void update(ll L,ll R,ll d,ll l,ll r,ll rt){
    if(L<=l&&r<=R){
        add[rt]+=d;
        a[rt]+=(r-l+1)*d;
        b[rt]+=(l+r)*(r-l+1)*d>>1;
        c[rt]+=(r*(r+1)*(r<<1|1)-(l-1)*l*(l-1<<1|1))/6*d;
        return;
    }pushdown(l,r,rt);
    if(L<=mid)  update(L,R,d,lson);
    if(mid<R)   update(L,R,d,rson);
    pushup(rt);
}void query(ll L,ll R,ll&A,ll&B,ll&C,ll l,ll r,ll rt){
    if(L<=l && r<=R){
        A=a[rt],B=b[rt],C=c[rt]; return;
    }pushdown(l,r,rt);
    ll SA=0,SB=0,SC=0,TA,TB,TC;
    if(L<=mid)  query(L,R,TA,TB,TC,lson), SA+=TA, SB+=TB, SC+=TC;
    if(mid<R)   query(L,R,TA,TB,TC,rson), SA+=TA, SB+=TB, SC+=TC;
    A=SA,B=SB,C=SC;
}inline ll gcd(ll a,ll b){
    return (!b)?a:gcd(b,a%b);
}int main(){ 
    fread(pt,1,5000000,stdin);  ll n,q,u,v,w,TA,TB,TC,A,B,C;
    for(n=getint(),q=getint();q;q--){
        if(getop()=='C'){
            u=getint(),v=getint(),w=getint();
            update(u,v-1,w,root);
        }else{
            u=getint(),v=getint();
            query(u,v-1,TA,TB,TC,root);
            A=(u+v-1)*TB+TA*(v-v*u)-TC;
            B=(v-u+1)*(v-u)>>1;
            C=gcd(A,B);
            print(A/C);*o++='/';print(B/C);*o++='\n';
        }
    }fwrite(buf2,1,o-buf2,stdout);return 0;
}

原来省选题也有裸背包啊、、

if (F[i-1][j]) then F[i][j+c[i]]=F[i][j-c[i]]=1

好了水掉了

#include<cstdio>
int f[52][1005]={0},n,st,ed,c[52];
int main(){
    scanf("%d%d%d",&n,&st,&ed); for(int i=1;i<=n;i++)scanf("%d",&c[i]);
    f[0][st]=1;  for(int i=1;i<=n;i++)   for(int j=0;j<=ed;j++){
        if(!f[i-1][j])  continue;
        if(j+c[i]<=ed)  f[i][j+c[i]]=1;
        if(j-c[i]>=0)   f[i][j-c[i]]=1;
    }int An;    for(An=ed;~An;An--) if(f[n][An]) break; printf("%d\n",An);
}

自己YY出来了？估计应该是比较简单的网络流入门题吧。。

既然每个点(i,j)最多只能通过c[i][j]个蜥蜴。那么很自然地想到拆点。(i,j)→(i,j)'连上容量为c[i][j]的边。(i,j)为入点。(i,j)'为出点。

对于所有有蜥蜴的点，从S给它连一条容量为1的边。对于所有可以跳到外面的点，连到T，容量是c[i][j]。

然后n^4枚举在内部跳来跳去的情况。最后跑网络流就好了。

连T的边的时候我一直在傻×、、一开始算的是到(0,0)的距离≤d、、果然还是太弱了哎、、

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000,maxm=500000,inf=1000000009;
int p[maxm],c[maxm],n1[maxm],q[maxn],h1[maxn],d[maxn],h[maxn],g[maxn],id[25][25];
int S,T,n,m,k,tot=0,cnt=0,N=0;    char s[25];
inline void ae(int x,int y,int z){
    p[tot]=y;   c[tot]=z;   n1[tot]=h[x];   h[x]=tot++;
    p[tot]=x;   c[tot]=0;   n1[tot]=h[y];   h[y]=tot++;
}inline int bfs(){
    memset(d,0xff,sizeof(d));   int r=d[q[0]=S]=0;
    for(int l=0;l<=r;l++)
        for(int k=h[q[l]];~k;k=n1[k])
            if(c[k] && !~d[p[k]])   d[q[++r]=p[k]]=d[q[l]]+1;
    return ~d[T];
}int dfs(int x=S,int lmt=inf){
    if(x==T)    return lmt; int flow;
    for(int &k=g[x];~k;k=n1[k]){
        if(c[k] && d[p[k]]==d[x]+1 && (flow=dfs(p[k],min(lmt,c[k])))){
            c[k]-=flow; c[k^1]+=flow;   return flow;
        }
    }return 0;
}int main(){
    scanf("%d%d%d",&n,&m,&k);   k;   S=0;    T=801;  memset(h,0xff,sizeof(h));
    for(int i=1,j;i<=n;i++) for(scanf("%s",s+1),j=1;j<=m;j++)   if(s[j]-'0'){
        id[i][j]=++cnt;
        ae((id[i][j]<<1)-1,id[i][j]<<1,s[j]-'0');
        if(min(min(i,n-i+1),min(j,m-j+1))<=k)ae(id[i][j]<<1,T,s[j]-'0');
    }for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int ii=1;ii<=n;ii++) for(int jj=1;jj<=m;jj++){
        if(!id[i][j]||!id[ii][jj])  continue;
        if((ii-i)*(ii-i)+(jj-j)*(jj-j)<=k*k)  ae(id[i][j]<<1,(id[ii][jj]<<1)-1,inf);
    }for(int i=1,j;i<=n;i++) for(scanf("%s",s+1),j=1;j<=m;j++) if(s[j]=='L'){
        N++; if(id[i][j])   ae(S,(id[i][j]<<1)-1,1);
    }int An=0,f=0;   while(bfs()){   memcpy(g,h,sizeof(h));  while(f=dfs())  An+=f;}
    printf("%d\n",N-An);    return 0;
}