noip模拟10
阅读原文时间:2021年10月07日阅读:1

被打回原形了emmmmm

贴张图吧,展示一下根本不行的水平

考试经过

上来浏览一遍T1到T3,读懂题之后发现都不是很可做

T1上了想到了前缀和,往矩阵快速幂想了一下觉得不可做,半小时之后还是只会\(n_4\)的暴力,然后调了半天暴力。。。

事实上这个题在我的洛谷推荐上,我还点进去过,可惜没仔细看……

T2想了一下先想的是贪心,觉得不太对就没打,后来发现树形dp有一万分,果断开打,\(k=1\)调了大概一个小时,由于不认为自己能打对\(k=2\)就没打,特殊性质也没管,事后发现贪心就是正解,嘎

T3根本不会,狂打特判骗分,然后回去看T1,推了个特殊性质,之后就没啥实质性操作了

出分65+45+0=110,再次归于平庸

T3白给的第一个点忘了\(return 0\),答案小于4我直接输出4,真就一分不得

T1.入阵曲

\(n_4\)暴力很显然,关键是怎么优化

前缀和肯定还是有的,推一些其他的性质

如果我们把问题简化到一维,那么现在我们已经有了前缀和,那么一个矩形就是两个前缀和相减,一个关键的操作出现了:

取模.

我们把前缀和对k取模,注意到只有两个余数相同的数才有相减模k是0,也就是k的倍数,那么问题就转化成了对于每个余数统计出现的次数,解决

扩展到二维依然是这个思路,我们用循环枚举列数,用一维的思想处理每个行,最多只有\(n^2/2\)行,暴力统计即可,\(n_3\)过400没问题

一个细节是统计的时候,朴素的统计方法是对每个余数出现的次数x,累加\(n\times(n-1)/2\),但这样涉及到反复查找和清空的问题,用哈希表或者stl都会浪费大量时间,一个好的做法是把这个式子拆成等差数列,每次遇到,先更新答案再累加cnt值,就可以保证复杂度了

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[500][500],b[500][500],c[500][500],d[500][500];
int n,m,kk;
inline int get(int x1,int y1,int x2,int y2)
{
    return d[x2][y2]-d[x1-1][y2]-d[x2][y1-1]+d[x1-1][y1-1];
}
int f[1000005];
stack <int> s;
signed main()
{
 //   freopen("data.out","r",stdin);
    cin>>n>>m>>kk;
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
      scanf("%lld",&a[i][j]);
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
      b[i][j]=b[i][j-1]+a[i][j];
    for(int i=1;i<=m;i++)
     for(int j=1;j<=n;j++)
      c[i][j]=c[i][j-1]+b[j][i];
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
      d[i][j]=c[j][i];
    int ans=0;
    for(int i=1;i<=n;i++)
     for(int j=1;j<=i;j++)
     {
        f[0]=1;
        for(int k=1;k<=m;k++)
        {
            int p=get(j,1,i,k)%kk;
            ans+=f[p];f[p]++;s.push(p);
        }
        while(!s.empty())
        {
            f[s.top()]=0;
            s.pop();
        }
     }
    cout<<ans;
    return 0;
}

注意0比较特殊,本身就能贡献答案,所以要先加1,清空最好用个栈,避免不必要浪费

一定要开\(longlong\),不然会死

T2.将军令

树形dp可以分别过1,2,3,越往后越复杂,感觉考场写出2就了不起了,(其实最多到4),但是这个有通用dp,详见树形dp强者Yubai

其实正解是个贪心,对于最深的点,控制它的最优方案一定是驻扎在他的k级祖先,理解一下,如果往上就看不住他了,往下的话,相当于哨兵的一部分守卫半径浪费了,也一定不会更优,所以这个贪心是对的

那么事情就变得简单了,按深度从大到小,依次看它有没有被看守,如果没有,就在它的k级祖先驻扎,然后通过暴力修改它周边点的状态,复杂度是\(kn\)的,搜索祖先时可以记忆化,不过貌似更慢,修改状态的时候用一个临时数组标记一下,防止重复造成死循环

#include <bits/stdc++.h>
using namespace std;
struct node{
    int from,to,next;
}a[200005];
int head[100005],mm=1;
inline void add(int x, int y)
{
    a[mm].from=x;a[mm].to=y;
    a[mm].next=head[x];head[x]=mm++;
}
int n,k,t;
bool v[100005];int d[100005];
bool l[100005];
queue <pair<int,int> > q;
inline int getk(int x,int p)
{
    if(p==0)return x;
    for(int i=head[x];i;i=a[i].next)
    {
        int y=a[i].to;
        if(d[y]>=d[x])continue;
        return getk(y,p-1);
    }
    return x;
}
void bfs()
{
    v[1]=1;
    q.push(make_pair(1,1));
    while(!q.empty())
    {
        int x=q.front().first,sb=q.front().second;
        for(int i=head[x];i;i=a[i].next)
        {
            int y=a[i].to;
            if(v[y])continue;
            v[y]=1;
            q.push(make_pair(y,sb+1));
        }
        d[x]=sb;q.pop();
    }
}
stack <int> s;
inline void gan(int x,int p)
{
    v[x]=1;s.push(x);l[x]=1;if(p==0)return;
    for(int i=head[x];i;i=a[i].next)
        {
          int y=a[i].to;
          if(v[y])continue;
          gan(y,p-1);
    }
}
inline void clear()
{
    while(!s.empty())
    {
       v[s.top()]=0;
       s.pop();
    }
}
struct ga{
   int bfn ,x;
}b[100005];
bool com(ga x,ga y)
{
    return x.bfn>y.bfn;
}
signed main()
{
//    freopen("data.out","r",stdin);
//    freopen("so.out","w",stdout);
    cin>>n>>k>>t;
    for(int i=1;i<=n-1;i++)
        {
          int x,y;scanf("%d%d",&x,&y);
          add(x,y);add(y,x);
    }
    if(k==0)
    {
      cout<<n;
      return 0;
    }
    bfs();memset(v,0,sizeof(v));
    for(int i=1;i<=n;i++)
    {
        b[i].bfn=d[i];
        b[i].x=i;
    }
    sort(b+1,b+1+n,com);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(l[b[i].x])continue;
        ans++;gan(getk(b[i].x,k),k);
        clear();
    }
    cout<<ans;
    return 0;
}

感觉写的好丑

T3.星空

乍一看貌似很不可做,这个题的精髓就在于转化问题

关键是要明白差分,对于难搞的区间反转,我们可以用差分实现

原序列亮是0,不亮是1(这么定义后面会方便),对于原数组a,差分数组b就是

\(b_i=a_i\oplus a_{i+1}\)

可以类比\(int\)的差分,就是不进位加法,那么对于每个a数组中的数,就可以表示为

\[a_x=\sum_i^{x-1}b_i(\oplus)
\]

这里求和是异或和,那么区间修改\(l\)到\(r\)就变成了单点修改\(l-1\)和\(r\)

最终结果是整个序列全是0,我们完成了第一次转化

我们分析一下,对于一次修改,有三种情况:

1.两边全是0

2.两边全是1

3.一个1一个0

显然全是0没有意义,白白增加工作量,全是1的可以都变成0,是我们想要的操作,一个1一个0的话,由于是反转,就把他们交换了位置,相当于把一个1移动了一个区间的长度,我们目标就是把他们都消去,这里引用一下出题人的描述

给定一个有n个点的图,只有不超过2k个点有物品,每次从m中距离中选择一种移动,两个物品碰到一起会消去,求最少操作次数

我们发现消去2个固定的1的最小步数是恒定的,可以BFS,全部预处理出来,然后至于该怎么选,就是一个裸的状压dp了

为啥是状压?看见小数据,你还能干啥?

#include <bits/stdc++.h>
using namespace std;
bool a[40050];int b[100];
bool c[40050];
vector <int> s;
int n,m,k;
int d[40050],dis[20][20];
queue <pair<int,int>> q;
void bfs(int x)
{
    memset(d,0x3f,sizeof(d));
    q.push(make_pair(x,0));
    d[x]=0;
    while(!q.empty())
    {
        int p=q.front().first,v=q.front().second;
        for(int i=1;i<=m;i++)
            {
             int bi=b[i];
             if(p-bi>=0&&d[p-bi]>v+1)d[p-bi]=v+1,q.push(make_pair(p-bi,v+1));
             if(p+bi<=n&&d[p+bi]>v+1)d[p+bi]=v+1,q.push(make_pair(p+bi,v+1));
        }
        q.pop();
    }
}
inline int getsum(int x)
{
    int ans=0;
    while(x)
    {
      if(x&1)ans++;
      x>>=1;
    }
    return ans;
}
vector <int> sta[17];
int f[1<<17];
signed main()
{
    cin>>n>>k>>m;
    for(int i=1;i<=k;i++)
    {
    int x;scanf("%d",&x);
    a[x]=1;
    }
    for(int i=1;i<=m;i++)scanf("%d",&b[i]);
    for(int i=0;i<=n;i++)c[i]=a[i]^a[i+1];
    for(int i=0;i<=n;i++)
     if(c[i])s.push_back(i);
    memset(dis,0x3f,sizeof(dis));
    for(int i=0;i<s.size();i++)
    {
        bfs(s[i]);
        for(int j=0;j<s.size();j++)
         dis[i][j]=d[s[j]];
    }
    int kk=s.size();
    for(int i=0;i<(1<<kk);i++)
     sta[getsum(i)].push_back(i);
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=0;i<kk;i+=2)
    for(int j=0;j<sta[i].size();j++)
    {
        int x=sta[i][j];
        if(f[x]>1e7)continue;
        for(int p=0;p<kk;p++)
        {
            if(x&(1<<p))continue;
            for(int t=0;t<kk;t++)
            {
                if(x&(1<<t))continue;
                if(t==p)continue;
                f[x|(1<<p)|(1<<t)]=min(f[x|(1<<p)|(1<<t)],f[x]+dis[p][t]);
            }
        }
    }
    cout<<f[(1<<kk)-1];
    return 0;
}

BFS的时候要在进队之前更新d数组,否则增加很多复杂度,狂T不止

考试总结

1.静心思考,相信自己的判断,要有勇气写正解

2.注意细节,别人都能骗到的分你挂了,就说明你有差距,少一份也是少

3.开阔眼界,学会从做过的题里面找规律