Codeforces Round #584 (Div. 1 + Div. 2)
Contest Page
A
sol
每次选最小的，然后把它的所有倍数都删掉。#include
using namespace std;
int read(){
int a = 0; char c = getchar(); bool f = 0;
while(!isdigit(c)){f = c == '-'; c = getchar();}
while(isdigit(c)){
a = a * 10 + c - 48; c = getchar();
}
return f ? -a : a;
}
set < int > num;
int main(){
int N , cnt = 0; cin >> N;
for(int i = 1 ; i <= N ; ++i){int a; cin >> a; num.insert(a);}
while(!num.empty()){
++cnt; int val = *num.begin();
for(int i = val ; i <= 100 ; i += val)
if(num.find(i) != num.end()) num.erase(i);
}
cout << cnt;
return 0;
}
B
sol
因为$lcm(2,3,4,5)=120$，所以在所有灯都开始闪了之后$120sec$之后到达的状态一定一致。所以暴力做$>125$轮即可。#include
using namespace std;
int num[1003] , N , A[1003] , B[1003];
int main(){
cin >> N;
for(int i = 1 ; i <= N ; ++i){
char c = getchar(); while(!isdigit(c)) c = getchar();
num[i] = c - '0';
}
for(int i = 1 ; i <= N ; ++i) cin >> A[i] >> B[i];
int ans = 0; for(int i = 1 ; i <= N ; ++i) ans += num[i];
for(int i = 1 ; i <= 250 ; ++i){
for(int j = 1 ; j <= N ; ++j)
if(i >= B[j] && (i - B[j]) % A[j] == 0)
num[j] ^= 1;
int sum = 0; for(int j = 1 ; j <= N ; ++j) sum += num[j];
ans = max(ans , sum);
}
cout << ans; return 0;
}
C
sol
枚举$i \in [0 , 8]$，先将$\leq i$的所有数都染$1$，然后将最后染$1$的位置之后的所有数值为$i+1$的位置染$1$，最后把剩下的数染$2$，check是否合法即可。#include
using namespace std;
int T; bool vis[200003];
int main(){
ios::sync_with_stdio(0);
for(cin >> T ; T ; --T){
int L; string s; cin >> L >> s; bool getans = 0;
for(int i = 0 ; i < 9 && !getans ; ++i){
memset(vis , 0 , sizeof(bool) * (s.size()));
int mx = 0 , pre = -1; bool flg = 1;
for(int j = 0 ; j < s.size() ; ++j)
if(s[j] - '0' <= i){
if(mx > s[j] - '0'){flg = 0; break;}
pre = j; mx = max(mx , s[j] - '0'); vis[j] = 1;
}
if(!flg) continue;
for(int j = pre + 1 ; j < s.size() ; ++j)
if(s[j] - '0' == i + 1) vis[j] = 1;
mx = 0;
for(int j = 0 ; j < s.size() ; ++j)
if(!vis[j]){
if(mx > s[j] - '0'){flg = 0; break;}
mx = s[j] - '0';
}
if(flg){
getans = 1;
for(int i = 0 ; i < s.size() ; ++i) putchar(vis[i] ? '1' : '2');
}
}
if(!getans) putchar('-');
putchar('\n');
}
return 0;
}
D
sol
对于$a=i,b=j$连边$(i,j)$，对于每一个连通块一定是先选择一条边，然后一直选择恰好有一端被标记过的边直到所有点被标记，那么一个连通块的贡献是$sz-1$。并查集实现连通块即可。#include
using namespace std;
const int _ = 1e5 + 7;
int N , K , fa[_] , sz[_];
int find(int x){return fa[x] == x ? x : (fa[x] = find(fa[x]));}
int main(){
cin >> N >> K; for(int i = 1 ; i <= N ; ++i) sz[fa[i] = i] = 1;
for(int i = 1 ; i <= K ; ++i){
int p , q; cin >> p >> q;
p = find(p); q = find(q);
if(p == q) continue;
fa[p] = q; sz[q] += sz[p];
}
for(int i = 1 ; i <= N ; ++i) if(fa[i] == i) K -= sz[i] - 1;
cout << K; return 0;
}
E
sol
E1：发现在最优情况下只有最大值最大的$n$行有意义，拿出来暴力即可。E2：在上面假设的基础上，我们发现$n$比较小，考虑状压。
但是最大值必须要每一列都确定了才是确定的，似乎有后效性。那么我们考虑在某一列位置确定的时候钦定某些位置当作最大值计算贡献，那么答案显然和原来的答案是一样的。
这样就可以状压了：设$f_{i,j}$表示前$i$列中集合为$j$的位置被钦定产生贡献，对于新来的一列先计算出所有旋转方案中钦定某些位置的最大贡献然后子集转移。复杂度$O(T(2^NN^2+3^N)$。
#include
using namespace std;
int arr[13][2003] , mx[2003] , id[2003] , dp[1 << 12] , val[1 << 12] , Mx[1 << 12] , N , M , T;
int main(){
for(cin >> T ; T ; --T){
cin >> N >> M; memset(dp , 0 , sizeof(dp)); memset(mx , 0 , sizeof(mx));
for(int i = 0 ; i < N ; ++i)
for(int j = 0 ; j < M ; ++j){
cin >> arr[i][j]; mx[j] = max(mx[j] , arr[i][j]);
}
for(int j = 0 ; j < M ; ++j) id[j] = j;
sort(id , id + M , [&](int p , int q){return mx[p] > mx[q];});
for(int i = 0 ; i < min(N , M) ; ++i){
memset(Mx , 0 , sizeof(Mx));
#define lowbit(x) ((x) & -(x))
for(int j = 0 ; j < N ; ++j)
for(int k = 1 ; k < 1 << N ; ++k){
val[k] = val[k - lowbit(k)] + arr[(j + (int)log2(lowbit(k) + 0.1)) % N][id[i]];
Mx[k] = max(Mx[k] , val[k]);
}
for(int k = (1 << N) - 1 ; k >= 0 ; --k){
int s = k; while(s){dp[k] = max(dp[k] , dp[s ^ k] + Mx[s]); s = (s - 1) & k;}
}
}
cout << dp[(1 << N) - 1] << endl;
}
return 0;
}
F
sol
对于每条边以其编号位数为权值跑最短路，建出最短路DAG，那么每个点的答案只有可能由最短路DAG上的路径构成。然后按照DAG拓扑序求出答案。对于每个点找到其在DAG上的所有前驱，两两比较数字串字典序大小。总串长度不长，可以通过建Trie树把每个点对应的串放上去然后求LCA比较字典序。VP的时候没想很多写了个比较麻烦的做法：
对于已求出的每个点确定其最短路转移的唯一前驱，这样就把最短路DAG变成了最短路树。那么二分第一个字符不相同的位置$mid$，然后在最短路树上倍增求出两个字符串的长度为$mid$的前缀的哈希值check，最后通过倍增得到对应位置的两个字符判断哪一个小。
#include
using namespace std;
int read(){
int a = 0; char c = getchar(); bool f = 0;
while(!isdigit(c)){f = c == '-'; c = getchar();}
while(isdigit(c)){
a = a * 10 + c - 48; c = getchar();
}
return f ? -a : a;
}
#define PII pair < int , int >
const int _ = 1e5 + 7 , MOD = 1e9 + 7 , MOD2 = 1e9 + 9;
priority_queue < PII > q;
vector < PII > Edge[_];
int logg10[_] , dis[_] , N , M , jump[_][20] , val[_] , ans[_]; long long faid[_];
int gethash(int x , int len , int id){
int now;
if(len > dis[x]){now = val[x]; len -= dis[x];}
else{
for(int i = 19 ; i >= 0 ; --i) if(dis[jump[x][i]] >= len) x = jump[x][i];
now = val[jump[x][0]]; len -= dis[jump[x][0]]; id = faid[x];
}
while(logg10[id] != len - 1) id /= 10;
for(int i = 0 ; i < len ; ++i) now = 1ll * now * 10 % MOD2;
return (now + id) % MOD2;
}
int getch(int x , int len , int id){
if(len > dis[x]) len -= dis[x];
else{
for(int i = 19 ; i >= 0 ; --i) if(dis[jump[x][i]] >= len) x = jump[x][i];
len -= dis[jump[x][0]]; id = faid[x];
}
while(logg10[id] != len - 1) id /= 10;
return id % 10;
}
bool cmp(int p , int q , int idp , int idq){
if(!p) return 1;
int L = 1 , R = logg10[idp] + 1 + dis[p];
while(L < R){
int mid = (L + R) >> 1;
gethash(p , mid , idp) != gethash(q , mid , idq) ? R = mid : L = mid + 1;
}
return getch(p , L , idp) > getch(q , L , idq);
}
void done(int x , int pre , int nid){
ans[x] = ans[pre]; for(int i = 0 ; i <= logg10[nid] ; ++i) ans[x] = ans[x] * 10ll % MOD;
val[x] = val[pre]; for(int i = 0 ; i <= logg10[nid] ; ++i) val[x] = val[x] * 10ll % MOD2;
ans[x] = (ans[x] + nid) % MOD; val[x] = (val[x] + nid) % MOD2;
faid[x] = nid; jump[x][0] = pre;
for(int i = 1 ; jump[x][i - 1] ; ++i) jump[x][i] = jump[jump[x][i - 1]][i - 1];
}
void dijk(){
memset(dis , 0x3f , sizeof(dis)); dis[0] = dis[1] = 0; q.push(PII(0 , 1));
while(!q.empty()){
PII t = q.top(); q.pop();
if(dis[t.second] != -t.first) continue;
int now = 0 , nid = 0;
for(auto p : Edge[t.second])
if(dis[p.first] + logg10[p.second] + 1 == dis[t.second])
if(cmp(now , p.first , nid , p.second)){
now = p.first; nid = p.second;
}
if(now) done(t.second , now , nid);
for(auto p : Edge[t.second])
if(dis[p.first] > dis[t.second] + logg10[p.second] + 1){
dis[p.first] = dis[t.second] + logg10[p.second] + 1;
q.push(PII(-dis[p.first] , p.first));
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
N = read(); M = read(); logg10[0] = -1;
for(int i = 1 ; i <= M ; ++i) logg10[i] = logg10[i / 10] + 1;
for(int i = 1 ; i <= M ; ++i){
int p = read() , q = read();
Edge[p].push_back(PII(q , i)); Edge[q].push_back(PII(p , i));
}
dijk();
for(int i = 2 ; i <= N ; ++i) printf("%d\n" , ans[i]);
return 0;
}
G
sol
G1：考虑将序列分成若干个极小块，每一块中包含若干种颜色且其他块中不包含这些颜色。那么每一个块的贡献就是块长减去出现次数最多的数字数量。求出这个极小块直接从左往右扫一遍维护当前块已经出现的颜色和如果当前颜色形成极小块块长是多少就可以了。
G2：我们把G1中的贪心思路变得更加可维护一些：
对于某种颜色记录其最开始和最后出现的位置$(p,q)$，那么在数轴上它代表一条线段$[p,q]$，权值为其出现次数。
这些线段可以把$[1,N]$分为若干个极小的部分，满足两个部分之间没有线段相交。答案就是$N-$所有部分的最大权值。
E.g 对于序列$3,3,1,2,1,2$，颜色$1,2,3$分别对应线段$[3,5],[4,6],[1,2]$，可以发现将原序列分为了$[1,2]$和$[3,6]$两个部分，两个部分的最大权值都是$2$，所以答案就是$6-2-2=2$。
我们对于$\frac{i}{2} , i \in [1,2N+1]$这些位置为下标建立线段树，那么如果我们把线段$[p,q]$在线段树上看作区间$[p,q]$中的点权值$+1$的话，一个极小的部分会表现为：这个部分的左邻居和右邻居的权值都是$0$，而中间没有权值为$0$的点。
这样我们把一条线段的贡献放在线段的左端点上，相当于每一个点有一个价值，然后在线段树上维护：区间$min$、当前区间中最靠左的$min$左边的所有价值的$max$、当前区间中最靠右的$min$右边的所有价值的$max$、当前整个区间的价值的$max$和区间的答案，就可以在线段树上进行pushup更新出整个序列中每个部分的最大价值和。
而修改只要做区间权值$\pm 1$、单点价值修改这两个操作。在线段树上打一个标记就能实现。
#include
using namespace std;
int read(){
int a = 0; char c = getchar(); bool f = 0;
while(!isdigit(c)){f = c == '-'; c = getchar();}
while(isdigit(c)){
a = a * 10 + c - 48; c = getchar();
}
return f ? -a : a;
}
const int _ = 2e5 + 11;
struct DATA{
int mn , mx , lftmx , rhtmx , sum , mrk;
DATA(){mn = 0; lftmx = rhtmx = sum = mrk = 0;}
friend DATA merge(DATA &p , DATA &q){
DATA t; t.mx = max(p.mx , q.mx);
if(p.mn == q.mn){
t.lftmx = p.lftmx; t.rhtmx = q.rhtmx;
t.mn = p.mn; t.sum = p.sum + q.sum + max(p.rhtmx , q.lftmx);
}
else if(p.mn < q.mn){t.mn = p.mn; t.sum = p.sum; t.lftmx = p.lftmx; t.rhtmx = max(p.rhtmx , q.mx);}
else{t.mn = q.mn; t.sum = q.sum; t.lftmx = max(p.mx , q.lftmx); t.rhtmx = q.rhtmx;}
return t;
}
void mark(int x){mrk += x; mn += x;}
};
namespace segt{
DATA now[_ << 3];
#define mid ((l + r) >> 1)
#define lch (x << 1)
#define rch (x << 1 | 1)
void down(int x){now[lch].mark(now[x].mrk); now[rch].mark(now[x].mrk); now[x].mrk = 0;}
void M1(int x , int l , int r , int L , int R , int val){
if(l >= L && r <= R) return now[x].mark(val);
down(x); if(mid >= L) M1(lch , l , mid , L , R , val);
if(mid < R) M1(rch , mid + 1 , r , L , R , val);
now[x] = merge(now[lch] , now[rch]);
}
void M2(int x , int l , int r , int tar , int val){
if(l == r){now[x].mx = val; return;}
down(x); mid >= tar ? M2(lch , l , mid , tar , val) : M2(rch , mid + 1 , r , tar , val);
now[x] = merge(now[lch] , now[rch]);
}
}
int N , Q , arr[_]; set < int > pos[_];
int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
N = read(); Q = read(); for(int i = 1 ; i <= N ; ++i) pos[arr[i] = read()].insert(i);
for(int i = 1 ; i <= 200000 ; ++i)
if(pos[i].size()){
segt::M2(1 , 1 , 2 * N + 1 , 2 * (*pos[i].begin()) , pos[i].size());
segt::M1(1 , 1 , 2 * N + 1 , 2 * (*pos[i].begin()) , 2 * (*--pos[i].end()) , 1);
}
printf("%d\n" , N - segt::now[1].sum);
while(Q--){
int p = read() , x = read() , t = arr[p];
if(pos[t].size() != 1)
if(p == *pos[t].begin()){
segt::M2(1 , 1 , 2 * N + 1 , 2 * p , 0);
segt::M2(1 , 1 , 2 * N + 1 , 2 * (*++pos[t].begin()) , pos[t].size() - 1);
segt::M1(1 , 1 , 2 * N + 1 , 2 * p , 2 * (*++pos[t].begin()) - 1 , -1);
}
else{
if(p == *--pos[t].end())
segt::M1(1 , 1 , 2 * N + 1 , 2 * (*----pos[t].end()) + 1 , 2 * (*--pos[t].end()) , -1);
segt::M2(1 , 1 , 2 * N + 1 , 2 * (*pos[t].begin()) , pos[t].size() - 1);
}
else{
segt::M2(1 , 1 , 2 * N + 1 , 2 * p , 0);
segt::M1(1 , 1 , 2 * N + 1 , 2 * p , 2 * p , -1);
}
pos[t].erase(p); pos[arr[p] = x].insert(p);
if(pos[x].size() != 1)
if(p == *pos[x].begin()){
segt::M2(1 , 1 , 2 * N + 1 , 2 * p , pos[x].size());
segt::M2(1 , 1 , 2 * N + 1 , 2 * (*++pos[x].begin()) , 0);
segt::M1(1 , 1 , 2 * N + 1 , 2 * p , 2 * (*++pos[x].begin()) - 1 , 1);
}
else{
if(p == *--pos[x].end())
segt::M1(1 , 1 , 2 * N + 1 , 2 * (*----pos[x].end()) + 1 , 2 * (*--pos[x].end()) , 1);
segt::M2(1 , 1 , 2 * N + 1 , 2 * (*pos[x].begin()) , pos[x].size());
}
else{
segt::M2(1 , 1 , 2 * N + 1 , 2 * p , 1);
segt::M1(1 , 1 , 2 * N + 1 , 2 * p , 2 * p , 1);
}
printf("%d\n" , N - segt::now[1].sum);
}
return 0;
}
H
sol
注意到$E=t(1-v)$（这里应该写积分，这样写相当于直接微元法考虑速度相同的一段），设$v_0 = v-1$，那么$E=t(1-(v_0+1)) = -v_0t = -S$，也就是说在这种情况下人走过的距离和能量是相反数。当然为了计算的正确，所有传送带的速度都$+1$，其中没有传送带的地方认为是$s_i=0$的传送带。此时$v_0 \in [-1,1]$。那么如果消耗$\Delta E$的能量，人走过的距离就是$\Delta E$，那么如果使用能量的这段时间走过了速度为$v_i$、长度为$l_i$的传送带，时间就一定是$\frac{l_i - \Delta E}{v_i}$，和中间的分配无关。那么我们可以认为在同一段传送带上能量的分配是均匀的，也就是能量和路程呈一次函数关系。
到这里不难发现能量放在速度更低的位置比放在更高的位置一定更优，因为更低的位置分母更小，更多的能量加入可以提供更小的时间。
我们以路程为$x$轴、能量为$y$轴，可以画出一个函数图像。这个图像的每一段都是一次函数，这意味着我们只需要关注拐点，也就是传送带之间的交点位置。我们需要这个图像满足以下条件：
1、任何时刻纵坐标不小于$0$；
2、满足上述的贪心条件；
3、因为人的速度在$[-1,1]$内，所以两个拐点之间的直线斜率有一定的限制。
考虑得到限制3中的斜率。因为消耗能量的速度$v_0 \in [-1,1]$，所以$\frac{\Delta E}{\frac{(l - \Delta E)}{v}} \in [-1,1]$，解一下可以解出$\Delta E \in [\frac{l}{1-v} , \frac{l}{1+v}]$。
我们已经将问题转化成了一个更加可做的问题，接下来开始构造函数。
首先我们用最节省能量的方法走过所有的传送带。注意到当传送带速度为$1$时可以无限保存能量，但因为传送带速度至少为$1$，所以后面的过程中这些能量也会用在自己身上，所以我们可以认为速度为$1$的传送带不需要节省能量。
接下来我们按照传送带速度从小到大考虑每个传送带，并尽可能将能量用在上面。这里会受到上面图像条件中1,3的约束，对于3比较好维护，对于1，我们在某个位置使用了$\Delta E$的能量，那么在这个位置以及之后的所有位置能量都会减少$\Delta E$，也就是说我们减少的量最多不能超过当前位置之后的所有位置的能量最小值。
不难发现这需要我们进行区间减法和区间取min操作，可以用线段树实现。
#include
using namespace std;
#define ld long double
#define PDI pair < ld , int >
const int _ = 4e5 + 3;
map < int , ld > nval; vector < int > pos; int N , L; ld ubd[_] , sum[_] , E[_]; vector < PDI > seg;
namespace segt{
ld mn[_ << 2] , mrk[_ << 2];
#define mid ((l + r) >> 1)
#define lch (x << 1)
#define rch (x << 1 | 1)
void mark(int x , ld val){mn[x] += val; mrk[x] += val;}
void down(int x){mark(lch , mrk[x]); mark(rch , mrk[x]); mrk[x] = 0;}
void init(int x , int l , int r){
if(l == r) (void)(mn[x] = sum[l]);
else{init(lch , l , mid); init(rch , mid + 1 , r); mn[x] = min(mn[lch] , mn[rch]);}
}
void modify(int x , int l , int r , int L , int R , ld val){
if(l >= L && r <= R) return mark(x , val);
down(x); if(mid >= L) modify(lch , l , mid , L , R , val);
if(mid < R) modify(rch , mid + 1 , r , L , R , val);
mn[x] = min(mn[lch] , mn[rch]);
}
ld qry(int x , int l , int r , int L , int R){
if(l >= L && r <= R) return mn[x];
down(x);
ld mn = 1e18; if(mid >= L) mn = qry(lch , l , mid , L , R);
if(mid < R) mn = min(mn , qry(rch , mid + 1 , r , L , R));
return mn;
}
}using namespace segt;
int main(){
scanf("%d %d" , &N , &L);
for(int i = 1 ; i <= N ; ++i){
int X , Y; ld val; scanf("%d %d %Lf" , &X , &Y , &val);
pos.push_back(X); pos.push_back(Y); nval[X] = val;
}
pos.push_back(0); pos.push_back(L); sort(pos.begin() , pos.end());
pos.resize(unique(pos.begin() , pos.end()) - pos.begin());
for(int i = 1 ; i < pos.size() ; ++i){
ld val = nval[pos[i - 1]] + 1; seg.push_back(PDI(val , i));
sum[i] = sum[i - 1] - (E[i] = val != 1 ? (pos[i] - pos[i - 1]) / (1.0 - val) : 0);
ubd[i] = (pos[i] - pos[i - 1]) / (val + 1.0) - E[i];
}
segt::init(1 , 1 , seg.size()); sort(seg.begin() , seg.end());
for(auto t : seg){
int id = t.second; ld mn = min(ubd[id] , segt::qry(1 , 1 , seg.size() , id , seg.size()));
E[id] += mn; segt::modify(1 , 1 , seg.size() , id , seg.size() , -mn);
}
ld ans = 0;
for(int i = 1 ; i < pos.size() ; ++i) ans += (pos[i] - pos[i - 1] - E[i]) / (nval[pos[i - 1]] + 1);
cout << fixed << setprecision(11) << ans; return 0;
}