比赛链接：https://codeforces.com/contest/2026
A. Perpendicular Segments
题目说了必定有答案，直接对角线即可
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#define ll long long
#define lowbit(x) (x & -x)
using namespace std;
mt19937 rnd(time(0));
const ll mod=1e9+7;
const ll N=2e5+5;
ll ksm(ll x,ll y)
{
ll ans=1;
while(y)
{
if(y&1)
ans=(ans%mod*x%mod)%mod;
x=x%mod*(x%mod)%mod;
y>>=1;
}
return ans%mod%mod;
}
ll gcd(ll x,ll y)
{
if(y==0)
return x;
else
return gcd(y,x%y);
}
void fio()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int main()
{
fio();
ll t;
cin>>t;
while(t--)
{
ll x,y,k;
cin>>x>>y>>k;
ll j=min(x,y);
cout<<0<<" "<<0<<" "<<j<<" "<<j<<endl;
cout<<j<<" "<<0<<" "<<0<<" "<<j<<endl;
}
}
B. Black Cells
n为偶数答案是固定的，n为奇数可以二分答案
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#define ll long long
#define lowbit(x) (x & -x)
using namespace std;
mt19937 rnd(time(0));
const ll mod=1e9+7;
const ll N=2e5+5;
ll ksm(ll x,ll y)
{
ll ans=1;
while(y)
{
if(y&1)
ans=(ans%mod*x%mod)%mod;
x=x%mod*(x%mod)%mod;
y>>=1;
}
return ans%mod%mod;
}
ll gcd(ll x,ll y)
{
if(y==0)
return x;
else
return gcd(y,x%y);
}
void fio()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
ll a[250000];
int main()
{
fio();
ll t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
if(n==1)
{
ll b;
cin>>b;
cout<<1<<endl;
continue;
}
for(ll i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+1+n);
//a[n+1]=0;
if(n%2==0)
{
ll ans=0;
for(ll i=1;i<=n-1;i+=2)
{
ans=max(ans,a[i+1]-a[i]);
}
cout<<ans<<endl;
}
else
{
ll l=1,r=1e18;
while(l<r)
{
ll mid=(l+r)>>1;
ll gs=1;
ll cnt=0;
ll pd=0;
while(gs<=n-1)
{
if(a[gs+1]-a[gs]<=mid)
{
gs+=2;
continue;
}
else
{
if(cnt==1){
pd=1;
break;
}
gs++;
cnt++;
continue;
}
}
if(pd)
l=mid+1;
else
r=mid;
}
cout<<r<<endl;
}
}
}
C. Action Figures
分析可得0点必选买，非0点优先用0点消除，其次用下标最小的1点消除
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#define ll long long
#define lowbit(x) (x & -x)
using namespace std;
mt19937 rnd(time(0));
const ll mod=1e9+7;
const ll N=2e5+5;
ll ksm(ll x,ll y)
{
ll ans=1;
while(y)
{
if(y&1)
ans=(ans%mod*x%mod)%mod;
x=x%mod*(x%mod)%mod;
y>>=1;
}
return ans%mod%mod;
}
ll gcd(ll x,ll y)
{
if(y==0)
return x;
else
return gcd(y,x%y);
}
void fio()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
ll a[550000];
int main()
{
fio();
ll t;
cin>>t;
while(t--)
{
ll mo=1;
ll n;
cin>>n;
string f;
cin>>f;
set<ll>q,k;
ll op=0;
ll ans=0;
for(ll i=1;i<=n;i++)
{
if(f[i-1]=='0')
q.insert(i);
else
k.insert(i);
}
for(ll i=f.size()-1;i>=0;i--)
{
if(f[i]=='1')
{
ll c=(i+1);
auto j=k.lower_bound(c);
if(j!=k.end())
{
if(q.size()>0)
{
ll u=*q.rbegin();
q.erase(u);
ans+=u;
k.erase(c);
}
else
{
if(k.size()==1)
{
ans+=c;
k.clear();
}
else
{
ll u=*k.begin();
k.erase(c);
k.erase(u);
ans+=u;
}
}
}
}
else
{
ll u=i+1;
if(q.lower_bound(u)!=q.end())
{
q.erase(u);
ans+=u;
}
}
//cout<<ans<<endl;
}
cout<<ans<<endl;
}
}
D. Sums of Segments
直接暴力统计优化，数据不会爆long long
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#define ll long long
#define lowbit(x) (x & -x)
using namespace std;
mt19937 rnd(time(0));
const ll mod=1e9+7;
const ll N=2e5+5;
ll ksm(ll x,ll y)
{
ll ans=1;
while(y)
{
if(y&1)
ans=(ans%mod*x%mod)%mod;
x=x%mod*(x%mod)%mod;
y>>=1;
}
return ans%mod%mod;
}
ll gcd(ll x,ll y)
{
if(y==0)
return x;
else
return gcd(y,x%y);
}
void fio()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
ll a[325000];
ll pre[325000];//一维前缀
ll pre1[325000];//类似二维
ll sub[320555];
ll pre3[325000];
//1
//1 2
//1 2 5
//1 2 5 10
ll n;
set<pair<ll,ll>>q;
ll qu(ll x)
{
ll ans=0;
auto j=q.lower_bound({x,0});
ll zq=(*j).second;
ans+=pre3[zq-1];
j--;
ll wz=x-(*j).first+zq-1;
ans+=pre1[zq]-sub[wz+1]-(pre[wz]-pre[zq-1])*(n-zq-(wz-zq));
return ans;
}
int main()
{
fio();
ll t;
t=1;
while(t--)
{
q.clear();
cin>>n;
ll cnt=0;
for(ll i=1;i<=n;i++)cin>>a[i],pre[i]=pre[i-1]+a[i],cnt+=pre[i];
pre1[1]=cnt;
for(ll i=2;i<=n;i++)pre1[i]=pre1[i-1]-(n-i+2)*a[i-1];
for(ll i=1;i<=n;i++)pre3[i]=pre3[i-1]+pre1[i];
sub[n+1]=0;
for(ll i=n;i>=1;i--)sub[i]=sub[i+1]+a[i]*(n-i+1);
q.insert({0,0});
cnt=0;
for(ll i=1;i<=n;i++)
{
cnt+=(n-i+1);
q.insert({cnt,i});
}
ll op;
cin>>op;
while(op--)
{
ll l,r;
cin>>l>>r;
cout<<qu(r)-(l-1?qu(l-1):0)<<endl;
}
}
}