Codeforces Round #657 (Div. 2)

A. Acacius and String

题意：

给你一个串，你可以把 换成任意字符，使得这个串最后只出现一次

暴力枚举

AC代码：

string s;
int n;
string T = "abacaba";
bool check(string &a)
{
  int cnt = 0;
  rep(i, 0, n - 7)
  {
    if (a.substr(i, 7) == T)
      cnt++;
  }
  return cnt == 1;
}
int main()
{
  int t;
  sd(t);
  while (t--)
  {
    cin >> n >> s;
    int flag = 0;
    rep(i, 0, n - 7)
    {
      string ss = s;
      bool ok = 1;
      rep(j, 0, 6)
      {
        if (ss[i + j] != T[j] && ss[i + j] != '?')
        {
          ok = 0;
          break;
        }
        ss[i + j] = T[j];
      }
      if (ok && check(ss))
      {
        rep(j, 0, n - 1)
        {
          if (ss[j] == '?')
            ss[j] = 'z';
        }
        puts("Yes");
        flag = 1;
        cout << ss << endl;
        break;
      }
    }
    if (!flag)
      puts("No");
  }
  return 0;
}

B. Dubious Cyrpto

题意;

有三个整数 。满足 还有一个整数 。 是严格大于 的正整数。题面给定 。要求出

枚举 ，

AC代码：

ll l, r, m;
 
int main()
{
  int T;
  sd(T);
  while (T--)
  {
    slddd(l, r, m);
    for (ll a = l; a <= r; ++a)
    {
      ll t = m / a;
      ll p = m % a;
      if (t > 0 && p <= r - l)
      {
        plddd(a, l + p, l);
        break;
      }
      t++;
      p = t * a - m;
      if (t > 0 && p <= r - l)
      {
        plddd(a, l, l + p);
        break;
      }
    }
  }
  return 0;
}

C. Choosing flowers

题意：

有 种花，每种花有第一次购买获得的数值与第 次购买获得的数值 ，问你买

按照 从大到小排序，如果当前 比最大的 还要打那就全选这个。否则就找到一个比当前 大最接近他的 。所有的 都比这个 大，那就全都买

AC代码：

const int N = 1e6 + 50;
struct node
{
  ll a, b;
} v[N];

bool cmp(node a, node b)
{
  return a.a > b.a;
}

ll sum[N];
int main()
{
  int t;
  sd(t);
  while (t--)
  {
    int n, m;
    sdd(n,m);
    rep(i, 1, m) 
    sdd(v[i].a,v[i].b);
    sort(v + 1, v + 1 + m, cmp);
    sum[0] = 0;
    rep(i, 1, m) 
    sum[i] = sum[i - 1] + v[i].a;
    ll res = 0;
    rep(i, 1, m)
    {
      if (v[i].b >= v[1].a)
        res = max(res, v[i].a + (n - 1) * v[i].b);
      else
      {
        int l = 1, r = m, mid, ans;
        while (l <= r)
        {
          mid = (l + r) >> 1;
          if (v[mid].a > v[i].b)
            l = mid + 1, ans = mid;
          else
            r = mid - 1;
        }
        if (ans >= n)
          res = max(res, sum[n]);
        else
        {
          ll tmp = sum[ans], nd = n - ans;
          if (i > ans)
            tmp += v[i].a, nd--;
          tmp += v[i].b * nd;
          res = max(res, tmp);
        }
      }
    }
    pld(res);
  }
  return 0;
}