transaction transaction transaction

transaction transaction transaction

【2017 ACM/ICPC Asia Regional Shenyang Online】

【DP问题】

Solution:

对于这个问题,首先可以想到一个暴力办法,即把每一种出发点到每一种结束点的可能性都枚举一遍,找到最优解,显然,这种办法虽然可以求出解,但是会超时,因此我们采用dp的办法来解决。我们建立一个二维dp数组,dp[i][0]表示从某个城市购买书籍并运送到这里的最少花费,存储为负值;dp[i][1]表示从某个城市送货到当前城市所能得到的最大收益。显然,dp[i][0] + dp[i][1]表示从某个城市出发经由城市i买到另外一所城市的最大收益,本题的最优解也就在这些值中产生。

#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:

这道题的关键在于时间消耗,由于循环放到末尾,所以不妨在读取时便复制一份,开一个二倍的数组,而节省时间的关键在于:不要针对每一个为起点进行一次判断,而是直接从这个二倍数组从头到尾遍历一次,每遇到一次penalty为负数导致游戏结束的情况就进行一次初始化,从下一个位置接着来。这么做可以的原因十分简单,可以这样想:如果从第三张牌开始摸到第六张是最大的情况,那么我们不需要再开一次从第四张、第五章、第六张的尝试,因为它们不可能比上面那种情况更优。

另外,采取了一个“哨兵”技巧,即在二倍数组的最后放一个很大的惩罚值,这样是为了避免出现当读取到最后一个牌堆的时候Penalty还是正值而导致这一种情况没有被考虑入可能的答案中。【备注:由于在n*2位置处加上了“哨兵”,我们应当将循环条件设置成i <= n * 2】

#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:

对于M个显示器,我们不如这样考虑:对于前K个【备注:题目保证了K不大于M】显示器,分别只与一个信号源连接,需要K根信号线;接下来断言,剩下的M-K个显示器每个都必要与K个信号源连接,也就是K*(M-K)根线,我们使用反证法证明,做如下思考,假如我们在选取K个显示器的时候,先将这K个显示器选定,之后任意从中去除一个显示器,再从剩下的M-K个显示器中选一个假如进来,如果这剩下的显示器中存在一个没有连接到K个信号源的显示器的话,假设它没有连接\(K_a\)信号源,那么,如果我们在选取时不选那个只连接着\(K_a\)信号源的显示器,而选择这个,就会导致不满足K个显示器有K个颜色,故断言必然成立。

因此公式为:

\(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:

反过来找最长不上升子序列的长度,就是正着找最长不下降子序列的长度,所以这道题其实就是找两次最长不上升子序列,注意,\(O(n^2)\)会超时。

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