A.Pokemon Master
portal
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template <typename T>
inline void rd(T& x)
{
ll tmp = 1; char c = getchar(); x = 0;
while (c > '9' || c < '0') { if (c == '-')tmp = -1; c = getchar(); }
while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
x *= tmp;
}
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
const int M = 1e7 + 10;
const double eps = 1e-8;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
//FILE* _INPUT = freopen("input.txt", "r", stdin);
//FILE* _OUTPUT = freopen("output.txt", "w", stdout);
int T; rd(T);
while (T--) {
int n, m; rd(n), rd(m);
ll suml=0,sumr=0;
for (int i = 1; i <= n; ++i) {
ll tmp; rd(tmp);
suml+=tmp;
}
for (int i = 1; i <= m; ++i) {
ll tmp; rd(tmp);
sumr+=tmp;
}
if (suml > sumr) puts("Calem");
else if (suml == sumr) puts("Draw");
else puts("Serena");
}
return 0;
}
B.Problem Arrangement
Portal
dp, here 12 problems will be binary compression, the bit of 0 means unresolved, 1 means resolved;
Enumeration with state compression properties
0
–
2
n
–
1
0-2^{n-1}
Since the number of points M is only 500, considering the violent enumeration number M, the equation of state is easy to derive, as detailed in the code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template <typename T>
inline void rd(T& x)
{
ll tmp = 1; char c = getchar(); x = 0;
while (c > '9' || c < '0') { if (c == '-')tmp = -1; c = getchar(); }
while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
x *= tmp;
}
const int inf = 0x3f3f3f3f;
const int mod = 7;
const int N = (1 << 13) + 10;
const int M = 1e7 + 10;
const double eps = 1e-8;
ll dp[N][510];
int a[13][13];
ll gcd(ll x, ll y) {
if (y == 0) return x;
return gcd(y, x % y);
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
// FILE* _INPUT = freopen("input.txt", "r", stdin);
// FILE* _OUTPUT = freopen("output.txt", "w", stdout);
int T; rd(T);
while (T--) {
memset(dp, 0, sizeof dp);
int n, m; rd(n), rd(m);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) rd(a[i][j]);
}
dp[0][0] = 1;
for (int i = 0; i < (1 << n); ++i) {
int cnt = 0;
for (int j = 0; j < n; ++j) {
if (i & (1 << j)) ++cnt;
}
for (int j = 0; j < n; ++j) {
if (i & (1 << j)) continue;
for (int k = 0; k <= m; ++k) {
int tmp = k + a[j][cnt];
if (tmp >= m) {
dp[i ^ (1 << j)][m] += dp[i][k];
}
else dp[i ^ (1 << j)][tmp] += dp[i][k];
}
}
}
if (dp[(1 << n) - 1][m] == 0) puts("No solution");
else {
ll ans = 1;
for (int i = 1; i <= n; ++i) ans = ans * i;
ll tmp = gcd(ans, dp[(1 << n) - 1][m]);
printf("%lld/%lld\n", ans/tmp, dp[(1 << n) - 1][m]/tmp);
}
}
return 0;
}
C.Talented Chef
portal
Needs to be done in the shortest time cooking, clearly need to split the time step by step, this is the average time required to take up the whole, but also consider a bit when a fish cooking time for a long time, even more than the average amount of time, this time will need to take a larger one, namely with single cooking time of the fish
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template <typename T>
inline void rd(T& x)
{
ll tmp = 1; char c = getchar(); x = 0;
while (c > '9' || c < '0') { if (c == '-')tmp = -1; c = getchar(); }
while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
x *= tmp;
}
const int inf = 0x3f3f3f3f;
const int mod = 7;
const int N = 1e5 + 10;
const int M = 1e7 + 10;
const double eps = 1e-8;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
// FILE* _INPUT = freopen("input.txt", "r", stdin);
// FILE* _OUTPUT = freopen("output.txt", "w", stdout);
int T; rd(T);
while (T--) {
int n, m; rd(n), rd(m);
ll sum = 0; ll maxn = 0;
for (int i = 1; i <= n; ++i) {
int tmp; rd(tmp);
sum += tmp;
maxn = max(maxn, 1LL*tmp);
}
ll ans = sum/m;
if (sum % m) ++ans;
printf("%lld\n", max(ans,maxn));
}
return 0;
}
E.Paint the Grid Again
portal
The meaning is to brush a wall to have a rule, horizontal can only brush black, longitudinal can brush white, so the problem is good to solve now only see each line, according to the rule should be a line of black, if appeared white, explain first transverse brush black, again longitudinal brush the white of that column, namely
R
[
i
]
–
>
C
[
j
]
.
set
the
point
sit
mark
for
(
i
.
j
)
R[i]-> C[j], let the coordinate of this point be (I,j)
R [I] – & gt; C[j], let the coordinate of this point be (I,j), also only look at each column, if black appears in a column, then that means
C
[
j
]
–
>
R
[
i
]
C[j]-> R[i]
C [j] – & gt; R[I] according to the above rules, build the edge, and then run through the topological order, but the answer needs to output the minimum dictionary order, first column
C
C
C dictionary sequence
<
R
< R
< R; The Numbers go from small to large, so when you build the edge, you build the edge as
j
∈
[
1
.
n
]
j\in[1,n]
J ∈[1,n], set the edge of the row as
i
∈
[
n
+
1
.
2
x
n
]
I \ [in the n * n + 1, 2]
I ∈ [n + 1, 2 * n] finally in the topological order will point in the priority queue, small in first out queue can figure no solution is the first sign all painted rows and columns, and then in the topology sequence of time for a new round of tags, when we have painted columns or rows did not appear in the topological order, there is no solution, similar to form a ring
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template <typename T>
inline void rd(T& x)
{
ll tmp = 1; char c = getchar(); x = 0;
while (c > '9' || c < '0') { if (c == '-')tmp = -1; c = getchar(); }
while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
x *= tmp;
}
const int inf = 0x3f3f3f3f;
const int mod = 7;
const int N = 1e3 + 10;
const int M = 1e7 + 10;
const double eps = 1e-8;
int head[N], cnt;
struct edge {
int next, to;
}e[M];
void add(int u, int v) {
e[cnt].next = head[u];
e[cnt].to = v;
head[u] = cnt++;
}
char mp[505][505];
int degree[N];
bool row[505], col[505], vis[N];
vector<int>ans;
bool check(int n) {
memset(vis, false, sizeof vis);
priority_queue<int,vector<int>,greater<int> >que;
for (int i = 1; i <= n; ++i) {
if (col[i] && !degree[i]) {
que.push(i);
}
}
for (int i = 1; i <= n; ++i) {
if (row[i] && !degree[i+n]) {
que.push(i+n);
}
}
if (que.empty()) return 0;
while (!que.empty()) {
int u = que.top(); que.pop();
vis[u] = true;
if (u > n) {
ans.push_back(u);
vis[u] = true;
}
else {
ans.push_back(u);
vis[u] = true;
}
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to;
if (!(--degree[v])) {
que.push(v);
}
}
}
for (int i = 1; i <= n; ++i) {
if (col[i]&&!vis[i]) return false;
}
for (int i = n + 1; i <= 2 * n; ++i) {
if (row[i - n] && !vis[i]) return false;
}
for (int i = 0; i < ans.size(); ++i) {
if (ans[i] > n) {
printf("R%d", ans[i] - n);
}
else printf("C%d", ans[i]);
printf("%s", i == ans.size() - 1 ?"\n" : " ");
}
return 1;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
//FILE* _INPUT = freopen("input.txt", "r", stdin);
//FILE* _OUTPUT = freopen("output.txt", "w", stdout);
int T; rd(T);
while (T--) {
int n; rd(n);
memset(head, -1, sizeof head); cnt = 0;
memset(row, false, sizeof row);
memset(col, false, sizeof col);
memset(degree, 0, sizeof degree);
ans.clear();
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
scanf(" %c", &mp[i][j]);
if (mp[i][j] == 'X') row[i] = true;
else if (mp[i][j] == 'O') col[j] = true;
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (row[i]&&mp[i][j] == 'O') {
add(i + n, j);
++degree[j];
}
}
}
for (int j = 1; j <= n; ++j) {
for (int i = 1; i <= n; ++i) {
if (col[j]&&mp[i][j] == 'X') {
add(j, i + n);
++degree[i + n];
}
}
}
if (!check(n)) puts("No solution");
}
return 0;
}
F.Paint the Grid Reloaded
Portal
A unicom block can form a unicom block where the upper, lower, left and right are connected in the same color. Then a unicom block nearby must be the unicom block with the opposite color. So if a unicom block reverses color, it must be connected with the nearby unicom block, and then reverse… Therefore, this problem first needs to indent the graph, then enumerate the starting point for BFS to determine the number of reversals, and find the minimum number of reversals
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template <typename T>
inline void rd(T& x)
{
ll tmp = 1; char c = getchar(); x = 0;
while (c > '9' || c < '0') { if (c == '-')tmp = -1; c = getchar(); }
while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
x *= tmp;
}
const int inf = 0x3f3f3f3f;
const int mod = 7;
const int N = 1e4 + 10;
const int M = 1e7 + 10;
const double eps = 1e-8;
int n, m;
char mp[55][55];
bool vis[55][55];
int num[55][55];
int dir[][2] = { 1,0,-1,0,0,1,0,-1 }, cnt;
void bfs(int x,int y) {
queue<pii>que;
que.push({ x,y });
stack<pii>stk;
while (!que.empty()) {
pii p = que.front(); que.pop();
stk.push(p);
if (vis[p.first][p.second]) continue;
vis[p.first][p.second] = 1;
for (int i = 0; i < 4; ++i) {
int xx = p.first + dir[i][0], yy = p.second + dir[i][1];
if (xx <= 0 || xx > n || yy <= 0 || yy > m || vis[xx][yy] || mp[xx][yy] != mp[p.first][p.second]) continue;
que.push({ xx,yy });
}
}
++cnt;
while (!stk.empty()) {
pii p = stk.top(); stk.pop();
num[p.first][p.second] = cnt;
}
}
int head[N], cntE;
struct edge {
int next, to;
}e[M];
void add(int u, int v) {
e[cntE].to = v;
e[cntE].next = head[u];
head[u] = cntE++;
}
bool mark[N];
int bfs(int x) {
queue<pii>que;
que.push({ x,1 });
int ans = 0;
while (!que.empty()) {
pii p = que.front(); que.pop();
int u = p.first;
if (mark[u]) continue;
mark[u] = true;
ans = max(ans, p.second);
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to;
if (mark[v]) continue;
que.push({ v,p.second + 1 });
}
}
return ans-1;
}
int solve() {
memset(vis, false, sizeof vis); cnt = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (vis[i][j]) continue;
bfs(i, j);
}
}
memset(head, -1, sizeof head); cntE = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
for (int k = 0; k < 4; ++k) {
int x = i + dir[k][0], y = j + dir[k][1];
if (x <= 0 || x > n || y <= 0 || y > m) continue;
if (num[x][y] != num[i][j]) add(num[i][j], num[x][y]);
}
}
}
int minn = inf;
for (int i = 1; i <= cnt; ++i) {
for (int j = 1; j <= cnt; ++j) mark[j] = false;
minn = min(minn, bfs(i));
}
return minn;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
// FILE* _INPUT = freopen("input.txt", "r", stdin);
// FILE* _OUTPUT = freopen("output.txt", "w", stdout);
int T; rd(T);
while (T--) {
rd(n), rd(m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf(" %c", &mp[i][j]);
}
}
printf("%d\n", solve());
}
return 0;
}
G.Ternary Calculation
Portal
, only three Numbers of operation, direct enumeration of the possibility of only 25
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template <typename T>
inline void rd(T& x)
{
ll tmp = 1; char c = getchar(); x = 0;
while (c > '9' || c < '0') { if (c == '-')tmp = -1; c = getchar(); }
while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
x *= tmp;
}
const int inf = 0x3f3f3f3f;
const int mod = 7;
const int N = 1e5 + 10;
const int M = 1e7 + 10;
const double eps = 1e-8;
char s[N];
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
// FILE* _INPUT = freopen("input.txt", "r", stdin);
// FILE* _OUTPUT = freopen("output.txt", "w", stdout);
int T; rd(T);
while (T--) {
int a[5]; char b[5];
scanf("%d %c %d %c %d", &a[1], &b[1], &a[2], &b[2], &a[3]);
if (b[1] == '-' && (b[2] == '-' || b[2] == '+')) {
if (b[2] == '+') printf("%d\n", a[1] - a[2] + a[3]);
else printf("%d\n", a[1] - a[2] - a[3]);
continue;
}
if (b[1] == '+'||b[1]=='-') {
int ans;
if (b[2] == '+') ans = a[2] + a[3];
else if (b[2] == '-') ans = a[2] - a[3];
else if (b[2] == '*') ans = a[2] * a[3];
else if (b[2] == '/') ans = a[2]/a[3];
else ans = a[2] % a[3];
if (b[1] == '+') printf("%d\n", a[1] + ans);
else printf("%d\n", a[1] - ans);
}
else {
int ans;
if (b[1] == '*') ans = a[1] * a[2];
else if (b[1] == '/') ans = a[1]/a[2];
else ans = a[1] % a[2];
if (b[2] == '+') ans = ans + a[3];
else if (b[2] == '-') ans = ans - a[3];
else if (b[2] == '*') ans = ans * a[3];
else if (b[2] == '/') ans = ans/a[3];
else ans = ans % a[3];
printf("%d\n", ans);
}
}
return 0;
}
J.What day is that day?
Portal
this problem can be tabulated to find the law, can also use the principle of modulus, found that it happens to be a geometric sequence of sums
L.Access System
Access System
save all the time in seconds and sort it
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template <typename T>
inline void rd(T& x)
{
ll tmp = 1; char c = getchar(); x = 0;
while (c > '9' || c < '0') { if (c == '-')tmp = -1; c = getchar(); }
while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
x *= tmp;
}
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
const int M = 1e7 + 10;
const double eps = 1e-8;
struct node {
int id, num;
bool friend operator<(const node& a, const node& b) {
if (a.num == b.num) return a.id < b.id;
return a.num < b.num;
}
}a[N];
vector<int>ans;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
//FILE* _INPUT = freopen("input.txt", "r", stdin);
//FILE* _OUTPUT = freopen("output.txt", "w", stdout);
int T; rd(T);
while (T--) {
int n, l; rd(n), rd(l);
ans.clear();
for (int i = 1; i <= n; ++i) {
int x, y, z;
scanf("%d:%d:%d", &x, &y, &z);
a[i].num = x * 3600 + y * 60 + z;
a[i].id = i;
}
sort(a + 1, a + 1 + n);
ans.push_back(a[1].id);
int now = a[1].num + l;
for (int i = 2; i <= n; ++i) {
if (a[i].num < now) continue;
ans.push_back(a[i].id);
now = a[i].num + l;
}
sort(ans.begin(), ans.end());
printf("%d\n%d", ans.size(),ans[0]);
for (int i = 1; i < ans.size();++i) {
printf(" %d", ans[i]);
}
puts("");
}
return 0;
}
1
. Stata highlights ||
