首页 > 其他分享 >AcWing第84场周赛

AcWing第84场周赛

时间:2023-01-01 19:11:07浏览次数:57  
标签:周赛 int namespace cin long using include 84 AcWing

本蒟蒻第一次AK周赛


第一题、最大数量

本题使用桶排序

代码

#include<bits/stdc++.h>
using namespace std;
int m[10005];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int a,b;
        cin>>a>>b;
        m[(a*100)+b]++;
    }
    sort(m,m+2459);
    cout<<m[2458];
    return 0;
}

第二题、前缀和序列

前置知识:AcWing算法基础课——前缀和

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100010;
int a[N],q[N],b[N],q1[N];
signed main()
{
    int n,m;
    cin>>n;
    q[0]=0;
    for(int i=1;i<=n;i++) {cin>>a[i];b[i]=a[i];}
    sort(b+1,b+1+n);
    cin>>m;
    for(int i=1;i<=n;i++) {q[i]=q[i-1]+a[i];q1[i]=q1[i-1]+b[i];}
    while(m--){
        int s,l,r;
        cin>>s>>l>>r;
        if(s==1){
            cout<<q[r]-q[l-1]<<endl;
        }
        else cout<<q1[r]-q1[l-1]<<endl;

    }
}

第三题、买可乐

第一种方法、暴力

时间复杂度:$O(n)$

#include <iostream>
#include <cstring>
#include <algorithm>
typedef long long LL;
using namespace std;
LL c, d, n, m, k;

int main() {
	cin >> c >> d >> n >> m >> k;
	LL need = n * m - k;
	if (need <= 0) {
		cout << 0 << endl;
		return 0;
	}
	LL ans = 1e18;
	for (LL i = 0; i <= 10000; i ++ )
		for (LL j = 0; j <= 10000; j ++ )
			if (n * i + j >= need)
				ans = min(ans, c * i + d * j);
	cout << ans << endl;
	return 0;
}

第二种方法、贪心

时间复杂度$O(1)$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int c, d, n, m, k;
    cin >> c >> d >> n >> m >> k;
    int cnt = n * m - k;
    if (cnt <= 0) puts("0");
    else
        cout << min({cnt * d, cnt / n * c + cnt % n * d, (cnt + n - 1) / n * c}) << endl;

    return 0;
}

标签:周赛,int,namespace,cin,long,using,include,84,AcWing
From: https://www.cnblogs.com/LuoGuyexc/p/17018444.html

相关文章

  • CCNUACM寒假培训第二周周赛部分题解(ACF)
    A题大意:给出n个数,每次可以选择任意一个数进行加一操作,可执行k次,求最大值可能的最大最小值考虑最大值最大,即所有操作都对初始n个数中的最大值进行,答案即max(a1,.....,an)+......
  • [第326场周赛]分解质因数,埃氏筛,欧拉筛
    leetcode新年福利,本次周赛没有Hard难度的题目,然后我就第一次AK了~总的来说不是很难,涉及到了三个算法,在此记录一下。分解质因数题目链接:​​6279.数组乘积中的不同质因数数......
  • leetcode-584. 寻找用户推荐人
    584.寻找用户推荐人-力扣(Leetcode)sql题,还是比较简单的#WriteyourMySQLquerystatementbelowselectnamefromcustomerwherereferee_id<>2orreferee_id......
  • Codeforces Round #841 (Div. 2) and Divide by Zero 2022 比赛总结
    vp的一场比赛,打得还行,有点慢。注意:前两道题的特色是答案需要\(\times2022\)输出。A.JoeyTakesMoney简单题,一定是\(n-1\)个\(1\)和一个\(\displaystyle\prod......
  • AcWing362. 区间
    题目描述给定\(n\)个区间\([a_i,b_i]\)和\(n\)个整数\(c_i\)。你需要构造一个整数集合\(Z\),使得\(\foralli\in[1,n]\),\(Z\)中满足\(a_i\lex\leb_i\)......
  • CodeForces Round #841 (Div. 2) vp记
    在2022年的最后一天,和大神stOJerry__JiangOrz开了一场CodeForces的vp,顺便来水一下博客。前言:前两题的输出为actualanswer\(\times2022\)CodeForcesRound#......
  • ACWING 第 84 场周赛 ABC
    来水一篇博客:)https://www.acwing.com/activity/content/competition/problem_list/2742/难度偏低(三题都cf800的难度),就不写详解了4788.最大数量#include<bits/stdc++......
  • LeetCode第 94 场双周赛
    1.最多可以摧毁的敌人城堡数目题目最多可以摧毁的敌人城堡数目Solution可以第一重循环找到\(1\),然后从该位置分别向左和向又寻找\(-1\),寻找过程中遇到\(1\)则停止,不......
  • AcWing 1359. 洛谷P1457 城堡
    解题思路\(\qquad\)这道题目是需要维护各种连通块信息的,所以这里我们可以也用并查集维护。这题我们如果注意一点细节,也是可以让代码变得很简洁的:\(\qquad\quad1.\)这道......
  • LeetCode周赛325
    到目标字符串的最短距离题目SolutionclassSolution{public:intclosetTarget(vector<string>&words,stringtarget,intstartIndex){intn=wo......