T1 动物园
题意
给定一个带点权图，求每两个点之间路径上最小点权的最大值之和。
怎么做
点权下方边权跑最大生成树（边权是两个点中的最小值），这样就可以保证每条路径都是两个点之间最小点权的最大值。
考虑统计答案，这个路径对答案的贡献是两边经过他的点的个数 * 2。在跑最小生成树的时候使用带权并查集维护两边点的数量即可。
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC target ("avx2")
namespace fdata
{
inline char nextchar()
{
static const int BS = 1 << 21;
static char buf[BS], *st, *ed;
if (st == ed)
ed = buf + fread(st = buf, 1, BS, stdin);
return st == ed ? -1 : *st++;
}
#ifdef lky233
#define nextchar getchar
#endif
template <typename Y>
inline void poread(Y &ret)
{
ret = 0;
char ch;
while (!isdigit(ch = nextchar()))
;
do
ret = ret * 10 + ch - '0';
while (isdigit(ch = nextchar()));
}
#undef nextcar
} // namespace fdata
using fdata::poread;
using namespace std;
const int MAXN = 1e5 + 10;
const int MAXM = 1e6 + 10;
int n, m;
long long ans = 0;
int val[MAXN];
int a[MAXN], siz[MAXN];
inline void init()
{
for (register int i = 1; i <= n; ++i)
a[i] = i;
for (register int i = 1; i <= n; ++i)
siz[i] = 1;
}
int find(int x)
{
return a[x] == x ? x : a[x] = find(a[x]);
}
struct road
{
int x, y, w;
inline bool operator<(const road &t) const
{
return w > t.w;
}
} r[MAXM];
int main()
{
poread(n), poread(m);
init();
for (register int i = 1; i <= n; ++i)
poread(val[i]);
for (register int i = 1; i <= m; ++i)
{
poread(r[i].x), poread(r[i].y);
r[i].w = min(val[r[i].x], val[r[i].y]);
}
sort(r + 1, r + m + 1);
for (register int i = 1; i <= m; ++i)
{
register int x = find(r[i].x);
register int y = find(r[i].y);
if (x == y)
continue;
ans += siz[x] * siz[y] * r[i].w * 2ll;
a[x] = y;
siz[y] += siz[x];
}
printf("%lld\n", ans);
}T2 线段计数
题意
插入或删除线段，询问插入的线段覆盖了几个线段。线段长度递增
怎么做
我们考虑线段完全覆盖某一个线段的情况：
R >= r && l >= L
这样我们开两个树状数组维护区间左端点个数以及区间右端点个数。每次查询时答案就是 右端点左侧的右端点个数 减去 左端点左侧的左端点个数。
这个方法会在下面这个情况出锅：
但由于数据保证了线段长度单调递增，这个情况不存在啦啦啦。
建议：贪婪大陆
//多测不清空，爆零两行泪
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
namespace fdata
{
inline char nextchar()
{
static const int BS = 1 << 21;
static char buf[BS], *st, *ed;
if (st == ed)
ed = buf + fread(st = buf, 1, BS, stdin);
return st == ed ? -1 : *st++;
}
#ifdef lky233
#define nextchar getchar
#endif
template <typename Y>
inline void poread(Y &res)
{
res = 0;
bool bo = 0;
char c;
while (((c = nextchar()) < '0' || c > '9') && c != '-')
;
if (c == '-')
bo = 1;
else
res = c - 48;
while ((c = nextchar()) >= '0' && c <= '9')
res = (res << 3) + (res << 1) + (c - 48);
if (bo)
res = ~res + 1;
// std::cerr << res << std::endl;
}
#undef nextcar
} // namespace fdata
using fdata::poread;
using namespace std;
namespace lky
{
const int MAXN = 2e5 + 10;
int n, m, tot;
//封装是个好东西
class T
{
public:
int t[MAXN << 1];
inline void init() { memset(t, 0, sizeof(t)); }
inline void add(int x)
{
for (; x <= m; x += (x & -x))
++t[x];
}
inline void del(int x)
{
for (; x <= m; x += (x & -x))
--t[x];
}
inline int ask(int x)
{
register int res = 0;
for (; x; x -= (x & -x))
res += t[x];
return res;
}
} t1, t2;
struct node
{
int opt, x, y;
} opt[MAXN];
//根本不用开两个结构体分别记录操作和序列，只要这样映射一下
int po[MAXN];
int b[MAXN << 1];
inline int find(const int &x)
{
register int l = 1, r = m, res = 1, mid;
while (l <= r)
{
mid = (l + r) >> 1;
if (b[mid] <= x)
res = mid, l = mid + 1;
else
r = mid - 1;
}
return res;
}
inline void sov()
{
poread(n);
t1.init(), t2.init();
tot = 0;
m = 0;
for (register int i = 1, cnt = 0; i <= n; ++i)
{
poread(opt[i].opt), poread(opt[i].x);
if (opt[i].opt == 0)
{
opt[i].y = opt[i].x + (++tot);
po[tot] = i;
b[++m] = opt[i].x, b[++m] = opt[i].y;
}
}
sort(b + 1, b + m + 1);
m = unique(b + 1, b + m + 1) - (b + 1);
for (register int i = 1; i <= n; ++i)
{
if(opt[i].opt == 1)
continue;
opt[i].x = find(opt[i].x);
opt[i].y = find(opt[i].y);
}
for (register int i = 1, cnt = 0; i <= n; ++i)
{
if (opt[i].opt == 0)
{
++cnt;
printf("%lld\n", t2.ask(opt[po[cnt]].y) - t1.ask(opt[po[cnt]].x - 1));
t1.add(opt[po[cnt]].x), t2.add(opt[po[cnt]].y);
}
else
{
t1.del(opt[po[opt[i].x]].x), t2.del(opt[po[opt[i].x]].y);
}
}
}
} // namespace lky
signed main()
{
#ifdef lky233
freopen("testdata.in", "r", stdin);
freopen("testdata.out", "w", stdout);
#endif
int T;
poread(T);
for (register int ttt = 1; ttt <= T; ++ttt)
{
printf("Case #%d:\n", ttt);
lky::sov();
}
}T3 填数游戏
题意
给一个矩阵，每个格子可以填1或者-1，会给定一些已经填了的格子。问可能填法。
咋做
如果行列相加是偶数，没有可行解
否则判断给出的状态是否合法
合法的话答案就是\({2 ^ {(剩余格子 - 1)}}\)
//暴力判合法的，没有优化，时间贼差劲
#include <bits/stdc++.h>
using namespace std;
#define int long long
int MOD;
int n, m;
int k;
struct num
{
int x, y, num;
} N[1000005];
int cx[1000006], cy[1000006];
inline int qpow(int a, int b)
{
if (b <= 0)
return 1;
int res = 1;
for (; b; b >>= 1)
{
if (b & 1)
res = res * a % MOD;
a = a * a % MOD;
}
return res;
}
signed main()
{
cin >> n >> m;
cin >> k;
if ((n + m) & 1)
{
puts("0");
return 0;
}
for (register int i = 1; i <= k; ++i)
{
cin >> N[i].x >> N[i].y >> N[i].num;
++cx[N[i].x], ++cy[N[i].y];
}
for (register int i = 1; i <= n; ++i)
{
if (cx[i] >= m)
{
int pan = 1;
for (register int j = 1; j <= k; ++j)
{
if (N[j].x == i)
pan *= N[j].num;
}
if (pan == 1)
{
puts("0");
return 0;
}
}
}
for (register int i = 1; i <= m; ++i)
{
if (cy[i] >= n)
{
int pan = 1;
for (register int j = 1; j <= k; ++j)
{
if (N[j].y == i)
pan *= N[j].num;
}
if (pan == 1)
{
puts("0");
return 0;
}
}
}
cin >> MOD;
cout << qpow(2, (n - 1) * (m - 1) - k) << endl;
}