NOIp2017总结

发表于

NOIp2017 反思总结

Day0

白天看了下sh的语法和vimrc，去__debug的博客看了一些黑科技。
晚上睡的特别早。

Day1

起的比以往都早，感觉自己好勤快啊。老爸更早还买了早饭回来

T1

简直不敢相信自己的眼睛？几行完事简直不是T1风格。
考场上连公式都不信，硬要打表看看。

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
#define LL long long
using namespace std ;
int main() {
    freopen ( "math.in", "r", stdin ) ;
    freopen ( "math.out", "w", stdout ) ;
    LL a, b ;
    cin >> a >> b ;
    cout << a*b-a-b << endl ;
    return 0 ;
}

  • 最终100pt

T2

除了字符串略微恶心之外也没什么，但是我还是调了好久，主要原因还是对字符串处理不太熟练吧。
过了大样例就直接跑掉没管了，当时已经10:30了。
最终还是F语句里的数字只用了首位……
这还有90pt？？辣鸡数据
先贴考场原文件吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>
using namespace std ;
void File() {
    freopen ( "complexity.in", "r", stdin ) ;
    freopen ( "complexity.out", "w", stdout ) ;
}
const int maxm = 105 ;
int n, m, stk[maxm], top = 0 ;
char c[maxm], t[maxm], p[maxm] ;
bool vis[35] ;
int l[maxm], r[maxm], s[maxm], maxx[maxm] ;
void init() {
    top = 0 ;
    memset ( vis, 0, sizeof vis ) ;
    memset ( s, 0, sizeof s ) ;
    memset ( stk, 0, sizeof stk ) ;
    memset ( l, 0, sizeof l ) ;
    memset ( r, 0, sizeof r ) ;
    memset ( maxx, 0, sizeof maxx ) ;
}
void solve() {
    //puts("") ;
    int i ;
    bool ok = 1 ;
    scanf ( "%d %s", &m, c+1 ) ;
    for ( i = 1 ; i <= m ; i ++ ) {
        scanf ( "%s", p+1 ) ;
        if (p[1] == 'F') {
            ++top ;
            scanf ( "%s", p+1 ) ;
            if (vis[p[1]-'a']) {
                //printf ( "%d %c\n", i, p[1] ) ;
                ok = 0 ;
            }
            t[top] = p[1] ;
            vis[p[1]-'a'] = 1 ;
            scanf ( "%s", p+1 ) ;
            s[top] = 0 ;
            l[top] = r[top] = -1 ;
            if (p[1] == 'n') s[top] = -1 ;
            else l[top] = p[1]-'0' ;
            scanf ( "%s", p+1 ) ;
            if (p[1] == 'n') {
                if (s[top] == -1) s[top] = 0 ;
                else s[top] = 1 ;
            }
            else r[top] = p[1]-'0' ;
        } else {
            if (s[top] == -1) ;
            else if (s[top] > 0) {
                maxx[top-1] = max(maxx[top-1], s[top]+maxx[top]) ;
            } else if (l[top] <= r[top]) maxx[top-1] = max(maxx[top-1], maxx[top]) ;
            vis[t[top]-'a'] = 0 ;
            maxx[top] = 0 ;
            -- top ;
            if (top < 0) {
                //printf ( "%d top=%d\n", i, top ) ;
                ok = 0 ;
            }
        }
        //printf ( "top=%d s=%d maxx=%d\n", top, s[top], maxx[top] ) ;
    }
    //for ( i = 0 ; i <= m ; i ++ ) printf ( "t %d = %c\n", i, t[i] ) ;
    //for ( i = 0 ; i < 30 ; i ++ ) if (vis[i]) printf ( "%c\n", i+'a' ) ;
    if ((m&1) || ok==0 || top!=0) {
        //printf ( "m=%d ok=%d top=%d\n", m, ok, top ) ;
        puts("ERR") ;
        return ;
    }
    //for ( i = 0 ; i <= m ; i ++ ) printf ( "%d s=%d maxx=%d\n", i, s[i], maxx[i] ) ;
    int cc ;
    if (c[3] == '1') cc = 0 ;
    else {
        for ( cc = 0, i = 1 ; !isdigit(c[i]) ; i ++ ) ;
        for ( ; isdigit(c[i]) ; i ++ ) cc = cc*10 + c[i] - '0' ;
    }
    s[0] += maxx[0] ;
    //printf ( "cc=%d s=%d\n", cc, s[0] ) ;
    if (cc == s[0]) puts("Yes") ;
    else puts("No") ;
}
int main() {
    File() ;
    int _ ;
    scanf ( "%d", &_ ) ;
    while (_--) {
        init() ;
        solve() ;
    }
    return 0 ;
}

  • 最终90pt

真的辣鸡，连那里都忘记了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
using namespace std ;
void File() {
    freopen ( "complexity.in", "r", stdin ) ;
    freopen ( "complexity.out", "w", stdout ) ;
}
const int maxm = 105 ;
int n, m, stk[maxm], top = 0 ;
char c[maxm], t[maxm], p[maxm] ;
bool vis[35] ;
int l[maxm], r[maxm], s[maxm], maxx[maxm] ;
void init() {
    top = 0 ;
    memset ( vis, 0, sizeof vis ) ;
    memset ( s, 0, sizeof s ) ;
    memset ( stk, 0, sizeof stk ) ;
    memset ( l, 0, sizeof l ) ;
    memset ( r, 0, sizeof r ) ;
    memset ( maxx, 0, sizeof maxx ) ;
}
void solve() {
    int i, x, j, len ;
    bool ok = 1 ;
    scanf ( "%d %s", &m, c+1 ) ;
    for ( i = 1 ; i <= m ; i ++ ) {
        scanf ( "%s", p+1 ) ;
        if (p[1] == 'F') {
            ++top ;
            scanf ( "%s", p+1 ) ;
            if (vis[p[1]-'a']) ok = 0 ;
            t[top] = p[1] ;
            vis[p[1]-'a'] = 1 ;
            scanf ( "%s", p+1 ) ;
            s[top] = 0 ;
            l[top] = r[top] = -1 ;
            if (p[1] == 'n') s[top] = -1 ;
            else {
                len = strlen(p+1) ;
                x = p[1]-'0' ;
                for ( j = 2 ; j <= len ; j ++ ) x = 10*x + p[j] - '0' ;
                l[top] = x ;
            }
            scanf ( "%s", p+1 ) ;
            if (p[1] == 'n') {
                if (s[top] == -1) s[top] = 0 ;
                else s[top] = 1 ;
            }
            else {
                len = strlen(p+1) ;
                x = p[1]-'0' ;
                for ( j = 2 ; j <= len  ; j ++ ) x = 10*x + p[j] - '0' ;
                r[top] = x ;
            }
        } else {
            if (s[top] == -1) ;
            else if (s[top] == 1) {
                maxx[top-1] = max(maxx[top-1], 1+maxx[top]) ;
            } else if (l[top] <= r[top]) maxx[top-1] = max(maxx[top-1], maxx[top]) ;
            vis[t[top]-'a'] = 0 ;
            maxx[top] = 0 ;
            -- top ;
            if (top < 0) ok = 0 ;
        }
    }
    if ((m&1) || ok==0 || top!=0) {
        puts("ERR") ;
        return ;
    }
    int cc ;
    if (c[3] == '1') cc = 0 ;
    else {
        for ( cc = 0, i = 1 ; !isdigit(c[i]) ; i ++ ) ;
        for ( ; isdigit(c[i]) ; i ++ ) cc = cc*10 + c[i] - '0' ;
    }
    s[0] += maxx[0] ;
    if (cc == s[0]) puts("Yes") ;
    else puts("No") ;
}
int main() {
    File() ;
    int _ ;
    scanf ( "%d", &_ ) ;
    while (_--) {
        init() ;
        solve() ;
    }
    return 0 ;
}

T3

本来觉得可以打出正解的，时间有点紧，也心急了。
瞎打一通发现除了浪费时间之外就毫无意义了。
最后想骗拓扑序的分都写WA了，真的菜。
懒得贴代码了，毫无意义。

  • 最终20pt。
  • 然而现在并没有改完，留坑。

下午晚上把农药的2h限制都打完了所以晚上只能玩电脑。
颓的不行。10:30睡并没有前一天早。

Day2

起的和昨天一样早，但是并不是很精神。
吃完早饭好些了，在大巴上精力就比较充沛了。

T1

简直在逗我笑，9:20打完跑了。
但是后来发现最大数据可以爆long long，心惊胆战了几天，但是redbag告诉我ccf并没有卡掉。
简直感激

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
#define LL long long
using namespace std ;
void File() {
    freopen ( "cheese.in", "r", stdin ) ;
    freopen ( "cheese.out", "w", stdout ) ;
}
const LL maxn = 1050 ;
LL n, m, h, r ;
bool vis[maxn] ;
struct node {
    LL x, y, z ;
} s[maxn] ;
LL dist ( node a, node b ) {
    LL d = 0 ;
    d = (a.x-b.x)*(a.x-b.x) ;
    d += (a.y-b.y)*(a.y-b.y) ;
    d += (a.z-b.z)*(a.z-b.z) ;
    return d ;
}
queue <LL> Q ;
void init() {
    memset ( vis, 0, sizeof vis ) ;
    while (!Q.empty()) Q.pop() ;
}
void solve() {
    LL i, x ;
    r = r*r ;
    for ( i = 1 ; i <= n ; i ++ )
        if (s[i].z*s[i].z <= r) {
            Q.push(i) ;
            vis[i] = 1 ;
        }
    while (!Q.empty()) {
        x = Q.front() ;
        Q.pop() ;
        for ( i = 1 ; i <= n ; i ++ )
            if (vis[i] == 0&&dist(s[x], s[i]) <= 4*r) {
                Q.push(i) ;
                vis[i] = 1 ;
            }
    }
    for ( i = 1 ; i <= n ; i ++ )
        if (vis[i] && (s[i].z-h)*(s[i].z-h) <= r) {
            puts("Yes") ;
            return ;
        }
    puts("No") ;
}
int main() {
    File() ;
    LL i, _ ;
    scanf ( "%lld", &_ ) ;
    while (_--) {
        init() ;
        scanf ( "%lld%lld%lld", &n, &h, &r ) ;
        for ( i = 1 ; i <= n ; i ++ )
            scanf ( "%lld%lld%lld", &s[i].x, &s[i].y, &s[i].z ) ;
        solve() ;
    }
    return 0 ;
}

  • 最终得分100pt

T2

想了一下，发现并不会，就先打了T3的30pt暴力。然后才回来看这一题。
看了下数据范围，简直就是写着状态压缩DP。
然而发现好像还是不会。
最终弃了正解，目标改成70pt。
设 $f[x][d][S]$ 表示以点$x$为根，到赞助商距离为$d$，点集为$S$的这棵子树的最小代价。顺便记下树的边权和。
式子好推的很，枚举子树合并即可。
mmp，最后出来才发现这是正解？？？没有什么优化就交了？？？
不过还是怪自己不会枚举子集的骚操作。

先贴下考场代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
#define LL long long
using namespace std ;
void File() {
    freopen ( "treasure.in", "r", stdin ) ;
    freopen ( "treasure.out", "w", stdout ) ;
}
const LL maxn = 15, maxS = (1<<12)+5, zhf = 1e9 ;
LL n, m, g[maxn][maxn], f[maxn][maxn][maxS] ;
LL bt[maxS], v[maxn][maxn][maxS] ;
bool have ( LL s, LL x ) {
    s >>= x-1 ;
    return s&1 ;
}
LL check_min ( LL &a, LL b ) { return a = a<b? a:b ; }
int main() {
    File() ;
    LL rec, d, i, j, S, s, s1, s2, x, u ;
    scanf ( "%lld%lld", &n, &m ) ;
    S = (1<<n)-1 ;
    for ( i = 0 ; i <= n ; i ++ )
        for ( j = 0 ; j <= n ; j ++ ) {
            g[i][j] = zhf ;
            for ( s = 0 ; s <= S ; s ++ )
                f[i][j][s] = zhf ;
        }
    for ( i = 1 ; i <= m ; i ++ ) {
        scanf ( "%lld%lld%lld", &x, &u, &rec ) ;
        check_min(g[x][u], rec) ;
        g[u][x] = g[x][u] ;
    }
    bt[0] = 0 ;
    for ( i = 1 ; i <= S ; i ++ ) bt[i] = bt[i>>1]+(i&1) ;
    for ( i = 1 ; i <= n ; i ++ )
        for ( j = 0 ; j <= n ; j ++ )
            f[i][j][1<<(i-1)] = 0 ;
    int bit ;
    for ( bit = 2 ; bit <= n ; bit ++ )
        for ( s = 0 ; s <= S ; s ++ ) {
            if (bt[s] != bit) continue ;
            for ( s1 = 0 ; s1 <= S ; s1 ++ ) {
                if (bt[s1]==0 || bt[s1] >= bit) continue ;
                s2 = s^s1 ;
                if ((s1&s2)!=0 || (s1|s2)!=s) continue ;
                for ( x = 1 ; x <= n ; x ++ ) {
                    if (have(s1,x)==0) continue ;
                    for ( u = 1 ; u <= n ; u ++ ) {
                        if (have(s2,u)==0) continue ;
                        if (g[x][u] == zhf) continue ;
                        for ( d = 1 ; d <= n ; d ++ ) {
                            rec = f[x][d-1][s1] + f[u][d][s2] + d*g[x][u] ;
                            if (f[x][d-1][s] > rec) {
                                f[x][d-1][s] = rec ;
                                v[x][d-1][s] = v[x][d-1][s1] + v[u][d][s2] + g[x][u] ;
                            } else if (f[x][d-1][s] == rec) {
                                check_min(v[x][d-1][s], v[x][d-1][s1]+v[u][d][s2]+g[x][u]) ;
                            }
                        }
                    }
                }
            }
        }
    LL ans = zhf ;
    for ( i = 1 ; i <= n ; i ++ )
        check_min(ans, f[i][0][S]) ;
    printf ( "%lld\n", ans ) ;
    return 0 ;
}

  • 最终得分80pt。

然后改了一点枚举方法就行。

T3

直接模拟。懒得贴代码了。
还没改，留坑。

  • 最终得分30pt

中午聚完餐，回家睡了觉好的。
晚上嘛……
(￣▽￣)

After All

  • 最终得分420，全省排名44。
    考试的时候坑自己，两天T2煮熟的鸭子都飞了。（雾）
    考试的时候心态明显没有平常好，考前20min还在床上？（大雾）
    不过考试的时候会发挥低于正常水平也是意料之中的事情，都过去了也不要再多说了。

  • 接下来干什么？有些迷茫，先搞搞文化休息一下脑袋吧。
    现在的化学课都成了美术课了，还有翻生物、化学书就像字典？？？

  • 不打算退组，但是这个星期也不打算停课。
    不如颓颓文化，某些人说的好听点是要冲冬令营实际上不就是在逃避文化课？

  • 和猫还有赛克做了下ACM北京的同步赛，我就是去搞笑（混饭吃）的？
    代码能力奇差。

  • 准备趁这点时间把不会的东西都学了，但是绝对不能把脑袋做傻。
    换了个座位，在机房少搞颓。
    坐在fastest旁边感觉快到模糊，瞎写了几道杜教筛。
    还把redbag赶到一边去了，（然而她似乎并没有怼我

11-23:逃课搞竞赛被抓，偷鸡不成蚀把米，很不爽2333