6月3日 AtCoder Grand Contest 025
题目链接:https://agc025.contest.atcoder.jp/assignments

A – Digits Sum

直接枚举就好了,不多说。

B – RGB Coloring

思路:
思路比较巧妙。我们可以将题意进行转化,你可以在n层中选取任意a层涂红,再从n层中选取任意b层涂蓝(如果一层既涂成红,又涂成蓝,那就相当与原题中的涂成绿)。

这样就把原来三种颜色变成两种。于是只要枚举a, b,答案就是之和,其中满足A*a+B*b=K。

代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define LL long long
#define MAXN 300005
#define p 998244353
using namespace std;

LL n, a, b, k, ans, fac[MAXN], inv[MAXN];

LL ksm(LL x, LL y)
{
    LL sum=1;
    while(y)
    {
        if(y&1) sum=(x*sum)%p;
        x=(x*x)%p; y>>=1;
    }
    return sum;
}

void init()
{
    fac[0]=fac[1]=1;
    inv[0]=inv[1]=1;
    for(int i=2; i<=n; i++) inv[i]=(p-p/i)*inv[p%i]%p;
    for(int i=2; i<=n; i++) fac[i]=fac[i-1]*i%p;
    for(int i=2; i<=n; i++) inv[i]=inv[i-1]*inv[i]%p; 
}

LL com(int n, int m)
{
    if(m>n) return 0; 
    return fac[n]*inv[n-m]%p*inv[m]%p;
}

int main()
{
    scanf("%lld%lld%lld%lld", &n, &a, &b, &k);
    if(k==0) {printf("1\n"); return 0;}
    init();
    for(int i=1; a*i<=k && i<=n; i++)
    {
        if((k-a*i)%b!=0) continue;
        int j=(k-a*i)/b;
        ans=(com(n, i)*com(n, j)%p+ans)%p;
    }
    printf("%lld\n", ans);
}

C – Interval Game

思路:
这是一个贪心,每次Aoki一定会选择让Takahashi行走距离最长的区间,而Takahashi一定会走到区间上最靠近自己的端点(如果Takahashi在区间中,则不动)。

因此,Aoki会选择左端点最右或右端点最左的区间,他轮流选择
左区间和右区间,这样使得Takahashi走的最长。

长度就比较好计算(细节见代码),但要注意由于起点和终点在原点,所以要把[0,0]这个区间加入进去。

代码:

#include <bits/stdc++.h>
#define MAXN 100005
#define LL long long 
using namespace std;

LL n, ans, l[MAXN], r[MAXN];

bool CMP1(LL x, LL y) {return x>y;}
bool CMP2(LL x, LL y) {return x<y;}

int main()
{
    scanf("%lld", &n);
    for(int i=1; i<=n; i++) scanf("%lld%lld", &l[i], &r[i]);
    sort(l, l+n+1, CMP1);
    sort(r, r+n+1, CMP2);
    for(int i=0; i<=n; i++) if(l[i]>r[i]) ans+=l[i]-r[i];
    printf("%lld\n", ans*2);
} 

D – Choosing Points

思路:
这其实是一个二分图染色,假设一个点为白色,那么我们可以将与它相距$\sqrt{D}$的点染成黑色,那么这样永远不会有两种颜色相同的点距离为$\sqrt{D}$(由于是二分图,染色是不会冲突)。二分图的证明可以看原题题解,证明了一大堆

于是我们可以依据D1和D2,将这个图进行两次染色。我们可以根据我们染的颜色,确定出n^2个点。原题题解也证明了保证有n^2个点符合要求。
代码:

#include <bits/stdc++.h>
#define MAXN 600
using namespace std;

int n, m, cnt, d[5], col[MAXN][MAXN][2];
bool vis[MAXN][MAXN][2];

void dfs(int x, int y, int a, int b)
{
    if(x<0 || x>m || y<0 || y>m || vis[x][y][a]) return;
    vis[x][y][a]=true; col[x][y][a]=b;
    for(int i=0; i*i<=d[a]; i++)
    {
        int j=sqrt(d[a]-i*i);
        if(i*i+j*j!=d[a]) continue;
        dfs(x+i, y+j, a, 3-b);
        dfs(x-i, y+j, a, 3-b);
        dfs(x+i, y-j, a, 3-b);
        dfs(x-i, y-j, a, 3-b);
    }
}

void debug()
{
    for(int i=0; i<=m; i++)
    {
        for(int j=0; j<=m; j++) printf("%d ", col[i][j][0]);
        printf("\n");
    }
    printf("\n\n");
    for(int i=0; i<=m; i++)
    {
        for(int j=0; j<=m; j++) printf("%d ", col[i][j][1]);
        printf("\n");
    }
}

int main()
{
    scanf("%d%d%d", &n, &d[0], &d[1]);
    m=n*2-1;
    for(int i=0; i<=m; i++)
    for(int j=0; j<=m; j++)
    {
        if(!vis[i][j][0]) dfs(i, j, 0, 1);
        if(!vis[i][j][1]) dfs(i, j, 1, 1);
    }
    for(int i=0; i<=m; i++)
    for(int j=0; j<=m; j++)
    {
        if(col[i][j][0]==1 && col[i][j][1]==1)
        {
            printf("%d %d \n", i, j);
            if(++cnt==n*n) return 0;
        }
    }
} 

发表评论

邮箱地址不会被公开。 必填项已用*标注