CF1198
CF1198A
CF1198A题意
有一种数字化一段录音的常用方式，是记录每一个时刻的强度值。这些非负的强度值就可以代表一段音频
对于一段音频，若有 \(K\) 个不同的强度值，那么每一位我们都需要 \(k = \lceil\log_2K \rceil\) \(\text{bit}\) 来存储
也就是说，为了存储这一段音频，我们需要 \(nk\) 个 \(\text{bit}\)
为了压缩音频大小，我们们采取如下的方式：
选择两个整数 \(l, r(l \leq r)\)，对于音频的强度值序列 \(v\)，将其作一次变换：
\[v_i = \begin{cases} v_i&l \leq v_i \leq r \\ l &v_i < l\\ r &r < v_i \end{cases} \]其中第 \(2, 3\) 种情况被视作 \(v_i\) 这个强度值被更改了
你的任务是对于给定的强度值序列 \(a\)，找到一组 \(l, r\)，使得在经过上述压缩后能够被大小为 \(I \ \text{bytes} (\text{1bytes = 8 bit})\) 的存储器装下，并最小化被更改的强度值的数量。
CF1198A题解
坏了坏了，Eric被1600爆杀了（
首先别读错题，\([l,r]\) 表示值域范围，不是下标范围。
然后计算最多保留的不同数字 \(k = 2^{\lfloor\frac{I}{n}\rfloor}\)。
直接暴力枚举左端点 \(l=i\)，则 \(r=i+k-1\)，预处理下在这个范围之外的数字有多少个即可。
时间复杂度 \(O(n)\)
CF1198A代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 4e5 + 10;
int n, I;
int a[maxn], b[maxn];
int pre[maxn], suf[maxn];
int buc[maxn];
int qpow(int x,int a){
int res = 1;
while(a){
if(a & 1)res = res * x;
if(res >= n)return n;
x = x * x;a >>= 1;
if(x >= n)x = n;
}
return res;
}
signed main(){
n = read(); I = read() * 8;
for(int i = 1;i <= n;i++){b[i] = a[i] = read();}
sort(b + 1,b + 1 + n);
int tot = unique(b + 1,b + 1 + n) - b - 1;
for(int i = 1;i <= n;i++){a[i] = lower_bound(b + 1,b + 1 + tot,a[i]) - b;}
for(int i = 1;i <= n;i++)buc[a[i]]++;
for(int i = 1;i <= tot;i++)pre[i] = buc[i] + pre[i - 1];
for(int i = tot;i;i--)suf[i] = buc[i] + suf[i + 1];
int ans = n, k = qpow(2,I / n);
if(k >= tot){puts("0");return 0;}
for(int i = 1;i + k - 1 <= tot;i++) ans = min(ans,pre[i - 1] + suf[i + k]);
printf("%lld\n",ans);
// printf("tot = %lld, k = %lld\n",tot, k);
return 0;
}
CF1198B
CF1198B题意
给出一个长度为 \(n\) 的数组 \(a\)，对它进行 \(m\) 次操作，每个操作如下：
- \(1\space u\space v\)：将 \(a_u\gets v\)。
- \(2\space u\)：将所有小于 \(u\) 的数改成 \(u\)。
问最后的数组。
CF1198B题解
操作 \(1\) 相当于单点修改，操作 \(2\) 相当于区间取 \(max\)，这东西线段树随便维护一下就OK了。
CF1198B代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 2e5 + 10;
int n, a[maxn], m;
struct Segment_Tree{
struct node{
int maxx, tag;
node(int maxx = 0,int tag = 0):maxx(maxx),tag(tag){}
}d[maxn << 2];
node mergenode(node l,node r){return node(max(l.maxx,r.maxx));}
void pushdown(int p){
if(d[p].tag){
d[p << 1].maxx = max(d[p].tag,d[p << 1].maxx);
d[p << 1].tag = max(d[p].tag,d[p << 1].tag);
d[p << 1 | 1].maxx = max(d[p].tag,d[p << 1 | 1].maxx);
d[p << 1 | 1].tag = max(d[p].tag,d[p << 1 | 1].tag);
d[p].tag = 0;
}
}
void build(int l,int r,int p){
if(l == r){d[p] = node(a[l]);return;}
int mid = l + r >> 1;
build(l,mid,p << 1);build(mid + 1,r,p << 1 | 1);
d[p] = mergenode(d[p << 1],d[p << 1 | 1]);
}
void update(int l,int r,int pos,int p,int upd){
if(l == r && l == pos){d[p] = node(upd);return;}
int mid = l + r >> 1;pushdown(p);
if(pos <= mid)update(l,mid,pos,p << 1,upd);
else update(mid + 1,r,pos,p << 1 | 1,upd);
d[p] = mergenode(d[p << 1],d[p << 1 | 1]);
}
void update(int l,int r,int s,int t,int p,int upd){
if(s <= l && r <= t){d[p].tag = max(d[p].tag,upd);d[p].maxx = max(d[p].maxx,upd);return;}
int mid = l + r >> 1;pushdown(p);
if(s <= mid)update(l,mid,s,t,p << 1, upd);
if(mid < t)update(mid + 1,r,s,t,p << 1 | 1,upd);
d[p] = mergenode(d[p << 1],d[p << 1 | 1]);
}
void query(int l,int r,int p){
if(l == r){printf("%d ",d[p].maxx);return;}
int mid = l + r >> 1;pushdown(p);
query(l,mid,p << 1);query(mid + 1,r,p << 1 | 1);
}
}tree;
signed main(){
n = read();for(int i = 1;i <= n;i++)a[i] = read();
tree.build(1,n,1);m = read();int u, opt;
for(int i = 1;i <= m;i++){
opt = read(); u = read();
if(opt == 1)tree.update(1,n,u,1,read());
else tree.update(1,n,1,n,1,u);
}
tree.query(1,n,1);
return 0;
}
CF1198C
CF1198C题意
给一个无向图，\(3\times n\) 个点， \(m\) 条边，请找大小为 \(n\) 的点独立集或边独立集，如果都没有报告无解。
CF1198C题解
首先不存在无解情况，理由很简单，每次加入边的时候，类似最小生成树的形式选择加入哪条边。
然后如果还剩下 \(k\ge n\) 个点没有被任何加入边覆盖，那就一定有点独立集，直接输出即可。
否则表明至少有 \(k\ge 2\times n+1\) 个点是联通的，这些点至少组成 \(n\) 条边，直接输出即可。
故不存在无解的情况，解法也在上文说完了。
CF1198C代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f= 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 1e5 + 10;
int n, m;
int book[maxn * 3], ans[maxn];
signed main(){
int T = read();
while(T--){
n = read() * 3;m = read();int cnt = 0;
for(int i = 1;i <= n;i++)book[i] = 0;
for(int i = 1;i <= m;i++){
int u = read(), v = read();
if(!book[u] && !book[v] && cnt < n / 3){book[u] = book[v] = 1;ans[++cnt] = i;}
}
if(cnt >= n / 3){
puts("Matching");
for(int i = 1;i <= n / 3;i++){printf("%d ",ans[i]);}
puts("");
}
else{
puts("IndSet");cnt = 0;
for(int i = 1;i <= n && cnt < n / 3;i++){
if(!book[i]){cnt++;printf("%d ",i);}
}
puts("");
}
}
return 0;
}