省选测试 13
T1
给定一个(n*m)大小的网格, 每个格子里可以填('(')或(')'). 某一行或某一列可以形成一个合法的括号序列.问最大有多少行和多少列是合法的括号序列.
(n,mleq 5000).
分情况构造就好了. (我当时竟然一直在想二分图....)
首先如果(n, m)有奇数, 那么行或列一定不能构成合法的括号序列.
如果都是偶数就判断一下这三种方法哪一种更优就好了 :
(n + m/2 - 4) :
((()))
()()()
((()))
()()()
((()))
()()()
// 每一行都合法, 列最多合法的数量
(n / 2 + m - 1) : 与上一种同理.
(n + m - 4) :
((((((
()()()
)()()(
()()()
)()()(
))))))
// 只有第一行, 第一列, 最后一行, 最后一列不合法
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int n, m, num;
void Work1() {
for(int i = 1;i <= n; i++, puts(""))
for(int j = 1;j <= m; j++) cout << "(";
}
void Work2() {
for(int i = 1;i <= n; i++, puts("")) {
for(int j = 1;j <= m / 2; j++) cout << "(";
for(int j = 1;j <= m / 2; j++) cout << ")";
}
}
void Work3() {
for(int i = 1;i <= n / 2; i++, puts(""))
for(int j = 1;j <= m; j++) cout << "(";
for(int i = 1;i <= n / 2; i++, puts(""))
for(int j = 1;j <= m; j++) cout << ")";
}
void Work4() {
if(n / 2 + m - 1 > n + m - 4 || n + m / 2 - 1 > n + m - 4) {
// cout << n / 2 + m - 1 << " " << n + m / 2 - 1 << "
";
if(m / 2 + n - 1 > n + m - 4 && m / 2 + n - 1 >= n / 2 + m - 1) {
for(int i = 1;i <= n / 2; i++, puts("")) {
for(int j = 1;j <= m / 2; j++) cout << "(";
for(int j = 1;j <= m / 2; j++) cout << ")";
}
for(int i = 1;i <= n / 2; i++, puts(""))
for(int j = 1;j <= m; j++) if(j & 1) cout << "("; else cout << ")";
}
else {
for(int i = 1;i <= m; i++) cout << "("; cout << "
";
for(int i = 2;i < n; i++, puts("")) {
if(i & 1) {
for(int i = 1;i <= m / 2; i++) cout << ")";
for(int i = 1;i <= m / 2; i++) cout << "(";
}
else {
for(int i = 1;i <= m / 2; i++) cout << "(";
for(int i = 1;i <= m / 2; i++) cout << ")";
}
}
for(int i = 1;i <= m; i++) cout << ")"; cout << "
";
}
}
else {
// cout << n + m - 4 << "
";
for(int i = 1;i <= m; i++) cout << "("; cout << "
";
for(int i = 2;i < n; i++, puts("")) {
if(i & 1) {
cout << "(";
for(int j = 2;j < m; j++) if(j & 1) cout << ")"; else cout << "(";
cout << ")";
}
else {
for(int j = 1;j <= m; j++) if(j & 1) cout << "("; else cout << ")";
}
}
for(int i = 1;i <= m; i++) cout << ")";
}
}
int main() {
freopen("butterfly.in","r",stdin); freopen("butterfly.out","w",stdout);
scanf("%d %d", &n, &m);
if((n & 1) && (m & 1)) Work1();
else if(n & 1) Work2();
else if(m & 1) Work3();
else Work4();
fclose(stdin); fclose(stdout);
return 0;
}
/*
2 2
*/
/*
2 3
*/
T2
给定一个(n)个点, (m)条边的无向联通图. (maxflow(x,y))代表以(x)为源点, (y)为汇点的最大流.如果说所有的边权为1, 那么所有的(maxflow(x,y)leq 2), 可是边权为(c_i)(hhhhhha). 给定p, 求(sum_{s=1}^nsum_{t=1}^{n} maxflow(s,t)*p^{(s-1)n+t})对998244353取模的值.
(n leq 300000, m leq 500000)
生成树, 并查集.
因为任意两点的最大流不超过2, 所以可以判断整个图是一个仙人掌.
啥是仙人掌呢? 就是一个连通图, 图上的任意一条边都只被包含于一个环内.
证明 : 假如说图上友谊条边被包含在两个环内, 就像下图一样, 那么他们两个点之间最大流一定大于2.那么就与题目条件不符了.
(好丑.....)
如果这道题给的是一棵树就好做了, 我们直接把边从大到小排序, 然后并查集维护一下就行了. 但问题是它是仙人掌而不是树.
那我们把它转化成树不就好了. 我们找到每一个环内的最小值(因为这条边一定是对最大流有贡献的). 我们把它删掉, 然后让这个环上的其它边都加上这个边的权值, 整个最大流不变.
所以我们成功的把它转化成了树上问题, 然后就好做了.
#include <bits/stdc++.h>
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N = 3e5 + 5, M = 6e5, mod = 998244353, inf = 1e9;
int n, m, p, cnt, ans;
int fa[N], val[M], dep[N], vis[M], val2[N], head[N], pow_p[N], f[N][21];
struct edge { int to, nxt, val; } e[N << 1];
struct Edge { int x, y, val; } E[M], L[N];
int ksm(int x, int y) {
int res = 1;
while(y) { if(y & 1) res = 1ll * res * x % mod; x = 1ll * x * x % mod; y >>= 1; }
return res;
}
void make_pre() {
pow_p[0] = 1;
for(int i = 1;i < N; i++) pow_p[i] = 1ll * pow_p[i - 1] * p % mod;
}
void add(int x, int y, int z) {
e[++ cnt].nxt = head[x]; head[x] = cnt; e[cnt].to = y; e[cnt].val = z;
}
int cmp(Edge x, Edge y) {
return x.val > y.val;
}
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void get_f(int x, int Fa) {
f[x][0] = Fa; dep[x] = dep[Fa] + 1;
for(int i = 1;i <= 20; i++) f[x][i] = f[f[x][i - 1]][i - 1];
for(int i = head[x]; i ; i = e[i].nxt) if(e[i].to != Fa) get_f(e[i].to, x);
}
int LCA(int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
for(int i = 20;i >= 0; i--) if(dep[x] - dep[y] >= (1 << i)) x = f[x][i];
if(x == y) return x;
for(int i = 20;i >= 0; i--) if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
return f[x][0];
}
void Kruskal() {
sort(E + 1, E + m + 1, cmp);
for(int i = 1;i <= n; i++) fa[i] = i;
for(int i = 1;i <= m; i++) {
int x = find(E[i].x), y = find(E[i].y);
if(x == y) continue ;
fa[x] = y; vis[i] = 1;
add(E[i].x, E[i].y, E[i].val); add(E[i].y, E[i].x, E[i].val);
}
get_f(1, 0);
for(int i = 1;i <= m; i++) {
if(vis[i]) continue ;
int x = E[i].x, y = E[i].y, val = E[i].val;
int lca = LCA(x, y);
while(x != lca) {
int tmp = f[x][0];
for(int ii = head[tmp]; ii ; ii = e[ii].nxt)
if(e[ii].to == x) { e[ii].val += val; e[ii ^ 1].val += val; break; }
x = tmp;
}
while(y != lca) {
int tmp = f[y][0];
for(int ii = head[tmp]; ii ; ii = e[ii].nxt)
if(e[ii].to == y) { e[ii].val += val; e[ii ^ 1].val += val; break; }
y = tmp;
}
}
}
void get_tree(int x, int Fa) {
for(int i = head[x]; i ; i = e[i].nxt) {
int y = e[i].to; if(y == Fa) continue ;
++ cnt; L[cnt].x = x; L[cnt].y = y; L[cnt].val = e[i].val;
get_tree(y, x);
}
}
int main() {
freopen("sakura.in","r",stdin); freopen("sakura.out","w",stdout);
n = read(); m = read(); p = read();
cnt = 1;
for(int i = 1;i <= m; i++) {
E[i].x = read(); E[i].y = read(); E[i].val = read();
}
make_pre();
Kruskal();
// cout << "!!!!!!
";
cnt = 0;
get_tree(1, 0);
sort(L + 1, L + cnt + 1, cmp);
for(int i = 1;i <= n; i++) fa[i] = i, val[i] = pow_p[i], val2[i] = ksm(pow_p[i], n);
for(int i = 1;i <= cnt; i++) {
int x = find(L[i].x), y = find(L[i].y);
// cout << x << " " << y << " " << L[i].val << " " << val[x] << " " << val[y] << "
";
ans = (ans + 1ll * L[i].val * val2[x] % mod * val[y] % mod) % mod;
ans = (ans + 1ll * L[i].val * val2[y] % mod * val[x] % mod) % mod;
fa[x] = y; val[y] = (val[y] + val[x]) % mod; val2[y] = (val2[y] + val2[x]) % mod;
}
// cout << pow_p[n] << " " << ksm(pow_p[n], mod - 2) << "
";
ans = 1ll * ans * ksm(pow_p[n], mod - 2) % mod;
printf("%d
", ans);
fclose(stdin); fclose(stdout);
return 0;
}
/*
3 3 1
1 2 5
2 3 6
3 1 5
5 12 1
1 2 5
2 3 6
3 1 5
1 4 1
1 5 1
4 5 2
5 6 1
6 7 1
5 7 1
3 6 1
6 8 1
3 8 1
*/
T3
神仙题, 不可做......
T4 ??
就是今天下午第一次打了一次完整的CF嘛, 感觉自己好菜....
A,B题很轻松就过了, 然后去看C题.
想了一会就搞出来了, 乱搞的不知道为啥对. 机房大佬说这是个鸽笼原理, 说我的程序在数据小的时候会错. 果然考后被Hack了....
最后半个小时去做的D题, 但是没做出来, 考后才知道用exgcd合并啥的可以做, 感觉也不难, 但就是没想出来.
总之第一次打CF成绩并不好, 只有两个最简单的题的分(第三题被Hack了减分了qwq).
但是还是了解了不少的, 比如怎么Hack, 为什么先做后边的题(因为那样得的分高, 时间越长得到的分就越少).QWQ