2026年10月2日（南山S）
2026-10-02 16:45:40
发布于：广东
44阅读
0回复
0点赞
优先队列
// priority_queue
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
ll a[N];
struct Node{
int a,b;//要求优先队列的规则为先拿最大a
bool operator <(const Node &other)const{
return a<other.a;//对应结构体a的大根堆
// return a>other.a;//对应小根堆
}
};
void solve(){
Node x={1,10},y={20,2};
cout<<(x<y);
// priority_queue<int>que;//默认拿最大（大根堆）
// priority_queue<int,vector<int>,greater<int>>que;//小根堆
// 1 2 3
// -1 -2 -3
//小根堆
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
第一题
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
void solve(){
vector<pair<int,int>>vec;
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
int a,b;cin>>a>>b;
vec.push_back({a,b});
}
sort(vec.begin(),vec.end());
reverse(vec.begin(),vec.end());
priority_queue<int>que;//默认大根堆，去拿取可以拿的最大的。
ll ans=0;
for(int i=1;i<=m;i++){
//判断数组里面是否有&&数组中发工资最快的在时间范围i内可以发出来
while(vec.size()&&vec.back().first==i){
que.push(vec.back().second);
vec.pop_back();//存放目前所有可以拿的
}
//拿目前可以拿的最大的，并且要及时pop
if(que.size()){
ans+=que.top();que.pop();
}
}
cout<<ans<<endl;
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
第二题
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
ll a[N];
void solve(){
int n,k,c;
cin>>n>>k>>c;
string s;cin>>s;
vector<int>a,b;
s=' '+s;
for(int i=1;i<=n;i++){
if(s[i]=='o'&&a.size()<k){
a.push_back(i);
i+=c;
}
}
for(int i=n;i>=1;i--){
if(s[i]=='o'&&b.size()<k){
b.push_back(i);
i-=c;
}
}
reverse(b.begin(),b.end());
for(int i=0;i<a.size();i++){
if(a[i]==b[i])cout<<a[i]<<endl;
}
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
第三题思路
1.记忆化 设置了一个怎么样的数组，以及存储了一个怎样的答案。
dp[i][0/1]:前i个位置且以s[i]结尾的所有字串中奇数串和偶数串的个数
2.状态转移方程 （利用已知推导未知）
if(s[i]=='0'){//等于0的时候，前面的奇偶不会发生改变，直接继承
dp[i][0]=dp[i-1][0];
dp[i][1]=dp[i-1][1];
}
if(s[i]=='1'){//奇偶翻转
dp[i][0]=dp[i-1][1];
dp[i][1]=dp[i-1][0];
}
//本身产生的贡献
dp[i][s[i]-'0']++;
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
ll a[N];
ll dp[N][2];
void solve(){
int n;cin>>n;
string s;cin>>s;
//版本1
// ll one=0,zero=0;//奇偶串的个数
// ll ans=0;
// for(auto c:s){
// if(c=='0');
// else {
// swap(one,zero);
// }
// if(c=='0')zero++;
// else one++;
// ans+=one;
// }
// cout<<ans<<endl;
//版本2
s=' '+s;
for(int i=1;i<=n;i++){
if(s[i]=='0'){
dp[i][0]=dp[i-1][0];
dp[i][1]=dp[i-1][1];
dp[i][0]++;
}else{
dp[i][0]=dp[i-1][1];
dp[i][1]=dp[i-1][0];
dp[i][1]++;
}
ans+=dp[i][1];
}
cout<<ans<<endl;
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
第四题
// //求前缀i个的答案
// //第i个位置给不给钱[0/1] i位置给钱，喂养i i+1;
// 1.记忆化 dp[i][0/1]
// 到i位置位置，且1-i位置全部都喂养了，0/1对应i位置给不给钱
// 2.状态转移方程
// //当前位置给钱的话，前一个位置给不给都无所谓/两种选最小
// dp[i][1]=min(dp[i-1][0],dp[i-1][1]);
// //当前位置不给钱，前一个位置一定要给钱
// dp[i][0]=dp[i-1][1];
// //从第一个位置开始直接求[1-n]的结果
// //特判先给n位置钱，求[1,n-1]+a[n]的结果
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
ll a[N];
ll dp[N][2];//dp[i]=dp[i-1],dp[i-2]
void solve(){
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
ll ans=0;
dp[0][1]=1e18;
//情况1
for(int i=1;i<=n;i++){
// //当前位置给钱的话，前一个位置给不给都无所谓/两种选最小
dp[i][1]=min(dp[i-1][0],dp[i-1][1])+a[i];
// //当前位置不给钱，前一个位置一定要给钱
dp[i][0]=dp[i-1][1];
}
ans=min(dp[n][1],dp[n][0]);
//情况2//买了最后一个
dp[1][1]=a[1]+a[n];
dp[1][0]=a[n];
for(int i=2;i<=n;i++){
// //当前位置给钱的话，前一个位置给不给都无所谓/两种选最小
dp[i][1]=min(dp[i-1][0],dp[i-1][1])+a[i];
// //当前位置不给钱，前一个位置一定要给钱
dp[i][0]=dp[i-1][1];
}
//[1,n-1];
ans=min(ans,min(dp[n-1][0],dp[n-1][1]));
cout<<ans<<endl;
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
第五题
// [A-S]=[A-B]+[B-S]
// [A-B]=[A-S]-[B-S];
// //枚举坐标B，去找最小的[A-S]使得式子
// [A-S]-[B-S]最小[A-B];
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
#define ll long long
ll a[N][N];
ll dp[N][N];//二维前缀最小值
int n,m,c;
ll cal(ll i,ll j){//计算坐标[i,j]到右下角的花费
return (abs(i-n)+abs(j-m))*c;
}
ll run(){
ll ans=1e18;
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
dp[i][j]=1e18;
//枚举坐标B
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
ll mi=min(dp[i-1][j],dp[i][j-1]);//前缀最小的A
ll val=cal(i,j);//当前B坐标的值
dp[i][j]=min(mi,val+a[i][j]);//更新二维前缀最小值
// cout<<i<<' '<<j<<' '<<dp[i][j]<<' '<<val<<endl;
if(i==1&&j==1)continue;//[1,1]坐标没有前缀，不参与计算
ans=min(ans,mi-val+a[i][j]);
}
return ans;
}
void solve(){
cin>>n>>m>>c;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
ll ans=run();
for(int i=1;i<=n;i++)reverse(a[i]+1,a[i]+m+1);
ans=min(ans,run());
cout<<ans<<endl;
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
第六题
//[l,r] x
// [l,l+1][l,r][r-1,r]
#include<bits/stdc++.h>
using namespace std;
const int N=2000+10;
#define ll long long
ll a[N],vis[N][N];
ll ans=0;
int n;
//[1,5]->[l,r]
//[3,3]-->重复访问--记忆化
void dfs(int l,int r,int x){
ans=max(ans,n-(r-l+1LL));
if(l>=r||vis[l][r])return ;//结束，不能够继续删除
vis[l][r]=1;
if(a[l]+a[l+1]==x)dfs(l+2,r,x);
if(a[l]+a[r]==x)dfs(l+1,r-1,x);
if(a[r-1]+a[r]==x)dfs(l,r-2,x);
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
dfs(1,n,a[1]+a[2]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
vis[i][j]=0;
dfs(1,n,a[1]+a[n]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
vis[i][j]=0;
dfs(1,n,a[n-1]+a[n]);
cout<<ans/2<<endl;
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
第七题
//分层图
//给定n*m的图，你可以向四个方向随便走，;
//图中有门的存在*,墙壁#，空地. 钥匙k
//钥匙会产生损耗（即一把钥匙只能开一个门，用完即消失）
//问是否能从左上角走到右下角
#include<bits/stdc++.h>
using namespace std;
const int N=3000+10;
#define ll long long
ll a[N][N];
ll dp[N][N][4];//dp[i][j][k]表示坐标[i,j]已经拿了k个物品的最大价值
void solve(){
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=k;i++){
int u,v,x;cin>>u>>v>>x;
a[u][v]=x;
}
//0/1背包
// dp[i]=max(dp[i],dp[i-w]+v);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=3;k>=0;k--){//
if(a[i][j]&&k<3){
// 向右走
dp[i][j+1][k+1]=max(dp[i][j+1][k+1],dp[i][j][k]+a[i][j]);
//向下走
dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][k]+a[i][j]);
}
//不管有没有都不拿，向右走
dp[i][j+1][k]=max(dp[i][j+1][k],dp[i][j][k]);
//向下走
dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][k]);
}
ll ans=0;
for(int k=0;k<=3;k++)ans=max(ans,max(dp[n+1][m][k],dp[n][m+1][k]));
cout<<ans<<endl;
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
第八题
// //给定一个长度为n的字符串，由0-9组成
// 问有多少个连续子串对应的数字%13==7
// //U142876.奇数个 1 的子串
// dp[i][0/1]//前i个数字，以s[i]结尾%2==0的方案数，%2==1的方案数
// 14 1 1*10%13+5%13
// 145 145=(140+5)%13=(14*10+5)%13=(14%13*10%13+5%13)%13
// 1459
// dp[i][j];//前i个字符，且以s[i]结尾，余数为j的方案数
// 当前字符为c(int)
// dp[i+1][(j*10+c)%13]+=dp[i][j];
// x%4
// (x+1)%5
// dp[i][j][k]:总数为i，当前已经拿了j个且余数为k的时候的方案数
#include<bits/stdc++.h>
using namespace std;
const int N=100+10;
#define ll long long
ll a[N],dp[N][N][N];
ll mod=998244353;
void solve(){
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)dp[i][0][0]=1;
for(int i=1;i<=n;i++)//枚举拿第i个数字
for(int j=1;j<=n;j++)//枚举拿取的总数j
for(int k=i-1;k>=0;k--)//表示当前拿了k个
for(int r=0;r<j;r++){//当前余数，和个数有关,
dp[j][k+1][(r+a[i])%j]+=dp[j][k][r];
dp[j][k+1][(r+a[i])%j]%=mod;
}
ll ans=0;
for(int i=1;i<=n;i++)ans=(ans+dp[i][i][0])%mod;
cout<<ans<<endl;
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
第九题
// A班x人编号1-x，B班y人编号1-y
// 要求A，B班的所有人站成一列
// 但是每个班级学生出来的顺序都必须从小到大
// 问总共有多少个不同的排列
// A1 B1//同编号，不同班级算不同的人
// 12345678
// [1,8]
// [1,2]*[3,8]
// [1,4]*[5,8]
// [1,6]*[7,8]
// [2,7]
#include<bits/stdc++.h>
using namespace std;
const int N=200*2+10;
#define ll long long
ll a[N],n,m;
ll rela[N][N];
ll dp[N][N],vis[N][N],mod=998244353;
ll C[N][N];//C(n,m)
ll dfs(int l,int r){
if(l>r)return 1;//错位情况return 1
if(vis[l][r])return dp[l][r];
vis[l][r]=1;
ll sum=0;
for(int mid=l+1;mid<=r;mid+=2){
if(rela[l][mid]){
ll len=(r-l+1)/2,x=(mid-l+1)/2
sum+=C[len][x]*dfs(l+1,mid-1)%mod*dfs(mid+1,r);
sum%=mod;
}
}
// cout<<l<<' '<<r<<' '<<sum<<endl;
dp[l][r]=sum;
return dp[l][r];
}
void solve(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;cin>>x>>y;
rela[x][y]=1;
rela[y][x]=1;
}
C[0][0]=1;
for(int i=1;i<=n*2;i++)
for(int j=0;j<=i;j++){
if(j==0)C[i][j]=1;
else C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
cout<<dfs(1,n*2);
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
有帮助，赞一个