思路:套用拉格朗日乘数法在限制下函数最值的方法,添加未知数\(\lambda\),不过限制是什么呢?

显然能量应该满足限制.在最优意义下不难发现能量应该全部耗尽.于是需要我们最优化的函数如下:

\[min{\sum_{i=1}^{n}\frac{s_i}{v_i}+\lambda(\sum_{i=1}^{n}k_i(v_i-v_i')^2{s_i}-E)}\]

对于每个\(v_i\)求导,得到如下等式:

\[2\lambda{k_i}v_i^2(v_i-v_i')=1\]

对于\(\lambda\)求导,有:

\[\sum_{i=1}^{n}k_i(v_i-v_i')^2{s_i}=E\]

首先显然合理的\(v_i\)都应该满足\(v_i>v_i'\),我们考虑给定\(\lambda\)时,我们能够通过二分又第一种限制解出每个\(v_i\).

那么\(\lambda\)是什么?考虑第二种限制,显然左面的值是关于\(\lambda\)单调变化的,我们解出所有\(v_i\)check一下就可以通过二分解出\(\lambda\)的值了.

总之,二分套二分,时间复杂度\(O(nlog^2{n})\).

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef double f2;
 
#define N 10010
f2 s[N],k[N],_v[N];
 
f2 solve(f2 lam,int i){
    f2 L=_v[i],R=1e10,mid;
    while(R-L>1e-12){
        mid=(L+R)/2;
        if(2*lam*k[i]*mid*mid*(mid-_v[i])<1)L=mid;else R=mid;
    }return L;
}
int main(){
    int n;f2 E;scanf("%d%lf",&n,&E);
    register int i;for(i=1;i<=n;++i)scanf("%lf%lf%lf",&s[i],&k[i],&_v[i]);
     
    f2 llam=0,rlam=1e5,mid,add,tmp;
    while(rlam-llam>1e-12){
        mid=(llam+rlam)/2;
        for(add=0,i=1;i<=n;++i)tmp=solve(mid,i),add+=k[i]*s[i]*(tmp-_v[i])*(tmp-_v[i]);
        if(add>E)llam=mid;else rlam=mid;
    }
     
    f2 ans=0;for(i=1;i<=n;++i)ans+=s[i]/solve(llam,i);
     
    printf("%.10lf",ans);
     
    return 0;
}

思路:注意到三元环不好求,于是转化为所有三元组的数量减去不能形成环的三元组的数量.

我们令\(i\)输给\(j\),便有一条\(i\rightarrow{j}\)的有向边.

考虑不能形成三元环的三元组,则三个点之中必然有一个点入度为\(2\).

那么不能形成环的所有三元组的数量就等于:

\[add=\sum_{i=1}^{n}C_{indegree_{i}}^{2}\]

这意味着:对于所有入边,我们随意找出两个,都显然可以形成一个不能形成环的三元组.而且这样计算显然是不重不漏的.

考虑我们的答案:

\[ans=C_{n}^{3}-add=C_{n}^{3}-\sum_{i=1}^{n}\frac{indegree_{i}(indegree_{i}-1)}{2}\]

那么我们事实上是要最小化后面减去的东西.

我们对于每一场结果未知的比赛分配胜负,若令一个人取胜,那么其入度\(+1\),就会带来总答案的增加,我们发现每一次增广从某个节点通过的费用是单调不减的,于是拆边作费用流即可.

输出方案也就随便搞搞.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
  
#define INF 0x3f3f3f3f
  
#define N 110
int G[N][N];
  
queue<int>q;
struct Solver{
    int head[5100],next[50010],end[50010],flow[50010],cost[50010],ind;
    int d[5100],used[5100],slack[5100],id;bool inq[5100];
    inline void reset(){ind=0,id=1,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int f,int c){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f,cost[q++]=c;}
    inline void make(int a,int b,int f,int c){addedge(a,b,f,c),addedge(b,a,0,-c);}
    inline void spfa(int S,int T){
        memset(d,0x3f,sizeof d),d[S]=0,inq[S]=1,q.push(S);
        while(!q.empty()){
            int i=q.front();q.pop(),inq[i]=0;
            for(int j=head[i];j!=-1;j=next[j])if(flow[j]&&d[end[j]]>d[i]+cost[j]){
                d[end[j]]=d[i]+cost[j];
                if(!inq[end[j]])inq[end[j]]=1,q.push(end[j]);
            }
        }for(int i=S;i<=T;++i)d[i]=d[T]-d[i];
    }
    inline bool Newlabel(int S,int T){
        int Min=INF;for(int i=S;i<=T;++i)if(used[i]!=id&&slack[i]<Min)Min=slack[i];
        if(Min==INF)return 0;
        for(int i=S;i<=T;++i)if(used[i]==id)used[i]=-1,d[i]+=Min;return 1;
    }
    int Getflow(int p,int T,int maxflow){
        if(p==T)return maxflow;
        used[p]=id;
        for(int j=head[p];j!=-1;j=next[j]){
            if(flow[j]&&used[end[j]]!=id&&d[end[j]]+cost[j]==d[p]){
                int to=Getflow(end[j],T,maxflow<flow[j]?maxflow:flow[j]);if(to){flow[j]-=to,flow[j^1]+=to;return to;}
            }else if(flow[j])slack[end[j]]=min(slack[end[j]],d[end[j]]+cost[j]-d[p]);
        }return 0;
    }
    int Mincost(int S,int T){
        int res(0),get;spfa(S,T);
        do{
            memset(slack,0x3f,sizeof slack);
            while((get=Getflow(S,T,INF)))res+=d[S]*get,++id;
        }while(Newlabel(S,T));return res;
    }
}InuyashaKikyou;
  
#define Make InuyashaKikyou.make
int win[N],lose[N];
int main(){
    int n;scanf("%d",&n);
    register int i,j;for(i=1;i<=n;++i)for(j=1;j<=n;++j)scanf("%d",&G[i][j]);
    int id=0,t=0;for(i=1;i<=n;++i)for(j=i+1;j<=n;++j)if(G[i][j]==2)++id;
    int S=0,T=n+id+1;
    InuyashaKikyou.reset();
    for(i=1;i<=n;++i)for(j=i+1;j<=n;++j){
        if(G[i][j]==1)++win[i],++lose[j];else if(G[i][j]==0)++win[j],++lose[i];
        else Make(S,++t,1,0),Make(t,id+i,1,0),Make(t,id+j,1,0);
    }
    int nowcnt=0;
    for(i=1;i<=n;++i){
        int last=n-1-win[i]-lose[i];nowcnt+=win[i]*(win[i]-1)/2;
        while(last--)Make(id+i,T,1,win[i]++);
    }
    nowcnt+=InuyashaKikyou.Mincost(S,T);
    printf("%d\n",n*(n-1)*(n-2)/6-nowcnt);
  
    int to[2],last[2];
    for(i=1;i<=id;++i){
        int cnt=0;
        for(j=InuyashaKikyou.head[i];j!=-1;j=InuyashaKikyou.next[j]){
            if(InuyashaKikyou.end[j]>id)to[cnt]=InuyashaKikyou.end[j]-id,last[cnt++]=InuyashaKikyou.flow[j];
        }
        if(last[0]==0&&last[1]==1)G[to[0]][to[1]]=1,G[to[1]][to[0]]=0;
        else G[to[1]][to[0]]=1,G[to[0]][to[1]]=0;
    }
    for(i=1;i<=n;++i){
        for(j=1;j<=n;++j)printf("%d ",G[i][j]);puts("");
    }
    return 0;
}

思路:一开始的暴力思路是对于每个串,若想使得它成为字典序最小的串,就找到它和任意其他串的从前向后第一个字母不同的位置,并添加限制:这个串的该位置字母的字典序小于其他串的该位置字母的字典序.这样若限制无环,我们就说这个串可以是字典序最小的.

然而这样建图花费的时间太长.

若将所有的串插入一颗Trie树,考虑对于每个串,其需要考虑的限制仅仅是从根节点到串的结尾所对应的节点的路径上的分岔.这样限制数最多为\(O(L*26)\),那么总的限制数最多为\(O(300000*26)\),就可以暴力建图并利用TarjanCheck了.

(为什么没想到Trie树..)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

#define N 30010
#define L 300010

int ch[L][26],cnt,isend[L];
char s[L];int begin[N],len[N];

int G[26][26];
inline void reset(){memset(G,0,sizeof G);}
inline void addedge(int a,int b){/*printf("%d %d\n",a,b);*/G[a][b]=1;}

int dfn[26],low[26],tclock,stk[26],top,num;bool instk[26];
void dfs(int x){
	dfn[x]=low[x]=++tclock;stk[++top]=x,instk[x]=1;
	for(int j=0;j<26;++j)if(G[x][j]){
		if(!dfn[j])dfs(j),low[x]=min(low[x],low[j]);
		else if(instk[j])low[x]=min(low[x],dfn[j]);
	}if(dfn[x]==low[x]){
		++num;
		while(1){int i=stk[top--];instk[i]=0;if(x==i)break;}
	}
}
inline bool judge(){
	memset(dfn,0,sizeof dfn);tclock=top=num=0;memset(instk,0,sizeof instk);
	for(int i=0;i<26;++i)if(!dfn[i])dfs(i);
	return num==26;
}

int ans[N],siz;
int main(){
	int n;cin>>n;
	register int i,j,k;
	int now=0;for(i=1;i<=n;++i)begin[i]=now,scanf("%s",s+now),len[i]=strlen(s+now),now+=len[i];
	int p,y;
	for(i=1;i<=n;++i){
		for(p=0,j=0;j<len[i];++j){if(!ch[p][y=s[begin[i]+j]-'a'])ch[p][y]=++cnt;p=ch[p][y];}
		isend[p]=i;
	}
	for(i=1;i<=n;++i){
		bool notok=0;
		for(reset(),p=0,j=0;j<len[i];p=ch[p][y],++j){
			if(isend[p]&&isend[p]!=i)notok=1;
			y=s[begin[i]+j]-'a';for(k=0;k<26;++k)if(k!=y&&ch[p][k])addedge(y,k);
		}
		if(!notok&&judge())ans[++siz]=i;
	}
	printf("%d\n",siz);
	//for(i=1;i<=siz;++i)printf("%d\n",ans[i]);
	for(i=1;i<=siz;++i){for(j=0;j<len[ans[i]];++j)putchar(s[begin[ans[i]]+j]);puts("");}
	return 0;
}