异色弧

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