1.[USACO20JAN] Wormhole Sort S
算法:二分，并查集

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+10,M=N,INF=1e9;

int n,m;
int t[N],cnt;
int p[N];
int c[N];
bool flag;

struct node
{
    int u,v,w;
}a[N];

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

bool cmp(node a,node b)
{
    return a.w>b.w;
}

bool check(int mid)
{
    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=1;i<=m&&a[i].w>=mid;i++)
    {
        int tu=find(a[i].u),tv=find(a[i].v);
        p[tu]=tv;
    }
    for(int i=1;i<=cnt;i++)
    {
        if(find(c[t[i]])!=find(t[i]))
            return 0;
    }
    return 1;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i];
        if(c[i]!=i)
        {
            flag=1;
            t[++cnt]=i;
        }
    }
    for(int i=1;i<=m;i++)
    {
        cin>>a[i].u>>a[i].v>>a[i].w;
    }
    if(!flag)
    {
        puts("-1");
        return 0;
    }
    sort(a+1,a+m+1,cmp);
    int l=a[m].w,r=a[1].w;
    while(l<r)
    {
        int mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<r;
    return 0;
}

2.[USACO20JAN]Farmer John Solves 3SUM G
算法:哈希表，区间dp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N=5010,T=1e6,M=3e6+10;

ll n,q;
ll h[M];
ll a[N];
ll f[N][N];

int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++) h[a[j]+T]=0;
        for(int j=i+1;j<=n;j++)
        {
            if(-a[i]-a[j]+T>=0) f[i][j]=h[-a[i]-a[j]+T];
            h[a[j]+T]++;
        }
    }
    for(int l=2;l<=n;l++)
    {
        for(int i=1;i<=n;i++)
        {
            int j=i+l-1;
            if(j<=n)
            {
                f[i][j]+=f[i+1][j]+f[i][j-1]-f[i+1][j-1];
            }
        }
    }
    while(q--)
    {
        ll ll,rr;
        cin>>ll>>rr;
        cout<<f[ll][rr]<<endl;
    }
    return 0;
}

3.[USACO20JAN]Springboards G
算法:dp+树状数组优化

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N=2e5+10;

int n,p;
int fr[N],to[N];
int t[N];
int tr[N];

struct node
{
    int x,y,yy,id;
}a[N];

bool cmp(node a,node b)
{
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}

bool ycmp(node a,node b)
{
    return a.y<b.y;
}

int lowbit(int x)
{
    return x&-x;
}

void add(int x,int val)
{
    for(int i=x;i<=p*2;i+=lowbit(i)) tr[i]=min(tr[i],val);
}

int query(int x)
{
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res=min(res,tr[i]);
    return res;
}

signed main()
{
    cin>>n>>p;
    for(int i=1;i<=p;i++)
    {
        cin>>a[i].x>>a[i].y;
        a[i].id=i;
        cin>>a[i+p].x>>a[i+p].y;
        a[i+p].id=i;
    }
    sort(a+1,a+2*p+1,ycmp);
    a[0].y=-1;
    for(int i=1;i<=2*p;i++) a[i].yy=a[i-1].yy+(a[i].y!=a[i-1].y);
    sort(a+1,a+2*p+1,cmp);
    for(int i=1;i<=2*p;i++)
    {
        if(fr[a[i].id]) to[a[i].id]=i;
        else fr[a[i].id]=i;
    }
    int res=1e9;
    for(int i=1;i<=2*p;i++)
    {
        t[i]=min(t[i],query(a[i].yy));
        if(fr[a[i].id]==i)
        {
            int tt=t[i]+a[i].x+a[i].y-a[to[a[i].id]].x-a[to[a[i].id]].y;
            t[to[a[i].id]]=min(t[to[a[i].id]],tt);
        }
        add(a[i].yy,t[i]);
        res=min(res,t[i]);
    }
    cout<<res+n*2;
    return 0;
}

4.[USACO20JAN]Time is Mooney G
算法:dp

#include <bits/stdc++.h>
using namespace std;

const int N=1010,M=2010;

int n,m,c;
int w[N];
int h[N],e[M],ne[M],idx;
int f[N][N];
int ans;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int main()
{
    cin>>n>>m>>c;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        add(v,u);
    }
    memset(f,-1,sizeof f);
    f[0][1]=0;
    for(int i=1;i<=1000;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=h[j];~k;k=ne[k])
            {
                int v=e[k];
                if(~f[i-1][v])
                {
                    f[i][j]=max(f[i][j],f[i-1][v]+w[j]);
                }
            }
        }
        if(ans<f[i][1]-c*i*i) ans=f[i][1]-c*i*i; 
    }
    cout<<ans;
    return 0;
}

5.Help Yourself
算法:dp,快速幂

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+10,mod=1e9+7;

struct seg
{
    int l,r;
}a[N];

int s[N*2];
long long f[N];

bool cmp(seg a,seg b)
{
    return a.l<b.l;
}

long long qmi(long long x,long long y)
{
    long long res=1;
    while(y)
    {
        if(y&1) res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].l>>a[i].r;
        s[a[i].r]++;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=2*n;i++)
    {
        s[i]+=s[i-1];
    }
    for(int i=1;i<=n;i++)
    {
        f[i]=(2*f[i-1]+qmi(2,s[a[i].l-1]))%mod;
    }
    cout<<f[n];
    return 0;
}

6.Swapity Swapity Swap S
算法:快速幂

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+10;

struct per
{
    int m[N];
}a,e;

int n,m,k;
int l[N],r[N];

void init()
{
    for(int i=1;i<=n;i++)
    {
        a.m[i]=e.m[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>l[i]>>r[i];
        reverse(e.m+l[i],e.m+r[i]+1);
    }
}

per mul(per x,per y)
{
    per c;
    for(int i=1;i<=n;i++)
    {
        c.m[i]=x.m[y.m[i]];
    }
    return c;
}

void qpow(int p)
{
    while(p)
    {
        if(p&1) a=mul(a,e);
        e=mul(e,e);
        p>>=1;
    }
}

int main()
{
    cin>>n>>m>>k;
    init();
    qpow(k);
    for(int i=1;i<=n;i++) cout<<a.m[i]<<endl;
    return 0;
}

7.[USACO20FEB] Triangles S
算法:数学，桶排序

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N=1e5+10,mod=1e9+7,T=10007;

int n;
int sum[N*2],cnt[N*2];
int ans=0;
struct node
{
    int x,y;
    bool operator< (const node o)const
    {
        if(x!=o.x) return x<o.x;
        return y<o.y;
    }
}a[N];

void solve()
{
    sort(a+1,a+n+1);
    memset(sum,0,sizeof sum);
    memset(cnt,0,sizeof cnt);
    int now=0,tot=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i].x!=a[i-1].x) now=0,tot=0;
        ans=(ans+(a[i].x*cnt[a[i].y+T]-sum[a[i].y+T])%mod
        *(a[i].y*tot-now)%mod)%mod;
        tot++;
        now=(now+a[i].y)%mod;
        cnt[a[i].y+T]++;
        sum[a[i].y+T]=(a[i].x+sum[a[i].y+T])%mod;
    }
}

void rev()
{
    for(int i=1;i<=n;i++)
    {
        int x=a[i].x,y=a[i].y;
        a[i].x=y;a[i].y=-x;
    }
}

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
    for(int i=0;i<=3;i++)
    {
        solve();
        rev();
    }
    cout<<ans;
    return 0;
}

8.Clock Tree S
算法:二分图

#include <bits/stdc++.h>
using namespace std;

const int N=3e4+10,M=N*2;

int n;
int u[N];
int h[N],e[M],ne[M],idx;
int s[3];
int v[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int x,int op,int f)
{
    s[v[x]=op]+=u[x];
    for(int i=h[x];~i;i=ne[i])
    {
        int j=e[i];
        if(j==f) continue;
        dfs(j,op^1,x);
    }
}

int main()
{
    memset(h,-1,sizeof h);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>u[i];
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y),add(y,x);
    }
    dfs(1,0,0);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int val=((s[v[i]]-s[v[i]^1])%12+12)%12;
        if(val==1||val==0) ans++;
    }
    cout<<ans;
    return 0;
}

9.Haircut G
算法:树状数组

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N=1e5+10;

int n;
int tr[N];
struct node
{
    int a,num;
}nd[N];

bool operator < (const node &x,const node &y)
{
    if(x.a==y.a) return x.num<y.num;
    return x.a<y.a;
}

int lowbit(int x)
{
    return x&-x;
}

void add(int x,int c)
{
    for(int i=x;i<=n;i+=lowbit(i))
    {
        tr[i]+=c;
    }
}

int query(int x)
{
    int res=0;
    for(int i=x;i;i-=lowbit(i))
    {
        res+=tr[i];
    }
    return res;
}

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>nd[i].a;
        nd[i].num=i;
        add(nd[i].num,1);
    }
    sort(nd+1,nd+n+1);
    int ans=0,ind=1;
    for(int i=0;i<n;i++)
    {
        cout<<ans<<endl;
        int t=ind;
        while(i==nd[t].a)
        {
            ans+=query(nd[t].num-1);
            add(nd[t].num,-1);
            t++;
        }
        ind=t;
    }
    return 0;
}