8.11 NOIP模拟测试17 入阵曲+将军令+星空

T1 入阵曲

前缀和维护可以得60分 f[x1][y1][x2][y2]=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]; O（n4）

如果同一行的两个前缀和在模k意义下相等，那么他们之间的数的和一定是k的整数倍。把余数拿桶存起来，每次查询之前相同余数的有几个，直接加上。把一行拓展成许多行。

枚举矩阵的左右端点，中间的连续几列压成一列，（然后可以把纸旋转90°）就跟一行的一样了。复杂度O（n3）

需要注意的一点是初始化桶t[0]=1 因为如果这一整块本来就在模k意义下为0，用前缀和求这一段的和需要q[x]-q[0]，而q[0]=0，需要把他也放进去。

桶里的东西怎么放进去的怎么拿出来。

ans要开long long

#include<iostream>

#include<cstring>

#include<cstdio>

#define ll long long

using namespace std;

int n,m,k,a[][],sum[][],t[],q[];

ll ans;

int read()

{

    int aa=,bb=;char cc=getchar();

    while(cc>''||cc<''){if(cc=='-') bb=-;cc=getchar();}

    while(cc<=''&&cc>=''){aa=(aa<<)+(aa<<)+(cc^);cc=getchar();}

    return aa*bb;

}

int main()

{

    n=read();m=read();k=read();

    for(int i=;i<=n;i++){

        for(int j=;j<=m;j++){

            a[i][j]=read()%k;

            sum[i][j]=(sum[i][j-]+a[i][j])%k;

        }

    }

    for(int i=;i<=m;i++){

        for(int j=i;j<=m;j++){

            q[]=;t[q[]]=;

            for(int l=;l<=n;l++){

                q[l]=(q[l-]+sum[l][j]-sum[l][i-]+k)%k;

                ans+=t[q[l]];

                t[q[l]]++;

            }

            for(int l=;l<=n;l++) t[q[l]]=;

        }

    }

    printf("%lld\n",ans);

    return ;

}

入阵曲

T2 将军令

贪心

找到深度最深的节点，向上找距离他为k的节点，没有就是根，在这驻扎一定优于在这下面的节点，因为越往上他的拓展性越强。

所以每次找到没有被控制的最深的节点，向上找到能控制他且距离最远的祖先，控制他，祖先点亮造成的其他儿子被控制，直接dfs找到并标记，统计答案。

每次贪心的题都不会太难，难的是能想到贪心并且正确实现。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<vector>

#include<algorithm>

using namespace std;

struct node

{

    int to,nxt;

}h[];

int n,k,t,tot,ans,nxt[],dep[],f[];

priority_queue< pair<int,int> >q;

bool vis[],flag;

vector<int>ve[];

void add(int x,int y)

{

    h[++tot].to=y;

    h[tot].nxt=nxt[x];

    nxt[x]=tot;

}

void dfs(int x)

{

    for(int i=nxt[x];i;i=h[i].nxt){

        int y=h[i].to;

        if(dep[y]) continue;

        dep[y]=dep[x]+;

        q.push(make_pair(dep[y],y));

        f[y]=x;

        dfs(y);

    }

}

void dfs1(int x,int d,int fa)

{

    if(d>=k) return;

    for(int i=nxt[x];i;i=h[i].nxt){

        int y=h[i].to;

        if(y==fa) continue;

        vis[y]=;

        dfs1(y,d+,x);

    }

}

int main()

{

    scanf("%d%d%d",&n,&k,&t);

    int u,v;

    for(int i=;i<=n-;i++){

        scanf("%d%d",&u,&v);

        add(u,v);

        add(v,u);

    }

    q.push(make_pair(,));

    dep[]=;

    dfs();

    while(q.size()){

        int d=q.top().first,x=q.top().second;

        q.pop();

        if(!vis[x]){

            int fa=x;

            for(int i=;i<=k;i++){

                if(fa==) break;

                fa=f[fa];

            }

            vis[fa]=;

            dfs1(fa,,);

            ans++;

        }

    }

    printf("%d\n",ans);

    return ;

}

将军令

T3 星空

卡了一下午，有点难过

把亮不亮抽象成01串，没点亮为1，点亮为0（反过来不好做）。区间取反可以用差分单点修改。c[i]=a[i]^a[i+1] c数组为差分数组，下标从0开始。

我们要的最终状态是所有灯都点亮，即全部为0，对应到差分数组上也是全部为0。

因为一共有k个没被点亮，和左边的0会在差分数组里得到一个1，右边同理也会得到一个。所以差分数组里最多有2*k个1。

区间翻转操作在差分数组里就变成了单点修改。翻转[2,4]，就是单点修改1和4。

下面的操作均在差分数组上进行

假设我们操作的区间的端点是0和1，把0变成1，1变成0，及相当于1跳了b[i]的距离去找了0，代价为1;如果两个1相遇了，那么就全部翻转，全部变为0（消没了）。所以这就是1跳一跳去找另一个1的问题。。。

考虑在序列上建边，每个点跑b[i]的距离能到达哪，跑最短路。

剩下的就是状压了，把2*k个1状压，看那两个点匹配去消除。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<vector>

#include<queue>

using namespace std;

struct node

{

    int to,nxt;

}h[];

int n,k,m,a[],b[],c[],tot,nxt[],dis[][],cnt,f[(<<)+],pos[(<<)+];

vector<int>ve;

bool vis[];

int lowbit(int x)

{

    return x&(-x);

}

void add(int x,int y)

{

    h[++tot].to=y;

    h[tot].nxt=nxt[x];

    nxt[x]=tot;

}

int read()

{

    int aa=,bb=;char cc=getchar();

    while(cc>''||cc<''){if(cc=='-') bb=-;cc=getchar();}

    while(cc<=''&&cc>=''){aa=(aa<<)+(aa<<)+(cc^);cc=getchar();}

    return aa*bb;

}

void dj(int p)

{

    memset(vis,,sizeof(vis));

    queue<int> q;

    dis[p][ve[p]]=;

    vis[ve[p]]=;

    q.push(ve[p]);

    while(q.size()){

        int x=q.front();q.pop();vis[x]=;

        for(int i=nxt[x];i;i=h[i].nxt){

            int y=h[i].to;

            if(dis[p][y]>=dis[p][x]+){

                dis[p][y]=dis[p][x]+;

                if(!vis[y]){

                    vis[y]=;

                    q.push(y);

                }

            }

        }

    }

}

int main()

{

    memset(dis,0x3f,sizeof(dis));

    memset(f,0x3f,sizeof(f));

    n=read();k=read();m=read();

    int cc;

    for(int i=;i<=k;i++){

        cc=read();

        a[cc]=;

    }

    for(int i=;i<=m;i++) b[i]=read();

    for(int i=;i<=n;i++){

        c[i]=a[i]^a[i+];

        if(c[i]) ve.push_back(i);

    }

    for(int i=;i<=n;i++){

        for(int j=;j<=m;j++){

            if(i-b[j]>=) add(i,i-b[j]);

            if(i+b[j]<=n) add(i,i+b[j]);

        }

    }

    cnt=ve.size();

    for(int i=;i<=cnt;i++) pos[<<i]=i;

    for(int i=;i<cnt;i++) dj(i);

    cnt=(<<cnt)-;

    f[cnt]=;

    for(int i=cnt;i>=;i--){

        for(int j=i;j;j-=lowbit(j)){

            int x=lowbit(j);

            for(int l=j-x;l;l-=lowbit(l)){

                int y=lowbit(l);

                f[i-x-y]=min(f[i-x-y],f[i]+dis[pos[x]][ve[pos[y]]]);

            //    cout<<i-x-y<<" "<<pos[x]<<" "<<pos[y]<<" "<<dis[pos[y]]<<" "<<f[i]<<" "<<f[i-x-y]<<endl;

            }

        }

    }

    printf("%d\n",f[]);

    return ;

}

星空

出题人好像很喜欢五月天的样子。。。

巴特西

8.11 NOIP模拟测试17 入阵曲+将军令+星空

最新文章

热门文章