[题解] Atcoder Regular Contest ARC 148 A B C E 题解

题目质量一言难尽（至少对我来说

所以我不写D的题解了

A - mod M

发现如果把M选成2，就可以把答案压到至多2。所以答案只能是1或2，只要判断答案能不能是1即可。如果答案是1，那么M必须是所有任意两个数的差的GCD的因子，只要检查这个GCD是否是1即可。实现的话之间取所有相邻两个数的GCD就行了。

时间复杂度\(O(nloga_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 pii pair <int,int>

#define pb push_back

#define fi first

#define se second

#define mpr make_pair

using namespace std;

int n;

vector <int> v;

int main()

{

  cin>>n;

  int x;

  rep(i,n)

  {

    scanf("%d",&x);

    v.pb(x);

  }

  sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());

  if(v.size()==1)

  {

    puts("1");

    return 0;

  }

  int ans=0;

  rep(i,v.size()-1) ans=__gcd(ans,v[i+1]-v[i]);

  if(ans>1) puts("1");

  else puts("2");

  return 0;

}

B - dp

注意翻转次数可以是0的，所以先用原串更新一下答案。

考虑一个区间[l,r]，我们把他翻转会是什么情况。首先这个区间中如果全是d肯定是不优的，不用考虑。其次，如果r的位置在原串中是d，那把r往左移，移到任意一个区间内p的位置再翻转，一定会更优。现在就已经确定了只有结尾是p的区间才可能被翻转，考虑一个右端点r，满足原串中它的位置是p，选择哪个左端点l翻转会最优(l可以等于r)。找出[0,r]中的第一个是p的位置x，很容易发现，如果l选在x右边，肯定不如直接选在x好。l选在x左边的话，如果[x,r]中全是p，那么显然选在x更好；否则找出[x,r]中最靠右的一个d，可以发现它会导致选x时的整个串第一个p的位置比选在x左边时的整个串第一个p的位置靠后，所以还是选在x最好。对于每个r，找出x，翻转[x,r]，用这个串更新答案即可。

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

点击查看代码

#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 pii pair <int,int>

#define pb push_back

#define fi first

#define se second

#define mpr make_pair

using namespace std;

int n;

string s,ans;

int main()

{

  cin>>n>>s;

  ans=s;

  rep(i,n) if(s[i]=='p')

  {

    string t=s;t[i]='d';

    ans=min(ans,t);

    t=s;

    rep(j,i) if(s[j]=='p')

    {

      reverse(t.begin()+j,t.begin()+i+1);

      for(int k=j;k<=i;++k) if(t[k]=='p') t[k]='d';else t[k]='p';

      ans=min(ans,t);

      break;

    }

  }

  cout<<ans<<endl;

  return 0;

}

C - Lights Out on Tree

注意到一个节点最终的状态是它一开始的状态异或上从根到它的路径上被翻转节点数的奇偶性。所以如果有上下两个相邻节点初始状态不同，那么下面那个一定要挨一次翻转。如果根节点初始状态是正面，那么它也需要被翻转一次。发现只要翻转了上面提到的几种节点，整棵树就满足要求了。接下来主要问题就是对父亲节点和自己的初始状态不懂的节点计数。这个也是很容易做到的，因为这种节点只有两种，一种是在\(S_i\)集合里的，还有一种是集合中节点的直接儿子。求出集合中节点的儿子数量之和再减一下就行了，细节不再赘述。

时间复杂度\(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 pii pair <int,int>

#define pb push_back

#define fi first

#define se second

#define mpr make_pair

using namespace std;

int n,q,p[200010],sn[200010],mark[200010];

int main()

{

  cin>>n>>q;

  for(int i=2;i<=n;++i)

  {

    scanf("%d",&p[i]);

    ++sn[p[i]];

  }

  repn(qn,q)

  {

    int m,x,ans=0,sum=0;

    scanf("%d",&m);

    vector <int> v;

    rep(i,m) scanf("%d",&x),v.pb(x),mark[x]=qn,sum+=sn[x];

    rep(i,m) if(v[i]==1||mark[p[v[i]]]!=qn) ++ans;else --sum;

    ans+=sum;

    printf("%d\n",ans);

  }

  return 0;

}

E - ≥ K

对我来说这E比D简单多了

把相邻两个元素之和\(\geq k\)转化一下，可以把每一个数先都加上\(\frac k2\)，然后条件就变成相邻两个数之和非负，然后就好办多了。k可能是奇数，所以先把输入的所有数都乘2。

把负数和非负数分开，发现最终序列的结构是这样：

\[\cdots 负数，非负数，非负数 \cdots(一堆非负数)，负数，非负数，非负数 \cdots(一堆非负数)，\cdots
\]

也就是不能有两个负数相邻。还有就是与负数相邻的数的绝对值不得小于这个负数的绝对值。

这启发我们按照绝对值从大到小往序列里放数，绝对值相同的先放非负数再放负数。这样负数在被插入时就不会违反上面的第二个条件。观察发现插入一个负数时其实是占用了两个非负数之间的空隙(也可以是序列头尾的空间)，这个空隙以后不能再放任何数(非负数也不行，因为会违反第一个条件)，也可以看成是把旁边的两个非负数合并成1个了。具体来说，在插入某个特定绝对值的数时：

接下来

然后

这样这题就做完了，实现很简单。时间复杂度\(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 pii pair <LL,LL>

#define pb push_back

#define fi first

#define se second

#define mpr make_pair

using namespace std;

const LL MOD=998244353;

LL qpow(LL x,LL a)

{

	LL res=x,ret=1;

	while(a>0)

	{

		if((a&1)==1) ret=ret*res%MOD;

		a>>=1;

		res=res*res%MOD;

	}

	return ret;

}

LL n,k,a[200010],ans=1,fac[400010],inv[400010];

map <LL,pii> mp;

LL C(LL nn,LL mm){return fac[nn]*inv[mm]%MOD*inv[nn-mm]%MOD;}

int main()

{

  fac[0]=1;repn(i,400005) fac[i]=fac[i-1]*i%MOD;

  rep(i,400003) inv[i]=qpow(fac[i],MOD-2);

  cin>>n>>k;

  rep(i,n) scanf("%lld",&a[i]),a[i]+=a[i]-k;

  rep(i,n)

  {

    if(a[i]>=0) ++mp[-a[i]].fi;

    else ++mp[a[i]].se;

  }

  LL len=1;

  for(auto it:mp)

  {

    if(it.se.fi>0) (ans*=C(it.se.fi+len-1,len-1))%=MOD;

    len+=it.se.fi;

    if(it.se.se>len)

    {

      puts("0");

      return 0;

    }

    (ans*=C(len,it.se.se))%=MOD;

    len-=it.se.se;

  }

  cout<<ans<<endl;

  return 0;

}

这几题代码都很短诶

巴特西

[题解] Atcoder Regular Contest ARC 148 A B C E 题解

题目质量一言难尽（至少对我来说

A - mod M

B - dp

C - Lights Out on Tree

E - ≥ K

最新文章

热门文章