水题...看懂了就是求 $100/\gcd(100,k)$.
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
ll k;
inline void solve()
{
cin >> k;
ll fenmu = 100 / __gcd(k, 100ll);
cout << fenmu << endl;
}
int main()
{
TIME__START = clock();
int Test = 1;
scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
不难看出最多只会操作 3 次，此时 1 在末尾，n 在开头。其他情况就最多 2 次，总之讨论下 1 和 n 的位置以及中间的排序情况即可。
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
int n, a[55];
inline void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
int ans = 0;
if (is_sorted(a + 1, a + n + 1))
return cout << 0 << endl, void();
if (a[1] == 1 && a[n] == n)
{
if (is_sorted(a + 2, a + n))
cout << 0 << endl;
else
cout << 1 << endl;
return;
}
if (a[1] == 1 || a[n] == n)
return cout << 1 << endl, void();
if (a[1] == n && a[n] == 1)
return cout << 3 << endl,void();
cout << 2 << endl;
}
int main()
{
TIME__START = clock();
int Test = 1;
scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
这个题突然就变得有点恶心了起来......
不难看出只有初始坐标相同奇偶性的才会发生碰撞，所有奇数位置的最后最多剩一个，偶数也同理。那就把这两个分开来看。
用一个栈来维护，类似括号序列那样，一个 L 和一个 R 匹配。栈中连续两个 L 也是可以匹配的，而连续的 R 则需要看后面是否还有 L。
这样搞完之后，栈中还剩下形如 LRRRRRR... 这种，此时先每两个 R 相消，最后就可能剩下 RR 或者 LR，两种情况分别算下即可。
由于一开始输入的 x 不一定有序，故需要先排个序。时间复杂度为 $\mathcal{O}(n \log n)$.
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
int n, m, ans[N];
struct ro
{
int x, d, id;
} a[N];
ro st1[N], st2[N];
int p1, p2;
inline void solve()
{
scanf(
mem(ans, -1, n, int);
p1 = p2 = 0;
for (int x, i = 1; i <= n; ++i)
{
scanf(
a[i].x = x, a[i].id = i;
}
for (int i = 1; i <= n; ++i)
{
char dir[2];
scanf(
a[i].d = (dir[0] == 'R');
}
sort(a + 1, a + n + 1, [&](auto x, auto y) { return x.x < y.x; });
for (int i = 1; i <= n; ++i)
{
auto [x, d, id] = a[i];
if (x & 1)
{
if (p1 == 0 || d == 1)
st1[p1++] = {x, d, id};
else
{
if (st1[p1 - 1].d == 0)
{
ans[id] = ans[st1[p1 - 1].id] = st1[p1 - 1].x + abs(x - st1[p1 - 1].x) / 2;
p1--;
}
else
{
ans[id] = ans[st1[p1 - 1].id] = abs(x - st1[p1 - 1].x) / 2;
p1--;
}
}
}
else
{
if (p2 == 0 || d == 1)
st2[p2++] = {x, d, id};
else
{
if (st2[p2 - 1].d == 0)
{
ans[id] = ans[st2[p2 - 1].id] = st2[p2 - 1].x + abs(x - st2[p2 - 1].x) / 2;
p2--;
}
else
{
ans[id] = ans[st2[p2 - 1].id] = abs(x - st2[p2 - 1].x) / 2;
p2--;
}
}
}
}
while (p1 > 2)
{
auto x1 = st1[p1 - 1], x2 = st1[p1 - 2];
ans[x1.id] = ans[x2.id] = m - x1.x + abs(x1.x - x2.x) / 2;
p1 -= 2;
}
if (p1 == 2)
{
if (st1[0].d == 0)
{
auto x1 = st1[p1 - 1], x2 = st1[p1 - 2];
ans[x1.id] = ans[x2.id] = -abs(x1.x - x2.x) / 2 + m;
}
else
{
auto x1 = st1[p1 - 1], x2 = st1[p1 - 2];
ans[x1.id] = ans[x2.id] = m - x1.x + abs(x1.x - x2.x) / 2;
}
}
while (p2 > 2)
{
auto x1 = st2[p2 - 1], x2 = st2[p2 - 2];
ans[x1.id] = ans[x2.id] = m - x1.x + abs(x1.x - x2.x) / 2;
p2 -= 2;
}
if (p2 == 2)
{
if (st2[0].d == 0)
{
auto x1 = st2[p2 - 1], x2 = st2[p2 - 2];
ans[x1.id] = ans[x2.id] = -abs(x1.x - x2.x) / 2 + m;
}
else
{
auto x1 = st2[p2 - 1], x2 = st2[p2 - 2];
ans[x1.id] = ans[x2.id] = m - x1.x + abs(x1.x - x2.x) / 2;
}
}
for (int i = 1; i <= n; ++i)
printf(
}
int main()
{
TIME__START = clock();
int Test = 1;
scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
这个题突然就变得简单了起来...
实际上之前准备模拟费用流，今天就遇到这个板题......
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
const int MAXN = 5005;
int n, m;
struct node
{
int op; //1是洞，0是老鼠
ll x, lim; //x是位置，lim是洞的容量上限
} a[N];
priority_queue<ll, vector<ll>, greater<ll>> s1;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> s2;
inline void solve()
{
int o;
int tot = 0;
scanf(
for (int i = 1, p, x = 1; i <= o; ++i, ++x)
{
scanf(
if (p == 1)
a[++tot] = {0, x, 0}, ++n;
else
a[++tot] = {1, x, 1}, ++m;
}
// for (int i = 1, x; i <= n; ++i)
// scanf(
// for (int i = 1, x; i <= m; ++i)
// scanf(
a[++tot] = {1, -llinf, m}, a[++tot] = {1, llinf, m};
sort(a + 1, a + tot + 1, [&](auto x, auto y) { return x.x < y.x; });
ll ans = 0;
for (int i = 1; i <= tot; ++i)
{
if (a[i].op == 1)
{
int li = a[i].lim;
while (!s1.empty() && li && s1.top() + a[i].x < 0)
{
li--;
ans += s1.top() + a[i].x;
s2.push({-s1.top() - 2 * a[i].x, 1});
s1.pop();
}
if (li)
s2.push({-a[i].x, li});
}
else
{
auto tmp = s2.top();
s2.pop();
ans += tmp.first + a[i].x;
s1.push({-tmp.first - 2 * a[i].x});
tmp.second--;
if (tmp.second)
s2.push(tmp);
}
}
cout << ans << endl;
}
int main()
{
TIME__START = clock();
int Test = 1;
// scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
这个题其实也很简单......
设 $I(j)$ 表示标号 j 是否被占领，那么我们要求的就是 $E(\sum\limits_{k=1}^{m}I(k))$。根据期望的线性性，上面这个就等于 $\sum\limits_{k=1}^{m}E(I(k))$。于是问题变成如何计算 $E(I(k))$。
正面其实并不太好算，其反面就是没有一个能够占领，这个好算，对于每一个城市选择的时间使得其不能占领的话，就是一个简单的乘法原理。
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
ll ksm(ll a, ll b, int mod2 = mod)
{
ll ret = 1;
while (b)
{
if (b & 1)
ret = ret * a
a = a * a
b >>= 1;
}
return ret;
}
int n, m, ans;
int sub(int a, int b) { return a - b < 0 ? a - b + mod : a - b; }
int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
int mul(long long a, long long b) { return a * b
int d[21][50050];
int fac(int n)
{
if (n == 0)
return 1;
return mul(n, fac(n - 1));
}
inline void solve()
{
scanf(
int inv = ksm(fac(n), mod - 2);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
scanf(
for (int j = 1; j <= m; ++j)
{
int res = 1;
vector<int> vec;
for (int i = 1; i <= n; ++i)
vec.push_back(d[i][j] - 1);
int c = 0, k = 1;
vecupsort(vec);
for (auto i : vec)
{
i = sub(i, c);
k = mul(k, i);
c++;
}
k = mul(k, inv);
res = sub(res, k);
ans = add(ans, res);
}
cout << ans << endl;
}
int main()
{
TIME__START = clock();
int Test = 1;
// scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
这个题就很好玩了...
如果一张 DAG 确定好了，那么哥布林实际上的最优策略就是走一个最小路径覆盖。DAG 的最小路径覆盖就是一个二分图匹配，所以我们可以求出进行一次删边操作之后是否能够使得能撑过的轮数 +1.
接下来就好做了：设 $dp(i,j)$ 表示撑过 $i$ 轮并且此时二分图最大匹配数为 $j$ 的最大值。首先预处理能够使撑过回合数增加的操作序列，那么每一次转移中间都会进行一段连续的操作序列，dp 是 $\mathcal{O}(n^3)$ 的，枚举第 $i$ 轮的操作数和第 $i+1$ 轮的操作数即可。
另外二分图匹配的话，hk 算法应该是最快的？
总之是个很有意思的题，mark~
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 150;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
const int MAXN = N;
struct HK
{
vector<set<int>> g;
int n1, n2;
int lnk[MAXN], dis[MAXN], dm;
bool vis[MAXN];
void clr_hk(int n, int m)
{
n1 = n;
n2 = m;
g.resize(n1 + n2 + 5);
for (int i = 1; i <= n1 + n2; ++i)
g[i].clear();
}
bool bfs_hk()
{
queue<int> q;
dm = INT_MAX;
fill(dis + 1, dis + n1 + n2 + 1, -1);
for (int i = 1; i <= n1; ++i)
if (!lnk[i])
q.push(i), dis[i] = 0;
while (!q.empty())
{
int u = q.front();
q.pop();
if (dis[u] > dm)
break;
for (int v : g[u])
{
if (dis[v] != -1)
continue;
dis[v] = dis[u] + 1;
if (!lnk[v])
dm = dis[v];
else
dis[lnk[v]] = dis[v] + 1, q.push(lnk[v]);
}
}
return dm != INT_MAX;
}
int dfs_hk(int u)
{
for (int v : g[u])
{
if (vis[v] || dis[v] != dis[u] + 1)
continue;
vis[v] = 1;
if (lnk[v] && dis[v] == dm)
continue;
if (lnk[v] && !dfs_hk(lnk[v]))
continue;
lnk[v] = u;
lnk[u] = v;
return 1;
}
return 0;
}
int hk()
{
fill(lnk + 1, lnk + n1 + n2 + 1, 0);
int res = 0;
while (bfs_hk())
{
fill(vis + 1, vis + n1 + n2 + 1, 0);
for (int i = 1; i <= n1; ++i)
if (!lnk[i] && dfs_hk(i))
res++;
}
return res;
}
inline void add(int u, int v)
{
g[u].insert(v + n1);
}
inline void clearEdge(int u, int t)
{
if (t == 0)
{
g[u].clear();
}
else if (t == 1)
{
for (int i = 1; i <= n1; ++i)
g[i].erase(u + n1);
}
}
} G;
int n, m, k;
struct Round
{
ll x, y;
int id;
ll cost(ll t) { return max(0ll, x - y * t); }
} r[N];
vector<int> e[N], vecops, ans;
ll dp[N][N];
int pre[N][N];
void work(int cur)
{
memarray(dp, -0x3f);
// auto mininf = dp[0][0];
dp[0][cur] = 0;
for (int i = 0; i < k; ++i)
for (int j = 0; j <= cur; ++j)
{
if (dp[i][j] < 0)
continue;
for (int p = 0; p < min(j + 1, n - i - 1); ++p)
{
ll t = j - p, c = r[i].cost(t);
if (dp[i + 1][p] < c + dp[i][j])
{
dp[i + 1][p] = c + dp[i][j];
pre[i + 1][p] = j;
}
}
}
}
void printans(int cur)
{
auto now = max_element(dp[k], dp[k] + cur + 1) - dp[k];
for (int i = k; i > 0; --i)
{
ans.push_back(0);
for (int j = pre[i][now] - 1; j >= now; --j)
ans.push_back(vecops[j]);
now = pre[i][now];
}
reverse(vecall(ans));
cout << ans.size() << '\n';
for (auto i : ans)
cout << i << ' ';
}
inline void solve()
{
scanf(
G.clr_hk(n, n);
for (int i = 1, u, v; i <= m; ++i)
{
scanf(
G.add(u, v);
e[u].push_back(v);
}
for (int i = 0, x, y; i < k; ++i)
{
scanf(
r[i] = {x, y, i};
}
int mx = G.hk(), ini = mx;
while (mx > 0)
{
int now = 0;
for (int i = 1; i <= n; ++i)
{
auto G2 = G;
G2.clearEdge(i, 0);
if (G2.hk() < mx)
now = i;
G2 = G, G2.clearEdge(i, 1);
if (G2.hk() < mx)
now = -i;
}
vecops.push_back(now);
G.clearEdge(abs(now), now < 0);
--mx;
}
reverse(vecall(vecops));
work(ini);
printans(ini);
}
int main()
{
TIME__START = clock();
int Test = 1;
// scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
Comments NOTHING