Preface
去年的 hangzhou Regional,前中期对着 M 题爆写 2h 终于堪堪通过(好像说现场这题数据水了导致过了一车)
后面开始疯狂补手上会做但没写的题,最后 B 题赛后 1min 发现读入没开 long long
,6 题大罚时倒闭
(平时训练 DS 一般都是我负责写的,但当时安排是让我去想 J,所以 DS 就扔给徐神了)
A. AUS
队友开场写的,我题都没看
#include <bits/stdc++.h>bool work() {std::string s1, s2, s3;std::cin >> s1 >> s2 >> s3;int n = s1.size();if(n != s2.size()) return false;if(n != s3.size()) return true;int fa[26];for(int i = 0; i < 26; ++i) fa[i] = i;auto father = [&](int i) {i -= 'a';static std::stack<int> stack;while(fa[i] != i) stack.push(i), i = fa[i];int res = i;while(stack.size()) fa[stack.top()] = res, stack.pop();return res;};auto unon = [&](int a, int b) {a = father(a), b = father(b);if(a == b) return;fa[b] = a;};for(int i = 0; i < n; ++i) unon(s1[i], s2[i]);for(int i = 0; i < n; ++i) if(father(s1[i]) != father(s3[i])) return true;return false;
}int main() {std::ios::sync_with_stdio(false);int T; std::cin >> T; while(T--) std::cout << (work() ? "YES\n" : "NO\n");return 0;
}
B. Barkley III
位运算一眼按位贪心,从高到低考虑二进制下每一位
如果区间内这一位上是 \(0\) 的数大于等于 \(2\) 个,则无论怎么操作这一位都是 \(0\);否则若这一位上是 \(0\) 的数为 \(0\),则无论怎么操作这一位都是 \(1\)
忽略以上两种情况后,遇到的第一个这一位上是 \(0\) 的数为 \(1\) 的情形时,删去那个数显然可以最大化答案
朴素的做法是开 \(\log a_i\) 棵线段树维护,但这题的数据范围一眼卡双 \(\log\),因此需要把每一位的信息压到一个 64 位数里
#include <bits/stdc++.h>using llui = long long unsigned int;
constexpr int $n = 1000006;namespace SMT {constexpr int $node = 4 * $n;llui ars[$node], hkr[$node], tag[$node];std::bitset<$node> isLeaf;void pushdown(int cur) {// if(isLeaf[cur]) return;int lc = cur << 1, rc = lc | 1;for(auto ch: (int[2]){lc, rc}) {ars[ch] &= tag[cur]; tag[ch] &= tag[cur];if(isLeaf[ch]) hkr[ch] = 0;else hkr[ch] |= ~tag[cur];}tag[cur] = ~0ull;}void pushup(int cur) {// if(isLeaf[cur]) return;int lc = cur << 1, rc = lc | 1;ars[cur] = ~0ull, hkr[cur] = 0;for(auto ch: (int[2]){lc, rc}) {ars[cur] &= ars[ch];hkr[cur] |= hkr[ch];}hkr[cur] |= ~ars[lc] & ~ars[rc];}void init(int p, int l, int r, llui *a) {tag[p] = ~0ull;if(l == r) {isLeaf[p] = true;ars[p] = a[l]; hkr[p] = 0;return ;}int mid = (l + r) >> 1;int lc = p << 1, rc = lc | 1;init(lc, l, mid, a);init(rc, mid + 1, r, a);pushup(p);}void assign(int p, int l, int r, int pos, llui val) {if(l == r) {ars[p] = val; hkr[p] = 0;return ;}pushdown(p);int mid = (l + r) >> 1;int lc = p << 1, rc = lc | 1;if(pos > mid) assign(rc, mid + 1, r, pos, val);else assign(lc, l, mid, pos, val);pushup(p);}void band(int p, int l, int r, int L, int R, llui val) {if(L > r || l > R) return ;if(L <= l && r <= R) {ars[p] &= val; tag[p] &= val;if(isLeaf[p]) hkr[p] = 0;else hkr[p] |= ~val;// std::cerr << "ars[p] = " << ars[p] << ", hkr[p] = " << hkr[p] << char(10);return ;}pushdown(p);int mid = (l + r) >> 1;int lc = p << 1, rc = lc | 1;band(lc, l, mid, L, R, val);band(rc, mid + 1, r, L, R, val);pushup(p);}void query(int p, int l, int r, int L, int R, std::vector<int> &vec) {if(L > r || l > R) return ;if(L <= l && r <= R) {vec.push_back(p);return ;}pushdown(p);int mid = (l + r) >> 1;int lc = p << 1, rc = lc | 1;query(lc, l, mid, L, R, vec);query(rc, mid + 1, r, L, R, vec);}llui ignore(int p, llui topz) {if(isLeaf[p]) return ~0ull;pushdown(p);int lc = p << 1, rc = lc | 1;if(~ars[lc] & topz) return ignore(lc, topz) & ars[rc];else return ignore(rc, topz) & ars[lc];}
}int n, q;
llui a[$n];llui solve(int l, int r) {using namespace SMT;std::vector<int> vec;query(1, 1, n, l, r, vec);llui Ars = ~0ull, Hkr = 0;for(auto p: vec) {Hkr |= hkr[p];Hkr |= ~Ars & ~ars[p];Ars &= ars[p];}llui topz;if(~Hkr & ~Ars) topz = 1ull << (63 - __builtin_clzll(~Hkr & ~Ars));else return Ars;llui ans = ~0ull;for(auto p: vec) {if(~ars[p] & topz) ans &= ignore(p, topz);else ans &= ars[p];}return ans;
}void work() {std::cin >> n >> q;for(int i = 1; i <= n; i++) std::cin >> a[i];SMT::init(1, 1, n, a);while(q--) {int type, l, r, s;llui x; std::cin >> type;switch(type) {case 1:std::cin >> l >> r >> x;SMT::band(1, 1, n, l, r, x);break;case 2:std::cin >> s >> x;SMT::assign(1, 1, n, s, x);break;case 3:std::cin >> l >> r;std::cout << solve(l, r) << char(10);break;}}return ;
}int main() {std::ios::sync_with_stdio(false);int T = 1; while(T--) work();return 0;
}
E. Elevator II
注意到如果我们把电梯移动到了 \(r_i\) 最大的位置,则剩下的要求都可以不消耗额外代价地完成,只需要按照 \(r_i\) 从大到小处理即可
因此问题转化为怎样用最小额外代价把电梯移动到最上面,考虑以下贪心
维护电梯当前所在楼层 \(cur\),每次找到满足 \(l_i\le cur\) 的需求中 \(r_i\) 最大的那个
若存在 \(r_i>cur\) 则直接用其更新 \(cur\);否则找一个最小的 \(l_i\),花费 \(cur-l_i\) 的代价移动过去
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<array>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,f,l[N],r[N]; array <int,3> a[N];
int main()
{for (scanf("%d",&t);t;--t){scanf("%d%d",&n,&f);long long sum=0;for (RI i=1;i<=n;++i){scanf("%d%d",&l[i],&r[i]);a[i][0]=l[i]; a[i][1]=r[i];sum+=r[i]-l[i]; a[i][2]=i;}sort(a+1,a+n+1); int p=1;vector <int> ans;while (p<=n){int nf=f,id=-1;while (p<=n&&a[p][0]<=f){if (a[p][1]>nf) nf=a[p][1],id=a[p][2];++p;}// printf("p = %d, id = %d, nf = %d\n",p,id,nf);if (id==-1){if (p<=n){sum+=a[p][0]-f;f=a[p][1];ans.push_back(a[p++][2]);}} else{f=nf;ans.push_back(id);}}printf("%lld\n",sum);static int vis[N];for (RI i=1;i<=n;++i) vis[i]=0;for (auto x:ans) vis[x]=1;vector <array <int,3>> left;for (RI i=1;i<=n;++i)if (!vis[i]) left.push_back({l[i],r[i],i});auto cmp=[&](const array <int,3>& A,const array <int,3>& B){return A[1]>B[1];};sort(left.begin(),left.end(),cmp);for (auto [l,r,id]:left) ans.push_back(id);for (auto x:ans) printf("%d ",x); putchar('\n');}return 0;
}
F. Fuzzy Ranking
把偏序关系看作一个 DAG,建图强连通分量缩点后,显然每个询问的区间对应着图上的一条链
不难发现统计答案就是找到区间内在同一个强连通分量里的点数量,直接预处理简单维护即可
#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,k,q; vector <int> a[N],v[N],pre[N],suf[N]; vector <long long> pfx[N];
int dfn[N],low[N],stk[N],top,idx,vis[N],bel[N],sz[N],scc;
inline void Tarjan(CI now)
{dfn[now]=low[now]=++idx;stk[++top]=now; vis[now]=1;for (auto to:v[now])if (!dfn[to]) Tarjan(to),low[now]=min(low[now],low[to]);else if (vis[to]) low[now]=min(low[now],dfn[to]);if (low[now]==dfn[now]){++scc;do{++sz[scc];bel[stk[top]]=scc;vis[stk[top]]=0;} while (stk[top--]!=now);}
}
int main()
{for (scanf("%d",&t);t;--t){scanf("%d%d%d",&n,&k,&q);for (RI i=1;i<=n;++i) dfn[i]=sz[i]=0,v[i].clear();for (RI i=1;i<=k;++i){a[i].resize(n+1);for (RI j=1;j<=n;++j){scanf("%d",&a[i][j]);if (j-1>=1) v[a[i][j-1]].push_back(a[i][j]);}}idx=scc=0;for (RI i=1;i<=n;++i)if (!dfn[i]) Tarjan(i);auto C2=[&](CI x){return 1LL*x*(x-1)/2LL;};for (RI i=1;i<=k;++i){pre[i].resize(n+1);suf[i].resize(n+1);pfx[i].resize(n+1);for (RI j=0;j<=n;++j) pre[i][j]=suf[i][j]=pfx[i][j]=0;int lst=0;for (RI j=1;j<=n;++j) a[i][j]=bel[a[i][j]];// for (RI j=1;j<=n;++j) printf("%d%c",a[i][j]," \n"[j==n]);for (RI j=1;j<=n;++j){if (j==n||a[i][j]!=a[i][j+1]){pfx[i][j]=pfx[i][lst]+C2(j-lst);lst=j; pre[i][j]=suf[i][j]=j;}}for (RI j=1;j<=n;++j)if (pre[i][j]==0) pre[i][j]=pre[i][j-1];for (RI j=n;j>=1;--j)if (suf[i][j]==0) suf[i][j]=suf[i][j+1];}long long ans=0;while (q--){int id,l,r; scanf("%d%d%d",&id,&l,&r);id=(id+ans)%k+1; l=(l+ans)%n+1; r=(r+ans)%n+1;// printf("id = %d, l = %d, r = %d\n",id,l,r);if (a[id][l]==a[id][r]){printf("%lld\n",ans=C2(r-l+1));continue;}int ql=suf[id][l],qr=pre[id][r];// printf("ql = %d, qr = %d\n",ql,qr);long long sum=C2(ql-l+1)+C2(r-qr);if (qr>ql) sum+=pfx[id][qr]-pfx[id][ql];printf("%lld\n",sum); ans=sum;}}return 0;
}
H. Heavy-light Decomposition
首先不难发现答案只和每条链的长度有关
若长度里最大值唯一,则以该链的某个端点为根,剩下的链全部挂在根下面即为合法解
否则考虑找一个长度最短的链挂在最长链某端的第二个节点上,剩下的链再挂在根下面
以上做法需要满足最短链长度小于等于最长链长度减 \(2\),不难发现这是有解的充要条件
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<array>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,k,fa[N];
int main()
{for (scanf("%d",&t);t;--t){scanf("%d%d",&n,&k);vector <array <int,3>> vec;for (RI i=1;i<=k;++i){int l,r; scanf("%d%d",&l,&r);vec.push_back({r-l,l,r});}if (k==1){for (RI i=vec[0][1];i<=vec[0][2];++i) printf("%d%c",i-1," \n"[i==vec[0][2]]);continue;}sort(vec.begin(),vec.end(),greater <array <int,3>>());int rt=vec[0][1];for (RI i=vec[0][1]+1;i<=vec[0][2];++i) fa[i]=i-1;fa[rt]=0;if (vec[1][0]==vec[0][0]){if (vec.back()[0]>vec[0][0]-2){puts("IMPOSSIBLE");continue;}int heavy_son=rt+1;fa[vec.back()[1]]=heavy_son;for (RI i=vec.back()[1]+1;i<=vec.back()[2];++i) fa[i]=i-1;for (RI j=1;j<(int)vec.size()-1;++j){fa[vec[j][1]]=rt;for (RI i=vec[j][1]+1;i<=vec[j][2];++i) fa[i]=i-1;}} else{for (RI j=1;j<(int)vec.size();++j){fa[vec[j][1]]=rt;for (RI i=vec[j][1]+1;i<=vec[j][2];++i) fa[i]=i-1;}}for (RI i=1;i<=n;++i) printf("%d%c",fa[i]," \n"[i==n]);}return 0;
}
J. Japanese Bands
感觉思路什么的都全对,但少了一步性质的分析,可惜
考虑枚举确定两边选取的集合 \(mask_1,mask_2\),则贡献为 \(\binom{n_1-1}{|mask_1|-1}\times \binom{n_2-1}{|mask_2|-1}\),现在考虑怎样的 \(mask_1,mask_2\) 是符合要求的
一个显著的观察是对于任意 \(\{a_i,b_i\}\),\(mask_1\cap\{a_i,b_i\}\ne \emptyset\and mask_2\cap\{a_i,b_i\}\ne \emptyset\),否则这条限制一定无法满足
但直接这么判会漏掉一种 Case,例如 \(mask_1,mask_2\) 中都仅包含了 \(a_i\) 而不包含 \(b_i\)
不难发现可以加一条 \(mask_1\cup mask_2=\bigcup \{a_i,b_i\}\) 来 fix 这种情况,现在考虑如何计数
考虑枚举确定 \(mask_2\) 时,根据最后一条 rule,合法的 \(mask_1\) 一定是某个状态的超集,用 sosdp 处理之即可
总复杂度 \(O(m2^m)\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int M=20,mod=1e9+7;
int t,n1,n2,m,k,ifac[M+5],f[1<<M],g[1<<M],cnt[1<<M];
inline int quick_pow(int x,int p=mod-2,int mul=1)
{for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(void)
{for (RI i=0;i<=20;++i) ifac[i]=quick_pow(i);for (RI i=0;i<(1<<20);++i) cnt[i]=cnt[i>>1]+(i&1);
}
inline int C(CI n,CI m) //m<=20
{if (n<0||m<0||n<m) return 0;int res=1;for (RI i=1;i<=m;++i) res=1LL*res*(n-i+1)%mod*ifac[i]%mod;return res;
}
int main()
{for (init(),scanf("%d",&t);t;--t){scanf("%d%d%d%d",&n1,&n2,&m,&k);for (RI i=0;i<(1<<m);++i) f[i]=g[i]=0;int all=0;for (RI i=1;i<=k;++i){int x,y; scanf("%d%d",&x,&y);--x; --y; all|=(1<<x)|(1<<y);g[(1<<x)|(1<<y)]=1;}for (RI i=0;i<m;++i)for (RI mask=0;mask<(1<<m);++mask)if (((mask>>i)&1)==1) g[mask]|=g[mask^(1<<i)];for (RI mask=0;mask<(1<<m);++mask)if (!g[mask^((1<<m)-1)]) f[mask]=C(n1-1,cnt[mask]-1);for (RI i=0;i<m;++i)for (RI mask=0;mask<(1<<m);++mask)if (((mask>>i)&1)==0) (f[mask]+=f[mask^(1<<i)])%=mod;int ans=0;for (RI mask=0;mask<(1<<m);++mask)if (!g[mask^((1<<m)-1)])(ans+=1LL*C(n2-1,cnt[mask]-1)*f[all^(all&mask)]%mod)%=mod;printf("%d\n",ans);}return 0;
}
K. Kind of Bingo
签到,枚举最后先填完的是哪一行,贪心地每次把最大的元素换出去即可,总复杂度 \(O(nm)\)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,m,k; vector <int> pos[N];
int main()
{for (scanf("%d",&t);t;--t){scanf("%d%d%d",&n,&m,&k);for (RI i=1;i<=n;++i) pos[i].clear();for (RI i=1;i<=n*m;++i){int x; scanf("%d",&x);pos[(x-1)/m+1].push_back(i);}int ans=1e9;for (RI i=1;i<=n;++i){sort(pos[i].begin(),pos[i].end(),greater <int>());// for (auto x:pos[i]) printf("%d ",x); putchar('\n');static int vis[N]; int mex=1;for (auto x:pos[i]) vis[x]=1;for (RI j=0;j<min(k,m);++j){while (vis[mex]) ++mex;if (pos[i][j]<mex) break;vis[mex]=1; vis[pos[i][j]]=0;pos[i][j]=mex;}// for (auto x:pos[i]) printf("%d ",x); putchar('\n');ans=min(ans,*max_element(pos[i].begin(),pos[i].end()));for (RI j=1;j<=mex;++j) vis[j]=0;for (auto x:pos[i]) vis[x]=0;}printf("%d\n",ans);}return 0;
}
M. Make It Divisible
感觉我们队做法复杂了,很难想象一个铜牌题要写笛卡尔树+Pollard_Rho,但你就说过没过吧
#include<bits/stdc++.h>
#define LL long long
using namespace std;const int N = 5e4+5;
int n, k, b[N], fa[N], id[N];
LL ans;struct Node {int l, r, f;bool operator<(const Node &a) const {return r < a.l;}
};
vector <int> vec2;
set<Node> st;
bool all = true;// vector<int> pro(int x) {
// // printf("x=%d\n", x);
// vector<int> vec;
// for (int i=1; i*i<=x; ++i) {
// if (x%i == 0) {
// vec.push_back(i);
// if (x/i != i) vec.push_back(x/i);
// }
// }
// sort(vec.begin(),vec.end());
// return vec;
// }#define RI register int
#define CI const int&
namespace Pollard_Rho
{inline int sum(CI x,CI y,CI mod){return x+y>=mod?x+y-mod:x+y;}inline int sub(CI x,CI y,CI mod){return x-y<0?x-y+mod:x-y;}inline int quick_pow(int x,int p,int mod,int mul=1){for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;}inline bool Miller_Robin(CI n){if (n<=1) return 0;vector <int> base={2,3,5,7,11,13,17,19,23};for (auto x:base){if (n==x) return 1;if (n%x==0) return 0;}int m=(n-1)>>__builtin_ctz(n-1);for (auto x:base){int t=m,a=quick_pow(x,m,n);while (t!=n-1&&a!=1&&a!=n-1) a=1LL*a*a%n,t*=2;if (a!=n-1&&t%2==0) return 0;}return 1;}inline int get_frac(CI n){if (n%2==0) return 2;auto f=[&](CI x){return sum(1LL*x*x%n,1,n);};int x=0,y=0,tot=0,p=1,q,g;for (int i=0;(i&0xff)||(g=__gcd(p,n))==1;++i,x=f(x),y=f(f(y))){if (x==y) x=tot++,y=f(x);q=1LL*p*sub(x,y,n)%n;if (q) p=q;}return g;}inline vector <int> solve(CI n){if (n==1) return {};if (Miller_Robin(n)) return {n};int d=get_frac(n);auto v1=solve(d),v2=solve(n/d);auto i1=v1.begin(),i2=v2.begin();vector <int> ans;while (i1!=v1.end()||i2!=v2.end()){if (i1==v1.end()) ans.push_back(*i2++);else if (i2==v2.end()) ans.push_back(*i1++);else ans.push_back(*i1<*i2?*i1++:*i2++);}return ans;}
}inline void DFS(CI now,int mul,vector <pair <int,int>>& num,vector <int>& res)
{if (now>=(int)num.size()){res.push_back(mul);return;}DFS(now+1,mul,num,res);for (RI i=1;i<=num[now].second;++i)mul*=num[now].first,DFS(now+1,mul,num,res);
}void calc(int a, int b) {// printf("a=%d b=%d\n", a, b);vector<int> res = Pollard_Rho::solve(b-a);vector<pair <int,int>> num;int lst=-1,cnt=1;for (auto x:res){if (x!=lst){if (lst!=-1) num.push_back({lst,cnt});cnt=1;} else ++cnt;lst=x;}num.push_back({lst,cnt});vector <int> frac;DFS(0,1,num,frac);sort(frac.begin(),frac.end());// vector<int> vec = pro(b-a);// printf("vec:"); for (int x : vec) printf("%d ", x); puts("");vector <int> vec1;for (int x : frac) if (x > a && x-a <= k) vec1.push_back(x-a);// printf("st1:"); for (int x : st1) printf("%d ", x); puts("");// printf("11111\n");if (all) {swap(vec2, vec1);} else {vector <int> tmp;if (vec2.size() > vec1.size()) swap(vec2, vec2);int p=0;for (auto x : vec2) {while (p<(int)vec1.size()&&vec1[p]<x) ++p;if (p<(int)vec1.size()&&vec1[p]==x) tmp.push_back(x);}swap(tmp, vec2);}all = false;// printf("st2:"); for (int x : st2) printf("%d ", x); puts("");
}void solve() {cin >> n >> k;for (int i=1; i<=n; ++i) cin >> b[i], id[i]=i;sort(id+1, id+n+1, [&](int aa, int bb){return b[aa]<b[bb];});st.clear();st.insert(Node{1, n, -1});for (int i=1; i<=n; ++i) {int x = id[i];auto it = st.find(Node{x, x, -1});auto [l, r, f] = *it;st.erase(it);fa[x] = f;if (x > l) st.insert(Node{l, x-1, x});if (x < r) st.insert(Node{x+1, r, x});}vec2.clear();all=true;for (int i=1; i<=n; ++i) if (fa[i]!=-1) {// printf("i=%d\n", i);if (b[fa[i]] == b[i]) continue;calc(b[fa[i]], b[i]);}ans = 0;if (all) {ans = 1LL*(k+1)*k/2;cout << k << ' ' << ans << '\n';} else {for (auto x : vec2) ans += x;cout << vec2.size() << ' ' << ans << '\n';}
}signed main() {ios::sync_with_stdio(0); cin.tie(0);// vector<int> res = Pollard_Rho::solve(24);// vector<pair <int,int>> num;// int lst=-1,cnt=1;// for (auto x:res)// {// if (x!=lst)// {// if (lst!=-1) num.push_back({lst,cnt});// cnt=1;// } else ++cnt;// lst=x;// }// num.push_back({lst,cnt});// vector <int> frac;// DFS(0,1,num,frac);// sort(frac.begin(),frac.end());// for (auto x:frac) printf("%d ",x); putchar('\n');int T; cin >> T; while (T--) solve();return 0;
}
Postscript
如果这场正常点打估计能场上勉强过个 B 苟个 7 题尾?
这么看来确实印证了去年选站的大失败,除了沈阳和昆明感觉剩下的站都能 Au 啊,今年能弥补下遗憾吗