首页 > 代码库 > 2017-4-9四校联考

2017-4-9四校联考

T2结论推得有点问题结果只有30,T3暴力骗了40,170/300

 

T1.交易

题目大意:一个人从0走到m,走1要1s,路上有n个点xi,每个点必须被经过2次,第二次要在第一次的ts之后经过才算数,求最少时间。(n<=3,000,000,0<xi<m<=10^9)

思路:f[i]表示完成前i个点后到达第i个点的最小时间,每次回头显然必须完成所有之前未完成的点,故有f[i]=min(f[j]+x[i]-x[j]+max(2*(x[i]-x[j+1]),t)),把max分开讨论,当2*(x[i]-x[j+1])<=t时,我们记最小的f[j]-x[j]-2*x[j+1]即可,2*(x[i]-x[j+1])>t时,显然只要考虑最左边的点(本人比较菜,写了单调队列),然后就O(n)了。

#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
char B[1<<15],*S,*T,C;int X;
#define getc() (S==T&&(T=((S=B)+fread(B,1,1<<15,stdin)),S==T)?0:*S++)
inline int read()
{
    while((C=getc())<0||C>9);
    for(X=C-0;(C=getc())>=0&&C<=9;)X=X*10+C-0;
    return X;
}
#define MN 3000000
#define INF (1LL<<60)
int x[MN+5],q[MN+5],ql,qr;
ll f[MN+5],mn=INF;
int main()
{
    freopen("trade.in","r",stdin);
    freopen("trade.out","w",stdout);
    int n,m,t,i,j;
    n=read();m=read();t=read();
    for(i=1;i<=n;++i)x[i]=read();
    for(i=1,j=0;i<=n;++i)
    {
        for(;(x[i]-x[j+1])<<1>=t;++j)
        {
            mn=min(mn,f[j]-(x[j+1]<<1)-x[j]);
            if(ql<=qr&&j==q[ql])++ql;
        }
        f[i]=min(3LL*x[i]+mn,x[i]+t+(ql<=qr?f[q[ql]]-x[q[ql]]:INF));
        while(ql<=qr&&f[i]-x[i]<=f[q[qr]]-x[q[qr]])--qr;
        q[++qr]=i;
    }
    printf("%I64d",f[n]+m-x[n]);
    fclose(stdin);fclose(stdout);return 0;
}

 

T2.字符串

题目大意:给定两个长度为n的字符串S和T,一次变换定义为从左到右,每次令s[i]变成s[i]或s[i-1],问S变成T至少需要几次变换。(n<=3,000,000)

思路:显然从后往前,每次找到S[k[i]]=T[i]且k[i]<=i,k[i]<=k[j](j>i),令T[i]由S[k[i]]变换到最优,考虑计算这么做的最小耗时,用x[i]表示第i格在前x[i]次操作都被占用了,动态计算x[i],最大值就是答案,每次k[i]减小时,我们要用S[k[i]]从k[i]染到i,那么有x[j]=max(x[j],x[j+1])+1(k[i]<=j<i),x[i]=x[i]+1,又由于x[j]不会超过x[j+1],故x[j]=x[j+1]+1(k[i]<=j<i),相当于每次把数组左移一位(小于k[i]都为0,左移无影响,大于i不用考虑)并区间加1,我们用变量记下现在左移了多少位并记下差分即可,总复杂度O(n)。

#include<cstdio>
#include<algorithm>
using namespace std;
#define MN 3000000
char a[MN+5],b[MN+5];
int f[MN+5];
int solve()
{
    int n,i,j,s=0,p=0,ans=0;
    scanf("%d%s%s",&n,a+1,b+1);
    for(i=j=n;i;--i)
    {
        if(j>i&&a[i]!=b[i])j=i;
        if(j<=i&&a[j]!=b[i])
        {
            while(j&&a[j]!=b[i])--j;
            if(!j)return 0*puts("-1");
            ans=max(ans,++s);++f[++p+j];
        }
        s-=f[p+i];f[p+i]=0;
    }
    printf("%d",ans);
}
int main()
{
    freopen("string.in","r",stdin);
    freopen("string.out","w",stdout);
    solve();
    fclose(stdin);fclose(stdout);return 0;
}

 

T3.矩阵

题目大意:一个n*n的矩阵,给出m个黑格,其他全是白的,每次若(x,y)和(y,z)都是黑的,可以把(z,x)染成黑的,问最多染出多少个黑格。(n,m<=1,000,000)

思路:结论题。把这个矩阵当成邻接矩阵,题目转化n个点m条边的有向图,为若x到y有边且y到z有边,z到x也有边,问有多少条边。每个弱联通块独立,分开考虑,对这个联通块染色,染成0,1,2,满足若u到v有边,则$c[u]+1\equiv c[v]\ (mod\ 3)$,如果染色成功且三个颜色都有,那么所有0到所有1有边,所有1到所有2有边,所有2到所有0有边,因为若只有三个点,其中0到1,1到2,那么这三个点显然满足,每次加入一个点连到已有的图中,仍然满足,故由归纳法可证;若只有两个或一个颜色,显然不可能出现新的边。如果染色失败,与上面同一种思路可用归纳法证明,所有点到所有点都有连边,包括自环。然后随便写写就O(n)了。

#include<cstdio>
char B[1<<15],*S,*T,C;int X;
#define getc() (S==T&&(T=((S=B)+fread(B,1,1<<15,stdin)),S==T)?0:*S++)
inline int read()
{
    while((C=getc())<0||C>9);
    for(X=C-0;(C=getc())>=0&&C<=9;)X=X*10+C-0;
    return X;
}
#define MN 1000000
struct edge{int nx,t;}e[MN*2+5];
int h[MN+5],en,c[MN+5],o,s,f[4];
inline void ins(int x,int y)
{
    e[++en]=(edge){h[x],y};h[x]=en;
    e[++en]=(edge){h[y],x};h[y]=en;
}
void dfs(int x)
{
    ++f[c[x]];
    for(int i=h[x],p;i;i=e[i].nx,++s)
    {
        p=(c[x]+2+(i&1?1:-1))%3+1;
        if(!c[e[i].t])c[e[i].t]=p,dfs(e[i].t);
        else if(c[e[i].t]!=p)o=1;
    }
}
int main()
{
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    int n,m,i;long long ans=0;
    n=read();m=read();
    while(m--)i=read(),ins(i,read());
    for(i=1;i<=n;++i)if(!c[i])
    {
        o=f[1]=f[2]=f[3]=s=0;
        c[i]=1;dfs(i);
        if(o)ans+=1LL*(f[1]+f[2]+f[3])*(f[1]+f[2]+f[3]);
        else if(f[1]&&f[2]&&f[3])ans+=1LL*f[1]*f[2]+1LL*f[2]*f[3]+1LL*f[3]*f[1];
        else ans+=s>>1;
    }
    printf("%I64d",ans);
    fclose(stdin);fclose(stdout);return 0;
}

 

2017-4-9四校联考