CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
怒草评测姬
Buy and Resell
维护目前为止购买价格的最小值，若比当前价格低则做一次买入/卖出操作。然而，这个操作可能不是最优的，因此将这一天的价格同时加入所有价格集合作为撤回操作，在价格相同时优先消耗撤回操作，此时不计数。
#include<bits/stdc++.h>
using namespace std;
int t,n;
int main()
{
for(scanf("%d",&t); t--;)
{
scanf("%d",&n);
priority_queue<int> q;
map<int,int> mp;
long long ans=0,cnt=0;
for(int i=0,a; i<n; q.push(-a),++i)
{
scanf("%d",&a);
if(q.empty())continue;
int u=-q.top();
if(u>=a)continue;
q.pop();
if(mp[u])--mp[u];//消耗撤回操作，不计数
else cnt+=2;
ans+=a-u;
q.push(-a);//加入撤回操作
++mp[a];
}
printf("%lld %lld\n",ans,cnt);
}
}
Dream
#include<stdio.h>
int t,p;
int main()
{
for(scanf("%d",&t); t--;)
{
scanf("%d",&p);
for(int k=0; k<2; ++k)
for(int i=0; i<p; ++i,printf("\n"))
for(int j=0; j<p; ++j)
printf("%d ",i*j%p);
}
}
Find Integer
#include<stdio.h>
int t,n,a,b,c;
int main()
{
for(scanf("%d",&t); t--; printf("%d %d\n",b,c))
{
scanf("%d%d",&n,&a);
if(n==1)b=1,c=a+1;
else if(n==2)
{
for(c=1; a%2==0;)c<<=1,a>>=1;
b=a*a/2*c,c*=a*a/2+1;
}
else b=c=-1;
}
}
Neko’s loop
单调队列，LCM
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,s,m,k,kase,a[10009];
int main()
{
for(scanf("%lld",&t); t--;)
{
scanf("%lld%lld%lld%lld",&n,&s,&m,&k);
for(ll i=0; i<n; ++i)scanf("%lld",&a[i]);
vector<ll> vis(n,0);
ll ans=0;
for(ll i=0; i<n; ++i)
if(!vis[i])
{
vector<ll> v;
for(ll j=i; !vis[j]; j=(j+k)%n)
v.push_back(a[j]),vis[j]=1;
vector<ll> sum(3*v.size()+1,0);
for(ll i=0; i+1<sum.size(); ++i)
sum[i+1]=sum[i]+v[i%v.size()];
ll r=m%v.size(),p=m/v.size(),tmp=0;
if(p)r+=v.size(),--p;//多处理一个循环节
deque<ll> q;//单调队列维护区间和
for(ll i=0; i+1<sum.size(); ++i)
{
while(!q.empty()&&sum[i]-sum[q.back()]<0)q.pop_back();
for(q.push_back(i); q.back()-q.front()+1>r;)q.pop_front();
tmp=max(tmp,sum[i+1]-sum[q.front()]);
}
ans=max(ans,tmp+max(sum[v.size()]*p,0LL));
}
printf("Case #%lld: %lld\n",++kase,max(s-ans,0LL));
}
}
Tree and Permutation
#include<bits/stdc++.h>
#define mul(a,b,c) (1LL*(a)*(b)%(c))
using namespace std;
typedef int ll;
const ll M=1e9+7;
struct Graph
{
struct Vertex
{
vector<int> a;
int siz;
};
struct Edge
{
int from,to;
ll dist;
};
vector<Vertex> v;
vector<Edge> e;
Graph(int n):v(n) {}
void add(const Edge &ed)
{
v[ed.from].a.push_back(e.size());
e.push_back(ed);
}
int build(int u)
{
int ret=0;
v[u].siz=1;
for(int i=0,k,to; i<v[u].a.size(); ++i)
if(k=v[u].a[i],to=e[k].to,!v[to].siz)
{
ret=(ret+build(to))%M;
v[u].siz+=v[to].siz;
ret=(ret+mul(mul(v[to].siz,v.size()-v[to].siz,M),e[k].dist,M))%M;
}
return ret;
}
};
int main()
{
for(int n; ~scanf("%d",&n);)
{
Graph g(n);
for(int i=1,x,y,l; i<n; ++i)
{
scanf("%d%d%d",&x,&y,&l);
g.add({x-1,y-1,l}),g.add({y-1,x-1,l});
}
int ans=mul(g.build(0),2,M);
for(int i=2; i<n; ++i)ans=mul(ans,i,M);
printf("%d\n",ans);
}
}
YJJ’s Salesman
离散化+树状数组维护区间最大值。
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
struct Coord
{
int X,Y,V;
bool operator<(const Coord &b)const
{
return Y!=b.Y?Y<b.Y:X>b.X;
}
};
struct Ranker:vector<ll>
{
void init()
{
sort(begin(),end()),resize(unique(begin(),end())-begin());
}
int ask(ll x)const
{
return lower_bound(begin(),end(),x)-begin();
}
};
struct BaseFenwick
{
vector<ll> v;
BaseFenwick(int n):v(n,0) {}
void set(int x,ll val)
{
for(int i=x; i<v.size(); i+=i&-i)v[i]=max(v[i],val);
}
ll ask(int x)
{
ll r=0;
for(int i=x; i; i-=i&-i)r=max(r,v[i]);
return r;
}
};
int main()
{
int t,n,ans;
for(scanf("%d",&t); t--; printf("%d\n",ans))
{
scanf("%d",&n);
vector<Coord> p(n);
Ranker rk;
for(int i=0; i<n; ++i)
{
scanf("%d%d%d",&p[i].X,&p[i].Y,&p[i].V);
rk.push_back(p[i].X);
}
sort(p.begin(),p.end());
rk.init();
BaseFenwick f(rk.size()+9);
for(int i=ans=0; i<n; ++i)
{
ans=max(ans,p[i].V+=f.ask((p[i].X=rk.ask(p[i].X)+2)-1));
f.set(p[i].X,p[i].V);
}
}
}