本场比赛的时间对中国人很不友好...... 题目不错, 知识点偏数学化, B题和D题有一些细节问题. E题需要一些数学推导或者大胆猜想. 比赛时完成A-C. 看Div.1的Standings, 感慨人与人的差距: 我1小时搞不出来的题杜教10分钟就切掉了. 题解: 5/5. # A. Anastasia and pebbles 两个口袋, 容量均为k, n种物品, 每种wi件. 一个口袋同一时刻只能装一种物品, 问多少趟能把物品全部带走. (1≤n≤10^5, 1≤k≤10^9, 1≤wi≤10^4)
输出
int main()
{
int n, k, cnt = 0;
cin >> n >> k;
Rep (i, 0, n) {
int w;
cin >> w;
cnt += (w + k - 1) / k;
}
cout << (cnt + 1) / 2 << endl;
return 0;
}B. Masha and geometric depression
一个等比数列 (这里允许首项和公比是0), 一项一项地写出来, 跳过一个特定集合S里的数, 一旦某项的绝对值大于l则停止, 问总共写出多少个数 (无穷输出"inf"). (首项b1, 公比q, 集合中的数属于[-10^9, 10^9], 1≤l≤10^9, 集合的大小属于[1,10^5])
显然, 如果公比不等于0, 1, -1, 首项非0, 暴力即可. 这些情况大力讨论一发: - |b1| > l: 0 首先特判这一种情况, 则后面不用考虑范围 - b1 = 0 或 q = 1: b1属于S输出0, 否则inf - q = 0: 如果0不属于S, 输出inf; 否则, 如果b1属于S, 输出0, 如果b1不属于S, 输出1 - q = -1: 如果b1或-b1不属于S, 输出inf; 否则, 输出0
复杂的分类讨论算我的弱项......? 看来得刻意地练习一下.
唉, 其实这题的分类也不是很复杂啦......但当时心情有点乱, 并且觉得题意有点模糊: Masha writes all progression terms one by one onto the board (including repetitive) while condition |bi| ≤ l is satisfied. 到底是只写|bi| ≤ l的项, 还是不满足这个条件就停止?
码完之后删掉, 换了下面这种写法. 如果答案不是inf, 则一定不超过31. 循环64次即可.
typedef long long ll;
set<ll> S;
int main()
{
ll b1, q, l, m;
cin >> b1 >> q >> l >> m;
Rep (i, 0, m) {
ll a;
cin >> a;
S.insert(a);
}
ll cnt = 0, loop = 0;
while (abs(b1) <= l && loop < 150) {
cnt += !S.count(b1);
b1 *= q;
++loop;
}
if (cnt <= 32)
cout << cnt << endl;
else
cout << "inf" << endl;
return 0;
}C. Functions again
有一个长度为n的数列a, 定义以下函数
可以利用前缀和, 但这里不能直接减, 需要分奇偶. 令
所以, 维护
typedef long long ll;
const int N = 1e5;
const ll inf = 1e16;
int main()
{
int n;
ll s = 0, a1, mn[2] = {inf, 0}, mx[2] = {-inf, 0}, ans = -inf;
cin >> n >> a1;
For (i, 2, n) {
ll a;
cin >> a;
s += abs(a-a1) * ((i & 1) ? -1 : 1);
ans = max(ans, max(s - mn[1], -s + mx[0]));
mn[i & 1] = min(mn[i & 1], s);
mx[i & 1] = max(mx[i & 1], s);
a1 = a;
}
cout << ans << endl;
return 0;
}D. Weird journey
n个点m条边的无向图, 问有多少条无向的路径经过(m-2)条边恰好两次, 经过另外2条边恰好1次. 两条路径被认为是不同的当且仅当经过1次的边集不等. 可能有自环. 没有重边. (1≤n,m≤10^6)
一般无向图上的算法似乎会的不多......分为两类吧: 在生成树上搞事情, 欧拉路径......还有个一般图最大匹配. 其余问题差不多都是NPC.
大概要从那两条只经过1次的边入手. 绕了一些弯子, 发现可以把每条边复制两份, 问题转化为去掉两条边, 使得欧拉路径存在, 求方案数.
连通图上, 欧拉路径存在的充要条件是奇点只有0或2个. 充分性显然, 必要性可以用数学归纳法+分类讨论证明.
如果这两条边都不是自环, 则它们必须有一个公共点. 如果有一个自环, 另一个是什么都可以.
考虑判断无解. 有这样一条Announcement: Note that it is not necessary for good path to go through all cities, we care only about roads. 存在多个连通块是允许的, 只要除了其中的一个, 其余都是孤立的点. 做一遍DFS, 数一数连通块内有多少条边即可.
先是TLE一发, 好像不太可能死循环, 结果是cin的锅. 然后WA. 此时离结束只剩3分钟, 静态查错无果. GG.
问题出在判无解上. DFS写到一半, 想起Announcement, 才发觉不是要数连通块大小. 但是main函数里没改, 只从点1开始DFS......数据造得挺好, 考虑到了这种错误.
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
const int N = 1e6;
vector<int> adj[N + 1];
vector<ii> E;
bool vis[N + 1];
int num, cnt[N + 1];
void dfs(int u)
{
vis[u] = true;
num += adj[u].size();
Rep (i, 0, adj[u].size()) {
int v = adj[u][i];
if (!vis[v])
dfs(v);
}
}
int main()
{
ios::sync_with_stdio(false);
int n, m, loop = 0;
cin >> n >> m;
Rep (i, 0, m) {
int u, v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
if (u != v) E.pb(ii(u, v));
else ++loop;
}
For (i, 1, n)
if (!vis[i]) {
num = 0;
dfs(i);
if (num != 0 && num != m*2) {
cout << "0" << endl;
return 0;
}
}
ll ans = 0;
Rep (i, 0, E.size()) {
const ii& e = E[i];
ans += cnt[e.first] + cnt[e.second];
++cnt[e.first];
++cnt[e.second];
}
ans += (ll)loop * (m-loop) + (ll)loop*(loop-1)/2;
cout << ans << endl;
return 0;
}E. The Great Mixing
k种浓度为ai/1000的可乐, 每种无限杯, 要求混合成一杯浓度为n/1000的, 求最少总杯数, 或报告无解. 只能将正整数杯的可乐相互混合. 杯子里不能啥都不装. (所有数均为整数, 0≤n,ai≤1000, 1≤k≤10^6, 同一个ai可能多次出现)
设第i种取xi杯 (xi不同时为0), 则
相信机智的你一定知道子集和问题, 也能发现这样一个现象: 如果一些和为0的数都在[-U, U]的范围内, 那么总有一种次序, 使得前缀和均在[-U, U]的范围内. 因为嫌一个正数太大, 总是可以调小; 嫌一个负数太小, 总是可以调大.
把和看作点, 取一个数看作边, 则点数不超过2001, 边数不超过2001*1001, 从0开始跑一个BFS找一条回到0的最短路径即可.
也可以做1000^3的DP, 用bitset优化. 这就需要另一个事实: 如果有解, 答案不超过1000. 可以通过构造的方式说明这一点.
只考虑前两种浓度, 不妨设
不管是DP还是BFS, 有一点很重要: 转化为和等于0, 那么只用考虑[-1000,1000]内的状态.
const int N = 1000;
queue<int> Q;
int tot, d[2*N + 1], x[N + 1];
bool f[N + 1];
int main()
{
int n, k;
scanf("%d%d", &n, &k);
Rep (i, 0, k) {
int a;
scanf("%d", &a);
f[a] = true;
}
For (i, 0, N) if (f[i]) x[tot++] = i-n;
Q.push(0);
fill_n(d, 2*N+1, -1);
d[N] = 0;
while (!Q.empty()) {
int u = Q.front(); Q.pop();
Rep (i, 0, tot) {
if (u + x[i] == 0) {
printf("%d\n", d[u+N] + 1);
return 0;
}
if (abs(u + x[i]) <= N && d[u+x[i]+N] == -1) {
d[u+x[i]+N] = d[u+N] + 1;
Q.push(u+x[i]);
}
}
}
puts("-1");
return 0;
}const int N = 1000;
bitset<2*N + 1> pre, now;
bool f[N + 1];
int x[N + 1];
int main()
{
int n, k, tot = 0;
scanf("%d%d", &n, &k);
Rep (i, 0, k) {
int a;
scanf("%d", &a);
f[a] = true;
}
For (i, 0, N) if (f[i]) x[tot++] = i-n;
pre[N] = 1;
For (i, 1, N) {
now.reset();
Rep (j, 0, tot) {
if (x[j] >= 0)
now |= pre << x[j];
else
now |= pre >> -x[j];
}
if (now[N]) {
printf("%d\n", i);
return 0;
}
pre = now;
}
puts("-1");
return 0;
}第二种方法虽然理论时间复杂度劣于方法一, 但是实际跑起来却更快. 所以松爷n^2/64跑30w......
收获: 1. 如果分类讨论略复杂, 先考虑有没有更简单的一锅端. 如果没有, 就硬上, 不要犹豫. 平时不要害怕分类讨论. 2. 写代码的过程中改变了想法, 要想想所有与此有关的地方. 3. 转化为一堆数的和等于0是个不错的想法.