1. 将的后继节点的前驱节点设置为的前驱节点
2. 将的前驱节点的后继节点设置为的后继节点
3. 将尾节点的后继节点设置为
4. 将的前驱节点设置为尾节点
5. 最后将尾节点设置为

#include<iostream>
#define endl '\n'
using namespace std;
using ll=long long;

int n,m,now,tail,l,r;
struct node{
    int prev;
    int next;
}a[1000005];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>now;
        a[now].prev=tail;
        a[tail].next=now;
        tail=now;
    }

    for(int i=1;i<=m;i++)
    {
        cin>>l>>r;
        if(r==tail)
            continue;
        a[a[r].next].prev=a[l].prev;
        a[a[l].prev].next=a[r].next;
        a[tail].next=l;
        a[l].prev=tail;
        tail=r;
    }

    while(a[tail].prev!=0)
    {
        cout<<tail<<' ';
        tail=a[tail].prev;
    }
    cout<<tail;

    return 0;
}

G 时钟巡回——同心协力（数论）

题目回顾

思路分析

注意到，并且最多有组测试用例，故直接进行模拟的时间复杂度在最坏情况下不低于，为数量级，会超出时间限制，并不可取。

由于移动时针的次数没有限制，则对于每一组确定的，最终能达到的最大时刻都是唯一确定的。本题是一道数学结论题，考察的是数学知识，正确的思路是用数学方法求解出答案并直接输出。

记，对于给定的，求  所能表示的最大数。即求在模意义下所能表示的最大数。

（1）

我们先考虑，且只有一种能转动的刻度的情况。

此时我们需要求出，在模意义下所能表示的最大数。若能表示出模意义下的数，则必然有，即以作为未知数的不定方程有解。由裴蜀定理：

可知，若能表示出模意义下的数，则，即。

（2）

下面来考虑有两种能转动的刻度的情况。

此时我们需要求出，在模意义下所能表示的最大数。

与（1）同理，若能表示出一个数，则有，即以作为未知数的不定方程有解。由裴蜀定理可知，。此时有。

若能表示出模意义下的数，则必然有，即，即以作为未知数的不定方程有解。由裴蜀定理可知，。即。

同理，可以进一步推广到有个数的情况，此时的。

（3）

最后我们来处理的情况。

由（2）可知，用我们可以在模意义下表示出所有的倍数。

当是的倍数时，可以被表示出来，所以的存在对结果没有影响。和时一样，最终答案为。

当不是的倍数时，显然有： 即 。其中部分可以被表示出来，对结果没有影响。余数无法被表示，将作为模意义下的一部分加入到最终结果中。此时最终答案为。

合并上述两种情况，最终答案为。

示例代码如下。由于求解最大公因数的辗转相除法的时间复杂度为，总的时间复杂度为。

代码示例

#include<iostream>
#include<algorithm>
#define endl '\n'
using namespace std;
using ll=long long;

ll x,y,n1,n2,t;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T;
	cin>>T;
	while(T--)
	{
		cin>>x>>y>>n1>>n2;
		t=__gcd(x, __gcd(n1, n2));
		cout<<x-t+y%t<<endl;
	}

	return 0;
}

题意速览

伟大的sjh选中了奇数个数字，想要让大家计算这奇数个数字中每两个两个做异或运算的所有结果。可是当sjh写好题目出样例的时候，他惊奇地发现他每一组计算的结果中居然都少了一个运算结果，sjh已经算了半天样例了不想再找了，并且把这个难题丢给你来完成。

现在已经知道的是：sjh一开始用了个数字（是一个奇数），分别是，sjh对每一组的个数两两进行异或运算结果全部存储在一个数组中。

输入描述

第一行输入一个数字，表示一共有组测试样例。

接下来每一组有三行输入数据：

第一行输入一个数字，表示一共有个需要进行运算的数字。

第二行输入n个数字，分别为（每两个数字之间会有一个空格隔开)。

第三行输入个数字，表示存储在数组中的运算结果。

数据总输入量。输入量较大，建议使用效率较高的方式读入数据，如scanf。

输出描述

输出行，每一行输出一个遗漏的结果。

思路分析

注意到数据总输入量，即题目保证了不会出现且每一组中都有的最坏情况。

因此我们直接暴力计算两两异或的结果是不会超过题目所要求的时间限制的。

（1）

容易直接想到的思路是直接根据题意进行模拟，计算出两两异或的结果，然后将该结果（共个数字）与数组中（共个数字）进行两两比对，找出遗漏的数字。但通过两两比对的常规方法进行检索显然是会超时的。我们可以利用异或运算的性质，来帮助我们在的时间复杂度内，完成从个数字中检索遗漏数字的工作。下面介绍异或运算的几个简单性质。

（2）

在数学上，一般用符号代表异或运算（在计算机科学领域中也常用“^”运算符或来表示异或运算）。

异或运算有以下三点性质：

1.   恒等律：任意一个数与0进行异或运算的结果是它本身。
2.   归零律：任意一个数与它本身进行异或运算的结果是0。
3.   自反性：任意一个数与同一个数进行两次异或运算后的结果是它本身。
   

此外，异或运算也满足结合律和交换律。

（3）

根据这几点性质，我们可以定义一个变量，令它与两两异或的每一个结果都进行异或运算，再与数组中每一个数字进行异或运算。这样一来，对于那些没有遗漏的运算结果，我们都令和它们分别进行了两次异或运算，而唯独那一个题目所要求找出的遗漏了的运算结果，我们只令和它进行了一次异或运算。

根据异或运算的恒等律与自反性，我们将得到

变量的值即为题目所要求找出的遗漏的结果的值，将其直接输出即可。

（4）进一步优化

4.1 该解法在空间上的优化

下文的“代码示例”使用了上文所述的解法，它的时间复杂度为，空间复杂度为，可以通过本题。由于数组中的每一个数字只会需要用到一次，可以据此进一步降低程序的空间复杂度为，留待读者思考完善。

4.2 该解法在时间上的优化

另外，注意到一定为奇数，我们可以利用这一条件对上文所述的解法进行进一步优化。因为一定为奇数，所以当进行两两异或时，每一个都参与了即偶数次运算，根据归零律，我们可以推出

，

进而有

，

也即

所以当我们用变量同数组中的每一个数字进行异或运算后，即可得到题目所求的遗漏的结果。

经过这一优化后，求解答案时进行的异或运算次数减少了一半以上，虽然渐进时间复杂度仍为，但由于常数减小，总的耗时也得到了减少。

另外，由于我们无需存储的值，空间复杂度可以借机进行再一次的优化，从经4.1优化后的进一步降低至。

这一做法的代码如下：代码查看 (nowcoder.com)

4.3 其他解法

此外，本题还有时间复杂度同样为的第二种解法（用求和的方法找出遗漏的结果）：代码查看 (nowcoder.com)

以及平均时间复杂度同样为的第三种解法（使用C++STL的unordered_map容器，但由于常数较大差点超时）：代码查看 (nowcoder.com)

针对第三种解法，可以考虑用数组实现的桶结构来替代unordered_map容器实现的哈希表，可以得到渐进时间复杂度同样为但常数大大减小的第四种解法：代码查看 (nowcoder.com)

具体思路不再赘述，有兴趣的读者可以点击上面的链接查看示例代码自行研究。

代码示例

#include<iostream>
#define endl '\n'
using namespace std;
using ull=long long;

int n,ans,a[3005],arr[5000000];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T;
	cin>>T;
	while(T--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
			cin>>a[i];
		for(int i=1;i<=(n*(n-1)/2)-1;i++)
			cin>>arr[i];

		ans=0;
		for(int i=1;i<=n-1;i++)
			for(int j=i+1;j<=n;j++)
				ans^=a[i]^a[j];
		for(int i=1;i<=(n*(n-1)/2)-1;i++)
			ans^=arr[i];

		cout<<ans<<endl;
	}

	return 0;
}

题意速览

Sakura想穿过一条路去得到一副神奇的卡牌。
这条路上的传送门两两为一对，Sakura不可以越过传送门而不进行传送。当Sakura从传送门的左侧一格进入，会从对应传送门出来并且下一次只能往右走；从传送门的右侧一格进入，会从对应传送门出来并且下一次只能往左走。
同时路中间有若干面墙，Sakura不能走到墙上（他不会爬墙，也不会穿墙）。
保证所有的墙和传送门不会重合。请问Sakura能否（从左往右）穿过这条路。

输入描述

第一行包含三个整数，分别表示路的长度，传送门的对数和墙的数量。

接下来行，第行包含两个整数，表示一对传送门的坐标。

接下来一行包含个整数，表示墙的坐标。

输出描述

如果你能穿过这条路就输出"Yes"。否则输出"No"。

思路分析

根据题意模拟走路的过程即可。

由于这条路是一维的，这意味着我们只需一直向前（右）走即可，若在某一时刻遇到了墙也无需考虑回头向左走，因为在一维的路上我们必然会沿着我们来时的路，从另一个方向进入我们曾经进入过的所有传送门，并最终重新退回到起点。这也表明了，一旦我们在闷头向右走的过程中遇到了墙，就意味着我们必然无法穿过这条路，可以直接输出结果并结束程序。同时由于没有传送门在起点的左侧，我们可以保证不会存在“在若干个传送门组合间不停来回传送”的死循环现象。明确了这两点，我们就可以放心按照“一直向右走”的贪心策略进行模拟了。

以下面的程序为例，我们可以新建一个有个元素的数组，将每一个数组元素看作这条路的“一格”，并根据题意将输入进来的“墙”或“传送门”放置在“格子”上，其余的格子置0。在模拟行走的过程中，若遇到则意味着这是一块空地，什么也不用做，让计数器自动加一，继续向右走；若遇到则意味着遇到了墙，根据先前的结论，可以认为必然无法穿过这条路，直接输出"No"并结束程序即可；若遇到为其他数字，则说明这是一对传送门的其中一个，由于我们事先在这一格内存储了这对传送门的另一个传送门的坐标，我们直接令，就跳转到了这对传送门的另一个传送门的坐标上，然后继续让计数器自动加一，继续向右走。如此重复模拟这个走路的过程，直到遇到时停下，这时我们已经到达了目的地，输出"Yes"并结束程序即可。

代码示例如下，时间复杂度为。

代码示例

#include<iostream>
#define endl '\n'
using namespace std;
using ull=long long;

int n,m,q,x,y,a[100005];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin>>n>>m>>q;
	while(m--)
	{
		cin>>x>>y;
		a[x]=y;
		a[y]=x;
	}
	while(q--)
	{
		cin>>x;
		a[x]=-1;
	}

	for(int i=1;i<=n;i++)
	{
		if(a[i]==-1)
		{
			cout<<"No";
			return 0;
		}
		if(a[i])
			i=a[i];
	}
	cout<<"Yes";

	return 0;
}