T2 实在吃不下去了，打一半跑去吃隔壁 TB 了。
T1 研讨室购物
题意
给长为 \(n\) 的正整数序列 \(a\) 和正整数 \(m\)。你可以构造一个长为 \(n\) 的非负整数序列 \(b\)，满足 \(\sum b=m\)，最小化 \(\sum_{i=1}^{n} \lfloor\dfrac{a_i}{2^{b_i}}\rfloor\)。
赛时
两分钟读题，一分钟理解题意，两分钟想到解法。
我不信这是 MX-S 会有的难度。
题解
显然可以转化成每次操作 \(a_i\gets \lfloor\dfrac{a_i}{2}\rfloor\)。
又很显然这个能贪。所以就做完了。
为啥这个 \(m\) 这么小。要是我来出这题我多少得给这个 \(m\) 卡到 \(10^7\) 然后强制让你线性做。
时间复杂度 \(O(n\log n+m\log n)\)。
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
using namespace std;int n,m;
int a[100010];priority_queue<int> q;int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);freopen("shopping.in","r",stdin);freopen("shopping.out","w",stdout);cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) q.push(a[i]);while(m--){int w=q.top();q.pop();q.push(w>>1);}long long sum=0;while(!q.empty()){sum+=q.top();q.pop();}cout<<sum;return 0;
}
T2 研讨室分配
题意
平面直角坐标系上有 \(n\) 个点，坐标为 \((x_i,y_i)\)，所有点组成一个集合 \(S\)。
对于集合 \(S\) 的非空子集 \(M\)，定义 \(f(M)\) 为将 \(M\) 中的点全部覆盖在内的最小矩形中包含的点数。包括边界。
求 \(\sum_{M\subseteq S}f(M)\)。
赛时
哈哈！天使玩偶！
写了个八常大数东西，结果造出来个容斥套容斥的啥比式子。然后被击败了。
题解
拆贡献。
显然每个点的基本贡献为 \(2^{n-1}\)。
对于每个点，考虑其左上角和右下角方向各选一个点，其余任意选，累计方案数。
考虑右上角和左下角方向各选一个点，其余任意选，累计方案数。
但是会算重。就再减去四个方向都选的情况就行了。
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
using namespace std;const long long mod=998244353;
long long qpow(long long x,long long a){long long res=1;while(a){if(a&1) res=res*x%mod;x=x*x%mod;a>>=1;}return res;
}template<typename T> class BinaryIndexTree{private:int len;vector<T> v;static int lowbit(int x){return (x&(-x));}public:BinaryIndexTree(int _len=0):len(_len),v(_len+1){}void reset(int _len=0){len=_len;v.clear();v.resize(_len+1);}void add(int x,T val){while(x<=len) v[x-1]+=val,x+=lowbit(x);}T query(int x){T res=T();while(x) res+=v[x-1],x-=lowbit(x);return res;}T query(int l,int r){return query(r)-query(l-1);}
};
BinaryIndexTree<int> bit;int n;
struct node{int x,y;bool operator<(const node&_Q)const{return _Q.x<x;}
}a[200010];vector<int> vec;
map<int,int> mp;int unq;int w1[200010],w2[200010],w3[200010],w4[200010];int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);freopen("assign.in","r",stdin);freopen("assign.out","w",stdout);cin>>n;for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;for(int i=1;i<=n;i++) vec.push_back(a[i].y);sort(vec.begin(),vec.end());mp[vec[0]]=++unq;for(int i=1;i<vec.size();i++) if(vec[i]!=vec[i-1]) mp[vec[i]]=++unq;for(int i=1;i<=n;i++) a[i].y=mp[a[i].y];sort(a+1,a+1+n);bit.reset(unq);for(int i=1;i<=n;i++){w3[i]=bit.query(a[i].y-1);w1[i]=i-1-w3[i];bit.add(a[i].y,1);}bit.reset(unq);for(int i=n;i>=1;i--){w4[i]=bit.query(a[i].y-1);w2[i]=n-i-w4[i];bit.add(a[i].y,1);}int ans=0;for(int i=1;i<=n;i++){ans=(ans+(qpow(2,w1[i])-1)*(qpow(2,w4[i])-1)%mod*(qpow(2,w2[i]))%mod*(qpow(2,w3[i]))%mod)%mod;ans=(ans+(qpow(2,w2[i])-1)*(qpow(2,w3[i])-1)%mod*(qpow(2,w1[i]))%mod*(qpow(2,w4[i]))%mod)%mod;ans=(ans-(qpow(2,w1[i])-1)*(qpow(2,w4[i])-1)%mod*(qpow(2,w2[i])-1)%mod*(qpow(2,w3[i])-1)%mod+mod)%mod;ans=(ans+qpow(2,n-1))%mod;}cout<<ans;return 0;
}
T3 研讨室验证
题意
给只含 A 和 B 的串串 \(s\) 和 \(t\)。
任意操作，每次操作如下：
- 选择一个
A变为BB。 - 选择一个
B变为AA。 - 删除一个
AAA或BBB的子串。
每次询问 \(s[l_1:r_1]\) 能否变为 \(t[l_2:r_2]\)。
题解
考虑以下变换过程：
A\(\to\)BB\(\to\)AAAA\(\to\)A。
所以一个 A 可以顶上两个 B。
把 \(s[l_1:r_1]\) 和 \(t[l_2:r_2]\) 都变成全是 A 的串，又因为三个 A 可以合成一个棍母，所以可以把数量对 \(3\) 取模。
#include<bits/stdc++.h>#define inf 0x3f3f3f3f#define infll 0x3f3f3f3f3f3f3f3fllusing namespace std;int n,m,q;int a[100010],b[100010];int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);freopen("check.in","r",stdin);freopen("check.out","w",stdout);string s;cin>>s;n=s.length(),s=' '+s;string t;cin>>t;m=t.length(),t=' '+t;for(int i=1;i<=n;i++) a[i]=a[i-1]+s[i]-'A'+1;for(int i=1;i<=m;i++) b[i]=b[i-1]+t[i]-'A'+1;cin>>q;while(q--){int l1,r1,l2,r2;cin>>l1>>r1>>l2>>r2;int w1=(a[r1]-a[l1-1])%3;int w2=(b[r2]-b[l2-1])%3;if(w1==w2) cout<<"YES\n";else cout<<"NO\n";}return 0;}
总结
这场没认真打，半个小时摸完 T1 就跑了。
事实证明 T3 < T2。