526互联

freee Programming Contest 2023（AtCoder Beginner Contest 310）题解

发布时间 2023-07-15 22:36:05作者: LegendStane

点我看题

A - Order Something Else

直接比较\(P\)和\(Q+min(D_i)\)，输出较小值即可。

点击查看代码 
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

int n,p,q,d;

int main()
{
	fileio();

  cin>>n>>p>>q;
  int mn=1e9;
  rep(i,n)
  {
    cin>>d;
    mn=min(mn,d);
  }
  cout<<min(p,q+mn)<<endl;

	termin();
}

B - Strictly Superior

发现n只有100，所以可以直接遍历所有的(i,j)，并判断i是否全面优于j。判断i的功能是否完全覆盖j以及是否还比j多出一些功能时，用bitset会比较方便。

时间复杂度\(O(n^2logn)\)(使用bitset)。

点击查看代码 
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

int n,m,p[110],c[110];
bitset <110> bs[110];

int main()
{
	fileio();

  cin>>n>>m;
  rep(i,n)
  {
    cin>>p[i]>>c[i];
    int x;rep(j,c[i]){cin>>x;bs[i][x-1]=1;}
  }
  rep(i,n) rep(j,n) if(i!=j&&p[i]<=p[j]&&(bs[i]&bs[j])==bs[j])
  {
    if(p[i]<p[j]||bs[i]!=bs[j])
    {
      puts("Yes");
      termin();
    }
  }
  puts("No");

	termin();
}

C - Reversible

令\(T_i\)为\(S_i\)翻转后的结果。对于i和j，显然第i根和第j根棍子等价当且仅当\(min(S_i,T_i)=min(S_j,T_j)\)，其中\(min(a,b)\)表示两者中字典序较小的。所以把所有的\(min(S_i,T_i)\)放到一起去重，输出剩下的个数即可。

时间复杂度\(O(nlogn)\)。

点击查看代码 
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

int n;
vector <string> ss;
string s;

int main()
{
	fileio();
  ios::sync_with_stdio(false);
  
  cin>>n;
  rep(i,n)
  {
    cin>>s;
    string t=s;reverse(t.begin(),t.end());
    ss.pb(min(s,t));
  }
  sort(ss.begin(),ss.end());ss.erase(unique(ss.begin(),ss.end()),ss.end());
  cout<<ss.size()<<endl;

	termin();
}

D - Peaceful Teams

令\(dp_{i,mask}\)表示已经分了i组，并且已经被分组的运动员集合是mask的方案数。转移时枚举接下来一组的运动员集合nxt，此时为了避免重复计算，要求nxt必须包含还没被分组的运动员中编号最小的那个。对枚举的nxt还有一个要求，就是其中没有任意两个人有矛盾。这个可以\(O(n^22^n)\)预处理。转移方程式为\(dp_{i+1,mask|nxt}+=dp_{i,mask}\)。

时间复杂度\(O(n3^n+n^22^n)\)。

由于这题怎么写都能过，所以下面代码的复杂度是\(O(n4^n)\)。

点击查看代码 
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

LL n,t,m,bad[20][20],badm[1100],dp[20][1100];

int main()
{
	fileio();

  cin>>n>>t>>m;
  rep(i,m){int x,y;cin>>x>>y;bad[x-1][y-1]=bad[y-1][x-1]=1;}
  rep(i,1<<n) rep(j,n) rep(k,n) if(j!=k&&(i&(1<<j))&&(i&(1<<k))&&bad[j][k]) badm[i]=1;
  dp[0][0]=1;
  rep(i,t) rep(j,1<<n) if(dp[i][j]&&j!=((1<<n)-1))
  {
    int lb;
    rep(k,n) if(!(j&(1<<k))){lb=1<<k;break;}
    rep(k,1<<n) if(!(j&k)&&(k&lb)&&!badm[k]) dp[i+1][j|k]+=dp[i][j];
  }
  cout<<dp[t][(1<<n)-1]<<endl;

	termin();
}

E - NAND repeatedly

先观察一下"NAND"运算。为了方便我们管NAND运算中左边的参数叫A，右边的参数叫B，结果叫C。发现C=0当且仅当A=B=1，且当B=0时，C必=1。

考虑枚举所有的j，分别计算\(\sum_{i=1}^j f(i,j)\)。如果\(S_i=0\)，这个值=j-1，因为\(f(j,j)=0,f(i,j)=1(1\le i <j)\)。否则令cnt表示从\(S_i\)向前的连续的1的个数，cnt可以在枚举j的同时维护。此时这个值的计算方法如下：对于\(j-cnt<i\le j\)的\(f(i,j)\)，举个例子，当cnt=5时，注意到\(f(j,j)=1,f(j-1,j)=0,f(j-2,j)=1,f(j-3,j)=0\cdots\)，所以这部分的贡献为\(\lfloor \frac {cnt}2\rfloor\)。还有两种情况：如果\(i-cnt>0\)，那么\(f(i-cnt,j)=cnt\ mod\ 2\)；如果\(i-cnt-1>0\)，那么\(\sum_{i=1}^{i-cnt-1}f(i,j)=(i-cnt-1)\cdot(1-(cnt\ mod\ 2))\)。这两部分的答案都需要加上。

时间复杂度\(O(n)\)。

点击查看代码 
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

LL n,ans=0;
string s;
char c[1000010];

int main()
{
	fileio();

  cin>>n;
  scanf("%s",c);s=c;
  LL con=0;
  rep(i,n)
  {
    if(s[i]=='0') con=0,ans+=(LL)i;
    else
    {
      ++con;
      ans+=(con+1)/2;
      if(con<i+1) ans+=con%2;
      if(con+1<i+1) ans+=(i-con)*(1-con%2);
    }
  }
  cout<<ans<<endl;

	termin();
}

F - Make 10 Again

令\(dp_{i,mask}\)表示已经投了前i个骰子，能合成的[0,10]中的数的集合刚好为mask的概率(\(0\le mask<2^{11}\))。转移的时候，如果接下来一个骰子的数值在10以内，可以直接枚举并转移；如果数值>10，对合成10是完全没有帮助的，可以当成一种情况统一处理掉。

时间复杂度\(O(2^{11}\cdot 10n)\)。

点击查看代码 
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

const LL MOD=998244353;

LL qpow(LL x,LL a)
{
	LL res=x,ret=1;
	while(a>0)
	{
		if(a&1) (ret*=res)%=MOD;
		a>>=1;
		(res*=res)%=MOD;
	}
	return ret;
}

LL n,a[110],dp[110][2100],nxt[2100][20];

int main()
{
	fileio();

  cin>>n;
  rep(i,n) cin>>a[i];
  dp[0][1]=1;
  rep(i,2048) repn(j,10)
  {
    int ii=i;
    rep(k,11) if((i&(1<<k))&&k+j<=10) ii|=(1<<(k+j));
    nxt[i][j]=ii;
  }
  rep(i,n) rep(j,2048) if(dp[i][j])
  {
    LL po=qpow(a[i],MOD-2);
    repn(k,min(10LL,a[i])) (dp[i+1][nxt[j][k]]+=dp[i][j]*po)%=MOD;
    if(a[i]>10) (dp[i+1][j]+=dp[i][j]*(a[i]-10)%MOD*po)%=MOD;
  }
  LL ans=0;
  rep(i,2048) if(i&(1<<10)) (ans+=dp[n][i])%=MOD;
  cout<<ans<<endl;

	termin();
}

G - Takahashi And Pass-The-Ball Game

纯纯的大模拟。对于每个i，我们从\(i\)向\(A_i\)连一条有向边，形成了一个内向基环森林。对于第i个人，我们考虑他手上的\(B_i\)个球最后会到哪个人手里。令\(t_j\)表示从第i个人开始沿着图走j步能走到的人。显然有\(\frac 1K\)的概率到\(t_1\)手里，有\(\frac 2K\)的概率到\(t_2\)手里\(\cdots\) 其中可能会重复经过一些人，对答案的贡献也是需要计算多次的，比较麻烦。

考虑枚举每个i，我们统计第i个人手上的\(B_i\)个球产生的贡献。我们把从第i个人开始走的长度为K的路径画出来。如果这个路径没有走到任何一个基环上，那就是一个树上路径加，用树上差分解决；如果走到了基环上，那就是一个树上路径加，给基环上所有点的答案统一加上一个值，然后还有一个基环上的区间加，这些都可以用差分解决或是很简单地维护。

时间复杂度\(O(n)\)。

很难写也很无聊，所以代码摆了。