timus 1175. Strange Sequence 解题报告
2024-10-15 16:52:02
1.题目描述:
1175. Strange Sequence
Time limit: 1.0 second
Memory limit: 2 MB
Memory limit: 2 MB
You have been asked to discover some important properties of one strange sequences set. Each sequence of the parameterized set is given by a recurrent formula:
Xn+1 = F(Xn-1, Xn),
where n > 1, and the value of F(X,Y) is evaluated by the following algorithm:
- find H = (A1*X*Y + A2*X + A3*Y + A4);
- if H > B1 then H is decreased by C until H ≤ B2;
- the resulting value of H is the value of function F.
The sequence is completely defined by nonnegative constants A1, A2, A3, A4, B1, B2 and C.
One may easily verify that such sequence possess a property that Xp+n = Xp+q+n for appropriate large enough positive integers p and q and for all n ≥ 0. You task is to find the minimal p and q for the property above to hold. Pay attention that numbers p and q are well defined and do not depend on way minimization is done.
Input
The first line contains seven integers: A1, A2, A3, A4, B1, B2 and C. The first two members of sequence (X1 and X2) are placed at the second line. You may assume that all intermediate values of H and all values of F fit in range [0..100000].
Output
An output should consist of two integers (p and q) separated by a space.
Sample
input | output |
---|---|
0 0 2 3 20 5 7 |
2 3 |
2.解题思路
题目要求确定p和q,我们先确定q再确定p,有了q只需要从x1,x2开始逐个尝试就能得出p。如何确定q呢?既然题目说了这个序列以q为循环节,我们可以假定序列在迭代足够多次之后就进入了循环,设这个次数为max。这样迭代max后再从1开始寻找q就可以啦~
3.代码:
#include <iostream>
#define max 300000
using namespace std; int a1,a2,a3,a4,b1,b2,c,x1,x2;
int p,q; int cal(int x, int y) {
int h = a1*x*y+a2*x+a3*y+a4;
if (h > b1) {
while (h > b2) {
h -= c;
}
}
return h;
} void iter(int& x, int& y) {
int tmp = cal(x, y);
x = y;
y = tmp;
} //假定迭代max次后处于稳定状态
//思路:迭代max次;继续迭代找到q;x1,x2迭代q次得到x3,x4;同时迭代直到x1==x3 && x2 == x4,找到p
int main() {
cin >> a1 >> a2 >> a3 >> a4 >> b1 >> b2 >> c >> x1 >> x2;
int i, tmp1, tmp2, tmp3, tmp4;
tmp3 = x1;
tmp4 = x2;
for (i = ; i < max; i++) {
iter(x1, x2);
}
tmp1 = x1;
tmp2 = x2;
q = ;
iter(x1, x2);
while (x1 != tmp1 || x2 != tmp2) {
q++;
iter(x1, x2);
}
tmp1 = tmp3;
tmp2 = tmp4;
iter(tmp1,tmp2);
i = ;
while (i != q) {
i++;
iter(tmp1, tmp2);
}
p = ;
while (tmp1 != tmp3 || tmp2 != tmp4) {
p++;
iter(tmp1, tmp2);
iter(tmp3, tmp4);
}
cout << p << " " << q << endl;
}
4.复杂度:
空间:O(1)
时间:O(p+q+max)
5.心得:
把这道题写出来,是因为我第一次尝试时思路是错的:把<x0,x1>作为一个pair,pos是迭代次数,用一个map<pair,pos> result存储,一直迭代<x0,x1>,递增pos,并把结果存入result,当重复插入时(x.pair == y.pair,x.pos < y.pos),就求出了p,q: p = x.pos, q = y.pos - x.pos。
。。。
没错我当时就是这么写的,然后华丽丽的爆了内存。
这种做法的复杂度:
时间:O(p+q)
空间:O(p+q)
然而根据题目要求,空间限制2M,是很严格的。。以后一定要好好看题目。。
最新文章
- 【从零开始学BPM,Day3】自定义表单开发
- pqgrid对json数据的绑定
- Jackson转换对象为json的时候报java.lang.stackoverflowerror
- 线程安全集合 ConcurrentDictionary<;TKey, TValue>; 类
- [LeetCode] next_permutation
- mybatis sql注入安全
- citrix+netscaler配置第一次培训
- C++学习之文件的输入输出
- 原代码,反码,解释和具体的补充 Java在&;gt;&;gt;和&;gt;&;gt;&;gt;差异
- Qt出现常量有换行符的错误的解决方法
- 使用spark ml pipeline进行机器学习
- vue实现双向数据绑定的原理
- Linux系统中存储设备的两种表示方法
- const函数
- [十]SpringBoot 之 普通类获取Spring容器中的bean
- js使用锚点回到顶部
- 高性能mysql-锁的调试
- centos6.9NAT网络模式
- Echarts 简单报表系列一:柱状图
- iostart 命令
热门文章
- 在线OJ实用技巧(转载)
- Python3中使用PyMySQL连接Mysql
- 使用github的使用,利用git shell命令行模式进行操作
- php 文件日志类
- C#组合查询小Demo
- 阿里云服务器Linux CentOS安装配置(零)目录
- Thinking in Java——笔记(13)
- 掌握Thinkphp3.2.0----模型初步
- [转]推荐一个简单、轻量、功能非常强大的C#/ASP.NET定时任务执行管理器组件–FluentScheduler
- 【php】命名空间 和 自动加载的关系