（AtCoder Beginner Contest 306）

news/2024/10/28 18:24:46/

A.直接模拟吧不解释了

import random
import sys
import os
import math
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from itertools import accumulate, combinations, permutations
from heapq import nsmallest, nlargest, heapify, heappop, heappush
from io import BytesIO, IOBase
from copy import deepcopy
import threading
import bisectBUFSIZE = 4096class FastIO(IOBase):newlines = 0def __init__(self, file):self._fd = file.fileno()self.buffer = BytesIO()self.writable = "x" in file.mode or "r" not in file.modeself.write = self.buffer.write if self.writable else Nonedef read(self):while True:b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))if not b:breakptr = self.buffer.tell()self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)self.newlines = 0return self.buffer.read()def readline(self):while self.newlines == 0:b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))self.newlines = b.count(b"\n") + (not b)ptr = self.buffer.tell()self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)self.newlines -= 1return self.buffer.readline()def flush(self):if self.writable:os.write(self._fd, self.buffer.getvalue())self.buffer.truncate(0), self.buffer.seek(0)class IOWrapper(IOBase):def __init__(self, file):self.buffer = FastIO(file)self.flush = self.buffer.flushself.writable = self.buffer.writableself.write = lambda s: self.buffer.write(s.encode("ascii"))self.read = lambda: self.buffer.read().decode("ascii")self.readline = lambda: self.buffer.readline().decode("ascii")sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")def I():return input()def II():return int(input())def MI():return map(int, input().split())def LI():return list(input().split())def LII():return list(map(int, input().split()))def GMI():return map(lambda x: int(x) - 1, input().split())def LGMI():return list(map(lambda x: int(x) - 1, input().split()))def solve():n=II()a=I()b=afor x,y in zip(a,b):print(x,end="")print(y,end="")if __name__ == '__main__':for _ in range(1):solve()

B.也直接模拟c的话记得开longlong

import random
import sys
import os
import math
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from itertools import accumulate, combinations, permutations
from heapq import nsmallest, nlargest, heapify, heappop, heappush
from io import BytesIO, IOBase
from copy import deepcopy
import threading
import bisectBUFSIZE = 4096class FastIO(IOBase):newlines = 0def __init__(self, file):self._fd = file.fileno()self.buffer = BytesIO()self.writable = "x" in file.mode or "r" not in file.modeself.write = self.buffer.write if self.writable else Nonedef read(self):while True:b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))if not b:breakptr = self.buffer.tell()self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)self.newlines = 0return self.buffer.read()def readline(self):while self.newlines == 0:b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))self.newlines = b.count(b"\n") + (not b)ptr = self.buffer.tell()self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)self.newlines -= 1return self.buffer.readline()def flush(self):if self.writable:os.write(self._fd, self.buffer.getvalue())self.buffer.truncate(0), self.buffer.seek(0)class IOWrapper(IOBase):def __init__(self, file):self.buffer = FastIO(file)self.flush = self.buffer.flushself.writable = self.buffer.writableself.write = lambda s: self.buffer.write(s.encode("ascii"))self.read = lambda: self.buffer.read().decode("ascii")self.readline = lambda: self.buffer.readline().decode("ascii")sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")def I():return input()def II():return int(input())def MI():return map(int, input().split())def LI():return list(input().split())def LII():return list(map(int, input().split()))def GMI():return map(lambda x: int(x) - 1, input().split())def LGMI():return list(map(lambda x: int(x) - 1, input().split()))def solve():a=LII()res=0for i in range(0,64):res+=pow(2,i)*a[i]print(res)if __name__ == '__main__':for _ in range(1):solve()

C.把每个数字位置拿出来排个序即可

import random
import sys
import os
import math
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from itertools import accumulate, combinations, permutations
from heapq import nsmallest, nlargest, heapify, heappop, heappush
from io import BytesIO, IOBase
from copy import deepcopy
import threading
import bisectBUFSIZE = 4096class FastIO(IOBase):newlines = 0def __init__(self, file):self._fd = file.fileno()self.buffer = BytesIO()self.writable = "x" in file.mode or "r" not in file.modeself.write = self.buffer.write if self.writable else Nonedef read(self):while True:b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))if not b:breakptr = self.buffer.tell()self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)self.newlines = 0return self.buffer.read()def readline(self):while self.newlines == 0:b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))self.newlines = b.count(b"\n") + (not b)ptr = self.buffer.tell()self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)self.newlines -= 1return self.buffer.readline()def flush(self):if self.writable:os.write(self._fd, self.buffer.getvalue())self.buffer.truncate(0), self.buffer.seek(0)class IOWrapper(IOBase):def __init__(self, file):self.buffer = FastIO(file)self.flush = self.buffer.flushself.writable = self.buffer.writableself.write = lambda s: self.buffer.write(s.encode("ascii"))self.read = lambda: self.buffer.read().decode("ascii")self.readline = lambda: self.buffer.readline().decode("ascii")sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")def I():return input()def II():return int(input())def MI():return map(int, input().split())def LI():return list(input().split())def LII():return list(map(int, input().split()))def GMI():return map(lambda x: int(x) - 1, input().split())def LGMI():return list(map(lambda x: int(x) - 1, input().split()))def solve():n=II()p=[[] for _ in range(0,n+10)]a=LII()for i,x in enumerate(a):p[x].append(i+1)res=[]for i in range(1,n+1):p[i].sort()res.append([p[i][1],i])res.sort()for i in range(0,n):print(res[i][1],end=" ")if __name__ == '__main__':for _ in range(1):solve()

D

很明显一个状态机dp

状态表示，前i个选项里的最大值，且当前状态是无毒或者有毒

如果有毒，只能从前面的无毒转移过来或者不选当前选项从前面有毒继续转移过来

如果无毒，可以从前面有毒或者无毒或者不选转移过来

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;const int N = 5e5+10;
typedef pair<int, int> PII;
int n,m,k;
PII a[N];
long long f[N][3];
signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);cin>>n;//f[0]代表当前有毒，[1]无毒for(int i=1;i<=n;i++){cin>>a[i].first>>a[i].second;}memset(f,-0x3f,sizeof(f));f[0][0]=0;f[0][1]=0;for(int i=1;i<=n;i++){if(a[i].first==0){f[i][0]=f[i-1][0];f[i][1]=max({f[i-1][1]+a[i].second,f[i-1][1],f[i-1][0]+a[i].second});}else{f[i][1]=f[i-1][1];f[i][0]=max({f[i-1][0],f[i-1][1]+a[i].second});}}cout<<max(f[n][0],f[n][1])<<"\n";
}

E

拿两个set维护

第一个set维护最大的k个，第二个维护剩余数

每次把全部数的最大的k个通过st1和st2的最小值和最大值交换即可

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;const int N = 5e5+10;
int n,m,k;
int a[N];
signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);cin>>n>>k>>m;multiset<long long> st1,st2;long long res=0;for(int i=1;i<=n;i++){if(i<=k) st1.insert(0);else st2.insert(0);}while (m -- ){int x,y;cin>>x>>y;int z=a[x];if(st1.find(a[x])!=st1.end()){st1.erase(st1.lower_bound(a[x]));res-=a[x];}else{st2.erase(st2.lower_bound(a[x]));}a[x]=y;st1.insert(a[x]);res+=a[x];while(st1.size()>k){auto it=*st1.begin();st2.insert(it);st1.erase(st1.begin());res-=it;}while(st1.size()&&st2.size()&&*st1.begin()<*st2.rbegin()){auto a=*st1.begin(),b=*st2.rbegin();res+=b-a;st2.insert(a);st2.erase(st2.lower_bound(b));st1.insert(b);st1.erase(st1.lower_bound(a));}cout<<res<<"\n";}
}

F.离散化+树状数组

首先先别想那么多，对于第一个集合的第一个数他的所有贡献是啥呢

贡献就是下面全部集合比他小的值的全部个数

所以要有个数据结构可以边添加边询问前缀的总和（树状数组或者线段树）

从最后一个集合遍历即可，边加贡献边添加数

到这里还没结束，因为还没算自己集合的，自己集合前面比自己小的数也要算贡献

第i个集合下面有（n-i）个集合要和他匹配，且前面有j个比自己小，别忘了这个贡献

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;const int N = 1e4+10,M=110,H=1e6+10;
typedef pair<int, int> PII;
int n,m,k;
int a[N][M];
vector<int> num;
int tr[H];
int lowbit(int x)
{return x & -x;
}void add(int x, int c)  // 位置x加c
{for (int i = x; i <=num.size(); i += lowbit(i)) tr[i] += c;
}int sum(int x)  // 返回前x个数的和
{int res = 0;for (int i = x; i; i -= lowbit(i)) res += tr[i];return res;
}int find(int x){return lower_bound(num.begin(),num.end(),x)-num.begin()+1;
}
signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];num.push_back(a[i][j]);}}sort(num.begin(),num.end());num.erase(unique(num.begin(),num.end()),num.end());long long res=0;for(int i=n;i>=1;i--){for(int j=1;j<=m;j++){int x=find(a[i][j]);res+=sum(x);res+=(n-i)*j;}for(int j=1;j<=m;j++){add(find(a[i][j]),1);}}cout<<res<<"\n";
}


http://www.ppmy.cn/news/444356.html

相关文章

C语言基础教程（动态内存分配）

C语言基础教程（动态内存分配）

文章目录 前言一、动态内存分配常用函数二、动态内存分配实战总结 前言 本篇文章来讲解C语言中的动态内存分配&#xff0c;在C语言中动态内存分配经常使用&#xff0c;合理的使用动态内存分配可以帮助我们节省代码空间&#xff0c;当然了不合理的使用可能导致程序的崩溃&#…
阅读更多...
59、基于51单片机多机 NRF24L01 无线温湿度 DHT11报警系统设计(程序+原理图+PCB源文件+参考论文+开题报告+任务书+元器件清单等)

59、基于51单片机多机 NRF24L01 无线温湿度 DHT11报警系统设计(程序+原理图+PCB源文件+参考论文+开题报告+任务书+元器件清单等)

摘 要 温湿度在工农业生产中占有很重要的地位&#xff0c;是工农业生产的重要组成数据。温湿度过高会造成粮食发霉长芽&#xff0c;还会引起大棚蔬菜一系列的病害。因此对其适时准确的测量就显得尤为重要。而一般的测量过程较为复杂繁琐&#xff0c;误差还大。比如现在所使…
阅读更多...
C++实验报告-1

C++实验报告-1

C实验报告-1 实验题目1 【旱冰场围栏造价】有一个圆形的旱冰场地&#xff0c;围栏用帆布围成&#xff0c;每平方米造价M元&#xff0c;输入旱冰场半径和围栏高度&#xff0c;用程序计算出其造价。类的声明已给出&#xff0c;请完善成员函数的定义和主函数。 程序源代码 #inc…
阅读更多...
电商行业线上活动方式有哪些优缺点（一）

电商行业线上活动方式有哪些优缺点（一）

电商行业线上活动方式有哪些优缺点&#xff08;一&#xff09; 如今电商行业发展的越来越快速&#xff0c;而且电商行业的线上活动营销方式也越来越多&#xff0c;商家们总能把握住各种节假日做营销活动。例如三月份的三八妇女节&#xff0c;传统的节假日&#xff0c;十一月份…
阅读更多...
vgp虚拟路面_吉水县道路运输展示价格实惠

vgp虚拟路面_吉水县道路运输展示价格实惠

吉水县道路运输展示价格实惠 北京四度的道路运输展示&#xff0c;首先&#xff0c;我们要知道什么是数字展厅&#xff1f;其实&#xff0c;我们在生活中所听到的数字化展厅&#xff0c;以及多媒体数字化展厅都是指多媒体数字化展厅。多媒体数字化展厅主要是把多媒体和数字化的技…
阅读更多...
seo名词术语解释网站优化名词术语

seo名词术语解释网站优化名词术语

1、图解seo黑帽。什么是黑帽seo&#xff1f; 我们定义seo黑帽这个名词是一切 违背正常思路制作、宣传、推广、排名网站的行为都称为黑帽seo。 这里的seo黑帽也是作弊的概念。 黑帽seo手法侧重于搜索引擎单方面的计算特性&#xff0c;利用一个特点狠狠的用力&#xff0c;短期内达…
阅读更多...
程序员为维持游戏开发被迫炒股，没想到一年内反赚1600万

程序员为维持游戏开发被迫炒股，没想到一年内反赚1600万

公众号后台回复“图书“&#xff0c;了解更多号主新书内容贾浩楠 博雯 发自 凹非寺 量子位 报道 | 公众号 QbitAI “不会炒股的游戏开发不是好飞机修理工….” 没抖机灵&#xff0c;这是真事&#xff01; 一开始我也不信&#xff0c;根本没人信。 辞掉军火巨头旱涝保收的工作&a…
阅读更多...
条件生成对抗神经网络,生成对抗网络gan原理

条件生成对抗神经网络,生成对抗网络gan原理

关于GAN生成式对抗网络中判别器的输出的问题 。 ...摘要生成式对抗网络GAN&#xff08;Generativeadversarialnetworks&#xff09;目前已经成为人工智能学界一个热门的研究方向.GAN的基本思想源自博弈论的二人零和博弈&#xff0c;由一个生成器和一个判别器构成&#xff0c;…
阅读更多...
最新文章

Copyright @ 2022~2023