[数据结构与算法][Acwing] 第 8 场周赛

前言

传送门 :

A.

看着像$dp$,其实就是一个贪心的递推

注意的是 三目运算符的优先级低于逻辑运算符

void solve(){
	cin>>n>>a>>b>>c;
	
	f[0] = 0 ;
	
	cin>>s; s =  " "+s;

	for(int i=1;i<=n;i++){
		f[i] = f[i-1]+(s[i]=='1'?min(b,c+a):min(a,b+c));
	}
	cout<<f[n]<<endl;
	
}

B.

题意 :
给定$a[]$,你需要选出一个序列使得其所选序列不仅满足条件而且和最大

限制条件如下 :
对于所选序列中,所有$i?j=a_i?a_j$

思路 :
首先对于形如这种$i?j=a_i?a_j$都可以化简为$i?a_i=j?a_j$

然后通过一次遍历,每次使用$map$存放$i?a_i$即可

但是这道题需要统计的是,和的最大值

所以一下子我纳闷了,偏到 选取多个等差数列然后求最大值

但是其实这题还是可以使用上面那个通法的

我们对于遍历的$i$设有$mp[i?a[i]]+=a[i]$

这样子就相当于把这个集合加上了$a[i]$,最后查询每个集合即可

最后还是在集合上面操作

map<int,int> mp;
int ans ;

void solve(){
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		mp[x-i] += x;
		ans = max(ans,mp[x-i]);
	}
	cout<<ans<<endl;
	
}

signed main(){
    //int t;cin>>t;while(t--)
    solve();
    return 0 ;
}

C.

// Problem: 更新线路
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/3775/
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i<=b;i++)
#define Fde(i,a,b) for(int i=a;i>=b;i--)

typedef priority_queue<int,vector<int>,greater<int>>  Pri_m;
typedef pair<int,int> pii;
typedef vector<int> VI;
map<int,int> mp;
const int N =  2e5+10 ;
vector<int> g[N];
int dist[N],cnt[N];
queue<int> q;
int path[N];
int n,m;

void bfs(int s){
	memset(dist,0x3f,sizeof dist);
	dist[s]  =0  ;
	q.push(s);
	
	while(!q.empty()){
		auto t =  q.front();
		q.pop();
		
		for(auto x  : g[t]){
			if(dist[x] > dist[t]+1){
				dist[x] = dist[t]+1;
				cnt[x] = 1;
				q.push(x);
			}else if(dist[x]  == dist[t]+1) cnt[x] ++ ;
		}
	}
}
void solve(){
	cin>>n>>m;
	while(m -- ){
		int a,b;cin>>a>>b;
		g[b].pb(a);//建立返图
	}
	
	int k;cin>>k;
	for(int i=1;i<=k;i++) cin>>path[i];
	bfs(path[k]);
	
	int minc = 0 ,maxc = 0 ;
	
	for(int i=1;i<k;i++){
		int a = path[i] , b = path[i+1];
		if(dist[a] < dist[b]+1) minc++,maxc++;
		else if(cnt[a] > 1)maxc++;
	}
	
	cout<<minc<<" "<<maxc<<endl;
	
	
}

int main(){
    //int t;cin>>t;while(t--)
    solve();
    return 0 ;
}

阅读世界，共赴山海

423全民读书节，邀你共读