【AtCoder】ARC074

时间：2022-08-21 03:11:34

ARC 074

C - Chocolate Bar

直接枚举第一刀横切竖切，然后另一块要求如果横切分成\(H / 2\)竖切分成\(W/2\)即可

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define MAXN 200005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

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

    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);

}

int64 H,W,ans = 1e18;

int64 maxdec(int64 a,int64 b,int64 c) {

    return max(max(abs(a - b),abs(a - c)),abs(b - c));

}

void Solve() {

    read(H);read(W);

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

	int64 h = (H - i) / 2;

	ans = min(ans,maxdec(i * W,h * W,(H - i - h) * W));

	int64 t = W / 2;

	ans = min(ans,maxdec(i * W,t * (H - i),(W - t) * (H - i)));

    }

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

	int64 h = (W - i) / 2;

	ans = min(ans,maxdec(i * H,h * H,(W - i - h) * H));

	int64 t = H / 2;

	ans = min(ans,maxdec(i * H,t * (W - i),(H - t) * (W - i)));

    }

    out(ans);enter;

}

int main() {

#ifdef ivorysi

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

#endif

    Solve();

}

D - 3N Numbers

直接算前i个数最大的N个是多少，后i个数最小的是多少，可以用set

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define MAXN 300005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

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

    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);

}

struct cmp {

    bool operator () (const int &a,const int &b) const {

	return a > b;

    }

};

int N,a[MAXN];

int64 f[MAXN],b[MAXN];

multiset<int> s2;

multiset<int,cmp> s1;

void Solve() {

    read(N);

    for(int i = 1 ; i <= 3 * N ; ++i) read(a[i]);

    int64 sum = 0;

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

	s1.insert(a[i]);sum += a[i];

	if(s1.size() > N) {

	    auto t = *(--s1.end());

	    s1.erase(--s1.end());

	    sum -= t;

	}

	f[i] = sum;

    }

    sum = 0;

    for(int i = 3 * N ; i >= 1 ; --i) {

	s2.insert(a[i]);sum += a[i];

	if(s2.size() > N) {

	    auto t = *(--s2.end());

	    s2.erase(--s2.end());

	    sum -= t;

	}

	b[i] = sum;

    }

    int64 ans = f[N] - b[N + 1];

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

	ans = max(ans,f[i] - b[i + 1]);

    }

    out(ans);enter;

}

int main() {

#ifdef ivorysi

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

#endif

    Solve();

}

E - RGB Sequence

就是记录\(dp[r][g][b]\)为上一次出现r的位置，出现g的位置和出现b的位置，把不合法的状态标成0

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

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

    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,M;

int dp[305][305][305],sum[3][305][305];

vector<pii > v[305];

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;

}

bool check(int r,int g,int b,int len) {

    for(int i = 0 ; i < v[len].size() ; ++i) {

	pii t = v[len][i];

	int cnt = 0;

	if(r >= t.fi) ++cnt;

	if(g >= t.fi) ++cnt;

	if(b >= t.fi) ++cnt;

	if(cnt != t.se) return false;

    }

    return true;

}

void increase(int r,int g,int b) {

    sum[0][g][b] = inc(sum[0][g][b],dp[r][g][b]);

    sum[1][r][b] = inc(sum[1][r][b],dp[r][g][b]);

    sum[2][r][g] = inc(sum[2][r][g],dp[r][g][b]);

}

void Solve() {

    read(N);read(M);

    int l,r,x;

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

	read(l);read(r);read(x);

	v[r].pb(mp(l,x));

    }

    dp[0][0][0] = 1;

    sum[0][0][0] = 1;

    sum[1][0][0] = 1;

    sum[2][0][0] = 1;

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

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

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

		dp[i][j][k] = sum[0][j][k];

		dp[j][i][k] = sum[1][j][k];

		dp[j][k][i] = sum[2][j][k];

		if(!check(i,j,k,i)) dp[i][j][k] = 0;

		if(!check(j,i,k,i)) dp[j][i][k] = 0;

		if(!check(j,k,i,i)) dp[j][k][i] = 0;

	    }

	}

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

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

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

		increase(i,j,k);

		increase(j,i,k);

		increase(j,k,i);

	    }

	}

    }

    int ans = 0;

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

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

	    ans = inc(ans,dp[N][i][j]);

	    ans = inc(ans,dp[i][N][j]);

	    ans = inc(ans,dp[i][j][N]);

	}

    }

    out(ans);enter;

}

int main() {

#ifdef ivorysi

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

#endif

    Solve();

}

F - Lotus Leaves

行列拆点，对于然后每个叶子新建一个点往对应的行列连边

对于起点和重点的边建成无穷大

然后跑网络流求最小割即可

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define MAXN 200005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

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

    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);

}

struct node {

    int to,next,cap;

}E[MAXN];

int sumE = 1,head[MAXN];

int H,W,Ncnt,S,T;

char s[105][105];

void add(int u,int v,int c) {

    E[++sumE].to = v;

    E[sumE].next = head[u];

    E[sumE].cap = c;

    head[u] = sumE;

}

void addtwo(int u,int v,int c) {

    add(u,v,c);add(v,u,0);

}

int gap[MAXN],dis[MAXN];

int isap(int u,int aug) {

    if(u == T) return aug;

    int flow = 0;

    for(int i = head[u] ; i ;i = E[i].next) {

	int v = E[i].to;

	if(E[i].cap) {

	    if(dis[v] + 1 == dis[u]) {

		int t = isap(v,min(aug - flow,E[i].cap));

		flow += t;

		E[i].cap -= t;

		E[i ^ 1].cap += t;

		if(aug == flow) return flow;//这块写错了，如果能满流的话应该返回而不是让dis++

		if(dis[S] >= Ncnt) return flow;

	    }

	}

    }

    --gap[dis[u]];

    if(!gap[dis[u]]) {dis[S] = Ncnt;return flow;}

    dis[u]++;

    ++gap[dis[u]];

    return flow;

}

void Solve() {

    read(H);read(W);

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

	scanf("%s",s[i] + 1);

    }

    Ncnt = H + W;

    pii p[2];

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

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

	    if(s[i][j] != '.') {

		++Ncnt;

		int t = 0;

		if(s[i][j] == 'o') t = 1;

		else t = 0x7fffffff;

		addtwo(Ncnt,i,t);addtwo(i,Ncnt,t);

		addtwo(j + H,Ncnt,t);addtwo(Ncnt,j + H,t);

		if(s[i][j] == 'S') {p[0] = mp(i,j);S = Ncnt;}

		if(s[i][j] == 'T') {p[1] = mp(i,j);T = Ncnt;}

	    }

	}

    }

    if(p[0].fi == p[1].fi || p[0].se == p[1].se) {puts("-1");return;}

    int ans = 0;

    while(dis[S] < Ncnt) ans += isap(S,0x7fffffff);

    out(ans);enter;

}

int main() {

#ifdef ivorysi

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

#endif

    Solve();

}

相关文章