A - First ABC
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n;
string s;
cin >> n >> s;
set<char> cnt;
int t = 0;
for( auto i : s){
t ++;
cnt.insert(i);
if( cnt.size() == 3 ) break;
}
cout << t << "\n";
return 0;
}
B - Vacation Together
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n , d;
cin >> n >> d;
vector<int> vis(d);
for( string s ; n ; n -- ){
cin >> s;
for( int i = 0 ; i < d ; i ++ )
if( s[i] == 'x' ) vis[i] = 1;
}
int res = 0;
for( int i = 0 , cnt = 0 ; i < d ; i ++ ){
if( vis[i] ) cnt = 0;
else cnt ++;
res = max( res , cnt );
}
cout << res << "\n";
return 0;
}
C - Find it!
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> vis , t , res;
void dfs( int x ){
if( vis[x] == 1 ){
res.push_back(x);
vis[x] ++;
dfs( t[x] );
}else if( vis[x] == 2 ){
return ;
}else{
vis[x] ++ ;
dfs(t[x]);
}
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n;
cin >> n;
vis = vector<int>(n+1);
t = vector<int>(n+1);
for( int i = 1 ; i <= n ; i ++ )
cin >> t[i];
for( int i = 1 ; i <= n ; i ++ ){
if( vis[i] ) continue;
dfs(i);
if( res.empty() ) continue;
cout << res.size() << "\n";
for( auto i : res )
cout << i << " ";
cout << "\n";
return 0;
}
return 0;
}
D - Grid Ice Floor
暴力的 bfs,在 bfs 的过程中既记录当前的位置,同时记录移动方向
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
#define mp make_pair
#define mt make_tuple
int32_t main() {
// ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n, m;
cin >> n >> m;
vector<string> g(n);
vector<vector<int>> vis(n, vector<int>(m));
for (auto &i: g) cin >> i;
queue<tuple<int, int, int>> q;
for (int i = 0; i < 4; i++)
q.emplace(1, 1, i);
while (!q.empty()) {
auto [x, y, d] = q.front();
q.pop();
if (vis[x][y] & (1 << d)) continue;
vis[x][y] |= (1 << d);
int fx = x + dx[d], fy = y + dy[d];
if (fx >= 0 && fx < n && fy >= 0 && fy < m && g[fx][fy] == '.')
q.emplace(fx, fy, d);
else if (fx >= 0 && fx < n && fy >= 0 && fy < m && g[fx][fy] == '#') {
for (int i = 0; i < 4; i++)
if (i != d) q.emplace(x, y, i);
}
}
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
res += (vis[i][j] > 0) && (g[i][j] == '.');
}
}
cout << res << "\n";
return 0;
}
E - Defect-free Squares
二维前缀和,枚举点,然后二分最大边长即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n, m;
cin >> n >> m;
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n , m , q;
cin >> n >> m >> q;
vector<vector<int>> a( n+1 , vector<int>(m+1) );
for( int x , y ; q ; q -- )
cin >> x >> y , a[x][y] = 1;
for( int i = 1 ; i <= n ; i ++ )
for( int j = 1 ; j <= m ; j ++ )
a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];
int res = 0;
for( int i = 1 ; i <= n ; i ++ )
for( int j = 1 ; j <= m ; j ++ ){
int l = 1 , r = 3000 , mid , ans = -1;
while( l <= r ){
mid = ( l + r ) >> 1;
int x = i + mid - 1, y = j + mid-1 , cnt = 0;
if( x > n || y > m ) cnt = 1;
else cnt = a[x][y] - a[x][j-1] - a[i-1][y] + a[i-1][j-1];
if( cnt == 0 ) ans = mid , l = mid + 1;
else r = mid-1;
}
if( ans == -1 ) continue;
res += ans;
}
cout << res << "\n";
return 0;
}
F - Yet Another Grid Task
首先某一列的黑色一定是只能放最下面连续的一段。
根据题目的要求可知如果第\(i\)列放了\(x\)个,则\(i+1\)至少放\(x-1\)个。
首先求出每一列至少放\(a[i]\)个
\(f[i][j]\)表示第\(i\)列到第\(m\)列,且第\(i\)列放了\(j\)个黑色的方案数,则
\[f[i][j] = \sum_{k= j+1}^{n} f[i+1][k]
\]
求和的过程可以用前缀和优化一下,从右往左 dp 一下就好了。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n, m;
cin >> n >> m;
vector<string> g(n);
vector<int> a(m);
for (int i = 0; i < n; i++) cin >> g[i];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
if (g[i][j] == '#') {
a[j]++;
if (i + 1 < n) g[i + 1][j] = '#';
if (i + 1 < n && j + 1 < m) g[i + 1][j + 1] = '#';
}
}
vector<int> s(n+2); // s[j] 存储是 f[i+1][j] 的前缀和
s[n+1] = 1; // 因为 j 的取值是 [0,n] , 为了便于差分的计算映射到 [1,n+1] 上
vector<vector<int>> f(m, vector<int>(n + 1)); // f[i][j] 第 i 列放 j 个黑色的方案数
for (int i = m - 1; i >= 0; i--) {
for (int j = a[i]; j <= n; j++)
f[i][j] = ( s[n+1] - s[max(j-1,0ll)] + mod) % mod;
s[1] = f[i][0];
for (int j = 1; j <= n; j++)
s[j+1] = (s[j] + f[i][j]) % mod;
}
cout << s[n+1] << "\n";
return 0;
}
G - One More Grid Task
比较朴素的做法是枚举两个点确定矩形,然后通过各种预处理实现\(O(1)\)的求和和求最值,这样复杂度是\(O(N^4)\)
这里我们枚举两行,表示选取中间的部分,这样在通过\(O(n)\)的预处理可以把二维的压缩为一维,然后如果考虑枚举区间又是不行的,我们转变思路,枚举点计算每个点的最大贡献。
首先这个点如果要产生贡献,必须是区间内的最小值,这样我们找到\(l_i,r_i\)分别表示\(i\)左右两侧第一个\(i\)小的值的下标,这样我们区间取\([l_i+1,r_i-1]\)就是该点的最大贡献,求和的过程可以用前缀和来解决。
现在我们只剩下求\(l_i,r_i\),在序列上求两次第一个比他小的值是很经典的单调栈,可以\(O(n)\)的求出。
所以整体的复杂度就是\(O(N^3)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int N, M;
cin >> N >> M;
vector a(N + 1, vector<int>(M + 1));
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
cin >> a[i][j];
int res = 0;
for (int u = 1; u <= N; u++) {
vector<int> s(M + 1, 0ll), m(M + 1, LLONG_MAX);
for (int v = u; v <= N; v++) {
for (int i = 1; i <= M; i++)
s[i] += a[v][i], m[i] = min(m[i], a[v][i]);
vector<int> l(M + 1, 0), r(M + 1, M + 1), stk;
// l[i] , r[i] 表示左右两侧第一个比 i 小的数的下标
for (int i = 1; i <= M; i++) {
while (!stk.empty() && m[i] < m[stk.back()])
r[stk.back()] = i, stk.pop_back();
if (!stk.empty()) l[i] = stk.back();
stk.push_back(i);
}
vector<int> pre(M + 1);
for (int i = 1; i <= M; i++)
pre[i] = pre[i - 1] + s[i];
for (int i = 1; i <= M; i++)
res = max(res, m[i] * (pre[r[i] - 1] - pre[l[i]]));
}
}
cout << res << "\n";
return 0;
}
- Beginner AtCoder Contest 311beginner atcoder contest 311 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 310