Codeforces Round #596 (Div. 2) 题解

省略的程序头：

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define mp make_pair
#define ha 1000000007
#define ui unsigned int
#define pii pair<int,int>
#define pid pair<int,double>
 
using namespace std;
 
inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

A.Forgetting Things

题意

题解

就三种情况：$d_a=d_b$ ，$d_a=9,d_b=1$ ，$d_b=d_a+1$ ，分别构造即可。

int a,b;

signed main()
{
    a=read(); b=read();
    if (a==9 && b==1) return !printf("99 100");
    if (a!=b && a!=b-1) return 0&puts("-1");
    if (a==b) printf("%d0 %d1",a,b);
    else printf("%d9 %d0",a,b);
    return 0;
}

B.TV Subscriptions

题意

题解

用 $cnt[i]$ 维护颜色 $i$ 的数量，$cur$ 表示当前的颜色数。按题意模拟即可。

int t,n,k,d,a[200005],cnt[1000005];

signed main()
{
    t=read();
    while (t--)
    {
        memset(cnt,0,sizeof(cnt));
        n=read(); k=read(); d=read();
        for (int i=1;i<=n;i++) a[i]=read();
        int j=1,cur=0,ans=0;
        for (;j<=d;j++)
        {
            if (!cnt[a[j]]) cur++;
            cnt[a[j]]++;
        }
        ans=cur;
        for (int i=2;j<=n;i++,j++)
        {
            cnt[a[i-1]]--;
            if (!cnt[a[i-1]]) cur--;
            if (!cnt[a[j]]) cur++;
            cnt[a[j]]++;
            ans=min(ans,cur);
        }
        printf("%d\n",ans);
    }
    return 0;
}

C.p-binary

题意

题解

直接枚举答案 $ans$，要求 $(n)_2$ 中 $1$ 的个数 $\le ans$ （不够的可以拆开来凑），还有 $n\geq ans$ （全用 $1$ 能凑出）。

int n,p;

inline bool check(int res,int m)
{
    if (m<res) return 0;
    int ans=0;
    for (int i=30;~i;i--)
    {
        if (m>=(1<<i)) m-=1<<i,ans++;
    }
    if (ans>res || m) return 0;
    return 1;
}

signed main()
{
    n=read(); p=read();
    int i=1;
    for (;i<=100000;i++) if (check(i,n-i*p)) break;
    if (i==100001) return 0&puts("-1");
    printf("%d",i);
    return 0;
}

D.Power Products

题意

题解

很容易想出对于每个 $a_i$ ，统计它的所有约数如 $p^q$ ，那么只有满足包含所有 $p^{k-q\ mod \ k}$ 的 $a_j$ 才能与之匹配。

然后我就陷入了沉思，这™一个数这么多约数，怎么统计啊。

直到比赛后我看到了这个东西：

map <vector<pair<int,int> >,int> mp;

长见识了，第一次用 STL 套 STL 套 STL 。

具体做法就是用个 vector 记录一个数的所有约数 $p$ 和指数 $q$ ，然后得到与之互补的情况，并用 map 统计所有情况出现的次数来统计答案。

const int N=100005;
bool ss[N];
ll ans;
int cnt,n,k,zs[N];
map <vector<pii>,int> m;

inline void getPrime()
{
    memset(ss,1,sizeof(ss));
    ss[0]=ss[1]=0;
    for (int i=2;i<=100000;i++)
    {
        if (ss[i]) zs[++cnt]=i;
        for (int j=1;j<=cnt && zs[j]*i<=100000;j++)
        {
            ss[zs[j]*i]=0;
            if (i%zs[j]==0) break;
        }
    }
}

inline void work(int x)
{
    vector <pii> u,v; //当前状态和互补状态
    for (int i=1;zs[i]*zs[i]<=x;i++)
    {
        if (x%zs[i]) continue;
        int cur=0;
        while (x%zs[i]==0) x/=zs[i],cur++;
        if (cur%k) u.emplace_back(mp(i,cur%k));
    }
    if (x>1)
    {
        int pos=lower_bound(zs+1,zs+cnt+1,x)-zs;
        u.emplace_back(mp(pos,1));
    }
    for (auto i:u) v.emplace_back(mp(i.first,k-i.second));
    ans+=m[v]; //用互补状态统计答案
    m[u]++;
}

signed main()
{
    getPrime();
    n=read(); k=read();
    for (int i=1;i<=n;i++) work(read());
    printf("%lld",ans);
    return 0;
}

E.Rock Is Push

题意

题解

如果当前在 $(x,y)$ ，可以发现向右最多能行进 $m-y-\text{右侧的石头个数}$ 步 。向下同理。

考虑DP，根据上述限制只能倒过来转移。用 $D[x][y]$ 表示下一步向下走，从 $(x,y)\rightarrow (n,m)$ 的方案数；$R[x][y]$ 表示下一步向右走。

考虑向下，设下面有 $s$ 块石头，那么最多走 $n-x-s$ 步。方程式为：

$$D[x][y]=\sum_{i=x+1}^{n-x} R[i][y]$$

向右同理：

$$R[x][y]=\sum_{i=y+1}^{m-x} D[x][i]$$

下面/右边的石头个数可以预处理出来。至于方程式中的求和可以直接用树状数组来搞。

还有对于 $1\times 1$ 的矩阵需要特判。（cf样例真良心）

const int N=2005;
char mp[N][N];
int n,m,sx[N][N],sy[N][N],tr[N][N],td[N][N],r[N][N],d[N][N];

inline void addD(int x,int y,int z) { for (;y<=m;y+=y&-y) (td[x][y]+=z)%=ha; }

inline void addR(int x,int y,int z) { for (;y<=n;y+=y&-y) (tr[x][y]+=z)%=ha; }

inline int queryD(int x,int y)
{
    int ans=0;
    for (;y;y-=y&-y) (ans+=td[x][y])%=ha;
    return ans;
}

inline int queryR(int x,int y)
{
    int ans=0;
    for (;y;y-=y&-y) (ans+=tr[x][y])%=ha;
    return ans;
}

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++) scanf("%s",mp[i]+1);
    for (int i=1;i<=n;i++)
        for (int j=m;j;j--)
            sx[i][j]=sx[i][j+1]+(mp[i][j]=='R');
    for (int j=1;j<=m;j++)
        for (int i=n;i;i--)
            sy[i][j]=sy[i+1][j]+(mp[i][j]=='R');
    d[n][m]=r[n][m]=1;
    addD(n,m,1); addR(m,n,1);
    for (int i=n;i;i--)
    {
        for (int j=m;j;j--)
        {
            if (i==n && j==m) continue;
            int sd=sy[i+1][j],sr=sx[i][j+1]; //下/右的石头个数
            if (i+1<=n-sd) d[i][j]=(queryR(j,n-sd)-queryR(j,i)+ha)%ha;
            if (j+1<=m-sr) r[i][j]=(queryD(i,m-sr)-queryD(i,j)+ha)%ha;
            addD(i,j,d[i][j]); addR(j,i,r[i][j]);
        }
    }
    if (n==1 && m==1) return !printf("%d",mp[1][1]=='.'); //特判
    return !printf("%d",(d[1][1]+r[1][1])%ha);
}