10 月 3 日解题报告
10 月 3 日题解
Tasklist
[T1] ARC_134_C
[T2] ARC_108_D
[T3] ARC_137_C
[T4] ARC_064_E
[T1] ARC_134_C The Majority
题目
因为原翻译有些重点并没有点出来，所以这里给出原题直译而不是带有《原神》游戏专业术语的转译版本。
有编号为 \(1\) 到 \(K\) 的 \(K\) 个盒子。最初，所有的盒子都是空的。
Snuke 有一些球，上面写着从 \(1\) 到 \(N\) 的整数。其中 \(a_i\) 个球的编号为 \(i\) 。写有相同整数的球不能被区分。
Snuke 决定把他所有的球都放进盒子里。他希望数字为 \(1\) 的球在每个盒子中都占多数。换句话说，在每个盒子中，编号为 \(1\) 的球的数量应该大于其他球的数量。
求使用这种方式将所有球放入箱子的方案数。
答案对 \(998244353\) 取模。
思路
直接按照上面的翻译写了
咋一看肯定是排列组合的题。
最直接的想法就是我枚举每个箱子放多少哪种球，但这样显然会超时。
反过来想，如果没有 \(1\) 号球必须比其它球多的限制，这题直接挨个隔板就行。
现在有这条限制了。如果我直接把 \(1\) 球和后面每个球配对就可以了，这样就可以不用考虑这条限制了…………吗？
显然，原题是大于不是大于等于。
所以我们再把剩下的 \(1\) 种类球放到每个盒子里各一个。
此时如果 \(1\) 种类球不够了，则不存在答案，方案数是 \(0\)，它对答案就没有影响，无视就行。
如果还剩 \(1\) 种类球，直接用隔板法隔就行。
考虑完剩下的 \(1\) 种类球后，我们考虑剩下的所有球。
因为此时每个盒子里都有 1 个 \(1\) 球，所以剩下每种球都单独考虑怎么放就行。
因为前面已经把每种球匹配起来了，可以直接使用隔板法计算答案。
最终公式为 $ C^{K - 1}{K + a^n - 1} \times \prod^{N} C^{K - 1}_{K + a_i - 1} $。
因为有除法，所以需要写个逆元。
Code
MD 又没调出来就不写了
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int mod=998244353;
int n,k;
long long a[N];
long long fac[N],inv[N];
long long ans;
long long modpow(int x,int y){
long long sum=1;
for(;y!=0;y>>=1){
if(y&1)
sum=sum*x%mod;
x=x*x%mod;
}
return sum%mod;
}
long long C(long long n,long long m){
long long reu=1;
for(int i=m+1;i<=n;i++)
reu=reu*i%mod;
long long cs=1;
for(int i=1;i<=n-m;i++)
cs=cs*i%mod;
reu=reu*modpow(cs,mod-2)%mod;
return reu%mod;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
long long sum=0;
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i],sum+=a[i];
sum-=a[1];
a[1]-=sum+k;
if(a[1]<0){
cout<<0;
return 0;
}
long long delta= a[1] == 0 ? 1 : C(a[1]-1,k-1);
ans= delta <= 0 ? 1 : delta ;
for(int i=2;i<=n;i++)
ans=ans*C(k+a[i]-1,k-1)%mod;
cout<<ans%mod;
return 0;
}
[T2] ARC_108_D AB
思路
直接想很难，首先打个表。
打完表后题目就简单多了。
直接找规律就行。
找完规律后分类讨论就行。
因为总共只用 16 种可能的 C 序列出现。
Code
真没调，不写了
[T3] ARC_137_C ARC_137_C
思路
一眼博弈题。
众所周知博弈题思路难 but 代码短
以下思路默认先手
首先，先考虑必败态：一堆都没有。
然后显然就有必胜态：有且只有一堆。
然后考虑转移到必胜态的必败态。
可以是更大的一堆…………吗？
显然不行。如果有这样一堆的话，它是可以直接转移到必败态的。
所以只能是两堆。
两堆的话我完全有可能来回缩小使得对手总是处于一个可能为失败的状态。
所以这里需要开始限定数字了。
假设第一次推出来的那个状态中唯一一堆数字是 1。
那么此时必败态为 1 2。
如果另一个数字不是 2 呢？
那我可以转移到这个状态，使得下一个人必败。
如果不是 1 2 而是 2 3 呢？
也可以……吗？
我转移有 2->1 和 3->1 两种。
显然，任何一个转移到 0 是自讨苦吃。
前者变为 1 3，此时必败。
后者变为 1 2，此时必败。
所以 2 3 为一个必败态。
如果是 2 4 呢？
必胜。转移到 1 2 即可。
如果是 3 4 呢？
必败。
可以转移到 2 4，1 4，2 3，1 3
这四个都是必败。
如果是 3 5 呢？
必胜。
所以我们可以看出来，如果最后两个数字之差 \(>\) \(1\)，此时必胜。
如果前面有怎么办？
直接分开转移就行。
可以证明一定能够使局面变成只有最后两个数字的情况。
现在，如果 \(a[n] - a[n-1] \xlongequal {} 1\) 呢？
Alice 必败吗？
Alice 可以选择移动后保持这个局面（\(a[n] - a[n-1] \xlongequal {} 1\) ），Bob 同理。
此时，因为有且只有 $ a[n] − (n − 1) $ 个回合，若 \(a[n] - n\) 为偶数，Alice 必胜。
反之，Bob 必败。
Code
博弈题特有的短小精悍
#include <bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n;
int a[N];
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
if(a[n]-a[n-1]>1||(a[n]-n)%2==0)
cout<<"Alice";
else
cout<<"Bob";
return 0;
}
短小精悍到复杂度最大的甚至是 O(n) 的输入
无视输入，复杂度 O(1)
[T4] ARC_064_E Cosmic Rays
思路
第一眼看题的时候以为只能平行于坐标轴走……
看一眼数据范围：
$ -10^9 \le X_i, Y_i, X_s, Y_x, X_t, Y_t \le 10^9$
$ ± 1e9 $，显然不能直接对坐标 bfs，更何况还可以不平行坐标轴走。
再看眼题目，发现答案的贡献来自没走障碍物的情况。
那我为什么不直接往障碍物里走呢？
如果到终点距离比到最近障碍物距离大呢
可以直接分讨：
- 到终点距离比到最近的障碍物距离近
- 到终点距离比到最近的障碍物距离远
这样的话，看情况 \(2\)：
如果我们移动到圆内了，那么此时不论怎么走都对答案没有贡献毕竟它又没要求在此基础上走过距离最短。
我们可以把起点和终点看作两个 \(r \xlongequal {} 0\) 的圆。
那么我们可以把圆缩成点了。
那么点之间的边距可以预处理出来…………吗？
看一下数据范围：
\(1 \le N \le 1000\)
可以。
此时应该能想到在点之间连边跑 \(Dijsktra\) 了。
这样的话其实用不上分讨了，直接把起点和终点也连上边，再和每个点连上边跑最短路就行了。
Code
我们有 3 个人想到正解了，但就我 AC 了，另外两位一位 94 一位 6 分
6 分那位数组开小了->不用 vector 执意用链表导致的
94 分那位最大值开小了
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
struct Circle{
int x,y,r;
}c[N];
struct edge{
int v;
double w;
};
struct node{
int u;
long double dis;
bool operator < (const node &a) const { return dis > a.dis ; }
};
// 特别的，s 为 0 号点，t 为 n+1 号点
long double dis[N];
bool vis[N];
int n,sx,sy,ex,ey;
vector <edge> g[N];
inline void dij(){
priority_queue <node> q;
for(int i=1;i<=n+1;i++)
dis[i]=INFINITY;
q.push((node){0,0.0});
while(!q.empty()){
node no=q.top();
q.pop();
if(vis[no.u])
continue;
vis[no.u]=1;
for(edge ed:g[no.u])
if(dis[ed.v] > ed.w + no.dis)
dis[ed.v]=ed.w + no.dis,q.push((node){ed.v,dis[ed.v]});
}
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>sx>>sy>>ex>>ey>>n;
for(int i=1;i<=n;i++)
cin>>c[i].x>>c[i].y>>c[i].r;
double tmpdis;
long long deltax;
long long deltay;
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++){
deltax=c[i].x-c[j].x;
deltay=c[i].y-c[j].y;
tmpdis=max(sqrt(deltax*deltax+deltay*deltay)-(double)c[i].r-(double)c[j].r,0.0);
g[i].emplace_back((edge){j,tmpdis});
g[j].emplace_back((edge){i,tmpdis});
}
deltax=sx-ex;
deltay=sy-ey;
tmpdis=sqrt(deltax*deltax+deltay*deltay);
g[0].emplace_back((edge){n+1,tmpdis});
g[n+1].emplace_back((edge){0,tmpdis});
for(int i=1;i<=n;i++){
deltax=sx-c[i].x;
deltay=sy-c[i].y;
tmpdis=max(sqrt(deltax*deltax+deltay*deltay)-c[i].r,0.0);
g[0].emplace_back((edge){i,tmpdis});
g[i].emplace_back((edge){0,tmpdis});
}
for(int i=1;i<=n;i++){
deltax=ex-c[i].x;
deltay=ey-c[i].y;
tmpdis=max(sqrt(deltax*deltax+deltay*deltay)-c[i].r,0.0);
g[n+1].emplace_back((edge){i,tmpdis});
g[i].emplace_back((edge){n+1,tmpdis});
}
dij();
printf("%.10Lf",dis[n+1]);
return 0;
}