模拟赛
赛后看着分哗啦啦的往下掉。
T1 median
找中位数，赛时假做法 A 了，
没想到直接搜。。。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5,mod = 998244353;
int n;
int a[6][N],ans,f[6][4];
unordered_map<int,bool> mp;
int dfs(int p,int l,int e,int g)
{
if(p>5) return 1;
int res=0;
if(l<2&&f[p][1]) res=(res+1ll*dfs(p+1,l+1,e,g)*f[p][1])%mod;
if(f[p][2]) res=(res+1ll*dfs(p+1,l,e+1,g)*f[p][2])%mod;
if(g<2&&f[p][3]) res=(res+1ll*dfs(p+1,l,e,g+1)*f[p][3])%mod;
return res;
}
int main()
{
freopen("median.in","r",stdin);
freopen("median.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=5;i++)
{
for(int j=1;j<=n;j++) scanf("%d",&a[i][j]);
sort(a[i]+1,a[i]+1+n);
}
for(int i=1;i<=5;i++)
{
for(int j=1;j<=n;j++)
{
int mid=a[i][j];
if(mp[mid]) continue;
mp[mid]=1;
memset(f,0,sizeof(f));
for(int k=1;k<=5;k++)
{
f[k][1]=upper_bound(a[k]+1,a[k]+1+n,mid)-a[k]-1;
f[k][3]=n-(lower_bound(a[k]+1,a[k]+1+n,mid)-a[k])+1;
f[k][2]=f[k][1]+f[k][3]-n;
f[k][1]-=f[k][2]; f[k][3]-=f[k][2];
}
int res=dfs(1,0,0,0);
ans=(ans+1ll*mid*res)%mod;
}
}
printf("%d\n",ans);
return 0;
}
T2 travel
细节较多，发现有两种情况会使 \(f\) 是发散的。
-
有环。
-
一条路径上有两个自环。
注意差分约束或者 tarjan 判环。
重学 tarjan
code
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int n,m;
int head[N],tot,du[N],zh[N];
struct E {int u,v;} e[N<<1];
inline void add(int u,int v) {e[++tot]={head[u],v}; head[u]=tot;}
queue<int> q;
bool vs[N];
bool dfs(int u,int cnt)
{
cnt++; vs[u]=1;
for(int i=head[u];i;i=e[i].u)
{
int v=e[i].v; if(!du[v]||vs[v]) continue;
if(dfs(v,cnt)) return 1;
}
return cnt>=1;
}
bool dfs1(int u,bool p)
{
vs[u]=1; if(zh[u]) p=1;
for(int i=head[u];i;i=e[i].u)
{
int v=e[i].v; if(vs[v]) continue;
if(p&&zh[v]) return 1;
if(dfs1(v,p)) return 1;
}
return 0;
}
int main()
{
freopen("travel.in","r",stdin);
freopen("travel.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y; scanf("%d%d",&x,&y);
if(x==y) zh[x]++;
else add(x,y), du[y]++;
}
for(int i=1;i<=n;i++) if(!du[i]) q.push(i);
for(int i=1;i<=n;i++)
{
if(zh[i]>=2) {printf("Yes\n"); return 0;}
}
for(int i=1;i<=n;i++) if(!vs[i])
{
if(dfs1(i,0)) {printf("Yes\n"); return 0;}
}
memset(vs,0,sizeof(vs));
while(!q.empty())
{
int u=q.front(); q.pop();
for(int i=head[u];i;i=e[i].u)
{
int v=e[i].v; du[v]--;
if(!du[v]) q.push(v);
}
}
for(int i=1;i<=n;i++) if(du[i]&&!vs[i])
{
if(dfs(i,0)) {printf("Yes\n"); return 0;}
}
printf("No\n");
return 0;
}
T3 game
博弈论捏。
发现 \({1,1}\) 的情况先手必输。
然后考虑有什么性质。
如果把所有数放在数轴上的话：
对于一个个数为奇数且每个数出现次数不全为偶数的局面，我们选取最大的数然后分给其他的，都能得到一个每个数都出现偶数次的局面。
如果每个数都出现偶数次，那下一个状态一定不可能还是每个数出现偶数次。
所以如果一开始每一个数都出现偶数次，那么先手必输，否则后手必输。
注意判断 \(n\) 的奇偶。如果奇数个必赢。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int T,n,a[N];
int main()
{
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
scanf("%d",&T);
while(T--)
{
int x=0,y=0;
scanf("%d\n",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+1+n);
if(n&1) {printf("Yes\n"); continue;}
bool fl=0;
for(int i=1;i<n;i+=2) if(a[i]!=a[i+1]) {printf("Yes\n"); fl=1; break;}
if(!fl) printf("No\n");
}
return 0;
}