#include<bits/stdc++.h>usingnamespace std;#defineintlonglongvoidsolve(){int n, m; cin >> n >> m;vector<int>a(n +1),b(m +1);int ans =0;for(int i =1; i <= n; i ++) cin >> a[i];for(int i =1; i <= m; i ++) cin >> b[i];for(int i =2; i <= n; i ++) ans +=labs(a[i]- a[i -1]);for(int i =2; i <= m; i ++) ans +=labs(b[i]- b[i -1]);cout << ans <<'\n';}signedmain(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t =1;// cin >> t;while(t --){solve();}return0;}
Problem I. 数据结构假象(线段树合并)
思路参考官方题解,用的线段树合并
#include<bits/stdc++.h>usingnamespace std;#defineintlonglongconstint N =5e5+5;structNode{int ch[2];int val;} tr[N *20];int rt[N];
stack<int> pool;int tot;// 新建结点 返回结点编号intnewnode(){if(pool.empty()){// tr.emplace_back();return(++ tot);}else{int res = pool.top(); pool.pop();return res;}}// 删除结点uvoiddel(int u){pool.push(u);tr[u].ch[0]= tr[u].ch[1]= tr[u].val =0;}// 单点修改: 加x个pos (当前结点为u 表示范围为[l,r])voidmodify(int&u,int l,int r,int pos,int x){if(!u) u =newnode();tr[u].val += x;if(l == r)return;int mid = l + r >>1;if(pos <= mid)modify(tr[u].ch[0], l, mid, pos, x);elsemodify(tr[u].ch[1], mid +1, r, pos, x);}// 区间查询: 返回[lq,rq]内数值个数 (当前结点为u 表示范围为[l,r])intquery(int u,int l,int r,int lq,int rq){if(rq < l || lq > r)return0;if(lq <= l && rq >= r)return tr[u].val;int mid = l + r >>1;returnquery(tr[u].ch[0], l, mid, lq, rq)+query(tr[u].ch[1], mid +1, r, lq, rq);}// 返回第k小的值intkth(int u,int l,int r,int k){if(l == r)return l;int mid = l + r >>1;if(tr[tr[u].ch[0]].val >= k)returnkth(tr[u].ch[0], l, mid, k);elsereturnkth(tr[u].ch[1], mid +1, r, k - tr[tr[u].ch[0]].val);}// 合并结点abintmerge(int a,int b){if(!a ||!b)return a + b;tr[a].val += tr[b].val;tr[a].ch[0]=merge(tr[a].ch[0], tr[b].ch[0]);tr[a].ch[1]=merge(tr[a].ch[1], tr[b].ch[1]);del(b);return a;}// 分裂以x为根的子树为xy两棵树 其中x的大小是kvoidsplit(int x,int&y,int k){if(!x)return;y =newnode();int v = tr[tr[x].ch[0]].val;if(k > v)split(tr[x].ch[1], tr[y].ch[1], k - v);elseswap(tr[x].ch[1], tr[y].ch[1]);if(k < v)split(tr[x].ch[0], tr[y].ch[0], k);tr[y].val = tr[x].val - k;tr[x].val = k;}voidsolve(){int n, m, k; cin >> n >> m >> k;vector<int>a(n +1),rst(1,-1),mod(1,-1);for(int i =1; i <= n; i ++){cin >> a[i];rst.push_back(a[i]/ k), mod.push_back(a[i]% k +1);}// 离散化sort(rst.begin(), rst.end()); rst.erase(unique(rst.begin(), rst.end()), rst.end());sort(mod.begin(), mod.end()); mod.erase(unique(mod.begin(), mod.end()), mod.end());vector<int>sz(rst.size());// sz[i]表示rst[i]的个数vector<int>pfx(rst.size());// sz的前缀和for(int i =1; i <= n; i ++){int id1 =lower_bound(rst.begin(), rst.end(), a[i]/ k)- rst.begin();int id2 =lower_bound(mod.begin(), mod.end(), a[i]% k +1)- mod.begin();sz[id1]++;modify(rt[id1],1, mod.size()-1, id2,1);}for(int i =1; i < rst.size(); i ++) pfx[i]= pfx[i -1]+ sz[i];int nw = rst.size()-1, unop =0;auto merge1 =[&](int nw)// 合并nw层和nw-1层{rt[nw -1]=merge(rt[nw -1], rt[nw]);sz[nw -1]+= sz[nw];pfx[nw -1]+= sz[nw];sz[nw]=0;unop =0;};while(m --){char c;int x;cin >> c >> x;if(c =='C'){int yu = sz[nw]- unop;// 当前层还剩下的if(yu >= x) unop += x;else{// 把当前层剩下的都减掉 相当于整体往下减一层x -= sz[nw]- unop;if(nw >1&& rst[nw]== rst[nw -1]+1)// 如果减一层能直接和下一层合并{merge1(nw --);}else// 不能和下一层合并{rst[nw]--;}while(x){if(nw ==1)// 当前层为最底层{int cnt = x / sz[nw];rst[nw]-= cnt;unop = x % sz[nw];x =0;}else// 还有下一层{int need =(rst[nw]- rst[nw -1])* sz[nw];// 将当前层合并到下一层需要多少步操作if(x >= need)// 将当前层与下一层合并{x -= need;merge1(nw --);}else// 当前层不能和下一层合并{int cnt = x / sz[nw];rst[nw]-= cnt;unop = x % sz[nw];x =0;}}}}if(unop == sz[nw]){if(nw ==1|| rst[nw -1]+1!= rst[nw]){unop =0;rst[nw]--;}else{rt[nw -1]=merge(rt[nw -1], rt[nw]);unop =0;sz[nw -1]+= sz[nw]; pfx[nw -1]+= sz[nw];sz[nw]=0;nw --;}}}elseif(c =='A'){int yu = sz[nw]- unop;// 当前层剩下的if(yu >= x) cout << rst[nw]* k + mod[kth(rt[nw],1, mod.size()-1, sz[nw]- x - unop +1)]-1<<'\n';else{int id =lower_bound(pfx.begin(), pfx.end(), n - x +1)- pfx.begin();if(id >= nw -1)// 答案在当前层的下一层{if(nw !=1&& rst[nw]== rst[nw -1]+1){int a =0;split(rt[nw], a, sz[nw]- unop);rt[nw -1]=merge(rt[nw -1], a);sz[nw -1]+= unop; pfx[nw -1]+= unop;sz[nw]-= unop;x -= sz[nw];unop =0;cout << rst[nw -1]* k + mod[kth(rt[nw -1],1, mod.size()-1, sz[nw -1]- x +1)]-1<<'\n';}else{if(id == nw)// 说明答案在unop里{x -= sz[nw]- unop;cout <<(rst[nw]-1)* k + mod[kth(rt[nw],1, mod.size()-1, sz[nw]- x +1)]-1<<'\n';}elseif(id == nw -1)// 答案在nw-1段里{x -= sz[nw];cout << rst[nw -1]* k + mod[kth(rt[nw -1],1, mod.size()-1, sz[nw -1]- x +1)]-1<<'\n';}}}else{x = n - x +1- pfx[id -1];cout << rst[id]* k + mod[kth(rt[id],1, mod.size()-1, x)]-1<<'\n';}}}}}signedmain(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t =1;// cin >> t;while(t --){solve();}return0;}
Problem J. 维克多词典(状压+记忆化)
只记录有效状态,对有效状态进行转移
什么叫有效状态呢:第一,一定要合法;第二,不能再往里加任何一个元素
#include<bits/stdc++.h>usingnamespace std;#defineintlonglongconstint INF =0x3f3f3f3f3f3f3f3f;voidsolve(){int n, w; cin >> n >> w;vector<int>cnt(14);for(int i =1; i <= n; i ++){int x; cin >> x;cnt[x]++;}set<int> st, tmp;auto check1 =[&](int x,int y)// 状态x变为y是否为合法集合{int need =0;for(int i =0; i <13; i ++){if(((x >> i)&1)==1&&((y >> i)&1)==0)returnfalse;elseif(((x >> i)&1)==0&&((y >> i)&1)==1){need += cnt[i +1];if(need > w)returnfalse;}}returntrue;};auto check2 =[&](int x,int y)// 状态x变为y是否为最大有效集合{int yu = w, minn = INF;for(int i =0; i <13; i ++){int xx =((x >> i)&1), yy =((y >> i)&1);if(xx ==1&& yy ==1)continue;elseif(xx ==0&& yy ==0) minn =min(minn, cnt[i +1]);elseif(xx ==0&& yy ==1) yu -= cnt[i +1];}if(yu >= minn)returnfalse;elsereturntrue;};int ans =1;for(int i =0; i <(1ll<<13); i ++){if(!check1(0, i))continue;if(!check2(0, i))continue;if(i ==((1ll<<13)-1)){cout << ans <<'\n';return;}st.insert(i);}while(1){ans ++;tmp.clear();for(auto t : st){for(int i =0; i <(1ll<<13); i ++){if(!check1(t, i))continue;if(!check2(t, i))continue;tmp.insert(i);}}st.clear();for(auto t : tmp){if(t ==((1ll<<13)-1)){cout << ans <<'\n';return;}st.insert(t);}}}signedmain(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t =1;while(t--){solve();}return0;}
Problem M. 生成树计数(树形dp)
思路参考官方题解
#include<bits/stdc++.h>usingnamespace std;#defineintlonglongconstint mod =998244353;voidsolve(){int n; cin >> n;vector<vector<int>>g(n +1);for(int i =1; i < n; i ++){int u, v; cin >> u >> v;g[u].push_back(v), g[v].push_back(u);}vector<bool>p(n +1),vis(n +1);vector<int>dp1(n +1),dp2(n +1);function<void(int,int)> dfs =[&](int u,int fa){if(!p[u]){dp1[u]=1, dp2[u]=0;return;}dp1[u]=0, dp2[u]=1, vis[u]=true;for(int i =0; i < g[u].size(); i ++){int j = g[u][i];if(j == fa)continue;dfs(j, u);dp1[u]=(dp1[u]* dp2[j]% mod + dp2[u]* dp1[j]% mod +2* dp1[u]* dp1[j]% mod)% mod;dp2[u]=(dp2[u]* dp2[j]% mod +2* dp2[u]* dp1[j]% mod)% mod;}};for(int i =1; i < n; i ++){int x; cin >> x;p[x]=true;vis.assign(vis.size(),false);int ans =1;for(int j =1; j <= n; j ++){if(p[j]&&!vis[j]){dfs(j,0);ans = ans * dp1[j]% mod;}}cout << ans <<'\n';}}signedmain(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t =1;// cin >> t;while(t --){solve();}return0;}