A - Potions
#include <bits/stdc++.h>
using namespace std;
#define int long long
int power(int x, int y, int p) {
x %= p;
int ans = 1;
while (y) {
if (y & 1) ans = ans * x % p;
y >>= 1, x = x * x % p;
}
return ans;
}
void solve() {
int a, m;
cin >> a >> m;
for (int i = 0; i < 50; i++) {
if (power(a, i, m) == i % m) cout << i << "," << i;
}
cout << "\n";
return;
}
int32_t main() {
ios::sync_with_stdio(0), cin.tie(0);
int n , h , t;
cin >> n >> h >> t;
for( int i = 1 , x ; i <= n ; i ++ ){
cin >> x;
if( x + h >= t ) cout << i , exit(0);
}
return 0;
}
B - MissingNo.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int power(int x, int y, int p) {
x %= p;
int ans = 1;
while (y) {
if (y & 1) ans = ans * x % p;
y >>= 1, x = x * x % p;
}
return ans;
}
void solve() {
int a, m;
cin >> a >> m;
for (int i = 0; i < 50; i++) {
if (power(a, i, m) == i % m) cout << i << "," << i;
}
cout << "\n";
return;
}
int32_t main() {
ios::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for( auto & i : a ) cin >> i;
sort( a.begin() , a.end() ) ;
for( int i = 1 ; i < n ; i ++ ){
if( a[i] != a[i-1] + 1 ) cout << a[i-1] +1 , exit(0);
}
return 0;
}
C - Remembering the Days
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, m, res = 0;
cin >> n >> m;
vector<vector<pair<int, int>>> e(n + 1);
vector<int> vis(n + 1);
for (int i = 1, x, y, z; i <= m; i++)
cin >> x >> y >> z, e[x].emplace_back(y, z), e[y].emplace_back(x, z);
auto dfs = [ &vis , e , &res ]( auto && self , int x , int d ) -> void{
vis[x] = 1 , res = max( res , d );
for( auto [y,w] : e[x] ){
if( vis[y] ) continue;
self( self , y , d + w );
}
vis[x] = 0;
};
for( int i = 1 ; i <= n ; i ++ )
dfs( dfs , i , 0 );
cout << res << "\n";
return 0;
}
D - President
注意到\(\sum Z \le 10^5\),这样我们就可以背包了。\(f[i][j]\)表示前\(i\)个区赢得\(j\)张选票的最小花费。
从第\(i\)个选区赢得\(Z_i\)张选票代价是\(w_i=\max( 0 , \left \lceil \frac{X_i+Y_i}{2} \right \rceil -X_i)\)
剩下的就是 01背包
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, sum = 0;
cin >> n;
vector<int> a(n + 1), b(n + 1), c(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i] >> b[i] >> c[i], sum += c[i];
vector<vector<int>> f(n + 1, vector<int>(sum + 1, 1e18));
f[0][0] = 0;
for (int i = 1, w; i <= n; i++) {
w = max(0ll, (a[i] + b[i] + 1) / 2 - a[i]);
for (int j = 0; j <= sum; j++){
f[i][j] = f[i-1][j];
if( j >= c[i] ) f[i][j] = min( f[i][j] , f[i-1][j-c[i]] + w);
}
}
int res = 1e18;
for( int i = (sum+1) / 2 ; i <= sum ; i ++ )
res = min( res , f[n][i] );
cout << res << "\n";
return 0;
}
E - Avoid Eye Contact
赛时想复杂了,直接暴力的标记不能到达的点即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const array<int, 4> dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
int32_t main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, m, sx, sy, ex, ey;
cin >> n >> m;
vector<vector<char>> e(n + 1, vector<char>(m + 1));
vector<vector<bool>> g(n + 1, vector<bool>(m + 1, false));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> e[i][j];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (e[i][j] == '#') g[i][j] = true;
else if (e[i][j] == 'S') sx = i, sy = j;
else if (e[i][j] == 'G') ex = i, ey = j;
else if (e[i][j] == '>') {
g[i][j] = true;
for (int nj = j + 1; nj <= m and e[i][nj] == '.'; nj++)
g[i][nj] = true;
} else if (e[i][j] == '<') {
g[i][j] = true;
for (int nj = j - 1; nj >= 1 and e[i][nj] == '.'; nj--)
g[i][nj] = true;
} else if (e[i][j] == '^') {
g[i][j] = true;
for (int ni = i - 1; ni >= 1 and e[ni][j] == '.'; ni--)
g[ni][j] = true;
} else if (e[i][j] == 'v') {
g[i][j] = true;
for (int ni = i + 1; ni <= n and e[ni][j] == '.'; ni++)
g[ni][j] = true;
}
}
}
vector<vector<int>> dis(n + 1, vector<int>(m + 1, INT_MAX));
dis[sx][sy] = 0;
queue<pair<int, int>> q;
q.emplace(sx, sy);
vector<vector<bool>> vis(n + 1, vector<bool>(m + 1));
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
if (vis[x][y]) continue;
vis[x][y] = true;
for (int i = 0, fx, fy; i < 4; i++) {
fx = x + dx[i], fy = y + dy[i];
if (fx < 1 or fy < 1 or fx > n or fy > n) continue;
if (vis[fx][fy] or g[fx][fy] or dis[fx][fy] <= dis[x][y] + 1) continue;
dis[fx][fy] = dis[x][y] + 1;
q.emplace(fx, fy);
}
}
if( dis[ex][ey] == INT_MAX ) cout << "-1\n";
else cout << dis[ex][ey] << "\n";
return 0;
}
- Beginner AtCoder Contest 317beginner atcoder contest 317 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 315