Codeforces Round 876 (Div. 2) A～D

news/2025/2/21 7:12:08/

A B C 就不说了，看懂题目就能AC。

A

#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <stdio.h>
#include<vector>
#include<queue>
#include<map>
#include <unordered_map>
#include<set>
#include<tuple>
#include<numeric>
#include<stack>
using namespace::std;
typedef long long  ll;
inline char nc() {static char buf[1000000], *p1 = buf, *p2 = buf;return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename _Tp> inline void read(_Tp&sum) {char ch = nc(); sum = 0;while (!(ch >= '0'&&ch <= '9')) ch = nc();while (ch >= '0'&&ch <= '9') sum = (sum << 3) + (sum << 1) + (ch - 48), ch = nc();
}
inline __int128 read128(){__int128 x = 0, f = 1;char ch128 = getchar();while(ch128 < '0' || ch128 > '9'){if(ch128 == '-')f = -1;ch128 = getchar();}while(ch128 >= '0' && ch128 <= '9'){x = x * 10 + ch128 - '0';ch128 = getchar();}return x * f;
}
inline void print128(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9)print128(x / 10);putchar(x % 10 + '0');
}
//struct dian{
//    double x,y;
//}A,B,C,D,E,F;//点
//cin>>A.x>>A.y>>B.x>>B.y>>C.x>>C.y>>D.x>>D.y>>E.x>>E.y>>F.x>>F.y;
//double len(dian x,dian y){
//    return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
//}//两点之间距离
//double xj(dian x,dian y,dian z){
//    x.x-=y.x;
//    x.y-=y.y;
//    z.x-=y.x;
//    z.y-=y.y;
//    return x.x*z.y-x.y*z.x;
//}//叉积
int n,t,m;
void wanyurukong(){cin>>n>>m;int jk=2;int kl=m+1;while (kl<n) {jk++;kl+=m;}cout<<jk<<"\n";
}
int main(){ios::sync_with_stdio(false);cin.tie(); cout.tie();cin>>t;while (t--) {wanyurukong();}//wanyurukongreturn 0;
}

B

#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <stdio.h>
#include<vector>
#include<queue>
#include<map>
#include <unordered_map>
#include<set>
#include<tuple>
#include<numeric>
#include<stack>
using namespace::std;
typedef long long  ll;
inline char nc() {static char buf[1000000], *p1 = buf, *p2 = buf;return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename _Tp> inline void read(_Tp&sum) {char ch = nc(); sum = 0;while (!(ch >= '0'&&ch <= '9')) ch = nc();while (ch >= '0'&&ch <= '9') sum = (sum << 3) + (sum << 1) + (ch - 48), ch = nc();
}
inline __int128 read128(){__int128 x = 0, f = 1;char ch128 = getchar();while(ch128 < '0' || ch128 > '9'){if(ch128 == '-')f = -1;ch128 = getchar();}while(ch128 >= '0' && ch128 <= '9'){x = x * 10 + ch128 - '0';ch128 = getchar();}return x * f;
}
inline void print128(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9)print128(x / 10);putchar(x % 10 + '0');
}
//struct dian{
//    double x,y;
//}A,B,C,D,E,F;//点
//cin>>A.x>>A.y>>B.x>>B.y>>C.x>>C.y>>D.x>>D.y>>E.x>>E.y>>F.x>>F.y;
//double len(dian x,dian y){
//    return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
//}//两点之间距离
//double xj(dian x,dian y,dian z){
//    x.x-=y.x;
//    x.y-=y.y;
//    z.x-=y.x;
//    z.y-=y.y;
//    return x.x*z.y-x.y*z.x;
//}//叉积
int n,t,m;
struct we{int x,y;
}c[200005];
bool cmp(we a,we b){if (a.x==b.x) {return a.y>b.y;}return a.x<b.x;
}
void wanyurukong(){cin>>n;for (int i=1; i<=n; i++) {cin>>c[i].x>>c[i].y;}sort(c+1, c+1+n,cmp);c[0].x=c[0].y=0;int fx=0;ll na=0;for (int i =1; i<=n; i++) {if (c[i].x!=c[i-1].x) {fx=c[i].x-1;na+=c[i].y;continue;
//            cout<<c[i].x<<" "<<c[i].y<<"\n";}if (fx) {fx--;na+=c[i].y;
//            cout<<c[i].x<<" "<<c[i].y<<"\n";}}cout<<na<<"\n";
}
int main(){ios::sync_with_stdio(false);cin.tie(); cout.tie();cin>>t;while (t--) {wanyurukong();}//wanyurukongreturn 0;
}

C

#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <stdio.h>
#include<vector>
#include<queue>
#include<map>
#include <unordered_map>
#include<set>
#include<tuple>
#include<numeric>
#include<stack>
using namespace::std;
typedef long long  ll;
inline char nc() {static char buf[1000000], *p1 = buf, *p2 = buf;return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename _Tp> inline void read(_Tp&sum) {char ch = nc(); sum = 0;while (!(ch >= '0'&&ch <= '9')) ch = nc();while (ch >= '0'&&ch <= '9') sum = (sum << 3) + (sum << 1) + (ch - 48), ch = nc();
}
inline __int128 read128(){__int128 x = 0, f = 1;char ch128 = getchar();while(ch128 < '0' || ch128 > '9'){if(ch128 == '-')f = -1;ch128 = getchar();}while(ch128 >= '0' && ch128 <= '9'){x = x * 10 + ch128 - '0';ch128 = getchar();}return x * f;
}
inline void print128(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9)print128(x / 10);putchar(x % 10 + '0');
}
//struct dian{
//    double x,y;
//}A,B,C,D,E,F;//点
//cin>>A.x>>A.y>>B.x>>B.y>>C.x>>C.y>>D.x>>D.y>>E.x>>E.y>>F.x>>F.y;
//double len(dian x,dian y){
//    return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
//}//两点之间距离
//double xj(dian x,dian y,dian z){
//    x.x-=y.x;
//    x.y-=y.y;
//    z.x-=y.x;
//    z.y-=y.y;
//    return x.x*z.y-x.y*z.x;
//}//叉积
int n,t,m;
int a[100005];
void wanyurukong(){cin>>n;for (int i=1; i<=n; i++) {cin>>a[i];}if (a[n]==1) {cout<<"NO\n";return;}if (n==1) {if (a[1]==0) {cout<<"YES\n";cout<<"0\n";}else{cout<<"NO\n";}return;}cout<<"YES\n";vector<int>fx;int jk=0;for (int i =n; i>=1; i--) {if (a[i]==0) {fx.push_back(0);}if (a[i]==1) {jk++;if (a[i-1]==0) {fx.push_back(jk);jk=0;}else{fx.push_back(0);}}}for (int i =0; i<fx.size(); i++) {cout<<fx[i]<<" ";}cout<<"\n";
}
int main(){ios::sync_with_stdio(false);cin.tie(); cout.tie();cin>>t;while (t--) {wanyurukong();}//wanyurukongreturn 0;
}

D

这道题我们不难看出，如果花费最少，我们需要找最长上升子序列，然后基于其来，不断维护其他的上升序列，然后中间分段。思路很简单，但是代码不是很好写，我们用dp来转移。具体的细节原理，写到了代码注释里面，可以仔细思考一下。

#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <stdio.h>
#include<vector>
#include<queue>
#include<map>
#include <unordered_map>
#include<set>
#include<tuple>
#include<numeric>
#include<stack>
using namespace::std;
typedef long long  ll;
inline char nc() {static char buf[1000000], *p1 = buf, *p2 = buf;return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename _Tp> inline void read(_Tp&sum) {char ch = nc(); sum = 0;while (!(ch >= '0'&&ch <= '9')) ch = nc();while (ch >= '0'&&ch <= '9') sum = (sum << 3) + (sum << 1) + (ch - 48), ch = nc();
}
inline __int128 read128(){__int128 x = 0, f = 1;char ch128 = getchar();while(ch128 < '0' || ch128 > '9'){if(ch128 == '-')f = -1;ch128 = getchar();}while(ch128 >= '0' && ch128 <= '9'){x = x * 10 + ch128 - '0';ch128 = getchar();}return x * f;
}
inline void print128(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9)print128(x / 10);putchar(x % 10 + '0');
}
//struct dian{
//    double x,y;
//}A,B,C,D,E,F;//点
//cin>>A.x>>A.y>>B.x>>B.y>>C.x>>C.y>>D.x>>D.y>>E.x>>E.y>>F.x>>F.y;
//double len(dian x,dian y){
//    return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
//}//两点之间距离
//double xj(dian x,dian y,dian z){
//    x.x-=y.x;
//    x.y-=y.y;
//    z.x-=y.x;
//    z.y-=y.y;
//    return x.x*z.y-x.y*z.x;
//}//叉积
int n,t;
int a[505];
ll dp[505][505];
ll ans[505];
void wanyurukong(){cin>>n;for (int i =1; i<=n; i++) {cin>>a[i];}for (int i =0; i<=n; i++) {ans[i]=-100;for (int j =0; j<=n; j++) {dp[i][j]=-10000;}}dp[0][0]=0;//初始化//以i结尾，有j段非最长上升子序列for (int i =1; i<=n; i++) {for (int j =0; j<=(i+1)/2; j++) {if (a[i-1]<a[i]) {dp[i][j]=max(dp[i][j], dp[i-1][j]+1);//上一个以i-1结尾最大，如果继续上升，则转移+1}if (!j) {continue;}//中间断续for (int  k=0; k<i-1; k++) {if (a[k]<a[i]) {dp[i][j]=max(dp[i][j], dp[k][j-1]+1);//每次j-1，从i后面中间中断一次，更新最大值，每次至少断一个数字//后续j++。前边断过的变大的值不会再被更新，而且每次断续是连续的，如果继续并且有更大价值更新，那么一定不是一段，所以以此来推断不断断续来更新最大值的值}}}}for (int j=0; j<=n; j++) {for (int i =1; i<=n; i++) {if (i==n) {//i==n是最后一位，所以不用再考虑后续数字的情况ans[j]=max(ans[j], dp[i][j]);}else{   //考虑后续数字，所以j-1ans[j]=max(ans[j], dp[i][j-1]);}}//简单的前值最大值转移，小段可优，则大段不需再多分割ans[j]=max(ans[j], ans[j-1]);}
//     debug
//    for (int i=0; i<=n;i++) {
//        for (int j =0; j<=n; j++) {
//            cout<<dp[i][j]<<" ";
//        }
//        cout<<"\n";
//    }
//    for (int i =1; i<=n; i++) {
//        cout<<ans[i]<<" ";
//    }
//    cout<<"\n";
//    return;for (int i =1; i<=n; i++) {cout<<n-ans[i]<<" ";}cout<<"\n";
}
int main(){ios::sync_with_stdio(false);cin.tie(); cout.tie();cin>>t;while (t--) {wanyurukong();}//wanyurukongreturn 0;
}


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

相关文章

个人和企业如何有效保护IP地址？

个人和企业如何有效保护IP地址？

随着互联网的快速发展&#xff0c;个人和企业对于保护IP地址的重要性越来越清晰。为了帮助读者更好地了解如何有效保护IP地址&#xff0c;以下将介绍几种方法&#xff0c;并提供一些相关的数据和专家意见。 使用防火墙是保护IP地址的一个重要手段。防火墙可以监控和过滤网络流量…
阅读更多...
2006中国企业500强名单

2006中国企业500强名单

名次 企业名称 地区 营业收入(万元) 平均数 2828097 1 中国石油化工集团公司 北京 82301173 2 国家电网公司 北京 71270322 3 中国石油天然气集团公司 北京 69438972 4 中国工商银行股份有限公司 北京 23898000 5 中国移动通信集团公司 北京 23578982 6 中国人寿保险&#xff0…
阅读更多...
2008年《中国最具价值品牌500强》的名单（2008中国500强企业名单1-500）

2008年《中国最具价值品牌500强》的名单（2008中国500强企业名单1-500）

名次 企业名称 营业收入&#xff08;万元&#xff09; 1 中国石油化工集团公司 106466742 2 中国石油天然气集团公司 89380643 3 国家电网公司 85452374 4 中国工商银行股份有限公司 29089700 5 中国移动通信集团公司 28631777 6 中国银行 24219200 7 中国南方电网有限责…
阅读更多...
【iOS】 各iPhone手机屏幕尺寸分辨率

【iOS】 各iPhone手机屏幕尺寸分辨率

机型物理像素逻辑像素规格对角线iPhone 14 Pro Max1290*2796px430*932pt3x6.7英寸iPhone 14 Pro1179*2556px393*852pt3x6.1英寸iPhone 14 Plus1284*2778px428*926pt3x6.7英寸iPhone 141170*2532px390*844pt3x6.1英寸iPhone 13 Pro Max1284*2778px428*926pt3x6.7英寸iPhone 13 P…
阅读更多...
JVM-jvisualvm性能监控可视化工具使用与eden-s0-s1分配分析(三)

JVM-jvisualvm性能监控可视化工具使用与eden-s0-s1分配分析(三)

目录 第一步&#xff1a;安装jvisualvm 第二步&#xff1a;安装VisualvmGc插件 方式一&#xff1a;jvisualvm工具直接下载安装 方式二&#xff1a;去官网下载导入安装 总结 第三步&#xff1a;idea安装VisualvM Launcher插件 第四步&#xff1a;演示young中eden、s0、s1垃…
阅读更多...
Android 14新版本新功能即将发布

Android 14新版本新功能即将发布

​ 以下是到目前为止我们所知道的关于下一个版本的Android的一切。 可能感觉 Android 13 仍然是全新的&#xff0c;但自 2022 年 8 月以来&#xff0c;它已经在一些最新、最伟大的 Android 手机上出现。随着这个大版本的发布&#xff0c;谷歌正在努力准备下一个主要版本&#…
阅读更多...
Android 13：我们所知道的关于谷歌操作系统大更新的一切

Android 13：我们所知道的关于谷歌操作系统大更新的一切

经过几个月的测试&#xff0c;谷歌的 Android 13 终于来了。这是一个非常小的更新&#xff0c;可以看到谷歌建立在它从Android 12和12L开始的基础上。Material 你可以通过额外的自定义功能变得更加丰富多彩&#xff0c;Google 计划将图标主题扩展到目前支持的少量 Google 应用程…
阅读更多...
linux(类UNIX)体系家族

linux(类UNIX)体系家族

Linux是一种自由和开放源码的类Unix操作系统。目前存在着许多不同的Linux,但它们都使用了Linux内核。Linux可安装在各种计算机硬件设备中&#xff0c;从手机、平板电脑、路由器和视频游戏控制台&#xff0c;到台式计算机、大型机和超级计算机。Linux是一个领先的操作系统&#…
阅读更多...
最新文章

Copyright @ 2022~2023