2024年3月7日发(作者：)
Noip2013提高组解题报告--ByGreenCloudS
Day1:第一题：转圈游戏（快速幂）根据题目，答案明显是(x+10^km)modn，化简一下，就成了(x+m(10^kmodn)modn)modn,所以，只需要求出10^kmodn即可，可以使用快速幂来求解,复杂度O(logk)。（另一个算法，设f(i)=10^imodn,则f(i)=f(i-1)*10modn,然后求出f(i)的循环节，复杂度O(n)）代码(C++)：#include
return0;}第二题：火柴排队（贪心+逆序对）对距离公式化简得：∑(ai-bi)^2=∑(ai^2-2aibi+bi^2)=∑ai^2+∑bi^2-2∑aibi要求∑(ai-bi)^2最小，就只需要∑aibi最大即可。这里有个贪心，当a1 3214先排序:12341234保持序列1不动，那么序列2中的3就对应序列1中的2位置，2就对应序列1中的1位置，1就对应序列1中的3位置，4就对应序列1中的4位置，那么重定义数组为：2134这个序列的逆序对为(2,1),所以答案是1。求逆序对方法：1.2.归并排序把数组扫一遍，顺序把每个数加入BIT或者是线段树等数据结构中，同时查询比这个数大的数有几个，加入答案。复杂度:O(nlogn)代码（C++）（树状数组）：#include structsaver{intv,t;};savera[MAXN],b[MAXN];boolcmp(saverx,savery){returnx.v 理，很明显，这样生成的图，两点之间要么没有路径，要么唯一一条路径中权值的最小值最大。所以，我们只要先跑一次最大生成树，然后在求点对之间的树上路径最小值就可以了。复杂度：O(mlogm+qlogn)代码（C++）（MST+树上倍增）：#include j=k;}returni;}intup[MAXN][MAXD],Min[MAXN][MAXD],h[MAXN];boolf[MAXN];structedge{edge*next;intt,d;edge(){next=NULL;}}*head[MAXN];voidAdd(ints,intt,intd){edge*p=new(edge);p->t=t,p->d=d,p->next=head[s];head[s]=p;}voidBuildTree(intv){f[v]=false;for(edge*p=head[v];p;p=p->next)if(f[p->t]){up[p->t][0]=v,Min[p->t][0]=p->d,h[p->t]=h[v]+1;BuildTree(p->t);}}intMove(int&v,intH){intrec=inf;for(inti=MAXD-1;i>=0;i--){if(h[up[v][i]]>=H){rec=min(rec,Min[v][i]);v=up[v][i];}}returnrec;}intQuery(intu,intv){if(Find(u)!=Find(v))return-1;intrec=inf; if(h[u]!=h[v])rec=h[u]>h[v]?Move(u,h[v]):Move(v,h[u]);//printf("%dn",rec);if(u==v)returnrec;for(inti=MAXD-1;i>=0;i--){if(up[u][i]!=up[v][i]){rec=min(rec,min(Min[u][i],Min[v][i]));u=up[u][i],v=up[v][i];}}rec=min(rec,min(Min[u][0],Min[v][0]));returnrec;}intmain(){clear(father),clear(head),clear(up);scanf("%d%d",&n,&m);for(inti=0;i Day2:第一题：积木大赛（模拟）直接贪心，每次取最大一个连续区间，然后模拟即可。令h[0]=0,答案就是：∑h[i]-h[i-1](0 usingnamespacestd;#defineMAXH10010#defineMAXN100010structnode{node*next;intt;node(){next=NULL;}}*head[MAXH];intmaxh=0;voidInsert(inth,intt){maxh=max(maxh,h);node*p=new(node);p->t=t,p->next=head[h];head[h]=p;}intn,h,delta=1,ans=0;boolf[MAXN];intmain(){memset(f,true,sizeof(f)),memset(head,0,sizeof(head));cin>>n;f[0]=f[n+1]=false;for(inti=0;i++ for(inti=0;i<=maxh;i++){if(i)ans+=delta;for(node*p=head[i];p;p=p->next){if(f[p->t-1]&&f[p->t+1])delta++;if((!f[p->t-1])&&(!f[p->t+1]))delta--;f[p->t]=false;}}cout< 如果直接DP毫无疑问复杂度是O(n^2)，会TLE，但是，考虑到我们每次取最值时候取得都是一个区间里的数，如f(i,0)=max{f(j,1)}+10<=j intmain(){scanf("%d",&n);for(inti=0;i++ q较小的情况是无压力的，但是在q大的情况下，毫无疑问会TLE，明显，在q较大的情况下，我们需要将每次BFS中重复搜索的冗余信息除去，所以我们可以先分析题目性质：（这里称要移动的棋子为目标棋子）首先，如果要移动目标棋子，那么我们首先必须要将空格移到该棋子的上下左右四个方向上相邻位置之一，然后才可以移动该棋子。然后，我们分析该棋子移动时候的性质：棋子每次可以移动，仅当空格位于其相邻位置的时候，每次移动完棋子，空格总会在棋子相邻的位置，那么我们发现，对于棋子在某一位置，然后空格又在其四个方向上某一相邻位置时，棋子要想某一方向移动一个时的花费的步数是一定的，那么，就可以先进行一次预处理，预处理出对于目标棋子在上述条件下每次移动所需的步数。然后，预处理完成之后，我们会发现每次查询都会变成一个求最短路的问题，用Dijstra或SPFA的话，可以在时限范围内解决。实现：定义一个数组Step[x][y][k][h]，表示目标棋子在位置（x，y）且空格在目标棋子的k方向上的相邻格子时，目标棋子往h方向移动1格所需的步数，然后用状态[x][y][k]作为节点建图，用各个状态的关系连边，每次询问时重新定义一个源点跟终点，跑最短路就可以得出答案。(预处理时跑n^2次O(n^2)的BFS就可以了)复杂度（Dijstra）：（n^4+qn^2logn）复杂度（SPFA）：（n^4+qn^2） 代码（SPFA）（Cpp）：#include intv[MAXN][MAXN][4],V=0;intdist[MAXN][MAXN],Move[MAXN][MAXN][4][4];intDist[MAXV];boolf[MAXV];intS,T;structnode{intx,y;node(int_x,int_y):x(_x),y(_y){}};queue if(Map[u.x+dir[i][0]][u.y+dir[i][1]]&&dist[u.x+dir[i][0]][u.y+dir[i][1]]==inf){dist[u.x+dir[i][0]][u.y+dir[i][1]]=dist[u.x][u.y]+1;if(u.x+dir[i][0]==Tx&&u.y+dir[i][1]==Ty)returndist[u.x][u.y]+1;(node(u.x+dir[i][0],u.y+dir[i][1]));}}}returninf;}structCmp{booloperator()(intx,inty){returnDist[x]>Dist[y];}};priority_queue }intmain(){if(u==T)returnDist[T];for(edge*p=head[u];p;p=p->next){if(Dist[p->t]>Dist[u]+p->d){Dist[p->t]=Dist[u]+p->d;f[p->t]=true;(p->t);}}}returnDist[T] }}for(inti=0;i++ }}}while(q--){cin>>ex>>ey>>sx>>sy>>tx>>ty;if(sx==tx&&sy==ty){cout<<0< cout<
发布评论