ARC163
A
显然划分两次最优,直接枚举即可
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2005;
int t;
int n;
char s[MAXN];
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
scanf("%s",s+1);
// for(int i=1;i<=n;i++)
// {
// printf("%c",s[i]);
// }
// printf("\n");
bool f=0;
for(int i=2;i<=n;i++)
{
string S,T;
S.clear();
T.clear();
for(int j=1;j<i;j++)
{
S+=s[j];
}
for(int j=i;j<=n;j++)
{
T+=s[j];
}
// cout<<T<<endl;
// cout<<S<<' '<<T<<endl;
if(S<T)
{
f=1;
}
}
if(f)
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
}
B
直接枚举\(a_1\),然后二分找到最小\(a_2\)的位置,线段树维护一下
两个\(log\)有点卡常
#include<bits/stdc++.h>
#define ls Tree[p].lc
#define rs Tree[p].rc
using namespace std;
const int MAXN=2e5+5;
int n;
int m;
int A[MAXN];
struct Seg{
int date,lc,rc;
}Tree[MAXN*30];
int rt;
int cnt_node;
void Insert(int &p,int l,int r,int k)
{
if(!p)
{
p=++cnt_node;
}
Tree[p].date++;
if(l==r)
{
return;
}
int mid=(l+r)>>1;
if(k<=mid){
Insert(ls,l,mid,k);
}
else
{
Insert(rs,mid+1,r,k);
}
}
int Query(int p,int l,int r,int ql,int qr)
{
if(!p)
{
return 0;
}
if(l>=ql&&r<=qr)
{
return Tree[p].date;
}
int Res=0;
int mid=(l+r)>>1;
if(ql<=mid)
{
Res+=Query(ls,l,mid,ql,qr);
}
if(qr>mid)
{
Res+=Query(rs,mid+1,r,ql,qr);
}
return Res;
}
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&A[i]);
}
for(int i=3;i<=n;i++)
{
Insert(rt,1,1e9,A[i]);
}
int Res=2e9;
for(int i=1;i<=n;i++)
{
int l=A[i];
int r=1e9;
int Key=-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(Query(rt,1,1e9,A[i],mid)>=m)
{
r=mid-1;
Key=mid;
}
else
{
l=mid+1;
}
}
if(Key!=-1)
{
int Tot=max(0,A[1]-A[i])+max(0,Key-A[2]);
Res=min(Res,Tot);
}
}
printf("%d",Res);
}
C
首先有\(\dfrac{1}{n(n+1)}=\dfrac{1}{n}-\dfrac{1}{n+1}\)
有个比较显的思路,考虑\(a_i=\dfrac{1}{i(i+1)},a_n=\dfrac{1}{n}\)
唯一的问题在于\(n\)在之前被访问过
实际上直接整体\(\times\dfrac{1}{2}\)再用个\(\dfrac{1}{2}\)即可
#include<bits/stdc++.h>
using namespace std;
const int MAXN=505;
int T;
int n;
int Vis[MAXN*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++)
{
Vis[i*(i+1)]=1;
}
if(n==2)
{
printf("No\n");
}
else if(!Vis[n])
{
printf("Yes\n");
for(int i=1;i<n;i++)
{
printf("%d ",i*(i+1));
}
printf("%d\n",n);
}
else
{
printf("Yes\n2 ");
for(int i=1;i<n-1;i++)
{
printf("%d ",2*i*(i+1));
}
printf("%d\n",2*(n-1));
}
for(int i=1;i<n;i++)
{
Vis[i*(i+1)]=0;
}
}
}
D
竞赛图有个性质是缩点后拓扑序已经确定了
考虑把拓扑序拉出来,\(s_1,s_2,s_3,s_4....s_k\)
对于\(s_i,s_{i+1}\),我们可以将\([1,i]\)化分为一个点集\(A\),\([i+1,k]\)划分成另一个点集\(B\),满足两点集之间的边都是\(A\rightarrow B\)
可以发现任意合法的点集划分对应这一个分割点\(i\)
于是直接考虑对点集划分计数,设\(dp_{i,j,k}\)表示前\(i+j\)个点,有\(i\)个点分到\(A\),\(j\)个点分到\(B\)其中有\(k\)对小指大的方案
转移就直接枚举\(A/B\)中的连边情况,注意一下\(i+j\)归到\(B\)时\(k\)要\(+i\)
// LUOGU_RID: 120168019
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
const int MAXN=55;
int n;
int m;
int dp[MAXN][MAXN][MAXN*MAXN];
int C[MAXN*MAXN][MAXN*MAXN];
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d %d",&n,&m);
C[0][0]=1;
for(int i=1;i<=n*n;i++)
{
C[i][0]=1;
for(int j=1;j<=i;j++)
{
C[i][j]=((long long)C[i-1][j]+C[i-1][j-1])%MOD;
}
}
dp[0][0][0]=1;
for(int i=0;i<=n;i++)
{
for(int j=0;(i+j)<=n;j++)
{
for(int k=0;k<=m;k++)
{
if(!dp[i][j][k])
{
continue;
}
for(int t=0;t<=i;t++)
{
dp[i+1][j][k+t]=((long long)dp[i+1][j][k+t]+((long long)dp[i][j][k]*C[i][t])%MOD)%MOD;
}
for(int t=0;t<=j;t++)
{
dp[i][j+1][k+t+i]=((long long)dp[i][j+1][k+t+i]+((long long)dp[i][j][k]*C[j][t])%MOD)%MOD;
}
}
}
}
int Res=(MOD-C[(n*(n-1))/2][m]);
for(int i=0;i<=n;i++)
{
Res=((long long)Res+dp[i][n-i][m])%MOD;
}
printf("%d\n",Res);
}