这是今年我的最后一场,顺便写一下游记,第一场因为发挥打铁,心里很郁闷,加之最近学业加(我们学院都是硬件专业) 。那天考了四级(不能过)就和另外一个队一起坐高铁来到西安,到的时候时间还有还可以打一打热身赛,不得不说志愿者服务真好。
第一天热身赛,看了一眼,旁边都是比我们好的学校,直接签了A题,C++,JAVA都试了一下还不错,Clion好用,B题刚刚开始想对了,但不过被自己干掉了,然后试了一试机器,就走了,会宾馆点外卖。
第二天正式赛,其实挺慌的,不敢多开,就三个人看一道题,好在刚刚开场就有人过了A题,然后看A题,三个人反复确认没有读错后,大家一起写了一发,一发A,然后有人交了E,M题,就看E题和M题,M题刚刚我有点误解题意了,好在队友小G纠正过来了,然后小Z感觉E题题意不是很好,然后因为小G擅长图论,就让一起读懂了题意让他看了看,结果他想了10分钟,没有思路,然后小Z有想到了M题怎么做,我们让小G继续看看E,我和小Z写M,一会儿写出来了,测了很多数据没有问题,交WA,因为有了南京的前车之鉴,一下子看到了爆了int,该了一交A了,然后这时E题过得比H多,然后不知道怎么的大家好像多E题没有思路就都来看H题,H题一会儿也读懂了,然后大家都在想不知道怎么做,中间我口嗨了一个原根。。。然后忽然听到旁边有一个队说了一个n/2个数,肯定不会超过二的间隔不是2就是1,最多3,然后我们好像知道怎么做了,写了一会儿,WA一发,好在一下子就测出了,特殊样例,改了A了,然后还有两个小时,我们分别看了C题和E题,我想了30分钟C题确实想不到,然后我们去看E题,中间我想了个假算法,WA了,然后大家,想法层出不穷,没一个对的,然后就结束了,心想南京有这状态多好。好在最后混了一个银尾,很开心了。。。。
本人水平有限,有不对的地方,请指正。。。

A. City

本场比赛唯一的签到题,给一个网格,问有多少条线段两端是格点,同时中点也是格点,比赛时拿着这道题,想了一会儿,直接就上去写了,就是暴力统计,偶数长度边的数量,然后偶数偶数进行组合。

#include "bits/stdc++.h"


using namespace std;
inline int read() {
    int x = 0;
    bool f = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = 0;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
    if (f) return x;
    return 0 - x;
}
typedef long long ll;
const int maxn = 100000 + 10;
const ll mod = 998244353;
int n, m;

int main() {
    cin >> n >> m;
    ll ans = 0;
    for (int i = 2; i <= n; i += 2)
        ans += 1ll * (m + 1) * (n - i + 1);
    for (int i = 2; i <= m; i += 2)
        ans += 1ll * (n + 1) * (m - i + 1);
    for (int i = 2; i <= n; i += 2) {
        for (int j = 2; j <= m; j += 2) {
            ans += 2ll * (n - i + 1) * (m - j + 1);
        }
    }
    cout << ans << endl;
    return 0;
}

C.Dirichlet k kk-th root

我想说的是,题意很好的,就是求一个函数f,他自己狄利克雷卷自己k次得到的g。
这是以前学习中不曾想过的,今天偶然发现一个函数卷自己mod+1次就是自己,mod次就是
把我惊倒了,我就想和mod有关,没想到开k次方根就是一个快速幂 次,交了一发居然过了。我也不知道,等能证明了再来补上。

#include "bits/stdc++.h"


using namespace std;
inline int read() {
    int x = 0;
    bool f = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = 0;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
    if (f) return x;
    return 0 - x;
}
typedef long long ll;
const int maxn = 100000 + 10;
const ll mod = 998244353;
ll quick(ll a, ll n) {
    a %= mod;
    ll ans = 1;
    while (n) {
        if (n & 1) ans = ans * a % mod;
        n >>= 1;
        a = a * a % mod;
    }
    return ans;
}
int n, k;
ll f[maxn], g[maxn], s[maxn], ss[maxn], pro[maxn], inv_f[maxn];
void mult(ll a[], ll b[]) {
    memset(s, 0, sizeof(s));
    for (int i = 1; i * i <= n; i++) {
        s[i * i] = (s[i * i] + a[i] * b[i] % mod) % mod;
        for (int j = i + 1; i * j <= n; j++) {
            s[i * j] = (s[i * j] + a[i] * b[j] % mod + a[j] * b[i] % mod) % mod;
        }
    }
    for (int i = 1; i <= n; i++) a[i] = s[i];
}

void power(ll a[], int p) {
    for (int i = 1; i <= n; i++) ss[i] = a[i];
    memset(pro, 0, sizeof(pro));
    pro[1] = 1;
    while (p) {
        if (p & 1) mult(pro, ss);
        mult(ss, ss);
        p >>= 1;
    }
    for (int i = 1; i <= n; i++) a[i] = pro[i];
}
int main() {
    n = read(), k = read();
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &f[i]);
        g[i] = 1;
    }
    ll inv = quick(k, mod - 2);
    power(f, inv);
    printf("%lld", f[1]);
    for (int i = 2; i <= n; i++) {
        printf(" %lld", f[i]);
    }
    cout << endl;
    return 0;

E.Flow

本题题意,给你一个图,这个图很特殊,源点1到汇点n的长度都相等,而且每一条源点到汇点的路径都是独立路径互补相交,类似与链,你可让一条边加1另外一条边减去1,问使得流尽量大的最少操作数。比赛的假算法就算了吧。
参考同校的宋大佬,能过的算法是这样的,对每一条链的流进行排序,并对每一条链的流进行排序,然后统计每一条链排序后,把所有链一起流扩到下一个结点的代价。然后就可以进行贪心了,枚举每一点,剩余流量能加就加上,同时判断能不能扩充到下一个流量。

#include "bits/stdc++.h"


using namespace std;
inline int read() {
    int x = 0;
    bool f = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = 0;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
    if (f) return x;
    return 0 - x;
}
typedef long long ll;
const int maxn = 200000 + 10;
struct edge {
    int v, next, w;
} ed[maxn];
int head[maxn], cnt = 0, n, m;
void add_edge(int u, int v, int w) {
    ++cnt;
    ed[cnt].v = v;
    ed[cnt].w = w;
    ed[cnt].next = head[u];
    head[u] = cnt;
}
vector<int> g[maxn];
void dfs(int u, int f) {
    for (int i = head[u]; i; i = ed[i].next) {
        int v = ed[i].v;
        if (v == f) continue;
        g[cnt].push_back(ed[i].w);
        dfs(v, u);
    }
}
ll addflow[maxn];
int main() {
    n = read(), m = read();
    int u, v, w, len;
    ll flow = 0;
    for (int i = 1; i <= m; i++) {
        u = read();
        v = read();
        w = read();
        add_edge(u, v, w);
//        add_edge(v, u, w);
        flow += w;
    }
    cnt = 0;
    for (int i = head[1]; i; i = ed[i].next) {
        v = ed[i].v;
        g[++cnt].push_back(ed[i].w);
        dfs(v, 1);
        len = g[cnt].size();
        sort(g[cnt].begin(), g[cnt].end());
        int l = 0;
        while (l < len - 1) {
            while (l < len - 1 && g[cnt][l] == g[cnt][l + 1]) l++;
            if (l < len) addflow[l + 1] += g[cnt][l + 1] - g[cnt][l];
            l++;
        }
        flow -= 1ll * g[cnt][0] * len;
    }
    ll ans = 0, tmp;
    for (int i = 1; i < len; i++) {
        if (flow < len) break;
        tmp = min(addflow[i], flow / len);
        ans += 1ll * tmp * i;
        flow -= 1ll * tmp * len;
    }
    cout << ans << endl;
    return 0;
}

H.kink

题意类似于求,等比数列的长度,要求长度大于等于n/2向上取整。
做法,对每个相邻的数,求公比,用map进行记录,然后中间相隔一个的求公比,然后用map记录。
对出现次数大于n/8(准确多少我也不知道,刚刚gym上n/5可以过)的进行计数,取最大值输出就可以了。
计数的时候我用的dp要特判1的情况。现场赛,听说有很多队被卡了,我们用的map,不知道怎么的过了,下来在gym上1s能过,牛客就不行了,可能我写得不对吧。。。

#include "bits/stdc++.h"


using namespace std;
inline int read() {
    int x = 0;
    bool f = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = 0;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
    if (f) return x;
    return 0 - x;
}
typedef long long ll;
const int maxn = 200000 + 10;
ll mod, b[maxn], inv[maxn];
int T, n;
ll quick(ll a, ll n, ll p) {
    a %= p;
    ll ans = 1;
    while (n) {
        if (n & 1) ans = ans * a % p;
        n >>= 1;
        a = a * a % p;
    }
    return ans;
}

int check(ll q) {
    unordered_map<int, int> dp;
    int ret = 0;
    if (q == 1) {
        for (int i = n; i >= 1; i--) {
            dp[b[i]]++;
            ret = max(dp[b[i]], ret);
        }
        return ret;
    }
    for (int i = n; i >= 1; i--) {
        dp[b[i]] = 1;
        dp[b[i]] = dp[(int)(b[i] * q % mod)] + 1;
        ret = max(ret, dp[b[i]]);
    }
    return ret;
}
unordered_map<int, int> mp;

int main() {
    scanf("%d", &T);
    while (T--) {
        mp.clear();
        scanf("%d %lld", &n, &mod);
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &b[i]);
            inv[i] = quick(b[i], mod - 2, mod);
        }
        ll q;
        for (int i = 1; i < n; i++) {
            q = b[i + 1] * inv[i] % mod;
            mp[q]++;
        }
        for (int i = 1; i < n - 1; i++) {
            q = b[i + 2] * inv[i] % mod;
            mp[q]++;
        }
        unordered_map<int, int>::iterator it = mp.begin();
        int ans = 0;
        for (; it != mp.end(); it++) {
            if ((it->second) >= n / 6) {
                ans = max(ans, check(it->first));
            }
        }
        if (ans < (n + 1) / 2) ans = -1;
        printf("%d\n", ans);
    }
    return 0;
}

M.value

这道题,可能有的人被题意杀了,题意就是你可以选择一些下标的集合,价值为下标对于的a数组值,如果下标集合中满足任意则减去b[j]。问价值最大值。
做法就是,对于每一个进制判断在n的范围内有多少个数并且记录下来 ,然后对此进行二进制状压暴力判断每一个进制的最大值就可以了
具体就是,每一个值对应一个状态,你要从小的更新上去,直接两重for循环都可以,具体就是你要取j位,因为先前记录了他是i的次方,for循环查看前面有没有他的次方的因子就可以了。

#include "bits/stdc++.h"


using namespace std;
inline int read() {
    int x = 0;
    bool f = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = 0;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
    if (f) return x;
    return 0 - x;
}
typedef long long ll;
const int maxn = 100000 + 10;
const ll mod = 998244353;
int n, vis[maxn], mp[maxn];
vector<int> v[maxn];
ll a[maxn], b[maxn], ans = 0;

ll solve(int st, int sz, vector<int> l) {
    int ss = 0, p[20] = {0};
    ll ret = 0;
    for (int i = 0; i < sz; i++) {
        if ((st >> i) & 1) {
            p[++ss] = i + 1;
            ret += a[l[i]];
        }
    }
    for (int i = 1; i <= ss; i++) {
        for (int j = i - 1; j >= 1; j--) {
            if (p[i] % p[j] == 0)
                ret -= b[l[p[i] - 1]];
        }
    }
    return ret;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &b[i]);
    }
    int cnt = 0;
    for (ll i = 2; i <= n; i++) {
        if (vis[i]) continue;
        ll tmp = i;
        mp[++cnt] = i;
        while (tmp <= n) {
            vis[tmp] = 1;
            v[i].push_back(tmp);
            tmp *= i;
        }
    }
    ll ans = 0;
    for (int i = 1; i <= cnt; i++) {
        int sz = v[mp[i]].size();
        if (sz == 1) {
            ans += a[v[mp[i]][0]];
            continue;
        }
        ll tmp = 0;
        for (int j = 0; j < (1 << sz); j++) {
            tmp = max(tmp, solve(j, sz, v[mp[i]]));
        }
        ans += tmp;
    }
    ans += a[1];
    cout << ans << endl;
    return 0;
}