反正没时间写，先把简要题解（嘴巴A题）都给他写了记录一下。
upd：任务倒是完成了，我也自闭了。
CST2018 2-1 Meteorites：
乘法版的石子合并，堆 + 高精度。
写起来有点烦貌似。
upd：由于内存问题我高精度是动态开点，同时用的是可并堆（比较简单）。
#include <cstdio>
#include <cmath>
#include <cstring> using namespace std;
typedef double lf;
typedef long long ll;
const lf pi = acos(-1.0);
const int N = ;
const int MaxLen = ;
const int MOD = ; struct BigNumber;
inline int getint();
inline void getInt(BigNumber &res); // get Big number
inline void print(ll *num, int Len); template<class T> inline void swap(T &x, T &y) {
register T tmp;
tmp = x, x = y, y = tmp;
} int n; struct Complex {
lf x, y; Complex(lf _x = , lf _y = ) : x(_x), y(_y) {
}
~Complex() {
} Complex operator +(const Complex &_c) {
return Complex(x + _c.x, y + _c.y);
}
Complex operator -(const Complex &_c) {
return Complex(x - _c.x, y - _c.y);
}
Complex operator *(const Complex &_c) {
return Complex(x * _c.x - y * _c.y, x * _c.y + y * _c.x);
}
Complex operator *(const lf &_x) {
return Complex(_x * x, _x * y);
}
Complex operator !() {
return Complex(x, -y);
}
} w[MaxLen], A[MaxLen], B[MaxLen], C[MaxLen]; struct BigNumber {
ll *x;
int len; BigNumber() {
x = new ll[];
x[] = ;
len = ;
} void destroy() {
if (x) delete[] x;
} ~BigNumber() {
destroy();
} void ChangeSize(int length) {
if (x) delete[] x;
x = new ll[length + ];
memset(x, , (length + ) * sizeof(x));
len = ;
} void zero() {
ChangeSize();
x[] = ;
len = ;
}
void one() {
ChangeSize();
x[] = ;
len = ;
} void copy(const BigNumber &_num) {
ChangeSize(_num.len);
len = _num.len;
for (int i = len; i >= ; --i)
x[i] = _num.x[i];
} inline bool operator > (const BigNumber &_num) const {
if (len > _num.len) return ;
if (len < _num.len) return ;
for (int i = len; i >= ; --i) {
if (x[i] > _num.x[i]) return ;
if (x[i] < _num.x[i]) return ;
}
return ;
} void print() {
for (int i = len; i >= ; --i)
printf(i == len ? "%lld" : "%04lld", x[i]);
puts("");
}
}; struct heap {
heap *ls, *rs;
BigNumber num;
int dep; void *operator new(size_t) {
static heap mempool[N << ], *c = mempool;
c -> ls = c -> rs = NULL;
c -> dep = ;
c -> num.zero();
return c++;
} inline void get_value(const BigNumber &_num) {
num.copy(_num);
} #define Dep(p) (p ? p -> dep : 0)
inline void update() {
dep = Dep(rs) + ;
} friend heap* merge(heap *x, heap *y) {
if (!x) return y;
if (!y) return x;
if (x -> num > y -> num) swap(x, y);
x -> rs = merge(x -> rs, y);
if (Dep(x -> rs) > Dep(x -> ls))
swap(x -> ls, x -> rs);
x -> update();
return x;
}
#undef Dep inline heap* pop() {
this -> num.ChangeSize();
return merge(ls, rs);
}
} *Root; void work(const BigNumber &a, const BigNumber &b, BigNumber &c) {
int n = a.len, m = b.len, l = a.len + b.len + ;
c.ChangeSize(l); for (int k = ; k <= l; ++k) c.x[k] = ; for (int i = ; i <= n; ++i)
for (int j = ; j <= m; ++j)
c.x[i + j] += a.x[i] * b.x[j];
for (int k = ; k < l; ++k) {
c.x[k + ] += c.x[k] / MOD;
c.x[k] %= MOD;
} while (c.x[l] == ) --l;
c.len = l;
} int main() {
BigNumber ans, tmp, a, b, c;
heap *tmp_node; n = getint();
tmp.one(); Root = new()heap;
Root -> get_value(tmp); for (int i = ; i <= n; ++i) {
getInt(tmp);
tmp_node = new()heap;
tmp_node -> get_value(tmp); Root = merge(Root, tmp_node);
} ans.one();
for (int i = ; i <= n; ++i) {
a.copy(Root -> num);
Root = Root -> pop();
b.copy(Root -> num);
Root = Root -> pop();
/*
puts("a and b:");
a.print();
b.print();
puts("---------");
*/
work(a, b, c);
/*
puts("c:");
c.print();
*/
tmp.copy(ans);
if (i != ) {
/*
puts("----");
tmp.print();
c.print();
*/
work(tmp, c, ans);
}
/*
puts("ans:");
ans.print();
*/
tmp_node = new()heap;
tmp_node -> get_value(c); Root = merge(Root, tmp_node);
}
ans.print(); return ;
} const int BUF_SIZE = ;
char buf[BUF_SIZE], *buf_s = buf, *buf_t = buf + ;
#define isdigit(x) ('0' <= x && x <= '9')
#define PTR_NEXT() { \
if (++buf_s == buf_t) \
buf_s = buf, buf_t = buf + fread(buf, , BUF_SIZE, stdin); \
} int getint() {
register int x = ;
while (!isdigit(*buf_s)) PTR_NEXT();
while (isdigit(*buf_s)) {
x = x * + *buf_s - '';
PTR_NEXT();
}
return x;
} void getInt(BigNumber &res) {
static ll num[];
static int len, Len, cnt, base;
memset(num, , sizeof(num)), len = ;
for (int i = ; i < ; ++i) num[i] = ; while (!isdigit(*buf_s)) PTR_NEXT();
while (isdigit(*buf_s) && buf_s != buf_t) {
num[len++] = *buf_s - '';
PTR_NEXT();
}
len -= ; res.ChangeSize((len + ) / - );
Len = -, cnt = ;
for (int i = len; i >= ; --i) {
cnt++;
if (cnt % == ) Len += , base = ;
res.x[Len] += base * num[i];
base *= ;
}
res.len = Len; /*
for (int i = 0; i <= len; ++i)
printf("%lld ", num[i]);
puts(""); res.print();
*/
}
CST2018 2-2 Circuit
首先是一个二进制trie + 贪心，但是由于有间隔限制，所以这个trie要支持插入和删除标记操作。
写起来并不麻烦。
upd：哪个xx卡内存。。。要把指针改成数组下标，同时把叶子和非叶子分开。
#include <cstdio>
#include <cstring> using namespace std;
typedef unsigned long long ull;
const int N = 5e5 + ;
const int SIZE = 18e6 + ;
int n, k;
int a[];
ull f[N]; struct trie_node {
int son[];
int cnt;
} trie[SIZE];
int Root;
int cnt = ; struct leaf_node {
int cnt;
int next;
} leaf[N];
int cnt_leaf = ; int get_new() {
++cnt;
trie[cnt].son[] = trie[cnt].son[] = -;
trie[cnt].cnt = ;
return cnt;
} int get_new_leaf() {
++cnt_leaf;
leaf[cnt_leaf].cnt = ;
leaf[cnt_leaf].next = -;
return cnt_leaf;
} struct Queue {
int next, value;
} q[N];
int size; void init() {
Root = get_new();
} void trie_add(int *a, int id) {
int tmp = Root;
for (int i = ; i <= ; ++i) {
trie[tmp].cnt += ;
if (trie[tmp].son[a[i]] == -) {
if (i != ) trie[tmp].son[a[i]] = get_new();
else trie[tmp].son[a[i]] = get_new_leaf();
}
tmp = trie[tmp].son[a[i]];
} //leaf
leaf[tmp].cnt += ;
int t = leaf[tmp].next;
if (t == -) {
size += ;
leaf[tmp].next = size;
q[size].next = -;
q[size].value = id;
} else {
while (q[t].next != -) t = q[t].next;
size += ;
q[t].next = size;
q[size].next = -;
q[size].value = id;
}
} void trie_delete(int *a) {
int tmp = Root;
for (int i = ; i <= ; ++i) {
trie[tmp].cnt -= ;
tmp = trie[tmp].son[a[i]];
} //leaf
leaf[tmp].cnt -= ;
leaf[tmp].next = q[leaf[tmp].next].next;
} int trie_find(int *a, int id) {
int tmp = Root;
int t;
for (int i = ; i <= ; ++i) {
if (i != ) {
t = trie[tmp].son[!a[i]];
if (t != - && trie[t].cnt != )
tmp = trie[tmp].son[!a[i]];
else
tmp = trie[tmp].son[a[i]];
} else {
t = trie[tmp].son[!a[i]];
if (t != - && leaf[t].cnt != )
tmp = trie[tmp].son[!a[i]];
else
tmp = trie[tmp].son[a[i]];
}
}
int x = leaf[tmp].next;
while (q[x].value == id) {
x = q[x].next;
}
return q[x].value;
} //--------------------------------------------------------------------
//-------------------------------------------------------------------- void split(ull x) {
memset(a, , sizeof(a));
for (int i = ; x; x >>= , --i) {
a[i] = x % ;
}
/*
for (int i = 1; i <= 64; ++i)
printf("%d", a[i]);
puts("");
*/
} void add_in_trie(int i) {
if (i < || i > n) return;
//printf("Add : %d %llu\n", i, f[i]);
split(f[i]);
trie_add(a, i);
} void delete_in_trie(int i) {
if (i < || i > n) return;
//printf("Delete : %d %llu\n", i, f[i]);
split(f[i]);
trie_delete(a);
} int get_ans(int i) {
//printf("Find : %d %llu\n", i, f[i]);
split(f[i]);
return trie_find(a, i);
} int main() {
ull x;
scanf("%d%d", &n, &k);
/*
for (int i = 1; i <= n; ++i) {
scanf("%llu", &x);
printf("%llu\n", x);
f[i] = x;
split(x);
}
*/ int L, R, nowL, nowR;
nowL = , nowR = ;
L = - k - ;
R = + k + ;
init();
for (int i = ; i <= n; ++i) {
//add in trie
while (nowR < R) {
nowR += ;
scanf("%llu", &f[nowR]);
split(f[nowR]);
add_in_trie(nowR);
}
//delete in trie
while (nowL < L) {
delete_in_trie(nowL);
nowL += ;
} //printf("%d %d %d\n", i, nowL, nowR);
printf("%d\n", get_ans(i) - ); //change the segment
L += ;
R += ;
if (L > n) L = n;
if (R > n) R = n;
} return ;
}
CST2018 2-3-1 Mooney(basic)
求一个有向图的强连通分量个数，直接tarjan就好了。
写起来 = 抄板子。
upd：没写。
CST2018 2-3-2 Mooney
两个小问题：
第一个就是求最短路，Dijkstra。
第二个先按照前一道题tarjan求强连通分量，然后对DAG树形DP。
写起来有点麻烦。
upd：第一问我写了SLF优化的spfa，应该不卡，第二问要注意有的连通分量走不到T要删掉。
#include <cstdio> using namespace std;
const int N = 5e5 + ;
const int M = 12e5 + ;
const int inf = 1e9; int n, m;
int f[N];
int tot, first[N];
int TOT, FIRST[N]; struct edge {
int next, to;
edge() {}
edge(int _n, int _t) : next(_n), to(_t) {}
} e[M], E[M]; inline void add_edge(int x, int y) {
e[++tot] = edge(first[x], y), first[x] = tot;
} int q[N], v[N], dis[N];
void spfa(int S) {
int p, x, y, l, r; for (x = ; x <= n; ++x)
dis[x] = inf; q[] = S, dis[S] = (f[S] == ), v[S] = ;
for (l = r = ; l != (r + ) % N; ) {
p = q[l], ++l %= N;
for (x = first[p]; x; x = e[x].next) {
y = e[x].to;
if (dis[p] + (f[y] == ) < dis[y]) {
dis[y] = dis[p] + (f[y] == );
if (!v[y]) {
v[y] = ;
if (dis[y] < dis[q[l]]) q[(l += N - ) %= N] = y;
else q[++r %= N] = y;
}
}
}
v[p] = ;
}
} int __main1__() {
spfa();
printf("%d\n", dis[n]);
} int low[N], dfn[N], vis[N], inq[N], s[N], w[N];
int Cnt[N], num;
int VIS[N], ans[N];
int cnt, top;
int S, T; inline int min(int x, int y) {
return x < y ? x : y;
} inline int max(int x, int y) {
return x > y ? x : y;
} void dfs(int p){
low[p] = dfn[p] = ++cnt;
vis[p] = inq[p] = ;
s[++top] = p;
int x, y;
for (x = first[p]; x; x = e[x].next)
if (!vis[(y = e[x].to)]){
dfs(y);
low[p] = min(low[p], low[y]);
}else
if (inq[y]) low[p] = min(low[p], dfn[y]);
if (low[p] == dfn[p]){
++num, y = ;
while (y != p){
inq[(y = s[top--])] = ;
w[y] = num;
if (f[y] == )
++Cnt[num];
}
}
} inline void ADD_EDGE(int x, int y) {
E[++TOT] = edge(FIRST[x], y), FIRST[x] = TOT;
} void rebuild_graph() {
int x, y;
for (int i = ; i <= n; ++i)
for (x = first[i]; x; x = e[x].next)
if (w[i] != w[(y = e[x].to)])
ADD_EDGE(w[i], w[y]);
} int tag[N]; void work(int p) {
int x, y;
ans[p] = ;
if (p == T) {
tag[p] = ;
ans[p] = Cnt[T];
return;
}
for (x = FIRST[p]; x; x = E[x].next) {
if (!VIS[y = E[x].to]) {
VIS[y] = ;
work(y);
}
if (tag[y]) tag[p] = ;
ans[p] = max(ans[p], ans[y]);
}
if (tag[p] == )
ans[p] += Cnt[p];
} int __main2__() {
for (int i = ; i <= n; ++i)
if (!vis[i])
dfs(i);
rebuild_graph(); S = w[];
T = w[n];
work(S); printf("%d\n", ans[S]);
} int main() {
int x, y;
char ch; scanf("%d%d\n", &n, &m);
for (int i = ; i <= n; ++i) {
ch = getchar();
while (ch != 'm' && ch != 'M')
ch = getchar();
if (ch == 'M') f[i] = ;
if (ch == 'm') f[i] = ;
} for (int i = ; i <= m; ++i) {
scanf("%d %d", &x, &y);
add_edge(x + , y + );
} __main1__();
__main2__(); return ;
}
CST2018 2-4 Sort
我记得好像是原题，忘了咋做了。
大概想法是归并排序的时候分析归并子序列1的前两个数和子序列2的前一个数的大小，不能证明其上界。。。
写起来不麻烦。。就是不知道对不对。
upd：自闭了，四路归并写不来。
CST2018 2-5 ChromPoly
也没有什么想法，直接dfs好像就可以了。
问题是怎么判断两张图是同构的，这样子可以大幅度剪枝，甚至在小情况的时候进行打表预处理。
然后这是个NP问题，我xxxx。
我还是决定用hash来做。。但是还是没想好怎么hash
写起来不麻烦，如果hash搞定了的话。
upd：并不是hash，有别人的代码，戳这里。写到一半自闭了，不想写了。
CST2018 2-6 Temperature
二维数组，单点修改，矩阵求和，在线算法。
好像可以写二维的树状数组，子矩阵可以通过左上角二维前缀和解决。
写起来比较简单。
upd：好像没什么好讲的，要是每道题都这么简单就好了。
#include <cstdlib>
#include "temperature.h" using namespace std;
const int N = ;
const int M = ; int sum[N][M];
int _t[N][M]; void change(int, int, int); void init(int n, int m, int **temp) {
for (int i = ; i <= n; ++i)
for (int j = ; j <= m; ++j) {
change(i, j, temp[i][j]);
_t[i][j] = temp[i][j];
}
} inline int Q(int x, int y) {
int res = ;
for (int i = x; i; i -= i&(-i))
for (int j = y; j; j -= j&(-j))
res += sum[i][j];
return res;
} int query(int x1, int y1, int x2, int y2) {
return (Q(x2, y2) - Q(x2, y1 - ) - Q(x1 - , y2) + Q(x1 - , y1 - )) / ((x2 - x1 + ) * (y2 - y1 + ));
} void change(int x, int y, int temp) {
int del = temp - _t[x][y];
_t[x][y] = temp;
for (int i = x; i < N; i += i&(-i))
for (int j = y; j < M; j += j&(-j))
sum[i][j] += del;
}
CST2018 2-7 Virus
就是求所有离0最远的1，直接bfs就好了。
写起来非常简单。
upd： 好像也没什么好讲的，但是少了5分。。。有毒。
#include <cstdio> using namespace std;
const int N = ;
const int M = ;
const int CNT = N * M; const int dx[] = {, -, , };
const int dy[] = {, , , -}; int ans;
int n, m;
int w[N][M];
int x[CNT], y[CNT];
int time[CNT], vis[CNT];
int q[CNT], l, r;
int cnt, cnt_virus; inline void _max(int &x, int y) {
if (x < y) x = y;
} inline void push_q(int x, int y, int t) {
r++;
q[r] = w[x][y];
vis[w[x][y]] = ;
time[w[x][y]] = t;
ans += t;
++cnt_virus;
} inline bool IN(int x, int y) {
return < x && x <= n && < y && y <= m;
} int main() {
char ch;
int C;
int _x, _y, __x, __y;
scanf("%d%d", &n, &m);
cnt = ;
l = , r = ;
for (int i = ; i <= n; ++i)
for (int j = ; j <= m; ++j) {
w[i][j] = ++cnt;
x[cnt] = i, y[cnt] = j; ch = getchar();
while (ch != '' && ch != '') ch = getchar();
if (ch == '') push_q(i, j, );
}
while (l <= r) {
C = q[l];
_x = x[C], _y = y[C];
for (int i = ; i < ; ++i) {
__x = _x + dx[i], __y = _y + dy[i];
if (IN(__x, __y) && !vis[w[__x][__y]])
push_q(__x, __y, time[w[_x][_y]] + );
}
++l;
}
printf("%d\n", ans);
return ;
}
CST2018 2-8 MST
求最小生成树。
ctrl c + ctrl v = AC。
20分题：1，2，3-2，4， 5， 6。
15分题：3-1， 7， 8。
吐槽：15分题和20分题真的是一个难度的吗？助教nb。