首页 > 其他分享 >#链表#CF706E Working routine

#链表#CF706E Working routine

时间:2023-10-29 15:12:06浏览次数:37  
标签:xia Working int routine Tp Tq 链表 ans iut

题目

给出一个 \(n*m\) 的矩阵,每次交换两个等大的矩阵,输出 \(q\) 次操作后的矩阵


分析

维护向右和向下的指针,考虑最后输出只需要从每行的头指针向右跳,

那么修改实际上是将矩阵左边一列、上面一行、最后一行和最后一列向右下指针交换

时间复杂度 \(O((n+m)Q)\)


代码

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int N=1048576;
int n,m,Q,you[N],xia[N],a[N],rk[1011][1011];
int iut(){
	int ans=0; char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans;
}
void print(int ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
}
int main(){
	n=iut(),m=iut(),Q=iut();
	for (int i=0;i<n+2;++i)
	for (int j=0;j<m+2;++j) rk[i][j]=i*(m+2)+j;
	for (int i=0;i<n+2;++i)
	for (int j=0;j<m+1;++j) you[rk[i][j]]=rk[i][j+1];
	for (int i=0;i<n+1;++i)
	for (int j=0;j<m+2;++j) xia[rk[i][j]]=rk[i+1][j];
	for (int i=1;i<=n;++i)
	for (int j=1;j<=m;++j) a[rk[i][j]]=iut();
	for (int T=1;T<=Q;++T){
		int px=iut(),py=iut(),qx=iut(),qy=iut(),xl=iut(),yl=iut();
		int tp=rk[px-1][0],tq=rk[qx-1][0];
		for (int i=1;i<py;++i) tp=you[tp];
		for (int i=1;i<qy;++i) tq=you[tq];
		for (int Tp=tp,Tq=tq,i=0;i<xl+yl;++i)
		if (i<xl){
			Tp=xia[Tp],Tq=xia[Tq];
			swap(you[Tp],you[Tq]);
		}else{
			Tp=you[Tp],Tq=you[Tq];
			swap(xia[Tp],xia[Tq]);
		}
		for (int Tp=tp,Tq=tq,i=0;i<xl+yl;++i)
		if (i>=yl){
			Tp=xia[Tp],Tq=xia[Tq];
			swap(you[Tp],you[Tq]);
		}else{
			Tp=you[Tp],Tq=you[Tq];
			swap(xia[Tp],xia[Tq]);
		}
	}
	for (int i=1;i<=n;++i){
		int t=you[rk[i][0]];
		for (;t!=rk[i][m+1];t=you[t]) print(a[t]),putchar(32);
		putchar(10);
	}
	return 0;
}

标签:xia,Working,int,routine,Tp,Tq,链表,ans,iut
From: https://www.cnblogs.com/Spare-No-Effort/p/17795896.html

相关文章

  • 237. 删除链表中的节点(中)
    目录题目代码题目有一个单链表的 head,我们想删除它其中的一个节点 node。给你一个需要删除的节点 node 。你将 无法访问 第一个节点  head。链表的所有值都是唯一的,并且保证给定的节点 node 不是链表中的最后一个节点。删除给定的节点。注意,删除节点并不是指从......
  • 代码随想录第四天 | 24. 两两交换链表中的节点 19.删除链表的倒数第N个节点 面试题
    question1:SwapNodesinPairshttps://leetcode.cn/problems/swap-nodes-in-pairs/IwasalittleconfusedatfirstbecauseI'mthinkingwhethershouldIcreatanewhead,butsoonIcameupwiththeideaofcreatpre=Noneandwithan'if-els......
  • 206.反转链表
    1.题目介绍2.题解2.1迭代假设链表为1→2→3→∅,我们想要把它改成∅←1←2←3。在遍历链表时,将当前节点的next指针改为指向前一个节点。由于节点没有引用其前一个节点,因此必须事先存储其前一个节点。在更改引用之前,还需要存储后一个节点。最后返回新的头引用。作者:力扣......
  • Python数据结构——链表
    链表(LinkedList)是一种基本的数据结构,用于组织和管理数据。它是由一系列节点(Node)组成的数据结构,每个节点包含一个数据元素和指向下一个节点的引用。链表是一种非线性数据结构,与数组不同,它可以根据需要动态分配内存。什么是链表?链表是由节点组成的数据结构,每个节点包含两部分:数据元......
  • 数据结构与算法(LeetCode) 第二节 链表结构、栈、队列、递归行为、哈希表和有序表
    一、链表结构1.单向链表节点结构publicclassNode{ publicintvalue;publicNodenext;publicNode(intdata){value=data;}}2.双向链表节点结构publicclassDoubleNode{publicintvalue;publicDoubleNodelast;publicDouble......
  • 面试必刷TOP101:15、删除有序链表中重复的元素-I
    题目题解importjava.util.*;publicclassSolution{publicListNodedeleteDuplicates(ListNodehead){//空链表if(head==null)returnnull;//遍历指针ListNodecur=head;//指针当前和下一位不为空......
  • day 3 链表 203.移除链表元素、707.设计链表、206.反转链表
    203.移除链表元素题目链接:203.移除链表元素视频教程文字教程虚拟头节点虚拟头节点的目的:消除头节点的特殊性痛点:删除头节点和删除其他节点的操作是不一样的,导致写代码时需要分两种情况考虑因为其他链表都是通过前一个节点删除的而头节点没有前一个节点,只需将头节点向......
  • org.apache.subversion.javahl.ClientException: The working copy needs to be upgra
    eclipse不编译,每次修改代码控制台都显示错误svn:Theworkingcopyneedstobeupgradedorg.apache.subversion.javahl.ClientException:Theworkingcopyneedstobeupgradedsvn:Workingcopy‘E:\aliyun-spirit\spiritmap0916′istooold(format10,createdbySubversi......
  • 代码随想录第三天 | 203.移除链表元素 707.设计链表 206.反转链表
    第一题:https://leetcode.cn/problems/remove-linked-list-elements/我一开始打算是搞先判断第一个节点是不是,如果不是就作为头节点来着,不过后来一想觉得太麻烦了,仔细一看题目发现居然已经提供了模拟头节点的方法,就用了呗GPT3.5:那你我的想法有颇多相似之处啊.jpg第二题:https://l......
  • 双向链表的建立和使用场景
    双向链表(DoublyLinkedList)是一种常见的数据结构,它在链表的基础上增加了一个指向前一个节点的指针,这使得在双向链表中可以方便地进行双向遍历。创建双向链表的步骤:定义节点类:首先,定义一个节点类,这个节点类通常包含三个属性:数据域(存储数据的部分)、指向下一个节点的指针(通常称为n......