ABC330题解AtCoder Beginner Contest 330A – Counting Passes思路:
枚举一遍,当前数大于\(L\)使\(ans+1\)即可.
代码:
#include#define int long longusing namespace std;int n, l, ans;int x;signed main(){cin >> n >> l;for(int i=1; i> x;if(x >= l){ans ++;}}cout << ans;return 0;}B – Minimize Abs 1思路:
枚举一遍,当前数在\(L,R\)之间,结果就是它本身,小于\(L\)为\(L\),大于\(R\)为\(R\).
代码:
#include#define int long longusing namespace std;int n, l, r;int x;signed main(){cin >> n >> l >> r;for(int i=1; i> x;if(x <= l){cout << l <= r){cout << r << " ";continue;}cout << x << " ";}return 0;}C – Minimize Abs 2思路:
枚举\(i:0\sim\sqrt{d}\)为第一个数,以\(1\)为左边界,\(\sqrt{d-i^2}+1\)为右边界,判定条件为\(mid^{2}\)与\(d-i^2\)之间的大小关系,每次更新边界后\(ans=\min{ans, |d-i^2-mid^2|}\)为条件二分查找第二个数.
其中\(d-i^2\)为当前的\(i\)下剩余\(d\)的大小,\(mid\)为当前的第二个数\((mid > i)\)
特判:当\(mid^2=d-i^2\)时直接输出\(0\).
代码:
#include#include#define int long longusing namespace std;int abss(int x){return x > -x ? x : -x;}int d, ans = 1e18;int t, l, r, mid;signed main(){cin >> d;for(int i=0; i*i<d; i++){t = d - i*i;l = 1;r = sqrt(t) + 1;while(l > 1;if(mid * mid t){r = mid - 1;}else{cout << 0;return 0;}ans = min(ans, abss(t - mid * mid));}}cout << ans;return 0;}D – Counting Ls思路:
由于元组的无序性,仅顺序不同的元组会被视为同一个元组,所以我们只统计每个\(\text{o}\)能和后面的\(\text{o}\)组成合法元组的个数.
只统计第2、3点在第1点右方、下方的方案,忽略左方、上方的点
设:
\(row_i\)表示第\(i\)行\(\text{o}\)的个数
\(col_i\)表示第\(i\)列\(\text{o}\)的个数
\(b_{i,j}\)表示第\(i\)行中第\(j\)列后每个\(\text{o}\)所在列在第\(i\)行往下\(\text{o}\)的个数总和
\(c_{i,j}\)表示第\(i\)行中第\(j\)列后\(\text{o}\)的个数总和
则第\(i\)行第\(j\)列的\(\text{o}\)可组成的方案个数为:
当第二个点位于第\(j\)列上,第三个点位于第\(i\)行上时:
第二个点的方案数\(\times\)第三个点的方案数即
(col[j] - 1) * c[i][j+1]当第二个点位于\(i,j_2\),第三个点位于第\(j_2\)列上时:
每个第二个点所对应的第三个点的方案数总和即
b[i][j+1]
将它们加起来,最后输出即可
代码:
#include#define int long longusing namespace std;int n, ans;bool a[2010][2010];int row[2010], col[2010];int b[2010][2010]; //第i行第j列每列的o后缀和int c[2010][2010]; //第i行第j列的o后缀和signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n;char ch;for(int i=1; i<=n; i++){for(int j=1; j> ch;a[i][j] = (ch == 'o');row[i] += a[i][j];}}for(int j=1; j<=n; j++){for(int i=1; i<=n; i++){col[j] += a[i][j];}}for(int i=1; i=1; j--){b[i][j] = b[i][j+1];c[i][j] = c[i][j+1];if(a[i][j]){b[i][j] += col[j] - 1;c[i][j] += 1;}}}for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){if(a[i][j]){ans += (col[j] - 1) * c[i][j+1];ans += b[i][j+1];}}}cout << ans;return 0;}E – Mex and Update思路:
\(\large STL大法好\)
因为\(A\)数组最多有\(2\times10^5\)个数,所以输出的答案必定小于\(2\times10^5\)
所以\(Mex\)可以转化为:一个存储了\(1\sim2\times10^5\)所有数的数组,去掉\(A\)数组中的数,剩下数中的最小值
有序数组,无需插入,删除,\(\Theta(n\log{n})\),可以使用\(map\),先在\(map\)里存储\(1\sim2\times10^5\)所有数,再设\(cnt_i\)表示\(map\)去掉\(A\)之后剩下的每个数的数量(同样只需要存储\(1\sim2\times10^5\))
在输入时
cnt[y]--;,如果cnt[y] < 0,那么s.erase(y);cnt[a[x]]++;,如果cnt[a[x]] >= 0,那么s.insert(a[x]);a[x]=y;
再输出*s.begin()即可
代码:
#include#include#define int long longusing namespace std;const int N = 200010;int n, m;int cnt[N], a[N];set s;signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n >> m;for(int i=0; i<=n; i++){s.insert(i);}for(int i=1; i> a[i];if(a[i] > N-10){continue;}cnt[a[i]]--;s.erase(a[i]);}while (m--){int x, y;cin >> x >> y;if(y <= 2e5){cnt[y]--;if(cnt[y] < 0){s.erase(y);}}if(a[x] = 0) {s.insert(a[x]);}}a[x] = y;cout << *s.begin() << '\n';}return 0;}