Educational Codeforces Round 102 (Rated for Div. 2)(A-E)

目录

A. Replacing Elements

大意:

给出n个数,以及一个数d,可以对这n个数进行任意次操作,每次操作可以选互不相同的三个值i j k,然后令\(a_i=a_j+a_k\)

问能否在任意次操作后,使得每个数都小于等于d

思路:

先看是不是都小于等于d,如果都小于等于d直接输出yes

否则的话,看是否能找到两个数的和小于等于d,能找到的话就可以把大于d的数都赋值为这两个数的和

#include <bits/stdc++.h>

using namespace std;

const int N = 1e2 + 5;
typedef long long LL;
int t, a[N];
int main() {
    cin >> t;
    while (t--) {
        int n, d, flag = 0;
        cin >> n >> d;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (a[i] > d) flag = 1;
        }
        if (flag) {
            int yes = 0;
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (a[i] + a[j] <= d) yes = 1;
                }
            }
            if (yes) cout << "YES" << endl;
            else
                cout << "NO" << endl;
        } else
            cout << "YES" << \endl;
    }
    return 0;
}

B. String LCM

大意:

求两个字符串的lcm,字符串的lcm定义为能被两个字符串整除的最短字符串,若a由1一个或多个b拼接而成,那么称a能被b整除

如果找不到lcm,输出-1

思路:

直接求两个字符串长度的lcm,然后将他们都拼接到这个长度上来,最后看是否相等,相等的话就直接输出,否则没有lcm

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
int const N = 2e5 + 10;
int n, m, T;

int main() {
    cin >> T;
    string s1, s2;
    while (T--) {
        cin >> s1 >> s2;
        int l1 = s1.size();
        int l2 = s2.size();
        int len = l1 * l2 / __gcd(l1, l2);
        string ans1 = "";
        for (int i = 0; i < len/l1;i++){
            ans1 += s1;
        } 
        string ans2 = "";
        for (int i = 0; i < len/l2;i++){
            ans2 += s2;
        } 

        if (ans1 == ans2) cout << ans1 << endl;
        else
            cout << "-1" << endl;

        
    }
    return 0;
}

C. No More Inversions

大意:

给出n和k,a为一个序列:\(1, 2, 3, \dots, k - 1, k, k - 1, k - 2, \dots, k - (n - k)\)

要求求出一个1到k的全排列p,使得\(b[i] = p[a[i]]\),此时b的逆序对数量不小于a,且b的字典序最大

思路:

一顿乱搞,因为a的后面\(2(k - (n - k))+1\)个数是对称的,那么构造出来的b后面的数也是对称的,然后既要满足b的逆序对数量不小于a,又要满足b的字典序最大,所以在纸上试试发现只能是前面的数保持不变,然后后面的“V"字上下颠倒过来即可

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
typedef long long LL;
int t, n, k;
int main() {
    cin >> t;
    while (t--) {
        cin >> n >> k;
        for (int i = 1; i < (k - (n - k)); i++) {
            cout << i << ' ';
        }
        for (int i = k; i >= (k - (n - k)) ; i--) {
            cout << i << ' ';
        }
        cout << endl;
    }
    return 0;
}

D. Program

大意:

一个机器人,给出长度为n的指令,’+‘代表向前走1步,'-'代表向后退一步,初始位置为0

现在给出m个查询,每个查询给出l和r

要求问在忽略l到r这一段指令的情况下,机器人坐标的取值范围有多大

思路:

前缀后缀去做,首先求出前缀数组,那么就代表在第i步机器人的坐标为\(pre[i]\)

同时在求前缀的时候维护一个\(maxp[i]\)代表机器人在前i步,从0开始能达到的最右边的位置

维护一个\(minp[i]\)代表机器人在前i步,从0开始能达到的最左边的位置

然后求后缀,\(bk[i]\),在求后缀的时候更新\(maxb[i]\)和\(minb[i]\),分别代表从i到n这个区间,与终点的左右偏移量最大是多少

最后分别求出来起点和终点的左右偏移量,然后取个max相减即可

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;
typedef long long LL;
int t, pre[N],maxp[N],minp[N],maxb[N],minb[N],bk[N];
string s;
int main() {
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        cin >> s;
        s =" "+ s;
        maxp[0] = maxb[n + 1] = 0;  //-0x3f3f3f3f;
        minp[0] = minb[n + 1] = 0;  //0x3f3f3f3f;
        pre[0] = pre[n+1] = bk[n + 1] = bk[0] = 0;
        for (int i = 1; i <= n; i++) {
            if (s[i] == '+')
                pre[i] = pre[i - 1] + 1;
            else
                pre[i] = pre[i - 1] - 1;
            maxp[i] = max(maxp[i - 1], pre[i]);
            minp[i] = min(minp[i - 1], pre[i]);
        }
        for (int i = n; i >=0 ; i--) {
            if (s[i] == '+')
                bk[i] = bk[i + 1] + 1;
            else
                bk[i] = bk[i + 1] - 1;
            maxb[i] = max(maxb[i + 1], bk[i]);
            minb[i] = min(minb[i + 1], bk[i]);
        }
        while(m--){
            int l, r;
            cin >> l >> r;
            int max1 = maxp[l - 1], min1 = minp[l - 1];
            int mid = pre[r] - pre[l - 1];
            r++;
            int max2 = pre[n] - mid - minb[r], min2 = pre[n] - mid - maxb[r];
            //cout <<pre[n]<<' '<< max1 << ' ' << min1 << ' ' << max2 << ' ' << min2 << endl;
            cout << max(max1, max2) - min(min1, min2) + 1 << endl;
        }
    }
    return 0;
}

E. Minimum Path

大意:

定义无向图上两个点之间的距离为两点之间路径之和减去最大边权,再加上最小边权

输出1号点到其他所有点的最短距离

思路:

相当于在最短路的基础上加了两个约束条件,一个约束条件是必须有一条边的权被减去,一个约束条件是必须有一条边的权被加了一次

那么可以开三维数组:\(dis[i][f1][f2]\)代表1号点到i号点,约束条件1和2是否达到的最短路径

这样只需要将dijstra进行修改,每次更新都有四个选择:这条边作为普通的边,这条边作为最大边,这条边最为最小边,以及这条边既是最大又是最小边

证明正确性:因为全部的情况都被枚举出来,而对于一条路来说,如果必须要删掉一条边,然后加上一条边,那么一定是删掉最大边,加上最小边,所以\(dis[i][1][1]\)一定是符合条件的最小值

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
int const N = 4e5 + 10;
int e[N], ne[N], h[N], idx, n, m, st[N][2][2];
typedef long long LL;
LL dis[N][2][2], w[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a],
    h[a] = idx++;  // e代表idx连接的边,w为权,ne代表idx的上一条边,h代表a最近加入的一条边
}
struct node {
    int ver, f1, f2;
    LL dis;
    bool operator<(const node& a) const { return dis > a.dis; }
};
// 堆优化版dijkstra
void dijkstra() {
    memset(dis, 0x3f, sizeof dis);  // 初始化距离为无穷
    priority_queue<node>q;  // 定义一个按照距离从小到大排序的优先队列,第一维:距离,第二维:点
    dis[1][0][0] = 0;  // 一开始源点距离为0
    node start;
    start.dis = 0, start.ver = 1, start.f1 = start.f2 = 0;
    q.push(start);      // 把源点信息放入队列
    while (q.size()) {  // 每个点只出入队列一次
        auto t = q.top();
        q.pop();

        LL distance = t.dis;
        int ver = t.ver, f1 = t.f1, f2 = t.f2;
        if (st[ver][f1][f2])
            continue;  // 这个操作保证每个点只出入队一次,因为队列里面可能会出现{dis1[3],
                       // 3}, {dis2[3],
                       // 3}的情况,这样保证dis1[3]<dis2[3]时,3号点只进出入队一次
        st[ver][f1][f2] =1;  // 标记,因为dijkstra的贪心策略保证每个点只需要进出队一次

        for (int i = h[ver]; ~i; i = ne[i]) {  // 遍历ver的邻接点
            int j = e[i];
            if (dis[j][f1][f2] > distance + w[i]) {
                dis[j][f1][f2]  = distance + w[i];
                node ne;
                ne.dis = dis[j][f1][f2],ne.f1 = f1,ne.f2=f2,ne.ver=j;
                q.push(ne); 
            }

            if (f1 == 0) {
                if (dis[j][1][f2] > distance) {
                    dis[j][1][f2]  = distance ;
                    node ne;
                    ne.dis = dis[j][1][f2],ne.f1 = 1,ne.f2=f2,ne.ver=j;
                    q.push(ne); 
                }
            }
            if (f2 == 0) {
                if (dis[j][f1][1] > distance + 2*w[i]) {
                    dis[j][f1][1]  = distance + 2*w[i];
                    node ne;
                    ne.dis = dis[j][f1][1],ne.f1 = f1,ne.f2=1,ne.ver=j;
                    q.push(ne);  
                }
            }
            if (f1 == 0&&f2==0) {
                if (dis[j][1][1] > distance + w[i]) {
                    dis[j][1][1]  = distance + w[i];
                    node ne;
                    ne.dis = dis[j][1][1] ,ne.f1 = 1,ne.f2=1,ne.ver=j;
                    q.push(ne);  // 这里不需要判断st,因为一旦更新发现更小必须放入队列
                }
            }
        }
    }
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 1, a, b, c; i <= m; ++i) {  // 读入m条边
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }
    dijkstra();
    for (int i = 2; i <= n; i++) cout << dis[i][1][1] << ' ';
    return 0;
}
上一篇:闭包是什么?用处如何?


下一篇:【JavaScript】7-6 混合类型数据格式化输入 (5分)