牛客周赛 Round 16"/>
牛客周赛 Round 16
A、
题目描述
给定一个大小为n的数组a，请你判断一个数组是否满足以下条件：
1. 数组严格升序，即a1<a2<...<an。
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;
} 最小生成树改一点点就行。
把预置的边优先级设为最大，然后再取边的时候进行小改一下就行。
更多推荐
牛客周赛 Round 16
发布评论