【AtCoder】ARC089

C - Traveling

先看能不能走到，再看看奇偶性是否相同

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define pdi pair<db,int>

#define mp make_pair

#define pb push_back

#define enter putchar('\n')

#define space putchar(' ')

#define eps 1e-8

#define mo 974711

#define MAXN 200005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 + c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

int N;

void Solve() {

    int pt,px,py;

    int t,x,y;

    read(N);

    pt = 0,px = 0,py = 0;

    for(int i = 1 ; i <= N ; ++i) {

	read(t);read(x);read(y);

	int k = abs(x - px) + abs(y - py);

	if(k > t - pt) {

	    puts("No");return;

	}

	if((k ^ t) & 1) {puts("No");return;}

    }

    puts("Yes");

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

    return 0;

}

D - Checker

我们计算右下角在\((-2k,-2k)\)到\((-1,-1)\)这个区域内，每个点所在的格子的颜色

发现根据右下角的位置会分成九个小块，把九个小块里的颜色和需求一样的矩阵用差分矩阵加，最后统计前缀和中最大的即可

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define pdi pair<db,int>

#define mp make_pair

#define pb push_back

#define enter putchar('\n')

#define space putchar(' ')

#define eps 1e-8

#define mo 974711

#define MAXN 200005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 + c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

int N,K;

int a[2005][2005];

int dx[5],dy[5];

void add(int x1,int y1,int x2,int y2) {

    if(x1 > x2 || y1 > y2) return;

    a[x1][y1]++;a[x2 + 1][y2 + 1]++;

    a[x1][y2 + 1]--;a[x2 + 1][y1]--;

}

void Solve() {

    read(N);read(K);

    int x,y;char c[5];

    for(int i = 1 ; i <= N ; ++i) {

	read(x);read(y);scanf("%s",c + 1);

	++x;++y;

	int tx = x % K,ty = y % K;

	int now = ((x / K) ^ (y / K)) & 1,u;

	if(c[1] == 'W') u = 0;

	else u = 1;

	dx[1] = K - tx,dx[2] = K,dx[3] = tx;

	dy[1] = K - ty,dy[2] = K,dy[3] = ty;

	for(int i = 1 ; i <= 3 ; ++i) dx[i] += dx[i - 1],dy[i] += dy[i - 1];

	for(int h = 1 ; h <= 3 ; ++h) {

	    for(int t = 1 ; t <= 3 ; ++t) {

		int w = (h ^ t ^ now) & 1;

		if(w == u) {

		    add(dx[h - 1] + 1,dy[t - 1] + 1,dx[h],dy[t]);

		}

	    }

	}

    }

    int ans = 0;

    for(int i = 1 ; i <= 2 * K ; ++i) {

	for(int j = 1 ; j <= 2 * K ; ++j) {

	    a[i][j] = a[i][j] + a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1];

	    ans = max(ans,a[i][j]);

	}

    }

    out(ans);enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

    return 0;

}

E - GraphXY

显然\(ax + by + f(a,b) >= d(x,y)\)

\(a\)最多100个\(b\)最多100个，可以都构建出来

然后对于每个\((a,b)\)求出来\(f(a,b)\)

最后再对于每个\(x,y\)判一遍\(d(x,y)\)是否合法

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define pdi pair<db,int>

#define mp make_pair

#define pb push_back

#define enter putchar('\n')

#define space putchar(' ')

#define eps 1e-8

#define mo 974711

#define MAXN 200005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 + c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

int A,B;

int d[15][15];

int f[105][105],tot,gx[105],gy[105],S,T;

pii p[305 * 305];

int val[305 * 305],cnt;

int check(int x,int y) {

    int res = 1000000;

    for(int i = 0 ; i <= 100 ; ++i) {

	for(int j = 0 ; j <= 100 ; ++j) {

	    res = min(res,f[i][j] + i * x + j * y);

	}

    }

    return res;

}

void Solve() {

    read(A);read(B);

    for(int i = 1 ; i <= A ; ++i) {

	for(int j = 1 ; j <= B ; ++j) {

	    read(d[i][j]);

	}

    }

    for(int i = 0 ; i <= 100 ; ++i) {

	for(int j = 0 ; j <= 100 ; ++j) {

	    for(int k = 1 ; k <= A ; ++k) {

		for(int h = 1 ; h <= B ; ++h) {

		    f[i][j] = max(f[i][j],d[k][h] - k * i - h * j);

		}

	    }

	}

    }

    for(int i = 1 ; i <= A ; ++i) {

	for(int j = 1 ; j <= B ; ++j) {

	    if(check(i,j) != d[i][j]) {

		puts("Impossible");

		return;

	    }

	}

    }

    puts("Possible");

    S = ++tot;

    gx[0] = S;

    for(int i = 1 ; i <= 100 ; ++i) {

	gx[i] = ++tot;

	p[++cnt] = mp(gx[i - 1],gx[i]);

	val[cnt] = -2;

    }

    T = ++tot;

    gy[0] = T;

    for(int i = 1 ; i <= 100 ; ++i) {

	gy[i] = ++tot;

	p[++cnt] = mp(gy[i],gy[i - 1]);

	val[cnt] = -1;

    }

    for(int i = 0 ; i <= 100 ; ++i) {

	for(int j = 0 ; j <= 100 ; ++j) {

	    p[++cnt] = mp(gx[i],gy[j]);

	    val[cnt] = f[i][j];

	}

    }

    out(tot);space;out(cnt);enter;

    for(int i = 1 ; i <= cnt ; ++i) {

	out(p[i].fi);space;out(p[i].se);space;

	if(val[i] < 0) {

	    if(val[i] == -2) {puts("X");}

	    else puts("Y");

	}

	else {out(val[i]);enter;}

    }

    out(S);space;out(T);enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

    return 0;

}

F - ColoringBalls

本来以为是个dp没想到是个搜索加剪枝，迷的很。。然而就是搜索我都写跪了……菜的要死QAQ

我们对于白块分成的每一个小块进行分组

然后把相邻的同颜色合起来，比如说RRBBRR变成RBR

然后我们根据所需要达到的最小操作次数来分组

1次操作 r R

2次操作 rb B BR RB BRB

3次操作 rb? BRB RBRB BRBR RBRBR

4次操作 rb?? BRBRB RBRBRB BRBRBR RBRBRBR

问号表示可以任意一种操作

然后对于一种序列，我们可以把必须要填的位置填上，然后挖上几个坑，往里扔数，方案数就是组合数了

例如序列 2 2 3

我们必须要填的是

BWBWBRB

然后挖的坑是

W/R/B/R/W/R/B/R/W/R/B/R/B/R/W

往坑里扔数就行

怎么判断一个序列合不合法，找出所有的r以及它们最靠左没有被搭配过的b，从后往前枚举r，从小到大枚举所需要操作序列长度，对于一个b加上我后面需要用的位置的个数，统计一个后缀和看看合不合法即可

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define pdi pair<db,int>

#define mp make_pair

#define pb push_back

#define enter putchar('\n')

#define space putchar(' ')

#define eps 1e-8

#define mo 974711

#define MAXN 1000005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 + c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

const int MOD = 1000000007;

int N,K,C[1005][1005],L[75],fac[1005],invfac[1005],cnt;

int sum[75],pos[75],tot,ans,matc[75];

char s[75];

bool vis[75];

int inc(int a,int b) {

    return a + b >= MOD ? a + b - MOD : a + b;

}

int mul(int a,int b) {

    return 1LL * a * b % MOD;

}

void update(int &x,int y) {

    x = inc(x,y);

}

int fpow(int x,int c) {

    int res = 1,t = x;

    while(c) {

        if(c & 1) res = mul(res,t);

        t = mul(t,t);

        c >>= 1;

    }

    return res;

}

bool check() {

    if(tot < cnt) return false;

    memset(sum,0,sizeof(sum));

    int p = 1;

    for(int i = cnt ; i >= 1 ; --i) {

	sum[pos[i]]++;

	if(L[p] >= 2) {

	    if(!matc[pos[i]]) return false;

	    sum[matc[pos[i]]] += L[p] - 1;

	}

	++p;

    }

    for(int i = K ; i >= 1 ; --i) {

	sum[i] += sum[i + 1];

	if(sum[i] > K - i + 1) return false;

    }

    return true;

}

bool dfs(int pre,int dep,int len) {

    cnt = dep;

    if(!check()) return false;

    int k = 1 + cnt;

    for(int i = 1 ; i <= cnt ; ++i) {

        if(L[i] == 1) ++k;

        else k += 2 * L[i] - 1;

    }

    int res = C[N - len + k - 1][k - 1];

    res = mul(res,fac[cnt]);

    int t = 0;

    for(int i = 1 ; i <= cnt ; ++i) {

        if(L[i] != L[i - 1]) {

            res = mul(res,invfac[t]);

            t = 0;

        }

        ++t;

    }

    res = mul(res,invfac[t]);

    update(ans,res);

    if(dep + 1 > tot) return true;

    for(int i = pre ; i <= 70 ; ++i) {

        int tl = len;

        if(dep != 0) ++tl;

        if(i == 1 || i == 2) tl += 1;

        else tl += i - 2 + i - 1;

        if(tl > N) break;

        L[dep + 1] = i;

        if(!dfs(i,dep + 1,tl)) break;

    }

    return true;

}

void Solve() {

    read(N);read(K);

    scanf("%s",s + 1);

    C[0][0] = 1;

    for(int i = 1 ; i <= 1000 ; ++i) {

        C[i][0] = 1;

        for(int j = 1 ; j <= i ; ++j) {

            C[i][j] = inc(C[i - 1][j - 1],C[i - 1][j]);

        }

    }

    fac[0] = 1;

    for(int i = 1 ; i <= 1000 ; ++i) fac[i] = mul(fac[i - 1],i);

    invfac[1000] = fpow(fac[1000],MOD - 2);

    for(int i = 999 ; i >= 0 ; --i) invfac[i] = mul(invfac[i + 1],i + 1);

    tot = 0;

    for(int i = 1 ; i <= K ; ++i) {

        if(s[i] == 'r') {

	    pos[++tot] = i;

	    for(int j = i + 1 ; j <= K ; ++j) {

		if(s[j] == 'b' && !vis[j]) {matc[i] = j;vis[j] = 1;break;}

	    }

	}

    }

    dfs(1,0,0);

    out(ans);enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

    return 0;

}

巴特西

【AtCoder】ARC089

C - Traveling

D - Checker

E - GraphXY

F - ColoringBalls

最新文章

热门文章