Educational Codeforces Round 80

比赛链接：

Educational Codeforces Round 80

A-Deadline

由 ​ ， ​得 ​.

所以我们只需要枚举​到 ​即可。

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="cpp" cid="n35" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> #include <bits/stdc++.h>
using namespace std;

define ll long long

const int maxn = 3e5+7;
ll p[maxn];
int main(){
ios_base::sync_with_stdio(0);
int t;
cin >> t;
while(t--){
int n, d;
cin >> n >> d;
int ma = sqrt(d) + 10, i;
for (i = 0; i < ma; i++){
if(i + (d+i)/(i+1) <= n)
break;
}
cout << (i < ma ? "YES" : "NO") << endl;
}
return 0;
}</pre>

B - Yet Another Meme Problem

由题：

​

​

​

​

答案是 ​

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="cpp" cid="n40" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> #include <bits/stdc++.h>
using namespace std;

define ll long long

const int maxn = 3e5+7;
ll p[maxn];
int main(){
ios_base::sync_with_stdio(0);
int t;
cin >> t;
while(t--){
ll a, b, cnt=0;
cin >> a >> b;
b++;
while(b){
cnt++;
b /= 10;
}
ll ans = a * (cnt - 1);
cout << ans << endl;
}
return 0;
}</pre>

C - Two Arrays

由题目知道 ：

这是一个非递减序列。

这题有个有趣的数学知识，用到了搁板法，意思就是从个数中取个有多少种取法。

还有++必须用逆元来做，否则会输出.

用其他语言应该可以直接求C。

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="cpp" cid="n45" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> #include <bits/stdc++.h>
using namespace std;

define ll long long

const int mod = 1e9 + 7;
const int maxn = 10005;
ll fac[maxn];
​
​
ll qpow(ll a, ll b){
ll res = 1;
while(b){
if(b&1){
res = (res * a) % mod;
}
a = (a * a) % mod;
b >>= 1;
}
return res;
}
ll C(ll m, ll n){
if(m>n || m <0)
return 0;
ll f1 = fac[n], f2 = fac[m] * fac[n - m] % mod;
return f1 * qpow(f2, mod - 2) % mod;
}
int main(){
ios_base::sync_with_stdio(0);
fac[0] = 1;
for (int i = 1; i < maxn; i++)
fac[i] = fac[i - 1] * i % mod;
ll n, m;
cin >> n >> m;
ll ans = C(n - 1, 2 * m + n - 1) % mod;
cout << ans << endl;
return 0;
}const int N = 1e3 + 7, M = 13;
int n, m;
modint f[M][N], ans;
​
int main() {
rd(n), rd(m);
f[0][1] = 1;
for (int i = 0; i < m; i++)
for (int j = 1; j <= n; j++)
for (int k = j; k <= n; k++)
f[i+1][k] += f[i][j];
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++)
ans += f[m][i] * f[m][n-j+1];
print(ans);
return 0;
}</pre>

D - Minimax Problem

二分。

题目的讲解卿学姐实在是良心。

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="cpp" cid="n50" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> #include <bits/stdc++.h>
using namespace std;

define ll long long

const int maxn = 3e5+7;
int n, m, ans_l, ans_r;
int num[1000];
int a[maxn][11];
​
bool judge(int mid){
memset(num, 0, sizeof(num));
for (int i = 0; i < n; i++){
int x = 0;
for (int j = 0; j < m; j++){
if(a[i][j] >= mid)
x += (1 << j);
}
num[x] = i + 1;
}
for (int i = 0; i < (1 << m); i++){
for (int j = 0; j < (1 << m); j++){
if(num[i] && num[j] && ((i|j) == ((1<<m)-1))){
ans_l = num[i];
ans_r = num[j];
return true;
}
}
}
return false;
}
​
​
int main(){
ios_base::sync_with_stdio(0);
​
cin >> n >> m;
int l = -1, r = 1e9;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> a[i][j];
l = min(l, a[i][j]);
r = max(r, a[i][j]);
}
}
​
int ans = l;
while(l<=r){
int mid = (l + r) >> 1;
if(judge(mid)){
ans = mid;
l = mid + 1;
}
else
r = mid - 1;
}
judge(ans);
cout << ans_l << " " << ans_r << endl;
return 0;
}</pre>

E - Messenger Simulator

树状数组。

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="cpp" cid="n55" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> #include <bits/stdc++.h>
using namespace std;

define ll long long

const int maxn = 1e6+7;
​
int bit[maxn], a[maxn], max_a[maxn], min_a[maxn];
int pos[maxn];
int n, m;
​
int lowbit(int x){
return x & (-x);
}
​
void update(int x, int op){
while(x < maxn){
bit[x] += op;
x += lowbit(x);
}
}
int get(int x){
int ans=0;
while(x){
ans += bit[x];
x -= lowbit(x);
}
return ans;
}
int main(){
ios_base::sync_with_stdio(0);
cin >> n >> m;
memset(bit, 0, sizeof(bit));
for (int i = 1; i<=n; i++){
max_a[i] = min_a[i] = i;
pos[i] = i + m;
update(i+m, 1);
}
for (int i = 0; i<m; i++){
int x;
cin >> x;
min_a[x] = 1;
max_a[x] = max(max_a[x], get(pos[x]));
​
update(pos[x], -1);
pos[x] = m - i;
update(pos[x], 1);
}
for (int i = 1; i<=n; i++){
max_a[i] = max(max_a[i], get(pos[i]));
}
for (int i = 1; i <= n; i++){
cout << min_a[i] << " " << max_a[i] << endl;
}
return 0;
}</pre>