当前位置: 首页 > news >正文

混乱的置换 解题报告

简要题意

给定一个长度为 \(n\) 的序列 \(a\),值域为 \([0,m]\)。将该序列循环右移 \(1\) 位,并记录下当前序列,重复该过程 \(n\) 次。将得到的序列按字典序升序排序,构成一个 \(n \times n\) 的矩阵,给出该矩阵的最后一列,询问矩阵的第一行。

数据范围:\(n \le 10^3,m \le 9\)

分析

循环位移有很多有意思的性质。

我们首先可以知道该矩阵的第一列,就是最后一列排序升序的结果。

那么我们观察到:将某一行循环右移后得到的序列,一定在矩阵里。这不废话

那么我们再观察:如果将所有以 \(x\) 结尾的行都循环右移一位,那么得到的行就是矩阵中所有以 \(x\) 开头的行。这不还是废话

那么我们再观察:这些序列在操作前后的相对顺序没有改变。为什么?

证明:我们假设对于两个以 \(x\) 结尾的序列 \(T_1,T_2\)\(T_1\) 排在 \(T_2\) 前),有 \(T_1=t_1+x,T_2=t_2+x\)。因为 \(T_1 < T_2\)(字典序比较,下同),那么有 \(T_1<T_2 \rightarrow t_1+x < t_2+x \rightarrow t_1<t_2\)。那么有 \(x+t_1<x+t_2\),也就是 \(T_1'<T_2'\)。Q.E.D.

那么依据这个结论,我们可以找到每一个序列右移后得到的序列,那么按这个顺序遍历,输出每一个序列的第一个元素即可。

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define Inf (1ll<<60)
#define For(i,s,t) for(int i=s;i<=t;++i)
#define Down(i,s,t) for(int i=s;i>=t;--i)
#define ls (i<<1)
#define rs (i<<1|1)
#define bmod(x) ((x)>=p?(x)-p:(x))
#define lowbit(x) ((x)&(-(x)))
#define End {printf("NO\n");exit(0);}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
inline void ckmx(int &x,int y){x=(x>y)?x:y;}
inline void ckmn(int &x,int y){x=(x<y)?x:y;}
inline void ckmx(ll &x,ll y){x=(x>y)?x:y;}
inline void ckmn(ll &x,ll y){x=(x<y)?x:y;}
inline int min(int x,int y){return x<y?x:y;}
inline int max(int x,int y){return x>y?x:y;}
inline ll min(ll x,ll y){return x<y?x:y;}
inline ll max(ll x,ll y){return x>y?x:y;}
char buf[1<<20],*p1,*p2;
#define gc() (p1 == p2 ? (p2 = buf + fread(p1 = buf, 1, 1 << 20, stdin), p1 == p2 ? EOF : *p1++) : *p1++)
#define read() ({\int x = 0, f = 1;\char c = gc();\while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = gc();\while(c >= '0' && c <= '9') x = x * 10 + (c & 15), c = gc();\f * x;\
})
void write(int x){if(x>=10) write(x/10);putchar(x%10+'0');
}
const int N=10100,M=20;
int n,m,t[M],a[N],cnt,st[N];
void findst(){For(i,0,m) ct[i]=t[i];int ind=0;For(i,1,n){while(!ct[ind]) ++ind;st[i]=ind;--ct[ind];}
}
vector<int> nod[M];
int cur[M],to[N];
int main()
{
#if !ONLINE_JUDGEfreopen("permutation.in","r",stdin);freopen("permutation.out","w",stdout);
#endif n=read(),m=read();int mn=m;For(i,1,n) a[i]=read(),++t[a[i]],ckmn(mn,a[i]);findst();For(i,1,n) nod[st[i]].push_back(i);For(i,1,n){to[nod[a[i]][cur[a[i]]]]=i;++cur[a[i]];}int nw=1;For(i,1,n){printf("%d ",st[nw]);nw=to[nw];}return 0;
}
http://www.hskmm.com/?act=detail&tid=32247

相关文章:

  • 我42岁才顿悟:穷人的富养是带娃到处旅游,富人的富养是教会这一项本事
  • 2025年10月环保板材品牌推荐:榜单聚焦西南龙头杰家
  • Dash to Dock
  • 2025 年碳纤维布厂家 TOP 企业品牌推荐排行榜,碳纤维布 / 建筑碳纤维布 / 加固碳纤维布 / 300 克碳纤维布 / 碳纤维加固布公司推荐!
  • 2025年10月龙骨机厂家最新推荐榜,轻钢,装配式建筑,高速,全自动,吊顶,隔墙,高精度,快装式,方通龙骨龙骨机推荐这十家公司!
  • 命令行AI编程工具Jules Tools发布解析
  • 2025年东莞脱模剂混合机厂家最新权威推荐榜:专业设备与高效服务深度解析,优质供应商联系方式全收录
  • 2025年破胶机厂家TOP企业品牌推荐排行榜,610,710,810,大型,自动型,低温环保,节能省电,自动打块,轮胎破胶机公司推荐
  • 2025年10月品牌设计公司推荐排行榜,聚焦企业综合实力与核心竞争力
  • 2025年3C铝型材厂家行业标杆:船舶铝材/电力铝材/3C铝材廊坊国美铝业,21项专利加持,全品类适配获五星推荐
  • 2025年工业机器人厂家最新权威推荐榜:专业集成与智能应用解决方案深度解析
  • what is 8.3 file-naming convention?
  • 2025智慧水务平台
  • 机惨
  • auipc指令在NEMU中的执行过程 - Zeeh
  • 如何在AutoCAD中进行GIS空间查询?
  • initContainers实现整个数据目录的挂载
  • 2025年屋脊通风天窗厂家最新权威推荐榜:工业厂房自然通风解决方案优选品牌
  • 2025年10月电子散热器行业权威报告:十大品牌技术创新、性能表现与市场布局全景解析及选购指南
  • 迁移boot分区解决brtfs引起的Sparse File Not Allowed问题
  • 阿里面试:Redis挂了怎么办?集群主节点挂了怎么 恢复数据?可能有多长时间 数据丢失?【转自】
  • 2025年10月北京开锁公司最新服务商平台推荐排行榜,北京紧急开锁换锁上门服务推荐!
  • 学霸的期末 解题报告
  • 一种适用于正整数值域的无旋平衡树
  • 2025 年电子散热器厂家 TOP 企业品牌推荐排行榜,电子 / 型材 / 插片 / 电源 / 固态 / 变频器 / 铝合金 / 逆变器散热器 / 散热器铝型材公司推荐
  • 禁用sentinel
  • 静态网站宣言:用IPFS重建开放网络的乐趣
  • 收敛数列的性质
  • Eclipse Mosquitto MQTT 代理中持久性引擎(database.c 概念)的作用分析报告 - 指南
  • FFmpeg 实现视频批量剪辑