Codeforces Round #383 总结

Veröffentlicht am   |  

第一次参加codeforeces的线上比赛，最后A了两道水题，事后发现B题因为没有使用long long 而溢出了（汗），所以实际上A了一题。最后排名3561，分数达到1409。

题解在这里http://codeforces.com/blog/entry/48871

这里讲一下前三题思路。

742A - Arpa’s hard exam and Mehrdad’s naive cheat

一道很直白的题，看完题之后写出暴力算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int ans = 1378;
    while(--n)
    {
        ans *= 1378;
        ans %= 10;
    }
    cout << ans%10 << endl;
    return 0;
}

然后喜闻乐见的TLE了。其实想一下，由于只取最后一位数字，而一共只有10个数字，所以必然会出现循环。观察了一下规律写出第二版

1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>
using namespace std;
int ans[4] = {8, 4, 2, 6};
int main()
{
    int n;
    cin >> n;
    cout << ans[(n-1)%4] << endl;
    return 0;
}

然而由于没有考虑边界条件(n=0)被Hack了。

补上边界条件后终于A了:

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
int ans[4] = {8, 4, 2, 6};
int main()
{
    int n;
    cin >> n;
    if (n == 0)
        cout << 1 << endl;
    else
        cout << ans[(n-1)%4] << endl;
    return 0;
}

742B - Arpa’s obvious problem and Mehrdad’s terrible solution

第二题二话不说用Hash:

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
#include <bits/stdc++.h>
using namespace std;
map<int, int> num;
int nums[100001];
int main()
{
    ios::sync_with_stdio(false);
    int n, x;
    cin >> n >> x;
    for (int i = 0;i < n;i++)
        cin >> nums[i];
    long long ans = 0;
    map<int, int>::iterator iter;
    for (int i = 0;i < n;i++)
    {
        if ((iter = num.find(nums[i] ^ x)) != num.end())
        {
            ans += num[nums[i] ^ x];
        }
        if ((iter = num.find(nums[i])) != num.end())
            num[nums[i]] += 1;
        else
            num[nums[i]] = 1;
    }
    cout << ans << endl;
    return 0;
}

ps:开始ans用的int，然后悲剧了。
但发现由于n的大小不超过$10^5$，所以可以开个数组，直接存：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 17;
int n, x, cnt[maxn];
long long ans;
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> x;
    for(int i = 0, a; i < n; i++){
	    cin >> a;
	    ans += cnt[a ^ x];
	    cnt[a]++;
    }
    cout << ans << '\n';
    return 0;
}

741A - Arpa’s loud Owf and Mehrdad’s evil plan

读完题后，以为是用Floyd cycle detection，花了40分钟写好后一直WA。等后面看了Editorial之后才发现是自己理解错了题意。我以为是要找到链中的最小环，结果是要找所有环的最小公倍数，这就很气。1000多分就没了。

后来看了题解后写了一个AC的版本：

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
#include <bits/stdc++.h>
using namespace std;
long long S[1000];
int G[101];
bool vis[101];
int ans;
bool inedge[101];
void dfs(int n)
{
    vis[n] = true;
    ans++;
    if (!vis[G[n]])
        dfs(G[n]);
}
int gcd(int a, int b)
{
    if (a < b)
       return gcd(b, a);
    if (b == 0)
        return a;
    return gcd(b, a%b);
}
int lcm(int k)
{
    int ret = S[0];
    for (int i = 1;i < k;i++)
    {
        ret = ret*S[i] / gcd(ret,S[i]);
    }
    return ret;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(false);
    int n;
    cin >> n;
    memset(vis, 0, sizeof(vis));
    memset(G, 0, sizeof(vis));
    for(int i = 0;i < n;i++)
    {
        int crush;
        cin >> crush;
        G[i+1] = crush;
        inedge[crush] = true;
    }
    bool flag = true;
    for (int i = 1;i <= n;i++)
    {
        if (!inedge[i])
        {
            flag = false;
            break;
        }
    }
    if (flag)
    {
        int k = 0;
        for (int i = 0;i < n;i++)
        {
            ans = 0;
            if (!vis[i+1])
            {
                dfs(i+1);
                if (ans%2 == 0)
                    ans /= 2;
                S[k++] = ans;
            }
        }
        cout << lcm(k) << endl;
    }
    else
    {
        cout << -1 << endl;
    }
    return 0;
}

DFS找环，没什么好说的。

总结

虽然达到了一开始设定的目标(1400)，但是结果并不那么让人满意。最后只A了两道水题。但是作为第一次，也许还算不错了。经过这次，暴露出几个问题。
首先就是手速太慢，前两道简单题就花了1个小时的时间，说明还是不够熟练，第二题用map的时候还要去查资料，蛋疼(为什么那么熟练啊）。
然后是对题目理解有偏差。第三题就是这样。直接导致一道很水的题没做出来。

下一个目标就是冲上1600，争取能把Div2都做完。

以后要开始怼论文了，接下来又是期末考试，刷题一刷刷一天的日子看来是一去不复返了，且做且珍惜。

PS：之前说只要CF上了1400就买个静电容键盘，那么问题来了，是买HHKB呢还是Realforce？