EOJ-1860 Finger Counting

http://acm.cs.ecnu.edu.cn/problem.php?problemid=1860

题意:简单地说,对于一个1,2,3,4,5,4,3,2,1,2,……序列,限定某个数最多出现cnt次,求可得到序列元素个数的最大值

cnt为10^8级,不能直接模拟,故找到循环节1,2,3,4,5,4,3,2

有8个元素,1和5各出现一次,2,3,4各出现2次,观察序列可得到规律,即(cnt/出现次数)+a,a由该数的位置决定

可推广至n种数字的序列。对于1,2,3,4,……n-1,n,n-1,…,2,1,2,……

可知 循环节长度d=2n-2。循环节中,1与n各出现1次,其余各出现2次。限定某个数最多出现cnt次

则对于1与n,max=cnt*d+(n-1)

对于其他数x,max=cnt/2*d+a.

当cnt为奇数时,即是数到第二个x停止,a=d-(x-1); (包括x,还有x-1个数)

当cnt为偶数时,数到新循环的第一个x停止,a=x-1; (新的循环节中x前有x-1个数)

 1 #include<map>
 2 #include<set>
 3 #include<list>
 4 #include<cmath>
 5 #include<ctime>
 6 #include<queue>
 7 #include<stack>
 8 #include<cctype>
 9 #include<cstdio>
10 #include<string>
11 #include<cstdlib>
12 #include<cstring>
13 #include<iostream>
14 #include<algorithm>
15 using namespace std;
16 const int n=5;
17 const int d=8;
18 int main(){
19     int pos,cnt;
20     while(~scanf("%d%d",&pos,&cnt)){
21         if(pos==1 || pos==n)
22             printf("%d
",cnt*d+(pos-1));
23         else{
24             if(cnt%2) printf("%d
",cnt/2*d+d-(pos-1));
25             else printf("%d
",cnt/2*d+pos-1);
26         }
27     }
28     return 0;
29 }
View Code
原文地址:https://www.cnblogs.com/KimKyeYu/p/3147534.html