A. 选车站
枚举 \(x_i<0\) 可以 \(\mathcal{O}(\sqrt{x_i})\) 的计算出最小的 \(x_j>0\) 使得 \(-x_ix_j\) 为一个平方数，再枚举倍数即可
// Author: xiaruize
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)
{
if (a > b)
return a;
return b;
}
int min(int a, int b)
{
if (a < b)
return a;
return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;
const int M = 1e5;
// bool st;
int n, m;
int a[N], b[N];
bool mpx[N], mpy[N];
int res = 0;
// bool en;
void calc()
{
bool flag = false;
rep(i, 1, n) flag |= (a[i] == 0);
if (flag)
res += (n - 1) * m;
rep(i, 1, n)
{
if (a[i] >= 0)
continue;
int x = -a[i], y = -a[i];
int tmp = 1;
rep(j, 2, x)
{
if (j * j > x)
break;
if (x % j == 0)
{
int cnt = 0;
while (x % j == 0)
{
x /= j;
cnt++;
}
if (cnt & 1)
tmp = tmp * j;
}
}
tmp *= x;
x = y;
int cur = sqrt(x * tmp);
// cerr << x << ' ' << tmp << ' ' << cur << endl;
rep(p, 1, 400)
{
if (tmp * p * p > 1e5 || cur * p > 1e5)
break;
if (mpx[tmp * p * p + M] && mpy[cur * p + M])
res++;
if (mpx[tmp * p * p + M] && mpy[-cur * p + M])
res++;
}
}
}
void solve()
{
res = 0;
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(mpx, 0, sizeof(mpx));
memset(mpy, 0, sizeof(mpy));
cin >> n >> m;
rep(i, 1, n)
{
cin >> a[i];
mpx[a[i] + M] = true;
}
rep(i, 1, m)
{
cin >> b[i];
mpy[b[i] + M] = true;
}
sort(a + 1, a + n + 1);
sort(b + 1, b + m + 1);
calc();
swap(a, b);
swap(n, m);
swap(mpx, mpy);
calc();
cout << res << endl;
}
signed main()
{
// freopen("railway.in", "r", stdin);
// freopen("railway.out", "w", stdout);
// cerr<<(&en-&st)/1024.0/1024.0<<endl;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testcase = 1;
cin >> testcase;
while (testcase--)
solve();
return 0;
}
B. 好题
如好的题
\(dp_{i,j}\) 表示到 \(i\) 这个点，有 \(j\) 个不一样的，最小用几个
发现转移的时候没法去重
考虑记录每一个状态的前 \(30\) 个最小方案，然后dp就行
// Author: xiaruize
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)
{
if (a > b)
return a;
return b;
}
int min(int a, int b)
{
if (a < b)
return a;
return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 1e4 + 10;
// bool st;
int n, m;
int a[N];
vector<int> g[N];
struct node
{
int val;
vector<int> vec;
bool operator<(node b) const
{
return val < b.val;
}
};
vector<node> dp[N][12];
// bool en;
vector<node> operator+(vector<node> a, vector<node> b)
{
vector<node> res;
map<vector<int>, int> mp;
for (auto u : a)
{
for (auto v : b)
{
node tmp;
for (auto x : u.vec)
tmp.vec.push_back(x);
for (auto x : v.vec)
tmp.vec.push_back(x);
sort(ALL(tmp.vec));
tmp.vec.resize(unique(ALL(tmp.vec)) - tmp.vec.begin());
tmp.val = u.val + v.val;
if (!mp.count(tmp.vec))
mp[tmp.vec] = tmp.val;
else
mp[tmp.vec] = min(mp[tmp.vec], tmp.val);
}
}
for (auto v : mp)
res.push_back((node){v.second, v.first});
sort(ALL(res));
if (res.size() >= 30)
res.resize(30);
return res;
}
vector<node> cln(vector<node> a)
{
vector<node> res;
map<vector<int>, int> mp;
for (auto tmp : a)
{
if (!mp.count(tmp.vec))
mp[tmp.vec] = tmp.val;
else
mp[tmp.vec] = min(mp[tmp.vec], tmp.val);
}
for (auto v : mp)
res.push_back((node){v.second, v.first});
sort(ALL(res));
if (res.size() >= 30)
res.resize(30);
return res;
}
int ans = INF;
void dfs(int x, int fa)
{
dp[x][1].push_back({1, {a[x]}});
for (auto v : g[x])
{
if (v == fa)
continue;
dfs(v, x);
per(i, 10, 1)
{
rep(j, 1, i - 1)
{
if (!dp[x][i - j].empty() && !dp[v][j].empty())
{
vector<node> vec = (dp[x][i - j] + dp[v][j]);
for (auto v : vec)
{
if (v.vec.size() <= 10)
dp[x][v.vec.size()].push_back(v);
}
}
}
}
rep(i, 1, 10)
{
dp[x][i] = cln(dp[x][i]);
}
}
if (!dp[x][m].empty())
ans = min(ans, dp[x][m].front().val);
}
void solve()
{
cin >> n >> m;
rep(i, 1, n) cin >> a[i];
rep(i, 1, n - 1)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
// if (ans == INF)
// {
// while (1)
// ;
// }
cout << ans << endl;
}
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// cerr<<(&en-&st)/1024.0/1024.0<<endl;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testcase = 1;
// cin >> testcase;
while (testcase--)
solve();
return 0;
}
C. 串串怎么你了
参考 loj6564
用 \(\frac{n^2}{64}\) 的时间复杂度做LCS就行
D. Bounce
对于每个点，拆点
黑白染色，钦定黑色格子横进竖出，白色格子横出竖进
强制经过的条件可以通过再拆点后两个点之间不连边，判最后的maxflow是不是 \(n\times m\)
最后的maxcost就是答案
// Author: xiaruize
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)
{
if (a > b)
return a;
return b;
}
int min(int a, int b)
{
if (a < b)
return a;
return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;
namespace MCMF
{
const int MAXN = 2e3 + 10, MAXM = 2e4 + 10, INF = 0x7fffffff;
int head[MAXN], cnt = 1;
struct Edge
{
int to, w, c, next;
} edges[MAXM * 2];
int maxflow, mincost;
void init()
{
maxflow = mincost = 0;
memset(head, 0, sizeof(head));
memset(edges, 0, sizeof(edges));
cnt = 1;
}
inline void add(int from, int to, int w, int c)
{
edges[++cnt] = {to, w, c, head[from]};
head[from] = cnt;
}
inline void addEdge(int from, int to, int w, int c)
{
add(from, to, w, c);
add(to, from, 0, -c);
}
int s, t, dis[MAXN], cur[MAXN];
bool inq[MAXN], vis[MAXN];
queue<int> Q;
bool SPFA()
{
while (!Q.empty())
Q.pop();
copy(head, head + MAXN, cur);
fill(dis, dis + MAXN, INF);
dis[s] = 0;
Q.push(s);
while (!Q.empty())
{
int p = Q.front();
Q.pop();
inq[p] = 0;
for (int e = head[p]; e != 0; e = edges[e].next)
{
int to = edges[e].to, vol = edges[e].w;
if (vol > 0 && dis[to] > dis[p] + edges[e].c)
{
dis[to] = dis[p] + edges[e].c;
if (!inq[to])
{
Q.push(to);
inq[to] = 1;
}
}
}
}
return dis[t] != INF;
}
int dfs(int p = s, int flow = INF)
{
if (p == t)
return flow;
vis[p] = 1;
int rmn = flow;
for (int eg = cur[p]; eg && rmn; eg = edges[eg].next)
{
cur[p] = eg;
int to = edges[eg].to, vol = edges[eg].w;
if (vol > 0 && !vis[to] && dis[to] == dis[p] + edges[eg].c)
{
int c = dfs(to, min(vol, rmn));
rmn -= c;
edges[eg].w -= c;
edges[eg ^ 1].w += c;
}
}
vis[p] = 0;
return flow - rmn;
}
inline void run(int s, int t)
{
MCMF::s = s, MCMF::t = t;
while (SPFA())
{
int flow = dfs();
maxflow += flow;
mincost += dis[t] * flow;
}
}
} // namespace MCMF
// bool st;
int n, m;
map<pii, int> mp;
// bool en;
int id(int x, int y, int t)
{
return (x - 1) * m + y + t * n * m;
}
void solve()
{
mp.clear();
MCMF::init();
cin >> n >> m;
rep(i, 1, n)
{
rep(j, 1, m - 1)
{
int x;
cin >> x;
if ((i + j) & 1)
MCMF::addEdge(id(i, j, 0), id(i, j + 1, 1), 1, -x);
else
MCMF::addEdge(id(i, j + 1, 0), id(i, j, 1), 1, -x);
}
}
rep(i, 1, n - 1)
{
rep(j, 1, m)
{
int x;
cin >> x;
if ((i + j) & 1)
MCMF::addEdge(id(i + 1, j, 0), id(i, j, 1), 1, -x);
else
MCMF::addEdge(id(i, j, 0), id(i + 1, j, 1), 1, -x);
}
}
int q;
cin >> q;
rep(i, 1, q)
{
int x, y;
cin >> x >> y;
mp[{x, y}] = true;
}
int s = n * m * 2 + 1, t = n * m * 2 + 2;
rep(i, 1, n)
{
rep(j, 1, m)
{
MCMF::addEdge(s, id(i, j, 0), 1, 0);
MCMF::addEdge(id(i, j, 1), t, 1, 0);
if (!mp.count({i, j}))
MCMF::addEdge(id(i, j, 0), id(i, j, 1), 1, 0);
}
}
MCMF::run(s, t);
if (MCMF::maxflow != n * m)
cout << "Impossible" << endl;
else
cout << -MCMF::mincost << endl;
}
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// cerr<<(&en-&st)/1024.0/1024.0<<endl;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testcase = 1;
cin >> testcase;
while (testcase--)
solve();
return 0;
}