## transaction transaction transaction

transaction transaction transaction

【2017 ACM/ICPC Asia Regional Shenyang Online】

【DP问题】

Solution:

#include <iostream>
#include <vector>

using namespace std;

struct node {
int to, weight;
};

const int NIL = -1;
const int LIM = 1e5 + 10;

int val[LIM], n;
vector<node> edges[LIM];
int dp[LIM][2], ans = 0;

inline int maxi(int a, int b) {
return a > b ? a : b;
}

void init() {
ans = 0;
for (int i = 1; i <= n; i++) {
edges[i].clear();
}
}

void dfs(int crt, int from) {
dp[crt][0] = -val[crt];
dp[crt][1] = val[crt];
for (vector<node>::iterator ite = edges[crt].begin(); ite != edges[crt].end(); ite++) {
int to = ite->to;
if (to == from) continue;
dfs(to, crt);
dp[crt][0] = maxi(dp[crt][0], dp[to][0] - ite->weight);
dp[crt][1] = maxi(dp[crt][1], dp[to][1] - ite->weight);
}
ans = maxi(ans, dp[crt][0] + dp[crt][1]);
}

int main(void) {
int t, from, to, w;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
init();
for (int i = 1; i <= n; i++)
scanf("%d", val + i);
for (int i = 1; i < n; i++) {
scanf("%d%d%d", &from, &to, &w);
edges[from].push_back({to, w});
edges[to].push_back({from, w});
}
dfs(1, NIL);
printf("%d\n", ans);
}
return 0;
}

## card card card

【2017 ACM/ICPC Asia Regional Shenyang Online】card card card

【循环置尾问题】

Solution:

#include <iostream>

using namespace std;

const int LIM = 1e6 + 10;
int arr[LIM * 2];
int penal[LIM * 2];

int main(void) {
int n;
while (~scanf("%d", &n)) {
for (int i = 0; i < n; i++) {
scanf("%d", arr + i);
arr[i + n] = arr[i];
}
for (int i = 0; i < n; i++) {
scanf("%d", penal + i);
penal[i + n] = penal[i];
}
penal[n * 2] = 1e7;
arr[n * 2] = 0;
int ans, tp = 0, ti = 0, ts = 0, maxi = 0;
for (int i = 0; i <= 2 * n; i++) {
ti += arr[i];
tp += arr[i] - penal[i];
if (tp < 0) {
if (ti > maxi) {
maxi = ti;
ans = ts;
}
tp = ti = 0;
ts = i + 1;
}
}
printf("%d\n", ans);
}
return 0;
}

## number number number

【2017 ACM/ICPC Asia Regional Shenyang Online】number number number

Solution:

#include <iostream>
#include <cstdio>
using namespace std;

const int MOD = 998244353;

typedef unsigned long long ULL;

struct Matrix {
ULL v[2][2];
Matrix operator * (const Matrix & m) const {
Matrix ret = {{0}};
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
ret.v[i][j] += (v[i][k] * m.v[k][j]) % MOD;
ret.v[i][j] %= MOD;
}
}
}
return ret;
}
void operator *= (const Matrix & m) {
*this = *this * m;
}
};

Matrix fastPow(Matrix x, ULL n) {
Matrix ans = {{{1, 0}, {0, 1}}};
while (n) {
if (n & 1) ans *= x;
x *= x;
n >>= 1;
}
return ans;
}

const Matrix trans = {{{1, 1}, {1, 0}}};

int main(void) {
ios::sync_with_stdio(false);
ULL k;
while (cin >> k) {
if (k == 1) cout << 4 << endl;
else {
Matrix transform = fastPow(trans, 2 * (k - 1) - 1);
cout << (transform.v[0][0] * 8 + transform.v[0][1] * 5 - 1) % MOD << endl;
}
}
return 0;
}


## cable cable cable

【2017 ACM/ICPC Asia Regional Shenyang Online】cable cable cable

Solution:

$$k + k * (m – k) = k * (m – k + 1)$$

#include <iostream>

using namespace std;

typedef unsigned long long ULL;

int main(void) {
ios::sync_with_stdio(false);
ULL k, m;
while (cin >> m >> k) {
cout << k * (m - k + 1) << endl;
}
return 0;
}

## array array array

【2017 ACM/ICPC Asia Regional Shenyang Online】array array array

Solution:

#include <iostream>
#include <cstring>

using namespace std;

const int LIM = 1e5 + 10;
int arr[LIM];
int rarr[LIM];
int dp[LIM];
int rdp[LIM];
int n;

inline int maxi(int a, int b) {
return a > b ? a : b;
}

int lis() {
memset(dp, 0, sizeof dp);
memset(rdp, 0, sizeof rdp);
int dpl, rdpl;
dpl = rdpl = 0;
for (int i = 0; i < n; i++) {
int j;
for (j = 0; j < dpl; j++) {
if (arr[i] > dp[j]) {
dp[j] = arr[i];
break;
}
}
if (j == dpl) dp[dpl++] = arr[i];
for (j = 0; j < rdpl; j++) {
if (rarr[i] > rdp[j]) {
rdp[j] = rarr[i];
break;
}
}
if (j == rdpl) rdp[rdpl++] = rarr[i];
}
return maxi(dpl, rdpl);
}

int main(void) {
int t, k;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) {
scanf("%d", arr + i);
rarr[n - i - 1] = arr[i];
}
int maxi = lis();
printf("%s\n", maxi >= n - k ? "A is a magic array." : "A is not a magic array.");
}
return 0;
}

## 【2017ACM-ICPC广西邀请赛】Color it

【2017ACM-ICPC广西邀请赛】Color it

【动态线段树】

Solution:

C++代码：

#include <iostream>
#include <cstring>

using namespace std;

const int INF = 1e7;
const int LIM = 2e6;
bool flag;
int tree[LIM], rootPos[51], lrt[LIM], rrt[LIM], num;

inline int mini(int a, int b) {
return a < b ? a : b;
}

inline void clear() {
num = 0;
for (int i = 0; i < LIM; i++) tree[i] = INF;
memset(rootPos, 0, sizeof rootPos);
memset(lrt, 0, sizeof lrt);
memset(rrt, 0, sizeof rrt);
}

inline void pushup(int rt) {
tree[rt] = mini(tree[lrt[rt]], tree[rrt[rt]]);
}

void update(int l, int r, int si, int x, int &rt) {
if (l > si || r < si) return;
if (!rt) rt = ++num;
if (l == r) {
if (tree[rt] > x) tree[rt] = x;
return;
}
int mid = (l + r) >> 1;
update(l, mid, si, x, lrt[rt]);
update(mid + 1, r, si, x, rrt[rt]);
pushup(rt);
}

void query(int l, int r, int qs, int qe, int x, int &rt) {
if (!rt || flag || l > qe || r < qs) return;
if (l >= qs && r <= qe) {
if (tree[rt] <= x) flag = true;
return;
}
int mid = (l + r) >> 1;
query(l, mid, qs, qe, x, lrt[rt]);
query(mid + 1, r, qs, qe, x, rrt[rt]);
}

int main(void) {
int op, x, y1, y2, c;
while (~scanf("%d", &op) && op != 3) {
if (op == 0) clear();
else if (op == 1) {
scanf("%d%d%d", &x, &y1, &c);
update(1, LIM, y1, x, rootPos[c]);
} else if (op == 2) {
scanf("%d%d%d", &x, &y1, &y2);
int ans = 0;
for (int i = 0; i <= 50; i++) {
flag = false;
query(1, LIM, y1, y2, x, rootPos[i]);
if (flag) ans++;
}
printf("%d\n", ans);
}
}
return 0;
}

## 【2017ACM-ICPC广西邀请赛】Covering

【2017ACM-ICPC广西邀请赛】Covering

【递推+矩阵快速幂】

Solution 1:

#include <iostream>
#include <cstring>
using namespace std;

const int LIM = 10;
bool vis[4][LIM];
int n;
int cnt = 0;

bool find(int & r, int & c) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < n; j++) {
if (!vis[i][j]) {
r = i;
c = j;
return true;
}
}
}
return false;
}

void bruteDfs() {
int r, c;
if (!find(r, c)) {
cnt++;
return;
}
if (r < 3 && !vis[r + 1][c]) {
vis[r][c] = vis[r + 1][c] = true;
bruteDfs();
vis[r][c] = vis[r + 1][c] = false;
}
if (c < n - 1 && !vis[r][c + 1]) {
vis[r][c] = vis[r][c + 1] = true;
bruteDfs();
vis[r][c] = vis[r][c + 1] = false;
}
}

int main(void) {
for (n = 1; n <= 10; n++) {
memset(vis, false, sizeof vis);
cnt = 0;
bruteDfs();
printf("4*%d : %d\n", n, cnt);
}
return 0;
}

4*1 : 1
4*2 : 5
4*3 : 11
4*4 : 36
4*5 : 95
4*6 : 281
4*7 : 781
4*8 : 2245
4*9 : 6336
4*10 : 18061

#include <iostream>

using namespace std;

int main(void) {
for (int a1 = -10; a1 <= 10; a1++) {
for (int a2 = -10; a2 <= 10; a2++) {
for (int a3 = -10; a3 <= 10; a3++) {
for (int a4 = -10; a4 <= 10; a4++) {
if (a1 * 1 + a2 * 5 + a3 * 11 + a4 * 36 == 95 &&
a1 * 5 + a2 * 11 + a3 * 36 + a4 * 95 == 281 &&
a1 * 11 + a2 * 36 + a3 * 95 + a4 * 281 == 781 &&
a1 * 36 + a2 * 95 + a3 * 281 + a4 * 781 == 2245) {
printf("f(n) = %df(n - 1) + %df(n - 2) + %df(n - 3) + %df(n - 4)\n", a4, a3, a2, a1);
}
}
}
}
}
return 0;
}

f(n) = 1f(n - 1) + 5f(n - 2) + 1f(n - 3) + -1f(n - 4)

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const LL MOD = 1000000007;
struct Matrix {
LL v[4][4];
Matrix operator * (const Matrix & m) const {
Matrix ret = {{0}};
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
for (int k = 0; k < 4; k++) {
ret.v[i][j] += (v[i][k] * m.v[k][j] + MOD) % MOD;       //注意v[i][k] * m.v[k][j]可能会变成负数，需要加上MOD
ret.v[i][j] %= MOD;
}
}
}
return ret;
}
void operator *= (const Matrix & m) {
*this = *this * m;
}
};
const Matrix base = {{{1, 5, 1, -1}, {1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}}};
LL start[] = {1, 5, 11, 36};

Matrix fastPow(Matrix x, LL pow) {
Matrix ans = {{{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}};
while (pow) {
if (pow & 1) ans *= x;
x *= x;
pow >>= 1;
}
return ans;
}

int main(void) {
ios::sync_with_stdio(false);
LL n;
while (cin >> n) {
if (n <= 4) cout << start[n - 1] << endl;
else {
Matrix fac = fastPow(base, n - 4);
cout << (fac.v[0][0] * start[3]
+ fac.v[0][1] * start[2]
+ fac.v[0][2] * start[1]
+ fac.v[0][3] * start[0]) % MOD << endl;
}
}
return 0;
}

## 【2017ACM-ICPC广西邀请赛】Duizi and Shunzi

【2017ACM-ICPC广西邀请赛】Duizi and Shunzi

【贪心】

9

1 2 3 3 4 5 5 6 7

12

2 3 4 4 5 6 6 7 8 8 9 10

5

2 2 2 2 2

6

4 4 5 5 6 6

3

4

2

3

Solution:

ceil(a / 2) + ceil(b / 2) + ceil(c / 2).    【其中ceil()表示向下取整】

ceil(a / 2) + ceil(b / 2) + ceil(c / 2) >= $$\frac{3t}{2}$$.

#include <iostream>
#include <cstring>

using namespace std;

const int LIM = 1e6 + 5;
int data[LIM];

int main(void) {
int n, ans, t;
while (~scanf("%d", &n)) {
memset(data, 0, sizeof data);
ans = 0;
for (int i = 0; i < n; i++) {
scanf("%d", &t);
data[t]++;
}
for (int i = 1; i <= n; i++) {
ans += data[i] / 2;
data[i] %= 2;
if (data[i] && data[i + 1] && data[i + 1] % 2 && data[i + 2]) {
ans++;
data[i + 1]--;
data[i + 2]--;
}
}
printf("%d\n", ans);
}
return 0;
}

## 【2017ACM-ICPC广西邀请赛】CS Course

【2017ACM-ICPC广西邀请赛】CS Course

【前后缀/位数统计+异或的运算性质】

Solution 1:

Core concept:

1. 对于一串数$$a_1, a_2 … a_n$$，要求去掉$$a_p (p \in [1, n])$$后，求剩下全部数的与、或、异或的值，为了方便表述，我们将这里的运算用符号$$\oplus$$表示，则当前问题是求：

$$a_1 \oplus … a_{p – 1} \oplus a_{p + 1}… \oplus a_n = ?$$.

$$(a_1 \oplus … a_{p – 1}) \oplus (a_{p + 1} … \oplus a_n)$$

2.对于异或运算，我们也可以采用上边的办法，但是，由于有更好的办法（即利用异或运算性质），我们采用另一种办法。

b ^ b = 0（^表示异或），即一个数总是其自身的异或逆元。

a ^ b = b ^ a，即交换律。

#include <iostream>

using namespace std;

const int LIM = 1e5 + 10;
struct node {
int av, ov;     // "and value" and "or value"
};

int a[LIM];
node pre[LIM], suf[LIM];

int main(void) {
int n, q;
int xorans;
while (~scanf("%d%d", &n, &q)) {
xorans = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
xorans ^= a[i];
pre[i].av = pre[i].ov = suf[i].av = suf[i].ov = a[i];
if (i != 1) {
pre[i].av &= pre[i - 1].av;
pre[i].ov |= pre[i - 1].ov;
}
}
for (int i = n - 1; i >= 1; i--){
suf[i].av &= suf[i + 1].av;
suf[i].ov |= suf[i + 1].ov;
}
int p;
while (q--) {
scanf("%d", &p);
if (p == 1) printf("%d %d %d\n", suf[2].av, suf[2].ov, xorans ^ a[1]);
else if (p == n) printf("%d %d %d\n", pre[n - 1].av, pre[n - 1].ov, xorans ^ a[n]);
else printf("%d %d %d\n", pre[p - 1].av & suf[p + 1].av, pre[p - 1].ov | suf[p + 1].ov, xorans ^ a[p]);

}
}
return 0;
}

Solution 2:

#include <iostream>
#include <cstring>
using namespace std;

const int LIM = 1e5 + 10;
const int BITS = 32;
int a[LIM];
int cnt[BITS];
int cnttmp[BITS];

int main(void) {
int n, q;
int xorans;
while (~scanf("%d%d", &n, &q)) {
memset(cnt, 0, sizeof cnt);
xorans = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
xorans ^= a[i];
int tmp = a[i];
for (int i = 0; tmp; i++, tmp >>= 1)
if (tmp & 1) cnt[i]++;
}
int p, andans, orans;
while (q--) {
andans = orans = 0;
scanf("%d", &p);
memcpy(cnttmp, cnt, sizeof cnt);
int tmp = a[p];
// 使用cnttmp数组来存储去掉a_p后，各位的1的个数
for (int i = 0; tmp; i++, tmp >>= 1) {
if (tmp & 1) cnttmp[i]--;
}
for (int i = BITS - 1; i >= 0; i--, tmp >>= 1) {
andans <<= 1;
orans <<= 1;
if (cnttmp[i] == n - 1) andans |= 1;
if (cnttmp[i] > 0) orans |= 1;
}
printf("%d %d %d\n", andans, orans, xorans ^ a[p]);
}
}
return 0;
}

## 【2017ACM-ICPC广西邀请赛】A Math Problem

【2017ACM-ICPC广西邀请赛】A Math Problem

Solution:

#include <iostream>

using namespace std;

typedef unsigned long long ULL;

ULL fastPow(ULL a, ULL b) {
ULL ret = 1;
for (; b; b >>= 1) {
if (b & 1) ret *= a;
a *= a;
}
return ret;
}

int main(void) {
ULL n;
while (cin >> n) {
ULL k;
for (k = 1; k <= 15; k++)
if (fastPow(k, k) > n) break;
cout << k - 1 << endl;
}
return 0;
}