题目列表
排名
一开始不明白为什么一堆大佬死这题了。
一翻代码：年级从大到小。
……
正文开始：
首先排序，首先按成绩大到小，其次按年级小到大。
然后可以开个 hash 数组统计到目前为止每个年级的人数，输出直接输出自己年级之前的总和。
代码
#include<bits/stdc++.h>
using namespace std;
struct node
{
int Scr,Grd;
}a[114514];
bool cmp(node a,node b)
{
if(a.Scr!=b.Scr)return a.Scr>b.Scr;
return a.Grd<b.Grd;
}
int n;
int h[10];
int main()
{
freopen("paiming.in","r",stdin);
freopen("paiming.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].Scr>>a[i].Grd;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
{
int ans=0;
for(int j=1;j<a[i].Grd;j++)ans+=h[j];
h[a[i].Grd]++;
cout<<ans<<'\n';
}
return 0;
}旅游
一道搜索。
对于每个点，我们扫一遍看它是山还是湖。
后记：调了一上午，发现是本地栈空间没有机房开得大……
吃席！
代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
bool hill,lake;
int mp[1020][1020];
bool f[1020][1020];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
// int dx[]={-1,0,0,1};
// int dy[]={0,-1,1,0};
int cnt;
bool ok(int x,int y)
{
return 1<=x&&x<=n&&1<=y&&y<=m;
}
void dfs(int x,int y)
{
// cout<<++cnt<<endl;
// cout<<x<<" "<<y<<endl;
f[x][y]=1;
for(int i=0;i<4;i++)
{
int X=dx[i]+x,Y=dy[i]+y;
if(!ok(X,Y)||(f[X][Y]&&mp[X][Y]==mp[x][y]))continue;
if(mp[X][Y]>mp[x][y]){lake=1;continue;}
if(mp[X][Y]<mp[x][y]){hill=1;continue;}
// cout<<X<<" "<<Y<<endl;
dfs(X,Y);
}
}
int main()
{
freopen("seek.in","r",stdin);
freopen("seek.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>mp[i][j];
}
}
int ansf=0,ansg=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(!f[i][j])
{
hill=lake=0;
dfs(i,j);
if(hill&&lake)continue;
ansf+=lake;
ansg+=hill;
}}
}
cout<<ansf<<" "<<ansg<<endl;
return 0;
}遗址
https://www.luogu.com.cn/blog/516346/solution-p8197
愤怒的小鸟
题目改了，可以连续爆炸。
那么我们只需要找出两两之间的差，除掉前 $k-1$ 个最大的，之后的最大即为答案。
显然过程是 排序整个数组-得到两两间的差-找出答案。
代码
#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[50020];
priority_queue<int>q;
int main()
{
freopen("angry.in","r",stdin);
freopen("angry.out","w",stdout);
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+n+1);
for(int i=2;i<=n;i++){
/*cout<<a[i]-a[i-1]<<" ";*/q.push(a[i]-a[i-1]);
}
// cout<<endl;
while(k!=1)
{
q.pop();
k--;
}
cout<<q.top()<<endl;
return 0;
}
/*
7 2
20
25
18
8
10
3
1
1 3 8 10 18 20 25
*/