AGC003 补题小结

墨蓝 2022-01-07 14:51 187阅读 0赞

#### Problem A Wanna go back home ####

简要题意：给定一个由 \$N,S,W,E\$ 构成的字符串，字母表示向东南西北走一步(任意长度)，问能否回到原点 \$|S|\\le 10^5\$

tag：小学生贪心

题解：南北和东西要么同时有，要么都没有

#include <cstdio>
    #include <cstring>
    char a[1005];bool N=0,S=0,W=0,E=0;
    int main (){
        scanf ("%s",a+1);int n=strlen(a+1);
        for (int i=1;i<=n;i++) 
            if (a[i]=='N') N=1;
            else if (a[i]=='S') S=1;
            else if (a[i]=='W') W=1;
            else E=1;
        if ((N^S)||(W^E)) puts("No");
        else puts("Yes");
        return 0;
    }

#### Problem B Simplified mahjong ####

简要题意：你有 \$a\_i\$ 个数字 \$i\$ ，每次可以选两个差不超过 \$1\$ 的数字配对，问最多配对对数。\$n\\le 10^5,a\_i\\le 10^9\$

tag：贪心

题解：两两配对，类似桶排

#include <cstdio>
    #define ll long long
    inline int Min(int a,int b){
        return a<b?a:b;
    }
    ll ans=0;int a[100005];
    int main() {
        int n;scanf ("%d",&n);
        for (int i=1;i<=n;i++) scanf ("%d",&a[i]);
        for (int i=1;i<=n;i++){
            if (a[i]&&a[i-1]) a[i]--,a[i-1]--,ans++;
            ans+=(a[i]>>1),a[i]&=1;
        }
        printf ("%lld",ans);
        return 0;
    }

#### Problem C BBuBBBlesort! ####

简要题意：给定一个长度为 \$n\$ 序列，支持两种操作

1.  翻转任意长度为 \$3\$ 的子段
2.  翻转任意长度为 \$2\$ 的子段

求给数列排序使用的最少的操作 \$2\$ 的次数。\$n\\le 10^5,a\_i\\le 10^9\$

tag：贪心，结论题

题解：有这样一个结论：如果 \$i\$ 位置的元素距离其目标位置 \$a\_i\$ 的距离是奇数，则必须用一次 \$2\$ 操作。设这样的元素个数是 \$k\$ 个，答案就是 $\\frac\{k\}\{2\} $。

证明：必要性：\$1\$ 操作不能改变一个元素离它的目标位置的奇偶性。充分性：两个距离其目标位置是奇数的元素，用 \$2\$ 操作一定可以把它们挪到一起，它们两个交换一下位置，一定可以用 \$2\$ 操作移回自己的目标位置。

#include <map>
    #include <cstdio>
    using namespace std;
    const int N=1e5+5;
    map <int ,int > ma;
    int a[N],b[N];
    int main (){
        int n;scanf ("%d",&n);
        for (int i=1;i<=n;i++) scanf ("%d",&a[i]),b[i]=a[i];
        sort(b+1,b+n+1);for (int i=1;i<=n;i++) ma[b[i]]=i;
        int k=0;
        for (int i=1;i<=n;i++)
            if ((i-ma[a[i]])&1) k++;
        printf ("%d",(k>>1));
        return 0;
    }

#### Problem D Anticube ####

简要题意：给定 \$n\$ 个数 \$s\_i\$ ，要求从中选出最多的数并且任意两个数字的积不是完全立方数。 \$n\\le 10^5,s\_i\\le 10^\{10\}\$

tag：Hash，质因数分解，补集转化

题解：可以分解到 \$a^\{\\frac\{1\}\{3\}\}\$ ，然后要么是某质数平方 \$p^2\$ ，要么是大质数 \$p\$ ，这样可以不用使用 \$Pollard-Rho\$ 当然有兴趣写也行 ，考虑把每一个指数对 \$3\$ 取模，如果两个数所有对应质因子指数之和都是3的倍数，那么它们不能划在同一个集合，这样补集转化一下，直接用map存下来就可以了。

#include <map>
    #include <cmath>
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    #define ll long long
    map <ll ,int > ma;
    const int M=3005,N=100005;
    int p[M],tot=0;bool notp[M];
    ll a[N];ll c1[N],c2[N];
    int cnt[N];
    map <ll,bool > used;
    inline void getp(){
        for (int i=2;i<=3000;i++){
            if (!notp[i]) p[++tot]=i;
            for (int j=1;i*p[j]<=3000&&j<=tot;j++){
                notp[i*p[j]]=true;
                if (i%p[j]==0) break;
            }
        }
    }
    int main (){
        int n;scanf ("%d",&n);
        getp();bool flag=false;
        for (int i=1;i<=n;i++) scanf ("%lld",&a[i]);
        for (int i=1;i<=n;i++){
            for (int j=1;j<=tot;j++) cnt[j]=0;
            ll hash=1,hash2=1;
            for (int j=1;j<=tot;j++)
                while (a[i]%p[j]==0) a[i]/=p[j],cnt[j]++;
            for (int j=1;j<=tot;j++) {
                cnt[j]%=3;
                for (int k=1;k<=cnt[j];k++) hash*=p[j];
                if (cnt[j]) for (int k=2;k>=cnt[j];k--) hash2*=p[j];
            }
            if (a[i]==1) c1[i]=hash,c2[i]=hash2;
            else {
                ll t=(ll)sqrt(a[i]);
                if (t*t==a[i]) hash*=t,hash*=t,hash2*=t;
                else hash*=a[i],hash2*=a[i],hash2*=a[i];
                c1[i]=hash,c2[i]=hash2;
            }
        }
        int ans=0;
        for (int i=1;i<=n;i++) ma[c1[i]]++;
        for (int i=1;i<=n;i++){
            ll x=c1[i],y=c2[i];
            if (used[x]||used[y]) continue;
            ll t=ma[x]>ma[y]?x:y;used[t]=1;
            ans+=(t==1)?1:ma[t];
        }
        printf ("%d",ans);
        return 0;
    }

#### Problem E Sequential operations on Sequence ####

简要题意：一串数，初始为 \$1...N\$ ，现在给 \$Q\$ 个操作，每次操作把数组长度变为 \$q\_i\$ ，新增的数为上一个操作后的数组不停自身复制直到长度等于 \$q\_i\$ 。问 \$Q\$ 次操作后 \$1-N\$ 每个数出现了多少次。\$N,Q\\le 10^5,q\_i\\le 10^\{18\}\$

tag：巧妙思维题，数据结构，单调栈，递归，差分

题解：数据结构题中很妙的一种，应该是我目前见过最妙的数据结构题之一了。

首先，如果满足 \$q\_i\\ge q\_\{i+1\}\$，那么 \$q\_\{i+1\}\$ 显然不会造成任何影响，所以维护一个单调栈，只留下有用的操作，即使得最后的操作序列单调递增

考虑一个计算第 \$i\$ 次操作过程。前面的一大堆都是上一次操作所得答案的若干倍，所以对于一个操作，只要单独处理 \$q\_i\\ \\%\\ q\_\{i-1\}\$ 那一部分的答案就好了。至于前面那些没用的，就给第 \$i-1\$ 个操作加上一个系数，到时候操作它的时候答案乘上这个系数即可。

那单独处理的这一部分，做法也是一样的。跳过前面比这一段长度更大的操作，找到第一个小于它长度的 \$q\_t\$ ，前面一大堆都是第 \$t\$ 次操作的若干倍，所以直接给第 \$t\$ 次操作加上一个系数，再处理 \$(q\_i\\ \\%\\ q\_\{i-1\}) \\% q\_t\$ 即可。就这样不断递归下去，直到没有比它更小的了，此时直接给答案区间 \$\[1, len\]\$ 加上当前操作的系数即可（len表示当前区间长度）。区间加法可以用差分实现，最后还原即可。

那这个过程显然要倒着来做，否则你不知道当前操作的系数是多少。

至于复杂度，递归时每次长度模一个数，那层数显然不超过 \$log\$ 层。因为要二分找上面说的那个 \$t\$ ，所以复杂度是\$O(nlognlogq)\$。代码非常好写。

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    const int N=100005;
    #define ll long long
    ll a[N],f[N],d[N];int top=0;
    inline void work(ll x,ll y){
        if (!x) return;
        int t=upper_bound(a+1,a+top+1,x)-a-1;
        if(!t) d[1]+=y,d[x+1]-=y;
        else f[t]+=x/a[t]*y,work(x%a[t],y);
    }
    int main (){
        int n,m;scanf ("%d%d",&n,&m);
        a[++top]=n;
        for (int i=1;i<=m;i++){
            ll x;scanf ("%lld",&x);
            while (x<=a[top]) --top;
            a[++top]=x;
        }
        f[top]=1;
        for (int i=top;i>=2;i--) f[i-1]+=a[i]/a[i-1]*f[i],work(a[i]%a[i-1],f[i]);
        d[1]+=f[1],d[a[1]+1]-=f[1];
        for (int i=1;i<=n;i++) d[i]+=d[i-1],printf ("%lld\n",d[i]);
        return 0;
    }

#### Problem F Fraction of Fractal ####

简要题意：给定一个 \$H\\times W\$ 的黑白网格，保证黑格四连通且至少有一个黑格

定义分形如下：\$0\$ 级分形是一个 \$1\\times 1\$ 的黑色单元格，\$k+1\$ 级分形由 \$k\$ 级分形得来。具体而言，\$k\$ 级分形中每个黑色单元格将会被替换为初始给定的 \$H\\times W\$ 的黑白网格，每个白色单元格会被替换为 \$H\\times W\$ 的全白网格

求 \$k\$ 级分形的四连通分量数，答案对 \$10^9+7\$ 取模 \$k\\le 10^\{18\},\\ \\ H,W\\le 10^3\$

**四连通分量就是连通块**

tag：找规律，矩阵快速幂，思维题

题解：

首先如果这个图形与四周不连通，那么答案就一定是 \$cnt^\{k-1\}\$ ，其中 \$cnt\$ 为黑点个数。

如果这个图形上接下是联通的，左接右也是联通的，那么答案就一定是 \$1\$，因为最后的分形一定联通。

那么剩下的情况就只有上边和下边联通，左边和右边联通两种情况之一了（其实旋转一下就是一种情况，这里只讨论行连通，列不连通的情况）。

那么我们就只需求出 \$x,y,z\$，其中 \$x\[k\]\$ 表示 \$k\$ 级分形有多少个黑连通块，\$y\[k\]\$ 表示 \$k\$ 级分形有多少个黑块满足它同一行右边一个也是黑块。 \$z\[k\]\$ 表示 \$k\$ 级分形有多少行是首位连通的。

\$x\[k\]=x\[k-1\]^2,y\[k\]=x\[k-1\]y\[k-1\]+z\[k-1\]y\[k-1\],z\[k\]=z\[k-1\]^2\$

那么可以构造矩阵优化这个过程，\$\\begin\{bmatrix\}x&y\\\\ 0 & z \\end\{bmatrix\}\$

用快速幂求 \$A=\\begin\{bmatrix\}x &y \\\\ 0 & z \\end\{bmatrix\}^\{k-1\}\$，答案就是 \$x-y\$ (即为 \$A\[1\]\[1\]-A\[1\]\[2\]\$ ) 。

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    #define ll long long
    const int N=4,Mod=1e9+7;
    struct Mat{
        int a[N][N];
        inline void clear(){memset (a,0,sizeof(a));}
        inline Mat operator *(Mat t){
            Mat c;c.clear();
            for (int i=1;i<=2;i++)
                for (int j=1;j<=2;j++)
                    for (int k=1;k<=2;k++){
                        c.a[i][j]+=1ll*a[i][k]*t.a[k][j]%Mod;
                        c.a[i][j]%=Mod;
                    }
            return c;
        }
    };
    inline int qpow(int a,ll b){
        int ans=1;
        while (b){
            if (b&1) ans=1ll*ans*a%Mod;
            a=1ll*a*a%Mod,b>>=1;
        }
        return ans;
    }
    const int M=1005;
    char s[M][M],ss[M][M];
    int n,m;ll k;
    inline void rev(){
        for (int i=1;i<=n;i++)
            for (int j=1;j<=m;j++)
                ss[m-j+1][i]=s[i][j];
        swap(n,m);
        for (int i=1;i<=n;i++)
            for (int j=1;j<=m;j++)
                s[i][j]=ss[i][j];
    }
    inline int query(){
        int cnt=0;
        for (int i=1;i<=n;i++)
            if (s[i][1]=='#'&&s[i][m]=='#') ++cnt;
        return cnt;
    }
    int main ()
        scanf ("%d%d%lld",&n,&m,&k);
        for (int i=1;i<=n;i++)
            scanf ("%s",s[i]+1);
        int x=0,y=0,z=0;
        for (int i=1;i<=n;i++)
            for (int j=1;j<=m;j++)
                x+=(s[i][j]=='#');
        int f1=query(),cnt=0;
        rev();int f2=query();rev();
        if (f1&&f2) return puts("1"),0;
        else if (!f1&&!f2) return printf ("%d",qpow(x,k-1)),0;
        else if (f2) rev();
        for (int i=1;i<=n;i++)
            for (int j=1;j<m;j++)
                y+=(s[i][j]=='#'&&s[i][j+1]=='#');
        for (int i=1;i<=n;i++)
            z+=(s[i][1]=='#'&&s[i][m]=='#');
        Mat t;t.clear();
        t.a[1][1]=x,t.a[1][2]=y,t.a[2][2]=z;
        Mat ans;ans.clear();--k;ans.a[1][1]=ans.a[2][2]=1;
        while (k){
            if (k&1) ans=ans*t;
            t=t*t,k>>=1;
        }
        printf ("%d",(ans.a[1][1]-ans.a[1][2]+Mod)%Mod);
        return 0;
    }

转载于:https://www.cnblogs.com/crazyzh/p/10883758.html