QZ-10.18,10.19-J/S

Posted on By 张, 高畅 QZ-10.18,10.19-J/S无评论

众所周知，同时报名J/S组的每天都有两套题要改/打。
于是前两天的BLOG就一起写了……

DAY 1

真是令人爆0的一天。

井字棋

作为不负责的验题人，这题实际上在CQ的时候就验过。
的确非常不容易往抽屉原理那方面想。
不过就算可能知道抽屉原理还是会挂分。
CODE:

#include
using namespace std;
const int N=1e3+5;
int n,cnth[26],cntl[N][26],cnt,flags[N];
char str[N];
int main()
{
    scanf("%d",&n);
    if(n>26)
    {
        puts("N0");
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%s",str+1);
        int flag=0;
        for(int j=0;j=2&&!flags[j])
            {
                cnt++;
                flags[j]=1;
            }
        }
        if(!flag)
        {
            puts("YE5");
            return 0;
        }
    }
    if(cnt==n)
    {
        puts("N0");
        return 0;
    }
    puts("YE5");
    return 0;
}

校门前的地砖

？可能第一次出现T2比T1简单的情况，毕竟这题相较于T1，实在是良心太多了。
画一个图，很显然能走到的格子是类似两个等腰直角三角形。
CODE:

#include
using namespace std;
const int N=1e3+5;
typedef long long LL;
LL a,b,c,d;
int checkl(LL a,LL b,LL c,LL d)
{
    if(c<=a&&b<=d&&a-c<=d-b)return 1;
    else return 0;
}
int checkr(LL a,LL b,LL c,LL d)
{
    if(a<=c&&b<=d&&c-a<=d-b)return 1;
    else return 0;
}
void work()
{
    scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
    if((a+b)%2)//向右拓展 
    {
        if(checkr(a,b,c,d)||checkl(a,b+1,c,d))printf("T");
        else printf("F");
    }
    else//向左拓展 
    {
        if(checkl(a,b,c,d)||checkr(a,b+1,c,d))printf("T");
        else printf("F");
    }
    if(b==d)puts(" 1");
    else printf(" %lld\n",2*(d-b));
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)work(); 
    return 0;
}

完全二叉树

找规律。
根据二叉树基本知识，y=log_2(n)+1
接下来考虑x。
首先我们知道，对于偶数节点的树，我们删掉最后一个点，不影响树根的坐标。
把这个点删掉。
最后一层会有cntq=n-((2^h)-1),h=log_2(n)个节点
因此，倒数第二层有编号的节点数cntl=(2^h-cntq)\div 2。
答案：(1+…+cntq)\div 2^h+(cntq+1)…..+(cntq+cntl+1)\div(2^(h-1))
CODE:

#include
using namespace std;
double get(int x)
{
    int high=__lg(x);
    int cnt_q=x-((1<<high)-1);
    int cnt_b=(1<<high)-cnt_q;//构造满
    int cnt_l=cnt_b/2;//实际上
    //ans=1+....+cntq/(1<<high)/ + /(cntq+1).....+(cntq+cntl)/(1<<(high-1))
    double sum=1.0*cnt_q*(cnt_q+1)/2;
    double csum=1.0*(cnt_q+cnt_l)*(cnt_q+cnt_l+1)/2;
    return 1.0*sum/(1<<high)+1.0*(csum-sum)/(1<<(high-1));
}
void work()
{
    int n;
    scanf("%d",&n);
    if(n==1)
    {
        printf("%.8lf %.8lf\n",1.0,1.0);
        return;
    }
    int mfloor=__lg(n);
    int y=mfloor+1;
    if(!(n%2))n--;//向下悬挂节点，没有必要留下
    printf("%.8lf %.8lf\n",get(n),1.0*y);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)work();
    return 0;
}

变速带

第一问的DP是显然的。
然后QR开始质问我为什么没有往这个DP式子上想。
我只觉得我是**
第二问，我们将k换成q做一遍DP，再换成q-1再做一遍，然后把两个答案相减。
滚动优化其实无所谓，数据放的很水。
CODE:

#include
using namespace std;
const int N=1005,S=9000,mod=998244353;
typedef long long LL;
int n;
int f[N][S];
void DP(int limit)
{
    memset(f,0,sizeof f);
    f[0][1]=1;
    for(int i=0;i<n;i++)
    {
        for(int j=1;j=1)f[i+1][j-1]=(f[i+1][j-1]+f[i][j])%mod;
            if(j+1=1)f[i+2][j/2]=(f[i+2][j/2]+f[i][j])%mod;
            if(j*2<=limit)f[i+2][j*2]=(f[i+2][j*2]+f[i][j])%mod;
        }
    }
}
int k,p,q;
int main()
{
    scanf("%d%d%d%d",&n,&k,&p,&q);
    DP(k);
    printf("%d ",f[n][p]);
    DP(q);
    int res1=0,res2=0;
    for(int i=1;i<=q;i++)res1=(res1+f[n][i])%mod;
    DP(q-1);
    for(int i=1;i<q;i++)res2=(res2+f[n][i])%mod;
    printf("%d",((res1-res2)%mod+mod)%mod);
    return 0;
}

运输计划

首先，路径由于是确定的，因此我们倍增求LCA。
求完LCA之后，我二分确认答案。
在二分的check函数中，我们每次检查每一个任务是否满足要求。
如果没有，树上查分把他们记录下来，再一遍前缀和还原。
然后检查是不是有边>=要减的数，随后返回值。
CODE:

#include
using namespace std;
typedef pairPII;
const int N=300005,M=600005;
int n,m;
int h[N],e[M],w[M],ne[M],idx;
int dist[N],d[N],fa[N][25],dfn[N],timestamp;
int par[N],sum[N];
PII tr[N];
void add(int a,int b,int c){e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;}
void dfs(int u,int father)
{
    dfn[++timestamp]=u;
    d[u]=d[father]+1;
    fa[u][0]=father;
    for(int j=1;j<=20;j++)fa[u][j]=fa[fa[u][j-1]][j-1];
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j==father)continue;
        dist[j]=dist[u]+w[i];
        dfs(j,u);
    }
}
int LCA(int a,int b)
{
    if(d[a]=d[b])a=fa[a][i];
    }
    if(a==b)return a;
    for(int i=20;~i;i--)
    {
        if(fa[a][i]!=fa[b][i])
        {
            a=fa[a][i];
            b=fa[b][i];
        }
    }
    return fa[a][0];
}
int check(int mid)
{
    memset(sum,0,sizeof sum);
    int md=0,ms=0;
    for(int i=1;imid)
        {
            sum[x]++;
            sum[y]++;
            sum[p]-=2;
            md=max(md,d-mid);
            ms++;
        }
    }
    if(!ms)return 1;
    for(int i=n;i;i--)sum[fa[dfn[i]][0]]+=sum[dfn[i]];
    for(int i=1;i=md)return 1;
    }
    return 0;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1,0);
    for(int i=1;i1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    printf("%d",l);
    return 0;
}

子串

为什么是DP(悲)
我觉得我的DP连初学者都不如。
只会点记忆化。
设f(i,j,k)为从A’中，顺序取k个不重复子串，首尾相接后与B’相等的方案数，
用滚动数组优化一维，然后前缀和维护。

#include
using namespace std;
typedef long long LL;
const int N=1005,mod=1e9+7;
int n,m,s;
char a[N],b[N];
LL f[N][N],sum[N][N];
int main()
{
    scanf("%d%d%d%s%s",&n,&m,&s,a+1,b+1);
    f[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j;j--)
        {
            for(int k=s;k;k--)
            {
                if(a[i]==b[j])sum[j][k]=sum[j-1][k]+f[j-1][k-1];
                else sum[j][k]=0;
                f[j][k]=(f[j][k]+sum[j][k])%mod;
            }
        }
    }
    printf("%lld",f[m][s]);
    return 0;
}

天天爱跑步

和上面的挺像的。
先倍增求LCA，然后开两个桶，分别记录S->LCA,LCA->T的贡献。

#include
using namespace std;
const int N=300005,M=600005;
int n,m,w[N],t1[M],t2[M],res[N];
int h[N],e[M],ne[M],idx;
int d[N],fa[N][30],cnt[N];
vectorG1[N],G2[N];
struct node
{
    int s,t,lca,dist;
}q[N];
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void dfs1(int u,int father)
{
    d[u]=d[father]+1;
    fa[u][0]=father;
    for(int j=1;j<=25;j++)fa[u][j]=fa[fa[u][j-1]][j-1];
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j==father)continue;
        dfs1(j,u);
    }
}
int LCA(int a,int b)
{
    if(d[a]=d[b])a=fa[a][i];
    }
    if(a==b)return a;
    for(int i=25;~i;i--)
    {
        if(fa[a][i]!=fa[b][i])
        {
            a=fa[a][i];
            b=fa[b][i];
        }
    }
    return fa[a][0];
}
void dfs2(int u)
{
    int x=t1[w[u]+d[u]],y=t2[w[u]-d[u]+N];
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j==fa[u][0])continue;
        dfs2(j);
    }
    t1[d[u]]+=cnt[u];
    for(auto j:G1[u])t2[q[j].dist-d[q[j].t]+N]++;
    res[u]+=t1[w[u]+d[u]]-x+t2[w[u]-d[u]+N]-y;
    for(auto j:G2[u])
    {
        t1[d[q[j].s]]--;    
        t2[q[j].dist-d[q[j].t]+N]--;
    }
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    dfs1(1,0);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&q[i].s,&q[i].t);
        cnt[q[i].s]++;
        q[i].lca=LCA(q[i].s,q[i].t);
        q[i].dist=d[q[i].s]+d[q[i].t]-2*d[q[i].lca];
        G1[q[i].t].push_back(i);
        G2[q[i].lca].push_back(i);
        if(d[q[i].lca]+w[q[i].lca]==d[q[i].s])res[q[i].lca]--;
    }
    dfs2(1);
    for(int i=1;i<=n;i++)printf("%d ",res[i]);
    return 0;
}

魔法阵

数学，推式子，优化。

#include
using namespace std;
const int N=40005;
int n,m,sum,a[N],st[N],res[N][5];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&a[i]);
        st[a[i]]++;
    }
    for(int t=1;t*9<n;t++)
    {
        sum=0;
        for(int D=9*t+2;D<=n;D++)
        {
            int A=D-9*t-1;
            int B=D-7*t-1;
            int C=D-t;
            sum+=st[A]*st[B];
            res[C][3]+=st[D]*sum;
            res[D][4]+=st[C]*sum;   
        }
        sum=0;
        for(int A=n-9*t-1;A;A--)
        {
            int B=A+2*t;
            int C=B+6*t+1;
            int D=A+9*t+1;
            sum+=st[C]*st[D];
            res[A][1]+=st[B]*sum;
            res[B][2]+=st[A]*sum;   
        }
    }
    for(int i=1;i<=m;i++)printf("%d %d %d %d\n",res[a[i]][1],res[a[i]][2],res[a[i]][3],res[a[i]][4]);
    return 0;
}

DAY 2

J太水了就不写了。

道路游戏

单调队列优化DP。
原来的方程显然非常好推，而且好写（然而似乎并不是）。
（而且原来的方程也可以直接通过，无需优化）。

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,p,s[N][N],cost[N],f[N],g[N][N];
struct node
{
    int v,i,j;
    node(int x,int y,int z)
    {
        v=x;
        i=y;
        j=z;
    }
    bool operator<(const node&W)const
    {
        return v<W.v;
    }
};
priority_queue<node>q[N];
int get(int x)
{
    x%=n;
    if(x<=0)x+=n;
    return x;
}
int main()
{
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)scanf("%d",&s[i][j]);
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(j==1)s[j][i]+=s[n][i-1];
            else s[j][i]+=s[j-1][i-1];
        }
    }
    memset(f,-0x3f,sizeof f);
    memset(g,-0x3f,sizeof g);
    f[0]=0;
    for(int i=1;i<=n;i++)scanf("%d",&cost[i]);
    for(int i=1;i<=n;i++)
    {
        g[0][i]=-cost[get(i+1)];
        q[get(0-i)].push(node(g[0][i],0,i));
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            priority_queue<node>&h=q[get(i-j)];
            while(h.size())
            {
                node t=h.top();
                if(i-p>t.i)h.pop();
                else
                {
                    f[i]=max(f[i],s[j][i]+t.v);
                    break;
                }
            }
        }
        for(int j=1;j<=n;j++)
        {
            g[i][j]=f[i]-s[j][i]-cost[get(j+1)];
            q[get(i-j)].push(node(g[i][j],i,j));
        }
    }
    int res=0;
    for(int i=0;i<=m;i++)res=max(res,f[i]);
    printf("%d",res);
    return 0;
}

解方程

具体的方法请移步这里
我们发现，实际上如果不想写高精度（实际上也不能写）的话，我们就只能考虑hash的思想。
选取1个到2个的大模数，并依照秦九韶算法来算，可以优化复杂度。
但是就算这样最后一个点还是跑了100s(不是ms)

#include<bits/stdc++.h>
using namespace std;
const int N=105,M=10005,mod=998244353;
typedef long long LL;
int n;
LL a[N];
vector<LL>res;
int check(LL x)
{
    LL sum=0;
    for(int i=n;i;i--)sum=((a[i]+sum)*x)%mod;
    sum=(sum+a[0])%mod;
    return !sum;
}
int main()
{
//  freopen("equation.in","r",stdin);
//  freopen("equation.out","w",stdout);
    int m;
    char str[M];
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++)
    {
        scanf("%s",str+1);
        int nn=strlen(str+1);
        LL ans=0;
        for(int j=1;j<=nn;j++)
        {
            if(&#039;0&#039;<=str[j]&&str[j]<=&#039;9&#039;)ans=(10LL*ans+(str[j]-&#039;0&#039;))%mod;
        }
        if(str[1]==&#039;-&#039;)ans*=-1;
        a[i]=ans;
    }
    for(LL i=1;i<=m;i++)
    {
        if(check(i))res.push_back(i);
    }
    printf("%d\n",res.size());
    for(auto item:res)printf("%lld\n",item);
    return 0;
}

换教室

为什么都是DP！
(瘫倒)
首先我们一个floyd预处理路径长度，再一个DP。
设dp(i,j,0/1)表示走完前i个教室，换了j个教室，当前换不换教室.

#include<bits/stdc++.h>
using namespace std;
const int N=2005;
const double INF=1e9;
int s,num,n,m;
int dist[N][N];
double res=INF,k[N],f[N][N][2];
pair<int,int>c[N];
#define x first
#define y second
int main()
{
    scanf("%d%d%d%d",&s,&num,&n,&m);
    memset(dist,0x3f,sizeof dist);
    for(int i=1;i<=s;i++)scanf("%d",&c[i].x);
    for(int i=1;i<=s;i++)scanf("%d",&c[i].y);
    for(int i=1;i<=s;i++)scanf("%lf",&k[i]);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        dist[a][b]=dist[b][a]=min(dist[a][b],c);
    }
    for(int i=1;i<=n;i++)dist[0][i]=dist[i][0]=dist[i][i]=0;
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
        }
    }
    for(int i=0;i<=s;i++)
    {
        for(int j=0;j<=num;j++)f[i][j][0]=f[i][j][1]=INF;
    }
    f[1][0][0]=f[1][1][1]=0;
    for(int i=2;i<=s;i++)
    {
        f[i][0][0]=f[i-1][0][0]+dist[c[i-1].x][c[i].x];
        for(int j=1;j<=min(i,num);j++)
        {
            f[i][j][0]=min(f[i][j][0],min(f[i-1][j][0]+dist[c[i-1].x][c[i].x],f[i-1][j][1]+dist[c[i-1].x][c[i].x]*(1.0-k[i-1])+dist[c[i-1].y][c[i].x]*k[i-1]));
            f[i][j][1]=min(f[i][j][1],min(f[i-1][j-1][0]+dist[c[i-1].x][c[i].x]*(1.0-k[i])+dist[c[i-1].x][c[i].y]*k[i],
            f[i-1][j-1][1]+dist[c[i-1].y][c[i].y]*k[i]*k[i-1]+dist[c[i-1].y][c[i].x]*k[i-1]*(1.0-k[i])+dist[c[i-1].x][c[i].y]*(1.0-k[i-1])*k[i]+dist[c[i-1].x][c[i].x]*(1-k[i-1])*(1.0-k[i])));
        }
    }
    for(int i=0;i<=num;i++)res=min(res,min(f[s][i][0],f[s][i][1]));
    printf("%.2lf",res);
    return 0;
}
训练日志

发表回复