A
分析
排序+中位数性质
AC代码
cpp;gutter:true;</p>
<h1>include</h1>
<p>using namespace std;
int a[100010];
void sort(int l,int r)
{
if(l>=r) return ;
int i=l-1,j=r+1,mid=a[l+r>>1];
while(ia[i]);
do j--;while(mid>n;
for(int i=0;i>a[i];
sort(0,n-1);
for(int j=0;j</p>
<pre><code>
手搓快排玩玩，嘿嘿🤭🤭
B
分析
这里要我们求连续不小于f块地的栅栏所围的奶牛的平均数的最大值。
根据要求可知，所求平均数最大值一定在每单个区域奶牛数量的最大值和最小值之间。
那么现在就可以很明显的看出，这是一个二分查找左区间的右边界点的题目。
我们只需从每单个区域奶牛数量的最大值和最小值之间二分查找答案即可。
AC代码
;gutter:true;
#include
using namespace std;
const int N=100010;
int n,m,c[N];
double sum[N];
bool check(double avg)
{
for(int i=1;i=minv) return true;//进行判断
}
return false;//如果所有的都不满足，那么这个平均数就一定不满足
}
int main()
{
scanf("%d%d",&n,&m);
double l=0,r=0;
for(int i=1;i1e-5)
{
double mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
printf("%d\n ",int(r*1000));
return 0;
}
C
分析
两边的牛高 中间的牛矮数据范围很大所以我们可以使用差分但是题目最高又限制了最高的牛所以我们还需要查重
AC代码
cpp;gutter:true;</p>
<h1>include</h1>
<h1>include</h1>
<p>using namespace std;
int main()
{
int n,p,h,m;
int hi[10010],c[10010];
cin>>n>>p>>h>>m;
// hi[1]=h;
set>e;
for(int i=0,a,b;i>a>>b;
if(a>b) swap(a,b);
if(!e.count({a,b}))
{
e.insert({a,b});
hi[a+1]--;
hi[b]++;
}</p>
<pre><code>}
for (int i = 1; i
</code></pre>
<pre><code>
D
分析
炸弹的范围是R，可以看成每个城市的影响范围是R，找出最多的重叠部分就可以了
用到二维前缀和
AC代码
;gutter:true;
#include
#include
using namespace std;
const int M=5010;
int n,m,s[M][M];
int main()
{
int cnt, R;
cin >> cnt >> R;
R = min(5001, R);
n = m = 5001;
while (cnt — )
{
int x, y, w;
cin >> x >> y >> w;
x ++, y ++ ;
s[x][y] += w;
}
for(int i=1;i
E
分析
以每个矩形的高度为准，向两边扩展，直到遇到比它矮的为止
每个矩形的高度都是>=0的，为了使得每个矩形的两侧都有矮于它的矩形，
所以往两侧放了两个-1的矩形h[0] = h[n + 1] = -1;
由于有-1矩形的存在，不会有任何矩形的高度 hh 满足 −1>=h−1>=h，所以栈不会空
因此可以省略栈中是否有元素的判断条件tt >= 0
AC代码
cpp;gutter:true;</p>
<h1>include</h1>
<h1>include</h1>
<p>using namespace std;
const int N=100010;
int h[N],q[N],l[N],r[N];
int main()
{
int n;
while(cin>>n, n)
{
for(int i = 1; i >h[i];
h[0]=h[n+1]=-1;</p>
<pre><code> int tt=-1;
q[++tt]=0;
for(int i=1;i=h[i]) tt--;
l[i]=i-q[tt];
q[++tt]=i;
}
tt=0;
q[0]=n+1;
for(int i=n;i;i --)
{
while(h[q[tt]]>=h[i]) tt--;
r[i]=q[tt]-i;
q[++tt]=i;
}
long long res=0;
for(int i=1;i
</code></pre>
<pre><code>
F
分析
题目中的操作都是在数据的最后一位所以可以用对顶栈就是top对着top的栈
AC代码
;gutter:true;
#include
#include
#define N 1000010
using namespace std;
int sum[N],f[N],sul[N],sur[N],t1,t2;
int main()
{
string a;
int n,x;
f[0]=-0x3f3f3f3f;
cin>>n;
for(int i=0;i>a;
if(a=="I")
{
cin>>x;
sul[++t1]=x;
sum[t1] = sum[t1 – 1] + sul[t1];
f[t1] = max(f[t1 – 1], sum[t1]);
}
if(a=="D")
if (t1) t1–;
if(a=="L") if (t1) sur[++t2] = sul[t1–];
if(a=="R")
if (t2)
{
sul[++t1] = sur[t2–];
sum[t1] = sum[t1 – 1] + sul[t1];
f[t1] = max(f[t1 – 1], sum[t1]);
}
if(a=="Q")
{
cin>>x;
cout<
G
分析
入队
先判断小组是否有人，如果没人，将小组编号加入 pointer 中
将新人加入她所在的小组
出队
先判断pointer指向的第一个小组还有没有人
——如果没人，就出队第一个小组编号，去判断第二个
然后正常出队即可
AC代码
cpp;gutter:true;</p>
<h1>include</h1>
<h1>include</h1>
<h1>include</h1>
<p>using namespace std;
const int N=1010;
int t[N*N];
int main()
{
int n,q=1;</p>
<p>while(cin>>n&&n)
{
printf("Scenario #%d\n",q++);
for(int i=0;i>cnt;
while(cnt--)
{
int x;
cin>>x;
t[x]=i;
}</p>
<pre><code>}
queueteam;
queueperson[N];
string ss;
while(cin>>ss&&ss!="STOP")
{
if(ss=="ENQUEUE")
{
int x;
cin>>x;
int id=t[x];
if(person[id].empty()) team.push(id);//如果无这小组就加到后面
person[id].push(x);
}
if(ss=="DEQUEUE")
{
int id=team.front();
cout<
</code></pre>
<pre><code>
H
分析
目标是s[i] - s[i-j], j = 1, 2, ..., m 的最大值，等价于求 s[i-j], j = 1, 2, ..., m 的最小值，即 s 的下标取区间 [i-m, i-1] 内的最小值，即滑动窗口求最小值问题，可以用单调队列来优化。
AC代码
;gutter:true;
#include
#include
#include
using namespace std;
const int N=3e5+10;
int n,m;
dequeq;
long long s[N];
int main()
{
cin>>n>>m;
for(int i=1;i>s[i];
s[i]+=s[i-1];
}
long long res=INT_MIN;
q.push_back(0);
for(int i=1;im)
{
q.pop_front();
}
res=max(res,s[i]-s[q.front()]);
while (!q.empty() && s[q.back()] >= s[i])
q.pop_back();
q.push_back(i);
}
cout<
Original: https://www.cnblogs.com/zandebokegu/p/15819910.html
Author: szf45
Title: 寒假集训一补题与题解
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/583893/
转载文章受原作者版权保护。转载请注明原作者出处！