暑假第一场个人赛总结

发表于 | 分类于 | 阅读次数：

又是自闭的一下午，但是收获还是挺多的。下面总结一下。

比赛链接

A

看这道题，就算不会也能猜到奇偶的问题，但是我把输入的层数和里面的变量都用了n,然后就陷入了自闭。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 #include <iostream>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <set>
#include <string>
#include <stack>
using namespace std;

int main()
{
    int n,k;
    cin >> n;
    while(n--)
    {
        scanf("%d",&k);
        if(k % 2)cout << "Balanced" << '\n';
        else  cout << "Bad" << '\n';
    }

}

B

看题目中的2，3，5，7以及样例，直接发现类似做过的一道humble number题目，紫书也出现了(优先队列做的)，可以移步题目

类似的这道题已经很熟练了，速度的敲完，发现TLE。什么情况，我都预处理完了。。发现询问的次数可以达到500000，因此二分，因为预处理的数组是有序的。

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
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <set>
#include <string>
#include <stack>
using namespace std;

int a[5900];

void f()
{
    int aa ,bb,cc,dd ;
    aa = 0,bb = 0,cc = 0, dd = 0;
    a[0] = 1;
    for(int i = 1; i <= 5842; ++i)
    {
        a[i] = min(2 * a[aa], min(3 * a[bb], min(5 * a[cc], 7 * a[dd])));
        if(a[i] == 2 *a[aa])
            aa++;
        if(a[i] == 3 * a[bb])
            bb++;
        if(a[i] == 5 * a[cc])
            cc++;
        if(a[i] == 7* a[dd])
            dd++;
    }
}
int main()
{
    f();
    int n;
    scanf("%d",&n);
    int num;
    while(n--)
    {
    scanf("%d",&num);
    int m = lower_bound(a , a + 5500, num) - a;
    printf("%d\n",a[m]);
    }
}

C

也是自闭的一道题目，本身很简单。我想到N很大的时候，答案就确定了，可是为什么还是不对呢？？ 后来看到输入不超过1M，什么概念？？ 不清楚，看来输入上可能会出现超级大的一串数字了，所以输入改用string就过了

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
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <set>
#include <string>
#include <stack>
#include <math.h>
using namespace std;

int zhuanhuan(string s)
{
    int sum = 0;
    for(int i = 0; i < s.size(); ++i)
    {
        sum = sum * 10 + s[i] - '0';
    }
    return sum;
}
int main()
{
    string s;
    while(cin >> s)
    {
        if(s.size() >= 7){
            printf("1.64493\n");
            continue;
        }
    int n = zhuanhuan(s);
    double sum = 0;
    if(n >= 115000)
    {
        printf("1.64493\n");
        continue;
    }
    for(int i = 1 ; i<=n; ++i)
    {
        double num = double((1.0/i)*(1.0/i));
        sum += num;
    }
    printf("%.5lf\n",sum);
    }
}

G

数学题，按说应该不会也能猜出这个公式的，但是真的猜不出来啊QWQ。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <set>
#include <string>
#include <stack>
#include <math.h>
using namespace std;

int main()
{
    long long n,k;
    while(cin >> n >> k)
    {
        cout << (n - k + 1)*k << '\n';
    }

}

H

想到先求最长上升或者下降子序列的长度，但是却用到了单调栈，敲完才想到，单调栈的单调性是从第一个元素就开始确定的，可能我们都应该删除第一个元素，自闭了。还是老老实实用模板把。

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
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <set>
#include <string>
#include <stack>
#include <math.h>
using namespace std;

int dp[100005];
int s[100005];
int main()
{
    int t,n,k;;
    cin >> t;
    while(t--)
    {
        int len;
        scanf("%d %d",&n,&k);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d",&s[i]);
        }
        dp[1] = s[1];
        len = 1;
        for(int i = 2; i <= n; ++i)
        {
            if(s[i] > dp[len]){
                dp[++len] = s[i];
            }
            else{
                int m = lower_bound(dp +1,dp + len + 1,s[i])- dp;
                dp[m] = s[i];
            }
        }
        int len1 = len;
        for(int i = 1; i <= n/2; ++i)
        {
            swap(s[i],s[n-i+1]);
        }
        dp[1] = s[1];
        len = 1;
        for(int i = 2; i <= n; ++i)
        {
            if(s[i] > dp[len]){
                dp[++len] = s[i];
            }
            else{
                int m = lower_bound(dp + 1,dp + len + 1,s[i])- dp;
                dp[m] = s[i];
            }
        }
        int len2 = len;
        if(n - len1 <= k || n - len2 <= k)
            cout << "A is a magic array." << '\n';
        else
            cout << "A is not a magic array." << '\n';
    }
}

I

开始大意了，没想到要开始就要消耗的情况，我直接用总的消耗和总的收获做差，然后我还奇怪，这么简单么。后来想到开始的路程可能是消耗的大于收获的，把这个差值积累一下，记录一下最大值即可。

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
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <set>
#include <string>
#include <stack>
using namespace std;
int LL[105];
int RR[105];
int main()
{
    int t,caser = 1;
    int n,A,B,L;
    cin >> t;
    while(t--)
    {
        cin >> n >> A >> B >> L;  //失去A  得到B
        int sum = 0;
        int maxer = -1;
        for(int i = 1; i <= n; ++i)
        {
            cin >> LL[i] >> RR[i];
            int num = (RR[i] - LL[i])*A;   //num代表失去的
            int num1 = (LL[i] - RR[i - 1]) * B;
            sum += num - num1;
            maxer = max(maxer,sum);
        }
        cout << "Case #" << caser++ << ": ";
        if(maxer <= 0)  cout << '0' << '\n';
        else
            cout << maxer << '\n';
    }
}

K

水题，但是没发现，始终在纠结别的题目。

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
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <set>
#include <string>
#include <stack>
#include <math.h>
using namespace std;

int main()
{
    int n,caser = 1;
    cin >> n;
    while(n--)
    {
          string s;
        cin >> s;
        int i;
        for(i = 0; i < s.size(); ++i)
        {
            if(s[i] == '[')
                break;
        }
        cout << "Case #" << caser++ << ": ";
        string s2;
        char c = s[i + 1];
        if(c == 'B')
        {
            cout << "0.00";
        }
        if(c == 'M')
        {
            double num = (pow(10,6) * 1.0)/(pow(2,20)) * 100;
            double a = 100 - num;
            printf("%.2f",a);
        }
        if(c == 'K')
        {
            double num = (pow(10,3) * 1.0)/(pow(2,10)) * 100;
            double a = 100 - num;
            printf("%.2f",a);
        }
        if(c == 'G')
        {
            double num = (pow(10,9) * 1.0)/(pow(2,30)) * 100;
            double a = 100 - num;
            printf("%.2f",a);
        }
        if(c == 'T')
        {
            double num = (pow(10,12) * 1.0)/(pow(2,40)) * 100;
            double a = 100 - num;
            printf("%.2f",a);
        }
        if(c == 'P')
        {
            double num = (pow(10,15) * 1.0)/(pow(2,50)) * 100;
            double a = 100 - num;
            printf("%.2f",a);
        }
        if(c == 'E')
        {
             double num = (pow(10,18) * 1.0)/(pow(2,60)) * 100;
            double a = 100 - num;
            printf("%.2f",a);
        }
        if(c == 'Z')
        {
             double num = (pow(10,21) * 1.0)/(pow(2,70)) * 100;
            double a = 100 - num;
            printf("%.2f",a);
        }
        if(c == 'Y')
        {
            double num = (pow(10,24) * 1.0)/(pow(2,80)) * 100;
            double a = 100 - num;
            printf("%.2f",a);
        }
        cout << "%" << '\n';
    }
}

L

模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <set>
#include <string>
#include <stack>
using namespace std;

int main()
{
    string s;
    int cnt = 0;
    while(cin >> s)
    {
        if(s.size() <= 3)continue;
        for(int i = 0; i < s.size(); ++i)
        {
            if(i + 3 > s.size() - 1)break;
            if((s[i] == 'D' || s[i] == 'd') && (s[i + 1] == 'O' || s[i+1] == 'o') && (s[i + 2] == 'G'|| s[i+2] == 'g' )&&(s[i +3] == 'E' || s[i + 3] == 'e'))                cnt++;
        }
    }
    cout << cnt << '\n';
}