异色弧

solution

70分

\(Let's\;orz\) BearChild!

朗格拉姆计数

solution

60分

将环复制两遍,预处理出前\(i\)个数中比\(j\)大的数的个数 ,枚举\(a,b\),答案加上\(c\)的个数.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 5001
#define M 10001
using namespace std;
typedef long long ll;
//s[i][j]表示前i个数中比j大的数的个数 
ll ans;
int s[M][N],a[M],n;
inline int read(){
    int ret=0;char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        ret=(ret<<1)+(ret<<3)+c-'0';
        c=getchar();
    }
    return ret;
}
inline void Aireen(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;++i)
        a[i+n]=a[i];
    for(int j=1;j<=n;++j)
        for(int i=1;i<=(n<<1);++i){
            s[i][j]=s[i-1][j];
            if(a[i]>j) ++s[i][j];
        }
    for(int i=1;i<=n;++i)
        for(int j=i;ja[i]){
                ans+=(ll)(s[i+n-1][a[j]]-s[j][a[j]]);
            }
    printf("%lld\n",ans);
}
int main(){
    freopen("counter.in","r",stdin);
    freopen("counter.out","w",stdout);
    Aireen();
    fclose(stdin);
    fclose(stdout);
    return 0;
}

100分

三元组的形式为\(123,231,312\).
\(231=XX1-321\).
\(312=3XX-321\).
树状数组或线段树维护即可.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 200005
using namespace std;
typedef long long ll;
ll ans;
int a[N],s[N],g[N],fr[N],be[N],n;
inline int read(){
    int ret=0;char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        ret=(ret<<1)+(ret<<3)+c-'0';
        c=getchar();
    }
    return ret;
}
inline int lowbit(int x){
    return x&(-x);
}
inline void add(int k){
    for(int i=k;i<=n;i+=lowbit(i))
        ++s[i];
}
inline int ask(int k){
    int ret=0;
    for(int i=k;i;i-=lowbit(i))
        ret+=s[i];
    return ret;
}
inline ll c(int k){
    return 1ll*k*(k-1)>>1ll;
} 
inline void Aireen(){
    n=read();
    for(int i=1;i<=n;++i){
        a[i]=read();g[a[i]]=i;
    }
    for(int i=1;i<=n;++i){
        fr[i]=ask(g[i]-1);
        be[i]=ask(n)-ask(g[i]);
        add(g[i]);
    }
    memset(s,0,sizeof(s));
    for(int i=n,f,b;i;--i){
        f=ask(g[i]-1);
        b=ask(n)-ask(g[i]);
        add(g[i]);
        ans+=1ll*fr[i]*b;//123
        ans+=c(be[i])-1ll*f*be[i];//312
        ans+=c(f)-1ll*f*be[i];//231 
    }
    printf("%lld\n",ans);
}
int main(){
    freopen("counter.in","r",stdin);
    freopen("counter.out","w",stdout);
    Aireen();
    fclose(stdin);
    fclose(stdout);
    return 0;
}

修路

solution

斯坦纳树

\(f[i][j]\)表示以\(i\)为根的树中,连通的节点的状态为\(j\)的最小/大权值.
\(f[i][j]=min\{f[i][l]+f[i][l^j]\}\),\(l\)为\(j\)的子集.
\(f[i][j]=min\{f[k][j]+g[k][i]\}\),这可以用\(spfa\)或\(dijkstra\)求解.

100分

用斯坦纳树求出\(f[\;][\;]\)数组.
如果在状态\(j\)中,\(i\)与\(n-i+1\)在\(j\)中或都不在\(j\)中,\(g[j]=min\{f[i][j]\}\)(保证\(i\)与\(n-i+1\)连通).
\(g[i]=min\{g[j]+g[i^j]\}j\)为\(i\)的子集\()\).

#include
#include
#include
#include
#define K 8
#define N 10005
#define M 20005
#define INF 10000000
#define min(a,b) a