今天的题
\(75pts\ rk50+\) ，最废的一次。
T1
简单 \(\mathcal{DP}\)。
#include <iostream>using std::cin;
using std::cout;
const int N = 1e3 + 10;
#define int long long
const int mod = 998244353;int a[N][N];
char c[N][N];
int f[N][N][2];
int g[N][N][2];
int cnt[N][N][2];signed main()
{int n, m;cin >> n >> m;for (int i = 1; i <= n; ++i){for (int j = 1; j <= m; ++j)cin >> c[i][j];}if ((n == 1 && m == 1) || (c[1][1] == '#') || (c[n][m] == '#')){cout << 0 << '\n';return 0;}for (int i = 1; i <= n; ++i){for (int j = 1; j <= m; ++j)a[i][j] = 1ll * i * j % mod;}if (m >= 2 && c[1][2] == '.'){cnt[1][2][0] = 1;f[1][2][0] = 2;g[1][2][0] = 2;}if (n >= 2 && c[2][1] == '.'){cnt[2][1][1] = 1;f[2][1][1] = 2;g[2][1][1] = 2;}for (int i = 1; i <= n; ++i){for (int j = 1; j <= m; ++j){if (c[i][j] == '#' || (i == 1 && j == 1))continue;if (i > 1 && c[i - 1][j] != '#'){if (f[i - 1][j][1]){cnt[i][j][1] = (cnt[i][j][1] + cnt[i - 1][j][1]) % mod;f[i][j][1] = (1ll * f[i][j][1] + f[i - 1][j][1] + 1ll * cnt[i - 1][j][1] * a[i][j] % mod) % mod;g[i][j][1] = (1ll * g[i][j][1] + g[i - 1][j][1] + f[i - 1][j][1] + 1ll * a[i][j] * cnt[i - 1][j][1] % mod) % mod;}if (f[i - 1][j][0]){cnt[i][j][1] = (cnt[i][j][1] + cnt[i - 1][j][0]) % mod;f[i][j][1] = (1ll * f[i][j][1] + 1ll * cnt[i - 1][j][0] * a[i][j] % mod) % mod;g[i][j][1] = (1ll * g[i][j][1] + 1ll * g[i - 1][j][0] + cnt[i - 1][j][0] * a[i][j] % mod) % mod;}}if (j > 1 && c[i][j - 1] != '#'){if (f[i][j - 1][0]){cnt[i][j][0] = (cnt[i][j][0] + cnt[i][j - 1][0]) % mod;f[i][j][0] = (1ll * f[i][j][0] + f[i][j - 1][0] + 1ll * cnt[i][j - 1][0] * a[i][j] % mod) % mod;g[i][j][0] = (1ll * g[i][j][0] + g[i][j - 1][0] + f[i][j - 1][0] + 1ll * a[i][j] * cnt[i][j - 1][0] % mod) % mod;}if (f[i][j - 1][1]){cnt[i][j][0] = (cnt[i][j][0] + cnt[i][j - 1][1]) % mod;f[i][j][0] = (1ll * f[i][j][0] + 1ll * cnt[i][j - 1][1] * a[i][j] % mod) % mod;g[i][j][0] = (1ll * g[i][j][0] + g[i][j - 1][1] + 1ll * cnt[i][j - 1][1] * a[i][j] % mod) % mod;}}}}cout << (1ll * g[n][m][0] + g[n][m][1]) % mod;return 0;
}
T2
虚树 \(or\) 重链剖分 \(or\) 结论。
我用的是结论。
取dfn排序的中位数。
那么答案肯定是这个中位数的某个祖先，直接倍增就行。
#include <iostream>
#include <vector>
#include <algorithm>
#define lowbit(x) x & (-x)using std::cin;
using std::cout;
const int N = 1e5 + 10;int k;
int idx;
int dep[N];
int dfn[N];
int sum[N];
int size[N];
int fa[N][25];
std::vector<int> now;
std::vector<int> e[N];void dfs(int x, int father)
{dep[x] = dep[father] + 1;dfn[x] = ++idx;fa[x][0] = father;for (int i = 1; i <= 20; ++i)fa[x][i] = fa[fa[x][i - 1]][i - 1];for (auto to : e[x]){if (to != father)dfs(to, x);}size[x] = 1;for (auto to : e[x]){if (to != father)size[x] += size[to];}
}
void add(int x, int k)
{for (; x <= idx; x += lowbit(x))sum[x] += k;
}
int query(int x)
{int ret = 0;for (; x; x -= lowbit(x))ret += sum[x];return ret;
}
int ask(int l, int r)
{return query(r) - query(l - 1);
}
int where(int x)
{if (ask(dfn[x], dfn[x] + size[x] - 1) > (k / 2))return x;for (int i = 20; i >= 0; --i){int l = fa[x][i];if (l && ask(dfn[l], dfn[l] + size[l] - 1) <= k / 2)x = l;} return fa[x][0];
}int main()
{int n;cin >> n;for (int i = 1; i < n; ++i){int u, v;cin >> u >> v;e[u].push_back(v);e[v].push_back(u);}dfs(1, 0);int q;cin >> q;while (q--){now.clear();cin >> k;for (int i = 1; i <= k; ++i){int s;cin >> s;now.push_back(s);add(dfn[s], 1);}std::sort(now.begin(), now.end(), [&](const int &a, const int &b){return dfn[a] < dfn[b];});k = now.size();if (now.size() & 1)cout << where(now[(now.size() >> 1)]) << '\n';else{int x = where(now[now.size() >> 1]);int y = where(now[(now.size() >> 1) - 1]);cout << (dep[x] > dep[y] ? x : x) << '\n';}for (auto it : now)add(dfn[it], -1);}return 0;
}
T3
找欧拉回路。
奇数加一条边，偶数加两条边。
#include <iostream>
#include <vector>
#include <stack>using std::cin;
using std::cout;
const int N = 12e5 + 10;int idx;
int top;
int w[N];
bool vis[N];
int lst[N];
int deg[N];
int stk[N];
std::vector<int> odd;
std::vector<int> gg[N];void add(int x, int y)
{w[++idx] = x ^ y;gg[x].push_back(idx);gg[y].push_back(idx);
}
void dfs(int x)
{for (int i = lst[x]; i < (int)gg[x].size(); i = lst[x]){lst[x] = std::max(lst[x], i + 1);int to = w[gg[x][i]] ^ x;if (!vis[gg[x][i]]){vis[gg[x][i]] = true;dfs(to);stk[++top] = to;}}
}int main()
{int n, m;cin >> n >> m;for (int i = 1; i <= m; ++i){int u, v;cin >> u >> v;int t;cin >> t;if (t & 1){add(u, v);deg[v]++;deg[u]++;}else{add(u, v);add(u, v);deg[v] += 2;deg[u] += 2;}}for (int i = 1; i <= n; ++i){if (deg[i] & 1)odd.push_back(i);}if (odd.size() == 1 || odd.size() > 2){cout << -1 << '\n';return 0;}if (odd.size() == 0){dfs(1);stk[++top] = 1;cout << top << '\n';for (int i = top; i >= 1; --i)cout << stk[i] << ' ';cout << '\n';}else{add(odd[0], odd[1]);dfs(odd[0]);int ge;for (int i = 1; i <= top; ++i){for (int j = 0; j <= 1; ++j){if (stk[i] == odd[j] && stk[i % top + 1] == odd[j ^ 1]){ge = i;break;}}}cout << top << '\n';for (int i = ge; i >= 1; --i)cout << stk[i]<< ' ';for (int i = top; i >= ge + 1; --i)cout << stk[i] << ' ';cout << '\n';}return 0;
}
T4
容斥。
#include<bits/stdc++.h>
using namespace std;int read();
typedef long long ll;
#define fr(i,l,r) for(int i=(l);i<=(r);++i)
#define rf(i,l,r) for(int i=(l);i>=(r);--i)
#define fo(i,l,r) for(int i=(l);i<(r);++i)
#define foredge(i,u,v) for(int i=fir[u],v;v=to[i],i;i=nxt[i])
#define filein(file) freopen(file".in","r",stdin)
#define fileout(file) freopen(file".out","w",stdout)const int N=1e6+5,MOD=1e9+7;
int n,m,k;
ll fac[N],ifac[N];
ll qpow(ll a,int x) {ll z=1;for(;x;x>>=1,a=a*a%MOD)if(x&1) z=z*a%MOD;return z;
}
ll C(int n,int m) {if(n<m) return 0;return fac[n]*ifac[m]%MOD*ifac[n-m]%MOD;
}
int main() {//filein("count");//fileout("count");cin>>n>>m>>k;*fac=1; fr(i,1,m) fac[i]=fac[i-1]*i%MOD;ifac[m]=qpow(fac[m],MOD-2);rf(i,m,1) ifac[i-1]=ifac[i]*i%MOD;ll ans=0,sum=0;sum=1;rf(i,m,0) {(ans+=(i&1?-1:1)*C(m,i)*qpow(sum-1,n))%=MOD;sum=(sum*2-C(m-i,k))%MOD;//sum=\sum_{j=0}^k C(m-i,j)}cout<<(ans+MOD)%MOD<<endl;return 0;
}