Brief description:
Problem A. najboljih
…
Problem B. okret
问迷宫是否有死路。
Problem C. zadaca
问两个巨大整数的 gcd 的后 9 位数字，巨大整数用 N 个 integer 的乘积表示。
( .. .N <= 1,000 .. .)
Problem D. kompici
问 N 个数可以组成多少对 pair， pair 定义位有至少一个相同的 digit 。。
( .. N <= 1,000,000 ..)
Problem E. funkcija
有一定程度依赖的 for 循环计数问题... .
Problem F. raspored
。。。
Analysis:
(前略。。)
Problem E. funkcija
E 是一道很值得进一步思考的问题。。
首先。。像是这样的一组 Input 。。
Input:
3
2 3
1 a
b a
Output:
9
（题目里要求说。。Xi, Yi 不可以同时为字母。。但是去除这个限制。也是一个 will defined 的问题。。但似乎就不解了。。）
。。。于是依赖关系形成有根树森林（有多个左孩子和右孩子的“二叉树”。。）
。。之后迎刃照做就可以了。。（利用部分和进行状态转移。。具体做法也可以参考这里。。）
Problem F. raspored
。F 首先第一问可以通过排序后贪心的方法得到。。原理参照排序不等式。。
。。以下假定读者默认排序不等式的正确性。。
于是处理第二问。。发现修改过程。。。需要的是一种支持 O(1) 插入、O(1) 删除 和 二分查找的数据结构。。
进一步分析可以将题目中所说的两种代价分离。。第一个可以直接 O(1) 维护。。第二个将所有的需求时间插入到一颗平衡树中动态维护。。。
需要额外添加一些域。。
1. sz[] 用以维护子树的规模
2. ss[] 维护子树的关键字权和。
3. cost[] 维护子树所引起的代价。。
因为需要 sz[] 域所以考虑用 sbt 实现平衡树。。。于是这道题的真正核心是：
cost[x] = cost[lx] + cost[rx] + LL(ss[lx] + key[x]) * (sz[rx] + 1) 。。。
…
...
int A[8], O[8];
bool comp(int a, int b){
return A[a] > A[b];
}
int main(){
REP(i, 8) RD(A[i]), O[i] = i;
sort(O, O+8, comp);
int s = 0; REP(i, 5) s += A[O[i]];
cout << s << endl;
REP(i, 8) A[O[i]] = i;
s = 5; REP(i, 8) if (A[i] < 5){
if (--s) cout << i + 1 << " ";
else cout << i + 1 << endl;
}
}
.. .
const int N = 11;
bool Map[N][N];
int n, m;
int main(){
//freopen("in.txt", "r", stdin);
RD(n, m); char t; REP_2(i, j, n, m){
RC(t); if (t == '.') Map[i][j] = true;
else Map[i][j] = false;
}
int Dead = 0; REP_2(x, y, n, m) if (Map[x][y]){
int cnt = 0; REP(ii, 4){
int xx = x + dx[ii], yy = y + dy[ii];
if (xx < 0 || yy < 0 || xx >= n || yy >= m) continue;
if (Map[xx][yy]) ++cnt;
}
if (cnt == 1) Dead = 1;
}
cout << Dead << endl;
}
.. .
template<class T> inline void OT(const T &x){
if (flag) REP(i, 9 - log(D) / log(10)) putchar('0');
printf("%d\n", x);
}
inline void MUL(int &a, int b){
LL t = (LL)a * b; if (t > MOD) flag = true;
a = t % MOD;
}
const int N = 1009;
int D, a[N], b[N]; bool flag = false;
int n, m;
int main(){
//freopen("in.txt", "r", stdin);
D = 1; REP_C(i, _RD(n)) RD(a[i]); REP_C(i, _RD(m)) RD(b[i]);
int d; REP_2(i, j, n, m){
d = __gcd(a[i], b[j]);
a[i] /= d, b[j] /= d, MUL(D, d);
}
OT(D);
}
LL A[1024]; int mask;
LL res, t;
LL Cn2(LL x){
return x * (x - 1) / 2;
}
int main(){
//freopen("in.txt", "r", stdin);
Rush {
for (mask = 0,RD(t); t; t /= 10) mask |= _1(t % 10);
++A[mask];
}
FOR(s, 1, 1024) {
res += Cn2(A[s]);
FOR(t, s+1, 1024) if (s&t)
res += A[s] * A[t];
}
OT(res);
}
.. .
const int N = 26, C = 100000, CC = C + 9;
VI lc[N], rc[N]; int s[N][CC], ls[N][CC], rs[N][CC], l[N], r[N]; bool root[N];
string buff; int res, n;
int stoi(const string &s){
int res = 0; REP(i, SZ(s)){
res *= 10, res += s[i] - '0';
}
return res;
}
void stat(int x){
REP_1(i, C) ls[x][i] = sum(ls[x][i-1], s[x][i]);
DWN_1(i, C, 1) rs[x][i] = sum(rs[x][i+1], s[x][i]);
}
int main(){
//freopen("in.txt", "r", stdin);
FLC(root, true); REP_C(i, _RD(n)){
l[i] = 1, r[i] = C;
cin >> buff; if ('a' <= buff[0] && buff[0] <= 'z') root[i] = false, lc[buff[0] - 'a'].PB(i); else l[i] = stoi(buff);
cin >> buff; if ('a' <= buff[0] && buff[0] <= 'z') root[i] = false, rc[buff[0] - 'a'].PB(i); else r[i] = stoi(buff);
}
DWN(i, n, 0) {
FOR_1(j, l[i], r[i]) {
s[i][j] = 1;
REP(ii, SZ(lc[i])) MUL(s[i][j], rs[lc[i][ii]][j]);
REP(ii, SZ(rc[i])) MUL(s[i][j], ls[rc[i][ii]][j]);
}
stat(i);
}
res = 1; REP(i, n) if (root[i]){
MUL(res, rs[i][1]);
}
OT(res);
}
.. .
const int N = 400009;
int lc[N], rc[N], key[N], sz[N]; LL ss[N], cost[N]; int root, tot;
int L[N], T[N]; LL S;
int n, m, v;
#define lx lc[x]
#define rx rc[x]
inline void Update(int x){
if (x){
sz[x] = sz[lx] + sz[rx] + 1, ss[x] = ss[lx] + ss[rx] + key[x];
cost[x] = cost[lx] + cost[rx] + (ss[lx] + key[x]) * (sz[rx] + 1);
}
}
inline void rotate(int &x, int lc[], int rc[]){
int t = rx; rx = lc[t], lc[t] = x;
Update(x), Update(t), x = t;
}
inline void maintain(int &x, int lc[], int rc[]){
if (sz[lc[lx]] > sz[rx]) rotate(x, rc, lc);
else {
if (sz[rc[lx]] > sz[rx]) rotate(lx, lc, rc), rotate(x, rc, lc);
else return;
}
maintain(::lx, ::lc, ::rc), maintain(::rx, ::rc, ::lc);
maintain(x, ::rc, ::lc), maintain(x, ::lc, ::rc);
}
inline void Insert(int &x = root){
if (!x){
x = ++tot, sz[x] = 1;
cost[x] = ss[x] = key[x] = v;
}
else {
Insert(v < key[x] ? lx : rx), Update(x);
//if (v < key[x]) if (sz[lc[lx]] > sz[rx]) rotate(x, rc, lc); else;
//else if (sz[rc[rx]] > sz[lx]) rotate(x, lc, rc);
if (v < key[x]) maintain(x, lc, rc);
else maintain(x, rc, lc);
}
}
inline int Delete(int &x = root){
int res; if (v == key[x] || v < key[x] && !lx || v > key[x] && !rx){
res = key[x];
if (!lx || !rx) x = lx + rx;
else {
int _v = v; v = key[x] + 1;
key[x] = Delete(lx), v = _v;
}
}
else {
res = v < key[x] ? Delete(lx) : Delete(rx);
}
Update(x);
return res;
}
int main(){
//freopen("in.txt", "r", stdin);
RD(n, m); REP(i, n){
RD(L[i], T[i]), S += L[i];
v = T[i], Insert();
}
OT(S - cost[root]);
int x, l, t, rk; DO(m){
RD(x, l, t), --x, S -= L[x], S += L[x] = l;
v = T[x], Delete(), v = T[x] = t, Insert();
OT(S - cost[root]);
}
}
.. .
const int N = 400009;
int lc[N], rc[N], key[N], sz[N]; LL ss[N], cost[N]; int root, tot;
int L[N], T[N]; LL S;
int n, m, v;
#define lx lc[x]
#define rx rc[x]
#define Update ss[x] = ss[lx] + ss[rx] + key[x], cost[x] = cost[lx] + cost[rx] + LL(ss[lx] + key[x]) * (sz[rx] + 1)
inline void Insert(int &x = root){
if (!x){
x = ++tot, sz[x] = 1;
cost[x] = ss[x] = key[x] = v;
}
else {
++sz[x], Insert(v < key[x] ? lx : rx);
Update;
}
}
inline int Delete(int &x = root){
int res; --sz[x]; if (v == key[x] || v < key[x] && !lx || v > key[x] && !rx){
res = key[x];
if (!lx || !rx) x = lx + rx;
else {
int _v = v; v = key[x] + 1;
key[x] = Delete(lx), v = _v;
}
}
else {
res = v < key[x] ? Delete(lx) : Delete(rx);
}
Update;
return res;
}
int main(){
//freopen("in.txt", "r", stdin);
RD(n, m); REP(i, n){
RD(L[i], T[i]), S += L[i];
v = T[i], Insert();
}
OT(S - cost[root]);
int x, l, t, rk; DO(m){
RD(x, l, t), --x, S -= L[x], S += L[x] = l;
v = T[x], Delete(), v = T[x] = t, Insert();
OT(S - cost[root]);
}
}
