2.21自我训练情况

题目：洛谷P1052，P1233，P1201。

比赛时间：2.21下午1:30~2:30。

T1

本来想DP的，结果空间不够（$O(L)$）。

写个记忆化深搜 $30$ 分走人。

  1 #include
  2 #include<string.h>
  3 #include

T2

把 L 排序后求个 W 的最长上升子序列。

好像没问题的样子。

  1 #include
  2 #include
  3 #define reg register
  4 #define ri reg int
  5 #define rep(i, x, y) for(ri i = x; i <= y; ++i)
  6 #define nrep(i, x, y) for(ri i = x; i >= y; --i)
  7 #define DEBUG 1
  8 #define ll long long
  9 #define il inline
 10 #define max(i, j) (i) > (j) ? (i) : (j)
 11 #define min(i, j) (i) < (j) ? (i) : (j)
 12 #define read(i) io.READ(i)
 13 #define print(i) io.WRITE(i)
 14 #define push(i) io.PUSH(i)
 15 struct IO {
 16     #define MAXSIZE (1 << 20)
 17     #define isdigit(x) (x >= '0' && x <= '9')
 18     char buf[MAXSIZE], *p1, *p2;
 19     char pbuf[MAXSIZE], *pp;
 20     #if DEBUG
 21     #else
 22         IO() : p1(buf), p2(buf), pp(pbuf) {}
 23         ~IO() {
 24             fwrite(pbuf, 1, pp - pbuf, stdout);
 25         }
 26     #endif
 27     inline char gc() {
 28         #if DEBUG
 29             return getchar();
 30         #endif
 31         if(p1 == p2)
 32             p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
 33         return p1 == p2 ? ' ' : *p1++;
 34     }
 35     inline bool blank(char ch) {
 36         return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
 37     }
 38     template <class T>
 39     inline void READ(T &x) {
 40         register double tmp = 1;
 41         register bool sign = 0;
 42         x = 0;
 43         register char ch = gc();
 44         for(; !isdigit(ch); ch = gc())
 45             if(ch == '-') sign = 1;
 46         for(; isdigit(ch); ch = gc())
 47             x = x * 10 + (ch - '0');
 48         if(ch == '.')
 49             for(ch = gc(); isdigit(ch); ch = gc())
 50                 tmp /= 10.0, x += tmp * (ch - '0');
 51         if(sign) x = -x;
 52     }
 53     inline void READ(char *s) {
 54         register char ch = gc();
 55         for(; blank(ch); ch = gc());
 56         for(; !blank(ch); ch = gc())
 57             *s++ = ch;
 58         *s = 0;
 59     }
 60     inline void READ(char &c) {
 61         for(c = gc(); blank(c); c = gc());
 62     }
 63     inline void PUSH(const char &c) {
 64         #if DEBUG
 65             putchar(c);
 66         #else
 67             if(pp - pbuf == MAXSIZE) {
 68                 fwrite(pbuf, 1, MAXSIZE, stdout);
 69                 pp = pbuf;
 70             }
 71             *pp++ = c;
 72         #endif
 73     }
 74     template <class T>
 75     inline void WRITE(T x) {
 76         if(x < 0) {
 77             x = -x;
 78             PUSH('-');
 79         }
 80         static T sta[35];
 81         T top = 0;
 82         do {
 83             sta[top++] = x % 10;
 84             x /= 10;
 85         }while(x);
 86         while(top)
 87             PUSH(sta[--top] + '0');
 88     }
 89     template <class T>
 90     inline void WRITE(T x, char lastChar) {
 91         WRITE(x);
 92         PUSH(lastChar);
 93     }
 94 } io;
 95 int n, f[5010];
 96 struct _{
 97     int l, w;
 98 } a[5010];
 99 bool cmp(_ a, _ b) {
100     return a.l > b.l;
101 }
102 int main() {
103     read(n);
104     rep(i, 1, n) read(a[i].l), read(a[i].w);
105     std::sort(a + 1, a + n + 1, cmp);
106     f[1] = 1;
107     rep(i, 2, n) {
108         rep(j, 1, i) 
109             if(a[i].w > a[j].w)
110                 f[i] = max(f[i], f[j] + 1);
111     }
112     print(f[n]);
113     return 0;
114 }

T3

大模拟。

用 map 写最开始挂了。

然后写了个随便卡卡的哈希。

  1 #include
  2 #include

RESULT

$ 27+20+67=114 $。

完全不发挥。