A. City Day
暴力搜索就可以了
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int n, x, y;
const int N = 100002;
int arr[N];
bool valid[N];
int main()
{
#ifdef CODEBLOCKS
freopen("in.txt", "r", stdin);
#endif // CODEBLOCKS
while(cin>>n>>x>>y)
{
for(int i=0;i<n;i++)
{
cin>>arr[i];
valid[i] = false;
}
for(int i=0;i<n;i++)
{
bool flag = true;
for(int j=0;j<x&&i-j-1>=0;j++)
{
if(arr[i]>=arr[i-j-1])
{
flag = false;
break;
}
}
valid[i] = flag;
}
// for(int i=0;i<n;i++)
// {
// cout<<valid[i]<<' ';
// }
// cout<<endl;
for(int i=0;i<n;i++)
{
bool flag = true;
for(int j=0;j<y&&i+j+1<n;j++)
{
if(arr[i]>=arr[i+j+1])
{
flag = false;
break;
}
}
if(valid[i] && flag)
{
cout<<i+1<<endl;
break;
}
}
}
return 0;
}
B. Water Lily
设高度是x，则斜边是H+x。有，得
#include <iostream>
#include <cstdio>
using namespace std;
int h,l;
int main()
{
#ifdef CODEBLOCKS
freopen("in.txt", "r", stdin);
#endif // CODEBLOCKS
while(cin>>h>>l)
{
printf("%.7f\n",(1.0*l/2/h*l - 1.0*h/2));
}
return 0;
}
C. MP3
需要，则
。首先如果
，则无需做任何修改。
排序，然后顺序统计cnt[j]为相同数字的数目，第j大的数字有多少格，假设有
个不同数字，cnt数组的长度为cn。然后计算
，所求答案为
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, I;
const int N = 4*100001;
int arr[N];
int sum[N];
int sn;
int main()
{
#ifdef CODEBLOCKS
freopen("in.txt", "r", stdin);
#endif // CODEBLOCKS
while(cin>>n>>I)
{
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
sort(arr, arr+n);
sn = 0;
for(int i=0;i<n;i++)
{
if(i==0||arr[i]!=arr[i-1])
{
sum[sn] = 1;
if(sn>0)
{
sum[sn]+=sum[sn-1];
}
sn++;
}
else
{
sum[sn-1] ++;
}
}
int k = 8*I/n;
int K = 1;
for(int i=0;i<k;i++)
{
K<<=1;
if(K >= sn)
{
break;
}
}
if(K>=sn)
{
cout<<0<<endl;
}
else
{
int ret = sum[sn-1] - sum[K-1];
for(int i=K;i<sn;i++)
{
ret = min(ret, sum[sn-1]-(sum[i] - sum[i-K]));
}
cout<<ret<<endl;
}
}
return 0;
}
D. Welfare State
构造线段树，线段树节点seg.val保存该区间的最小值是多少。
对于2类操作，直接使树根节点root.val=x，表明该区间的最小值将调整为x
对于1类操作，从树根往下更新对应点所在区间的节点。更新一个节点时，首先把当前节点的seg.val往下传递，使child.val = max(child.val, seg.val)，然后递归往下。遇到叶子节点时，如果下标是操作目标p，使，如果不是，则是
。所有操作完成后，再对整个线段树进行更新，如果
小于所在区间的最小值val，把它更新为val。
#include <iostream>
#include <cstdio>
using namespace std;
int n;
const int N = 2*100001;
int arr[N];
int q;
struct seg
{
int l,r;
int val;
seg(){}
seg(int l, int r):l(l),r(r){}
}segs[N*4];
seg build_tree(int root, int l, int r)
{
segs[root] = seg(l, r);
if(l==r)
{
segs[root].val = arr[l];
}
else
{
int mid = (l+r)/2;
build_tree(2*root, l, mid);
build_tree(2*root+1, mid+1, r);
segs[root].val = min(segs[2*root].val, segs[2*root+1].val);
}
}
void apply(int root, int index, int val)
{
// cout<<"apply"<<segs[root].l <<' '<< segs[root].r<<' '<<index<<' '<<val<<endl;
if(segs[root].l == segs[root].r)
{
if(segs[root].l == index)
{
arr[index] = val;
segs[root].val = val;
}
else
{
if(segs[root].val > arr[segs[root].l])
{
arr[segs[root].l] = segs[root].val;
}
}
return;
}
if(segs[root].l<=index && index<=segs[root].r)
{
seg left = segs[2*root];
seg right = segs[2*root + 1];
if(left.val < segs[root].val)
{
segs[2*root].val = segs[root].val;
}
if(right.val < segs[root].val)
{
segs[2*root+1].val = segs[root].val;
}
if(left.l<=index && index<=left.r)
{
apply(2*root, index, val);
}
else
{
apply(2*root, index, segs[root].val);
}
if(right.l<=index &&index<=right.r)
{
apply(2*root+1, index, val);
}
else
{
apply(2*root+1, index, segs[root].val);
}
segs[root].val = min(segs[2*root].val, segs[2*root+1].val);
}
else
{
if(val>segs[root].val)
{
segs[root].val = val;
}
}
}
void applyFinal(int root, int val)
{
// cout<<"apply final"<<segs[root].l <<' '<< segs[root].r<<' '<<segs[root].val<<endl;
if(segs[root].l == segs[root].r)
{
arr[segs[root].l] = max(segs[root].val, val);
return;
}
applyFinal(2*root, max(val, segs[root].val));
applyFinal(2*root+1, max(val, segs[root].val));
}
int main()
{
#ifdef CODEBLOCKS
freopen("in.txt","r", stdin);
#endif // CODEBLOCKS
while(cin>>n)
{
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
build_tree(1, 0, n-1);
// cout<<"build end"<<endl;
cin>>q;
for(int i=0;i<q;i++)
{
int t,p,x;
cin>>t;
if(t==1)
{
cin>>p>>x;
apply(1, p-1, x);
// for(int i=0;i<n;i++)
// {
// cout<<arr[i]<<' ';
// }
// cout<<endl;
}
else
{
cin>>x;
if(x > segs[1].val)
{
segs[1].val = x;
}
}
}
applyFinal(1, segs[1].val);
for(int i=0;i<n;i++)
{
if(i)cout<<' ';
cout<<arr[i];
}
cout<<endl;
}
return 0;
}
