首页 > ACM题库 > HDU-杭电 > hdu 3754 Binary Operation[解题报告]C++
2015
04-10

hdu 3754 Binary Operation[解题报告]C++

Binary Operation

问题描述 :

Alignment of Code

输入:

The input begins with an integer T. The next T blocks each represents a case.
Alignment of Code

输出:

The input begins with an integer T. The next T blocks each represents a case.
Alignment of Code

样例输入:

1
0 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 0
2 3 4 5 6 7 8 9 0 1
3 4 5 6 7 8 9 0 1 2
4 5 6 7 8 9 0 1 2 3
5 6 7 8 9 0 1 2 3 4
6 7 8 9 0 1 2 3 4 5
7 8 9 0 1 2 3 4 5 6
8 9 0 1 2 3 4 5 6 7
9 0 1 2 3 4 5 6 7 8
0 10

样例输出:

15

#include <cstdio>

typedef unsigned long long ullong;

int eval(int f[], int x, ullong k){
bool vst[10];
for(int i = 0;i < 10; ++i) vst[i] = false;
vst[x] = true;
while(k--){
x = f[x];
if(vst[x]){
int len = 1;
for(int y = f[x];y != x;y = f[y]) ++len;
k %= len;
while(k--) x = f[x];
return x;
}
else vst[x] = true;
}
return x;
}

int g[10][10];

ullong min(ullong a, ullong b){
return a < b ? a : b;
}
int main(){
int TT;
scanf("%d", &TT);
for(int cas = 1; cas <= TT; ++cas){
for(int i = 0;i < 10; ++i){
for(int j = 0;j < 10; ++j){
scanf("%d", g[j] + i);
}
}
ullong a, b;
scanf("%I64u %I64u", &a, &b);
ullong ans = 0;
for(ullong t = 1;t <= b;t *= 10){
ullong u = a, v = b;
int d = u / t % 10;
ullong uu = min((u / t + 1) * t - 1, v);
int val = eval(g[d], d, uu - u);
for(++d, u = uu;d < 10 && u < v; ++d, u = uu){
uu = min(u + t, v);
val = eval(g[d], val, uu - u);
}
if((v - u) / t >= 10){
int f[10];
for(int d = 0;d < 10; ++d){
f[d] = d;
for(int j = 0;j < 10; ++j){
f[d] = eval(g[j], f[d], t);
}
}
val = eval(f, val, (v - u) / t / 10);
u += (v - u) / t / 10 * t * 10;
}
for(d = 0; u < v; ++d, u = uu){
uu = min(u + t, v);
val = eval(g[d], val, uu - u);
}
ans += val * t;
}
printf("%I64u\n", ans);
}
return 0;
}

 


  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  3. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。