link
F. Fair Distribution
看到数据范围应该想到与根号有关，
那么分两种情况讨论：
①：机器人个数<sqrt(x)
②：机器人个数>sqrt(x)---->机器人平均能源数<sqrt(x)
分别枚举即可。
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define SZ(x) (int)(x.size())
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn = 2e6 + 6;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 2e3 + 3;
ll qpow(ll x,ll y) { ll ans=1;x%=mod; while(y) { if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1; } return ans; }
int _;
ll n,m;
ll cal(ll x,ll y) {
return (y+x-1)/x*x-y;
}
void so() {
scanf("%lld%lld",&n,&m);
ll ans=1ll<<60;
for(int i=1;i<=min(n,10000*1ll);i++) {//i robot
ans=min(ans,n-i+cal(i,m));
}
for(int i=1;i<=10000;i++) {//avg = i
if(n*i<m) continue;
ll x=n*i-m;
ans=min(ans,x%i+x/i);
}
printf("%lld\n",ans);
}
void init() {
}
int main() {
init();
for(scanf("%d",&_);_;_--) {
so();
}
return 0;
}
D. Shortest Path Query
关键在复杂度分析，首先很容易想到图是有返祖边的二叉树，那么每对点能够互相到达，必定经过两点的common ancestor，所以要先需处理出点到其所有祖先的最短距离。
对于每个节点i，求其到子孙节点的最短距离（在不经过比i深度小的点情况下），考虑连接子树内所有边跑最短路的整理复杂度，为
∑
E
[
i
]
∗
l
o
g
n
\sum{E[i]}*logn
∑E[i]∗logn 其中E[i]为子树内边的个数，考虑每个点所带来的边的贡献最多为log，那么总复杂度为
O
(
l
o
g
n
l
o
g
n
)
O(logn logn)
O(lognlogn)
直接对每个子树暴力dij就好。
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define SZ(x) (int)(x.size())
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pii;
const int maxn = 4e6 + 6;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
ll qpow(ll x,ll y) { ll ans=1;x%=mod; while(y) { if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1; } return ans; }
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
const double pi =acos(-1);
int _;
int n,m,q;
vector<ll>vec[maxn],cyc[maxn];
ll dis[maxn];
vector<pii>G[maxn],T[maxn];
void build(int u) {
int v=2*u;
if(v<=n) build(v);
if(v+1<=n) build(v+1);
v=u;
while(v) {
vec[v].pb(u);
v/=2;
}
}
int LCA(int x,int y){
vector<int>fx,fy;
while(x) {
fx.pb(x);
x/=2;
}
while(y) {
fy.pb(y);
y/=2;
}
reverse(all(fx));
reverse(all(fy));
int ans=1;
for(int i=0;i<min(SZ(fx),SZ(fy));i++) {
if(fx[i]==fy[i]) {
ans=fx[i];
}
else break;
}
return ans;
}
int get_(vector<ll>& v,int x) {
return lower_bound(all(v),x)-v.begin();
}
int main() {
scanf("%d%d",&n,&m);build(1);
for(int i=1;i<=m;i++) {
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
T[u].pb(mp(v,w));
}
for(int i=n;i>=1;i--) {
sort(all(vec[i]));
for(auto it:T[i]) {
int v=it.first;
int w=it.second;
G[i].pb(mp(v,w));
G[v].pb(mp(i,w));
}
for(auto v:vec[i]) dis[v]=1ll<<60;
priority_queue<pii>q;
q.push({0,i});
dis[i]=0;
while(!q.empty()) {
auto it=q.top();q.pop();
ll u=it.second;
ll w=-it.first;
if(dis[u]<w) continue;
for(auto k:G[u]) {
ll v=k.first;
ll w=k.second;
if(dis[u]+w<dis[v]) {
dis[v]=dis[u]+w;
q.push(mp(-dis[v],v));
}
}
}
for(auto v:vec[i]) cyc[i].pb(dis[v]);
}
// for(int i=1;i<=n;i++) {printf("%d:",i);
// for(int j:vec[i]) {
// printf("%d ",j);
// }printf("\n");
// }
scanf("%d",&q);
while(q--) {
int s,t,l;
scanf("%d%d",&s,&t);
l=LCA(s,t);
ll ans=1ll<<60;
//cout<<l<<endl;
while(l) {
//cout<<get_(vec[l],s)<<','<<get_(vec[l],t)<<endl;
ans=min(ans,cyc[l][get_(vec[l],s)]+cyc[l][get_(vec[l],t)]);
l/=2;
}
if(ans>=(1ll<<60)) ans=-1;
printf("%lld\n",ans);
}
return 0;
}
B. Restore Atlantis
注意到坐标<2000
可以考虑每个点的贡献。
注意到ban掉的点是连续的
那么对于每一个坐标来说，只需要管第一次和最后一次覆盖到它的矩形是谁就可。
这一部分在扫描线的过程中，对每个节点维护两个优先队列，表示删除和添加过的节点，对于每个i直接暴力查询就行。
1s有点卡常
O
(
C
∗
C
∗
l
o
g
n
+
n
∗
l
o
g
C
+
q
∗
l
o
g
n
)
O(C*C*logn+n*logC+q*logn)
O(C∗C∗logn+n∗logC+q∗logn)
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define SZ(x) (int)(x.size())
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pii;
const int maxn = 1e6 + 6;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
ll qpow(ll x,ll y) { ll ans=1;x%=mod; while(y) { if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1; } return ans; }
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
const double pi =acos(-1);
struct Tree {
priority_queue<int>mx[2];
priority_queue<int,vector<int>,greater<int>>mi[2];
}T[2001*4];
struct node {
int op,l,r,v;
};
vector<node>g[maxn];
int L[2020][2020],R[2020][2020];
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
void update(int rt,int l,int r,int ql,int qr,int o,int v) {
if(ql<=l&&r<=qr) {
T[rt].mx[o].push(v);
T[rt].mi[o].push(v);
return ;
}
if(ql<=mid) update(ls,l,mid,ql,qr,o,v);
if(qr>mid) update(rs,mid+1,r,ql,qr,o,v);
}
void dfs(int rt,int l,int r,int mx,int mi,int i) {
while(!T[rt].mx[0].empty()&&!T[rt].mx[1].empty()&&T[rt].mx[0].top()==T[rt].mx[1].top()) {
T[rt].mx[0].pop();
T[rt].mx[1].pop();
}
while(!T[rt].mi[0].empty()&&!T[rt].mi[1].empty()&&T[rt].mi[0].top()==T[rt].mi[1].top()) {
T[rt].mi[0].pop();
T[rt].mi[1].pop();
}
if(!T[rt].mx[1].empty()) mx=max(mx,T[rt].mx[1].top());
if(!T[rt].mi[1].empty()) mi=min(mi,T[rt].mi[1].top());
if(l==r) {
L[i][l]=mi;
R[i][l]=mx;
return ;
}
dfs(ls,l,mid,mx,mi,i);
dfs(rs,mid+1,r,mx,mi,i);
}
int n,q;
int s[maxn],t[maxn],p[maxn],c[maxn],ans[maxn];
bool cmp(int x,int y) {
return t[x]<t[y];
}
void add(int x,int v) {
for(;x<=n;x+=x&(-x)) c[x]+=v;
}
int ask(int x) {
int ans=0;
for(;x>0;x-=x&(-x)) ans+=c[x];
return ans;
}
vector<pii>o[maxn];
vector<int>qu[maxn];
int main() {
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) {
int xa,ya,xb,yb;
scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
xa++;xb++;ya++;yb++;
g[xa].pb({1,ya,yb-1,i});
g[xb].pb({0,ya,yb-1,i});
}
int all=0;
for(int i=1;i<=2001;i++) {
for(auto [op,l,r,v]:g[i]) {
update(1,1,2001,l,r,op,v);
}
dfs(1,1,2001,0,n+1,i);
for(int j=1;j<=2001;j++) {
if(R[i][j]!=0) {
qu[R[i][j]].pb(L[i][j]);
all++;
}
}
}
for(int i=1;i<=q;i++) {
scanf("%d%d",&s[i],&t[i]);
o[t[i]].pb({s[i],i});
}
for(int i=1,j=0;i<=n;i++) {
while(j+1<=i) {
++j;
for(int x:qu[j]) add(x,1);
}
for(auto [l,x]:o[i]) {
ans[x]=all-(ask(i)-ask(l-1));
}
}
for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
}
