Educational Codeforces Round 100 (Rated for Div. 2)

ACM算法日常

发布于 2020-12-31 10:25:28

5190

发布于 2020-12-31 10:25:28

文章被收录于专栏：ACM算法日常

A. Dungeon

有三个数

a, b, c, (1\leq a, b, c \leq 1e8)

，你可以对这三个数进行两种操作：

1.选择一个数减一

2.当且仅当当前是第

7, 14, 21...

次操作时，你必须把三个数全部减一。

问：能不能让三个数同时变成

「思路」

很明显，我们最后一次操作必然是第二种操作，设

sum = a + b + c

，

sum

必须是

的倍数

(6次操作一，1次操作二)

，否则输出

，此外还需满足

sum / 9 \geq min(a, b, c)

, 否则会提前把一个数变成

，可参照样例的第三组数据。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 50;
int n, m;
int main(int argc, char const *argv[]) {
 int t;
 scanf("%d", &t);
 while(t--){
  int a, b, c;
  scanf("%d%d%d", &a, &b, &c);
  int x = a + b + c;
  if(x % 9 == 0){
   int mi = x / 9;
   if(a < mi || b < mi || c < mi){
    printf("NO\n");
   } else {
    printf("YES\n");
   }
  } else {
   printf("NO\n");
  }
 }
 return 0;
}

B. Find The Array

给你一个长度为

n(n\le 100000)

的序列

S = \sum_{i = 1}^{n} a_i

，现在构造一个长度为

的序列

, 使得序列

中任意两个相邻的数

x, y

，满足

(x \% y == 0 || y \% x == 0)

，

并且

\sum_{i = 1}^{n} {|a_i - b_i|} \leq 2S

。

「思路」

设

sum1

为序列

奇数位的和，

sum2

位序列

偶数位的和，如果

sum1 \leq sum2

，那么只要把

的奇数位变成

，否则偶数位变成

，然后输出

就好了。

时间复杂度

O(n)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 50;
typedef long long LL;
int n, m;
int a[maxn], b[maxn];
int main(int argc, char const *argv[]) {
 int t;
 scanf("%d", &t);
 while(t--){
  scanf("%d", &n);
  LL sum1 = 0, sum = 0;
  for(int i = 1; i <= n; i++){
   scanf("%d", &a[i]);
   if(i % 2) sum1 += a[i];
   sum += a[i];
  }
  if(sum1 * 2LL <= sum){
   for(int i = 1; i <= n; i += 2){
    a[i] = 1;
   }
  } else {
   for(int i = 2; i <= n; i += 2){
    a[i] = 1;
   }
  }
  for(int i = 1; i <= n; i++){
   printf("%d ", a[i]);
  }
  printf("\n");
 }
 return 0;
}

C. Busy Robot

有一个机器人，在时刻

处于位置

，接下来又

条命令，每条命令是在时刻

a_i

命令机器人前往

b_i

，如果在

a_i

时刻，机器人处于静止，那么他会执行这条命令，否则会继续执行前一条命令。对于每一条命令

，如果在

a_i

到

a_{i + 1}

这段时间中的某一时刻，机器人处于

b_i

，那么视这条命令执行成功，

a_{n + 1} = inf

。

「思路」

模拟题，按题意操作即可，锻炼自己代码能力。注意特判一下第

个命令就好了。

时间复杂度

O(n)

。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 50;
typedef long long LL;
int n, m;
LL a[maxn], b[maxn];
int main(int argc, char const *argv[]) {
 int t;
 scanf("%d", &t);
 while(t--){
  scanf("%d", &n);
  for(int i = 1; i <= n; i++){
   scanf("%lld%lld", &a[i], &b[i]);
  }
  LL pos = 0;
  LL to = 0;
  int ans = 0;
  for(int i = 1; i <= n; i++){
   int pre = pos;
   if(to > pos){
    pos += min(to - pos, a[i] - a[i - 1]);
   } else if(to < pos){
    pos -= min(pos - to, a[i] - a[i - 1]);
   }
   if(i > 1 && ((pre <= b[i - 1] && b[i - 1] <= pos) || (pos <= b[i - 1] && b[i - 1] <= pre))){
    ans++;
   }
   if(i == n){
    if(pos == to) ans++;
    else if(pos < to && pos <= b[n] && to >= b[n]) ans++;
    else if(pos > to && to <= b[n] && pos >= b[n]) ans++;
   }
   if(pos == to){
    to = b[i];
   }
  }
  printf("%d\n", ans);
 }
 return 0;
}

D. Pairs

有

个数

1, 2, 3, 4, 5 .... 2n

, 把这

个数分成

对，然后选

个对取这

个队的最小值，剩下

n - x

个对取最大值，构成一个

个数的集合

，现在给你一个集合

，问你有多少种

，可以构造出集合

。

「思路」

网上大部分做法是二分的写法，复杂度为

o(nlogn)

，这里介绍一种

o(n)

的写法。

很明显，通过取最小值获得的数一定是集合中最小的那

个数是最优的，通过取最大值获得的数一定是集合中最大的那

n- x

个数是最优的。

现在我们先不考虑能不能让剩下

n - x

个数能不能通过取最大值获得，设这时最大的

为

res1

，这个值可以

o(n)

得出，我们把遍历

1-2n

，如果

属于集合

，那么我们看后面剩下的非集合中的数

sum

是否有剩余，如果有那么

res1=res1+ 1

，并且未分配的数的个数

ned = ned+1

，剩下的不输入集合中的数

sum = sum - 1

，注意，这里的分配只是判断该集合中的数有没有匹配到一个大于它的非集合中的数，不需要记录匹配的数是哪个，如果

不属于集合中的数，如果

ned \geq 1

，那么

ned = ned - 1

，否则

sum = sum - 1

。

res2

表示在不考虑能不能让剩下

个数能不能通过取最小值获得的时候

n - x

的最大值，我们只要按上面的方法从倒着从

开始遍历就可以得出了，然后我们从

0-res2

枚举

n - x

，如果

n - i \leq res1

，那么方案数加一，这里其实可以推公式得出，但懒得推了 o(￣▽￣)o。

时间复杂度为

o(n)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 50;
typedef long long LL;
int n, m;
int a[maxn], vis[maxn];
int main(int argc, char const *argv[]) {
 int t;
 scanf("%d", &t);
 while(t--){
  scanf("%d", &n);
  for(int i = 1; i <= 2 * n; i++){
   vis[i] = 0;
  }
  for(int i = 1; i <= n; i++){
   scanf("%d", &a[i]);
   vis[a[i]] = 1;
  }
  int res1 = 0, res2 = 0;
  int sum = n, ned = 0;
  for(int i = 1; i <= 2 * n; i++){
   if(vis[i] == 1){
    if(sum) sum--, ned++, res1++;
    else break;
   } else {
    if(ned) ned--;
    else sum--;
   }
  }
  reverse(vis + 1, vis + 2 * n + 1);
  sum = n, ned = 0;
  for(int i = 1; i <= 2 * n; i++){
   if(vis[i] == 1){
    if(sum) sum--, ned++, res2++;
    else break;
   } else {
    if(ned) ned--;
    else sum--;
   }
  }
  int ans = 0;
  for(int i = 0; i <= res2; i++){
   if(n - i <= res1) {
    ans++;
   }
  }
  printf("%d\n", ans);
 }
 return 0;
}

E. Plan of Lectures

要求你构造一个

的排列，要满足：

a[i]

出现在

之前，如果

a[i]=0

代表这个数没有限制。仅对条件一保证一定有解。

个特殊对

(i,j)

，要求满足

在排列中一定在

的左边。

询问是否存在这样的排列。

「思路」

这场的

题简单的贪心和模拟就可以解决XD。- 假设没有特殊对，那么直接按照条件1的限制跑一次拓扑排序（条件一实际构成了一个DAG图）。- 有特殊对后，因为特殊对是要排列在一起的，所以不妨直接并查集「缩点」。将这些特殊对当做一个点再建图跑拓扑排序。然后对于每个点再按照之前在特殊对中的次序「展开」。- 那么咋判断无解的情况呢？因为原本就是一个DAG图，所以新的图中也不会出现环。那么无解就是特殊对构成的次序有环，或者特殊对的次序不满足条件一的限制。

时间复杂度为

o(nlogn)

。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 7;
int nex[maxn],fa[maxn],deg[maxn];
int cnt,pos[maxn];
vector<int>G[maxn],ans,a;
int findset(int x) {
    if(fa[x] == x) {
        return x;
    }
    return fa[x] = findset(fa[x]);
}
void Union(int x,int y) {
    int rx = findset(x),ry = findset(y);
    if(rx != ry) {
        fa[ry] = rx;
    }
}
void bfs(int x) {
    queue<int>q;
    q.push(x);
    ans.push_back(x);
    while(!q.empty()) {
        int now = q.front();q.pop();
        for(int i = 0;i < G[now].size();i++) {
            int v = G[now][i];
            deg[v]--;
            if(deg[v] == 0) {
                q.push(v);
                ans.push_back(v);
            }
        }
    }
}

int main() {
    int n,k;scanf("%d%d",&n,&k);
    int root = 0;
    for(int i = 1;i <= n;i++) {
        int x;scanf("%d",&x);
        fa[i] = i;
        if(x == 0) root = i;
        a.push_back(x);
    }
    for(int i = 1;i <= k;i++) {
        int x,y;scanf("%d%d",&x,&y);
        nex[x] = y;
        Union(x,y);
    }
    for(int i = 1;i <= n;i++) {
        int x = findset(a[i - 1]),y = findset(i);
        if(x == y) continue;
        G[x].push_back(y);
        deg[y]++;
    }
    for(int i = 1;i <= n;i++) {
        if(i == findset(i)) {
            cnt++;
        }
    }
    
    root = findset(root);
    bfs(root);
    vector<int>res;
    for(int i = 0;i < ans.size();i++) {
        int now = ans[i];
        for(int j = now;j;j = nex[j]) {
            res.push_back(j);
            if(res.size() > n) {
                printf("0\n");
                return 0;
            }
        }
    }
    for(int i = 0;i < res.size();i++) {
        pos[res[i]] = i;
    }
    for(int i = 1;i <= n;i++) {
        int x = a[i - 1],y = i;
        if(pos[x] > pos[y]) {
            printf("0\n");
            return 0;
        }
    }
    for(int i = 0;i < res.size();i++) {
        printf("%d ",res[i]);
    }
    return 0;
}