2019.4.3AK记

老师说抓基础和细节,从穷举、贪心、模拟开始练习USACO的题。于是,这次模拟赛考了2道橙题1道黄题,有四个AK的……水题好啊

T1

题干

P1209

给一些区间,进行覆盖,求最小总长度,数据量巨小

程序实现

简单的贪心,差分排序就OK了。为了骚一波还用了C语言的qsort,没用STL的std :: sort

// luogu-judger-enable-o2
//                               `-://++ooooo++//:-.`                              
//                          -/oyhyso+/:::--::::/++osyyso/-`  `-://:.               
//                      `/shs+-.                       `-+yssho///hyho. ``         
//                   :sy+-                                oh    i  `/hhshy+`      
//                 `/ho-                                   h  h  i  .s d:`/hh-     
//               :hs.                                     s   h : /   h  `:hh:    
//              `sy-                                       `o   /.o   .h    .hh-   
//             -hs`                                          +Hostker+       /dy   
//       /ssso+h+                                 +o:        +Zhujike+       `hd/  
//      ohy-`+h: `:`                               -yy/         .`   s+       +dy  
//     :do/h/h:  `hh/                               `+hy-       -h.  -h.      -dd. 
//   ohdh+sd/    .ydy.                               -ydo`      oh.  h+       hd+ 
//   :syd/yho      `oddo`  `s+`                        `odh+`    `hy` sh       sds 
//   y//ds s`        /ddh+. -yh/`                        /hdy-    /d/ od.:     +dh 
//  /d. +h/y         /dyydho-`+hh/                `.--:://oddh/    yh`+d:h`    :dd.
//  yh   `/h`      -yhh/ :sddy/-odho:.       ./oyhddhhysooooydh+   :dhod-oo    .dd-
// -ds    -d.      -d+     .+hdhsoydddho/-./ydhs+/-.        `odd/   ydhd--h.   `hd/
// +do    :d-  `:+osdhso+/:.  :sdddddddhyddddhysoo+/-.        +dh.  +hhd- ss    hd+
// od+    :d/-shhhdhhs/+ooss+   ./yddddds+::/ohdddddddhs:      +ds.`:yod` -d:   hd+
// sdo    -dhyo. oh                `-/osyys/oh+/dddddddddy--.-shhdhhhs/d.  yy   ydo
// ods  .`.dy    .h/   :oyso/`             oy` `hdddddddddy+sds.+d: +dhd+  :d:  ydo
// /dh` // hd`    +d: odhohddho`           h-   :hdddddddd:`hy .hh. +dyyy   hy  ydo
// .hd: -h od/    .hy`dd- +dddd+           :`    :hdddddd+  /: +dd:-hd-+d.  hd: yd+
//  sdy  h:-dh`    sdsdh`  +hddh`                 .hdddh/      yho/hdo -d/  hdy hd/
//  .hd: oh`yd+  `-ydsoh.   :hddo                  .++:`       -ohdhd/  hs  hyd:hd/
//   /dh`od+-dh.   sd- -s`   +ddh.                           `ohhh`sd:  oh``h+hyhd-
//   sdo+dh`ods   od:   -    /ss. `.                      `/hs`oh.hd.  :d-`d/+ddd.
//   `ydyddo sdo  :ds                     `.---`        `+hh/  odody   `h+.d/.hdd`
//     .hdddd-`yd+ `yd-               `:+shhys+ho      -ohh+`   odhd+    oy-d: sdh 
//      -hdddy /ddo -hh.              hd+:.   :h.   ./ydy/`     +ddh.    .h+d- /dy 
//       :hdhd+.hhds`sdh/`            .sh/`   `  ./ydh+-        odds      +hd. .ds 
//       /dhyh-sh+hy/dyhdy/.           `.  `-/ohdy+-           odd-       yh`  h+ 
//         odohh:hs.hhhh::+shhhysso++//+osyhyso/-`              +ds        +h   s. 
//         `yh:hhsd-`ydds     `.---::::::-.`                    :y`        .s   :  
//          -hs-hhdy  +hd/                                                         
//           .s--hdd/  `oh-      >_<
//               `sdh`   /y:     
//                 :yo    `:.            QwQ
//                   -.

#include <iostream>
#include <cstdlib>

using namespace std;

const int MAXN = 255;

int m, s, c;

int num[MAXN], cha[MAXN];

int cmp(const void *x, const void *y) {
    return *(int*)x - *(int*)y;
}

int main() {
    ios :: sync_with_stdio(false); cin.tie(NULL);
    cin >> m >> s >> c;
    for (int i = 1; i <= c; i++) cin >> num[i];
    qsort(num + 1, c, sizeof(int), cmp);
    for (int i = 2; i <= c; i++) cha[i] = num[i] - num[i - 1] - 1;
    qsort(cha + 1, c, sizeof(int), cmp);
    int ret = s;
    ret -= num[1] - 1;
    ret -= s - num[c];
    for (int i = c; i >= 1 and i >= c - m + 2; i--) ret -= cha[i];
    cout << ret << endl;
    return 0;
}

T2

题干

P1207

找出从一个数开始的$n$个在$2$到$10$进制表示下至少两种进制是回文的数,数据量巨小。

程序实现

暴力枚举即可。我用了C++的stringstreamstd :: string,转换进制和判断回文的时候码量巨小,二十分钟搞定。

// luogu-judger-enable-o2
//                               `-://++ooooo++//:-.`                              
//                          -/oyhyso+/:::--::::/++osyyso/-`  `-://:.               
//                      `/shs+-.                       `-+yssho///hyho. ``         
//                   :sy+-                                oh    i  `/hhshy+`      
//                 `/ho-                                   h  h  i  .s d:`/hh-     
//               :hs.                                     s   h : /   h  `:hh:    
//              `sy-                                       `o   /.o   .h    .hh-   
//             -hs`                                          +Hostker+       /dy   
//       /ssso+h+                                 +o:        +Zhujike+       `hd/  
//      ohy-`+h: `:`                               -yy/         .`   s+       +dy  
//     :do/h/h:  `hh/                               `+hy-       -h.  -h.      -dd. 
//   ohdh+sd/    .ydy.                               -ydo`      oh.  h+       hd+ 
//   :syd/yho      `oddo`  `s+`                        `odh+`    `hy` sh       sds 
//   y//ds s`        /ddh+. -yh/`                        /hdy-    /d/ od.:     +dh 
//  /d. +h/y         /dyydho-`+hh/                `.--:://oddh/    yh`+d:h`    :dd.
//  yh   `/h`      -yhh/ :sddy/-odho:.       ./oyhddhhysooooydh+   :dhod-oo    .dd-
// -ds    -d.      -d+     .+hdhsoydddho/-./ydhs+/-.        `odd/   ydhd--h.   `hd/
// +do    :d-  `:+osdhso+/:.  :sdddddddhyddddhysoo+/-.        +dh.  +hhd- ss    hd+
// od+    :d/-shhhdhhs/+ooss+   ./yddddds+::/ohdddddddhs:      +ds.`:yod` -d:   hd+
// sdo    -dhyo. oh                `-/osyys/oh+/dddddddddy--.-shhdhhhs/d.  yy   ydo
// ods  .`.dy    .h/   :oyso/`             oy` `hdddddddddy+sds.+d: +dhd+  :d:  ydo
// /dh` // hd`    +d: odhohddho`           h-   :hdddddddd:`hy .hh. +dyyy   hy  ydo
// .hd: -h od/    .hy`dd- +dddd+           :`    :hdddddd+  /: +dd:-hd-+d.  hd: yd+
//  sdy  h:-dh`    sdsdh`  +hddh`                 .hdddh/      yho/hdo -d/  hdy hd/
//  .hd: oh`yd+  `-ydsoh.   :hddo                  .++:`       -ohdhd/  hs  hyd:hd/
//   /dh`od+-dh.   sd- -s`   +ddh.                           `ohhh`sd:  oh``h+hyhd-
//   sdo+dh`ods   od:   -    /ss. `.                      `/hs`oh.hd.  :d-`d/+ddd.
//   `ydyddo sdo  :ds                     `.---`        `+hh/  odody   `h+.d/.hdd`
//     .hdddd-`yd+ `yd-               `:+shhys+ho      -ohh+`   odhd+    oy-d: sdh 
//      -hdddy /ddo -hh.              hd+:.   :h.   ./ydy/`     +ddh.    .h+d- /dy 
//       :hdhd+.hhds`sdh/`            .sh/`   `  ./ydh+-        odds      +hd. .ds 
//       /dhyh-sh+hy/dyhdy/.           `.  `-/ohdy+-           odd-       yh`  h+ 
//         odohh:hs.hhhh::+shhhysso++//+osyhyso/-`              +ds        +h   s. 
//         `yh:hhsd-`ydds     `.---::::::-.`                    :y`        .s   :  
//          -hs-hhdy  +hd/                                                         
//           .s--hdd/  `oh-      >_<
//               `sdh`   /y:     
//                 :yo    `:.            QwQ
//                   -.
#include <iostream>
#include <sstream>
#include <string>

using namespace std;

string Turn(int num, int jz) {
    stringstream buf;
    while (num) {
        buf << num % jz;
        num /= jz;
    }
    string ret;
    buf >> ret;
    return ret;
}

bool ChkStr(string str) {
    int len = str.size();
    for (int i = 0; i < len; i++)
        if (str[i] != str[len - i - 1]) return false;
    return true;
}

bool Check(int num) {
    int cnt = 0;
    for (int i = 2; i <= 10; i++) {
        if (ChkStr(Turn(num, i))) {
            cnt++;
            if (cnt == 2) return true;
        }
    }
    return false;
}

int main() {
    ios :: sync_with_stdio(false); cin.tie(0);
    int n, cnt = 0, s;
    cin >> n >> s;
    s++;
    while (true) {
        if (Check(s)) {
            cout << s << endl;
            cnt++;
            if (cnt == n) return 0;
        }
        s++;
    }
    return 0;
}

T3

题干

P1205

给一个矩阵和一个目标矩阵和一些变换方式,求出怎么变换可以得到目标矩阵

程序实现

第一眼大模拟。但是如果封装好的话就是小模拟了,码量--。

// luogu-judger-enable-o2
//                               `-://++ooooo++//:-.`                              
//                          -/oyhyso+/:::--::::/++osyyso/-`  `-://:.               
//                      `/shs+-.                       `-+yssho///hyho. ``         
//                   :sy+-                                oh    i  `/hhshy+`      
//                 `/ho-                                   h  h  i  .s d:`/hh-     
//               :hs.                                     s   h : /   h  `:hh:    
//              `sy-                                       `o   /.o   .h    .hh-   
//             -hs`                                          +Hostker+       /dy   
//       /ssso+h+                                 +o:        +Zhujike+       `hd/  
//      ohy-`+h: `:`                               -yy/         .`   s+       +dy  
//     :do/h/h:  `hh/                               `+hy-       -h.  -h.      -dd. 
//   ohdh+sd/    .ydy.                               -ydo`      oh.  h+       hd+ 
//   :syd/yho      `oddo`  `s+`                        `odh+`    `hy` sh       sds 
//   y//ds s`        /ddh+. -yh/`                        /hdy-    /d/ od.:     +dh 
//  /d. +h/y         /dyydho-`+hh/                `.--:://oddh/    yh`+d:h`    :dd.
//  yh   `/h`      -yhh/ :sddy/-odho:.       ./oyhddhhysooooydh+   :dhod-oo    .dd-
// -ds    -d.      -d+     .+hdhsoydddho/-./ydhs+/-.        `odd/   ydhd--h.   `hd/
// +do    :d-  `:+osdhso+/:.  :sdddddddhyddddhysoo+/-.        +dh.  +hhd- ss    hd+
// od+    :d/-shhhdhhs/+ooss+   ./yddddds+::/ohdddddddhs:      +ds.`:yod` -d:   hd+
// sdo    -dhyo. oh                `-/osyys/oh+/dddddddddy--.-shhdhhhs/d.  yy   ydo
// ods  .`.dy    .h/   :oyso/`             oy` `hdddddddddy+sds.+d: +dhd+  :d:  ydo
// /dh` // hd`    +d: odhohddho`           h-   :hdddddddd:`hy .hh. +dyyy   hy  ydo
// .hd: -h od/    .hy`dd- +dddd+           :`    :hdddddd+  /: +dd:-hd-+d.  hd: yd+
//  sdy  h:-dh`    sdsdh`  +hddh`                 .hdddh/      yho/hdo -d/  hdy hd/
//  .hd: oh`yd+  `-ydsoh.   :hddo                  .++:`       -ohdhd/  hs  hyd:hd/
//   /dh`od+-dh.   sd- -s`   +ddh.                           `ohhh`sd:  oh``h+hyhd-
//   sdo+dh`ods   od:   -    /ss. `.                      `/hs`oh.hd.  :d-`d/+ddd.
//   `ydyddo sdo  :ds                     `.---`        `+hh/  odody   `h+.d/.hdd`
//     .hdddd-`yd+ `yd-               `:+shhys+ho      -ohh+`   odhd+    oy-d: sdh 
//      -hdddy /ddo -hh.              hd+:.   :h.   ./ydy/`     +ddh.    .h+d- /dy 
//       :hdhd+.hhds`sdh/`            .sh/`   `  ./ydh+-        odds      +hd. .ds 
//       /dhyh-sh+hy/dyhdy/.           `.  `-/ohdy+-           odd-       yh`  h+ 
//         odohh:hs.hhhh::+shhhysso++//+osyhyso/-`              +ds        +h   s. 
//         `yh:hhsd-`ydds     `.---::::::-.`                    :y`        .s   :  
//          -hs-hhdy  +hd/                                                         
//           .s--hdd/  `oh-      >_<
//               `sdh`   /y:     
//                 :yo    `:.            QwQ
//                   -.
#include <iostream>
#include <cstring>

using namespace std;

struct Mat{
    char** ch; int n;

    bool operator == (const Mat &b) const {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (ch[i][j] != b.ch[i][j]) return false;
        return true;
    }

    Mat(int siz) {
        n = siz;
        ch = new char*[siz];
        for (int i = 0; i < siz; i++) ch[i] = new char[siz];
    }
};

Mat Turn(Mat m) {
    int n = m.n;
    Mat ret = Mat(n);
    ret.n = n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            ret.ch[i][j] = m.ch[n - j - 1][i];
    return ret;
}

Mat Reflect(Mat m) {
    int n = m.n;
    Mat ret = Mat(n);
    ret.n = n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            ret.ch[i][j] = m.ch[i][n - j - 1];
    return ret;
}

int main() {
    ios :: sync_with_stdio(false); cin.tie(NULL);
    int n;
    cin >> n;
    Mat bef = Mat(n), aft = Mat(n);
    bef.n = aft.n = n;
    for (int i = 0; i < n; i++) cin >> bef.ch[i];
    for (int i = 0; i < n; i++) cin >> aft.ch[i];
    if (Turn(bef) == aft) cout << 1 << endl;
    else if (Turn(Turn(bef)) == aft) cout << 2 << endl;
    else if (Turn(Turn(Turn(bef))) == aft) cout << 3 << endl;
    else if (Reflect(bef) == aft) cout << 4 << endl;
    else if (Turn(Reflect(bef)) == aft) cout << 5 << endl;
    else if (Turn(Turn(Reflect(bef))) == aft) cout << 5 << endl;
    else if (Turn(Turn(Turn(Reflect(bef)))) == aft) cout << 5 << endl;
    else if (bef == aft) cout << 6 << endl;
    else cout << 7 << endl;
    return 0;
}