2017-08-12 14:00:00 - 2017-08-12 16:30:00
总共6道题，做了三道题1、5、6。但是最终还是全军覆没，bestcoder分从1460 -> 1181(-279)，贼伤心。bestcoder已经好久没运作了！！

1001小C的倍数问题

Accepts: 1990 Submissions: 4931
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

根据小学数学的知识，我们知道一个正整数x是3的倍数的条件是x每一位加起来的和是3的倍数。反之，如果一个数每一位加起来是3的倍数，则这个数肯定是3的倍数。

现在给定进制P，求有多少个B满足P进制下，一个正整数是B的倍数的充分必要条件是每一位加起来的和是B的倍数。

Input

第一行一个正整数T表示数据组数(1<=T<=20)。

接下来T行，每行一个正整数P(2 < P < 1e9)，表示一组询问。

Output

对于每组数据输出一行，每一行一个数表示答案。

Sample Input

1
10

Sample Output

3

分析

参考1：http://blog.csdn.net/sinat_35866463/article/details/77119380
参考2：http://blog.csdn.net/wyk1823376647/article/details/77123719

假设一个数a1a2a3满足 ： p 进制下的 a1a2a3 % B == 0,则以下俩个等式一定成立：
1）a1 p ^ 2 + a2 p ^ 1 + a3 * p ^ 0 = sum % B == 0,
2）a1 + a2 + a3 = ans % B == 0

以上两个式子同时成立的条件是 ： p % B == 1
所以满足条件的 B 的个数为 p - 1 的因子数

求余满足结合律：

20 % 3 = 2
(10 + 5 + 5) % 3 = 2
(1 + 2 + 2) % 3 = 2

42 % 5 = 2
(12 + 2 + 28) % 5 =  2
(2 + 2 + 3) % 5 = 2


(5 * 8) % 7 = 5
5 * 1 = 5

(8 * 11) % 3 = 1
(2 * 2) % 3 = 1

先理解一下为什么一个数各个数位上的和是3的倍数那这个数就是3倍数：
先看两位数字的,如数码ab组合 a+b为3的倍数
那么10a+b=9a+(a+b)
9a能被3整除,a+b能被3整除,所以10+b能被3整除
再看三位数字的,如数码abc组合 a+b+c为3的倍数
那么100a+10b+c=99a+9b+(a+b+c)
99a,9b,(a+b+c)都能被3整除,所以100a+10b+c能被3整除
实际上,对于任何一个自然数a(1)a(2)a(3)a(4)….a(n)
如果a(1)+a(2)+a(3)+…+a(n)为3的倍数
那么
a(1)10^(n-1)+a(2)10^(n-2)+….+a(n-1)10+a(n)
=a(1)[10^(n-1)-1]+a(2)[10^(n-2)-1]+…+a(n-1)*9+[a(1)+a(2)+…+a(n)]
中间的每一项.都能被3整除
所以：
一个数各个数位上的和是3的倍数那这个数就是3倍数

所以，这道题直接求q-1的因子数就好了
但是不能直接遍历，不然TLE,
优化方法:
每个数至少两个因子，一个1，一个自己本身，
所以直接定义ans=2，然后从2到sqrt(n)，遍历，
找到可以除尽的就把ans+=2；
考虑一点，如果n本身是完全平方数,就要把ans—;

理解

a1 p ^ 2 + a2 p ^ 1 + a3 p ^ 0 = sum % B == 0
==> a1(p^2 - 1) + a2 (p - 1) +(a1 + a2 + a3) = sum
==> 因为（a1 + a2 + a3)%B == 0,所以只要a1(p^2 - 1) + a2 * (p - 1)% B==0
==> 它们有共同的因数(p - 1),所以只要(p - 1) % B == 0即可
==> B就是(p - 1)的因子，B的个数就是(p - 1)的因子个数

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#define maxn 1000005
#define LL long long
using namespace std;

int main()
{
    int T;
    cin >> T;
    while(T--) {
        int P;
        cin >> P;
        int cnt = 0, tmp = sqrt(P - 1);
        for(int i = 1; i < tmp; i++) {
            if((P - 1) % i == 0) cnt += 2;
        }
        if(tmp * tmp == (P - 1)) cnt++;
        cout << cnt << endl;
    }
    //if(sqrt(6) * sqrt(6) == 6) cout << "6666666" << endl; //易错点
    return 0;
}

1005 今夕何夕

Accepts: 1345 Submissions: 5533
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

今天是2017年8月6日，农历闰六月十五。

小度独自凭栏，望着一轮圆月，发出了“今夕何夕，见此良人”的寂寞感慨。

为了排遣郁结，它决定思考一个数学问题：接下来最近的哪一年里的同一个日子，和今天的星期数一样？比如今天是8月6日，星期日。下一个也是星期日的8月6日发生在2023年。

小贴士：在公历中，能被4整除但不能被100整除，或能被400整除的年份即为闰年。

Input

第一行为T，表示输入数据组数。

每组数据包含一个日期，格式为YYYY-MM-DD。

1 ≤ T ≤ 10000

YYYY ≥ 2017

日期一定是个合法的日期

Output

对每组数据输出答案年份，题目保证答案不会超过四位数。

Sample Input

3
2017-08-06
2017-08-07
2018-01-01

Sample Output

2023
2023
2024

分析

郁闷，比赛时写的代码就忘记考虑了今天是2月29日的时候，下一次的年份必须是闰年，注意考虑2月份。

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdio>
#define maxn 10005
#define LL long long
using namespace std;

int main()
{
    int T;
    cin >> T;
    while(T--) {
        int Y,M,D;
        char ch;
        scanf("%d%c%d%c%d", &Y,&ch,&M,&ch,&D);
        bool flag = false;
        if((Y % 4 == 0 && Y % 100 != 0)||Y % 400 == 0) {
            if(M == 2 && D == 29) {
                flag = true;
            }
        }
        int tmp = 0;
        for(int i = Y + 1; i < Y + 10000; i++) {
            int year;
            if(M <= 2) {
                year = i - 1;
            }
            else {
                year = i;
            }
            int day = 365;
            if((year % 4 == 0 && year % 100 != 0)||year % 400 == 0) {
                day = 366;
            }
            tmp = (tmp + day) % 7;
            if(flag) {
                if((i % 4 == 0 && i % 100 != 0)||i % 400 == 0) {
                    if(tmp == 0) {
                        cout << i << endl;
                        break;
                    }
                }
                else continue;
            }
            if(tmp == 0) {
                cout << i << endl;
                break;
            }
        }
    }
    return 0;
}

1006 度度熊的01世界

Accepts: 967 Submissions: 3064
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

度度熊是一个喜欢计算机的孩子，在计算机的世界中，所有事物实际上都只由0和1组成。

现在给你一个n*m的图像，你需要分辨他究竟是0，还是1，或者两者均不是。

图像0的定义：存在1字符且1字符只能是由一个连通块组成，存在且仅存在一个由0字符组成的连通块完全被1所包围。

图像1的定义：存在1字符且1字符只能是由一个连通块组成，不存在任何0字符组成的连通块被1所完全包围。

连通的含义是，只要连续两个方块有公共边，就看做是连通。

完全包围的意思是，该连通块不与边界相接触。

Input

本题包含若干组测试数据。 每组测试数据包含： 第一行两个整数n,m表示图像的长与宽。 接下来n行m列将会是只有01组成的字符画。

满足1<=n,m<=100

Output

如果这个图是1的话，输出1；如果是0的话，输出0，都不是输出-1。

Sample Input

32 32
00000000000000000000000000000000
00000000000111111110000000000000
00000000001111111111100000000000
00000000001111111111110000000000
00000000011111111111111000000000
00000000011111100011111000000000
00000000111110000001111000000000
00000000111110000001111100000000
00000000111110000000111110000000
00000001111110000000111110000000
00000001111110000000011111000000
00000001111110000000001111000000
00000001111110000000001111100000
00000001111100000000001111000000
00000001111000000000001111000000
00000001111000000000001111000000
00000001111000000000000111000000
00000000111100000000000111000000
00000000111100000000000111000000
00000000111100000000000111000000
00000001111000000000011110000000
00000001111000000000011110000000
00000000111000000000011110000000
00000000111110000011111110000000
00000000111110001111111100000000
00000000111111111111111000000000
00000000011111111111111000000000
00000000111111111111100000000000
00000000011111111111000000000000
00000000001111111000000000000000
00000000001111100000000000000000
00000000000000000000000000000000
32 32
00000000000000000000000000000000
00000000000000001111110000000000
00000000000000001111111000000000
00000000000000011111111000000000
00000000000000111111111000000000
00000000000000011111111000000000
00000000000000011111111000000000
00000000000000111111110000000000
00000000000000111111100000000000
00000000000001111111100000000000
00000000000001111111110000000000
00000000000001111111110000000000
00000000000001111111100000000000
00000000000011111110000000000000
00000000011111111110000000000000
00000001111111111111000000000000
00000011111111111111000000000000
00000011111111111111000000000000
00000011111111111110000000000000
00000000001111111111000000000000
00000000000000111111000000000000
00000000000001111111000000000000
00000000000111111110000000000000
00000000000011111111000000000000
00000000000011111111000000000000
00000000000011111111100000000000
00000000000011111111100000000000
00000000000000111111110000000000
00000000000000001111111111000000
00000000000000001111111111000000
00000000000000000111111111000000
00000000000000000000000000000000
3 3
101
101
011

Sample Output

0
1
-1

别人的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

//错误的代码
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdio>
#define maxn 10005
#define LL long long
using namespace std;

int n, m;
char arr[105][105], brr[105][105], crr[105][105];
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};

void dfs(int x, int y) {
    arr[x][y] = '0';
    for(int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if(0 <= nx && nx < n && 0 <= ny && ny < m && arr[nx][ny] == '1') dfs(nx, ny);
    }
    return ;
}

void dfs0(int x, int y) {
    brr[x][y] = '1';
    for(int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if(0 <= nx && nx < n && 0 <= ny && ny < m && brr[nx][ny] == '0') dfs0(nx, ny);
    }
    return ;
}

int main()
{
    while(cin >> n >> m) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                cin >> arr[i][j];
                crr[i][j] = brr[i][j] = arr[i][j];
            }
        }
        int cnt = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(arr[i][j] == '1') {
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        if(cnt == 1) {
            int sum = 0;
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    if(brr[i][j] == '0') {
                        dfs0(i, j);
                        sum++;
                    }
                }
            }
            if(sum == 1) {
                cout << 1 << endl;
            }
            else if(sum == 2) {
                bool f = false;
                for(int i = 0; i < m && !f; i++){
                    if(crr[0][i] == 1) {
                        for(int j = 0; j < m; j++) {
                            if(crr[n-1][j] == 1) {
                                cout << 1 << endl;
                                f = true;
                                break;
                            }
                        }
                        break;
                    }
                }
                for(int i = 0; i < n && !f; i++){
                    if(crr[i][0] == 1) {
                        for(int j = 0; j < n; j++) {
                            if(crr[j][m-1] == 1) {
                                cout << 1 << endl;
                                f = true;
                                break;
                            }
                        }
                        break;
                    }
                }
                if(!f) {
                    cout << 0 << endl;
                }
            }
            else {
                cout << 0 << endl;
            }
        }
        else {
            cout << -1 << endl;
        }
    }
    return 0;
}