Educational Codeforces Round 5

垫底咯，中间老师找我去聊了下新学期的机房借用和训练，但出去前就只有我没出E

Educational Codeforces Round 5

A Comparing Two Long Integers

模拟字符串比较

string del(string s)
{
    int n = s.size();
    for(int i = 0; i < n; i++)
    {
        if(s[i] != '0')
        {
            return s.substr(i, n - i);
        }
    }
    return "0";
}

void solve()
{       
    string s, t;   cin>>s>>t;
    s = del(s);
    t = del(t);
    // cout<<s<<" "<<t<<'\n';
    if(s.size() != t.size())
    {
        if(s.size() > t.size())
            cout<<">";
        else if(s.size() < t.size())
            cout<<"<";
        return;
    }
    else
    {
        int n = s.size();
        for(int i = 0; i < n; i++)
            if(s[i] < t[i])
            {
                cout<<"<";
                return;
            }
            else if(s[i] > t[i])
            {
                cout<<">";
                return;
            }
        cout<<"=";return;
    }
    return;
}

B Dinner with Emma

最大化行上最小列

const int N = 1e2 + 10;
 
int n, m, a[N][N];
 
void solve()
{       
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin>>a[i][j];
    int res = 0;
    for(int i = 1; i <= n; i++)
    {
        int mav = 1e9 + 10;
        for(int j = 1; j <= m; j++)
            mav = min(a[i][j], mav);
        res = max(mav, res);
    }
    cout<<res<<'\n';
    return;
}

C The Labyrinth

连通块

const int N = 1e3 + 10;

int n, m, cnt;
char g[N][N];
int id[N][N];
int f[N * N];
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

void bfs(int t1, int t2, int tid)
{
    int sum = 1;
    queue<pair<int, int>> q;    q.push({t1, t2});
    id[t1][t2] = tid;
    while(!q.empty())
    {
        auto t = q.front(); q.pop();
        int tx = t.first;
        int ty = t.second;
        // cout<<tx<<" "<<ty<<'\n';
        for(int i = 0; i < 4; i++)
        {
            int x = tx + dx[i];
            int y = ty + dy[i];
            if(x < 1 || x > n || y < 1 || y > m || g[x][y] != '.' || id[x][y] != 0)
                continue;
            id[x][y] = tid;
            sum++;
            q.push({x, y});
        }
    }
    f[tid] = sum;
    // cout<<tid<<"  "<<sum<<'\n';

}

void solve()
{       
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin>>g[i][j];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(g[i][j] == '.' && id[i][j] == 0)
                bfs(i, j, ++cnt);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(g[i][j] == '.') 
            {
                cout<<g[i][j];
                continue;
            }
            vector<int> tid;
            for(int k = 0; k < 4; k++)
            {
                int x = i + dx[k];
                int y = j + dy[k];
                tid.push_back({id[x][y]});
            }
            sort(tid.begin(), tid.end());
            tid.erase(unique(tid.begin(), tid.end()), tid.end());
            int s = 1;
            for(auto w : tid)
                s = s + f[w];
            cout<<s % 10;
        }
        cout<<'\n';
    }
    return;
}

D Longest k-Good Segment

求出最长满足条件的一段区间，满足的\(\texttt{不同数字个数} \leq k\)

二分其区间长度 \(len\)，二分细节就是在数组上从左到右依次判断大小为 \(len\) 的窗口，用个数组和变量记录每个数字出现的次数和不同数字的个数。

const int N = 1e6 + 10;

int n, k, a[N], tl, tr;
int mp[N];
bool check(int len)
{
    for(int i = 0; i <= N - 10; i++)
        mp[i] = 0;
    tl = tr = -1;
    int sz = 0;
    for(int i = 1; i <= len; i++)
    {
        if(mp[a[i]] == 0)   sz++;
        mp[a[i]]++;
    }

    if(sz <= k) 
    {
        tl = 1, tr = len;
        return true;
    }

    for(int i = len + 1; i <= n; i++)
    {
        mp[a[i - len]]--;
        if(mp[a[i - len]] == 0) sz--;
        if(mp[a[i]] == 0) sz++;
        mp[a[i]]++;
        if(sz <= k)
        {
            tl = i - len + 1, tr = i;
            return true;
        }

    }
    return false;
}
void solve()
{       
    cin>>n>>k;
    for(int i = 1; i <= n; i++)
    {
        cin>>a[i];
    }
    int l = 1, r = n;
    while(l < r)
    {
        int mid = (l + r + 1) >> 1;
        if(check(mid))  l = mid;
        else r = mid - 1;
    }
    if(check(l))
        cout<<tl<<" "<<tr<<'\n';
    return;
}

E - Sum of Remainders

和余数求和是同一道题

求\(n \bmod 1 + n \bmod 2 + n \bmod 3 + \dots + n \bmod m\)

\[n \bmod 1 + n \bmod 2 + n \bmod 3 + \dots + n \bmod m = \sum_{i = 1}^{m} n \bmod i \\ = \sum_{i = 1}^{m}(n - ⌊\dfrac{n}{i}⌋ \times i) \\ = n \times m - \sum_{i = 1}^{m}⌊\dfrac{n}{i}⌋ \times i \]

\(⌊\dfrac{n}{i}⌋\) 最多只有 \(\sqrt{n}\) 种，接下来上数论分块

typedef long long ll;

const int mod = 1e9 + 7;

ll n, k;
void solve()
{
    cin>>n>>k;
    swap(n, k);
    __int128 res = (__int128)n * k;
    for(__int128 l = 1; l <= n; l++)
    {
        __int128 d = k / l, r;
        if(d == 0)
            r = n;
        else    
            r = min((__int128)n, (__int128)k / d);
        __int128 m = r - l + 1;
        res -= d * (l + r) * m / 2;
        l = r;
    }
    ll t =  res % mod;
    cout<<t<<endl;
}