poj1026 Cipher
2024-08-26 03:23:29
题目意思可概括为给定集合S = {1,..,n}的一个双射关系f, 求经过k次复合之后元素i对应的元素fk(i) (i∈S)。
由于函数是双射,一个原像对应唯一一个像,同样一个像有唯一一个原像,考虑整个映射关系,存在整数m∈ Z,使得fm=f0=I。
即具有周期性。
每个元素映射回它自己有独立的周期T(i),整个映射的周期T=lcm(T(i)), i ∈ S。
独立处理更快,但对于本题也是刚刚卡过。
当然如果事先把所有询问读入加以预处理或者直接全部预处理会更快。
样例代码860ms卡过。
http://poj.org/problem?id=1026#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std; const int maxn = + ;
int n;
char s[maxn];
int f[maxn];
int period[maxn];
int repeats; struct Node{
int from, to;
}node[maxn]; int gcd(int a, int b){
if(!b) return a;
return gcd(b, a % b);
} bool cmp(Node a, Node b){
return a.to < b.to;
} void init(){
for(int i = ; i < n; i++){
int t = f[i], cnt = ;
while(i != t) t = f[t], ++cnt;
period[i] = cnt;
}
} void solve(){
for(int i = ; i < n; i++) node[i].from = node[i].to = i;
for(int i = ; i < n; i++){
int p1 = repeats % period[i];
while(p1--) node[i].to = f[node[i].to];
}
sort(node, node + n, cmp);
for(int i = ; i < n; i++) printf("%c", s[node[i].from]);
printf("\n");
} int main(){
while(~scanf("%d", &n) && n){
for(int i = , j; i < n; i++){
scanf("%d", &j);
f[i] = j - ;
}
init();
while(~scanf("%d", &repeats) && repeats){
getchar();
gets(s);
int len = strlen(s);
for(int i = len; i < n; i++) s[i] = ' ';
s[n] = '\0';
solve();
}
printf("\n");
}
return ;
}
最新文章
- atitit. access token是什么??微信平台公众号开发access_token and Web session保持状态机制
- dipole antenna simulation by HFSS
- http和网页设计
- [转]ubuntu 14.04 系统设置不见了
- [iOS]为什么不要在init初始化方法里调用self.view
- DirectDraw 直接显示RGB图象的最简单实现
- (转)cocos2dx 内存管理
- ServletConfig对象 【通过此对象获取到web.xml中的信息】
- Android应用开发基础篇(6)-----Service
- boostrap插件
- Highest Rated Features
- 02_Python基本数据类型
- 使用 RHEL(RedHat)6.1 iso 安装包 安装Samba过程
- Unity3D学习(八):《Unity Shader入门精要》——透明效果
- sql语句优化(二)
- jquery 点击页面流畅弹出预定文字
- python笔记之循环控制
- angular 如何使用第三方组件ng-bootstrap
- D3 数据可视化实战 笔记
- POJ 2392 Space Elevator 贪心+dp
热门文章
- Java基础之访问文件与目录——获取与文件存储有关的信息(GetFileStores)
- JQuery实现页面企业广告图片切换和新闻列表滚动效果
- 别人写的一个Bootstrap系列教程
- spring AutowireCapableBeanFactory 自动注入
- PostgreSQL Replication之第十章 配置Slony(3)
- 成员变量&;&;局部变量
- HTML调用servlet(一)
- uboot.lds (一)
- /Users/alamps/AndroidStudioProjects/Demo11ListView
- System Hold, Fix Manager before resetting counters