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
由題目知道 ：
這是一個(gè)非遞減序列氏堤。
這題有個(gè)有趣的數(shù)學(xué)知識械哟，用到了擱板法映凳，意思就是從個(gè)數(shù)中取個(gè)有多少種取法录别。
還有++必須用逆元來做耕渴，否則會輸出.
用其他語言應(yīng)該可以直接求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
二分。
題目的講解卿學(xué)姐實(shí)在是良心橱脸。
<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
樹狀數(shù)組础米。
<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>
