Codeforces Round #658 (Div. 2)

A Common Subsequence

只要找到有一个相同的元素输出即可。

AC代码：

const int N = 1010;
int a[N], b[N];
int ans;
int cnt[N];
int main()
{
  int t;
  sd(t);
  while (t--)
  {
    int n, m, k;
    bool flag = 0;
    sdd(n, m);
    mem(cnt, 0);
    rep(i, 1, n)
    {
      sd(a[i]);
      cnt[a[i]]++;
    }
    rep(i, 1, m)
    {
      sd(b[i]);
      if (cnt[b[i]])
      {
        flag = 1;
        k = 1;
        ans = b[i];
      }
    }
    if (flag)
    {
      puts("YES");
      pdd(k, ans);
    }
    else
      puts("NO");
  }
  return 0;
}

B Sequential Nim

题意：

有 个石子堆，每个石子堆有

这个博弈明显的先手必胜态，因为先手拿的话可以每次都把每堆拿剩下一个，然后下一个拿只能拿最后一个，然后到了最后一堆直接拿完。

考虑一个特殊情况那就是中间出现

这种情况那就在 这一堆拿三个，然后在 这一堆拿 个，然后后手只能拿

考虑开头连续 的个数，如果奇数个

再对全为

AC代码：

int main()
{
  int t;
  sd(t);
  while (t--)
  {
    int n, m, k;
    int cnt = 0;
    sd(n);
    rep(i, 1, n)
      sd(a[i]);
    rep(i, 1, n)
    {
      if (a[i] == 1)
        cnt++;
      else
        break;
    }
    if (cnt == n)
    {
      if (cnt & 1)
        puts("First");
      else
        puts("Second");
    }
    else
    {
      if (cnt & 1)
        puts("Second");
      else
        puts("First");
    }
  }
  return 0;
}

C Prefix Flip

题意：

一种操作，可以选择前缀长度为 ，翻转前 的 值然后顺序再倒一下。要求在 步内把给定 串变成 串。
输出任意一种方案数。

既然是任意一种那就找罪容易的一种，每一个都操作，从最后一位往前开始考虑，如果 串这个位置和 串 的第一位相同那么就把 串 的第一位个翻转一下，然后再把当前位置的前缀都翻转，这样这一位就符合了。为了降低复杂度直接记录，在原序列中跳跃是这样的 一直到 。

举个例子：

AC代码：

const int N = 1e5 + 50;
int n;
char s1[N], s2[N];
int cnt, res, pos;
vector<int> v;

int main()
{
  int t;
  sd(t);
  while (t--)
  {
    sd(n);
    ss(s1 + 1);
    ss(s2 + 1);
    v.clear();
    cnt = n;
    res = 0;
    pos = 1;
    per(i, n, 1)
    {
      //pddd(s2[i] - '0',res,(s2[i] - '0') ^ res);
      if ((s1[pos] - '0') == ((s2[i] - '0') ^ res)) //每次都翻转前缀和为 n-- 的 这个操作就是代替了翻转的操作
        v.pb(1);
      v.pb(cnt--);
      pos = n - pos + 1;//翻转后的位置.
      if (pos <= n / 2)
        pos++;
      res = 1 - res; //0,1切换
    }
    printf("%d ", v.size());
    for (auto i : v)
      printf("%d ", i);
    printf("\n");
  }
  return 0;
}

D Unmerge

题意：

给两个数组的 规则，给一个 的序列 ，问是不是两个数组 之后的结果。 这个

所以先取

取

取

取

取

取

最后取

组成序列 。

考虑第一个数 ，则向右第一个比 大的数为

对

分组以后用

AC代码：

const int N = 4e5 + 50;
int n, k, m;
int a[N];
vector<int> ans;
int dp[N];
int tmp, cnt;
int main()
{
  int t;
  sd(t);
  while (t--)
  {
    mem(dp, 0);
    ans.clear();
    sd(n);
    rep(i, 1, 2 * n)
      sd(a[i]);
    tmp = a[1];
    cnt = 1;
    rep(i, 2, 2 * n)
    {
      if (a[i] < tmp)
        cnt++;
      else if (a[i] > tmp)
      {
        ans.pb(cnt);
        cnt = 1;
        tmp = a[i];
      }
    }
    ans.pb(cnt);
    sort(ans.begin(), ans.end());
    rep(i, 0, ans.size() - 1)
    {
      per(j, n, ans[i])
        dp[j] = max(dp[j], dp[j - ans[i]] + ans[i]);
    }
    if (dp[n] == n)
      puts("YES"); //刚好装满
    else
      puts("NO");
  }
  return 0;
}