CC BY 4.0 (除特别声明或转载文章外)
如果这篇博客帮助到你,可以请我喝一杯咖啡~
Sim Card
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> v{{30, 40}, {35, 30}, {40, 20}};
int main()
{
for (int c, d; ~scanf("%d%d", &c, &d) && (c || d);)
{
int ans = 1e9;
for (auto p : v)
ans = min(ans, c * p.first + d * p.second);
printf("%d\n", ans);
}
}
Bank Card Verifier
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
int main()
{
for (char s[31]; ~scanf("%s%s%s%s", s, s + 4, s + 8, s + 12) && strcmp(s, "0000000000000000");)
{
int sum = 0;
for (int i = 0; s[i]; ++i)
{
int t = s[i] - '0';
if (i % 2 == 0)
t <<= 1;
if (t > 9)
t -= 9;
sum += t;
}
printf(sum % 10 ? "No\n" : "Yes\n");
}
}
World Cup Draw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
using namespace std;
unordered_map<string, pair<int, string>> mp{
{"Russia", {65, "UEFA"}},
{"Spain", {8, "UEFA"}},
{"Denmark", {19, "UEFA"}},
{"Serbia", {38, "UEFA"}},
{"Germany", {1, "UEFA"}},
{"Peru", {10, "CONMEBOL"}},
{"Iceland", {21, "UEFA"}},
{"Nigeria", {41, "CAF"}},
{"Brazil", {2, "CONMEBOL"}},
{"Switzerland", {11, "UEFA"}},
{"CostaRica", {22, "CONCACAF"}},
{"Australia", {43, "AFC"}},
{"Portugal", {3, "UEFA"}},
{"England", {12, "UEFA"}},
{"Sweden", {25, "UEFA"}},
{"Japan", {44, "AFC"}},
{"Argentina", {4, "CONMEBOL"}},
{"Colombia", {13, "CONMEBOL"}},
{"Tunisia", {28, "CAF"}},
{"Morocco", {48, "CAF"}},
{"Belgium", {5, "UEFA"}},
{"Mexico", {16, "CONCACAF"}},
{"Egypt", {30, "CAF"}},
{"Panama", {49, "CONCACAF"}},
{"Poland", {6, "UEFA"}},
{"Uruguay", {17, "CONMEBOL"}},
{"Senegal", {32, "CAF"}},
{"SouthKorea", {62, "AFC"}},
{"France", {7, "UEFA"}},
{"Croatia", {18, "UEFA"}},
{"Iran", {34, "AFC"}},
{"SaudiArabia", {63, "AFC"}}};
void split(const string &s, char c, vector<string> &v)
{
istringstream sin(s);
for (string s; getline(sin, s, c);)
{
for (int n; n = s.find(' '), n != s.npos;)
s.erase(n, 1);
if (!s.empty())
v.push_back(s);
}
}
bool dfs(int x, int y, const vector<vector<string>> &s, vector<vector<string>> &t)
{
if (y >= s[0].size())
return dfs(x + 1, 0, s, t);
if (x >= s.size())
{
vector<pair<int, char>> ans(s[0].size());
for (int i = 0; i < ans.size(); ++i)
{
for (int j = 0; j < t.size(); ++j)
ans[i].first += mp[t[j][i]].first;
ans[i].second = i + 'A';
}
sort(ans.begin(), ans.end());
for (auto p : ans)
cout << p.second << ' ' << p.first << '\n';
return 1;
}
for (int i = 0; i < t[x].size(); ++i)
if (t[x][i].empty())
{
int cnt = mp[s[x][y]].second != "UEFA";
for (int j = 0; j < x; ++j)
if (mp[t[j][i]].second == mp[s[x][y]].second)
++cnt;
if (cnt < 2)
{
t[x][i] = s[x][y];
if (dfs(x, y + 1, s, t))
return 1;
t[x][i].clear();
}
}
return 0;
}
int main()
{
for (string s; getline(cin, s), s != "End";)
{
vector<vector<string>> v(4), vv(4, vector<string>(8));
split(s, ',', v[0]);
for (int i = 1; i < v.size(); ++i)
getline(cin, s), split(s, ',', v[i]);
dfs(0, 0, v, vv);
}
}
Barareh on Fire
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <bits/stdc++.h>
using namespace std;
const int N=1e2+10;
int n, m, k;
char a[N][N];
int dx[]= {-1, 1, 0, 0,-1,-1, 1, 1};
int dy[]= { 0, 0,-1, 1, 1,-1,-1, 1};
int first, Extended, ans;
struct Node {
int x, y, w;
};
queue<Node> Q, F;
int people() {
int up;
if (first==1) {
up=k-1;
first=0;
Extended=1;
}
else {
up=k;
}
for(int i=1; i<=up; i++) {
int sz=Q.size();
if (!sz) break;
for(int i=1; i<=sz; i++) {
Node u=Q.front();Q.pop();
for(int i=0; i<4; i++) {
int Nx=u.x+dx[i];
int Ny=u.y+dy[i];
int Nw=u.w+1;
if (Nx<1||Nx>n||Ny<1||Ny>m) continue;
if (a[Nx][Ny]=='t') return Nw;
if (a[Nx][Ny]!='-') continue;
a[Nx][Ny]='#';
Q.push(Node{Nx, Ny, Nw});
Extended=1;
}
}
}
return 0;
}
void fire() {
int sz=F.size();
if (!sz) return;
for(int i=1; i<=sz; i++) {
Node u=F.front();F.pop();
for(int i=0; i<8; i++) {
int Nx=u.x+dx[i];
int Ny=u.y+dy[i];
int Nw=u.w+1;
if (Nx<1||Nx>n||Ny<1||Ny>m) continue;
if (a[Nx][Ny]=='f') continue;
a[Nx][Ny]='f';
F.push(Node{Nx, Ny, Nw});
Extended=1;
}
}
}
int main() {
//freopen("e.in", "r", stdin);
while(scanf("%d %d %d", &n, &m, &k)) {
if (!n&&!m&&!k) break;
while(!Q.empty()) Q.pop();
while(!F.empty()) F.pop();
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
cin>>a[i][j];
if (a[i][j]=='s') {
Q.push(Node {i, j, 0});
}
if (a[i][j]=='f') {
F.push(Node {i, j, 0});
}
}
}
first=1;
Extended=1;
while(Extended) {
Extended=0;
ans=people();
// cout<<"ans="<<ans<<endl;
if (ans) break;
fire();
}
// for(int i=1; i<=n; i++) {
// for(int j=1; j<=m; j++) {
// cout<<a[i][j];
// }
// cout<<endl;
// }
if (ans) cout<<ans<<endl;
else cout<<"Impossible"<<endl;
}
return 0;
}
Column Addition
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n;
char A[N], B[N], C[N];
int a[N], b[N], c[N];
int dp[N][2];
int main()
{
// freopen("h.in", "r", stdin);
while (scanf("%d", &n))
{
if (!n)
break;
scanf("%s", A + 1);
scanf("%s", B + 1);
scanf("%s", C + 1);
for (int i = 1; i <= n; i++)
{
a[i] = A[i] - '0';
b[i] = B[i] - '0';
c[i] = C[i] - '0';
}
memset(dp, 0x3f, sizeof(dp));
dp[n + 1][0] = 0;
for (int i = n; i >= 1; i--)
{
dp[i][1] = min(dp[i][1], dp[i + 1][1] + 1);
dp[i][0] = min(dp[i][0], dp[i + 1][0] + 1);
if (a[i] + b[i] == c[i] + 10)
{
dp[i][1] = min(dp[i][1], dp[i + 1][0]);
}
else if (a[i] + b[i] + 1 == c[i] + 10)
{
dp[i][1] = min(dp[i][1], dp[i + 1][1]);
}
else if (a[i] + b[i] == c[i])
{
dp[i][0] = min(dp[i][0], dp[i + 1][0]);
}
else if (a[i] + b[i] + 1 == c[i])
{
dp[i][0] = min(dp[i][0], dp[i + 1][1]);
}
}
cout << dp[1][0] << endl;
}
return 0;
}
Cafe Bazaar
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
#define L first
#define R second
using namespace std;
typedef long long ll;
ll trans(ll a[])
{
ll r = 0;
for (ll i = 0; i < 5; ++i)
r = r * 256 + a[i];
return r;
}
int main()
{
for (ll n; ~scanf("%lld", &n) && n;)
{
vector<pair<ll, ll>> v;
for (ll a[5], t, m; n--;)
{
char c;
scanf("%lld.%lld.%lld.%lld.%lld%c", &a[0], &a[1], &a[2], &a[3], &a[4], &c);
t = trans(a);
if (c == '-')
{
scanf("%lld.%lld.%lld.%lld.%lld", &a[0], &a[1], &a[2], &a[3], &a[4]);
v.push_back({t, trans(a)});
}
else
{
scanf("%lld", &m);
v.push_back({t, t + (1LL << 40 - m) - 1});
}
}
sort(v.begin(), v.end());
vector<pair<ll, ll>> vp(1, v[0]);
for (auto p : v)
{
if (p.L > vp.back().R + 1)
vp.push_back(p);
else
vp.back().R = max(vp.back().R, p.R);
}
v.clear();
for (auto p : vp)
while (p.L <= p.R)
for (ll i = 40; ~i; --i)
if (p.L >> i << i == p.L && p.L + (1LL << i) - 1 <= p.R)
{
v.push_back({p.L >> i << i, 40 - i});
p.L += 1LL << i;
break;
}
printf("%d\n", v.size());
for (ll i = 0, a[5]; i < v.size(); ++i)
{
for (ll j = 0; j < 5; ++j)
a[j] = v[i].L % 256, v[i].L /= 256;
for (ll j = 4; ~j; --j)
printf("%lld%c", a[j], j ? '.' : '/');
printf("%lld\n", v[i].R);
}
}
}
Mars
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 7, M1 = 1e7 + 3, M2 = 998244353;
int tot, ans;
bool p[N];
char s[N];
ll b[N], c[N], an[N], f[N], g[N];
ll h[M1 + 7], to[M1 + 7];
struct Node
{
int x, y, z, f;
bool operator<(const Node &b) const
{
return z != b.z ? z < b.z : y < b.y;
}
} a[N];
void ins(ll x, ll y)
{
ll t = x;
while (h[t] != -1 && h[t] != y)
t = (t + 1) % M1;
if (h[t] == -1)
{
to[++tot] = t;
h[t] = y;
}
}
bool check(ll x, ll y)
{
ll t = x;
while (h[t] != -1 && h[t] != y)
t = (t + 1) % M1;
if (h[t] == -1)
return 1;
else
return 0;
}
void dfs(int x, int n, ll t1, ll t2, int y, int z)
{
if (ans)
return;
if (check(t1, t2))
{
ans = y;
return;
}
if (x > y)
return;
for (int i = z; i <= n; i++)
{
if (p[i])
continue;
ll tt1 = (t1 - c[i] * 1LL * f[n - i] % M1 + M1) % M1, tt2 = (t2 - c[i] * 1LL * g[n - i] % M2 + M2) % M2;
p[i] = 1;
c[i] ^= 1;
tt1 = (tt1 + c[i] * 1LL * f[n - i] % M1) % M1;
tt2 = (tt2 + c[i] * 1LL * g[n - i] % M2) % M2;
dfs(x + 1, n, tt1, tt2, y, i + 1);
p[i] = 0;
c[i] ^= 1;
}
}
void bfs(int n)
{
ll t1 = 0, t2 = 0;
ans = 0;
for (int i = 1; i <= n; i++)
t1 = (t1 * 1LL * 2 % M1 + c[i]) % M1, t2 = (t2 * 1LL * 2 % M2 + c[i]) % M2;
for (int i = 1; i <= n; i++)
{
dfs(1, n, t1, t2, i, 1);
if (ans)
break;
}
}
int main()
{
f[0] = g[0] = 1;
for (int i = 1; i <= 100000; i++)
f[i] = f[i - 1] * 1LL * 2 % M1, g[i] = g[i - 1] * 1LL * 2 % M2;
for (int i = 0; i < M1; i++)
h[i] = -1;
for (int n, m; ~scanf("%d%d%s", &n, &m, s + 1) && (n || m);)
{
for (int i = 1; i <= n; i++)
b[i] = s[i] - '0';
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &a[i].x, &a[i].y);
a[i].z = a[i].y - a[i].x + 1;
a[i].f = i;
}
sort(a + 1, a + 1 + m);
for (int i = 1; i <= m;)
{
int j = 1;
while (a[i].z == a[i + j].z)
j++;
ll t = a[i].z, t1 = 0, t2 = 0;
for (int k = 1; k <= t; k++)
t1 = (t1 * 1LL * 2 % M1 + b[k]) % M1, t2 = (t2 * 1LL * 2 % M2 + b[k]) % M2;
tot = 0;
ins(t1, t2);
for (int k = t + 1; k <= n; k++)
{
t1 = ((t1 * 1LL * 2 % M1 + b[k]) % M1 - f[t] * 1LL * b[k - t] % M1 + M1) % M1;
t2 = ((t2 * 1LL * 2 % M2 + b[k]) % M2 - g[t] * 1LL * b[k - t] % M2 + M2) % M2;
ins(t1, t2);
}
for (int k = i; k < i + j; k++)
{
int tt = 0;
for (int l = a[k].x; l <= a[k].y; l++)
c[++tt] = b[l];
bfs(tt);
an[a[k].f] = ans;
}
for (int k = 1; k <= tot; k++)
h[to[k]] = -1;
i += j;
}
for (int i = 1; i <= m; i++)
{
if (an[i])
printf("%lld\n", an[i]);
else
printf("Impossible\n");
}
}
}