Codeforces Round #254 (Div. 2)

题目链接

A题：给定一个棋盘，放B，W不能相邻，输出摆法
思路：模拟国际象棋，B放在白格，A放在黑格即可

B题：给定一些化学物品，给定哪些可以反应，现在一一加入试管，如果试管之前有加过可以反应的，危险度乘2，初始危险度为1，求最小危险度
思路：用并查集，找出有多少个集合，这些先加进去保证不会反应，那么剩下的一个个加进去都乘2即可

C题：求一个最小密度连通子图，子图必须为一个集合，并且两点存在的话，他们的边必须存在
思路：推一推公式发现是选两个点，密度最大的最优，再往后加一个点都会导致密度变小

D题：根据题目给的函数生成A和B数组，求出长度1-n的子数组中的max(ai*bn-i)
思路：如果1比较多的情况，那么之后从后往前找30个左右很快就能找到答案，如果1比较少的情况，那么直接从前往后，在1的情况上找，这样做的合理性在于，对于b数组，基本1的分布情况是30多个左右就会有1个1，所以总体复杂度并不会太高

E题：一个区间，两种操作，可以染上某种颜色，使每个位置增量增加染上和现有颜色之差绝对值，还有一种操作是询问某个区间的总增量
明显的线段树，区间询问区间查询，利用延迟操作求解

代码：

A:

#include <stdio.h>
#include <string.h>

int n, m;
char g[105][105];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
	scanf("%s", g[i]);
    for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
	    if (g[i][j] == '-') continue;
	    if ((i + j) % 2 == 0) g[i][j] = 'B';
	    else g[i][j] = 'W';
	}
    }
    for (int i = 0; i < n; i++)
	printf("%s\n", g[i]);
    return 0;
}

B:

#include <stdio.h>
#include <string.h>

int n, m;
int parent[55];

int find(int x) {
    if (x == parent[x]) return x;
    return parent[x] = find(parent[x]);
}
int main() {
    scanf("%d%d", &n, &m);
    int ans = n;
    int x, y;
    for (int i = 1; i <= n; i++)
	parent[i] = i;
    while (m--) {
	scanf("%d%d", &x, &y);
	int pa = find(x);
	int pb = find(y);
	if (pa != pb) {
	    parent[pa] = pb;
	    n--;
	}
    }
    long long out = 1;
    for (int i = 0; i < ans - n; i++)
	out *= 2;
    printf("%lld\n", out);
    return 0;
}

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int N = 505;
int n, m;
double v[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
	scanf("%lf", &v[i]);
    int a, b;
    double w;
    double ans = 0;
    while (m--) {
	scanf("%d%d%lf", &a, &b, &w);
	ans = max(ans, (v[a] + v[b]) / w);
    }
    printf("%.15lf\n", ans);
    return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100005;
int a[N], b[N], n, d, x, to[N], q[N];

int getnext() {
    x = (x * 37LL + 10007) % 1000000007;
    return x;
}

void initAB() {
    for (int i = 0; i < n; i++)
	a[i] = i + 1;
    for (int i = 0; i < n; i++)
	swap(a[i], a[getnext() % (i + 1)]);
    for (int i = 0; i < n; i++) {
	if (i < d)
	    b[i] = 1;
	else
	    b[i] = 0;
    }
    for (int i = 0; i < n; i++)
	swap(b[i], b[getnext() % (i + 1)]);
}

int main() {
    scanf("%d%d%d", &n, &d, &x);
    initAB();
    for (int i = 0; i < n; i++) {
	to[a[i]] = i;
	if (b[i]) q[++q[0]] = i;
    }
    int s = 30;
    for (int i = 0; i < n; i++) {
	int j;
	for (j = n; j >= n - s; j--) {
	    if (j > 0 && i >= to[j] && b[i - to[j]]) {
		printf("%d\n", j);
		break;
	    }
	}
	if (j < n - s) {
	    int ans = 0;
	    for (int j = 1; j <= q[0] && q[j] <= i; j++)
		ans = max(ans, a[i - q[j]]);
	    printf("%d\n", ans);
	}
    }
    return 0;
}

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int N = 100005;
typedef long long ll;
inline int lson(int x) {return x<<1;}
inline int rson(int x) {return x<<1|1;}

struct Node {
    int l, r;
    ll sum, col, add;
    int size() {return r - l + 1;}
    int mid() {return (r + l)>>1;}
} node[N * 4];

void pushup(int x) {
    node[x].col = (node[lson(x)].col == node[rson(x)].col?node[lson(x)].col : 0);
    node[x].sum = node[lson(x)].sum + node[rson(x)].sum;
}

void pushdown(int x) {
    if (node[x].add) {
	node[lson(x)].add += node[x].add;
	node[rson(x)].add += node[x].add;
	node[lson(x)].sum += node[x].add * node[lson(x)].size();
	node[rson(x)].sum += node[x].add * node[rson(x)].size();
	node[lson(x)].col = node[rson(x)].col = node[x].col;
	node[x].col = node[x].add = 0;
    }
}

void build(int x, int l, int r) {
    node[x].l = l; node[x].r = r;
    node[x].sum = node[x].col = node[x].add = 0;
    if (l == r) {
	node[x].col = l;
	return;
    }
    build(lson(x), l, node[x].mid());
    build(rson(x), node[x].mid() + 1, r);
    pushup(x);
}

void update(int x, int l, int r, ll col) {
    if (node[x].l >= l && node[x].r <= r && node[x].col) {
	node[x].add += abs(node[x].col - col);
	node[x].sum += abs(node[x].col - col) * node[x].size();
	node[x].col = col;
	return;
    }
    pushdown(x);
    if (l <= node[x].mid())
	update(lson(x), l, r, col);
    if (r > node[x].mid())
	update(rson(x), l, r, col);
    pushup(x);
}

long long query(int x, int l, int r) {
    if (node[x].l >= l && node[x].r <= r)
	return node[x].sum;
    pushdown(x);
    long long ans = 0;
    if (l <= node[x].mid())
	ans += query(lson(x), l, r);
    if (r > node[x].mid())
	ans += query(rson(x), l, r);
    return ans;
}

int n, m;

int main() {
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    int q, l, r;
    ll x;
    while (m--) {
	scanf("%d", &q);
	if (q == 1) {
	    scanf("%d%d%lld", &l, &r, &x);
	    update(1, l, r, x);
	}
	else {
	    scanf("%d%d", &l, &r);
	    printf("%lld\n", query(1, l, r));
	}
    }
    return 0;
}