Atcoder_abc277比赛记录

前言

这次还可以，有点超出我的预期。

比完不会后悔，因为自己尽了最大的努力。

比赛链接在这里

解题思路

第一题

第一题很简单，应该不用说。

#include <stdio.h>
int n, x, t;
int main()
{
  scanf("%d%d", &n, &x);
  for (int i = 1; i <= n; i++)
  {
    scanf("%d", &t);
    if (x == t)
      return printf("%d", i) & 0;
  }
  return 0;
}

第二题

第二题也很简单，但是可能会出一点小问题在题意理解和字符串hash上面。

我的hash函数是 $c1*129 + c2$ ，可以保证不重复，然后空间也不超。

#include <stdio.h>
#include <map>
int vals[20007];

bool valid1(char c)
{
  return c == 'H' || c == 'D' || c == 'C' || c == 'S';
}
bool valid2(char c)
{
  return c == 'A' || c == '2' || c == '3' || c == '4' || c == '5' || c == '6' || c == '7' || c == '8' || c == '9' || c == 'T' || c == 'J' || c == 'Q' || c == 'K';
}
bool valid3(char c1, char c2)
{
  if (vals[c1 * 129 + c2])
    return false;
  else
  {
    vals[c1 * 129 + c2] = 1;
    return true;
  }
}
bool validd(char c1, char c2)
{
  return valid1(c1) && valid2(c2) && valid3(c1, c2);
}

int n, vfl;
char c1, c2;
int main()
{
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
  {
    do
    {
      c1 = getchar();
    } while (c1 == ' ' || c1 == '\n' || c1 == '\r');
    do
    {
      c2 = getchar();
    } while (c2 == ' ' || c2 == '\n' || c2 == '\r');
    if (vfl == 0 && validd(c1, c2) == false)
      vfl = 1;
  }
  puts(vfl ? "No" : "Yes");
  return 0;
}

第三题

题意简述

有一座高为 $10^9$ 层的楼和很多层，你现在在第一层，上下只能靠传送门。

有 $n$ 个双向传送门连接 $a_i$ 和 $a_j$，求你最高可以到达的楼层。

解题思路

首先想到了并查集，但是要判断最高楼层的复杂度非常高 ($10^9$左右)，所以这种解法不可行。

然后就是老老实实写广搜。

但是！！！先别急！！！仔细看看数据范围，有这样一句话：

$1 \le a_i,b_i \le 10^9$

数组可以开 $10^9$ 吗？显然是不行的，所以要先写离散化。

std::map<int, int> lsh;
int lsh_rev[maxn];
inline int lis(int num) // 将数字离散化
{
  if (lsh[num])
    return lsh[num]; // 找得到就返回
  lsh[num] = ++cnt; // 找不到就加上
  lsh_rev[cnt] = num;
  return cnt;
}
inline int grevlis(int cnt)
{
  return lsh_rev[cnt]; // 根据离散化索引查值
}

完整代码在这里

#include <stdio.h>
#include <vector>
#include <queue>
#include <map>
#define maxn 400007

std::map<int, int> lsh;
int lsh_rev[maxn], vis[maxn];
int cnt = 0;

std::vector<int> edge[maxn];
std::queue<int> qu;

int n, u, uval, v, mx = 1;
inline int maxx(int a, int b)
{
  return a > b ? a : b;
}

inline int lis(int num)
{
  if (lsh[num])
    return lsh[num];
  lsh[num] = ++cnt;
  lsh_rev[cnt] = num;
  return cnt;
}

inline int grevlis(int cnt)
{
  return lsh_rev[cnt];
}

int main()
{
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
    scanf("%d%d", &u, &v),
        u = lis(u), v = lis(v),
        edge[u].push_back(v),
        edge[v].push_back(u);

  qu.push(lis(1));
  while (!qu.empty())
  {
    u = qu.front();
    uval = grevlis(u);
    qu.pop();

    if (vis[u])
      continue;
    vis[u] = 1;

    mx = maxx(mx, uval);
    for (auto s : edge[u])
      qu.push(s);
  }
  printf("%d", mx);
  return 0;
}

第四题

乍一看可能没什么思路，后来选择了类似贪心的解法，把序列先排序一遍，然后把可以连续选择的每一组合并起来，然后从头到尾扫一遍取max，用总和减去max就解决了。

有一个特殊情况就是当第一个值为 $0$，最后一个值为 $m-1$ 的时候应该删去最后一个块，把它的值加到第一个块里面。

复杂度 $O(n\logn)$。

#include <stdio.h>
#include <algorithm>
typedef unsigned long long ull;
#define maxn 400007
ull arr[maxn], arrsum[maxn], cnt, n, m, t, summ, maxx;

ull gmx(ull x, ull y){return x > y ? x : y;}

signed main()
{
  scanf("%llu%llu", &n, &m);

  if (n == 1)
    return puts("0") & 0;

  for (ull i = 1; i <= n; i++)
    scanf("%llu", &t),arr[i] = t,summ += t;

  std::sort(arr + 1, arr + n + 1);

  for (ull i = 1; i <= n; i++)
  {
    if (arr[i] - arr[i - 1] > 1)
      cnt++;
    arrsum[cnt] += arr[i];
  }

  if (arr[n] == m - 1 && arr[1] == 0 && cnt > 0)
    arrsum[0] += arrsum[cnt], cnt--;

  for (ull i = 0; i <= cnt; i++)
    maxx = gmx(arrsum[i], maxx);

  printf("%llu", summ - maxx);
  return 0;
}

第五题

这道题我想到思路的那一瞬间，最想说的一个字就是：妙！

我们这样想：把时间作为我们主要考虑的因素，唯一可能的操作有这些：

1. 移动到旁边的节点，时间为 $1$ 。
2. 按按钮，时间为 $0$ 。

再次思考：边的权值只有两种，按钮可以多次按（但是肯定没意义）。

之前第一感觉是并查集，但是后面没想到代码怎么写。

后来就想到了建两个图，一个图存权值为1的边，一个图存权值为0的边，然后按钮连接两个图。

比如对于样例数据：

5 5 2
1 3 0
2 3 1
5 4 1
2 1 1
1 4 0
3 4

构建出来的图应该长这样（源点汇点编号已省略）：

这样完了跑一遍最短路就解决。

#include <stdio.h>
#include <queue>
#include <vector>
#include <memory.h>

const int maxn = 6e5 + 7;

struct Node
{
  int id, val;
};

bool operator<(Node a, Node b)
{
  return a.val > b.val;
}

inline int min(int a, int b)
{
  return a < b ? a : b;
}

std::vector<std::pair<int, int>> edge[maxn];
std::priority_queue<Node> q;

int n, m, s, u, v, w, tmp, k;
int dis[maxn], vis[maxn];

int end;

int main()
{
  scanf("%d%d%d", &n, &m, &k);
  s = n * 2 + 1;
  for (int i = 1; i <= m; i++)
  {
    scanf("%d%d%d", &u, &v, &w);
    if (w)
      edge[u].push_back({v, 1}),
          edge[v].push_back({u, 1});
    else
      edge[u + n].push_back({v + n, 1}),
          edge[v + n].push_back({u + n, 1});
  }
  for (int i = 1; i <= k; i++)
    scanf("%d", &tmp),
        edge[tmp].push_back({tmp + n, 0}),
        edge[tmp + n].push_back({tmp, 0});

  edge[s].push_back({1, 0});

  edge[n].push_back({n * 2 + 2, 0});
  edge[n * 2].push_back({n * 2 + 2, 0});

  memset(dis, 0x3f, sizeof(dis));

  dis[s] = 0;
  q.push({s, 0});

  while (!q.empty())
  {
    Node top = q.top();
    q.pop();
    if (vis[top.id])
      continue;
    vis[top.id] = 1;
    for (auto t : edge[top.id])
    {
      if (dis[t.first] > dis[top.id] + t.second)
      {
        dis[t.first] = dis[top.id] + t.second;
        q.push({t.first, dis[t.first]});
      }
    }
  }

  if (dis[n * 2 + 2] == 1061109567)
    printf("-1");
  else
    printf("%d ", dis[n * 2 + 2]);
}

第六题

脑抽了考场上没策略，但是下来想到了。

表述不太清楚，但是思路是这样。

可以发现，无论如何交换，原先每行每列中的元素不变，那么就以这个为约束条件建图进行拓扑排序就行。