Codeforces Round #481 (Div. 3) 经典几道思维题

A - AAA

POJ - 3321

给你一颗树,支持两种操作

1.修改某一节点的权值

2.查询子树的权值(子树中节点的个数)

很显然可以用树状数组/线段树维护

B - BBB

CodeForces - 978A

存一下出现次数即可

int a[100], st[1100];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        st[a[i]] += 1;
    }
    for (int i = 1; i <= 1000; ++i) if (st[i]) cnt += 1;
    cout << cnt << "\n";
    int ccnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (st[a[i]] == 1) {
            cout << a[i];
            ccnt += 1;
            if (ccnt != cnt)cout << " ";
        } else st[a[i]] -= 1;
    }
}

C - CCC

CodeForces - 978C

两种做法,写前缀和 + 二分就找到楼层序号位置

const int N = 2e5 + 10;
ll a[N], s[N];
int n, m;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i], s[i] = s[i - 1] + a[i];
    while (m--) {
        ll t; cin >> t;
        int l = 1, r = n, cnt = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (s[mid] < t) l = mid + 1, cnt = mid;
            else r = mid - 1;
        }
        cout << cnt + 1 << " " << t - s[cnt] << "\n";
    }
}

D - DDD

CodeForces - 978D

题意:
给你一组数,然后给你三种操作,分别是+1,-1,不变,然后判断能否通过操作将这组数变成等差数列,若能则输出最小改变次数,若不行则输出-1。
思路:
乍一看题,以为是DFS的题,使劲想怎么搜,后来搜超时了555。下面说正解,其实根据等差数列的性质,只需要处理前两项枚举所有可能结果,暴力找出最小次数即可。

const int N = 1e5 + 10, inf = 0x3f3f3f3f;
ll a[N], b[N];
int n;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    int cnt = inf;
    for (int i = -1; i <= 1; ++i)
        for (int j = -1; j <= 1; ++j) {
            b[0] = a[0] + i;
            b[1] = a[1] + j;
            int d = b[1] - b[0];
            bool f = false;
            int t = abs(i) + abs(j);
            for (int r = 2; r < n; ++r) {
                b[r] = b[r - 1] + d;
                if (abs(b[r] - a[r]) > 1) {f = true; break;}
                else {
                    if (b[r] != a[r]) t += 1;
                }
            }
            if (!f) cnt = min(cnt, t);
        }
    if (cnt == inf) cout << "-1\n";
    else cout << cnt << "\n";
}

E - EEE

CodeForces - 978E

题意:

给你一个含有n个整数的数组,每一个数a[i]代表汽车在站i时,车上增多了a[i]个人,如果a[i]为负,代表减少了人数。

并告诉你这个汽车的最大承载力为w个人,

请你判断初始时汽车上有多少个人,才满足整个数组的情况,。

如果某一个情况,车上的人数为负,或者人数大于w,那么说明这个数组时不合理的,。这时请输出0

思路:

可以抽象为,求这个数组的前缀和数组中的最大值和最小值,。只要最大值不大于容量,再判断下最低值的绝对值不大于容量。就可以说明是合理的。

然后可以的方案数中初始的人数一定是连续的,那么这些人数中的最大值是 \(min(w-maxsum,w)\) ,即不让过程中容量大于 \(w\) 的最大值。

最小值是 \(max(0,-1*minsum)\),然后最大值减去最小值 \(+1\) 就是答案了。

const int N = 1e3 + 10;
ll a[N], s[N];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    ll n, m; cin >> n >> m;
    ll sum = 0, Max = 0, Min = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        sum += a[i];
        Max = max(sum, Max);
        Min = min(sum, Min);
    }
    if (Min < 0) Min = llabs(Min);
    sum = m - Max - Min + 1;
    if (sum < 0) cout << 0 << "\n";
    else cout << sum << "\n";
}

F - FFF

CodeForces - 978F

题意:

给定 \(n\)​ 个人员skill值,并给出 \(k\) 个有矛盾的对,对于每个人,可以做skill值比自己小且没有矛盾人的导师。输出每一个人可做多少人的导师。

思路:

  • 排序后对每个人的skill值二分查找,存储到ans[]中。
  • 对于每个矛盾对,skill值大的ans减1即可。
const int N = 2e5 + 10;
ll a[N], b[N], c[N];
int n, m;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i], b[i] = a[i];
    while (m--) {
        int x, y;
        cin >> x >> y;
        if (a[x] > a[y]) c[x] += 1;
        else c[y] += 1;
    }
    sort(b + 1, b + 1 + n);
    for (int i = 1; i <= n; ++i) {
        int t = lower_bound(b + 1, b + 1 + n, a[i]) - b - 1;
        cout << t - c[i] << " ";
    }
}

G - GGG

CodeForces - 978G

题意:

给你N天,和M个考试,

每一个考试有三个参数。

s是考试可以开始准备的日期。

e是考试日期(这一天必须考试,不能准备)

v,这个考试需要多少天。

每一天最多只能做一件事,要么这一天休息,要么准备考试,要么参加考试。

每一个考试必须在考试之前严格的准备了v天才能通过。

请你确定你是否能能过这M个考试,

如果不可以,只需要输出-1

否则输出每一天i是做什么事情,休息是0,考试是m+1,准备是准备的那个考试编号。

思路:

贪心题,

按照每一个考试的考试日期由近到远排序。

然后枚举每一个天,1~n

如果这一天没有被使用,去检查最近1~m哪一个考试在第 i 天准备。

如果可以填就填,这样贪心搞。

const int N = 1e2 + 10;
struct node {int s, d, c, id;} p[N];
int n, m, Day[N];
bool cmp(node a, node b) {return a.d < b.d;}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> p[i].s >> p[i].d >> p[i].c;
        p[i].id = i;
        Day[p[i].d] = m + 1;
    }
    sort(p + 1, p + 1 + m, cmp);
    for (int i = 1; i <= m; ++i) {
        int day = 0;
        for (int j = p[i].s; j <= n; ++j) {
            if (Day[j] == 0) day += 1, Day[j] = p[i].id;
            if (day == p[i].c) break;
            if (j >= p[i].d) {
                cout << -1 << "\n";
                return 0;
            }
        }
    }
    for (int i = 1; i <= n; ++i) cout << Day[i] << " \n"[i == n];
}
上一篇:PCIe-8604 USB3.0图像采集卡无需额外供电机器视觉智能相机网卡


下一篇:SYN4632型PCIe时钟同步卡PCIE总线授时PCIe时钟同步卡