2020 ICPC Shanghai Site

B. Mine Sweeper II

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n, m;
char s1[N][N], s2[N][N], s3[N][N];
int solve(char sa[N][N], char sb[N][N]) 
{
    int cnt = n * m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cnt -= sa[i][j] == sb[i][j];
    return cnt;
}
int main() 
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%s", s1[i] + 1);
    for (int i = 1; i <= n; i++) scanf("%s", s2[i] + 1);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            s3[i][j] = (s1[i][j] == '.' ? 'X' : '.');
    if (solve(s1, s2) <= n * m / 2) 
    {
        for (int i = 1; i <= n; i++) puts(s1[i] + 1);
        return 0;
    }
    for (int i = 1; i <= n; i++) puts(s3[i] + 1);
    return 0;
}

G. Fibonacci

若想让x * y为偶,只需其中一个为偶数。观察斐波那契数列,发现每3个数中就会有一个数是偶数。定义 odd 记录有几组这样的数,even 记录余下数(奇数)。 从第一组往后各组中的奇数能匹配的偶数成等差数列,求和即为 odd * (odd + 1) / 2。 每组中两个奇数匹配的偶数数量是相同的 * 2,所以奇数向后能匹配的偶数就有 odd * (odd  + 1)。 同样偶数与其后的奇数匹配的情况就是 odd * even + (odd - 1) * 3 * odd / 2。    
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n; cin >> n;
    ll even = n % 3, odd = n / 3;
    ll ans = odd * (odd + 1) + odd * even + (odd - 1) * 3 * odd / 2;
    cout << ans;
    return 0;
}

 M. Gitignore

把不能忽略的文件路径记录一下,再从可以忽略的文件里遍历,遇到可以忽略的文件就删除,后面遇到相同路径的文件就不用操作了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<string, ll> q, vis;
string a[1001];
int main()
{
    int cass;
    for (cin >> cass; cass; cass--)
    {
        ll m, n;
        cin >> n >> m;
        vis.clear();
        q.clear();
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= m; i++)
        {
            string x, y;
            cin >> x;
            for (int j = 0; j < x.size(); j++)
            {
                y += x[j];
                if (x[j] == '/') vis[y] = 1;
            }
        }
        ll s = 0;
        for (int i = 1; i <= n; i++)
        {
            string x;
            int flag = 0;
            for (int j = 0; j < a[i].size(); j++)
            {
                x += a[i][j];
                if (a[i][j] == '/')
                {
                    if (q[x])
                    {
                        flag = 1;
                        break;
                    }
                    if (!vis[x])
                    {
                        flag = q[x] = 1;
                        s++;
                        break;
                    }
                }
            }
            s += !flag;
        }
        cout << s << "\n";
    }
    return 0;
}

 

上一篇:笔试强训之每日一题(九)


下一篇:CF1611A Make Even 题解