【AtCoder】ARC093

2024-02-05 14:47:34

C - Traveling Plan

相当于一个环，每次删掉i点到两边的距离，加上新相邻的两个点的距离

代码

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define space putchar(' ')

#define enter putchar('\n')

#define mp make_pair

#define MAXN 100005

//#define ivorysi

using namespace std;

typedef long long int64;

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) {putchar('-');x = -x;}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

int N;

int64 A[100005],ans;

int main() {

#ifdef ivorysi

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

#endif

    read(N);

    for(int i = 1 ; i <= N ; ++i) read(A[i]);

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

	ans += abs(A[i] - A[i - 1]);

    }

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

	int64 tmp = ans;

	tmp -= abs(A[i] - A[i - 1]) + abs(A[i] - A[i + 1]);

	tmp += abs(A[i - 1] - A[i + 1]);

	out(tmp);enter;

    }

}

D - Grid Components

每次这样

先拎出一个黑联通块和一个白联通块

黑黑黑黑黑黑

白黑白黑白黑

黑黑黑黑黑黑

白黑白黑白黑

黑黑黑黑黑黑

这样每两行50个往下消，白的构造黑的同理

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define space putchar(' ')

#define enter putchar('\n')

#define mp make_pair

#define MAXN 100005

//#define ivorysi

using namespace std;

typedef long long int64;

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) {putchar('-');x = -x;}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

int A,B,w = 100,h = 0;

char a[105][105];

void Calc(int R,char W,char B)  {

    ++h;

    for(int i = 1 ; i <= w ; ++i) a[h][i] = B;

    if(!R) return;

    while(R >= 50) {

	R -= 50;

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

	    if(i & 1) a[h + 1][i] = W;

	    else a[h + 1][i] = B;

	}

	for(int i = 1 ; i <= w ; ++i) a[h + 2][i] = B;

	h += 2;

    }

    if(R) {

	int t = 1;

	while(R--) {

	    a[h + 1][t] = W;

	    a[h + 1][t + 1] = B;

	    t += 2;

	}

	for(int i = t ; i <= w ; ++i) a[h + 1][i] = B;

	for(int i = 1 ; i <= w ; ++i) a[h + 2][i] = B;

	h += 2;

    }

}

void Solve() {

    read(A);read(B);

    --A;--B;

    Calc(A,'.','#');Calc(B,'#','.');

    out(h);space;out(w);enter;

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

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

	    putchar(a[i][j]);

	}

	enter;

    }

}

int main() {

#ifdef ivorysi

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

#endif

    Solve();

}

E - Bichrome Spanning Tree

我们随意求一个生成树\(T\)出来，然后给每个非树边求一个\(diff(e)\)表示边的值减去\(u,v\)上路径最大值

我们设\(D = X - T\)

\(equal\)是\(diff(e) == D\)的个数

\(upper\)是\(diff(e) > D\)的个数

\(lower\)是\(diff(e) < D\)的个数

然后对于\(D < 0\)无解

对于\(D = 0\)

我们可以对于树上的边两种颜色染色\((2^{N - 1} - 2)2^{M - N + 1}\)

如果树上的边都是一种颜色，那么答案是\(2(2^{equal} - 1)2^{upper}\)，就是\(diff(e) == D\)的边至少有一个不同颜色的，大于的边随意染色

对于\(D > 0\)

我们对于树上的边和\(lower\)边必须用同一种颜色染色

答案是\(2(2^{equal} - 1)2^{upper}\)

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define space putchar(' ')

#define enter putchar('\n')

#define mp make_pair

#define MAXN 2005

//#define ivorysi

using namespace std;

typedef long long int64;

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) {putchar('-');x = -x;}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

const int MOD = 1000000007;

int N,M,bl[MAXN],fa[MAXN],dep[MAXN],up,eq;

int64 X,T,faE[MAXN];

bool vis[MAXN];

struct Edge {

    int to,next;int64 val;

}E[MAXN * 2];

int head[MAXN],sumE;

struct node {

    int u,v;int64 val;

    friend bool operator < (const node &a,const node &b) {

	return a.val < b.val;

    }

}Ed[MAXN];

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;

}

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;

}

void update(int &x,int y) {

    x = inc(x,y);

}

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

    E[++sumE].to = v;

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

    E[sumE].val = c;

    head[u] = sumE;

}

void dfs(int u) {

    dep[u] = dep[fa[u]] + 1;

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

	int v = E[i].to;

	if(v != fa[u]) {

	    fa[v] = u;

	    faE[v] = E[i].val;

	    dfs(v);

	}

    }

}

int getfa(int u) {

    return bl[u] == u ? u : bl[u] = getfa(bl[u]);

}

int64 Query(int u,int v) {

    if(dep[u] < dep[v]) swap(u,v);

    int64 res = 0;

    while(dep[u] > dep[v]) {

	res = max(res,faE[u]);

	u = fa[u];

    }

    if(u == v) return res;

    while(u != v) {

	res = max(res,faE[u]);

	res = max(res,faE[v]);

	u = fa[u];v = fa[v];

    }

    return res;

}

void Solve() {

    read(N);read(M);read(X);

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

	read(Ed[i].u);read(Ed[i].v);read(Ed[i].val);

    }

    for(int i = 1 ; i <= N ; ++i) bl[i] = i;

    sort(Ed + 1,Ed + M + 1);

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

	if(getfa(Ed[i].u) != getfa(Ed[i].v)) {

	    vis[i] = 1;

	    T += Ed[i].val;

	    add(Ed[i].u,Ed[i].v,Ed[i].val);

	    add(Ed[i].v,Ed[i].u,Ed[i].val);

	    bl[getfa(Ed[i].u)] = getfa(Ed[i].v);

	}

    }

    dfs(1);

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

	if(!vis[i]) {

	    int64 d = Ed[i].val - Query(Ed[i].v,Ed[i].u);

	    if(d == X - T) ++eq;

	    else if(d > X - T) ++up;

	}

    }

    if(X < T) {puts("0");return;}

    else if(X == T) {

	int ans = 0;

	update(ans,mul(inc(fpow(2,N - 1),MOD - 2),fpow(2,M - N + 1)));

	update(ans,mul(mul(2,inc(fpow(2,eq),MOD - 1)),fpow(2,up)));

	out(ans);enter;

    }

    else {

	int ans = 0;

	update(ans,mul(mul(2,inc(fpow(2,eq),MOD - 1)),fpow(2,up)));

	out(ans);enter;

    }

}

int main() {

#ifdef ivorysi

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

#endif

    Solve();

}

F - Dark Horse

我们把1当做放在第一个，之后的答案乘上\(2^N\)

答案显然就是\(2^0,2^1,2^2...2^(N - 1)\)大小的集合的最小值不为给定的\(M\)个数之一

我们计算\(f(S)\)表示\(S\)所代表的集合的最小值都是\(M\)个数之一，剩下的随意的方案数

答案就是容斥\(\sum(-1)^{|S|}f(S)\)

设\(dp[i][S]\)表示考虑到第\(i\)大的\(A\)，然后集合为\(S\)的都填满且最小值为\(M\)个数之一的方案数

因为从大到小填数可以很容易算出来当前集合还有几个可以用的

\(f[S] = dp[M][S]\)

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define space putchar(' ')

#define enter putchar('\n')

#define mp make_pair

//#define ivorysi

using namespace std;

typedef long long int64;

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) {putchar('-');x = -x;}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

const int MOD = 1000000007;

int fac[(1 << 16) + 5],invfac[(1 << 16) + 5],inv[(1 << 16) + 5],N,M;

int A[25],f[(1 << 16) + 5],dp[17][(1 << 16) + 5],cnt[(1 << 16) + 5];

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;

}

int C(int n,int m) {

    if(n < m) return 0;

    return mul(fac[n],mul(invfac[m],invfac[n - m]));

}

int lowbit(int x) {

    return x & (-x);

}

void update(int &x,int y) {

    x = inc(x,y);

}

void Solve() {

    read(N);read(M);

    for(int i = 1 ; i <= M ; ++i) read(A[i]);

    inv[1] = 1;

    for(int i = 2 ; i <= (1 << N) ; ++i) inv[i] = mul(inv[MOD % i],MOD - MOD / i);

    fac[0] = invfac[0] = 1;

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

	fac[i] = mul(fac[i - 1],i);

	invfac[i] = mul(invfac[i - 1],inv[i]);

    }

    sort(A + 1,A + M + 1);

    dp[0][0] = 1;

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

	int t = M - i + 1;

	for(int S = 0 ; S < (1 << N) ; ++S) {

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

		if(!(S >> j & 1)) {

		    update(dp[i][S ^ (1 << j)],mul(dp[i - 1][S],mul(C((1 << N) - A[t] - S,(1 << j) - 1),fac[1 << j])));

		}

	    }

	    update(dp[i][S],dp[i - 1][S]);

	}

    }

    int ans = 0;

    for(int S = 0 ; S < (1 << N) ; ++S) {

	if(S) cnt[S] = cnt[S - lowbit(S)] + 1;

	int t = mul(dp[M][S],fac[(1 << N) - 1 - S]);

	if(cnt[S] & 1) update(ans,MOD - t);

	else update(ans,t);

    }

    ans = mul(ans,1 << N);

    out(ans);enter;

}

int main() {

#ifdef ivorysi

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

#endif

    Solve();

}
上一篇：java.lang.Exception: DEBUG STACK TRACE for PoolBackedDataSource.close().


下一篇：菜鸟学Java（七）——Ajax+Servlet实现无刷新下拉联动