[题解向] 正睿Round435
2024-09-05 02:54:40
10.14
唔，这一场打得不好。获得了\(\rm 75pts/300pts\)的得分，但是居然可以获得\(\rm 27/69\)的名次，也不至于不满意……毕竟是真不会233
\(\rm T1\)
大概就是字典序那个地方比较爆炸……
于是就考虑奇数开头和偶数开头分开做，对于每种情况调整成一个合法最小代价序列。这个地方有一个贪心，原来在前面的依旧会在前面，在后面的也还会在后面，扫一遍就做完了。
这个贪心里面蕴含着一个性质。\(now_i<i,now_j<j\)，即“同向换”，那一定比交叉换代价更小。所以最优的答案会是一段一段相同方向的交换。那么考虑直接枚举对于一段相同方向的、相同奇偶性箭头，换一下彼此的顺序是不会影响结果的。所以就考虑对于同一块进行重排，方法（借鉴的std）大概就是用一个set去维护一下。
int ans[2][MAXN], now[MAXN] ; set <int> s ;
int N, Id[MAXN], base[MAXN], cnt[MAXN], Up[MAXN], cnt1 ;
void print(int *ans){
for (int i = 1 ; i <= N ; ++ i) cout << Up[ans[i]] << " " ;
}
int solve(int zt, int* res){
int fr = 0 ;
int ret = 0, a = zt, b = a ^ 1 ;
if (!a) a = 2 ; if (!b) b = 2 ;
for (int i = 1 ; i <= N ; ++ i){
int &x = Up[base[i]] & 1 ? a : b ;
res[x] = base[i], Id[base[i]] = i, x += 2 ;
}
// print(res) ;
for (int bg = 1 ; bg <= 2 ; ++ bg){
s.clear() ;
for (int l = bg, r = bg ; r <= N ; l = r, fr = 0){
while (r <= N && (Id[res[l]] < l) == (Id[res[r]] < r))
s.insert(r), now[++ fr] = res[r], r += 2 ;
sort(now + 1, now + fr + 1) ;
if (Id[res[l]] < l){
for (int i = 1 ; i <= fr ; ++ i){
int p = *s.lower_bound(Id[now[i]]) ;
s.erase(p), res[p] = now[i] ;
}
}
else {
for (int i = fr ; i >= 1 ; -- i){
int p = *-- s.upper_bound(Id[now[i]]) ;
s.erase(p), res[p] = now[i] ;
}
}
}
}
// print(res) ;
for (int i = 1 ; i <= N ; ++ i) ret += abs(Id[res[i]] - i) ; return ret ;
}
bool comp(int * a, int * b){
for (int i = 1 ; i <= N ; ++ i)
if (a[i] != b[i]) return a[i] < b[i] ;
return 0 ;
}
int main(){
cin >> N ; int i ;
for (i = 1 ; i <= N ; ++ i)
cin >> base[i], cnt1 += (base[i] & 1 == 1), Up[i] = base[i] ; sort(Up + 1, Up + N + 1) ;
for (i = 1 ; i <= N ; ++ i) base[i] = lower_bound(Up + 1, Up + N + 1, base[i]) - Up, base[i] += cnt[base[i]] ++ ;
if (N & 1) solve(N - cnt1 < cnt1, ans[0]), print(ans[0]) ;
else {
int x = solve(0, ans[0]), y = solve(1, ans[1]) ;
if (x < y || (x == y && comp(ans[0], ans[1]))) print(ans[0]) ;
else print(ans[1]) ;
}
return 0 ;
}
\(\rm T2\)
啧，根号分治，没怎么做过qaq。
首先就是\(nq\)暴力比较好写，但是自我感觉我写的暴力复杂度应该是优于普通暴力的，均摊下来或许在\(O(q\cdot \frac{n}{m})\)的亚子，但是似乎并没有这一档部分分，(；'⌒')。
然后就是正解。有一个求连通块的性质，就是当图\(\rm \{V,E\}\)是一棵森林的时候，有\(\rm S=V-E\)，其中\(\rm S\)即连通块个数。所以只需要考虑怎么维护边数就好。
考虑根号分治。即对于\(occur[i]\leq \sqrt n\)的颜色直接暴力修改，然后对于与这些块相邻的点，如果也是小颜色就不管，如果是大颜色就打上一个标记，意思是如果这个大颜色修改了的话，会如何影响这个小颜色的贡献。考虑假设\(i,i+1\)这个状态是\((1,1)\)，那么修改之后变成\((1,0)\),\(~\text {E-=1}\)，但是当时\(i\)变化（\(0\to 1\)）的时候是\(\text{E+=1}\)。大概这么分类讨论几波实际上就是抄的std就会发现规律。
然后对于大颜色，每次先算上打的标记（小颜色），然后考虑预处理出相邻大颜色点之间的边，询问时暴力\(\sqrt n\)扫过每一个大颜色计算贡献。
唔，然后就是\(q\sqrt n\)的复杂度了。
int ans1, ans2, E[MAXF][MAXF] ;
int N, M, K, base[MAXN], zt[MAXN], num[MAXN], Id[MAXN], cnt ;
int buc[MAXN], nxt[MAXN], tag[MAXN], s[MAXN], frx[MAXN], Lans, bk[MAXN], big[MAXN] ;
void Pre_links(){
memset(buc, 0, sizeof(buc)) ;
for (int i = N ; i >= 1 ; -- i)
if (!buc[base[i]])
nxt[i] = N + 1, buc[base[i]] = i ;
else nxt[i] = buc[base[i]], buc[base[i]] = i ;
memset(buc, 0, sizeof(buc)) ;
for (int i = 1 ; i <= N ; ++ i)
if (!buc[base[i]]) frx[base[i]] = i, buc[base[i]] = 1 ;
}
void Pre_blocks(){
for (int i = 1 ; i <= N ; ++ i){
scanf("%d", &base[i]) ;
if (base[i] == base[i - 1]) { N --, i -- ; continue ;}
buc[base[i]] ++ ;
}
for (int i = 1 ; i <= K ; ++ i) s[i] = buc[i] ;
for (int i = 1 ; i <= K ; ++ i)
if (buc[i] <= MAXS) num[i] = 1 ;
else num[i] = 2, big[++ cnt] = i, Id[i] = cnt ;
}
int main(){
//freopen("bulb3.in", "r", stdin) ;
//freopen("2.out", "w", stdout) ;
cin >> N >> M >> K ;
Pre_blocks(), Pre_links() ;
for (int i = 1 ; i <= cnt ; ++ i)
for (int j = frx[big[i]] ; j <= N ; j = nxt[j]){
if (j + 1 <= N && num[base[j + 1]] > 1)
E[i][Id[base[j + 1]]] ++ ;
if (j - 1 >= 1 && num[base[j - 1]] > 1)
E[i][Id[base[j - 1]]] ++ ;
}
while (M --){
int x, w ; scanf("%d", &x) ;
w = zt[x] ? -1 : 1, ans1 += w * s[x] ;
if (num[x] < 2){
if (!frx[x]) {
printf("%d\n", ans1 - ans2) ;
continue ;
}
for (int i = frx[x] ; i <= N ; i = nxt[i]) {
int o = base[i + 1], p = base[i - 1] ;
if (num[o] >= 2) tag[o] += w ;
if (num[p] >= 2) tag[p] += w ;
ans2 += (!zt[x] & zt[o]) - (zt[x] & zt[o]) ;
ans2 += (!zt[x] & zt[p]) - (zt[x] & zt[p]) ;
}
}
else {
ans2 += w * tag[x] ;
for (int i = 1 ; i <= cnt ; ++ i)
ans2 += ((!zt[x] & zt[big[i]]) - (zt[x] & zt[big[i]])) * E[Id[x]][i] ;
}
printf("%d\n", ans1 - ans2) ; zt[x] ^= 1 ;
}
return 0 ;
}
\(\rm T3\)
大概是一道小清新题，暴力很好写，然后就是考虑真正地设计状态：
令\(f_{i,j}\)表示前\(i\)个人选出\(j\)个人的集合的概率。
于是有两种转移（以下用\(p_1\)表示小标号赢的概率，\(p_2=1-p_1\)表示大标号赢的概率）：
考虑把\(i\)加入进来。那么\(f_{i,j}=f_{i-1,j-1}\cdot p_2^{i-j}+f_{i-1,j}\cdot p_1^{j}\)。前者是必须赢前面的\(i-j\)个人才能进集合，后者是必须输给\(j\)个人才能不在集合里面。
考虑把\(1\)加入进来。那么\(f_{i,j}=f_{i-1,j-1}\cdot p_1^{i-j}+f_{i-1,j}\cdot p_2^{j}\)。跟上面是对称的。
理解嘛…大概就是考虑每次是把当前更大的选进来还是更小的选进来。
然后就是比较神仙的点：联立！联立上面两个式子就会得到:
\[f_{i-1,j-1}\cdot p_2^{i-j}+f_{i-1,j}\cdot p_1^{j}=f_{i-1,j-1}\cdot p_1^{i-j}+f_{i-1,j}\cdot p_2^{j}
\]
\]
移项
\[f_{i-1,j}=\frac{p_1^{i-j}-p_2^{i-j}}{p_1^j-p_2^j}\cdot f_{i-1,j-1}
\]
\]
然后发现就跟\(i\)这一维无关了
#include <cstdio>
#include <cstring>
#include <iostream>
#define LL long long
#define MAXN 1500100
#define Mod 998244353
using namespace std ; LL ans ;
int stk[60], buc[30], cnt = 0, po[MAXN] ;
int N, M, A, B, P1, P2, Len[MAXN], dp[MAXN], f[MAXN] ;
int expow(int a, int b){
int res = 1 ;
while (b){
if (b & 1)
res = 1ll * res * a % Mod ;
a = 1ll * a * a % Mod, b >>= 1 ;
}
return res ;
}
int main(){
int i, j ; po[1] = 1 ;
cin >> N, M = (1 << N) - 1, cin >> A >> B ;
P1 = 1ll * A * expow(B, Mod - 2) % Mod, P2 = ((1 - P1) % Mod + Mod) % Mod ;
for (i = 1 ; i <= M ; ++ i) Len[i] = Len[i - (i & (-i))] + 1 ;
for (i = 2 ; i <= N ; ++ i) po[i] = (1ll * po[i - 1] * po[i - 1] % Mod + 2) % Mod ;
for (i = 1 ; i <= M ; ++ i){
cnt = 0 ; LL P = 1 ;
memset(buc, 0, sizeof(buc)) ;
for (j = 1 ; j <= N ; ++ j)
if ((1 << j - 1) & i)
stk[++ cnt] = j, buc[j] = 1 ;
for (j = 1 ; j <= N ; ++ j) buc[j] += buc[j - 1] ;
for (j = 1 ; j <= cnt ; ++ j){
P = P * expow(P2, stk[j] - 1 - buc[stk[j] - 1]) % Mod ;
P = P * expow(P1, N - stk[j] - buc[N] + buc[stk[j]]) % Mod ;
}
dp[i] = P ;
}
for (i = 1 ; i < M ; ++ i) f[Len[i]] = (f[Len[i]] + dp[i]) % Mod ;
for (i = 1 ; i < N ; ++ i) (ans += 1ll * f[i] * po[i]) %= Mod ; cout << ans << endl ; return 0 ;
}
最新文章
- CodeIgniter框架入门教程——第三课 URL及ajax
- transition代替简单的animation注意事项
- CSS3教程链接
- c# 使用hook来监控鼠标键盘事件的示例代码
- CSS3 transition 属性 过渡效果
- 将多个Sheet导入到同一个Excel文件中
- Qt 学习之路：元素布局
- 线性表（gcc实现）
- 2014.8.3情人节欢乐赛【Benny的农场】
- C++中常用特殊符号简介（& , * , : , :: , ->）
- 惊人go语言（image网站开发）
- linux安装oracle笔记
- Python 3.X安装配置
- 1.Cocos2d-x-3.2编写3d打飞机，粒子管理器代码
- 05-Eclispe配置Tomcat插件
- idea 方便的设置代码段
- stylus笔记（二）
- 【BZOJ3821/UOJ46】玄学（二进制分组，线段树）
- C# 调用存储过程 Sql Server存储过程 存储过程报错，程序中的try
- 16. 3Sum Closest(双指针)