7.17-白红宇

7.17

阅读量：5291 次

发布时间：2019-06-14

本文共 4688 字，大约阅读时间需要 15 分钟。

今天是第二天了，测评姬出了些毛病，今天的rating不算，有喜有悲吧

明天加油！

A：Adjacent Replacements

题解：奇数位置上的数不变，偶数位置上的数-1；

#include
    
     #include
     
      using namespace std;int a[1000 + 6];int main() {    int n;    scanf("%d", &n);    for (int i = 0; i < n; i++) {        scanf("%d", &a[i]);    }    if (a[0] % 2 == 0)printf("%d", a[0] - 1);    else printf("%d", a[0]);    for (int i = 1; i < n; i++) {        if (a[i] % 2 == 0)printf(" %d", a[i] - 1);        else printf(" %d", a[i]);    }    return 0;}

B：Polycarp’s Practice

题意：将一个序列分成n份，要求这n份中最大数的和最大

解法：由于分法不限制，所以我们将每个最大的数放到区间的右边，如果最右边的最大数不在序列最右边，就把它移过去

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;typedef pair
        
          pii;vector
         
          vi;int vis[10005], n, k, tmp, ans = 0;vector
          
           vp;priority_queue

, less

> q;bool cmp(pii a, pii b) { return a.second < b.second; }int find(int tmp) { for (int i = 0; i < n; i++) if (vi[i] == tmp&&vis[i] == 0) { vis[i] = 1; return i; }}int main() { scanf("%d%d", &n, &k); for (int i = 0; i < n; i++) { scanf("%d", &tmp); vi.push_back(tmp); q.push(tmp); } for (int i = 0; i < k; i++) { tmp = q.top(); q.pop(); int len = find(tmp); vp.push_back(make_pair(tmp, len)); ans += tmp; } sort(vp.begin(), vp.end(), cmp); if (vp[vp.size() - 1].second != n - 1)vp[vp.size() - 1].second = n - 1; printf("%d\n%d", ans, vp[0].second + 1); for (int i = 1; i < vp.size(); i++) { printf(" %d", vp[i].second - vp[i - 1].second); } return 0;}

C：Three Parts of the Array

题意：将一个序列分成三份，每份序列可以为空，要求最左边的序列的和等于最右边的序列的和，问最大的和为多少？

解法：meet—in—middle，从两边同时开始搜索，循环条件是两个指针的差>1，注意当序列长度小于2的时候（即只为1）的时候和是0

#include
    
     #include
     
      using namespace std;typedef long long ll;ll d[200000 + 5];int main() {    int n;    scanf("%d", &n);    for (int i = 0; i < n; i++) {        scanf("%d", &d[i]);    }    int i = 0, j = n - 1;    ll sum1 = d[0], sum3 = d[n - 1], fsum = 0;    while (j - i > 1) {        if (sum1 > sum3) { j--; sum3 += d[j]; }        else if (sum1 < sum3) { i++; sum1 += d[i]; }        else {            fsum = sum1;            if (j - i == 1)break;            else { i++; sum1 += d[i]; }        }    }    if (sum1 == sum3)fsum = sum1;    if (n < 2)fsum = 0;    printf("%I64d", fsum);    return 0;}

D：Two Strings Swaps

题意：两个字符串，三种交换方式：

1：交换a[i]和b[i]，2：交换a[i]和a[n-i+1]，3：交换b[i]和b[n-i+1]

在交换前可以将a中的任意一个字母替换成另外一个任意字母，之后可以随意使用上述变换，最终结果要求两个字符串相等，求最小替换次数（上述所有操作只针对第一串）

解法：

首先，如果位置为i的字符不用替换，那么两种串的分布有三种情况；在这种情况下，如果6个条件满足任意一个，就只能是一个字母需要替换，否则就得替换两个字母，非常好的题！

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;string s1, s2;int main() {    int n, ans = 0;    scanf("%d", &n);    cin >> s1 >> s2;    for (int l = 0; l < n/2; l++) {        int r = n - l - 1;        if ((s1[l] == s2[l] && s1[r] == s2[r]) || (s1[l] == s1[r] && s2[l] == s2[r]) || (s1[l] == s2[r] && s1[r] == s2[l]))            ans += 0;        else if ((s1[l] == s2[l] || s1[r] == s2[r]) || (s1[l] == s2[r] || s2[l] == s2[r]) || (s1[l] == s2[r] || s1[r] == s2[l]))            ans += 1;        else ans += 2;    }    if (n % 2 == 1 && s1[n / 2] != s2[n / 2])ans++;    cout << ans;    return 0;}

Fabled Rooks

题意：一个棋盘，横纵分成不同的几个区间，要求每个区间必须有一个棋子，不同棋子不能重叠，横纵坐标不能相同，输出每个棋子的坐标

解法：首先横坐标和纵坐标其实没关系，直接分开看；接下来以横坐标为例，将所有的区间先按右边界从小到大排序，相等的话就按左边界从大到小排序，之后从每个区间最左边搜，如果最后大于等于右边界就无解，输出IMPOSSIBLE

贪心的思路，直接dfs搜不过去

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;int vis[100000 + 5], n;const int maxn = 1e5 + 5;struct node {    int l, r, num;    bool operator < (const node &rhs){        //区间右端点越小，优先级越高；同等情况下，左端点越大优先级越高        //这种情况下，如果我们先取最右边的，则小区间必定满足，此时大区间被满足的几率也较大，因此不可以，所以我们从左边往右边取        return r < rhs.r || (r == rhs.r&&l > rhs.l);    }}x[maxn], y[maxn];int slove(int *a,node* q) {    memset(a, 0, sizeof(a));    memset(vis, 0, sizeof(vis));    for (int i = 0; i < n; i++) {        for (int j = q[i].l; j <= q[i].r; j++) {            if (!vis[j]) {                a[q[i].num] = j; vis[j] = 1;                break;            }            if (j >= q[i].r)return 0;        }    }    return 1;}int main() {    int a[maxn], b[maxn];    while (cin >> n && n)    {        for (int i = 0; i < n; ++i)        {            scanf("%d%d%d%d", &x[i].l, &y[i].l, &x[i].r, &y[i].r);            x[i].num = y[i].num = i;        }        sort(x, x + n); sort(y, y + n);        if (slove(a, x) && slove(b, y))        {            for (int i = 0; i < n; ++i)                printf("%d %d\n", a[i], b[i]);        }        else        {            printf("IMPOSSIBLE\n");        }    }    return 0;}

转载于:https://www.cnblogs.com/romaLzhih/p/9489809.html

你可能感兴趣的文章