UOJ Logo root的博客

博客

SwordOJ Senior Test Round #5解题报告

2017-07-14 15:42:20 By root

62. knum(knum.pas/cpp/c) JZOJ100043

看到 “第 K 小”,我们首先把读入的 a,b 两个数组从小到大排一遍序,方便处理。 考虑二分答案,将求值问题转化成判定性问题。 设二分到一个值 mid ,那么前 K 小的数都满足 a[i]∗b[j]<=mid ; 于是我们枚举 i ,算出 j ,得到数的个数,看满不满足 K 的条件。 接着我们如何算出 j 呢?二分?不,这样时间复杂度就是 O(N∗log(MaxNum)∗logN) 。 这复杂度可能遇到常数问题,但我们观察到枚举的 a[i] 是 递增 的(排过序了)。 所以得到的 j 是 单调递减 的(总乘积不变),利用单调性解决即可。 时间复杂度为 O(N∗log(MaxNum)) ,轻松通过。 Code

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=200001;
int n,m;
LL k;
LL a[N],b[N];
inline int read(){
    int X=0,w=1; char ch=0;
    while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}
int main()
{
    n=read(),m=read(),scanf("%lld",&k);
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=m;i++) b[i]=read();
    sort(a+1,a+1+n);
    sort(b+1,b+1+m);
    LL l=1,r=a[n]*b[m];
    while(l<r){
        LL mid=(l+r)>>1,sum=0;
        for(int i=1,x=m;i<=n;i++,sum+=x)
            while(a[i]*b[x]>mid) x--;
        if(sum>=k) r=mid; else l=mid+1;
    }
    printf("%lld",l);
    return 0;
}

63. string(string.pas/cpp/c) JZOJ5220

【参考题解1】dp求lcs很容易,关键是x串的子串只要y有一个对应就贡献1且只贡献1。考虑设g[i][j],x串dp到i,y到j的方案数,加入x串字符时可以直接累加方案数,但需要lcs相同,加入y串字符时不可以累加,同时加入x串字符和y串字符时需要找到y串前j个字符中最后的字符,将这个状态的前一个状态转移到当前状态,即lcs小1的状态。

code

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LF double
#define LL long long
#define ULL unsigned int
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define fr(i,j) for(int i=begin[j];i;i=next[i])
using namespace std;
int max(int x,int y){return (x>y)?x:y;}
int min(int x,int y){return (x<y)?x:y;}
int const mn=1e3+9,mo=1e9+7;
int n,m,f[mn][mn],to[mn][mn],pre[mn],tmp[mn];
LL g[mn][mn];
char a[mn],b[mn];
int main(){
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
    scanf("%s",a+1);n=strlen(a+1);
    scanf("%s",b+1);m=strlen(b+1);
    fo(i,0,n)g[i][0]=1;
    fo(i,0,m)g[0][i]=1;
    fo(i,1,n){
        fo(j,1,m){
            if((i==n)&&(j==m)){
                int bb;
                bb++;
            }
            tmp[b[j]]=j;
            f[i][j]=max(max(f[i][j-1],f[i-1][j]),f[i-1][j-1]+(a[i]==b[j]));
            if(f[i-1][j]==f[i][j])g[i][j]=g[i-1][j];
            if(tmp[a[i]]&&(f[i][j]==f[i-1][tmp[a[i]]-1]+1))
                g[i][j]=(g[i][j]+g[i-1][tmp[a[i]]-1])%mo;
        }
        fo(j,'a','z')tmp[j]=0;
    }
    printf("%lld",g[n][m]);
    return 0;
}

【参考题解2】 Solution 我们设dp[i][j]表示最长公共子序列。正常求。同时我们设f[i][j]表示在满足当前dp[i][j]的情况下前i个x中的子序列有多少是满足是y的子序列。那么我们枚举一下:若当前的子序列中匹配不包括i,那么我们考虑若dp[i-1][j]==dp[i][j],那么f[i][j]+=f[i-1][j]。若当前的子序列中匹配包括i,那么我们考虑i必须被匹配,所以我们在前j个字符中找一个最晚出现的满足s1[p]==s[i]的位置,若dp[i-1][p-1]+1==dp[i][j],那么f[i][j]+=f[i-1][p-1]。 Code

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const ll maxn=1e3+5,mo=1e9+7;
ll f[maxn][maxn],g[maxn][maxn];
char s[maxn],s1[maxn];
ll n,m,i,t,j,k,l,x,y,z,mx;
int main(){
    scanf("%s\n",s+1);scanf("%s\n",s1+1);
    n=strlen(s+1);m=strlen(s1+1);
    for (i=0;i<=m;i++)g[0][i]=1;
    for (i=0;i<=n;i++)g[i][0]=1;
    for(i=1;i<=n;i++){
        x=-1;
        for (j=1;j<=m;j++){
            if (s1[j]==s[i]) x=j;
            f[i][j]=max(max(f[i][j-1],f[i-1][j]),f[i-1][j-1]+(s[i]==s1[j]));
            if (f[i][j]==f[i-1][j]) g[i][j]=g[i-1][j];
            if (x>0 && f[i][j]==f[i-1][x-1]+1) g[i][j]=(g[i][j]+g[i-1][x-1])%mo;
        }
    } 
    printf("%lld\n",g[n][m]);
}

64. city(city.pas/cpp/c) JZOJ5064

题解链接:http://www.cnblogs.com/hiweibolu/p/6727057.html 70分 Kosarajo算法 这是一个区别于tarjan算法的求强连通分量的算法。 流程 1.在逆图上进行一次dfs,然后记录下每个点的后序编号(?)。 e.g.

void dfs(int v){
    dfs(next(v));  //先往后继递归
    st[++st[0]]=v; //再在这记录后序编号
}

2.按后序编号从大到小在原图上再进行一次dfs,所能走到的就是与这个点处于同一强连通分量的点。 3.时间复杂度为O(n+m)O(n+m)

正文 我们看到给出的区间的左端点和右端点都是不减的,就有边只会进出一次。 所以我们可以用邻接矩阵维护边,然后就可以使用Kosarajo算法统计答案。 这样的时间复杂度为O(n2∗q)O(n2∗q),然而这还是过不了70分。 bitset优化 由于边不存在权值,所以我们用bitset来存储邻接矩阵。 然后Kosarajo算法统计答案时,也要用到bitset的位运算优化。 于是就能把复杂度优化到O(132n2∗q)O(132n2∗q); 可能会用到的bitset函数 .reset(),归零; ._Find_next(int v),查找第v为后的第一个1,返回位置。 Warning:bitset的下标是从0开始算,所以如果要从头开始找,就用._Find_next(-1)。 100分 100分与70分的区别就是,边可能会重复加入。 注意到,如果对于两个已有的边集(邻接矩阵),那么我们可以利用bitset来优化合并,达到O(n232)O(n232)的复杂度,是很优秀的。 我们给mm条边分块,共m−−√m块,每个块考虑使用bitset来存储邻接矩阵; 按照一般的分块套路,我们确实可以用O(q∗(m−−√∗n232+m−−√))O(q∗(m∗n232+m))来维护邻接矩阵。 但是仍然无法被题目苛刻的条件所接受。 于是我们考虑对块建立ST表,那么就能把维护的时间降到O(q∗(logm√∗n232+m−−√))O(q∗(logm∗n232+m))。 就能通过本题。

为什么不用tarjan,而用Kosarajo代替 对于tarjan而言,他需要遍历一些已经被访问的点,所以不能使用bitset优化; 而Kosarajo,每个点只会被遍历一次,所以能使用bitset优化。

为什么不用线段树,而用ST表和分块代替 线段树的空间不能被接受,是O(m∗logm∗n232)O(m∗logm∗n232)

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<bitset>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;i++)
#define fd(i,x,y) for(int i=x;i>=y;i--)
using namespace std;
const char* fin="friend.in";
const char* fout="friend.out";
const int inf=0x7fffffff;
const int maxn=157,maxm=300007,maxk=557,maxl=10;
int n,m,q,a[maxm][2],ks,num,st[maxn],cnt=0,pre[maxn],ans;
bitset<maxn> b[maxk][maxl][maxn],bb[maxk][maxl][maxn],bz,p[maxn],pp[maxn];
void make(int l,int r){
    int k=maxl-1;
    fo(i,1,n) p[i].reset(),pp[i].reset();
    while (l<=r){
        if (l+(1<<k)-1<=r){
            fo(i,1,n) p[i]|=b[l][k][i],pp[i]|=bb[l][k][i];
            l+=(1<<k);
        }
        if (k>0) k--;
    }
}
void dfs(int v){
    bz.reset(v);
    while (1){
        int k=(pp[v]&bz)._Find_next(0);
        if (k>n) break;
        dfs(k);
    }
    st[++st[0]]=v;
}
void Dfs(int v){
    cnt++;
    bz.reset(v);
    while (1){
        int k=(p[v]&bz)._Find_next(0);
        if (k>n) break;
        Dfs(k);
    }
}
void kosarajo(){
    ans=0;
    bz.set();
    st[0]=0;
    fo(i,1,n)
        if (bz[i]){
            dfs(i);
        }
    bz.set();
    fd(i,st[0],1){
        if (bz[st[i]]){
            cnt=0;
            Dfs(st[i]);
            ans+=cnt*(cnt-1)/2;
        }
    }
}
int main(){
    freopen(fin,"r",stdin);
    freopen(fout,"w",stdout);
    scanf("%d%d%d",&n,&m,&q);
    fo(i,1,m) scanf("%d%d",&a[i][0],&a[i][1]);
    ks=int(sqrt(m));
    int j=1,k=ks;
    fo(i,1,m){
        if (i>k){
            k+=ks;
            j++;
        }
        b[j][0][a[i][0]].set(a[i][1]);
        bb[j][0][a[i][1]].set(a[i][0]);
    }
    num=j;
    fd(i,num,1){
        fo(j,1,maxl-1){
            if (i+(1<<(j-1))>num) break;
            fo(k,1,n){
                b[i][j][k]=b[i][j-1][k]|b[i+(1<<(j-1))][j-1][k];
                bb[i][j][k]=bb[i][j-1][k]|bb[i+(1<<(j-1))][j-1][k];
            }
        }
    }
    fo(i,1,q){
        int l,r;
        scanf("%d%d",&l,&r);
        int tmp=(l-1)/ks+1,tmd=(r-1)/ks+1;
        make(tmp+1,tmd-1);
        if (tmp!=tmd){
            fo(j,l,tmp*ks) p[a[j][0]].set(a[j][1]),pp[a[j][1]].set(a[j][0]);
            fo(j,(tmd-1)*ks+1,r) p[a[j][0]].set(a[j][1]),pp[a[j][1]].set(a[j][0]);
        }else fo(j,l,r) p[a[j][0]].set(a[j][1]),pp[a[j][1]].set(a[j][0]);
        /*fo(i,1,n) cout<<p[i]<<endl;
        fo(i,1,n) cout<<pp[i]<<endl;*/
        kosarajo();
        printf("%d\n",ans);
    }
    return 0;
}

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。