首页 > 编程语言 >华中农业大学第十三届程序设计竞赛 题解

华中农业大学第十三届程序设计竞赛 题解

时间：2024-04-14 21:36:10浏览次数：20  
标签：int 题解 ll 华中农业大学 cin ++ 第十三届 sum size

A - scx 的散文诗句

Solution

正负分开来分别处理，按照绝对值从大到小排序，两两匹配

注意：当没有 \(0\) 且 正数 和 负数 都为奇数，即最后剩下一个正数一个负数时，必须匹配

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve() {
    int n; cin >> n;
    vector<ll> a, b;
    int cnt_0 = 0;
    for (int i = 1; i <= n; i++) {
        ll x; cin >> x;
        if (x > 0) a.push_back(x);
        if (x < 0) b.push_back(x);
        if (x == 0) cnt_0 ++;
    }
    ll ans = 0;
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
    sort(b.begin(), b.end());
    for (int i = 0; i < a.size(); i += 2) {
        if (i + 1 < a.size())
            ans += a[i] * a[i + 1];
    }
    for (int i = 0; i < b.size(); i += 2) {
        if (i + 1 < b.size())
            ans += b[i] * b[i + 1];
    }
    if (cnt_0 == 0 && a.size() % 2 == 1 && b.size() % 2 == 1) 
        ans += a.back() * b.back();
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
}

B - 喵喵喵

Solution

我的做法和 std 好像不太一样

\[\sum\limits_{i=1}^n\sum\limits_{j=1}^n a_ia_j\lfloor \frac{x\gcd(a_i,a_j)+y}{z}\rfloor \]

当 \(\gcd(a_i,a_j) =d\) 的值确定了之后，\(\lfloor \frac{x\gcd(a_i,a_j)+y}{z}\rfloor=p\) 的值也就确定了

关键是 \(a_ia_j\)，考虑把 \(a_ia_j\) 变成 \(d^2 \times \frac{a_i}{d}\frac{a_j}{d}\)

我们枚举一个 \(d\) ，式子转化成

\[\sum\limits_{i=1}^n\sum\limits_{j=1}^n d^2 \times \frac{a_i}{d}\frac{a_j}{d}\times p \]

\[d^2 \times p\times \sum\limits_{d|a_i} \frac{a_i}{d} \sum\limits_{d|a_j} \frac{a_j}{d} \]

这个式子可以使用调和做法求出

但是有可能会算出，比如 \(8,4\) 会在 \(2\) 的地方算一次答案，会在 \(4\) 的地方算一个答案

所以我们对于 \(d\)，需要在 \(d\) 的倍数的地方把此时 \(d\) 的贡献减去

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll TT = 1e9 + 7;
ll x, y, z;
ll read() {
    ll ret = 0; char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch <= '9' && ch >= '0') ret = ret * 10 + ch - '0', ch = getchar();
    return ret;
}

void print(ll x) {
    if (x == 0) return ;
    print(x / 10);
    putchar(x % 10 + '0');
}
int main() {
    int n; cin >> n;
    ll ans = 0;
    x = read(), y = read(), z = read();
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++)
        a[i] = read();
    ll max_x = *max_element(a.begin() + 1, a.end());
    vector<ll> cnt(max_x + 1, 0), p(max_x + 1, 0);
    for (int i = 1; i <= n; i++)
        p[a[i]]++;
    for (ll d = max_x; d >= 1; d --) {
        ll now = 0, os = (x * d + y) / z;
        ll pre = 0;
        for (int j = 1; j * d <= max_x; j++) {
            pre = (pre + p[j * d] * j) % TT;
        }
        for (int j = 1; j * d <= max_x; j++) {
            now = (now + pre * p[j * d] % TT * j) % TT;
        }
        ll oa = d * d % TT;
        now = oa * now % TT;
        cnt[d] = now;
        for (int j = 2; j * d <= max_x; j++)
            cnt[d] = ((cnt[d] - cnt[j * d]) % TT + TT) % TT;
        ans = (ans + cnt[d] * os) % TT;
    }
    print(ans);
    return 0;
}

C - 猫猫大队

Solution

把人类看作 \(0\)，猫猫状态看作 \(1\)

使用魔法就可以看成异或操作

Code

#include <bits/stdc++.h>
using  namespace std;
int main() {
    int op = 0;
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        int now; cin >> now;
        op ^= now;
    }
    if (op == 0) 
        cout << "zzy" << endl;
    else 
        cout << "miao" << endl;
    return 0;
}

D - 无限的韵律源点

Solution

total best 的维护非常简单，用一个小根堆维护即可

recent best 的维护较复杂，可以使用 set + 一个大根堆维护 \([i - ra + 1, i]\) 的前 \(rb\) 大值

具体地，先从 \(set\) 中删去不合法元素，再把 \(a[i]\) 插入大根堆中，再对 set 的最小值和大根堆的对顶进行交换

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pil;
const ll MAXN = 2e5+5;
ll n, b, ra, rb, a[MAXN], flag[MAXN], ans;
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> b >> ra >> rb;
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
	}
	priority_queue<ll, vector<ll>, greater<ll> > total;
	set<pil> st;
	priority_queue<pil> op;
	ll sum1 = 0, sum2 = 0;
	for(int i = 1; i <= n; i ++){
		if(total.size() < b || total.top() <= a[i]){
			sum1 += a[i];
			total.push(a[i]);
		}
		while(total.size() > b){
			sum1 -= total.top();
			total.pop();
		}
		
		op.push({a[i], i});
		for(int i = 1; i <= n; i ++){
			
		}
		while(!op.empty() && op.top().second <= max(0ll, i - ra))
			op.pop();
		if(flag[max(0ll, i - ra)]){
			st.erase({a[max(0ll, i - ra)], max(0ll, i - ra)});
			flag[max(0ll, i - ra)] = 0;
			sum2 -= a[max(0ll, i - ra)];
		}
		if(st.size() < rb || st.begin() -> first <= op.top().first){
			st.insert(op.top());
			sum2 += op.top().first;
			flag[op.top().second] = 1;
			op.pop();
		}
		while(st.size() > rb){
			sum2 -= st.begin() -> first;
			flag[st.begin() -> second] = 0;
			op.push(*st.begin());
			st.erase(st.begin());
		}
		ans = max(ans, sum1 + sum2);
	}
	cout << ans << endl;
	return 0;
}

E - 怯战蜥蜴

Solution

求前缀和，在前缀和上二分

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 2e5+5;
ll n, q, a[MAXN], s[MAXN], x;
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> q;
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
		s[i] = s[i - 1] + a[i];
	}
	while(q --){
		cin >> x;
		ll idx = upper_bound(s + 1, s + n + 1, x) - s;
		cout << idx - 1 << endl;
	}
	return 0;
}

H - To the Moon, Finding Paradise

Solution

考虑使用传送器不会造成能量损失，能量 \(w\) 越大，可走的边越多，\(s-t\) 的体力消耗值越小，满足单调性

二分答案能量 \(w\)，check 使用 \(BFS\) 查看 \(s-t\) 的最小值，若小于 \(c\) 则 check 成功

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const ll inf = 1e18;
int main() {
    int N, M, S, T, C; cin >> N >> M >> S >> T >> C;
    vector<ll> V(N + 1, 0);
    for (int i = 1; i <= N; i++) cin >> V[i];
    vector<vector<pii> > g(N + 1, vector<pii>());
    for (int i = 1; i <= M; i++) {
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back({v, w});
    }
    
    auto check = [&] (int W) {
        vector<ll> dis(N + 1, inf);
        priority_queue<pii, vector<pii>, greater<pii> > pq;
        pq.push({V[S], S}); dis[S] = V[S];
        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (d != dis[u]) continue;
            for (auto [v, w] : g[u]) {
                if (w > W) continue;
                if (dis[v] > d + V[v]) {
                    dis[v] = d + V[v];
                    pq.push({dis[v], v});
                }
            }
        }
        return dis[T] <= C;
    };
    
    int l = -1, r = 1e9;
    while (l + 1 < r) {
        int mid = l + r >> 1;
        if (check (mid)) r = mid;
        else l = mid;
    }
    cout << r << endl;
    return 0;
}

I - fumo 星

Solution

枚举两个点生成一条直线

最后把所有直线排序后去重即可

Code

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;

int cmp (double A, double B) {
    if (fabs(A - B) < eps) return 0;
    if (A < B) return -1;
    else return 1;
}

struct Node {
    double x, y;
    Node() {x = 0; y = 0;}
    bool operator <(const Node B) const {
        return x < B.x || (x == B.x && y < B.y);
    }
};

struct Line {
    double k, b;
    Line() {k = 0; b = 0;}
    Line(Node A, Node B) {
        if (A.x == B.x) {
            k = inf; b = A.x;
        }
        else {
            k = (A.y - B.y) / (A.x - B.x);
            b = A.y - k * A.x;
        }
    }
    bool operator <(const Line B) const {
        return k < B.k || (k == B.k && b < B.b);
    }
};

int main() {
    int n; cin >> n;
    vector<Node> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].x >> a[i].y;
    }
    sort (a.begin(), a.end());
    for (int i = 1; i < n; i++) {
        if (cmp(a[i].x, a[i - 1].x) == 0 && cmp (a[i].y, a[i - 1].y) == 0) {
            cout << "inf" << endl;
            return 0;
        }
    }
    vector<Line> p;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            p.push_back(Line(a[i], a[j]));
        }
    int cnt = 0;
    sort (p.begin(), p.end());
    for (int i = 1; i < p.size(); i++) {
        if (cmp(p[i].k, p[i - 1].k) == 0 && cmp(p[i].b, p[i - 1].b) == 0)
            cnt ++;
    }
    cout << p.size() - cnt << endl;
    return 0;
}

J - 上春山

Solution

当高度为 \(k\) 时，答案为

\[\sum\limits_{h_i<k} h_i-(a_i-k) \]

按照 \(h_i\) 从大到小排序后，\(\sum h_i\) 和 \(\sum a_i\) 可以求出来，\(\sum k=k\times j\) 其中 \(j\) 表示 \(h_i\) 比 \(k\) 大的个数

由于每部分都说独立的，所以 \(k\) 越大越好，也就是取当前最矮的 \(h_i -1\)

就这样枚举找出最大值即可

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Node {
    ll h, a;
    bool operator < (const Node B) const {
        return h > B.h || (h == B.h && a < B.a);
    }
};

ll ans = 0;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;cin >> n;
    vector<Node> p(n);
    for (int i = 0; i < n; i++)
        cin >> p[i].h;
    for (int i = 0; i < n; i++)
        cin >> p[i].a;
    sort(p.begin(), p.end());
    ll sum_h = 0, sum_a = 0;
    for (int i = 0; i < n;) {
        int j = i;
        while (j < n && p[j].h == p[i].h) {
            sum_h += p[j].h;
            sum_a += p[j].a;
            j++;
        }
        ll k = p[i].h - 1;
        ll now = sum_a - sum_h + k * j;
        ans = max (ans, now);
        i = j;
    }
    cout << ans << endl;
    return 0;
}

L - 南湖少年团

Solution

直接使用 substr 截下来字符串即可

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    string s1, s2; cin >> s1 >> s2;
    int ans = 0;
    for (int i = 0; i + s1.size() - 1 < s2.size(); i++) {
        if (s2.substr(i, s1.size()) == s1)
            ans ++;
    }
    cout << ans << endl;
    return 0;
}

M - 上帝造题的八分钟

Solution

数位 DP 板子题

定义 \(dp[pos][cp][pre1][pre2][limit][lead]\)

表示枚举到 \(pos\) 位置，差值位 \(cp\)，前一个位置为 \(pre1\)，前两个位置为 \(pre2\)，最大限制和前导零限制

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll TT = 1e9 + 7;

ll dp[104][205][11][11][2][2][2];

ll dfs(int pos, int cp, int pre1, int pre2, int limit, int n3, int lead, vector<int> &num) {
    ll ret = 0;
    if (pos == -1)
        return n3 && (abs (cp - 100) >= 1);
    if (~ dp[pos][cp][pre1][pre2][limit][n3][lead])
        return dp[pos][cp][pre1][pre2][limit][n3][lead];
    int up = (limit ? num[pos] : 9);
    for (int i = 0; i <= up; i++) {
        if (lead && i == 0)
            ret += dfs (pos - 1, cp, i, pre1, limit && (i == up), n3 , 1, num);
        else 
            ret += dfs (pos - 1, cp + (i == 0) - (i == 1), i, pre1, limit && (i == up), n3 | (i == 3 && pre1 == 3 && pre2 == 3), 0, num);
        ret %= TT;
    }
    return dp[pos][cp][pre1][pre2][limit][n3][lead] = ret;
}

ll solve(vector<int> p) {
    memset(dp, -1, sizeof dp);
    return dfs (p.size() - 1, 100, -1, -1, 1, 0, 1, p);
}

int check (string s) {
    int op = 0, op2 = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '1') op ++;
        if (s[i] == '0') op --;
    }
    for (int i = 0; i + 3 - 1 < s.size(); i++) {
        if (s.substr(i, 3) == (string)"333")
            op2 |= 1;
    }
    op = (abs (op) >= 1);
    return op && op2;
}

int main() {
    string l, r; cin >> l >> r;
    vector<int> L, R;
    for (int i = 0; i < l.size(); i++)
        L.push_back(l[i] - '0');
    for (int i = 0; i < r.size(); i++)
        R.push_back(r[i] - '0');

    reverse(R.begin(), R.end());
    reverse(L.begin(), L.end());
    ll ans = ((solve(R) - solve(L) + check(l)) % TT + TT) % TT;
    cout << ans << endl;
    return 0;
}

标签：int,题解,ll,华中农业大学,cin,++,第十三届,sum,size
From： https://www.cnblogs.com/martian148/p/18134727

相关文章

  • [题解]P1629 邮递员送信
    好久不写图论题了，Dijkstra都花了好长时间捡起来……之前也没有接触过反图的概念。这个题算是我重拾图论知识以来的第一题了。__φ(．．)P1629邮递员送信Dijkstra是单源最短路的算法。但这个题除了要求节点\(1\)到其他节点的距离，还要知道其他节点回到节点\(1\)的距离。如果我们每个......
  • [POI2012] Rendezvous 题解
    众所周知，\(lyh\)是一名压行大师，也是一名\(juruo\)，所以他将他繁琐的方法用\(102\)行表现了出来……明显原题为基环内向树森林。首先用并查集计算连通块，不在一个连通块里的答案就是\(-1\-1\)。发现实际上答案就是以环为根节点，求\(lca\)的结果，求完后可以分为两种情况：根......
  • [ABC349] AtCoder Beginner Contest 349 题解
    [ABC349]AtCoderBeginnerContest349题解目录[ABC349]AtCoderBeginnerContest349题解A-ZeroSumGameB-CommencementC-AirportCodeD-DivideIntervalE-WeightedTic-Tac-ToeF-SubsequenceLCMG-PalindromeConstruction总结A-ZeroSumGame零和博弈，......
  • P10289 [GESP样题 八级] 小杨的旅游 题解
    题目简述给定一棵树，节点之间的距离为$1$，树上有$k$个传送门，可以从一个传送门瞬间传送到另一个传送门，有$q$此询问，问$u$和$v$之间的最短距离是多少。题目分析首先考虑没有传送门，我们可以直接求两个点的LCA，再用高度容斥计算即可。如果有传送门，那么有用与不用两种选择，如......
  • 【官方题解】Codeforces Round 939 (Div. 2)
    CodeforcesRoundAyachiNeneSolutions(div.2)A.Nene'sGameIdea:[user:Otomachi_Una]Solution不难发现如果一个人初始位置\(p\geqa_1\)，那么必然会在有限次回合当中被踢出。答案即为\(\min(n,a_1-1)\)。B.NeneandtheCardGameIdea:[user:Otomachi_Una]Hint......
  • 华中农业大学第十三届程序设计竞赛
    题目链接Bsyh喜欢猫猫，所以zzy为了哄syh睡觉，决定扮成猫猫。给定一个长为\(n\)的序列\(\{a_i\}\)和三个正整数\(x，y，z\)，计算\(\sum_{i=1}^n\sum_{j=1}^na_ia_j\lfloor\dfrac{x\gcd(a_i,a_j)+y}{z}\rfloor\)的值。答案对\(10^9+7\)取模。如果这个问题的答案能够......
  • [暴力题解系列+正经题解]好数
    好数虽然不是13号考的那批人，但是还是扔一个暴力题解在这里。首先数据范围\(n\le10^7\)，就算纯粹暴力去做也只是\(O(nlogn)\)，也就是直接从1到n去枚举。秉持着暴力就是要优化细节的精神，对题目进行一个分析，发现无论如何，个位数必须是奇数，否则必然不满足条件，那么优化手段就显而易见了......
  • P8741 [蓝桥杯 2021 省 B] 填空问题 题解
    题目传送门试题A：空间【解析】本题考察计算机存储的基础知识，只要掌握空间存储的换算方法，就能够算出答案。【程序】#include<bits/stdc++.h>usingnamespacestd;intmain(){printf("%d\n",256*8/32*1024*1024);return0;}【答案】67108864......
  • P8679 [蓝桥杯 2019 省 B] 填空问题 题解
    题目传送门试题A：组队【解析】本题是一道经典的DFS搜索题，每次对各号位的选手进行DFS，找到各号位上有成绩的选手时再进行进一步搜索即可。【程序】#include<bits/stdc++.h>usingnamespacestd;intteam[20][6];intmax_sum;boolvis[20];voiddfs(intu,intsu......
  • P9686 Judg. 题解
    题目传送门一道简单模拟。这道题最简单的方法就是直接在for循环中判断题目给出状态是否为AC，如果不是则输出当前\(i\)的值，否则就不输出。#include<bits/stdc++.h>usingnamespacestd;constintMAXN=1e5+10;intn;stringa[MAXN];intmain(){ scanf("%......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99