比赛链接：传送门
两个半小时的时候横扫了铜、银区的所有题，签到成功混进金区。奈何后面没能开出新的题。
最后一个小时的时候xk灵机一动想出了D题的做法，讨论了一波感觉可行，赶紧去敲。结束前2分钟终于过了样例结果WA3。
赛后10分钟，xk改了两个bug就过了D。。。。离金最近的一场（又来？）。
Problem B. Baby Bites 00：11 （-1） Solved by Dancepted
很明显的签到题，题面短又水。（那你还WA了一发？555我错了，我把循环里的j手滑写成了i）
代码：
#include <iostream>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <iomanip>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define N 100005
#define M 100005
#define INF 0x3f3f3f3f
#define mk(x) (1<<x) // be conscious if mask x exceeds int
#define sz(x) ((int)x.size())
#define upperdiv(a,b) (a/b + (a%b>0))
#define mp(a,b) make_pair(a, b)
#define endl '\n'
#define lowbit(x) (x&-x) using namespace std;
typedef long long ll;
typedef double db; /** fast read **/
template <typename T>
inline void read(T &x) {
x = ; T fg = ; char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') fg = -;
ch = getchar();
}
while (isdigit(ch)) x = x*+ch-'', ch = getchar();
x = fg * x;
}
template <typename T, typename... Args>
inline void read(T &x, Args &... args) { read(x), read(args...); }
template <typename T>
inline void write(T x) {
int len = ; char c[]; if (x < ) putchar('-'), x = -x;
do{++len; c[len] = x% + '';} while (x /= );
for (int i = len; i >= ; i--) putchar(c[i]);
}
template <typename T, typename... Args>
inline void write(T x, Args ... args) { write(x), write(args...); } int main() {
int n;
cin >> n;
bool ans = true;
for (int i = ; i <= n; i++) {
string s;
cin >> s;
if (s[] == 'm') {
continue;
}
int a = ;
for (int j = ; j < sz(s); j++)
a = a * + s[j] - '';
if (a != i) {
ans = false;
}
}
if (ans) {
puts("makes sense");
}
else {
puts("something is fishy");
}
return ;
}
Problem C. Code Cleanups 00：27 （+） Solved by xk
队友签的到。
代码：
#include <iostream>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <iomanip>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define N 2505
#define M 100005
#define INF 0x3f3f3f3f
#define mk(x) (1<<x) // be conscious if mask x exceeds int
#define sz(x) ((int)x.size())
#define upperdiv(a,b) (a/b + (a%b>0))
#define mp(a,b) make_pair(a, b)
#define endl '\n'
#define lowbit(x) (x&-x) using namespace std;
typedef long long ll;
typedef double db; int a[]; int main()
{
fast;
int n;
cin >> n;
for(int i = ; i < n; i++)
{
cin >> a[i];
}
int cnt = , p = ;
int dirty = ;
int ans = ;
for(int i = ; i <= && p < n; i++)
{
dirty += cnt;
if(a[p] == i) {
p++;
cnt++;
}
if(dirty + cnt >= ) {
ans++;
cnt = dirty = ;
}
}
if(cnt) ans++;
cout << ans << endl;
}
Problem K. King's Colors 01：13 （+） Solved by Dancepted
xk乍一看是个树形dp，直接丢了给我。我也差点被xk带偏。
实际上大概是类似容斥一样的线性dp：
首先，有n个节点的树，使用了 <= i种颜色的染色方案数为 $ i * (i-1)^{n-1} $，每个节点只要和父节点不同即可，有i-1种方案，而根没有限制，有i种方案。
设$f_{i}$为恰好使用了i种颜色的染色方案数：
那么$f_{i} = i * (i-1)^{n-1} - \sum_{j=1}^{i-1} C_{i}^{j} * f_{j}$。就是 <= i种颜色的染色方案数 - $\sum$(从i种颜色中选j种颜色的方案数) * j种颜色的染色方案数。
代码：$O(n^{2})$
#include <iostream>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <iomanip>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define N 2505
#define M 100005
#define INF 0x3f3f3f3f
#define mk(x) (1<<x) // be conscious if mask x exceeds int
#define sz(x) ((int)x.size())
#define upperdiv(a,b) (a/b + (a%b>0))
#define mp(a,b) make_pair(a, b)
#define endl '\n'
#define lowbit(x) (x&-x) using namespace std;
typedef long long ll;
typedef double db; /** fast read **/
template <typename T>
inline void read(T &x) {
x = ; T fg = ; char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') fg = -;
ch = getchar();
}
while (isdigit(ch)) x = x*+ch-'', ch = getchar();
x = fg * x;
}
template <typename T, typename... Args>
inline void read(T &x, Args &... args) { read(x), read(args...); }
template <typename T>
inline void write(T x) {
int len = ; char c[]; if (x < ) putchar('-'), x = -x;
do{++len; c[len] = x% + '';} while (x /= );
for (int i = len; i >= ; i--) putchar(c[i]);
}
template <typename T, typename... Args>
inline void write(T x, Args ... args) { write(x), write(args...); } #define md 1000000007
inline ll mul(ll a) {return a;}
template <typename... Args>
inline ll mul(ll a, Args ... args) {return a*mul(args...) % md;}
inline ll add(ll a) {return a;}
template <typename... Args>
inline ll add(ll a, Args ... args) {
ll res = (a+add(args...)) % md;
if (res < ) res += md;
return res;
}
inline ll fpow(ll a, ll p) {
ll res = ;
for (; p; p >>= ) {
if (p&) res = mul(res, a);
a = mul(a, a);
}
return res;
}
inline ll getInv(ll x) { return fpow(x, md-); }
#define MAXN 2505
ll fac[MAXN], inv[MAXN];
ll C(ll n, ll m) { if (m < || m > n) return ; return mul(fac[n], mul(inv[n-m], inv[m])); }
ll P(ll n, ll m) { return mul(fac[n], fac[n-m]); }
void init() {
fac[] = ; for (int i = ; i < MAXN; i++) fac[i] = mul(fac[i-], i);
inv[MAXN-] = fpow(fac[MAXN-], md-); for (int i = MAXN-; i >= ; i--) inv[i] = mul(inv[i+], i+);
} ll f[N];
int main() {
init();
int n; ll k; read(n, k);
for (int i = ; i <= n; i++) {
int a; read(a);
}
for (int i = ; i <= k; i++) {
f[i] = mul(i, fpow(i-, n-));
for (int j = ; j <= i-; j++) {
ll tmp = mul(C(i, j), f[j]);
f[i] = add(f[i], -tmp);
}
}
ll ans = f[k];
cout << ans << endl;
return ;
}
Problem H. House Lawn 01：39 （+） Solved by xk
在我和lh捣鼓J的时候，xk已经开出了I和H，抢键盘上机秒题。
代码：
#include <iostream>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <iomanip>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define sz(x) ((int)x.size())
#define forn(i, n) for(int i = 0; i < (n); i++)
#define forab(i, a, b) for(int i = (a); i <= (b); i++)
#define mp(a,b) make_pair(a, b)
#define endl '\n'
#define lowbit(x) (x&-x)
using namespace std;
typedef long long ll;
typedef double db; char s[][];
ll p[], c[], t[], r[]; int main()
{
ll l, n;
cin >> l >> n;
forn(i, n)
{
scanf("\n%[^,],%lld,%lld,%lld,%lld", s[i], &p[i], &c[i], &t[i], &r[i]);
}
ll mxp = 1e18;
forn(i, n)
{
if(p[i] > mxp) continue;
if(c[i] * t[i] * >= l * (r[i] + t[i]))
{
mxp = p[i];
}
}
if(mxp == 1e18) {
return puts("no such mower") * ;
}
forn(i, n)
{
if(p[i] == mxp && (c[i] * t[i] * >= l * (r[i] + t[i])))
{
puts(s[i]);
}
}
}
Problem J. Jumbled String 01：56 （-3） Solved by lh & Dancepted
lh在01：06的时候就已经写好了代码，但是有几个特殊值没有考虑到，差点弃题。
直接计算0和1的数量n和m，得到总数量n+m，$C_{n+m}^{2}$ = a + b + c + d。如果成立就贪心地在1之间插入0，使得01的数量是正确的，那么10的数量肯定是正确的。
需要特判abcd全0或者有3个0的情况。
代码：
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
long long a, b, c, d, n, m;
long long sum[] = {};
int main()
{
cin >> a >> b >> c >> d;
if (a == && b == && c == && d == )
{
puts("");
return ;
}
bool flag = false;
if (a == && d == )
n = , m = ;
else
{
if (a == )
n = ;
else
{
n = sqrt(a * );
for (long long i = max(n - , 0ll); i <= n + ; ++i)
{
if (i * (i - 1ll) == a * )
{
n = i, flag = true;
break;
}
}
if (!flag)
{
puts("impossible");
return ;
}
}
if (d == )
m = ;
else
{
m = sqrt(d * ), flag = false;
for (long long i = max(m - , 0ll); i <= m + ; ++i)
{
if (i * (i - 1ll) == d * )
{
m = i, flag = true;
break;
}
}
if (!flag)
{
puts("impossible");
return ;
}
}
}
if (c == && b == )
{
if (a == && d)
{
while (m--)putchar('');
return ;
}
else if (a && d == )
{
while (n--)putchar('');
return ;
}
}
long long tot = n + m;
if (a + b + c + d != (tot - 1ll) * tot / )
{
puts("impossible");
return ;
}
for (long long i = ; i < m; ++i)
{
sum[i] = b / (m - i);
b %= (m - i), n -= sum[i];
if (b == || n == )
break;
}
if (b)
{
puts("impossible");
return ;
}
for (int i = ; i < m; ++i)
{
while (sum[i])putchar(''), --sum[i];
putchar('');
}
while (n)putchar(''), --n;
return ;
}
/*
1 4 2 3
*/
Problem I. Intergalactic Bidding 02：32 （+） Solved by Dancepted & xk
就是个cf div2的a、b题难度的大水题，但是要大数。
自信满满地打开eclipse发现大数不会读入，不会重载小于号排序。。。
只能老老实实切回vscode，掏出尘封多年的c++大数板子，一字一句地抄上去（模拟现场赛）。
代码：O(n*logn*logs)
#include <iostream>
#include <istream>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <iomanip>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define N 1005
#define M 100005
#define INF 0x3f3f3f3f
#define mk(x) (1<<x) // be conscious if mask x exceeds int
#define sz(x) ((int)x.size())
#define upperdiv(a,b) (a/b + (a%b>0))
#define mp(a,b) make_pair(a, b)
#define endl '\n'
#define lowbit(x) (x&-x) using namespace std;
typedef long long ll;
typedef double db; /** fast read **/
template <typename T>
inline void read(T &x) {
x = ; T fg = ; char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') fg = -;
ch = getchar();
}
while (isdigit(ch)) x = x*+ch-'', ch = getchar();
x = fg * x;
}
template <typename T, typename... Args>
inline void read(T &x, Args &... args) { read(x), read(args...); }
template <typename T>
inline void write(T x) {
int len = ; char c[]; if (x < ) putchar('-'), x = -x;
do{++len; c[len] = x% + '';} while (x /= );
for (int i = len; i >= ; i--) putchar(c[i]);
}
template <typename T, typename... Args>
inline void write(T x, Args ... args) { write(x), write(args...); } struct bigInt{
int len, d[N];
void clean() {
while (len > && !d[len-]) len--;
}
bigInt() {memset(d, , sizeof d); len = ;}
bigInt(int num) {*this = num;}
bigInt operator = (int num) {
char s[];
sprintf(s, "%d", num);
*this = s;
return * this;
}
bigInt operator = (const char* num) {
memset(d, , sizeof d);
len = strlen(num);
for (int i = ; i < len; i++)
d[i] = num[len--i] - '';
clean();
return *this;
}
bool operator < (const bigInt& b) const {
if (len != b.len) return len < b.len;
for (int i = len-; i >= ; i--)
if (d[i] != b.d[i])
return d[i] < b.d[i];
return false;
}
bool operator == (const bigInt& b) const { return !(b < *this) && !(*this < b); }
bigInt operator + (const bigInt& b) const {
bigInt c = *this;
c.len = max(len, b.len) + ;
for (int i = ; i < c.len; i++) {
c.d[i] += b.d[i];
c.d[i+] += c.d[i] / ;
c.d[i] %= ;
}
c.clean();
return c;
}
bigInt operator - (const bigInt& b) {
bigInt c = *this;
int i;
for (i = ; i < b.len; i++) {
c.d[i] -= b.d[i];
if (c.d[i] < ) c.d[i] += , c.d[i+]--;
}
while (c.d[i] < ) c.d[i++] += , c.d[i]--;
c.clean();
return c;
}
}; istream& operator >> (istream& in, bigInt& x) {
string s; in >> s;
x = s.c_str();
return in;
} struct Node{
string name;
bigInt val;
bool operator < (const Node& x) const {
return val < x.val;
}
}nodes[N]; vector <string> ans;
int main() {
ios::sync_with_stdio(), cin.tie(), cout.tie();
int n; bigInt sum;
cin >> n >> sum;
for (int i = ; i <= n; i++) {
cin >> nodes[i].name >> nodes[i].val;
}
sort(nodes+, nodes++n);
for (int i = n; i >= ; i--) {
if (nodes[i].val < sum || nodes[i].val == sum) {
sum = sum - nodes[i].val;
ans.push_back(nodes[i].name);
}
}
if (sum.len == && sum.d[] == ) {
cout << ans.size() << endl;
for (string& s: ans) {
cout << s << endl;
}
}
else {
cout << << endl;
}
return ;
}
补题：
Problem E. Explosion Exploit（最短路 + 二分答案 + dp）
先跑n次Dijkstra得到两两之间的距离$dis_{i,j}$。
然后二分答案+dp确认。
$dp_{i}$表示在答案为mid时，第i个订单允许的最晚出发时间。
枚举骑手在送第i单时，连续送到第j个订单结束，才回披萨店取餐，则对于所有的k（i <= k <= j），满足下面条件的最大值，是$dp_{i}$的一个可能的值：
$dp_{i} + dis_{1, u_{i}} + \sum_{l=i+1}^{k}dis{u_{l}, u_{l-1}} + dis_{1, u_{k}} <= dp_{k+1}$。
最后的$dp_{i}$就是对所有的可能值取max。
如果存在$dp_{i} < t_{i}$，则说明不存在方案使得第i个单子在答案为mid时能被准时送到，则不可行。否则可行。
代码：$O(n^{2}logn)$
#include <iostream>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <iomanip>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define sz(x) ((int)x.size())
#define forn(i, n) for(int i = 0; i < (n); i++)
#define forab(i, a, b) for(int i = (a); i <= (b); i++)
#define mp(a,b) make_pair(a, b)
#define endl '\n'
#define lowbit(x) (x&-x)
using namespace std;
typedef long long ll;
typedef double db; const int maxn = ;
struct edge
{
int to;
ll len;
}; struct node
{
int id;
ll dis;
bool operator < (const node &a) const {
return dis > a.dis;
}
}; ll dis[maxn][maxn];
vector<edge> g[maxn]; void dij(int x)
{
priority_queue<node> q;
memset(dis[x], 0x3f, sizeof(dis[x]));
dis[x][x] = ;
q.push(node{x, });
while(!q.empty())
{
node t = q.top(); q.pop();
int u = t.id;
if(t.dis > dis[x][u]) continue;
forn(i, sz(g[u]))
{
edge &e = g[u][i];
if(dis[x][e.to] > dis[x][u] + e.len)
{
dis[x][e.to] = dis[x][u] + e.len;
q.push(node{e.to, dis[x][e.to]});
}
}
}
} int n, m, k;
ll s[maxn], u[maxn], t[maxn];
ll dp[maxn]; bool check(ll x)
{
// cout << x << endl;
dp[k + ] = 1e16;
for(int i = k; i > ; i--)
{
ll sumdis = dis[][u[i]];
ll temp = s[i] + x - sumdis;
dp[i] = min(s[i] + x - sumdis, dp[i + ] - * dis[][u[i]]);
for(int j = i + ; j <= k; j++)
{
sumdis += dis[u[j]][u[j - ]];
temp = min(temp, s[j] + x - sumdis);
ll tt = min(temp, dp[j + ] - dis[][u[j]] - sumdis);
if(tt >= t[j])
dp[i] = max(dp[i], tt);
}
if (dp[i] < t[i]) return false;
// cout << dp[i] << ' ';
}
// cout << endl;
return dp[] >= ;
} int main()
{
fast;
cin >> n >> m;
forn(i, m)
{
int u, v; ll l;
cin >> u >> v >> l;
g[u].push_back(edge{v,l});
g[v].push_back(edge{u,l});
}
forab(i, , n)
dij(i);
cin >> k;
forab(i, , k)
{
cin >> s[i] >> u[i] >> t[i];
}
ll l = -, r = 1e16;
while (r - l > )
{
ll mid = (l + r) / ;
if(check(mid))
r = mid;
else
l= mid;
}
cout << r << endl;
return ;
}
Problem D. Delivery Delays（状压dp）
直接状压的话空间是$7^{10} ≈ 2e9$，考虑对1-6数值的数量状压。
这样可以用dp来计算空间复杂度，5个人分到6个数值250左右个方案。两边有10个人，平方一下大概是5e4个。
实现的话用dfs比较方便，用map记忆化一下就好（vscode不知为啥不能用unordered_map）。
参考博客：传送门
代码：
#include <iostream>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
#include <type_traits>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <iomanip>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define N 5
#define M 100005
#define INF 0x3f3f3f3f
#define mk(x) (1<<x) // be conscious if mask x exceeds int
#define sz(x) ((int)x.size())
#define upperdiv(a,b) (a/b + (a%b>0))
#define mp(a,b) make_pair(a, b)
#define endl '\n'
#define lowbit(x) (x&-x) using namespace std;
typedef long long ll;
typedef double db; /** fast read **/
template <typename T>
inline void read(T &x) {
x = ; T fg = ; char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') fg = -;
ch = getchar();
}
while (isdigit(ch)) x = x*+ch-'', ch = getchar();
x = fg * x;
}
template <typename T, typename... Args>
inline void read(T &x, Args &... args) { read(x), read(args...); }
template <typename T>
inline void write(T x) {
int len = ; char c[]; if (x < ) putchar('-'), x = -x;
do{++len; c[len] = x% + '';} while (x /= );
for (int i = len; i >= ; i--) putchar(c[i]);
}
template <typename T, typename... Args>
inline void write(T x, Args ... args) { write(x), write(args...); } int a[][];
ll haxi() {
ll res = ;
for (int i = ; i < ; i++) {
for (int j = ; j <= ; j++) {
res = res * + a[i][j];
}
}
return res;
} map<ll, db> MP;
// unordered_map<ll, db> MP;
db dfs(ll sta, int resd) {
if (MP.count(sta)) return MP[sta];
if (sta < )
return MP[sta] = ;
if (resd == )
return MP[sta] = ; int sum = ;
for (int i = ; i < ; i++) {
for (int j = ; j <= ; j++) {
sum += a[i][j];
}
} db res = ;
for (int i = ; i < ; i++) {
for (int j = ; j <= ; j++) {
if (!a[i][j])
continue;
a[i][j]--, a[i][j-]++;
db tmp = dfs(haxi(), resd-);
a[i][j]++, a[i][j-]--;
res += (db)a[i][j] / sum * tmp;
}
}
return MP[sta] = res;
} int main() {
int n, m, d; read(n, m, d);
for (int i = ; i <= n; i++) {
int x; read(x);
a[][x]++;
}
for (int i = ; i <= m; i++) {
int x; read(x);
a[][x]++;
}
db ans = dfs(haxi(), d);
printf("%.8lf\n", ans);
return ;
}
总结：
切完银牌题之后有点飘没有静下心思想E的做法，优化状态的数量是想到了的，但是没有底气继续写。
xk写D的时候我觉得xk的debug手法太糙了，忍不住抢了键盘qwq，而xk赛后10分钟改了两个bug就过了D，这里我应该也要背个锅吧，痛失金牌。
lh今天好像掉线了？