CF1070
CF1070
和 Eric 共同处理的一套题，这里处理奇数题号。
A
Description
给定两个数 \(d(1\le d \le 500)\) 和 \(s(1\le s\le 5000)\)，找出最小数 \(n\) 使得 \(d\mid n\) 且\(n\) 的各个位数之和为 \(s\)。
Solution
数字很小，直接设状态 \((x,y)\) 表示和为 \(x\) 余数 \(y\) 是否出现过，记录一下转移的前缀。我们使用 BFS 确保最小。
Code
# include <bits/stdc++.h>
using namespace std;
# define PII pair< int , int >
# define MP make_pair
# define fi first
# define se second
const int D = 500 + 5 , S = 5000 + 5;
int s , d , vis[S][D];
queue< PII > Q;
pair< PII , int > f[S][D];
void Prt(int x , int y)
{
if(!x && !y) return ;
Prt(f[x][y].fi.fi , f[x][y].fi.se);
cout << f[x][y].se;
}
int main()
{
cin >> d >> s;
Q.push(MP(0 , 0));
vis[0][0] = 1;
while(!Q.empty())
{
int x = Q.front().fi , y = Q.front().se;
Q.pop();
for(int i = 0; i <= 9; i++)
{
int nx = x + i , ny = (y * 10 + i) % d;
if(nx <= s && !vis[nx][ny])
{
vis[nx][ny] = 1;
Q.push(MP(nx , ny));
f[nx][ny] = MP(MP(x , y) , i);
}
}
}
if(!vis[s][0]) cout << -1;
else Prt(s , 0);
return 0;
}
- 一开始从低位到高位扩展，无法处理连续 \(0\) 的数量，数位 DP 根本不熟啊。
C
Description
\(\text{Buber}\) 是一家致力于浪费投资者的钱的 \(\text{Berland}\) 技术公司。最近，\(\text{Buber}\) 决定将他的设施转移到云端。公司决定连续 \(n\) 天云端租用 \(\text{CPU}\)。\(\text{Buber}\)每天都要租用 \(k\) 个 \(\text{CPU}\)。
云端供应商提供 \(m\)个租用计划，第\(i\)个计划有如下的特征：
- \(l_i,r_i\) 表示第 \(i\) 个计划从第 \(l_i\) 天开始，第 \(r_i\) 天结束。
- \(c_i\) 表示第 \(i\) 个计划中，每天最多租用\(\text{CPU}\)个数。
- \(p_i\) 表示第 \(i\) 个计划中，租用一个\(\text{CPU}\)一天的花费。
\(\text{Buber}\) 可以同时使用多个计划，即他可以在第 \(x\) 天在每个进行中的计划（即\(l_i≤x≤r_i\)）中租用 \([0,c_i]\) 个 \(\text{CPU}\).
现在 \(\text{Buber}\) 告诉你正整数 \(k\) ，表示每天所需的 \(\text{CPU}\) 个数（如果某一天无论怎么租用都不能租到 \(k\) 个，他也希望租尽量多的\(\text{CPU}\)）。请你告诉他，他在这 \(n\) 天中最少需要花费多少钱来租用 \(\text{CPU}\)？
Solution
很简单，之间时间扫描线加一个权值线段树就做完了。
但是，为了做的更加复杂，学习了一下树状数组倍增，一样的道理，单点加，区间查，多余的部分用 set 存一下就好了。
Code
# include <bits/stdc++.h>
using namespace std;
# define int long long
int read()
{
# define C ch = getchar()
int x = 0; char C;
for(; ch > '9' || ch < '0'; C); for(; ch >= '0' && ch <= '9'; C) x = (x << 3) + (x << 1) + (ch ^ 48);
return x;
}
const int N = 1e6 + 5;
int n , k , m , ans;
set< int > s;
struct node
{
int val , num;
node() {}
node(int val , int num) : val(val) , num(num) {}
} ;
vector< node > vec[N];
struct BIT
{
int s1[N] , s2[N];
int Lowbit(int x) {return x & -x;}
void Upt(int x , int d1 , int d2) {for(; x < N; x += Lowbit(x)) s1[x] += d1 , s2[x] += d2;}
int Query1(int x) {int res = 0; for(; x; x -= Lowbit(x)) res += s1[x]; return res;}
int Query2(int x) {int res = 0; for(; x; x -= Lowbit(x)) res += s2[x]; return res;}
} bit;
signed main()
{
n = read() , k = read() , m = read();
for(int i = 1 , l , r , c , p; i <= m; i++)
{
l = read() , r = read() , c = read() , p = read();
vec[l].emplace_back(p , c);
vec[r + 1].emplace_back(p , -c);
}
for(int i = 1 , p , c; i <= n; i++)
{
for(auto x : vec[i])
{
p = x.val , c = x.num;
bit.Upt(p , c , p * c);
if(bit.Query1(p) - bit.Query1(p - 1)) s.insert(p);
else if(s.find(p) != s.end()) s.erase(p);
}
if(bit.Query1(N - 1) <= k) {ans += bit.Query2(N - 1); continue ;}
p = 0 , c = 0;
for(int j = 20; ~j; j--)
{
int np = p | (1 << j);
if(np > N - 1) continue ;
int nc = c + bit.s1[np];
if(nc > k) continue ;
p = np , c = nc;
}
ans += bit.Query2(p);
if(c == k) continue ;
p = *s.upper_bound(p);
ans += p * (k - c);
}
cout << ans;
return 0;
}
- 没什么难度，时间花在树状数组倍增上了。
E
Description
Polycarp有很多工作要做。最近他学会了一条新的时间管理技巧：“如果任务需要五分钟或更短时间，请立即执行”。Polycarp喜欢新技巧，但他不确定五分钟是最佳值。他认为这个值 d（分钟）应根据现有任务列表选择。
Polycarp有一份长度为 n 的要完成的任务清单。第 i 个任务有一个需要的时间Pi，即它确切地需要 Pi 分钟来完成。Polycarp从第一个到第 n 个逐个浏览任务。如果任务所需时间是 d 或更少，Polycarp立即开始执行任务。如果任务需要时间大于 d ，他不会去完成这个任务。列表中的任务的顺序是固定的了，所以，不容许你重新排序。当Polycarp阅读任务或跳过任务时，Polycarp不会花任何时间。
Polycarp有 T 分钟完成任务。但他不想一直工作。他决定在每做 m 个任务后休息一下。每次休息时间应该与完成这 m 个任务的时间相同。
Solution
是一个单峰函数，显然可以三分，但是我的三分一直是挂的。
考虑函数的性质，发现峰值一定是在一个因为时间超掉和任务无法做的临界值，那么我们就可以二分去找了。
Code
# include <bits/stdc++.h>
using namespace std;
# define int long long
int read()
{
# define C ch = getchar()
int x = 0; char C;
for(; ch > '9' || ch < '0'; C); for(; ch >= '0' && ch <= '9'; C) x = (x << 3) + (x << 1) + (ch ^ 48);
return x;
}
const int N = 2e5 + 5;
int n , m , t , p[N] , h[N] , cnt;
int check(int x)
{
cnt = 0;
int sum = 0 , res = 0 , tot = 0;
for(int i = 1; i <= n; i++)
{
if(p[i] > x) continue ;
if(sum + p[i] > t) return 0;
cnt++ , sum += p[i] , res += p[i] , tot++;
if(tot == m) sum += res , res = 0 , tot = 0;
}
return 1;
}
void solve()
{
n = read() , m = read() , t = read();
for(int i = 1; i <= n; i++) h[i] = p[i] = read();
sort(h + 1 , h + n + 1);
int _n = unique(h + 1 , h + n + 1) - h - 1;
int l = 1 , r = _n;
while(l < r)
{
// cout << l << ' ' << r << endl;
int mid = l + r + 1 >> 1;
if(check(h[mid])) l = mid;
else r = mid - 1;
}
check(h[l]);
// cout << '*';
int a0 = cnt , a1 = 0;
if(l < _n) check(h[l + 1]) , a1 = cnt;
if(!a0 && !a1) cout << "0 1\n";
else if(a0 < a1) cout << a1 << ' ' << h[l + 1] << '\n';
else cout << a0 << ' ' << h[l] << '\n';
}
signed main()
{
int T = read();
while(T--) solve();
return 0;
}
I
Descriptioin
给一个 \(n \leq 600\) 个点 \(m \leq 600\) 条边的无向图和一个参数 \(k\)，现在需要对图上的所有边染色，满足：
- 所有颜色为 \(1\) 至 \(100500\) 间的整数；
- 同种颜色的边最多两条；
- 每个点周围所有边的不同颜色数 \(\le k\)。
构造染色方案，若无解输出 \(m\) 个 \(0\)。
Solution
以为是什么神奇构造，其实是个网络流。
现在我们知道这个是网络流，那么我们反过来想想有什么线索告诉我们这个是网络流呢？首先这个数据范围就很网络流，之后是限制条件，同种颜色的边最多两条，限制很紧，单范围不大。有点有边的情况我们考虑 \(n\) 个点表示点 \(m\) 个点表示边。
我们记点的度数为 \(d\)，一个点的所有边中有 \(a\) 对相同颜色的边，那么 \(d-a\leq k\)，我们就能够得到 \(a\) 的最小值 \(d-k\)（这里就有一个判无解的地方了）。
之后怎么办？考虑一条边，只能给一个端点对于 \(a\) 一点贡献，因为至多两条同种颜色边，一对相同颜色边只可能在一个点里。
之后就好处理了，连边跑最大流，通过流量是否为 \(0\) 判断给了哪个点贡献。
Code
# include <bits/stdc++.h>
using namespace std;
int read()
{
# define C ch = getchar()
int x = 0; char C;
for(; ch > '9' || ch < '0'; C); for(; ch >= '0' && ch <= '9'; C) x = (x << 3) + (x << 1) + (ch ^ 48);
return x;
}
const int N = 1e5 , INF = 0x3f3f3f3f;
int n , m , k , deg[N] , sum , col[N] , cnt;
int ecnt = 1 , head[N] , nxt[N] , to[N] , w[N];
vector< int > e[N];
void AddEdge(int u , int v , int w)
{
nxt[++ecnt] = head[u] , head[u] = ecnt , to[ecnt] = v , ::w[ecnt] = w;
nxt[++ecnt] = head[v] , head[v] = ecnt , to[ecnt] = u , ::w[ecnt] = 0;
}
int s , t , lev[N] , cur[N];
bool BFS()
{
for(int i = s; i <= t; i++) lev[i] = -1 , cur[i] = head[i];
lev[s] = 0;
queue< int > Q;
Q.push(s);
while(!Q.empty())
{
int u = Q.front(); Q.pop();
for(int i = head[u]; i; i = nxt[i])
{
int v = to[i];
if(w[i] && lev[v] == -1)
{
lev[v] = lev[u] + 1 , Q.push(v);
if(v == t) return 1;
}
}
}
return 0;
}
int Dinic(int u , int flow)
{
if(u == t) return flow;
int res = 0 , delta;
for(int &i = cur[u]; i; i = nxt[i])
{
int v = to[i];
if(lev[v] > lev[u] && w[i])
{
delta = Dinic(v , min(flow - res , w[i]));
if(delta)
{
w[i] -= delta;
w[i ^ 1] += delta;
res += delta;
if(res == flow) break ;
}
}
}
if(res != flow) lev[u] = -1;
return res;
}
int MaxFlow()
{
int res = 0;
while(BFS()) res += Dinic(s , INF);
return res;
}
void solve()
{
n = read() , m = read() , k = read();
ecnt = 1;
cnt = sum = 0;
s = 0 , t = n + m + 1;
for(int i = s; i <= t; i++) deg[i] = head[i] = col[i] = 0 , e[i].clear();
for(int i = 1 , u , v; i <= m; i++)
{
u = read() , v = read();
deg[u]++ , deg[v]++;
AddEdge(s , i , 1) , AddEdge(i , u + m , 1) , AddEdge(i , v + m , 1);
}
for(int i = 1; i <= n; i++)
{
if(deg[i] > k * 2)
{
for(int i = 1; i <= m; i++) cout << 0 << ' '; cout << '\n';
return ;
}
int out = max(0 , deg[i] - k);
AddEdge(i + m , t , out * 2);
sum += out * 2;
}
int ans = MaxFlow();
if(ans != sum)
{
for(int i = 1; i <= m; i++) cout << 0 << ' '; cout << '\n';
return ;
}
for(int i = 1; i <= m; i++)
{
if(!w[i * 6 - 2]) e[to[i * 6 - 2] - m].push_back(i);
else if(!w[i * 6]) e[to[i * 6] - m].push_back(i);
}
for(int i = 1; i <= n; i++)
for(int j = 0; j < e[i].size(); j += 2)
col[e[i][j]] = col[e[i][j + 1]] = ++cnt;
for(int i = 1; i <= m; i++)
{
if(!col[i]) col[i] = ++cnt;
cout << col[i] << ' ';
}
cout << '\n';
}
int main()
{
int T = read();
while(T--) solve();
return 0;
}
- 笑死，根本想不到网络流。
讲个笑话：
lev[v] == lev[u] + 1
调了 \(40\) 分钟。
浙公网安备 33010602011771号