HGOI 20190830 题解

缺乏、安全感 2023-06-05 11:27 2阅读 0赞

Problem A 钥匙

> 有$n$个人和$m$个钥匙在数轴上，人的坐标为$a\_i$，钥匙的坐标为$b\_i$
> 
> 而门的坐标为$p$，要让所有人获得一把不同钥匙，并且到达门，最长时间最短是多少。
> 
> 对于$100\\%$的数据满足$10^3 \\leq n \\leq 10^3 , n \\leq k \\leq 2\\times 10^3$

Solution :

对于部分数据，可以二分答案然后进行二分图匹配，实测可以通过$80\\%$的数据。

事实上，对上面算法的极限复杂度是$O(n^2 k log\_2 10^9)$

事实上，我们可以将$nk$中人和钥匙的配对方案求出，排序后，直接从小往大贪心。

这样子复杂度是$O(n \\times k \\times (\\ log\_2 n + log\_2 k))$的。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

# include <bits/stdc++.h>
    # define int long long
    using namespace std;
    const int N=1e6+10;
    int n,k,p,a[N],b[N];
    inline int read() {
        int X=0,w=0; char c=0;
        while(c<'0'||c>'9') {w|=c=='-';c=getchar();}
        while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();
        return w?-X:X;
    }
    int calc(int i,int j) {
        if (a[i]<=b[j] && b[j]<=p) return p-a[i];
        if (a[i]<=p && p<=b[j]) return b[j]-a[i]+b[j]-p;
        if (b[j]<=a[i] && a[i]<=p) return a[i]-b[j]+p-b[j];
        if (b[j]<=p && p<=a[i]) return a[i]-b[j]+p-b[j];
        if (p<=a[i] && a[i]<=b[j]) return b[j]-a[i]+b[j]-p;
        if (p<=b[j] && b[j]<=a[i]) return a[i]-p;  
    }
    namespace Subtask1 {
        vector<int>E[N];
        bool vis[N];
        int pre[N];
        bool find(int u) {
            int sz = E[u].size();
            for (int i=0;i<sz;i++) {
                int v=E[u][i]; if (vis[v]) continue;
                vis[v]=true;
                if (pre[v]==-1 || find(pre[v])) {
                    pre[v]=u;
                    return true;
                }
            }
            return false;
        }
        int solve() {
            int ans = 0;
            memset(pre,-1,sizeof(pre));
            for (int i=1;i<=n;i++) {
                memset(vis,false,sizeof(vis));
                if (find(i)) ans++;
            }
            return ans;
        }
        bool check(int Mid) {
            for (int i=1;i<=n;i++) E[i].clear();
            for (int i=1;i<=n;i++)
             for (int j=1;j<=k;j++)
              if (calc(i,j)<=Mid) E[i].push_back(j);
            int ans = solve();
            return (ans==n);    
        }
        void main() {
            int l=0,r=2e9,ans;
            while (l<=r) {
                int mid = (l+r)>>1;
                if (check(mid)) r=mid-1,ans=mid;
                else l=mid+1; 
            }
            cout<<ans<<'\n';
        }
    }
    namespace Subtask2 {
        bool vis1[N],vis2[N];
        struct node {
            int u,v,val;
        }v[N];
        bool cmp (node a,node b) {
            return a.val<b.val;
        }
        void main() {
            int cnt = 0;
            for (int i=1;i<=n;i++)
             for (int j=1;j<=k;j++)
               v[++cnt]=(node){i,j,calc(i,j)};
            sort(v+1,v+1+cnt,cmp);
            int ans = 0 ;
            for (int i=1;i<=cnt;i++) {
                node tmp = v[i];
                if (vis1[tmp.u] || vis2[tmp.v]) continue;
                ans=max(tmp.val,ans);
                vis1[tmp.u] = vis2[tmp.v] = 1;
            }
            printf("%lld\n",ans);
        } 
    } 
    signed main() {
    //  freopen("key.in","r",stdin);
        //freopen("key.out","w",stdout);
        n=read();k=read();p=read();
        for (int i=1;i<=n;i++) a[i]=read();
        for (int i=1;i<=k;i++) b[i]=read();
        if (n*k <= 10000000/3/n)  Subtask1::main();
        else Subtask2::main();
        return 0;
    }

A.cpp

Problem B 汪哥图

> 给出$n\\times m$的$01$矩阵，保证这个矩阵中任意两个$1$之间最多有一条路径不经过$0$。
> 
> 给出$Q$组询问，求子矩阵联通块个数。
> 
> 对于$100\\%$的数据满足$2 \\times 10^3 \\leq n,m \\leq 2\\times 10^3 , 1 \\leq Q \\leq 2\\times 10^5 $

Solution :

我们先假设这个子矩阵中所有的$1$都自成一格连通块，显然，有好多连通块可以合并。

由于矩阵中的性质： 任意两个$1$之间最多有一条路径不经过$0$，所以合并的方式一定是从左到右或者从上到下。

即如果$a\[i\]\[j\] $和$a\[i+1\]\[j\]$都是$1$，那么必然会减少一个连通块，如果$a\[i\]\[j\]$和$a\[i\]\[j+1\]$都是$1$，也必然会减少一个连通块。

所以，我们定义$f\[i\]\[j\] = \[a\[i\]\[j\] = 1 \] \\times \[a\[i+1\]\[j\] = 1\] , g\[i\]\[j\] = \[ a\[i\]\[j\] = 1 \] \\times \[a\[i\]\[j+1\] = 1\] $

对于左上角坐标为$(x\_1,y\_1)$，右下角坐标为$(x\_2,y\_2)$的子矩阵，答案是$ans = \\sum\\limits\_\{i=x\_1\}^\{x\_2\} \\sum\\limits\_\{j=y\_1\} ^ \{y\_2\} a\[i\]\[j\] - \\sum\\limits\_\{i=x\_1\}^\{x\_2 - 1\} \\sum\\limits\_\{j=y\_1\} ^ \{y\_2\} f\[i\]\[j\] - \\sum\\limits\_\{i=x\_1\}^\{x\_2\} \\sum\\limits\_\{j=y\_1\} ^ \{y\_2-1\} g\[i\]\[j\]$

显然可以用二维前缀和优化。

复杂度是$O(nm + Q)$

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

# include <bits/stdc++.h>
    using namespace std;
    const int N=2e3+10;
    int a[N][N],c1[N][N],c2[N][N],sum1[N][N],suma[N][N],sum2[N][N];
    int n,m,q;
    inline int read() {
        int X=0,w=0; char c=0;
        while(c<'0'||c>'9') {w|=c=='-';c=getchar();}
        while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();
        return w?-X:X;
    }
    void write(int x) {
        if (x>9) write(x/10);
        putchar('0'+x%10);
    }
    int calca(int x1,int y1,int x2,int y2){
        return suma[x2][y2]-suma[x2][y1-1]-suma[x1-1][y2]+suma[x1-1][y1-1]; 
    }
    int calc1(int x1,int y1,int x2,int y2){
        if (x2<x1 || y2<y1) return 0;
        return sum1[x2][y2]-sum1[x2][y1-1]-sum1[x1-1][y2]+sum1[x1-1][y1-1];
    }
    int calc2(int x1,int y1,int x2,int y2) {
        if (x2<x1 || y2<y1) return 0;
        return sum2[x2][y2]-sum2[x2][y1-1]-sum2[x1-1][y2]+sum2[x1-1][y1-1];
    }
    int main() {
        n=read();m=read();q=read();
        for (int i=1;i<=n;i++) 
            for (int j=0;j<m;j++) {
                char op=0; while (op!='1' && op!='0') op=getchar();
                a[i][j+1]=op-'0';
            }
        for (int i=1;i<=n;i++)
         for (int j=1;j<=m;j++)
          c1[i][j]=a[i][j] && a[i+1][j],
          c2[i][j]=a[i][j] && a[i][j+1]; 
        for (int i=1;i<=n;i++)
         for (int j=1;j<=m;j++)
          suma[i][j]=suma[i-1][j]+suma[i][j-1]-suma[i-1][j-1]+a[i][j],
          sum1[i][j]=sum1[i-1][j]+sum1[i][j-1]-sum1[i-1][j-1]+c1[i][j],
          sum2[i][j]=sum2[i-1][j]+sum2[i][j-1]-sum2[i-1][j-1]+c2[i][j];
        while (q--) {
            int x1=read(),y1=read(),x2=read(),y2=read();
            int ans = calca(x1,y1,x2,y2)-calc1(x1,y1,x2-1,y2)-calc2(x1,y1,x2,y2-1);
            write(ans); putchar('\n');
        }
        return 0;
    }

B.cpp

Problem C 时空阵

> 本题时间限制$4000 ms$
> 
> 有$n$个点，用最多$\\frac\{n(n-1)\}\{2\}$条边权为$1$的双向边连接成一个图，
> 
> 给出$m$，要求在构造出的图中，有$1 - n$的最短路为$m$的图的个数$mod \\ 10^9 + 7$的值。
> 
> 当且仅当两个图中连边集合不同，则两个图不同。
> 
> 对于$100\\%$的数据满足$1 \\leq m < n\\leq 100 $。

Solution :

假设把这些点中的若干个点分成$m+1$个集合，编号为$\[0,m\]$ , 每个集合中至少有$1$个点，并且$1$个点最多在$1$个集合中。

并且保证，任取$i \\in \[0,m-1\]$，第$i$个集合和第$i+1$个集合中的点直接的距离是$1$。强制第$0$个集合为出发点，只有一个元素$1$.

为了体现$1$开始到其他点的最短路，特殊的，要求$1-n$的最短路为$m$,我们强制编号为$0$的集合为出发集，只有一个元素$1$，$n$必须在编号为$m$的集合中

这样一来，我们只需要计算划分集合的方案数了。

我们从编号为$1$的集合开始考虑。设$f\[i\]\[j\]\[k\]$表示考虑到集合$i$，已经放置了$j$个数字，第$i$个集合放置了$k$个数字的方案数。

我们可以枚举上一个集合放置元素个数$s$，从$f\[i-1\]\[j-k\]\[s\]$转移过来。

我们考虑构成当前集合的情况：

*   *  要求之前被安放的数字不重复：除了元素$n$之外还剩余$n-1-(j-k)$个数字，有$\\binom\{n-1-(j-k)\}\{k\}$种可能。
     *  当前集合里元素之间可以无限制连边：有$2 ^ \\binom\{k\}\{2\} $种可能。
     *  之前一个集合和当前集合至少需要有$1$条连边：有$(2^s - 1) ^ k$种可能

注意到，要求之前被安放的数字不重复中，若$i = m$的时候，由于最后一个集合中已经被强制放入元素$n$，所以需要另外选择的元素是$k-1$个，所以有$\\binom\{n-1-(j-k)\}\{k-1\}$种可能。

所以转移方程为：

$f\[i\]\[j\]\[k\] =\\left\\\{\\begin\{matrix\}\\sum\\limits\_\{s = 1\} ^ \{j-k\} f\[i-1\]\[j-k\]\[s\] \\times \\binom\{n-j+k-1\}\{k\} \\times 2 ^ \{\\binom\{k\}\{2\}\} \\times (2^s - 1) ^ k & (1 \\leq i < m )\\\\ \\sum\\limits\_\{s = 1\} ^ \{j-k\} f\[i-1\]\[j-k\]\[s\] \\times \\binom\{n-j+k-1\}\{k-1\} \\times 2 ^ \{\\binom\{k\}\{2\}\} \\times (2^s - 1) ^ k & (i=m) \\end\{matrix\}\\right.$

统计答案的时候，设当前已经将$j$个元素放置在分层图当中了，最后一层中放置了$k$个，那么考虑这些点直接互相连边，这些点和最后一层中所有点之间互相连边的可能即可。

最后的答案就是$ans = \\sum\\limits\_\{j = m+1\}^\{n\} \\sum\\limits\_\{k = 1\}^\{j-m\} f\[m\]\[i\]\[j\] \\times 2^\{\\binom\{n-j\}\{2\} + (n-j) \\times k\}$

复杂度是$O(n^4)$

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

# include <bits/stdc++.h>
    # define int long long
    # define fp(i,s,t) for (int i=s;i<=t;i++)
    using namespace std;
    const int mo=1e9+7;
    const int N=310;
    int c[N][N],n,m,f[N][N][N],Max;
    int Pow(int x,int n)
    {
        Max = max(Max,n);
        int ans = 1;
        while (n) {
            if (n&1) ans=ans*x%mo;
            x=x*x%mo;
            n>>=1;
        }
        return ans;
    }
    signed main()
    {
        scanf("%lld%lld",&n,&m);
        c[0][0]=1;
        fp(i,1,300) { 
            c[i][0]=c[i][i]=1;
            fp(j,1,i-1) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mo;
        }
        f[0][1][1]=1;
        fp(i,1,m)  fp(j,1,n) fp(k,1,j) fp(s,1,j-k) {
            if (i!=m) f[i][j][k]+=Pow(2,c[k][2]) * Pow((Pow(2,s)-1+mo)%mo,k)%mo * c[n-j+k-1][k] % mo * f[i-1][j-k][s] %mo;
            else f[i][j][k]+=Pow(2,c[k][2]) * Pow((Pow(2,s)-1+mo)%mo,k)%mo * c[n-j+k-1][k-1] % mo * f[i-1][j-k][s] %mo;
            f[i][j][k]%=mo;
        }
        int ans = 0;
        fp(j,m+1,n) fp(k,1,j-m) {
            ans=(ans+f[m][j][k]*Pow(2,c[n-j][2]+(n-j)*k)%mo)%mo;
        }
        cout<<ans<<'\n';
        return 0;
    }

C.cpp

转载于:https://www.cnblogs.com/ljc20020730/p/11434655.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/377d347e44ca47fe9038d1c7a677baf1.png