牛客周赛 Round 16

A、

题目描述

给定一个大小为n的数组a，请你判断一个数组是否满足以下条件：
1. 数组严格升序，即a1 2. 对于1≤i≤n−1，我们定义bi​=a(i+1​)−ai​，则数组b严格降序，即b1​>b2​>...>b(n−1)​。
输入描述:

第一行输入一个正整数n，代表数组的大小。
第二行输入n个正整数ai​，代表给定的数组。
3≤n≤10^5
1≤ai​≤10^9

输出描述:

若满足给定的两个条件，则输出 Yes。否则输出 No。

示例1

输入

3
1 3 4

输出

Yes

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
const int N=2e5+10;
const int mod=1e9+7;
const double eps=1e-5;
typedef double db;
int n;
int a[N];
int b[N];
void solve()
{
    ; 
}
signed main()
{
   cin>>n;
   
   fp(i,1,n)cin>>a[i];
   
   bool flag1=false;
   bool flag2=false;
   
   for(int i=1;i<=n-1;i++)
   {
   	  if(a[i]>=a[i+1])
   	  {
   	       flag1=true;
		   break;	
	  }
   }
   
   for(int i=1;i<=n-1;i++)
   {
   	   b[i]=a[i+1]-a[i];
   }
   
   for(int i=1;i<=n-2;i++)
   {
   	   if(b[i]<=b[i+1])
   	   {
   	       flag2=true;
			  break;	
	   }
   }
   
   if(flag1==false&&flag2==false)
   {
   	  cout<<"Yes"<<"\n";
   }
   else
   {
   	  cout<<"No"<<"\n";
   }
	
	
	return 0;
} 
 
 
 

 B、

题目描述

小美在训练场打靶，靶一共有 10 环，靶的中心位于 (0,0)，如果打中的位置在以靶心为圆心，半径为 1 的圆内，则得 10 分，之后每向外一圈分数减 1，直到 1 分，每圈的半径都比上一圈大 1。即如果打中的位置在以靶心为圆心，半径为 iii 的圆内，则得 11−i 分。
如果打中的位置不在任何一圈内，则得 0 分。

输入描述:

一行两个整数 x,y，表示打中的位置坐标。
0≤x,y≤10

输出描述:

输出一个整数，表示得分。

示例1

输入

1 0

输出

10

示例2

输入

1 1

输出

9

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
const int N=2e5+10;
const int mod=1e9+7;
const double eps=1e-5;
typedef double db;
int x,y;
void solve()
{
    ; 
}
signed main()
{
    cin>>x>>y;
    
    int f=x*x+y*y;
    
    int q=ceil(sqrt(f*1.0));
    
    cout<<min(10ll,max(0ll,11-q))<<"\n";
	
	return 0;
} 
 
 
 

 A、B很简单，不做分析。

C、

题目描述

小美在玩游戏，游戏中有 n 个怪物，怪物的血量为hi​，攻击力为 ai​。小美的血量为 H，攻击力为 A，小美可以击败血量和攻击力都小于自己的怪物，并且打败后血量降为怪物的血量，攻击力降为怪物的攻击力。小美想知道最多可以打败多少怪物。

输入描述:

第一行三个整数 n,H,A，分别表示怪物的数量，小美的血量，小美的攻击力。
第二行 n 个整数 hi​，表示怪物的血量。
第三行 n 个整数 ai​，表示怪物的攻击力。
1≤n≤10^3
1≤ai​,hi​,H,A≤10^9

输出描述:

输出一个整数表示答案。

示例1

输入

3 4 5
1 2 3
3 2 1

输出

1

说明

最多只能击败一个怪物。

建立dp

dp[i]=max(dp[i],dp[j]+1)

如何建立这个表达式？

首先我们得先对x、y的某一维从大到小排序。

然后二层循环跑一下，注意dp的逻辑需要正确。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
const int N=2e5+10;
const int mod=1e9+7;
const double eps=1e-5;
typedef double db;
int n,h,a;
int dp[N];
int x[N];
int y[N];
struct node
{
	int hh,aa;
}Node[N];
bool cmp(node f,node t)
{
	return f.hh>t.hh;
}
signed main()
{
    cin>>n>>h>>a;
    
    fp(i,1,n){
    	cin>>x[i];
	} 
	fp(i,1,n){
		cin>>y[i];
	}
	int ans=0;
	fp(i,1,n)
	{
		if(h>x[i]&&a>y[i])
		{
			Node[++ans]={x[i],y[i]};
		}
	}
	int mmax=0;
    
    
    sort(Node+1,Node+1+ans,cmp);
   
    
    for(int i=1;i<=ans;i++)
    {
    	dp[i]=max(1ll,dp[i]);
    	for(int j=1;j<=i-1;j++)
    	{
    		if(Node[i].aa<Node[j].aa&&Node[i].hh<Node[j].hh)
    		{
    			dp[i]=max(dp[i],dp[j]+1);
			}
		}
		mmax=max(mmax,dp[i]);
	}
	
	cout<<mmax<<"\n";
	
	
	return 0;
} 
 
 
 

D、

题目描述

地图上有n个城市，小美准备修建一些道路，使得任意两个城市之间都能通过道路到达。现在给定一些修路的计划（有一些计划是必选的），请你帮小美规划出最优的方案。

输入描述:

第一行输入两个正整数n,m，用空格隔开。代表城市数量。
接下来的m行，每行输入四个正整数u,v,w,p，代表一个计划是在城市u和城市v之间修建一条道路，花费为w。如果p为 1，代表该计划必选。如果p为 0，代表该计划是可选的。
1≤n,m≤10^5
1≤u,v≤n
1≤w≤10^9
0≤p≤1

输出描述:

如果无解（即无法使得任意两个城市之间都能通过道路到达），则输出 -1。
如果有解，则第一行输入一个正整数k，代表选择的计划数量。第二行输入k个正整数bi​，代表选择的计划。
你只需要保证最终所有的城市都可以通过道路连通，且总代价最小即可。请注意，p=1的计划是必选的，如果你的方案不包含某个p=1的计划，则会直接返回答案错误。

示例1

输入

3 4
1 2 3 1
1 2 2 0
1 3 1 0
2 3 3 0

输出

2
1 3

说明

选择第一个和第三个方案，总花费为 4。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
const int N=2e5+10;
const int mod=1e9+7;
const double eps=1e-5;
typedef double db;
int n,m;
struct node
{
	int u,v,w;
	int pos;
	bool p;
}Node[N];
bool cmp(node a,node b)
{
	if(a.p==b.p)
	{
		return a.w<b.w;
	}
	else
	{
		return a.p>b.p;
	}
	
}
int p[N];
void init()
{
	fp(i,1,n)
	{
		p[i]=i;
	}
}
int find(int x)
{
	if(p[x]!=x)return p[x]=find(p[x]);
	return p[x];
}
vector<int>T;
signed main()
{
    cin>>n>>m;
    
    fp(i,1,m)
    {
    	cin>>Node[i].u>>Node[i].v>>Node[i].w>>Node[i].p;
    	Node[i].pos=i;
	}
	
	init();
	
	sort(Node+1,Node+1+m,cmp);
	
	int cnt=0;
	int sum=0;
	
	for(int i=1;i<=m;i++)
	{
		int u=Node[i].u;
		int v=Node[i].v;
		int w=Node[i].w;
		//cout<<u<<" "<<v<<" "<<w<<"\n";
		u=find(u);
		v=find(v);
		if(p[u]!=v)
		{
			cnt++;
			sum+=w;
			p[u]=v;
			T.push_back(Node[i].pos);
		}
		else if(Node[i].p==1)
		{
			T.push_back(Node[i].pos);
			//cnt++;
		}
		if(cnt==n-1)
		{
			break;
		}
	}
	
	if(cnt==n-1){
	  cout<<T.size()<<"\n";
	  sort(T.begin(),T.end());
	  for(auto x:T)
	  {
	  	cout<<x<<" ";
	  }
	  cout<<"\n";
	}
	else cout<<-1<<"\n";
	
	
	return 0;
} 
 
 
 

最小生成树改一点点就行。

把预置的边优先级设为最大，然后再取边的时候进行小改一下就行。