Solved: 5/10
Rank: 1565
-90 又 -90，好不容易上点分两场全掉没了……
A. Tender Carpenter
题意：\(n\) 个数，问能否有多于一种划分方案，使得划分出的每组数中任选三个数（可以相同）都能构成三角形。
显然全划分成一个是合法的；那么只需考虑任意的相邻两个数能否分成一组即可。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define all(x) (x).begin(),(x).end()
bool solve(){
int n;
cin>>n;
vector<int> a(n);
for(int& x:a)cin>>x;
for(int i=0;i<n-1;++i){
if(a[i]<a[i+1]*2&&a[i+1]<a[i]*2)return 1;
}
return 0;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int T;
cin>>T;
while(T--)cout<<(solve()?"YES":"NO")<<'\n';
}
B. Outstanding Impressionist
题意：\(n\) 个区间，对每个 \(i\)，问是否存在一种方案，在所有区间中各取一个数，使得其他区间中取的数都于第 \(i\) 个区间取的数不同。
显然只有长度为 \(1\) 的区间会对答案产生影响，只需判断区间是否被长度为 \(1\) 的区间覆盖。对这类区间做一个前缀和。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
#define all(x) (x).begin(),(x).end()
bool solve(){
int n;
cin>>n;
vector<int> l(n),r(n);
vector<int> c(2*n+1);
vector<int> sc(2*n+1);
for(int i=0;i<n;++i){
cin>>l[i]>>r[i];
if(l[i]==r[i])++c[l[i]];
}
for(int i=1;i<=2*n;++i){
sc[i]=c[i]>0;
sc[i]+=sc[i-1];
}
for(int i=0;i<n;++i){
if(l[i]==r[i]){
if(c[l[i]]>1)cout<<0;
else cout<<1;
}
else{
int sum=sc[r[i]]-sc[l[i]-1];
if(sum<r[i]-l[i]+1)cout<<1;
else cout<<0;
}
}
cout<<'\n';
return 0;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int T;
cin>>T;
while(T--)solve();
}
C. Bewitching Stargazer
题意：初始有一个区间 \([1,n]\)，递归对区间进行如下操作：若长度 \(<k\) 则忽略；若长度为偶数，则拆分为两个长度相等的子区间\([l,mid]\)和\([mid+1,r]\)；若长度为奇数，则拆分为\([l,mid-1]\)和\([mid+1,r]\)并将\(mid\)的值加入答案。求最终答案。
右半区间的答案等于左半区间答案加左半区间数量乘一个常数，因此直接递归计算即可。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
#define all(x) (x).begin(),(x).end()
pll dfs(ll n,ll k){
if(n<k)return {0,0};
ll m=n+1>>1;
pll t;
if(n&1){
t=dfs(m-1,k);
return {2*t.first+m+t.second*m,t.second*2+1};
}
t=dfs(m,k);
return {2*t.first+t.second*m,t.second*2};
}
void solve(){
ll n,k;
cin>>n>>k;
cout<<dfs(n,k).first<<'\n';
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int T;
cin>>T;
while(T--)solve();
}
D. Refined Product Optimality
题意：给两个序列 \(a\) 和 \(b\)，要求支持单点加 1 和查询两个序列从小到大排序后对应取 min 的乘积。
直接维护有序序列和每个数的排名即可。若有相等的数，则可视为相等数中排名最大的那个数加 1。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
#define all(x) (x).begin(),(x).end()
const int N=2e5+5,mod=998244353;
ll qpow(ll x,int y){
ll r=1;
for(;y;y>>=1){
if(y&1)r=r*x%mod;
x=x*x%mod;
}
return r;
}
ll inv(ll x){return qpow(x,mod-2);}
int n,q,o,x,pa[N],pb[N];
pii a[N],b[N];
map<int,int> mra,mrb;
ll ans;
void solve(){
cin>>n>>q;
for(int i=1;i<=n;++i)cin>>a[i].first,a[i].second=i;
for(int i=1;i<=n;++i)cin>>b[i].first,b[i].second=i;
sort(a+1,a+n+1);
sort(b+1,b+n+1);
mra.clear(),mrb.clear();
for(int i=1;i<=n;++i){
pa[a[i].second]=i;
pb[b[i].second]=i;
mra[a[i].first]=i;
mrb[b[i].first]=i;
}
ans=1;
for(int i=1;i<=n;++i)ans=ans*min(a[i].first,b[i].first)%mod;
cout<<ans<<' ';
while(q--){
cin>>o>>x;
ll u,v;
if(o==1){
int r=pa[x];
if(r<mra[a[r].first]){
int t=mra[a[r].first];
u=min(a[t].first,b[t].first);
++a[t].first;
v=min(a[t].first,b[t].first);
swap(a[r].second,a[t].second);
pa[a[r].second]=r;
pa[a[t].second]=t;
mra[a[r].first]=t-1;
if(!mra.count(a[t].first))mra[a[t].first]=t;
}
else{
u=min(a[r].first,b[r].first);
if(a[r-1].first==a[r].first)mra[a[r].first]=r-1;
else mra.erase(a[r].first);
++a[r].first;
v=min(a[r].first,b[r].first);
if(!mra.count(a[r].first))mra[a[r].first]=r;
}
ans=ans*inv(u)%mod*v%mod;
}
else{
int r=pb[x];
if(r<mrb[b[r].first]){
int t=mrb[b[r].first];
u=min(a[t].first,b[t].first);
++b[t].first;
v=min(a[t].first,b[t].first);
swap(b[r].second,b[t].second);
pb[b[r].second]=r;
pb[b[t].second]=t;
mrb[b[r].first]=t-1;
if(!mrb.count(b[t].first))mrb[b[t].first]=t;
}
else{
u=min(a[r].first,b[r].first);
if(b[r-1].first==b[r].first)mrb[b[r].first]=r-1;
else mrb.erase(b[r].first);
++b[r].first;
v=min(a[r].first,b[r].first);
if(!mrb.count(b[r].first))mrb[b[r].first]=r;
}
ans=ans*inv(u)%mod*v%mod;
}
cout<<ans<<' ';
}
cout<<'\n';
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int T;
cin>>T;
while(T--)solve();
}
E. Resourceful Caterpillar Sequence
题意：给一棵树，两人轮流操作。初始有一条路径 \((p,q)\)，先手操作时可将路径向 \(p\) 的方向移动一条边，后手操作时可将路径向 \(q\) 的方向移动一条边。\(p\) 为叶子先手胜，\(q\) 为叶子后手胜。问初始路径有多少种情况可保证后手获胜。
首先 \(q\) 是叶子后手直接就获胜了。若 \(q\) 不是叶子，则只可能是一轮直接获胜（否则先手可以反复撤销后手的移动，对局无法终止）。即：\(q'\) 是某叶子 \(l\) 的父亲，\(q\) 与 \(q'\) 相邻，\(p\) 与任意叶子的距离至少为 \(2\)，\(q\) 和 \(p\) 在 \(q'\) 的不同子树中。此时枚举 \(q'\) 统计答案即可。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
#define all(x) (x).begin(),(x).end()
const int N=2e5+5,mod=998244353;
int n,x,y;
vector<int> e[N];
void adde(int x,int y){
e[x].push_back(y);
}
bool vis[N];
int sz[N],sum[N],fa[N];
void dfs(int u,int f){
sz[u]=1,sum[u]=!vis[u];
for(int v:e[u])if(v^f){
fa[v]=u;
dfs(v,u);
sz[u]+=sz[v];
sum[u]+=sum[v];
}
}
vector<int> lf;
void solve(){
cin>>n;
for(int i=1;i<=n;++i)e[i].clear();
for(int i=1;i<n;++i)cin>>x>>y,adde(x,y),adde(y,x);
lf.clear();
for(int i=1;i<=n;++i)if(e[i].size()==1)lf.push_back(i);
ll ans=lf.size()*(n-lf.size());
memset(vis,0,sizeof(bool)*(n+1));
set<int> s;
for(int u:lf){
vis[u]=1;
for(int v:e[u]){
vis[v]=1;
if(e[v].size()>1)s.insert(v);
}
}
int all=0;
for(int i=1;i<=n;++i)all+=!vis[i];
dfs(1,0);
for(int u:s){
int siz,summ;
for(int v:e[u]){
if(v==fa[u])siz=n-sz[u],summ=sum[u];
else siz=sz[v],summ=all-sum[v];
if(siz>1)ans+=summ;
}
}
cout<<ans<<'\n';
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int T;
cin>>T;
while(T--)solve();
}