526互联

SMU Summer 2023 Contest Round 1

发布时间 2023-08-03 12:46:51作者: battle_123

Problem - A The Contest（纯属眼瞎）

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e7 + 50, M = 5050, mod = 9901, MAX_N = 1e3 + 50, INF = 0x3f3f3f3f;
const double PI = 3.1415926;
#define IOS ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
int n, m, a[N], l[M], r[M], s;

int main () {
    IOS;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        s += a[i];
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> l[i] >> r[i];
    }
    int ans = -1;
    for (int i = 0; i < m; i++) {
        if (l[i] <= s && s <= r[i]) {
            ans = s;
            break;
        } else if (s < l[i]) {
            ans = l[i];
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

Problem - B The Golden Age（数学）

TLE

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e7 + 50, M = 5050, mod = 9901, MAX_N = 1e3 + 50, INF = 0x3f3f3f3f;
const double PI = 3.1415926;
#define IOS ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)

ll qpow (ll a, ll b) { //a ^ b
    ll res = 1;
    while (b) {
        if (b & 1)res = a * res;
        a = a * a;
        b >>= 1;
    }
    return res;
}

ll x, y, l, r, sum[M], cnt;

int main () {
    IOS;
    cin >> x >> y >> l >> r;
    for (int i = 0;; i++) {
        ll s1 = qpow (x, i);
        if (s1 > r)
            break;
        for (int j = 0;; j++) {
            ll s = s1 + qpow (y, j);
            if (s >= l && s <= r)
                sum[cnt++] = s;
            else if (s > r)
                break;
        }
    }

    sort (sum, sum + cnt);
    cnt = unique (sum, sum + cnt) - sum;

    if (cnt == 0) {
        cout << r - l + 1 << endl;
        return 0;
    }
    ll ma = max (r - sum[cnt - 1], sum[0] - l);
    for (int i = 1; i < cnt; i++)
        ma = max (ma, sum[i] - sum[i - 1] - 1);
    cout << ma << endl;

    return 0;
}

AC

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e7 + 50, M = 5050, mod = 9901, MAX_N = 1e3 + 50, INF = 0x3f3f3f3f;
const double PI = 3.1415926;
#define IOS ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)

ll a[M], b[M], s[M];

int main () {
    ll x, y, l, r;
    cin >> x >> y >> l >> r;
    a[0] = b[0] = 1;
    int cnt1 = 1, cnt2 = 1;
    while (r / x >= a[cnt1 - 1]) {
        a[cnt1] = a[cnt1 - 1] * x;
        cnt1++;
    }
    while (r / y >= b[cnt2 - 1]) {
        b[cnt2] = b[cnt2 - 1] * y;
        cnt2++;
    }
    int p = 0;
    for (int i = 0; i < cnt1; i++)
        for (int j = 0; j < cnt2; j++)
            if (a[i] + b[j] >= l && a[i] + b[j] <= r)
                s[p++] = a[i] + b[j];
    sort (s, s + p);
    ll ans = 0;
    if (p == 0) {
        ans = r - l + 1;
    } else {
        ans = max (s[0] - l, r - s[p - 1]);
        for (int i = 0; i < p; i++) {
            ans = max (s[i] - l - 1, ans);
            l = s[i];
        }
    }
    cout << ans << endl;
    return 0;
}

Problem - C The Tag Game(DFS + 思维)

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e7 + 50, M = 2e5 + 50, mod = 9901, MAX_N = 1e3 + 50, INF = 0x3f3f3f3f;
const double PI = 3.1415926;
#define IOS ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
vector<int> vc[M];
int dp[2][M];
int dis[M];
int n, x;
int flag;

void dfs (int u, int w, int d) {
    flag = 1;
    for (int i = 0; i < vc[u].size (); i++) {
        if (!dis[vc[u][i]]) {
            dis[vc[u][i]] = 1;
            dfs (vc[u][i], w + 1, d);
            dis[vc[u][i]] = 0;
        }
    }
    if (flag) {
        dp[d][u] = w;
        return;
    }
}

int main () {
    int a, b;
    cin >> n >> x;
    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b;
        vc[a].push_back (b);
        vc[b].push_back (a);
    }
    memset (dis, 0, sizeof (dis));
    dis[1] = 1;
    dfs (1, 0, 0);
    memset (dis, 0, sizeof (dis));
    dis[x] = 1;
    dfs (x, 0, 1);
    int ma = -1;
    for (int i = 1; i <= n; i++) {
        if (dp[1][i] < dp[0][i] && dp[0][i] > ma)
            ma = dp[0][i];
    }
    cout << ma * 2 << endl;
    return 0;
}

Problem - D Two Melodies

//应该会想到是dp，看数据量有可能是二维的不妨设dp[i][j],由于这里只需要求两组所以dp[i][j]要表示为一组以i为结尾，一组以j为结尾。那么如何更新dp?

i=j时dp[i][j]=0。这里可以选择一个基准遍历结尾小的，更新结尾大的。
假设x>y，如果更新dp[x][y]是从dp[x][i]来的话可能不能确保以x为结尾的最大值不经过i点。所以要更新dp[i][y]。

大神的码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 50, M = 5e3 + 50, mod = 9901, MAX_N = 6e3 + 50, INF = 0x3f3f3f3f;
const double PI = 3.1415926;
#define IOS ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
int a[M], Mod[8], num[N], dp[M][M], n, ans;
//Mod为a[i] mod 7 == j 时dp[i][y]的最大值
//num为a[i] == j 时dp[i][y]的最大值
int main () {
    IOS;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    memset (dp, 0, sizeof dp);
    for (int i = 0; i <= n; i++) {
        memset (Mod, 0, sizeof Mod);
        memset (num, 0, sizeof num);
        for (int j = 1; j <= i; j++) {
            Mod[a[j] % 7] = max (Mod[a[j] % 7], dp[i][j]);
            num[a[j]] = max (num[a[j]], dp[i][j]);
        }
        for (int j = i + 1; j <= n; j++) {
            dp[i][j] = max (dp[i][0] + 1, dp[i][j]);
            dp[i][j] = max (Mod[a[j] % 7] + 1, dp[i][j]);
            dp[i][j] = max (num[a[j] + 1] + 1, dp[i][j]);
            dp[i][j] = max (num[a[j] - 1] + 1, dp[i][j]);
            Mod[a[j] % 7] = max (Mod[a[j] % 7], dp[i][j]);
            num[a[j]] = max (num[a[j] + 1], dp[i][j]);
            dp[j][i] = dp[i][j];
            ans = max (ans, dp[i][j]);
        }
    }
    cout << ans << endl;

    return 0;
}

自己的

定义dp数组，dp[i][j]表示以第一个子序列的最后一个元素为i，以第二个子序列的最后一个元素为j时，两个子序列形成旋律的最大长度。

从前往后遍历每个元素，对于当前元素a[i]，考虑它与之前的每个元素a[j]的关系：

  • 如果a[j]和a[i]满足相邻差为1或模7同余，那么可以将a[j]加入第一个子序列，a[i]加入第二个子序列，此时dp[i] [j] = dp[j] [k] + 1，其中k < j，并且k位置处的元素与a[i]满足差为1或模7同余。
  • 对于每个j位置处的元素，更新dp[i] [j]，取所有可能的情况中的最大值。

最终，求取dp数组中的最大值即为所要求的答案。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 50, M = 5e3 + 50, mod = 9901, MAX_N = 6e3 + 50, INF = 0x3f3f3f3f;
const double PI = 3.1415926;
#define IOS ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
int n;

int main () {
    IOS;
    cin >> n;
    vector<int> notes (n);
    for (int i = 0; i < n; i++) {
        cin >> notes[i];
    }
    vector<vector<int>> dp (n, vector<int> (n, 0));
    for (int i = 1; i < n; i++) {
        int max_len = 0;
        for (int j = 0; j < i; j++) {
            if (abs (notes[j] - notes[i]) == 1 || abs (notes[j] - notes[i]) % 7 == 0) {
                dp[i][i] = max (dp[i][i], dp[j][i - 1] + 1);
                dp[i][i] = max (dp[i][i], dp[j][j] + 1);
                max_len = max (max_len, dp[j][i]);
            }
        }
        for (int j = i + 1; j < n; j++) {
            dp[i][j] = max_len;
        }
    }
    int max_sum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            max_sum = max (max_sum, dp[i][j]);
        }
    }
    cout << max_sum << endl;
    return 0;
}

Problem - E Army Creation

TLE

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 50, M = 5e3 + 50, mod = 9901, MAX_N = 6e3 + 50, INF = 0x3f3f3f3f;
const double PI = 3.1415926;
#define IOS ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)

int n, k, a[N], s[N], last, q, x, y;

int main () {
    IOS;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> q;
    for (int i = 0; i < q; i++) {//1e5
        cin >> x >> y;
        memset (s, 0, sizeof s);
        int l = ((x + last) % n) + 1;
        int r = ((y + last) % n) + 1;
        if (l > r) swap (l, r);
        int ans = 0;
        for (int j = l; j <= r; j++) {//1e5
            if (s[a[j]] < k) {
                s[a[j]]++;
                ans++;
            }
        }
        last = ans;
        cout << ans << endl;
    }
    return 0;
}
// 优化代码时间复杂度