Sorry for misjudging the difficulty of problem D, but we still hope you enjoyed the problems!↵
↵
[problem:2119A]↵
↵
Author: [user:YuJiahe,2025-07-06]↵
↵
<spoiler summary="Hint 1">↵
$a \oplus 1$ is equivalent to $a - 1$ when $a$ is an odd number, otherwise it is equivalent to $a + 1$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
If you apply $a \gets a \oplus 1$ when $a$ is odd, then that operation should make $a = b$.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2119A]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include <algorithm>↵
#include <cstring>↵
#include <cstdio>↵
#include <vector>↵
#include <queue>↵
using namespace std;↵
int t, a, b, x, y;↵
int main(){scanf("%d", &t);↵
while (t --){scanf("%d%d%d%d", &a, &b, &x, &y);↵
if (a > b) printf("%d\n", (a ^ 1) == b ? y : -1);↵
else {int c0 = b - a, c1 = (b + 1 >> 1) - (a + 1 >> 1);↵
printf("%lld\n", y > x ? 1ll * c0 * x : 1ll * (c0 - c1) * x + 1ll * c1 * y);}↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2119B]↵
↵
Author: [user:Lyz09,2025-07-06]↵
↵
<spoiler summary="Hint 1">↵
Transform $(p_x,p_y)$ to $(q_x,q_y)$ into an operation where $a_i$ is the distance between the two points.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
When $n+1=3$, there is a solution if and only if the largest $a_i$ is less than or equal to the sum of the remaining $a_i$.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2119B]↵
</spoiler>↵
↵
<spoiler summary="Implementation 1">↵
~~~~~↵
#include<iostream>↵
#include<algorithm>↵
#include<cmath>↵
using namespace std;↵
#define N 100010↵
#define int long long↵
int t,n,sx,sy,tx,ty;↵
double a[N];↵
signed main()↵
{↵
cin>>t;↵
while(t--)↵
{↵
cin>>n;↵
cin>>sx>>sy>>tx>>ty;↵
for(int i=1;i<=n;i++)↵
cin>>a[i];↵
a[++n]=sqrt((sx-tx)*(sx-tx)+(sy-ty)*(sy-ty));↵
sort(a+1,a+n+1);↵
double sum=a[n];↵
for(int i=1;i<n;i++)↵
sum-=a[i];↵
if(sum<=0)↵
puts("Yes");↵
else↵
puts("No");↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Implementation 2">↵
~~~~~↵
#include<iostream>↵
#include<algorithm>↵
using namespace std;↵
#define N 100010↵
#define int long long↵
int t,n,sx,sy,tx,ty,a[N];↵
signed main()↵
{↵
cin>>t;↵
while(t--)↵
{↵
cin>>n;↵
cin>>sx>>sy>>tx>>ty;↵
for(int i=1;i<=n;i++)↵
cin>>a[i];↵
sort(a+1,a+n+1);↵
int p=(sx-tx)*(sx-tx)+(sy-ty)*(sy-ty);↵
if(p>a[n]*a[n])↵
{↵
int sum=0;↵
for(int i=1;i<=n;i++)↵
{↵
sum+=a[i];↵
if(sum*sum>=p)↵
break;↵
}↵
if(sum*sum>=p)↵
puts("Yes");↵
else↵
puts("No");↵
}↵
else↵
{↵
int sum=a[n];↵
for(int i=1;i<=n-1;i++)↵
sum-=a[i];↵
if(sum<=0||sum*sum<=p)↵
puts("Yes");↵
else↵
puts("No");↵
}↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2119C]↵
↵
Author: [user:lizhous,2025-07-06]↵
Preparation: [user:Lyz09,2025-07-06]↵
↵
<spoiler summary="Hint 1">↵
For odd $n$, setting $a_i = l$ for all $i$ suffices.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
For even $n$, there does not exist a valid array $a$ that satisfies $a_1=a_2=\dots=a_{n-1}=l$.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
For even $n$, try to satisfy $\oplus_{i=1}^{n}a_i=0$.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2119C]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include<iostream>↵
using namespace std;↵
#define int long long↵
int t,n,l,r,k;↵
signed main()↵
{↵
cin>>t;↵
while(t--)↵
{↵
cin>>n>>l>>r>>k;↵
if(n%2==1)↵
{↵
cout<<l<<endl;↵
continue;↵
}↵
if(n==2)↵
{↵
cout<<-1<<endl;↵
continue;↵
}↵
int res=1;↵
bool fl=0;↵
while(res<=r)↵
{↵
if(res>l)↵
{↵
fl=1;↵
if(k<=n-2)↵
cout<<l<<endl;↵
else↵
cout<<res<<endl;↵
break;↵
}↵
res*=2;↵
}↵
if(!fl)↵
cout<<-1<<endl;↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2119D]↵
↵
Author: [user:YuJiahe,2025-07-06]↵
↵
<spoiler summary="Hint 1">↵
Calculating the weight of a single valid sequence is difficult. Try another way?↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2119D]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include <algorithm>↵
#include <cstring>↵
#include <cstdio>↵
#include <vector>↵
#include <queue>↵
using namespace std;↵
const int N = 5005;↵
int t, n, mod, f[N][N], ans;↵
inline void add(int& x, int y){x += y;if (x >= mod) x -= mod;}↵
int main(){scanf("%d", &t);↵
while (t --){scanf("%d%d", &n, &mod), f[0][0] = 1, ans = 0;↵
for (int i = 1;i <= n;i ++) for (int j = 0;j <= i;j ++) f[i][j] = 0;↵
for (int i = 1;i <= n;i ++)↵
for (int j = 0, now;j < i;j ++)↵
if (now = f[i - 1][j]) add(f[i][j + 1], now),↵
f[i][j] = (f[i][j] + (n - i + 1ll) * (j + 1) * now) % mod;↵
for (int j = 0;j <= n;j ++) add(ans, f[n][j]);printf("%d\n", ans);↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2119E]↵
↵
Author: [user:ma2021tyoi0037,2025-07-06]↵
↵
<spoiler summary="Hint 1">↵
As same as the title, can you find a simple necessary constraint? ↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Consider $a_i = 0$ first.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2119E]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
typedef long long ll;↵
struct stu{↵
int x;↵
ll dp;↵
};↵
int n,a[100007],b[100007];↵
vector<stu> f,g;↵
const ll inf=0x3f3f3f3f3f3f3f3f;↵
void Subt(){↵
cin>>n;↵
for(int i=1;i<n;i++) cin>>a[i];↵
for(int i=1;i<=n;i++) cin>>b[i];↵
a[n]=0;↵
f.clear();↵
f.push_back((stu){0,0});↵
for(int i=1;i<=n;i++){↵
int x=0;↵
g.clear();↵
for(int j=30;j>=-1;j--){↵
int y=x|a[i-1]|a[i];↵
if(j!=-1) y|=(1<<j); ↵
if(y>=b[i]){↵
ll mn=inf;↵
for(stu l:f){↵
if((l.x&y)!=a[i-1]) continue;↵
mn=min(mn,l.dp+y-b[i]);↵
}↵
if(mn<inf) g.push_back((stu){y,mn});↵
}↵
x|=((1<<j)&b[i]);↵
}↵
swap(f,g);↵
}↵
ll mn=inf;↵
for(stu l:f) mn=min(mn,l.dp);↵
if(mn<inf) cout<<mn<<endl;↵
else cout<<-1<<endl;↵
return;↵
}↵
signed main(){↵
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);↵
int T=1;↵
cin>>T;↵
while(T--) Subt();↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2119F]↵
↵
Author: [user:lizhous,2025-07-06]↵
↵
<spoiler summary="Hint 1">↵
Try to determine the vertex where you were before the last move.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
What form of moving path from the starting vertex to the end vertex is considered optimal?↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2119F]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include<iostream>↵
#include<cstdio>↵
#include<algorithm>↵
#include<cstring>↵
#include<vector>↵
#include<set>↵
#include<queue>↵
#include<unordered_map>↵
#include<map>↵
#define int long long↵
using namespace std;↵
int n,st,dist[1000002],w[1000001],tim[1000001],ans;↵
vector <int> g[1000001];↵
int f[1000001];↵
queue<int> q;↵
void getdis(int u,int fa)↵
{↵
for(int v:g[u])↵
{↵
if(v==fa) continue;↵
dist[v]=dist[u]+1;↵
getdis(v,u);↵
}↵
}↵
void dfs(int u,int fa,int k,bool inn,int hei,int TIM,int dis)↵
{↵
if(hei<0)↵
{↵
TIM=max(TIM,(-hei+1)/2*2+k*2+dis);↵
}↵
if(TIM<=dist[u])↵
{↵
ans=max(ans,dist[u]);↵
}↵
else↵
{↵
return;↵
}↵
for(int v:g[u])↵
{↵
if(v==fa) continue;↵
if(inn&&w[u]!=w[v])↵
{↵
dfs(v,u,min(k,tim[v]),inn,hei+w[v],TIM+1,dis+1);↵
}↵
else↵
{↵
dfs(v,u,k,0,hei+w[v],TIM+1,dis+1);↵
}↵
}↵
}↵
int T; ↵
signed main()↵
{↵
ios::sync_with_stdio(false);↵
cin>>T;↵
int cnt=0;↵
while(T--)↵
{↵
cnt++;↵
cin>>n>>st;↵
for(int i=1;i<=n;i++)↵
{↵
dist[i]=0;↵
tim[i]=1000000000;↵
g[i].clear();↵
f[i]=-10000000000000000;↵
}↵
ans=0;↵
for(int i=1;i<=n;i++)↵
{↵
cin>>w[i];↵
}↵
for(int i=1,u,v;i<n;i++)↵
{↵
cin>>u>>v;↵
g[u].push_back(v);↵
g[v].push_back(u);↵
}↵
getdis(1,-1);↵
for(int i=1;i<=n;i++)↵
{↵
for(int v:g[i])↵
{↵
if(w[i]==1&&w[v]==1)↵
{↵
tim[i]=0;↵
q.push(i);↵
break;↵
}↵
}↵
}↵
while(!q.empty())↵
{↵
int u=q.front();↵
q.pop();↵
for(int v:g[u])↵
{↵
if(tim[v]==1000000000&&w[v]!=w[u])↵
{↵
tim[v]=tim[u]+1;↵
q.push(v);↵
}↵
}↵
}↵
dfs(st,-1,tim[st],1,w[st],1,1);↵
cout<<ans+(dist[st]&1)-1<<'\n';↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
[problem:2119A]↵
↵
Author: [user:YuJiahe,2025-07-06]↵
↵
<spoiler summary="Hint 1">↵
$a \oplus 1$ is equivalent to $a - 1$ when $a$ is an odd number, otherwise it is equivalent to $a + 1$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
If you apply $a \gets a \oplus 1$ when $a$ is odd, then that operation should make $a = b$.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2119A]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include <algorithm>↵
#include <cstring>↵
#include <cstdio>↵
#include <vector>↵
#include <queue>↵
using namespace std;↵
int t, a, b, x, y;↵
int main(){scanf("%d", &t);↵
while (t --){scanf("%d%d%d%d", &a, &b, &x, &y);↵
if (a > b) printf("%d\n", (a ^ 1) == b ? y : -1);↵
else {int c0 = b - a, c1 = (b + 1 >> 1) - (a + 1 >> 1);↵
printf("%lld\n", y > x ? 1ll * c0 * x : 1ll * (c0 - c1) * x + 1ll * c1 * y);}↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2119B]↵
↵
Author: [user:Lyz09,2025-07-06]↵
↵
<spoiler summary="Hint 1">↵
Transform $(p_x,p_y)$ to $(q_x,q_y)$ into an operation where $a_i$ is the distance between the two points.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
When $n+1=3$, there is a solution if and only if the largest $a_i$ is less than or equal to the sum of the remaining $a_i$.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2119B]↵
</spoiler>↵
↵
<spoiler summary="Implementation 1">↵
~~~~~↵
#include<iostream>↵
#include<algorithm>↵
#include<cmath>↵
using namespace std;↵
#define N 100010↵
#define int long long↵
int t,n,sx,sy,tx,ty;↵
double a[N];↵
signed main()↵
{↵
cin>>t;↵
while(t--)↵
{↵
cin>>n;↵
cin>>sx>>sy>>tx>>ty;↵
for(int i=1;i<=n;i++)↵
cin>>a[i];↵
a[++n]=sqrt((sx-tx)*(sx-tx)+(sy-ty)*(sy-ty));↵
sort(a+1,a+n+1);↵
double sum=a[n];↵
for(int i=1;i<n;i++)↵
sum-=a[i];↵
if(sum<=0)↵
puts("Yes");↵
else↵
puts("No");↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Implementation 2">↵
~~~~~↵
#include<iostream>↵
#include<algorithm>↵
using namespace std;↵
#define N 100010↵
#define int long long↵
int t,n,sx,sy,tx,ty,a[N];↵
signed main()↵
{↵
cin>>t;↵
while(t--)↵
{↵
cin>>n;↵
cin>>sx>>sy>>tx>>ty;↵
for(int i=1;i<=n;i++)↵
cin>>a[i];↵
sort(a+1,a+n+1);↵
int p=(sx-tx)*(sx-tx)+(sy-ty)*(sy-ty);↵
if(p>a[n]*a[n])↵
{↵
int sum=0;↵
for(int i=1;i<=n;i++)↵
{↵
sum+=a[i];↵
if(sum*sum>=p)↵
break;↵
}↵
if(sum*sum>=p)↵
puts("Yes");↵
else↵
puts("No");↵
}↵
else↵
{↵
int sum=a[n];↵
for(int i=1;i<=n-1;i++)↵
sum-=a[i];↵
if(sum<=0||sum*sum<=p)↵
puts("Yes");↵
else↵
puts("No");↵
}↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2119C]↵
↵
Author: [user:lizhous,2025-07-06]↵
Preparation: [user:Lyz09,2025-07-06]↵
↵
<spoiler summary="Hint 1">↵
For odd $n$, setting $a_i = l$ for all $i$ suffices.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
For even $n$, there does not exist a valid array $a$ that satisfies $a_1=a_2=\dots=a_{n-1}=l$.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
For even $n$, try to satisfy $\oplus_{i=1}^{n}a_i=0$.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2119C]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include<iostream>↵
using namespace std;↵
#define int long long↵
int t,n,l,r,k;↵
signed main()↵
{↵
cin>>t;↵
while(t--)↵
{↵
cin>>n>>l>>r>>k;↵
if(n%2==1)↵
{↵
cout<<l<<endl;↵
continue;↵
}↵
if(n==2)↵
{↵
cout<<-1<<endl;↵
continue;↵
}↵
int res=1;↵
bool fl=0;↵
while(res<=r)↵
{↵
if(res>l)↵
{↵
fl=1;↵
if(k<=n-2)↵
cout<<l<<endl;↵
else↵
cout<<res<<endl;↵
break;↵
}↵
res*=2;↵
}↵
if(!fl)↵
cout<<-1<<endl;↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2119D]↵
↵
Author: [user:YuJiahe,2025-07-06]↵
↵
<spoiler summary="Hint 1">↵
Calculating the weight of a single valid sequence is difficult. Try another way?↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2119D]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include <algorithm>↵
#include <cstring>↵
#include <cstdio>↵
#include <vector>↵
#include <queue>↵
using namespace std;↵
const int N = 5005;↵
int t, n, mod, f[N][N], ans;↵
inline void add(int& x, int y){x += y;if (x >= mod) x -= mod;}↵
int main(){scanf("%d", &t);↵
while (t --){scanf("%d%d", &n, &mod), f[0][0] = 1, ans = 0;↵
for (int i = 1;i <= n;i ++) for (int j = 0;j <= i;j ++) f[i][j] = 0;↵
for (int i = 1;i <= n;i ++)↵
for (int j = 0, now;j < i;j ++)↵
if (now = f[i - 1][j]) add(f[i][j + 1], now),↵
f[i][j] = (f[i][j] + (n - i + 1ll) * (j + 1) * now) % mod;↵
for (int j = 0;j <= n;j ++) add(ans, f[n][j]);printf("%d\n", ans);↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2119E]↵
↵
Author: [user:ma2021tyoi0037,2025-07-06]↵
↵
<spoiler summary="Hint 1">↵
As same as the title, can you find a simple necessary constraint? ↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Consider $a_i = 0$ first.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2119E]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
typedef long long ll;↵
struct stu{↵
int x;↵
ll dp;↵
};↵
int n,a[100007],b[100007];↵
vector<stu> f,g;↵
const ll inf=0x3f3f3f3f3f3f3f3f;↵
void Subt(){↵
cin>>n;↵
for(int i=1;i<n;i++) cin>>a[i];↵
for(int i=1;i<=n;i++) cin>>b[i];↵
a[n]=0;↵
f.clear();↵
f.push_back((stu){0,0});↵
for(int i=1;i<=n;i++){↵
int x=0;↵
g.clear();↵
for(int j=30;j>=-1;j--){↵
int y=x|a[i-1]|a[i];↵
if(j!=-1) y|=(1<<j); ↵
if(y>=b[i]){↵
ll mn=inf;↵
for(stu l:f){↵
if((l.x&y)!=a[i-1]) continue;↵
mn=min(mn,l.dp+y-b[i]);↵
}↵
if(mn<inf) g.push_back((stu){y,mn});↵
}↵
x|=((1<<j)&b[i]);↵
}↵
swap(f,g);↵
}↵
ll mn=inf;↵
for(stu l:f) mn=min(mn,l.dp);↵
if(mn<inf) cout<<mn<<endl;↵
else cout<<-1<<endl;↵
return;↵
}↵
signed main(){↵
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);↵
int T=1;↵
cin>>T;↵
while(T--) Subt();↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2119F]↵
↵
Author: [user:lizhous,2025-07-06]↵
↵
<spoiler summary="Hint 1">↵
Try to determine the vertex where you were before the last move.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
What form of moving path from the starting vertex to the end vertex is considered optimal?↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2119F]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include<iostream>↵
#include<cstdio>↵
#include<algorithm>↵
#include<cstring>↵
#include<vector>↵
#include<set>↵
#include<queue>↵
#include<unordered_map>↵
#include<map>↵
#define int long long↵
using namespace std;↵
int n,st,dist[1000002],w[1000001],tim[1000001],ans;↵
vector <int> g[1000001];↵
int f[1000001];↵
queue<int> q;↵
void getdis(int u,int fa)↵
{↵
for(int v:g[u])↵
{↵
if(v==fa) continue;↵
dist[v]=dist[u]+1;↵
getdis(v,u);↵
}↵
}↵
void dfs(int u,int fa,int k,bool inn,int hei,int TIM,int dis)↵
{↵
if(hei<0)↵
{↵
TIM=max(TIM,(-hei+1)/2*2+k*2+dis);↵
}↵
if(TIM<=dist[u])↵
{↵
ans=max(ans,dist[u]);↵
}↵
else↵
{↵
return;↵
}↵
for(int v:g[u])↵
{↵
if(v==fa) continue;↵
if(inn&&w[u]!=w[v])↵
{↵
dfs(v,u,min(k,tim[v]),inn,hei+w[v],TIM+1,dis+1);↵
}↵
else↵
{↵
dfs(v,u,k,0,hei+w[v],TIM+1,dis+1);↵
}↵
}↵
}↵
int T; ↵
signed main()↵
{↵
ios::sync_with_stdio(false);↵
cin>>T;↵
int cnt=0;↵
while(T--)↵
{↵
cnt++;↵
cin>>n>>st;↵
for(int i=1;i<=n;i++)↵
{↵
dist[i]=0;↵
tim[i]=1000000000;↵
g[i].clear();↵
f[i]=-10000000000000000;↵
}↵
ans=0;↵
for(int i=1;i<=n;i++)↵
{↵
cin>>w[i];↵
}↵
for(int i=1,u,v;i<n;i++)↵
{↵
cin>>u>>v;↵
g[u].push_back(v);↵
g[v].push_back(u);↵
}↵
getdis(1,-1);↵
for(int i=1;i<=n;i++)↵
{↵
for(int v:g[i])↵
{↵
if(w[i]==1&&w[v]==1)↵
{↵
tim[i]=0;↵
q.push(i);↵
break;↵
}↵
}↵
}↵
while(!q.empty())↵
{↵
int u=q.front();↵
q.pop();↵
for(int v:g[u])↵
{↵
if(tim[v]==1000000000&&w[v]!=w[u])↵
{↵
tim[v]=tim[u]+1;↵
q.push(v);↵
}↵
}↵
}↵
dfs(st,-1,tim[st],1,w[st],1,1);↵
cout<<ans+(dist[st]&1)-1<<'\n';↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
