2015.01.03集训总结

shinbokuow posted @ Jan 03, 2015 06:11:50 PM in Something , 929 阅读

Task#1 Contest

考的这叫一个惨淡.好在T2通过找规律A掉了.

T1题目大意:给出一个长度为\(n\)的排列,已知它是由顺序排列经过不超过三次的区间翻转得来的.求一种可行的翻转方案.

思路:首先我们考虑暴力算法.每一次枚举所有翻转的区间,这样的复杂度是\(O(n^7)\).(反正我是都T了 T^T)

注意到一点性质,就是给定序列由于翻转次数少,连续块的数目是很少的.这证明我们只需考虑连续块就行了,因为一次翻转必定是翻转若干个连续块.

然而有一种特殊情况,就是块内的元素为2的时候.此时进行分裂这个块的翻转是可能减小答案的.然而当块内的元素数目\(>3\)时,分裂这个块并复原在有意义的情况下花费的次数必定超过\(3\)次.

因此至多有\(p=10+\)个块,我们再暴力\((0.5*P^2)^3*p\)看起来就可以过了.

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

#define N 100010
int n,p[N],cnt,ins[N],num[20],seq[20],workseq[20],l[20],r[20],siz;bool rev[20],workrev[20];

inline void Init(){
	memcpy(workseq,seq,sizeof seq);
	for(int i=1;i<=cnt;++i)workrev[i]=rev[workseq[i]];
}

inline void change(int l,int r){
	int _seq[20];bool _rev[20];
	memcpy(_seq,workseq,sizeof _seq),memcpy(_rev,workrev,sizeof _rev);
	for(int i=l;i<=r;++i)_seq[i]=workseq[l+r-i],_rev[i]=1-workrev[l+r-i];
	memcpy(workseq,_seq,sizeof _seq),memcpy(workrev,_rev,sizeof _rev);
}

int lim,ans,ansl[4],ansr[4];
bool dfs(int dep){
	if(dep==lim){
		Init();for(int i=1;i<=dep;++i)change(ansl[i],ansr[i]);
		for(int i=1;i<=cnt;++i)if(num[workseq[i]]==1)workrev[i]=0;
		bool OK=1;for(int i=1;i<=cnt&&OK;++i)if(workseq[i]!=i||workrev[i])OK=0;
		return OK;
	}
	for(int i=1;i<=cnt;++i){
		for(int j=i;j<=cnt;++j){
			ansl[dep+1]=i,ansr[dep+1]=j;if(dfs(dep+1))return 1;
		}
	}return 0;
}

int main(){
	freopen("dance.in","r",stdin),freopen("dance.out","w",stdout);
	int T;cin>>T;
	int i,j,k;
	while(T--){
		cin>>n;for(i=1;i<=n;++i)scanf("%d",&p[i]);
		memset(ins,0,sizeof ins);
		memset(rev,0,sizeof rev);
		for(cnt=0,i=1;i<=n;i=j+1){
			for(j=i;p[j+1]==p[j]-1||p[j+1]==p[j]+1;++j);
			if(j-i+1>2)ins[min(p[i],p[j])]=++cnt,rev[cnt]=p[i]>p[j],num[cnt]=j-i+1;
			else if(j-i+1==2)ins[p[i]]=++cnt,rev[cnt]=0,ins[p[i+1]]=++cnt,rev[cnt]=0,num[cnt]=num[cnt-1]=1;
			else ins[p[i]]=++cnt,rev[cnt]=0,num[cnt]=1;
		}
		for(siz=0,i=1;i<=n;++i)if(ins[i])seq[++siz]=ins[i];
		for(i=0;i<=3;++i){
			lim=i;
			if(dfs(0)){
				printf("%d\n",i);
				Init();
				for(j=1;j<=i;++j){
					int ladd=0;for(k=1;k<ansl[j];++k)ladd+=num[workseq[k]];
					int radd=0;for(k=ansr[j]+1;k<=cnt;++k)radd+=num[workseq[k]];
					printf("%d %d\n",ladd+1,n-radd);
					change(ansl[j],ansr[j]);
				}
				break;
			}
		}
	}
	fclose(stdin),fclose(stdout);
	return 0;
}

T2题目大意:给出一个矩阵,满足\(A_{i,j}=gcd(i,j)\),求A的行列式的值.

思路:经打表发现消成上三角后\(A_{i,i}=\phi(i)\),所以答案等于:

\[ans=\Pi_{i=1}^{n}\phi(i)\]

线性筛\(O(n)\)水.

证明:貌似是数学归纳法,我懒就暂时挖坑了.

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

#define N 10000010
int p[1000010],cnt,phi[N];bool notp[N];
inline void pre(int n){
	register int i,j;
	for(phi[1]=1,i=2;i<=n;++i){
		if(!notp[i])p[++cnt]=i,phi[i]=i-1;
		for(j=1;j<=cnt&&p[j]*i<=n;++j){
			notp[i*p[j]]=1;
			if(i%p[j]==0){phi[i*p[j]]=phi[i]*p[j];break;}
			else phi[i*p[j]]=phi[i]*(p[j]-1);
		}
	}
}
			
static const int mod=(1e9)+7;
int main(){
	freopen("matrix.in","r",stdin),freopen("matrix.out","w",stdout);
	int n;cin>>n;pre(n);int res=1;for(int i=1;i<=n;++i)res=(long long)res*phi[i]%mod;printf("%d",res);
	fclose(stdin),fclose(stdout);
	return 0;
}

T3题目大意:(粘题面了)

传说火焰纹章(Fire Emblem)属于太阳之神鲁格·麦克·埃索伦(Lugh mac Ethlenn ),其形状象征着太阳之子。当达努神族(Tuatha Dé Danann )的祈求者召唤他时,火焰纹章上散布的火神石便会汇聚无穷无尽的太阳之力,代表太阳神消灭纹章拥有者的敌人。

火神石共 N 块,初始每块神石都或多或少拥有自己独一无二的太阳之力,当祈求者对一块神石念动咒语时,这块神石就会吸引多种太阳之力渐渐向它汇聚。由于邪眼魔王巴罗尔(Balor)的嫉妒,每块神石只能将它自身拥有的或间接接收到的太阳之力传送给它唯一的一个后继,而且对于每种不同的天然之力,神石 i 都只能将其收到的最多 Ci 传送给它的后继。祈求者已经预言了每块神石最初拥有的能量,你需要告诉祈求者,他选择每块火神石作为祈祷对象分别能收集到多少太阳之力。

输入格式

第一行有一个正整数 N 表示共有 N 块神石(标号从 1 到 N)。

接下来 N 行,第 i+1 行 3 个整数 A,B,C 分别表示第 i 块神石初始能量为 A,后继为 B,传送上

限为 C。(输入数据保证存在一个神石使得所有神石均可向其传送太阳之力)

输出格式

输出 n 个整数分别表示祈求者选择该神石可获得的太阳之力总数。

数据范围和注释

对于 30%的数据,N≤200。

对于 60%的数据,N≤5000。

对于 100%的数据,N≤100000,1<=B<=N,1<=A,C<=10000

思路:首先如果是一棵树,那么子树内部的信息利用可并堆很容易合并.现在是基环树,那么我们就首先对于子树内部的点套用树上的处理方法,随后我们将环复制一份,在环上依旧利用可并堆处理即可.(详情见代码)时间复杂度\(O(nlogn)\).

upd@20140104 23:10 已经写完了代码

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

#define INF ~0U>>1
#define l ch[0]
#define r ch[1]
struct Node{
	Node*ch[2],*pa;
	int v,cnt;
	Node():v(0),cnt(0){}
}Tnull,*null=&Tnull,mem[1000010],*G=mem;
Node*Newnode(int _v,int _cnt){
	G->l=G->r=G->pa=null;G->v=_v,G->cnt=_cnt;return G++;
}
int d;
Node*Merge(Node*x,Node*y){
	if(x==null||y==null)return x==null?y:x;d=1-d;
	if(x->v>y->v)return(x->ch[d]=Merge(x->ch[d],y))->pa=x;
	else return(y->ch[d]=Merge(y->ch[d],x))->pa=y;
}
Node*Copy(Node*p){
	Node*now=Newnode(p->v,p->cnt);
	if(p->l!=null)now->l=Copy(p->l);
	if(p->r!=null)now->r=Copy(p->r);
	return now;
}

int count(Node*q,int lim){
	int res=(q->v>lim?lim:q->v)*q->cnt;
	for(int i=0;i<2;++i)if(q->ch[i]!=null)res+=count(q->ch[i],lim);
	return res;
}

#define N 100010
int w[N],a[N],lim[N];

int head[N],next[N],end[N];
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}

bool vis[N];
int cir[N],cnt;bool oncir[N];
inline void find(int x){
	while(1){vis[x]=1;if(!vis[a[x]])x=a[x];else break;}
	int t=a[x];while(t^x)cir[++cnt]=t,t=a[t];cir[++cnt]=x;
	for(int i=1;i<=cnt;++i)oncir[cir[i]]=1;
}

Node*Root[N];

int ans[N],sav[N];

Node*p,*add;int delcnt;
inline void Build(int x,int fa){
	Root[x]=Newnode(w[x],1);
	for(int j=head[x];j;j=next[j])if(end[j]!=fa&&!oncir[end[j]]){
		Build(end[j],x);
		p=Root[end[j]];delcnt=0;
		while(1){
			if(p==null||p->v<=lim[end[j]])break;
			delcnt+=p->cnt,p=Merge(p->l,p->r);
		}if(delcnt)add=Newnode(lim[end[j]],delcnt),p=Merge(add,p);
		Root[x]=Merge(Root[x],p);
	}
	if(!oncir[x])ans[x]=count(Root[x],INF);
}

Node*seqRoot[N<<1];int seqlim[N<<1];

int main(){
	freopen("fire.in","r",stdin),freopen("fire.out","w",stdout);
	int n;scanf("%d",&n);register int i;
	for(i=1;i<=n;++i)scanf("%d%d%d",&w[i],&a[i],&lim[i]),addedge(a[i],i);
	
	find(1);
	
	for(i=1;i<=cnt;++i)Build(cir[i],-1);
	int minlim=~0U>>1;for(i=1;i<=cnt;++i)minlim=min(minlim,lim[cir[i]]);
	for(i=1;i<=cnt;++i)sav[i]=sav[i-1]+count(Root[cir[i]],minlim);
	
	for(i=1;i<=cnt;++i)seqRoot[i]=Root[cir[i]];
	for(i=cnt+1;i<=2*cnt;++i)seqRoot[i]=Copy(seqRoot[i-cnt]);
	for(i=1;i<=cnt;++i)seqlim[i]=lim[cir[i]];
	for(i=cnt+1;i<=2*cnt;++i)seqlim[i]=seqlim[i-cnt];

	for(i=2;i<=2*cnt;++i){
		p=seqRoot[i-1];delcnt=0;
		while(1){
			if(p==null||p->v<=seqlim[i-1])break;
			delcnt+=p->cnt,p=Merge(p->l,p->r);
		}if(delcnt)add=Newnode(seqlim[i-1],delcnt),p=Merge(p,add);
		seqRoot[i]=Merge(seqRoot[i],p);
		if(i>cnt)ans[cir[i-cnt]]=count(seqRoot[i],INF)-sav[i-cnt];
	}
	
	for(i=1;i<=n;++i)printf("%d ",ans[i]);
	fclose(stdin),fclose(stdout);return 0;
}

Task#2 QY讲课、

(1)拉格朗日乘数法

用来求解函数最值的一种有效方法.

若函数不存在限制,我们求出该函数关于每一个未知数的导数,并令它们均为0.此时我们便能够利用这些未知数的值求出最值.值得注意的是,满足上述导数均为0的未知数的解可能会有多组,均带入验证即可.

下面讨论函数存在限制的情况.一般情况下限制都是关于未知数的等式,移项可得右侧等于\(0\)的情况,我们构造拉格朗日函数为原函数加上

\(\lambda_{1}equation_1+\lambda_{2}equation_2+...+\lambda_{m}equation_m\)的形式.\(equation_{i}\)即表示原函数的第\(i\)个限制移项后形成的式子.我们对于添加的\(m\)个\(\lambda_i\)和原有的所有未知数分别求导,并令这些导数均为\(0\),便可以得到原函数在限制下的最值.

http://wyfcyx.is-programmer.com/posts/75158.html

http://wyfcyx.is-programmer.com/posts/75432.html

(2)MatrixTree定理(貌似还能用于有向图?)

一个无向图的生成树的个数等于这个无向图的度数矩阵减去这个无向图的邻接矩阵得到的矩阵去掉第\(i\)行和第\(i\)列的代数余子式的绝对值.

证明:由于博客版面太小写不下(lan).

应用:直接通过行列式的形式推公式,或者利用行列式进行暴力计算.(或者找规律233)

BZOJ3321这个公式我推了一天没推出来,现在找规律水过了,先挖坟.

(3)泰勒级数

用一个无限项的多项式去逼近某个函数.

例如\(f(x)=a_0x^0+a_1x^1+a_2x^2+...\)

令\(x=0\),\(a_0=f(0)\)

对两侧分别求导,有:\(f'(x)=a_1+2a_2x+3a_3x^2+...\)