The 2018 ACM-ICPC Asia Qingdao Regional Contest

第三场集训

C - Flippy Sequence

题意：

现在你有两个长度为$n$的二进制序列$a,b$，现有一操作，你可以任意选择一长度不为零的区间，然后翻转其中的数即$0$变$1$，$1$变$0$，你必须进行两次操作，两次操作的区间不同的话视作不同的操作，操作完后$a,b$要相等，问总共的操作方案数是多少，若无则输出。

题解：

我们可以从有多少个连续的$a,b$不相同的区间入手，首先显然当区间数超过$3$个的时候答案为$0$。

$Case\ 1$：零个

答案很显然是$\frac{(n+1)\times n}{2}$

$Case\ 2$：一个

我们设这个区间自身的长度为$l_1$，左边的长度为$l_2$，右边的长度为$l_3$，则答案为$(l_2+l_3)\times 2+(l_1-1)\times 2$。

$Case\ 3$：两个

我们发现不管怎样我们都必须让$l1,l2$区间同时包括在一个操作数里面，则我们有以下$6$种方案，（1）$l_1$到$l_2$然后$l_1,l_2$中间的区间，反过来也算一种。（2）$l_1,l_2$分别各自翻转，有两种。（3）$l_1$和$l_1,l_2$之间的区间然后$l_2$和$l_1,l_2$之间的区间，反过来也算一种。

AC代码：

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define _for(i,a,b) for(int i = a;i < b;++i)
#define endl '\n'
using namespace std;


signed main() {
  FIO;
  int T;cin>>T;
  while(T--){
    int n;cin>>n;
    string a,b;cin>>a>>b;
    int cnt=0;
    int f=0;
    for(int i = 0;i < n;++i){
      if(b[i]!=a[i]&&!f)++cnt,f=1;
      if(a[i]==b[i])f=0;
    }
    if(!cnt)cout<<1ll*n*(n+1)/2;
    if(cnt==1){
      int i,j;
      for(i=0;i<n;++i)if(a[i]!=b[i])break;
      for(j=n-1;j>=0;--j)if(a[j]!=b[j])break;
      cout<<(i+n-j-1)*2+2*(j-i);
    }
    if(cnt==2)cout<<6;
    if(cnt>=3)cout<<0;
    cout<<'\n';
  }
  return 0;
}

E - Plants vs. Zombies

题意：

现在你有$n$种植物编号从$1\sim n$，每种植物都有一个值，现在你有一个浇水机器从$0$出发，初始的时候所有位置的值为$0$，你的浇水机器每经过一种植物，该处的值加上这种植物的值，现你的机器最多能走$k$步，它可以到$0$的位置，也可以到$n+1$的位置，现定义你植物的防御值为所有位置上的值的最小值，你要做的就是让这个最小值最大。

题解：

诶，让最小值最大，很明显的一个二分的题了，二分的策略就是。定义一个数组$d$，$d$每个位置上的值就是你$check$的最小值处于这个位置的植物的值，然后因为是你的机器来回走，则要同时考虑你当前格和下一格，若$check$为$true$则更新左端点，否则更新右端点，单次询问的时间复杂度为$O(nlog1e18)$。

AC代码：

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
using namespace std;
typedef long long ll;


int a[100005];
ll d[100005];
ll n,k;
int check(ll x){
  ll m=k;
  for(int i = 1;i < n+1;++i)d[i]=x/a[i]+(x%a[i]!=0);
  for(int i = 1;i < n+1;++i){
    if(d[i]>0){
      if(m>=2*d[i]-1)m-=2*d[i]-1,d[i+1]-=d[i]-1,d[i]=0;
      else break;
    }else if(m>0)m--;
    else break;
  }
  int f=1;
  for(int i = 1;i < n+1;++i){
    if(d[i]>0){
      f=0;
      break;
    }
  }
  return f;
}
signed main() {
  FIO;
  int T;cin>>T;
  while(T--){
    cin>>n>>k;
    for(int i = 1;i < n+1;++i)cin>>a[i];
    ll l = 0,r=1e18;
    while(l<=r){
      ll mid=(l+r)/2;
      if(check(mid))l=mid+1;
      else r=mid-1;
    }
    cout<<r<<'\n';
  }
  return 0;
}

M - Function and Function

题意：

现有以下对应表格：

$x$	$z(x)$	$x$	$z(x)$
0	1	5	0
1	0	6	1
2	0	7	0
3	0	8	2
4	1	9	1

定义$f(x)=\sum^{x的位数}_{i=x的每一位}z(i)$，有：

$$\left\{\begin{array}{} g^0(x)=x \\ g^k(x)=f(g^{k-1}(x))&if\ k\ge1 \end{array} \right.$$

现给你$x$和$k$，要你求$g^k(x)$。

题解：

不难发现$g^2(x)=f(f(x))$，$g^3(x)=f(f(f(x)))$，$g^k(x)=f(f(f(\dots f()\dots )))$

然后我们可以看出，若$k$足够大，则最后答案就是$1/0$，否则就模拟一遍就行，数据范围很小，时间复杂度为$O(1)$。

AC代码：

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
using namespace std;
typedef long long ll;


signed main() {
  FIO;
  int a[10]={1,0,0,0,1,0,1,0,2,1};
  int T;cin>>T;
  while(T--){
    int n,k;cin>>n>>k;
    while(n!=1&&n!=0&&k>0){
      int t=0;
      while(n>0){
        t+=a[n%10];
        n/=10;
      }
      n=t,--k;
    }
    if(k<0)cout<<n;
    else if(k==0)cout<<n;
    else{
      if(n==1)cout<<(k%2?0:1);
      else if(!n)cout<<(k%2?1:0);
    }
    cout<<endl;
  }
  return 0;
}

• 本文作者： baddog
• 本文链接： https://katoli.github.io/2020/09/29/The-2018-ACM-ICPC-Asia-Qingdao-Regional-Contest/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！