CSP - S 模拟9
赛时T2想了两个小时无果，极限一小时写T3
险些模拟退役，最后3分钟调出来T3
A ARC125C
考场上打表找规律
我们先把 \(k\) 个数放好，考虑一个一个贪心插入。
每回插入尽可能小的值，只能插一个，否则会延长LIS，最后插入很大的一串数字，为了防止LIS延长，我们倒序插入
B ARC125D
启发：dp之前观察性质，找到某个东西的充分必要条件
利用注意力：我们注意到一个序列是合法的，当且仅当，子序列任意两个元素在原序列位置中，不会出现另一个与这两个元素相同的元素
利用性质设计dp
\(dp_i = \sum{dp_j},i, j之间不存在与a_i, a_j相等的元素\)
\(ans = \sum{dp_i}, i是a_i最后一次出现\)
可以利用数据结构优化到 \(O(nlogn)\)
C ARC126C
首先考虑 \(ans\)的范围，是\([\lfloor{\frac{k}{n}} \rfloor,
\lfloor{\frac{k}{n}} \rfloor + mx]\)
我们枚举所有可能情况，判断是否合法
考虑一个答案 \(ans\) 的花费：
\((\sum{ans - a_i\; mod\; ans}) - (ans * \text{ans的倍数个数})\)
简单整理，我们其实就是要优化
\(\sum{cnt_i * \lfloor{i / mod} \rfloor}\)
\(cnt_i\) 是值 \(i\) 出现的次数
它的循环节是 \(mod\)
优化复杂度到 \(O(nH_n)\) = \(O(nlogn)\)
D ARC126D
\(k\) 这么小，考虑状压
\(dp(i,s)\) 表示考虑到第 \(i\) 个位置，已经选择集合（已排序）为 \(s\)，最少移动次数
\(i\)如果选，那么就会对答案贡献逆序对，
如果不选，为了让两边的集合就会跨过 \(i\)跑到一起，贡献左右集合 \(size\) 的较小值
T1
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
int n, k;
int a[N], b[N], c[N];
set<int> s;
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> k;
for(int i = 1; i <= k; ++i) cin >> b[i];
for(int i = 1; i <= n; ++i){
s.insert(i);
}
for(int i = 1; i <= k; ++i){
s.erase(b[i]);
}
int cnta = 0;
for(int i = 1; i < k; ++i){
a[++cnta] = b[i];
if(s.empty()) continue;
auto it = s.begin();
if(*it < b[i]){
a[++cnta] = *it;
s.erase(it);
}
}
while(!s.empty()){
// cerr<<"s.size() = " << s.size()<<endl;
auto it = prev(s.end());
// cerr<<"out" <<*it<<endl;
if((*it) > b[k]) a[++cnta] = *it;
else break;
// cerr<<"will erase"<<endl;
s.erase(it);
}
// cerr<<"!"<<endl;
a[++cnta] = b[k];
while(!s.empty()){
auto it = prev(s.end());
assert((*it) <= b[k]);
a[++cnta] = *it;
s.erase(it);
}
for(int i = 1; i <= n; ++i){
cout << a[i] <<" ";
}
cout << endl;
return 0;
}
T2
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
const ll MOD = 998244353;
ll f[N];
int a[N];
int pos[N];
int pre[N], nxt[N];
int n;
struct bitree{
ll c[N];
int lowbit(int x){
return x & -x;
}
ll query(int x){
ll ret =0;
while(x){
ret = (ret + c[x]) % MOD;
x -= lowbit(x);
}
return ret;
}
void modify(int x, ll val){
while(x <= n){
c[x] = (c[x] + val) % MOD;
x += lowbit(x);
}
}
ll query(int l, int r){
return (query(r) - query(l - 1) + MOD) % MOD;
}
}bit;
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
for(int i = 1; i <= n; ++i){
pre[i] = pos[a[i]];
pos[a[i]] = i;
}
for(int i = 1; i <= n; ++i){
pos[i] = n + 1;
}
for(int i = n; i >= 1; --i){
nxt[i] = pos[a[i]];
pos[a[i]] = i;
}
for(int i = 1; i <= n; ++i){
if(pre[i] == 0) f[i] = 1;
f[i] = (f[i] + bit.query(max(pre[i], 1), i - 1)) % MOD;
/*
for(int j = max(pre[i], 1); j < i; ++j){
f[i] = (f[i] + f[j]) % MOD;
}*/
bit.modify(i, f[i]);
if(pre[i]){
bit.modify(pre[i], -f[pre[i]]);
f[pre[i]] = 0;
}
}
ll ans = 0 ;
for(int i = 1; i <= n;++i){
if(nxt[i] == n + 1){
ans = (ans + f[i]) % MOD;
}
}
cout << ans << endl;
return 0;
}
T3
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5+10;
ll buc[N], pbuc[N];
int n;ll k;
ll mx;
ll sum;
ll calc(ll mod){
ll res = 0;
for(int i = mod; i <= mx; i += mod){
ll r = min(i + mod - 1, mx);
res = res + (pbuc[r] - pbuc[i - 1]) * (i / mod);
}
return res;
}
ll f[N], g[N];
ll getcost(ll mod){
ll res = 0;
if(mod <= mx)res = (mod * n - (sum - mod * g[mod]));
else res = mod * n - sum;
if(mod <= mx){
return res - mod * f[mod];
}else{
return res;
}
}
bool check(ll mod){
return getcost(mod) <= k;
}
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> k;
mx = 0;
for(int i = 1; i <= n; ++i){
ll tmp;
cin >> tmp;
buc[tmp]++;
sum += tmp;
mx = max(mx, tmp);
}
for(int i = 1; i <= mx; ++i) pbuc[i] = pbuc[i - 1] + buc[i];
for(int i = 1; i <= mx; ++i){
for(int j = 1; j * i <= mx; ++j){
f[i] += buc[j * i];
}
}
for(int mod = 1; mod <= mx; ++mod){
g[mod] = calc(mod);
}
ll l = floor(1.0 * k / n), r = ceil(1.0 * k / n) + mx;
for(ll i = r; i >= l; --i){
if(check(i)){
cout << i << endl;
return 0;
}
}
return 0;
}
T4
#include<bits/stdc++.h>
using namespace std;
const int N = 200+10, K = 20;
const int INF = 0x3f3f3f3f;
typedef bitset<8> bin;
int f[N][(1 << 17) +5];
int a[N];
int n, k;
struct popcount_t{
int data[(1 << 16) +5];
popcount_t(){
for(int i = 1; i <= (1 << 16); ++i){
data[i] = data[i >> 1] + (i & 1);
}
}
int operator ()(int x){
return data[x & 65535] + data[x >> 16];
}
}popcount;
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
memset(f, 0x3f, sizeof(f));
f[0][0] = 0;
for(int i = 1; i <= n; ++i){
int p = a[i] <= k ? 1 << (a[i] - 1) : 0;
for(int j = 0 ; j < (1 << k); ++j){
f[i][j] = f[i - 1][j] + min(popcount(j), k - popcount(j));
if(j & p){
f[i][j] = min(f[i][j], f[i - 1][j ^ p] + popcount(j >> (a[i])));
}
}
}
/*
for(int i = 1; i <= n; ++i){
cerr<<"i = " << i << endl;
for(int j = 0 ; j < (1 << k); ++j){
cerr<<bin(j) << " " << f[i][j] << endl;
}
cerr<<endl;
}*/
int ans = INF;
for(int i = 1; i <= n; ++i){
ans = min(ans, f[i][(1 << k) - 1]);
}
cout << ans << endl;
return 0;
}