A - Order Something Else
#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 , p , q;
cin >> n >> p >> q;
int res = p;
for( int x ; n ; n -- ){
cin >> x , res = min( res , q + x );
}
cout << res << "\n";
return 0;
}
B - Strictly Superior
#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<int> p(n + 1);
vector<vector<int>> f(n + 1, vector<int>(m + 1));
for (int i = 1, c; i <= n; i++) {
cin >> p[i] >> c;
for (int x; c; c--)
cin >> x, f[i][x] = 1;
}
for( int i = 1 ; i <= n ; i ++ ){
for( int j = 1 ; j <= n ; j ++ ){
if( p[i] < p[j] ) continue;
int q = 1 , t = 0 ;
for( int l = 1 ; q && l <= m ; l ++ ){
if( f[j][l] > f[i][l] ) t ++;
else if( f[j][l] < f[i][l] ) q = 0;
}
if( q == 0 ) continue;
if( p[i] > p[j] || t > 0 ){
cout << "Yes\n";
return 0;
}
}
}
cout << "No\n";
return 0;
}
C - Reversible
只存字典序较小的
#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;
cin >> n;
set<string> cnt;
for (string s, t; n; n--) {
cin >> s, t = s;
reverse(s.begin(),s.end());
s = min( s , t );
cnt.insert(s);
}
cout << cnt.size() << "\n";
return 0;
}
D - Peaceful Teams
直接暴搜,注意在搜索的过程中要及时盼到不合法的情况
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, T, m, res;
vector<vector<int>> g;
vector<set<int>> s;
void dfs(int x) {
if (x > n) {
if( s.size() == T ) res ++;
return;
}
if( s.size() + n - x + 1 < T ) return;
if (s.size() < T) {
s.push_back(set<int>());
s.back().insert(x);
dfs(x + 1);
s.pop_back();
}
for (auto &i: s) {
int f = 1;
for (auto j: g[x])
if (i.count(j)) {
f = 0;
break;
}
if( f == 0 ) continue;
i.insert(x);
dfs( x + 1 );
i.erase(x);
}
return;
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> T >> m;
g = vector<vector<int>>(n + 1);
for (int x, y; m; m--) {
cin >> x >> y;
if (x < y) swap(x, y);
g[x].push_back(y);
}
dfs(1);
cout << res << "\n";
return 0;
}
E - NAND repeatedly
简单的做一个 dp 就好了。
#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 , res = 0 ;
string s;
cin >> n >> s;
vector<array<int,2>> f(n+1);
for( int i = 1 , x ; i <= n ; i ++ ){
x = s[i-1] - '0';
if( x == 1 ) {
f[i][1] = 1 + f[i-1][0];
f[i][0] = f[i-1][1];
}else{
f[i][1] = f[i-1][0] + f[i-1][1];
f[i][0] = 1;
}
res += f[i][1];
}
cout << res << '\n';
return 0;
}
F - Make 10 Again
状压 dp,\(f[i][s]\)表示前\(i\)个数选部分数可以构成集合的概率。
对于枚举除了的\(s\)以及当前骰子掷出的数字\(j\),有三种情况
s
表示当前不要1<<(j-1)
表示之前的都不要s<<j
表示之前的加上当前的
把上述三种情况与到一起就是当前的数字全部可以构成的集合,注意要与\((1<<10)-1\)与一下防止溢出。
最后枚举所有包含10的集合把概率求和即为答案
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
const int N = 1 << 10;
int power(int x, int y) {
int ans = 1;
while (y) {
if (y & 1) ans = ans * x % mod;
x = x * x % mod, y >>= 1;
}
return ans;
}
int inv(int x) {
return power(x, mod - 2);
}
int read() {
int x = 0, f = 1, ch = getchar();
while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
if (ch == '-') f = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x * f;
}
int32_t main() {
int n = read();
vector<int> f(N);
f[0] = 1;
for (int x, y, invs; n; n--) {
x = read(), y = min(10ll, x), invs = inv(x);
vector<int> g(N);
for (int s = 0; s < N; s++) {
for (int i = 1; i <= y; i++)
(g[(s | s << i | 1 << (i - 1)) & (N - 1)] += f[s] * invs % mod) %= mod;
(g[s] += f[s] * (x - y) % mod * invs % mod) %= mod;
}
swap(f, g);
}
int res = 0;
for (int i = (1 << 9); i < N; i++)
(res += f[i]) %= mod;
cout << res << "\n";
return 0;
}
- Beginner AtCoder Contest 310beginner atcoder contest 310 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