关键词:
例题 6-5 移动盒子(Boxes in a Line, UVa127675)
问题 给定一行盒子,从左到右编号依次为1,2,...,n.可以执行以下命令:
1 X Y
把盒子 X 移动到 Y 的左边(如果已经在左边,忽略此命令)
2 X Y
把盒子 X 移动到 Y 右边(如果X已经在Y的右边,忽略此命令)
3 X Y
交换 X 和 Y 的位置
4
把整个顺序颠倒
指令保证合法,即X 不等于 Y, 输入包含不超过10组数据,每组第一行为盒子的数目n和指令的数目m(1<=n,m<=100000)。
Output :For each test case, print the sum of numbers at odd-indexed positions. Positions are numbered 1 to nfrom left to right.
样例输入:
6 4
1 1 4
2 3 5
3 1 6
4
6 3
1 1 4
2 3 5
3 1 6
100000 1
4
样例输出:
Case 1: 12
Case 2: 9
Case 3: 2500050000
如果用数组来求解,复杂度太高,每次要移动大量元素,因此很容易想到用双向链表求解。 当然可以用 自己构造双向链表,或者使用STL的list。
受到前一题的启发,其实可用两个 int
数组来构造双向链表,right 数组表示当前元素的下一个元素的下标,left表示前一个元素的下标。
i | 0 | 1 | 2 | 3 | 4 |
left[i] | 4 | 1 | 2 | 3 | 0 |
right[i] | 1 | 3 | 4 | 2 | 0 |
若交换 2和3 1 2 3 4-> 1 3 2 4 (right[i]) 变成
i代表元素位置下标 sum+=1+2=3
i | 0 | 1 | 2 | 3 | 4 |
left[i] | 4 | 0 | 3 | 1 | 2 |
right[i] | 1 | 3 | 4 | 2 | 0 |
分析:
用到了双向链表。
1。用了两个数组left[maxn],right[maxn]代表当前元素的左边一个或者右边一个,当这个值为0的时候代表不存在!
2。对于4号命令,逆转整个序列,并没有真正的逆转,而是用inv 记录 是否逆转,利用了逆转两次等于没有逆转这个道理。逆转只会影响到1命令和2命令,3命令是XY换一下,并不会影响到,所以对与1和2,直接op = 3 - op即可!利用inv这个变量也有利于最后的输出,最后输出发现inv是0的话,就是没逆转,那么直接把奇数位置的数加起来即可,反之,要用总和减去这个偶数序列,(因为当n是偶数并且逆转的情况,sum其实是偶数位置!)
3。最后注意的一点,对于3号命令,是XY置换,XY相邻和XY相隔很多元素,处理是不一样的。
如果用数组来求解,复杂度太高,每次要移动大量元素,因此很容易想到用双向链表求解。 当然可以用 自己构造双向链表,或者使用STL的list。受到前一题的启发,其实可用两个 int
数组来构造双向链表,rightt
数组表示当前元素的下一个元素的下标,leftt
表示前一个元素的下标。
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 100000 + 10;
int rightt[maxn],leftt[maxn];////left and righttt is ambiguous
void link(int x,int y)
{
rightt[x]=y;
leftt[y]=x;
}
int main()
{
int n,m,cnt=0;
while(scanf("%d%d",&n,&m) == 2)
{
for (int i = 0; i <= n; ++i)
{
leftt[i]=i-1;
rightt[i]=(i+1)%(n+1);
}
leftt[0]=n;
rightt[n]=0;
int op,inv=0,X,Y;
while(m--)
{
scanf("%d",&op);
if (op == 4)inv = !inv; //偶数列 项转置会变成奇数项 1 2 3 4 -> 4 3 2 1
else
{
scanf("%d%d",&X,&Y);
if(op==3&&rightt[Y]==X) //为了转化为同一种情况来处理,x、y只是一个代号,反正结果变得是值
swap(X,Y);
if (inv && op != 3)op = 3 - op;
if (op == 1 && rightt[X] == Y)continue;
if (op == 2 && rightt[Y] == X)continue;
int LX=leftt[X],RX=rightt[X],RY=rightt[Y],LY=leftt[Y];
if (op == 1)
{
link(LX,RX);
link(LY,X);
link(X,Y);
}
if (op == 2)
{
link(LX,RX);
link(Y,X);
link(X,RY);
}
//执行命令 3时候,注意如果X和Y是相邻的,需要特殊处理;
if (op == 3)
{
if(rightt[X]==Y)
{
link(LX,Y);
link(Y,X);
link(X,RY);
}
else
{
link(LX,Y);
link(Y,RX);
link(LY,X);
link(X,RY);
}
}
}
}
//0 1 2 3 4 ->1 3 2 4 0 交换2和3 结果 1+2
long long ans=0;
int b = 0;
for (int i = 1; i <= n; ++i)
{
b = rightt[b]; //向右推移
if (i % 2 == 1)ans+=b;
}
//
//如果n不是偶数的话,倒一下结果也一样
//最后输出发现inv是0的话,就是没逆转,那么直接把奇数位置的数加起来即可,反之,要用总和减去这个偶数序列,(因为当n是偶数并且逆转的情况,
//sum其实是偶数位置
if (n % 2 == 0 && inv)ans = (long long)(n+1)*n/2-ans;
printf("Case %d: %lld
",++cnt,ans);
}
return 0;
}
用left right定义数组会有歧义
left
and right
are already defined in namespace std
, which you are importing all of with using namespace std
. That‘s why you have an ambiguity.
法二:在op==3 分下来三种情况 XY相邻两种 不相邻 1种
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 100000 + 10;
int rightt[maxn],leftt[maxn];
void link(int x,int y)
{
rightt[x]=y;
leftt[y]=x;
}
int main()
{
int n,m,cnt=0;
while(scanf("%d%d",&n,&m) == 2)
{
for (int i = 0; i <= n; ++i)
{
leftt[i]=i-1;
rightt[i]=(i+1)%(n+1);
}
leftt[0]=n;
rightt[n]=0;
int op,inv=0,X,Y;
while(m--)
{
scanf("%d",&op);
if (op == 4)inv = !inv;
else
{
scanf("%d%d",&X,&Y);
if (inv && op != 3)op = 3 - op;
if (op == 1 && rightt[X] == Y)continue;
if (op == 2 && rightt[Y] == X)continue;
int LX=leftt[X],RX=rightt[X],RY=rightt[Y],LY=leftt[Y];
if (op == 1)
{
link(LX,RX);
link(LY,X);
link(X,Y);
}
if (op == 2)
{
link(LX,RX);
link(Y,X);
link(X,RY);
}
//执行命令 3时候,注意如果X和Y是相邻的,需要特殊处理;
if (op == 3)
{
if(rightt[X]==Y)
{
link(LX,Y);
link(Y,X);
link(X,RY);
}
else if(rightt[Y]==X)
{
link(LY,X);
link(X,Y);
link(Y,RX);
}
else{
link(LX,Y);
link(Y,RX);
link(LY,X);
link(X,RY);
}
}
}
}
//0 1 2 3 4 ->1 3 2 4 0 交换2和3 结果 1+2
long long ans=0;
int b = 0;
for (int i = 1; i <= n; ++i)
{
b = rightt[b]; //向右推移
if (i % 2 == 1)ans+=b;
}
//如果n不是偶数的话,倒一下结果也一样
//最后输出发现inv是0的话,就是没逆转,那么直接把奇数位置的数加起来即可,反之,要用总和减去这个偶数序列,(因为当n是偶数并且逆转的情况,
//sum其实是偶数位置
//偶数列 项转置会变成奇数项 1 2 3 4 -> 4 3 2 1
if (n % 2 == 0 && inv)ans = (long long)(n+1)*n/2-ans;
printf("Case %d: %lld
",++cnt,ans);
}
return 0;
}
算法入门经典第六章例题6-14abbott的复仇(abbott'srevenge)bfs算法实现
SampleInput31N33 11WLNR* 12WLFNRER* 13NLER* 21SLWRNF* 22SLWFELF* 23SFREL* 0SampleOutput(3,1)(2,1)(1,1)(1,2)(2,2)(2,3)(1,3)(1,2)(1,1)(2,1) (2,2)(1,2)(1,3)( 查看详情
第六章二叉树算法入门经典结构体指针
运行效果图结构体指针实现#include<stdio.h>#include<stdlib.h>#include<string.h>#defineN10000intfailed,n,v,ans[N];chars[N];//保存读入结点typedefstructNode//结点类型{ intflag;//是否被赋值过 intnumber;//结点值 structNo 查看详情
郑捷《机器学习算法原理与编程实践》学习笔记(第六章神经网络初步)6.5boltzmann机算法
6.5Boltzmann机算法6.5.1问题的提出6.5.2模拟退化原理6.5.3Boltzmann分布与退火过程6.5.4Boltzmann机类与退火过程 Boltzmann网络初始时,需要根据参数设置一系列的初始值,主要参数在_init_中 (1)构造方法如下classBoltzmannNet(object... 查看详情
html第六章
第六章盒子模型1.什么是盒子模型: CSS中盒子模型的概念就是,CSS将网页中所有元素都看成一个个盒子。 2.盒子模型的边框、内边距和外边距属性:盒子模型的属性图示边框border 内边距Padding外边距margin高heig... 查看详情
第六章例题
1#include<cstdio>2#include<cstring>34usingnamespacestd;56intbtr[1<<20];789intmain()10{11intD,I;1213while(scanf("%d%d",&D,&I)==2)14{15memset(btr,0,sizeof(btr));1617intk; 查看详情
第六章部分例题
1#include<iostream>2#include<sstream>34usingnamespacestd;56constintmaxn=100000;7intn;8intpostorder[maxn],inorder[maxn];9intlh[maxn],rh[maxn];101112boolread_list(int*a)13{14stringline;1516i 查看详情
第六章部分例题
1#include<iostream>2#include<cstdio>3#include<set>4#include<cstring>56usingnamespacestd;78constintmaxn=1000;9intUG[maxn][maxn];10intvis[maxn];11charstr[1024];12intin[maxn 查看详情
数据结构与算法(周鹏-未出版)-第六章树-6.5huffman树
6.5Huffman树 Huffman树又称最优树,可以用来构造最优编码,用于信息传输、数据压缩等方面,是一类有着广泛应用的二叉树。6.5.1二叉编码树 在计算机系统中,符号数据在处理之前首先需要对符号进行二进制编码。例如,... 查看详情
第六章部分例题
6-4自己先敲了一遍虽然可以完成书上的功能但是漏洞百出1#include<iostream>2#include<cstdio>3#include<cstring>45usingnamespacestd;67constintmaxn=100000+100;89chartxt[maxn];10intnext[maxn];1112intmain()13{1 查看详情
第六章部分例题
没看解答敲了一遍,发现自己题目的理解能力有点差 1#include<iostream>2#include<cstdio>34usingnamespacestd;56structNode7{8charvalue;9Node*ch1;10Node*ch2;11Node*ch3;12Node*ch4;1314Node():ch1(NULL),ch2(NULL 查看详情
第六章例题二叉树层次遍历
1.指针实现#include<iostream>#include<vector>#include<queue>#include<cstdio>#include<cstring>usingnamespacestd;#definemaxn100structNode{boolhave_value;intvalue;/*节点结构体*/ 查看详情
算法入门经典-第五章例题5-7丑数
#include<iostream>#include<vector>#include<queue>#include<set>usingnamespacestd;typedeflonglongll;constintcoeff={2,3,5};intmain(){//一些常见的优先队列,STL提供了更为简单的定义方法//对于任意丑数x则2x,3x,5x也 查看详情
第六章盒子模型
一.边框 1.边框颜色 border-color 边框颜色(可以设置上边框,如:border-top-color,也可以整体设置,但是要注意顺序) 2.边框粗细 border-width 边框粗细(可以设置上边框,如:border-top-width,也可以整体设置,但是要注意顺序) 2.边框样... 查看详情
dfs与dp算法之关系与经典入门例题(代码片段)
...具体代码dp思路解题思路具体代码声明本文不介绍dfs、dp算法的基础思路,有想了解的可以自己找资源学习。本文适合于刚刚接触dfs和dp算法的人,发现两种算法间的内在联系。本人算法之路走之甚短,如果理解出现问题欢迎大家... 查看详情
有关int范围的例题(算法竞赛入门经典)
对于任意大于1的自然数n,若n为奇数,则将n变为3n+1,否则变为n的一半。经过若干次这样的变换,一定会使n变为1。例如,3→10→5→16→8→4→2→1。输入n,输出变换的次数。n≤109。样例输入:3样例输出:71#include<iostream>2#... 查看详情
算法入门经典-第七章例题7-1除法
除法输入正整数n,按从小到大的顺序输出所有形如abcde/fghij=n的表达式,其中a~j恰好为数字0~9的一个排列,2<=n<=79.样例输入:62样例输出:79546/01238=6294736/01528=62#include<stdio.h>#include<string.h>intmain(){intn;//x/y=nx用abcde表示... 查看详情
第六章
盒子模型1.盒子(box)模型内容(content)、填充(padding)、边框(border)、边界(margin)2.不同部分的说明Content(内容):盒子中的内容,显示文本或图片Padding(内边距):清除内容周围的区域,内边距的透明度Border(边框)... 查看详情
======第六章文件管理======
文章目录6.1文件和文件系统6.1.1文件、记录和数据项6.1.2文件类型和文件系统模型6.1.3文件操作6.2文件的逻辑结构6.2.1文件逻辑结构的类型6.2.2顺序文件6.2.3索引文件6.2.4索引顺序文件6.5.2直接文件和哈希文件6.3外存分配方式6.3.1连续... 查看详情