极值你太美
2024-09-11 18:07:06
发布于:北京
https://www.acgo.cn/contest/detail/4344?matchRoundId=4344&examId=45980&teamCode=1661232050350374912&openLevel=2
NSRe
https://www.acgo.cn/contest/detail/3428?matchRoundId=3428&examId=43603&teamCode=1661232050350374912&openLevel=2
答题链接:ACGO平台:
https://www.acgo.cn/contest/detail/3593?matchRoundId=3593&examId=43801&teamCode=1661232050350374912&openLevel=2
邀请码:xTHX
//逆序对
#include <iostream>
using namespace std;
const int N = 5e5 + 10;
int a[N], tmp[N];
long long n, ans;
//a的[L1,R1] 和 [L2,R2] 做归并
void Merge(int a[], int L1, int R1, int L2, int R2)
{
//3、两个序列依次合并
int i = L1, j = L2;
int cnt = 0;
while (i <= R1 && j <= R2)
{
if (a[i] <= a[j])
tmp[cnt++] = a[i++];
else
{
//3.1、右区间的a[j]大于左区间的a[i],则a[j]与左区间的i~R1的所有数全部构成逆序对
tmp[cnt++] = a[j++];
ans += R1 - i + 1;
}
}
//左半段剩余的元素
while (i <= R1) tmp[cnt++] = a[i++];
//右半段剩余的元素
while (j <= R2) tmp[cnt++] = a[j++];
//0~cnt-1,tmp复制到a
for (int i = 0; i < cnt; i++)
{
a[L1 + i] = tmp[i];
}
}
void MergeSort(int a[], int l, int r)
{
if (l >= r)
return; //只有一个元素,划分结束,返回
int mid = (l + r) / 2;
MergeSort(a, l, mid); //递归处理左半边[l,mid]
MergeSort(a, mid + 1, r);//递归处理右半边[mid+1,r]
Merge(a, l, mid, mid + 1, r);//两个半边做归并
}
int main()
{
//1、定义变量、数组,进行输入
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
//2、归并排序,递归处理
MergeSort(a, 1, n);
cout << ans;
return 0;
}
9
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 7;
//1、定义变量n,x,数组
int n , a[maxn] , x;
int main()
{
//2、输入变量n,数组,x
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];
cin >> x;
//3、lower_bound函数,求第一个大于等于的位置
int pos = lower_bound(a , a + n , x) - a;
//4、输出
cout << pos;
return 0;
}
8
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e2 + 9;
//1、定义变量n,m,数组
int n , m;
int a[maxn];
bool cmp(int x , int y){
return x > y;
}
int main(){
//2、输入变量n,m,数组
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> a[i];
//3、从大到小排序
sort(a + 1 , a + 1 + n , cmp);
//4、定义变量sum,统计答案
int sum = 0;
//5、排序后的前m张钱累加
for(int i = 1; i <= m; i++)
sum += a[i];
//6、输出答案
cout << sum;
return 0;
}
4
30 1
10 1
50 2
20 2
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 9;
struct node {
int p, d;
}a[maxn];
bool cmp(node A, node B) {
return A.d < B.d;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].p >> a[i].d;
}
sort(a + 1, a + n + 1, cmp);
priority_queue<int, vector<int>, greater<int> >q;
for (int i = 1; i <= n; i++) {
if (a[i].d == q.size()) {
if (a[i].p > q.top()) {
q.pop();
q.push(a[i].p);
}
}
else if(a[i].d > q.size()) {
q.push(a[i].p);
}
}
long long ans = 0;
while (q.size()) {
ans += q.top();
q.pop();
}
cout << ans;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 9;
int heap[maxn], heap_size;
void put(int d) {
int son, pa;
heap[++heap_size] = d;//新增一个结点,值为d
son = heap_size;
while (son > 1) { //向上调整,使其满足小根堆的性质
pa = son >> 1; //找到父节点
if (heap[son] >= heap[pa]) break; //如果父节点的值小于等于儿子结点,调整完毕
swap(heap[son], heap[pa]); //向上调整
son = pa;
}
}
//返回堆顶的值,并删除堆顶
int get() {
int pa, son, res;
res = heap[1]; //存储堆顶的值
heap[1] = heap[heap_size--]; //用最后一个元素覆盖堆顶,并把堆元素个数减一
pa = 1;
//向下调整
while (pa * 2 <= heap_size) {
son = pa * 2;
if (son < heap_size && heap[son + 1] < heap[son]) son++;//找到存在的儿子中最小的一个
if (heap[pa] <= heap[son]) break; //调整完毕
swap(heap[pa], heap[son]);//向下调整
pa = son;
}
return res;//返回堆顶的值
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int a;
cin >> a;
put(a);
}
int ans = 0;
while (heap_size > 1) {
int x = get(), y = get();
ans += x + y;
put(x + y);
}
cout << ans;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
struct node{
int from , to , len;
};
vector<node>v[505];
int n , m , w , x , y , z;
int d[510];
int main(){
scanf("%d %d %d",&n,&m,&w);
for(int i = 2 ; i <= n ; i++){
d[i] = 1e9;
}
for(int i = 0 ; i < m ; i++){
scanf("%d %d %d",&x , &y , &z);
v[x].push_back((node){x,y,z});
v[y].push_back((node){y,x,z});
}
for(int i = 0 ; i < w ; i++){
scanf("%d %d %d",&x,&y,&z);
v[x].push_back((node){x,y,-z});
}
int from,to,len;
for(int k = 0 ; k < n ; k++){
for(int i = 1 ; i <= n ; i++){
for(int j = 0 ; j < v[i].size() ; j++){
from = v[i][j].from , to = v[i][j].to , len = v[i][j].len;
if(d[to] > d[from] + len){
d[to] = d[from] + len;
if(k == n - 1){
printf("YES\n");
return 0;
}
}
}
}
}
printf("NO\n");
return 0;
}
//阶乘和
#include<iostream>
#include<cstring>
using namespace std;
int n , a[90] , b[90] , c[90] , f[90] , d = 0; //定义变量
int l1 , l2 = 1 , l = 1 , len_ans , m = 1; //定义变量
int main(){ //主函数开始
cin >> n;
b[0] = 1; //初始化b数组
for(int i = 1 ; i <= n ; i++){ //计算i的阶乘,
len_a = 0; //i的长度
int p = i; //临时的i
while(p > 0){ //把i的每一位存进a数组
a[l1++] = p % 10; //取余数存入a数组
p /= 10;
}
for(int j = 0 ; j < l1 ; j++){ //遍历a数组
for(int k = 0 ; k <= l2 ; k++){ //遍历b数组
c[j+k] += a[j] * b[k]; //将a和b对应位相乘并累加到c数组中
}
}
for(int j = 0;j < l ; j++){ //遍历c数组 进位
if(c[j] > 9){
c[j+1] += c[j] / 10;
c[j] %= 10;
} 23 7
} 21 14
1 6 1
if(c[l]){ //如果c数组长度增加,更新l的值 逐步构建 1*2*3*4*5
l++;
}
len_ans = l2 , l2 = l; //更新len_ans和l2的值
m = max(m,l); //更新m的值
for(int k = l - 1 ; k >= 0 ; k--){ //倒序遍历c数组
b[k] = c[k]; //将c数组的值赋给b数组
}
l = l1 + len_ans; //更新l的值
memset(c,0,sizeof(c)); //清零c数组,准备计算下个阶乘
for(int j = 0 ; j < m ; j++){ //高精加,直接套模板
f[j] += b[j]; //将b数组的值累加到f数组中
if(f[j] > 9){ //如果当前位大于9,需要进位
f[j+1] += f[j] / 10; //进位到下一位
f[j] %= 10;
}
}
}
while(!f[m] && m > 0){ //去掉首导零
m--;
}
for(int i = m ; i >= 0 ; i--){ //倒序遍历f数组
cout << f[i]; //输出结果
}
return 0; //返回0表示程序正常结束
}
全部评论 23
🆗
2024-02-02 来自 北京
3鸡你太美
2024-02-02 来自 北京
3!
2024-02-05 来自 北京
2鸡
2024-07-09 来自 北京
0一加手机 永远第一
2024-07-09 来自 北京
0
MEI
424
2024-02-03 来自 北京
2666
2024-02-02 来自 北京
2讲你又不听,听你又不懂,懂你又不做,做你又做错,错你又不认,认你又不改,改你又不服,不服你又不出声
2024-02-02 来自 北京
2切,阿里嘎多美羊羊桑
2024-02-05 来自 北京
1切,阿里嘎多美羊羊桑
2024-02-19 来自 北京
0切,阿里嘎多美羊羊桑
2024-02-20 来自 北京
0
鸡
2024-02-02 来自 北京
2巴
2024-02-03 来自 北京
16
2024-02-03 来自 北京
1巴
2024-02-16 来自 北京
0
我创了一个题
U9188.小摔炮2024-02-05 来自 北京
1666
2024-02-03 来自 北京
1666
2024-02-03 来自 北京
1666
2024-02-03 来自 北京
134
2024-02-03 来自 北京
1波 波波鸡 波呀波波鸡
2024-02-03 来自 北京
1一元一串的波 波鸡
2024-02-03 来自 北京
1波 波波鸡 波呀波波鸡,一元一串的波 波鸡,波 波波鸡 波呀波波鸡,一元一串的波 波鸡,波 波波鸡 波呀波波鸡,一元一串的波 波鸡,波 波波鸡 波呀波波鸡,一元一串的波 波鸡,波 波波鸡 波呀波波鸡,一元一串的波 波鸡,波 波波鸡 波呀波波鸡,一元一串的波 波鸡,波 波波鸡 波呀波波鸡,一元一串的波 波鸡
2024-02-03 来自 北京
1波 波波鸡 波呀波波鸡,一元一串的波 波鸡,波 波波鸡 波呀波波鸡,一元一串的波 波鸡,波 波波鸡 波呀波波鸡,一元一串的波 波鸡,波 波波鸡 波呀波波鸡,一元一串的波 波鸡,波 波波鸡 波呀波波鸡,一元一串的波 波鸡,波 波波鸡 波呀波波鸡,一元一串的波 波鸡,波 波波鸡 波呀波波鸡,一元一串的波 波鸡波 波波鸡 波呀波波鸡,一元一串的波 波鸡,波 波波鸡 波呀波波鸡,一元一串的波 波鸡,波 波
2024-02-05 来自 北京
0
老师还有生命体征就扣1
2024-08-12 来自 北京
0我活着很好,看你的了
2024-08-14 来自 北京
0
主播你在哪个营
2024-08-11 来自 北京
0我在金源营
2024-08-14 来自 北京
0
?
2024-06-17 来自 广东
0?
2024-05-26 来自 广东
06666
2024-04-05 来自 北京
0.............
2024-02-25 来自 广东
0切,阿里嘎多美羊羊桑
2024-02-23 来自 广东
0
有帮助,赞一个