[题解] Atcoder Regular Contest ARC 146 A B C D 题解

点我看题

A - Three Cards

先把所有数按位数从多到少排序，答案的位数一定等于位数最多的三个数的位数之和\(tot\)。对于每个i，把有i位的数排序，并记录每个i的排序结果。最后枚举答案中三个数最靠前的数\(a_i\)，然后枚举第二个数的长度\(lenj\)，取长度为lenj的数中最大的。如果这个最大的数就是i，那就取第二个。第三个数的长度就是\(tot-leni-lenj\)，仍然是取这个长度中最大的数即可。

时间复杂度\(O(7 \cdot 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;

LL n,a[200010];

string s[200010],ans;

vector <LL> lens,v[10];

int main()

{

  cin>>n;

  rep(i,n)

  {

    scanf("%lld",&a[i]);

    LL tmp=a[i];

    while(tmp>0)

    {

      s[i].pb(tmp%10+'0');

      tmp/=10;

    }

    reverse(s[i].begin(),s[i].end());

    lens.pb(s[i].size());

    v[s[i].size()].pb(i);

  }

  sort(lens.begin(),lens.end());

  LL need=lens.back()+lens[lens.size()-2]+lens[lens.size()-3];

  repn(i,8) sort(v[i].begin(),v[i].end(),[](int x,int y){return a[x]>a[y];});

  rep(i,need) ans.pb('0');

  rep(i,n)

  {

    repn(nxtlen,7) if(v[nxtlen].size()>0)

    {

      int j=v[nxtlen][0];

      if(j==i)

      {

        if(v[nxtlen].size()==1) continue;

        j=v[nxtlen][1];

      }

      LL lftlen=need-s[i].size()-nxtlen;

      if(lftlen<1||lftlen>7) continue;

      rep(k,v[lftlen].size()) if(v[lftlen][k]!=i&&v[lftlen][k]!=j)

      {

        string res=s[i]+s[j]+s[v[lftlen][k]];

        if(res>ans) ans=res;

        break;

      }

    }

  }

  cout<<ans<<endl;

  return 0;

}

B - Plus and AND

考虑从高往低枚举答案的每一位能否取1（过程相当于二分答案）。假设现在需要检查答案能否\(\geq mid\)，则对每个\(a_i\)求出使得\(a_i \& mid=mid\)的最小代价，然后对所有代价排序取最小的k个即可。计算一个\(a_i\)的最小代价时，从高到低枚举mid为1的每一位，如果\(a_i\)的对应位也为1则跳过这一位，否则就把\(a_i\)不断+1直到这一位变成1为止。这个代价可以位运算\(O(1)\)计算。

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

点击查看代码

#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;

LL n,m,k,a[200010];

LL calc(LL need)

{

  vector <LL> v;

  rep(i,n)

  {

    LL res=0,curv=a[i];

    for(LL j=30;j>=0;--j) if((need&(1LL<<j))>0)

    {

      if((curv&(1LL<<j))>0) continue;

      LL nxt=curv|(1LL<<j);nxt&=(((1LL<<32)-1)^((1LL<<j)-1));

      res+=nxt-curv;

      curv=nxt;

    }

    v.pb(res);

  }

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

  LL ret=0;rep(i,k) ret+=v[i];

  return ret;

}

int main()

{

  cin>>n>>m>>k;

  rep(i,n) scanf("%lld",&a[i]);

  LL ans=0;

  for(LL i=30;i>=0;--i) if(calc(ans|(1LL<<i))<=m) ans|=(1LL<<i);

  cout<<ans<<endl;

  return 0;

}

C - Even XOR

又是脑筋急转弯/fn/fn/fn

考虑任意一个已经有i个元素的合法集合(没有大小为偶数的子集异或和为0)，有几种方法往里面加入一个元素，使得集合仍然合法。某一个元素加入这个集合中导致不合法，当且仅当这个集合中原有一个大小为奇数的集合，它的异或和与这个新的元素相等。观察发现原集合中任意两个大小为奇数的子集，它们的异或和一定不相等，否则这两个集合的XOR就是一个不合法的子集。所以原集合每一个大小为奇数的子集sub都唯一对应一个不能加入的数(大小为1的子集对应已经加入的，大小>1的对应未加入的)。因此，这个新的元素有\(2^n-2^{i-1}\)种选择。

接下来就可以DP了，\(dp_i\)表示i个元素的合法集合个数。

\[\begin{align}
dp_1&=2^n\\
dp_i&=\frac{dp_{i-1} \cdot (2^n-2^{i-2})}{i} (i>1)
\end{align}
\]

其中除以i是因为i个元素中的任意一个都可以作为新添加的元素，每种方案都被统计了i次。

注意到dp到n+2之后方案数就变成0了，所以时间复杂度\(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 <int,int>

#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,dp[200010];

int main()

{

  cin>>n;

  dp[1]=qpow(2,n);

  LL full=dp[1];

  for(int i=2;i<=n+2;++i) dp[i]=dp[i-1]*(full-qpow(2,i-2)+MOD)%MOD*qpow(i,MOD-2)%MOD;

  LL ans=0;repn(i,n+2) (ans+=dp[i])%=MOD;

  cout<<(ans+1)%MOD<<endl;

  return 0;

}

D - >=<

如果所有的\(x_i\)都>1，那么我们显然可以让所有变量都取1。如果有一个\(x_i=1\)，则\(a_{q_i}\)必须\(\geq y_i\)，因为\(a_{p_i}\)不能\(<x_i\)了。这启发我们，每个元素的取值范围也许都有一个上下界，如果上界<下界则无解。如果把每条限制的\(p_i\)和\(q_i\)连边且连出了环，也是不影响前一句话的结论的。上下界的限制是会传递的，如果一个元素必须小于一个值，那么另一个元素也可能会必须小于另一个值。这是由这题的独特性质决定的：如果一个元素取了一个比较小的值，他会强制另一些元素也取比较小的值，而不是比较大的值。(猜的，但确实是对的)

尝试以SPFA的方式求出每个变量的上下界。以上界为例，如果已知元素i的上界\(ub_i\)，则遍历从i连出去的每一条边\(j\)，如果\(x_j>ub_i\)，说明这条边连到的点\(q_i\)，上界至多是\(y_i-1\)(形式1)，这就相当于最短路的更新。如果\(x_j\geq ub_i\)，说明这条边连到的点\(q_i\)，上界至多是\(y_i\)(形式2)。每个变量的上界都是不断减小的，所以可以把每个点连出去的所有边按\(x_i\)从大到小排序，然后就可以用类似Dinic中的当前弧优化了，具体内容是每条以形式1访问过的边，以后都不会再访问了(形式2访问过的边以后还会以形式1访问)。

求出所有上下界后，先判无解；然后最小取值之和就是所有变量下界的和了。

时间复杂度O(能过)

点击查看代码

#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;

LL n,m,k,lb[200010],ub[200010],cur[200010];

vector <pair <pii,LL> > g[200010];

queue <LL> q;

bool inq[200010];

bool relax(LL x,LL d)

{

  if(ub[x]>d)

  {

    ub[x]=d;

    if(d<1){puts("-1");exit(0);}

    return true;

  }

  return false;

}

bool relax2(LL x,LL d)

{

  if(lb[x]<d)

  {

    lb[x]=d;

    if(d>m){puts("-1");exit(0);}

    return true;

  }

  return false;

}

int main()

{

  cin>>n>>m>>k;

  LL pp,qq,x,y;

  rep(i,k)

  {

    scanf("%lld%lld%lld%lld",&pp,&x,&qq,&y);

    g[pp].pb(mpr(mpr(x,y),qq));g[qq].pb(mpr(mpr(y,x),pp));

  }

  repn(i,n) sort(g[i].begin(),g[i].end());

  repn(i,n) lb[i]=1,ub[i]=m;

  //ub

  repn(i,n) q.push(i),inq[i]=true;

  repn(i,n) cur[i]=g[i].size();

  while(!q.empty())

  {

    int f=q.front();q.pop();inq[f]=false;

    int most=ub[f];

    while(cur[f]>0&&g[f][cur[f]-1].fi.fi>most)

    {

      --cur[f];

      if(relax(g[f][cur[f]].se,g[f][cur[f]].fi.se-1)&& !inq[g[f][cur[f]].se])

      {

        q.push(g[f][cur[f]].se);

        inq[g[f][cur[f]].se]=true;

      }

    }

    int sv=cur[f];

    while(cur[f]>0&&g[f][cur[f]-1].fi.fi==most)

    {

      --cur[f];

      if(relax(g[f][cur[f]].se,g[f][cur[f]].fi.se)&& !inq[g[f][cur[f]].se])

      {

        q.push(g[f][cur[f]].se);

        inq[g[f][cur[f]].se]=true;

      }

    }

    cur[f]=sv;

  }

  //lb

  repn(i,n) q.push(i),inq[i]=true;

  repn(i,n) cur[i]=-1;

  while(!q.empty())

  {

    int f=q.front();q.pop();inq[f]=false;

    int least=lb[f];

    while(cur[f]+1<g[f].size()&&g[f][cur[f]+1].fi.fi<least)

    {

      ++cur[f];

      if(relax2(g[f][cur[f]].se,g[f][cur[f]].fi.se+1)&& !inq[g[f][cur[f]].se])

      {

        q.push(g[f][cur[f]].se);

        inq[g[f][cur[f]].se]=true;

      }

    }

    int sv=cur[f];

    while(cur[f]+1<g[f].size()&&g[f][cur[f]+1].fi.fi==least)

    {

      ++cur[f];

      if(relax2(g[f][cur[f]].se,g[f][cur[f]].fi.se)&& !inq[g[f][cur[f]].se])

      {

        q.push(g[f][cur[f]].se);

        inq[g[f][cur[f]].se]=true;

      }

    }

    cur[f]=sv;

  }

  repn(i,n) if(lb[i]>ub[i])

  {

    puts("-1");

    return 0;

  }

  LL ans=0;

  repn(i,n) ans+=lb[i];

  cout<<ans<<endl;

  return 0;

}

巴特西

[题解] Atcoder Regular Contest ARC 146 A B C D 题解

点我看题

A - Three Cards

B - Plus and AND

C - Even XOR

D - >=<

最新文章

热门文章