Educational Codeforces Round 5
垫底咯，中间老师找我去聊了下新学期的机房借用和训练，但出去前就只有我没出E
目录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;
}