## 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;
}