怒草评测姬

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);
        }
    }
}