常州集训Day6！

Posted on By 王子晔, 王子晔 常州集训Day6！无评论

LPC 计算机学会第五届“鸭王争霸赛”

A.虫洞（wormhole）

动态规划

很明显是一道DP题。推一段时间之后，就发现了一个十分重要的结论：无论李Dog在哪个房间，一定不存在一个编号小于该房间的房间，使得该房间存在钥匙。

思路

  • 若i-1号房间初始时有钥匙，则直接利用钥匙走虫洞即可。此时有
  • DP[i]=DP[(i-1)]+1
  • 若 i-1号房间初始时没有钥匙，则无论李Dog在哪个房间，一定不存在一个编号小于该房间的房间，使得该房间存在钥匙。用类似方法可以轻易的证明这个结论在此时仍然成立。此时有
  • DP[i]=DP[(i-1)]+1+PD[(i-1)]-PD[(P[(i-1)])]+1
  • 其中PD[i]表示在A[i]=0的情形下，首次来到i号房间需要的最小步数。根据定义,PD[i]的转移方程即为
  • DP[i]=DP[(i-1)]+1+DP[(i-1)]-DP[(P[(i-1)])]+1
  • $ DP[n] $ 即为答案。
  • 复杂度O(n)。

代码：

#include
using namespace std;
#define ll long long
const ll N=1145141,mod=1710833; 
ll tot,n,m,p[N],dp[N],sum[N],ans;
bool a[N];
inline ll read()
{
    ll x=0,f=1;
    char c=getchar();
    while(!isdigit(c)&&c!='-') c=getchar();
    if(c=='-') f=-1,c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
    return f*x;
} 
int main()
{
    freopen("wormhole.in","r",stdin);
    freopen("wormhole.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
    }
    for(int i=1;i<=n;i++)
    {
        p[i]=read();
    }
    dp[1]=2;
    sum[1]=0;
    for(int i=2;i<=n;i++)
    {
        sum[i]=(dp[i-1]+sum[i-1])%mod;
        dp[i]=(sum[i]+2-sum[p[i]]+mod)%mod;
    }
    ans=sum[n];
    for(int i=1;i<=n-1;i++)
    {
        if(a[i]) 
        {
            ans=(ans-dp[i]+1+mod)%mod;
        }
    } 
    printf("%lld\n",ans);
    return 0;
}
/*
2
0 0
1 2*/

B.剪发（haircut）

倒序并查集

一开始就是单纯用深搜去打，卡过两个测试点去拿三十分。后来就是想到优化，通过建树和二分加查询来对剩下的两个测试点。结果在考试结束时没来得及写完。

思路

  • 每次填充先将簇数+1；
  • 依次检查填充处四周的头发，若某一侧有头发且与填充位置分属不同的并查集，则进行并查集合并，同时簇数-1，更新该并查集大小；
  • 将最终并查集大小与当前最大值答案取max，得到新的最大值答案
  • 若填充处两侧目前没有头发，则说明该次剪发前头发比剪发后多了“填充”的这一簇，簇数+1，最大面积和1取max；
  • 若填充处一侧目前有头发，则说明这次剪发没有改变簇数，将这个位置加入有头发一侧的并查集即可，然后重新统计最大值答案；
  • 若填充处两侧均有头发，则说明这次剪发将一簇头发“分”成了两簇，簇数-1（由于是倒序），然后将这个位置和左右两边加入同一个并查集，然后统计最大值答案。

错误代码：

#include
using namespace std;
inline int read()
{
    int x=0,f=1;char c;
    do c=getchar();while(!isdigit(c)&&c!='-');
    if(c=='-') f=-1,c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
    return x*f; 
}
int T;
int n,m,q;
int a[310][310],ans,sum,s;
int dx[5]={0,0,1,-1};
int dy[5]={1,-1,0,0};
bool v[310][310];
void dfs(int sx,int sy)
{
    v[sx][sy]=1;
    for(int i=0;in||fxm||fy<1)
        {
            continue;
        }
        if(!v[fx][fy]&&a[fx][fy]==1)
        {
            dfs(fx,fy);
            sum++;
        }
    }
}
int main()
{
    freopen("haircut.in","r",stdin);
    freopen("haircut.out","w",stdout);
    T=read();
    while(T--)
    {
        n=read(),m=read(),q=read();
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                a[i][j]=read();
            }
        }
        for(int k=1;k<=q;k++)
        {
            memset(v,0,sizeof(v));
            ans=0;
            s=0;
            int x=read(),y=read();
            a[x][y]=0;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=m;j++)
                {
                    if(!v[i][j]&&a[i][j]==1)
                    {
                        s++;
                        sum=1;
                        dfs(i,j);
                        ans=max(sum,ans);
                    }
                }
            }
            printf("%lld %lld\n",s,ans);
        }
    }
    return 0;
}
/*
1
5 5 3
1 0 0 0 0
1 1 0 0 0
0 0 1 1 1
1 0 1 0 1
1 0 1 1 1
3 4
2 2
5 4//
2
5 5 3
1 1 0 1 1
1 0 0 0 1
0 1 0 1 0
0 1 0 1 0
0 1 1 1 0
1 1
5 3
4 4
5 7 9
1 0 1 1 0 1 1
1 0 0 1 0 1 0
1 1 1 0 1 1 1
1 0 1 0 1 0 1
1 1 0 0 1 0 1
3 1
3 6
5 1
1 1
5 7
3 5
1 7
2 4
3 3*/

C.吃人（eatman）

莫队（学ing）

考试的时候没有什么思路，就暴力枚举[Li,Ri]之间每个区间，排序找出中位数并与K 比对.

错误代码：

#include
using namespace std;
const int N=5e4+100;
int a[N],d[N],f[N],ans[N];
int pre,cnt;
struct wzy
{
    int d,l,r;
}que[N];
bool cmp(wzy x,wzy y)
{
    if(x.l!=y.l)
    {
        return x.l/200n>>k>>q;
    d[0]=cnt;
    f[cnt]=1;
    for(int i=1;i>a[i];
        if(a[i]>k)
        {
            cnt++;
        }
        if(a[i]que[i].l>>que[i].r;
        que[i].l--;
    }
    sort(que+1,que+q+1,cmp);
    int l=0,r=0;
    for(int i=1;ique[i].l)
        {
            l--;
            int dl=d[l];
            pre+=f[dl];
            f[dl]++;
//          cout<<dl<<endl;
        }
        while(r<que[i].r)
        {
            r++;
            int dr=d[r];
            pre+=f[dr];
            f[dr]++;
//          cout<<dr<<endl;
        }
        while(l<que[i].l)
        {
            int dl=d[l];
            pre-=f[dl]-1;
            f[dl]--;
            l++;
//          cout<<dl<que[i].r)
        {
            int dr=d[r];
            pre-=f[dr]-1;
            f[dr]--;
            r--;
//          cout<<dr<<endl;
        }
//      cout<<pre<<endl;
        ans[que[i].d]=pre;
    }
    for(int i=1;i<=q;i++)
    {
        cout<<ans[i]<<endl;
    }
    return 0;
}
/*
3 3 3
2 1 4
2 3
1 2 
1 3
*/

D.鸭子（duck）

环形差分约束

不用想，100%是想不到正解的，环形差分约束根本不会。。。
考试的时候就暴力枚举每个房间所住的鸭子只数，然后忘记排除掉那些无论如何不可能的状态，就只能零分了。

思路

若L[i]≤R[i]，则转化为S[(R[i])]-S[(L[i]-1)]≤Di，(L[i-1])向 R[i]连权值为 D[i]的边即可。
若Li>Ri，则转化为 Sn+S(Ri)-S(Li-1)≤D[i]。即S[(R[i])]-S[(L[i]-1)]≤D[i-S[n]]。
枚举S[n]的值，将所有不等式右边转化为已知数，然后连边。对S[n]的每一种
取值，跑一边差分约束。若有解且算出的S[n]上限不小于枚举的S[n]，则枚举的S[n]
合法；否则需要将限制调松，即调小枚举的S[n]，再跑差分约束，直到合法为止。

错误代码

#include
using namespace std;
typedef long long ll;
inline ll read()
{
    ll x=0,f=1;char c;
    do c=getchar();while(!isdigit(c)&&c!='-');
    if(c=='-') f=-1,c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
    return x*f; 
}
int n,k,m,ans,gs;
struct stu
{
    int l;
    int r;
    int d;
}ques[510];
ll s[1010],a[1010];
bool chek()
{
    for(int i=1;iques[i].d)
                {
                    return false;
                }
            }
        }
    } 
    return true;
}
void dfs(int x,int sum)
{
    if(x>n)
    {
        if(chek())
        {
            ans=max(ans,sum);
        }
        return ;
    }
    for(int i=0;i<=k;i++)
    {
        a[x]=i;
        s[x]=s[x-1]+i;
        dfs(x+1,sum+i);
    }
}
int main()
{
    freopen("duck.in","r",stdin);
    freopen("duck.out","w",stdout);
    n=read(),k=read(),m =read();
    for(int i=1;iques[1].r)
        {
            gs=n-ques[1].l+1+ques[1].r;
        }
        else
        {
            gs=ques[1].r-ques[1].l+1;
        }
        ans=(n-gs)*k+min(ques[1].d,gs*k);
        printf("%d\n",ans);
        return 0;
    }
    dfs(1,0);
    printf("%d\n",ans);
    return 0;
}
/*
5 5 2
2 4 14
4 2 18
*/
训练日志

发表回复