noip2015_substring.cc

// Source code from laekov at noip 2015 day2 #define PRID “substring” #include #include #include using namespace std; const int maxa = 2003; const int maxb = 203; const int mod = 1e9 + 7; int n, m, l, f[2][maxb][maxb][2]; char a[maxa], b[maxb]; #define mInc(a,b) { a += b; if (a >= mod) a -= mod; } int main() { freopen(PRID “.in”, “r”, stdin); freopen(PRID “.out”, “w”, stdout); scanf("%d%d%d", &n, &m, &l); scanf("%s%s", a, b); memset(f, 0, sizeof(f)); int cur(0), prv(1); f[cur][0][0][0] = 1; for (int i = 0; i < n; ++ i) { swap(cur, prv); memset(f[cur], 0, sizeof(f[cur])); for (int j = 0; j <= m; ++ j) { for (int k = 0; k <= j && k <= l; ++ k) { if (f[prv][j][k][0]) mInc(f[cur][j][k][0], f[prv][j][k][0]); if (f[prv][j][k][1]) mInc(f[cur][j][k][0], f[prv][j][k][1]); } if (j < m && a[i] == b[j]) { for (int k = 0; k <= j && k <= l; ++ k) { if (f[prv][j][k][0] && k < l) mInc(f[cur][j + 1][k + 1][1], f[prv][j][k][0]); if (f[prv][j][k][1]) { if (k < l) mInc(f[cur][j + 1][k + 1][1], f[prv][j][k][1]); mInc(f[cur][j + 1][k][1], f[prv][j][k][1]); } } } } } printf("%d\n", (f[cur][m][l][0] + f[cur][m][l][1])% mod); }

November 17, 2015 · 1 min · laekov

noip2015 substring

水水的dp.压一维状态表示上一个字母到底有没有被用就可以算出子串数了. 然后会mle就滚一维呗.有高一小朋友不知道2333. 似乎会卡常数23333.

November 17, 2015 · 1 min · laekov

noip2015_stone.cc

// Source code from laekov at noip 2015 day2 #define PRID “stone” #include #include #include using namespace std; const int maxn = 50003; int n, m, l, a[maxn]; int checkStone(int lt) { int s(0), po(0); for (int i = 0; i < n; ++ i) if (a[i] - po >= lt) po = a[i]; else ++ s; if (l - po < lt) ++ s; return s; } int main() { freopen(PRID “....

November 17, 2015 · 1 min · laekov

noip2015 stone

水水的二分答案. 想四年前classroom还属于思考题.现在就已经沦落到开场题的地步了.oi界发展迅速啊. 然而真的不是3分钟搞定?

November 17, 2015 · 1 min · laekov

noip2015_landlords.cc

// Source code from laekov at noip 2015 day1 #define PRID “landlords” #include #include #include using namespace std; const int maxn = 17; int t, n, a[maxn], ans, c; int readCard() { int x, y; scanf("%d%d", &x, &y); if (x == 0) return 12 + y; else if (x == 1) return 11; else if (x == 2) return 12; else return x - 3; } void checkCtn(int, int, int, int);...

November 17, 2015 · 4 min · laekov

noip2015 landlords

day1考的农业题.据说可以状压然而退役的laekov已经不会写状压了(雾. 于是直接dfs就好了啊23333 每次搜索的时候强制把当前点数最小的牌出掉至少一张.这样时间复杂度/=答案!.然后就完辣.

November 17, 2015 · 1 min · laekov

noip2015_message.cc

// Source code from laekov at noip 2015 day1 #define PRID “message” #include #include #include using namespace std; const int maxn = 200003; int ans, n, t[maxn], d[maxn], v[maxn]; int walk(int po) { if (d[po]) return n; int p(po); d[p] = 1; v[p] = po; while (p) if (!d[t[p]]) { d[t[p]] = d[p] + 1; v[t[p]] = po; p = t[p]; } else if (v[t[p]] == po) return d[p] - d[t[p]] + 1; else return n; return n; }...

November 17, 2015 · 1 min · laekov

noip2015 message

依然是水水的题. 基环内向树.从任意点开走要么是o型环要么是ρ型环. 那些写bfs的是啥心态.非要展示代码能力么. 以及谁说没考数论的?这题不就是"泼辣的肉"的推广(雾.

November 17, 2015 · 1 min · laekov

noip2015_magic.cc

// Source code from laekov at noip 2015 day1 #define PRID “magic” #include #include #include using namespace std; const int maxn = 41; int n, a[maxn][maxn], px[maxn * maxn], py[maxn * maxn]; int main() { freopen(PRID “.in”, “r”, stdin); freopen(PRID “.out”, “w”, stdout); memset(a, -1, sizeof(a)); scanf("%d", &n); px[1] = 1; py[1] = (n + 1) >> 1; a[px[1]][py[1]] = 1; for (int i = 2; i <= n * n; ++ i) { if (px[i - 1] == 1 && py[i - 1] < n) px[i] = n, py[i] = py[i - 1] + 1; else if (py[i - 1] == n && px[i - 1] > 1) px[i] = px[i - 1] - 1, py[i] = 1; else if (px[i - 1] == 1 && py[i - 1] == n) px[i] = 2, py[i] = n; else if (a[px[i - 1] - 1][py[i - 1] + 1] == -1) px[i] = px[i - 1] - 1, py[i] = py[i - 1] + 1; else px[i] = px[i - 1] + 1, py[i] = py[i - 1]; a[px[i]][py[i]] = i; } for (int i = 1; i <= n; ++ i) for (int j = 1; j <= n; ++ j) printf("%d%c", a[i][j], (j == n) ?...

November 17, 2015 · 1 min · laekov

noip2015 magic

noip成绩终于出来辣可以水水地写个题解辣.假装窝还是在更新窝的网站嘛. “这么水的题还要写题解?” “对不起嘛,laekov是noi才ag弱渣嘛.” 3分钟题ovo.

November 17, 2015 · 1 min · laekov