Replay
Dup4：
- 两轮怎么退火啊？
- 简单树形dp都不会了，送了那么多罚时
- 简单题都不想清楚就乱写了，喵喵喵？
X：
- 欧拉怎么回路啊， 不会啊。
- 还是有没有手误？未思考清楚或者未检查就提交， 导致自己白送罚时。
A：夺宝奇兵
Solved.
考虑$所有i >= 2 需要跟i - 1 连两条边 只有两种可能 取最小的一种$
$注意n的两个点要连一条边$
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + ;
struct node{
int x1, x2, y1, y2;
}arr[maxn];
ll calc(int i,int j)
{
ll ans1 = abs(arr[i].x1 - arr[j].x1) + abs(arr[i].y1 - arr[j].y1) + abs(arr[i].x2 - arr[j].x2) + abs(arr[i].y2 - arr[j].y2);
ll ans2 = abs(arr[i].x1 - arr[j].x2) + abs(arr[i].y1 - arr[j].y2) + abs(arr[i].x2 - arr[j].x1) + abs(arr[i].y2 - arr[j].y1);
return min(ans1, ans2);
}
int n , m;
int main()
{
while(~scanf("%d %d", &n, &m))
{
for(int i = ; i <= n; ++i) scanf("%d %d %d %d", &arr[i].x1, &arr[i].y1, &arr[i].x2, &arr[i].y2);
ll ans = ;
for(int i = ; i <= n; ++i) ans += calc(i, i - );
ans += abs(arr[n].x1 - arr[n].x2) + abs(arr[n].y1 - arr[n].y2);
printf("%lld\n", ans);
}
return ;
}C：最小边覆盖
Solved.
考虑$No的情况$
- 存在一个点的度数为0(没有被覆盖)
- 存在一条边所连接的两个点其度数 >= 2 即这条边去掉还是个最小边覆盖
#include <bits/stdc++.h>
using namespace std; #define N 300010
#define pii pair <int, int>
int n, m;
pii G[N];
int d[N]; bool f()
{
for (int i = ; i <= n; ++i) if (!d[i]) return false;
for (int i = ; i <= m; ++i)
{
int u = G[i].first, v = G[i].second;
if (d[u] >= && d[v] >= )
return false;
}
return true;
} int main()
{
while (scanf("%d%d", &n, &m) != EOF)
{
memset(d, , sizeof d);
for (int i = , u, v; i <= m; ++i)
{
scanf("%d%d", &u, &v);
++d[u], ++d[v];
G[i] = pii(u, v);
}
puts(f() ? "Yes" : "No");
}
return ;
}
F：小小马
Solved.
因为不同颜色出现次数相同， 所以步数一定是奇数。
暴力跑出大数据的状态， 发现颜色相同就输出No， 否则输出Yes。
小数据暴力跑即可
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + ;
struct node{
int x, y;
int step;
node(){}
node(int x, int y, int step): x(x), y(y), step(step){}
};
int n, m;
int sx, sy, ex, ey;
int vis[][maxn][];
int dir[][] = {-, -, -, , -, -, -, , , -, , , , -, , };
int judge(int x, int y,int step)
{
if(x < || x > n || y < || y > m || vis[x][y][step % ]) return false;
else return true;
}
void BFS()
{
memset(vis, , sizeof vis);
queue<node>q;
q.push(node(sx, sy, ));
while(!q.empty())
{
node st = q.front();
q.pop();
node now = st;
now.step++;
for(int i = ; i < ; ++i)
{
now.x = st.x + dir[i][];
now.y = st.y + dir[i][];
if(judge(now.x, now.y, now.step))
{
vis[now.x][now.y][now.step % ] = ;
q.push(now);
}
}
}
}
int main()
{
while(~scanf("%d %d", &n, &m))
{
scanf("%d %d", &sx, &sy);
scanf("%d %d", &ex, &ey);
if(n < || m < )
{
if(n > m)
{
swap(n, m);
swap(sx, sy);
swap(ex, ey);
}
BFS();
if(vis[ex][ey][]) puts("Yes");
else puts("No");
}
else
{
int ans1 = (sx + sy) % ;
int ans2 = (ex + ey) % ;
if(ans1 != ans2) puts("Yes");
else puts("No");
}
}
return ;
}G：置置置换
Solved.
$在已知1-n的方案数， 枚举n+1出现的位置$
$当枚举到位置x的时候， 选出x-1个数放在前x个， 然后计算方案数 统计即可$
$2 \cdot ans_{n + 1} = \sum\limits_{i = 0}^{n} C_n^i \cdot ans_i \cdot ans_{n - i}$
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD = (ll)1e9 + ;
const int maxn = 1e3 + ; int n;
ll fac[maxn];
ll inv[maxn];
ll invfac[maxn]; ll ans[maxn]; void Init()
{
fac[] = , inv[] = , invfac[] = ;
for(int i = ; i < maxn; ++i)
{
fac[i] = fac[i - ] * i % MOD;
inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
invfac[i] = invfac[i - ] * inv[i] % MOD;
}
} ll calc(int n, int m)
{
if(n == m || m == ) return 1ll;
return fac[n] * invfac[m] % MOD * invfac[n - m] % MOD;
} int main()
{
Init();
ans[] = ans[] = ;
for(int i = ; i + < maxn; ++i)
{
for(int j = ; j <= i; ++j)
{
ans[i + ] = (ans[i + ] + calc(i, j) * ans[j] % MOD * ans[i - j] % MOD) % MOD;
}
ans[i + ] = (ans[i + ] * inv[]) % MOD;
}
while (scanf("%d", &n) != EOF)
{
printf("%lld\n", ans[n]);
}
return ;
}
I：咆咆咆哮
Solved.
考虑如果选择$a_i的个数固定为x，那么对于所有选取b_i的卡牌来说它的贡献是固定的$
枚举$x, 再贪心选取即可$
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 1010
int n, a[N], b[N]; ll f(int x)
{
priority_queue <ll> pq;
ll res = ;
for (int i = ; i <= n; ++i)
{
res += a[i];
pq.push(1ll * b[i] * x - a[i]);
}
for (int i = ; i <= n - x; ++i)
{
res += pq.top();
pq.pop();
}
return res;
} int main()
{
while (scanf("%d", &n) != EOF)
{
for (int i = ; i <= n; ++i) scanf("%d%d", a + i, b + i);
ll res = ;
for (int i = ; i <= n; ++i)
res = max(res, f(i));
printf("%lld\n", res);
}
return ;
}
Div1：
三分
好像满足凸性？ 我不会证啊。..
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 100010
int n, a[N], b[N]; ll check(int x)
{
ll res = ;
priority_queue <ll> pq;
for (int i = ; i <= n; ++i)
{
res = res + a[i];
pq.push(1ll * b[i] * x - a[i]);
}
for (int i = n - x; !pq.empty() && i; --i)
{
res += pq.top(); pq.pop();
}
return res;
} int main()
{
while (scanf("%d", &n) != EOF)
{
for (int i = ; i <= n; ++i) scanf("%d%d", a + i, b + i);
int l = , r = n; ll res = ;
while (r - l >= )
{
int midl = (l + r) >> ;
int midr = (midl + r) >> ;
ll tmpl = check(midl);
ll tmpr = check(midr);
if (tmpl <= tmpr)
{
res = max(res, tmpr);
l = midl + ;
}
else
{
res = max(res, tmpl);
r = midr - ;
}
}
printf("%lld\n", res);
}
return ;
}
K：两条路径
Solved.
考虑$x作为交它的权值要被算上$
在考虑两条路径可以选取端点，端点的选择在其儿子对应的子树中选取一个点且仅能选取一个
树形DP即可
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 100010
#define INFLL 0x3f3f3f3f3f3f3f3f
int n, q;
ll val[N];
vector <int> G[N];
ll Bit[], f[N]; void DFS(int u, int fa)
{
f[u] = -INFLL;
for (auto v : G[u]) if (v != fa)
{
DFS(v, u);
f[u] = max(f[u], f[v]);
}
f[u] = max(f[u], 0ll);
f[u] += val[u];
} void out(ll x)
{
if (x < ) putchar('-'), x = -x;
string res = "";
while (x)
{
res += (x % + '');
x /= ;
}
reverse(res.begin(), res.end());
cout << res << "\n";
} int main()
{
Bit[] = ;
for (int i = ; i <= ; ++i) Bit[i] = Bit[i - ] << ;
while (scanf("%d", &n) != EOF)
{
for (int i = ; i <= n; ++i) G[i].clear();
for (int i = , x; i <= n; ++i)
{
scanf("%d", &x);
if (!x)
{
val[i] = ;
continue;
}
int vis = ;
if (x < )
{
x = -x;
vis = -;
}
--x;
val[i] = Bit[x] * vis;
}
for (int i = , u, v; i < n; ++i)
{
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
int x;
scanf("%d", &q);
while (q--)
{
scanf("%d", &x);
priority_queue <ll> pq;
for (auto v : G[x])
{
DFS(v, x);
pq.push(f[v]);
}
ll res = val[x];
for (int i = ; i <= && !pq.empty() && pq.top() > ; ++i)
{
res += pq.top(); pq.pop();
}
//cout << res << endl;
out(res);
}
}
return ;
}