近況 && NOIP2018場外鏼題記

02-28

0x00 照例先bb幾句

最近有點忙，沒什麼時間寫文章，，，

0x01 EC-Final

打了一場ecfinal校內選拔賽，一手高精度把隊伍抬進了ecfinal

然後就聽說敝校辦賽不利，在知乎上吵得沸沸揚揚，因為這件事三天沒聽課+沒打Codeforces

一開始還覺得沒什麼，直到敝校具有ec資格的隊都沒有參加校內選拔賽，敝隊不幸空歡喜一場以後才知道各位的感覺。不過敝隊的水平參加了ecfinal估計也是鬧笑話，還是從明年的邀請賽開始打吧

0x02 「位元組跳動」冬令營網路賽

開場隊友開始推A的規律，然後我繼續看題，覺得可能F和G會比較好做（無語了。。。），看了一會兒也沒看出名堂。然後就有很多隊伍過了B，於是跟榜，發現題目是一個摺紙的問題，看了一眼樣例猜了一個逆序對的規律，交了一發WA……這個時候隊友開始做A，也錯得一塌糊塗。然後另一個隊友剪了一張紙，開始手玩B，卒。。。賽後聽說畫圖就可以發現轉化成相鄰兩個數構成的區間不能相交，然後就被我手玩掉了……

第一次爆零。。。之前老的隊名叫做「1A就回老家結婚」，英文名是「Always_Penalty」，這次比賽過後嚇得我直接改隊名了，新的名字是「Try a try, WA is OK」（試錯法）

0x03 大作業

第一個大作業很不要臉地從專欄里抽了一篇文章上去，就是置頂的那一篇（植入廣告2333）

第二個大作業既然不是Windows本也不好做什麼可視化編程，懶得配Qt的環境。想起來以前在《環球科學》上看到可以用貝葉斯方法分類郵件，於是到網上找了一份看起來還不錯的代碼學習了一下。總體思路是把訓練集和輸入讀進來，然後根據貝葉斯公式：

$egin{equation} P(B_i|A)=frac{P(B_i)P(A|B_i)}{sum_{j=1}^nP(B_j)P(A|B_j)} end{equation}$

計算概率。不過網上的代碼好像用了一點稍微不一樣的公式，還取了對數，水了過去。看高中同學的大作業都已經寫了遊戲，無限ym。以後準備看看caffe，畢竟c++只能用這個深度學習框架

發現Windows沒有dirent.h，還得自己寫……

除了這些東西，還在手玩hustoj，明天要給連fabs都用不好的人講題，害怕

0x04 NOIP2018場外鏼題記

因為敝人是敝高中信息競賽的第一屆，所以會比較關心一點，提高組我在相關問題下已經寫得比較詳細了

D1T1的話CCF：我抄我自己

#include <cstdio> #define N 100100


int n, a[N], delta[N];

int main() { // freopen("test.in", "r", stdin); scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", a + i); int ret = 0; for (int i = 1; i <= n; ++i) delta[i] = a[i] - a[i - 1]; for (int i = 1; i <= n; ++i) ret += delta[i] > 0 ? delta[i] : 0; printf("%d", ret); return 0; }

D1T2：Claris說是B站的原題，我只知道洛谷上有一個奶牛題的貨幣系統是用完全背包做的，一個學弟求了n次完全背包，其實是沒必要的。不過今年的機子快，分也挺高的……

#include <algorithm> #include <cstdio> #include <cstring> #define N 110 #define SYS_MAX 25010 using namespace std;


int T, n, a[N], sys[SYS_MAX], f[SYS_MAX];

int main() { //freopen("test.in", "r", stdin); scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", a + i); sort(a + 1, a + n + 1); memset(f, 0, sizeof(f)); memset(sys, 0, sizeof(sys)); f[a[n] + 1] = 1; int pnt = 1, ret = 0; for (int i = 1; i <= a[n] + 1; ++i) { if (i == a[pnt]) { if (!f[i]) f[i] = 1, sys[++ret] = a[pnt]; ++pnt; } if (f[i]) for (int j = 1; j <= ret; ++j) if (sys[j] + i <= a[n]) f[sys[j] + i] = 1; } printf("%d ", ret); } return 0; }

D1T3：聽Claris說又是B站原題，Orz.不會，調了半天沒調出來，占坑待補

D2T1：把環斷成鏈，然後和樹上一樣做，被卡了std::sort

#include <bits/stdc++.h> #define N 5050 using namespace std; typedef pair<int, int> pi;


inline char getc() {

    static char buf[1000000], *p1 = buf, *p2 = buf;

    return ((p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2)) ? EOF : *p1++;

}
inline void read(int& x) {

    x = 0; char c = getc();

    for (; !(c >= 0 && c <= 9); c = getc());

    for (; c >= 0 && c <= 9; x = x * 10 + c - 0, c = getc());

}
struct Edge {

    int to, nxt, no;

    Edge() {}

    Edge(const int& to, const int& nxt, const int& no) : to(to), nxt(nxt), no(no) {}

} e[N << 1];

int tot = 1, head[N];

inline void AddEdge(const int& u, const int& v, const int& no) {

    e[tot] = Edge(v, head[u], no), head[u] = tot++;

    e[tot] = Edge(u, head[v], no), head[v] = tot++;

}
int n, m, cnt, c, dfs_clock, dfn[N], low[N], bel[N], circle[N];

bool mark[N];

pi edge[N];
int st, s[N];

inline void tarjan(int u, int pre) {

    dfn[u] = low[u] = ++dfs_clock;

    s[++st] = u;

    for (int i = head[u]; i; i = e[i].nxt) {

        int v = e[i].to;

        if (v == pre) continue;

        if (!dfn[v]) {

            tarjan(v, u);

            low[u] = min(low[u], low[v]);

        } else if (!bel[v])

            low[u] = min(low[u], dfn[v]);

    }

    if (dfn[u] == low[u]) {

        ++cnt;

        for (;;) {

            int x = s[st--];

            bel[x] = cnt;

            if (x == u) break;

        }

    }

}
inline void qsort(int *a, int l, int r) {

    if (l >= r) return;

    int i = l, j = r, tmp = a[l];

    while (i < j) {

        for (; i < j && a[j] >= tmp; --j);

        if (j > i) a[i] = a[j];

        for (; i < j && a[i] <= tmp; ++i);

        if (j > i) a[j] = a[i];

    }

    a[i] = tmp;

    qsort(a, l, i - 1);

    qsort(a, i + 1, r);

}
int tp, tmp[N];

int pnt[N];

int pick[N][N];
inline void dfs(int u, int fa) {

    pnt[u] = 0, tmp[++tp] = u;

    for (int i = head[u]; i; i = e[i].nxt) {

        if (mark[e[i].no]) continue;

        if (e[i].to == fa) continue;

        pick[u][++pnt[u]] = e[i].to;

    }

    qsort(pick[u], 1, pnt[u]); // sort(pick[u] + 1, pick[u] + pnt[u] + 1);

    for (int i = 1; i <= pnt[u]; ++i)

		dfs(pick[u][i], u);

}

int ans[N]; int main() { read(n), read(m); for (int i = 1, u, v; i <= m; ++i) { read(u), read(v); AddEdge(u, v, i); edge[i] = pi(u, v); } if (m == n - 1) { dfs(1, 0); for (int i = 1; i <= n; ++i) printf("%d%c", tmp[i], i == n ? : ); return 0; } tarjan(1, 0); for (int i = 1; i <= m; ++i) { if (bel[edge[i].first] == bel[edge[i].second]) circle[++c] = i; } for (int i = 1; i <= n; ++i) ans[i] = n; int ret = 0; for (int i = 1; i <= c; ++i) { tp = 0; mark[circle[i]] = 1; dfs(1, 0); mark[circle[i]] = 0; bool flag = 0; for (int j = 1; j <= n; ++j) { if (tmp[j] == ans[j]) continue; if (tmp[j] < ans[j]) flag = 1; break; } if (flag) for (int j = 1; j <= n; ++j) ans[j] = tmp[j]; } for (int i = 1; i <= n; ++i) printf("%d%c", ans[i], i == n ? : ); return 0; } /* 1 3 4 5 2 1 */

D2T2：毒瘤計數題，沒看懂。

D2T3：有44分是「沒有上司的舞會」。一定要選的話ret += w[i], w[i] = 0;一定不選的話w[i] = INF;，然後做樹形dp。聽u裙大佬說有一個東西叫動態dp，去看了一眼確實挺板子的，還沒學，占坑待補。另外，這個題出題人的做法再次驚艷了我

普及組T2：還沒想過

普及組T3：不會捉，，，看了別人的記憶化搜索，還需要消化一段時間

普及組T4：把樹拍成一個帶權括弧序列然後做迴文串，馬拉車或者PAM都可以，還沒寫完

0x05 再bb幾句

明年就要正式開始打ACM了，加油吧。。。cf換了個新號，舊號徘徊在綠名上不去了……希望早日上橙把……我好菜啊QAQ

以及，要期末考了，我慌得一批……

大學就是p事比較多，或許我應該把文章轉移到WordPress或者什麼上，如果轉移了，應該會在專欄里通知的