ARC162E
A
简单分类讨论即可
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e3+5;
int T;
int n;
int P[MAXN];
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&P[i]);
}
int Res=0;
for(int i=1;i<=n;i++)
{
bool f=1;
for(int j=i+1;j<=n;j++)
{
if(P[j]<P[i])
{
f=0;
}
}
Res+=f;
}
printf("%d\n",Res);
}
}
B
一个初步的想法是将\(1-n\)每个数依次排好序,唯一可能出现的问题是目前想排的数被抵到末尾了,这里我们只需要把它调整\(n-1\)的位置即可,只有当剩余只有两个数出现这种情况时无解
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e3+5;
int n;
int P[MAXN];
int Tmp[MAXN];
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&P[i]);
}
vector<pair<int,int>>Opra;
for(int i=1;i<n;i++)
{
int Pos;
if(P[i]==i)
{
continue;
}
for(int j=i;j<=n;j++)
{
if(P[j]==i)
{
Pos=j;
break;
}
}
if(Pos==n)
{
if((n-i+1)<=2)
{
printf("No");
return 0;
}
Opra.push_back(make_pair(n-1,n-3));
Pos=n-1;
int gk=P[n-2];
P[n-2]=P[n-1];
P[n-1]=P[n];
P[n]=gk;
}
Opra.push_back(make_pair(Pos,i-1));
for(int j=i;j<=n;j++)
{
Tmp[j]=P[j];
}
P[i]=Tmp[Pos];
P[i+1]=Tmp[Pos+1];
int Poi=i;
for(int j=i+2;j<=n;j++)
{
if(Poi==Pos)
{
Poi+=2;
}
P[j]=Tmp[Poi];
++Poi;
}
}
printf("Yes\n");
printf("%ld\n",Opra.size());
for(int i=0;i<Opra.size();i++)
{
printf("%d %d\n",Opra[i].first,Opra[i].second);
}
}
C
很zz的博弈
很明显\(B\)只会填\(k\),填了\(u\)之后\(u\)的祖先都不可能赢
对于\(A\),她只能走第一步赢,因为\(B\)可以根据\(A\)选的点来破坏\(A\)想让\(u\)赢的意图
所以直接check一下\(A\)走一步能不能赢即可
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int T;
int n,k;
int x;
int A[MAXN];
vector<int>g[MAXN];
int Vis[MAXN];
int Cnt=0;
void find(int x,int f)
{
if(A[x]!=-1)
{
Vis[A[x]]=1;
}
else
{
++Cnt;
}
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==f)
{
continue;
}
find(v,x);
}
}
bool found=0;
void dfs(int x,int f)
{
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==f)
{
continue;
}
dfs(v,x);
}
for(int i=0;i<=n;i++)
{
Vis[i]=0;
}
Cnt=0;
find(x,f);
int Mex;
for(int i=0;i<=n;i++)
{
if(!Vis[i])
{
Mex=i;
break;
}
}
if(Mex==k&&((!Cnt)||(Cnt==1)))
{
found=1;
}
if(Cnt==1)
{
//printf("%d???\n",Mex);
Vis[Mex]=1;
for(int i=0;i<=n;i++)
{
if(!Vis[i])
{
Mex=i;
break;
}
}
if(Mex==k)
{
//printf("%deee???\n",x);
found=1;
}
}
}
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&T);
while(T--)
{
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)
{
g[i].clear();
}
for(int i=2;i<=n;i++)
{
scanf("%d",&x);
g[x].push_back(i);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&A[i]);
}
found=0;
dfs(1,0);
if(found)
{
printf("Alice\n");
}
else
{
printf("Bob\n");
}
}
}
E
乍一看都不知道这个题在说些什么
仔细想想就可以发现设\(d_i\)为\(i\)出现的次数
我们要保证\(d_i\le A_i\)并且满足填入第\(i\)位的数\(j\)满足\(d_j\le A_i\)
这个\(d_i\le A_i\),经典\(dp\)
而对于后面的条件,我们可以按填的\(d_i\)从大到小\(dp\),这样就可以得到哪些位置能填以及哪些值能用
具体的设\(dp_{i,j,k}\)表示考虑了出现次数\(\ge i\)的,填了\(j\)种数,填了\(k\)个位置的方案数
转移直接枚举下一次填了\(t\)种数即可,时间复杂度因为\(j,i\le\dfrac{n}{i}\),精细实现是\(O(n^3)\)的,多个\(log\)好像会\(T\)
// LUOGU_RID: 120706268
#include<bits/stdc++.h>
using namespace std;
const int MAXN=505;
const int MOD=998244353;
int n;
int a[MAXN];
int dp[MAXN][MAXN][MAXN];
int C[MAXN][MAXN];
int fac[MAXN];
int inv_fac[MAXN];
int Cp[MAXN];
int Pow(int a,int b,int p)
{
int res=1;
int base=a;
while(b)
{
if(b&1)
{
res=((long long)res*base)%p;
}
base=((long long)base*base)%p;
b>>=1;
}
return res;
}
int inv(int a,int p)
{
return Pow(a,p-2,p);
}
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=0;i<=n;i++)
{
Cp[i]=0;
for(int j=1;j<=n;j++)
{
if(a[j]>=i)
{
Cp[i]++;
}
}
}
C[0][0]=1;
fac[0]=1;
for(int i=1;i<=n;i++)
{
C[i][0]=1;
fac[i]=((long long)fac[i-1]*i)%MOD;
for(int j=1;j<=n;j++)
{
C[i][j]=((long long)C[i-1][j]+C[i-1][j-1])%MOD;
}
}
inv_fac[n]=inv(fac[n],MOD);
for(int i=n-1;i>=0;i--)
{
inv_fac[i]=((long long)inv_fac[i+1]*(i+1))%MOD;
}
dp[n+1][0][0]=1;
for(int i=n+1;i>=1;i--)
{
int P=Cp[i-1];
for(int j=0;j<=n&&j<=P&&(i*j<=n);j++)
{
for(int k=0;k<=P;k++)
{
if(!dp[i][j][k])
{
continue;
}
int Pw=1;
for(int t=1;t+j<=n&&k+(t*(i-1))<=P&&t<=P&&(P-k-t*(i-1))>=0;t++)
{
Pw=((long long)Pw*inv_fac[i-1])%MOD;
int DJ=dp[i][j][k];
DJ=((long long)DJ*C[P-j][t])%MOD;
DJ=((long long)DJ*fac[P-k])%MOD;
DJ=((long long)DJ*Pw)%MOD;
DJ=((long long)DJ*inv_fac[P-k-t*(i-1)])%MOD;
dp[i-1][t+j][k+(t*(i-1))]=((long long)dp[i-1][t+j][k+(t*(i-1))]+DJ)%MOD;
}
dp[i-1][j][k]=((long long)dp[i-1][j][k]+dp[i][j][k])%MOD;
}
}
}
printf("%d",dp[0][n][n]);
}