找规律 – hahaschool

UVa 11384 Help is needed for Dexter

December 06, 20152015-12-06hahaschoolLeave a comment

题意

请参考LRJ白书第一章例题10

思路

试验小数据，找规律。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

int main(){
    long long a;
    while(scanf(" %lld",&a) != EOF){
        int res = 0;
        long long fac = 1;
        while(fac <= a){
            fac *= 2;
            res++;
        }
        printf("%d\n",res);
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

int main(){

long long a;

while(scanf(" %lld",&a) != EOF){

int res = 0;

long long fac = 1;

while(fac <= a){

fac *= 2;

res++;

}

printf("%d\n",res);

}

return 0;

}

POJ 1019 Number Sequence

April 07, 20152015-04-07hahaschoolLeave a comment

题意

11212312341234512345612345671234567812345678912345678910123456789101112345678910…
让你求这么一个丧心病狂的数列第i位是啥。

思路

找规律，我们可以把数列切割为1/12/123/1234/…这样我们可以想办法求出每一段的控制范围，然后对于给出的i，先快速确定这个i会落在哪一个数的控制范围里面，是第几个，然后再想办法快速确定在这个控制范围内i到底对应了哪个数，我写的比较恶心（很长），其实在纸上试着写一些应该是能发现具体的规律和算法的。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

long long dp[100000];

int main(){
    for (int i = 1; i<= 100000; i++) {
        long long tmp = 0;
        long long base = 0;
        while (i-base > 0) {
            tmp += i-base;
            base = base*10 + 9;
        }
        dp[i] = dp[i-1] + tmp;
    }

    int caseCnt = 0;
    cin >> caseCnt;
    while (caseCnt--) {
        long long n = 0;
        cin >> n;
        long long pos = lower_bound(dp+1, dp+100000, n) - dp;
        pos--;
        n -= dp[pos];

        long long judge = 10;
        long long fact = 1;
        while (n / fact >= judge) {
            fact++;
            n += judge - 1;
            judge *= 10;
        }
        char num[1000];
        memset(num, 0, sizeof(num));
        sprintf(num, "%lld%lld",(n/fact)%10,(n/fact+1));
        cout << num[n%fact] << endl;
    }
    return 0;

}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

using namespace std;

long long dp[100000];

int main(){

for (int i = 1; i<= 100000; i++) {

long long tmp = 0;

long long base = 0;

while (i-base > 0) {

tmp += i-base;

base = base*10 + 9;

}

dp[i] = dp[i-1] + tmp;

}

int caseCnt = 0;

cin >> caseCnt;

while (caseCnt--) {

long long n = 0;

cin >> n;

long long pos = lower_bound(dp+1, dp+100000, n) - dp;

pos--;

n -= dp[pos];

long long judge = 10;

long long fact = 1;

while (n / fact >= judge) {

fact++;

n += judge - 1;

judge *= 10;

}

char num[1000];

memset(num, 0, sizeof(num));

sprintf(num, "%lld%lld",(n/fact)%10,(n/fact+1));

cout << num[n%fact] << endl;

}

return 0;

}

SGU 126 Boxes

April 07, 20152015-04-07hahaschoolLeave a comment

题意

http://www.nocow.cn/index.php/Translate:Sgu/126，翻译版。

思路

我是手写一些找规律，所以我也没办法细讲。

http://www.nocow.cn/index.php/Sgu/126详细题解，说是一个数论题，因为我是找规律所以代码肯定是写不严的，如果你需要严格证明请移步那边。

代码

#include <iostream>
#include <cstdlib>
#include <algorithm>

using namespace std;

int main(){
    long long a = 0,b = 0,sum = 0;
    cin >> a >> b;
    sum = a+b;
    if(a == 0 || b == 0){
        cout << 0 << endl;
    }
    if(sum%2){
        cout << -1 << endl;
        return 0;
    }
    int res = 0;
    long long now = min(a,b);
    while(now != sum/2){
        if(res > 10000){
            cout << -1 << endl;
            return 0;
        }
        res++;
        now *= 2;
        now = min(now,sum-now);
    }
    cout << res+1 << endl;
    return 0;
}

#include <iostream>

#include <cstdlib>

#include <algorithm>

using namespace std;

int main(){

long long a = 0,b = 0,sum = 0;

cin >> a >> b;

sum = a+b;

if(a == 0 || b == 0){

cout << 0 << endl;

}

if(sum%2){

cout << -1 << endl;

return 0;

}

int res = 0;

long long now = min(a,b);

while(now != sum/2){

if(res > 10000){

cout << -1 << endl;

return 0;

}

res++;

now *= 2;

now = min(now,sum-now);

}

cout << res+1 << endl;

return 0;

}

SGU 105 Div3

January 20, 20152015-01-20hahaschoolLeave a comment

#include <iostream>

using namespace std;

int main(){
    unsigned int toQuery;
    while (cin >> toQuery) {
        int tmp = 0;
        if (toQuery % 3 == 2) tmp++;
        cout << 2*(toQuery/3)+tmp << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main(){

unsigned int toQuery;

while (cin >> toQuery) {

int tmp = 0;

if (toQuery % 3 == 2) tmp++;

cout << 2*(toQuery/3)+tmp << endl;

}

return 0;

}

如果每一位加合等于3的话，这个数也可以被3整除。

然后打个表找下循环节发现是XOOXOOXOO这样的，直接简单判定一下实现就好了。