KOI 2025 Round 1 Unofficial Mirror

P13510 [KOI 2025 #1] 远方的卡片 - 洛谷

很简单的模拟题，注意一个数只会出现两次，只用记录每个数第一次出现的时间，再次出现时两个下标之差-1就是中间数的个数。 

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
int n,cnt[4005],a,ans=0;
int main()
{
jiasu
cin>>n;
for(int i=1;i<=2*n;i++){cin>>a;if(cnt[a]==0) cnt[a]=i;else ans=max(i-cnt[a]-1,ans);
}
cout<<ans;return 0;
}

P13511 [KOI 2025 #1] 等腰直角三角形 - 洛谷

该题的简单点在于这是等腰直角三角形，而且底边平行于x轴，那么三个边的直线表达式就是

y=x+a

y=-x+b

y=c

题目直接给我们说了有两种情况，正三角和倒三角

正三角：c取所有点坐标y的最大值,a=y-x,b=x+y取最小值（因为要包含所有点），倒三角反之

 

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
ll n,x,y,mn=1e18,mx=-1e18,a=1e18,b=1e18,c=-1e18,d=-1e18;
int main()
{
jiasu
cin>>n;
for(int i=1;i<=n;i++){cin>>x>>y;mx=max(mx,y);mn=min(mn,y);a=min(a,x+y);b=min(b,y-x);c=max(c,y-x);d=max(d,x+y);
}
cout<<min(2*mx-a-b,c+d-2*mn);return 0;
}

P13512 [KOI 2025 #1] 稻草人 - 洛谷

很明显，我们要用i之前的较大的数之和超过箭的力量，这样才能使数量最小。用小根堆维护，从前向后遍历，每次把该数的值加入堆，sum记录的是堆里的数据之和，如果sum>p，我们就不断删去最小值，知道sum刚好大于等于p，不能再删去数，此时堆的大小就是答案。 

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
priority_queue<ll,vector<ll>,greater<ll>>r;
int main()
{
ll n,k,a,sum=0;
cin>>n>>k;
while(n--){cin>>a;sum+=a;r.push(a);if(sum<k){cout<<"-1 ";}else{while(sum-r.top()>=k){sum-=r.top();r.pop();}cout<<r.size()<<" ";}
}return 0;
}

 P13514 [KOI 2025 #1] 干草堆 - 洛谷

 这道题博主也是勉强才做出来的。这是上一题的plus版本，我们要处理多个询问。首先我们肯定是按照下标x从前向后遍历得到答案，那么先要将询问离线，按x从小到大排序。还是上一题的思想，我们每增加一个数，都希望数组从大到小排序，这样我们遍历数组，前缀和大于等于q时下标就是答案。我们怎么高效实现这个操作？

用树状数组是很好的选择，他的单点修改，前缀查询很方便。首先我们要把数组离散化

原数组： 2  5  6  3  9  1

离散化： 5  3  2  4  1  6

大数排前面

注意：数值相同的要离散化为不同的值

原数组： 5  1  7  3  3  9

离散化： 4  1  5  2  3  6

因为我们数组从大到小排序后相同的数也会在不同的下标，如果离散化为同一值那么会出错。这个和逆序数不一样，因为逆序数是严格的大于，所以6 6不是逆序对，所以相同的数要离散化为同一值。

我用两个树状数组，一个用来记录插入的数，并快速查找前缀和。另一个记录插入数的个数。

每次询问都将x前面的数插入，然后用二分查找刚好大于等于q的位置，再用第二个树状数组查找有几个数，保存答案。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define lowbit(x) (x&(-x))
#define MAXN 500050
using namespace std;
ll n,Q,temp[300005],ans[300005],c[300005];
bool vis[300005];
struct Fenwick_Tree{ll tree[MAXN];void add(int x,int num){while(x<=n){	    tree[x]+=num;x+=lowbit(x);}}ll search(int x){	ll re=0;while(x){   re+=tree[x];x-=lowbit(x);}return re;}
}r1,r2;
struct point{ll x,num;}a[300005];
struct question{ll x,p,num;}q[300005];
bool cmp(point &s1,point &s2){return s1.x>s2.x;}
bool cmp2(question &s1,question &s2){return s1.x<s2.x;}
int main(){
cin>>n>>Q;
for(int i=1;i<=n;i++){cin>>c[i];a[i].x=c[i];a[i].num=i;temp[i]=a[i].x;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++) temp[a[i].num]=i;
for(int i=1;i<=Q;i++) cin>>q[i].x>>q[i].p,q[i].num=i;
sort(q+1,q+1+Q,cmp2);
ll now=0;
for(int i=1;i<=Q;i++){while(now<q[i].x){now++;if(!vis[now]){r1.add(temp[now],c[now]);r2.add(temp[now],1);vis[now]=true;}}ll l=0,r=n+1;while(l+1<r){ll mid=(l+r)/2;if(r1.search(mid)>=q[i].p) r=mid;else l=mid;}if(r==n+1) ans[q[i].num]=-1;else ans[q[i].num]=r2.search(r);
}
for(int i=1;i<=Q;i++) cout<<ans[i]<<endl;return 0;
}