Link
- Codeforces Round #374 Div. 2 (Contest 721)
- Editorial
A. One-dimensional Japanese Crossword
Just count consecutive ‘B’ in the sequence.
/*
*
*/
#include <cstdio>
#include <iostream>
using namespace std;
int a[100];
char c[100];
int main(){
#ifndef ONLINE_JUDGE
freopen("a5.in", "r", stdin);
#endif
int n;
scanf("%d", &n);
scanf("%s", c);
int k = 0;
int count = 0;
for (int i = 0; i < n; ++i) {
if (c[i] == 'B') {
count++;
} else {
if (count != 0) {
a[k++] = count;
count = 0;
}
}
}
if (count != 0) a[k++] = count;
printf("%d\n", k);
for (int j = 0; j < k; ++j) {
printf("%d%c", a[j], j==k-1 ? '\n' : ' ');
}
return 0;
}
B. Passwords
This is also easy, just count the number for each string length. You even don’t need to process any string manipulation.
/*
*
*/
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
char pass[105][105];
char correct[105]; //correct pass
int count[105]; // count[i] means how many pass is length i.
int main(){
#ifndef ONLINE_JUDGE
freopen("b2.in", "r", stdin);
#endif
int n, k;
scanf("%d %d", &n, &k);
for (int i = 0; i < n; ++i) {
scanf("%s", pass[i]);
int len = strlen(pass[i]);
count[len]++;
}
scanf("%s", correct);
int correct_len = strlen(correct);
int wrongpass = 0;
for (int j = 0; j < correct_len; ++j) {
wrongpass += count[j];
}
int min = wrongpass + wrongpass / k * 5 + 1;
wrongpass += count[correct_len] - 1;
int max = wrongpass + wrongpass / k * 5 + 1;
printf("%d %d", min, max);
return 0;
}
C. Journey
I felt it is difficult than problem D. During the contest, I tried to solve it by DFS but I got TLE.
/*
* TLE
* DFS method is not fast enough
*/
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
// road[i][j] is edge from i to start[i][j].first.
// start[i][j].second is the cost for this edge.
vector<pair<int, int> > road[5005];
int optimumroad[5005];
int n, m, T;
int maximumVisit = 0;
// current city with current time
bool dfs(int city, int time, int visited) {
if (time > T) return false;
if (city == n) {
if (visited > maximumVisit) {
maximumVisit = visited;
return true;
} else {
return false;
}
}
bool maximumRouteFound = false;
for (int i = 0; i < road[city].size(); ++i) {
if (dfs(road[city][i].first, time + road[city][i].second, visited + 1)) {
optimumroad[city] = road[city][i].first;
//cout << city << " " << road[city][i].first << endl;
maximumRouteFound = true;
}
}
return maximumRouteFound;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("c4.in", "r", stdin);
#endif
scanf("%d %d %d", &n, &m, &T);
for (int i = 0; i < m; ++i) {
int u, v, t;
scanf("%d %d %d", &u, &v, &t);
road[u].push_back(make_pair(v, t));
}
dfs(1, 0, 1);
printf("%d\n", maximumVisit);
int currentcity = 1;
printf("1 ");
while (true) {
currentcity = optimumroad[currentcity];
if (currentcity == n) {
printf("%d\n", n);
break;
} else {
printf("%d ", currentcity);
}
}
return 0;
}
To get answer, we can use DP (dynamic programming) to reduce computational complexity as \(O(mn)\).
/*
* DP method
* Accepted 93 ms 98300 KB
*/
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define INF (1e9+5)
struct edge {
int from;
int to;
int cost;
};
vector<edge> roadvec;
int optimumroad[5005];
int n, m, T;
int maximumVisit = 0;
// dp[i][j]: Minimum cost when already visited i cities, for city j.
// INF indicates not reachable.
// Do not use 0 for i and j.
int dp[2][5005];
// to remember optimal path. path[i][j]: To visit i cities at city j, optimal path is come from path[i][j].
int path[5005][5005];
int main(){
#ifndef ONLINE_JUDGE
freopen("c4.in", "r", stdin);
#endif
scanf("%d %d %d", &n, &m, &T);
for (int i = 0; i < m; ++i) {
int u, v, t;
scanf("%d %d %d", &u, &v, &t);
roadvec.push_back(edge{u, v, t});
}
for (int j = 0; j < 5005; ++j) {
dp[0][j] = INF;
}
dp[0][1] = 0;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < 5005; ++j) {
dp[1][j] = INF; // Need to init each time!
}
for (int j = 0; j < m; ++j) {
if (dp[0][roadvec[j].from] + roadvec[j].cost < dp[1][roadvec[j].to]) {
dp[1][roadvec[j].to] = dp[0][roadvec[j].from] + roadvec[j].cost;
path[i+1][roadvec[j].to] = roadvec[j].from;
//cout << "i " << i << ", from " << roadvec[j].from <<
// ", to " << roadvec[j].to << ", cost " << roadvec[j].cost <<
// ", dp[1][to] " << dp[1][roadvec[j].to] << endl;
}
}
if (dp[1][n] <= T) {
maximumVisit = i+1;
}
swap(dp[0], dp[1]);
}
// Reconstruct optimum road path
optimumroad[maximumVisit] = n;
for (int i = maximumVisit - 1; i > 0; --i) {
optimumroad[i] = path[i+1][optimumroad[i+1]];
}
printf("%d\n", maximumVisit);
for (int k = 1; k <= maximumVisit; ++k) {
printf("%d%c", optimumroad[k], k==maximumVisit ? '\n' : ' ');
}
return 0;
}
D. Maxim and Array
Basic strategy to get minimum product is as follows,
1. If the product is positive, then we want to reduce it. We can change the sign of number whose absolute value is minimum.
2. If the product is 0, then there exists at least one 0 in the array. We can change this 0 to get total product as negative.
3. If the product is negative, then we want to keep the sign of product as negative and just want to get the total absolute value product as maximum. To do this, we should get minimum absolute value and change this absolute value by +x.
To get minimum absolute value for each iteration efficiently, we can use priority_queue.
/*
* Accepted 233 ms 9300 KB
* use priority_queue
*/
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll sign[200005]; // sign: +1 positive or 0, -1 negative.
ll ans[200005];
ll checksign(ll a) {
if (a >= 0) {
return 1;
} else {
return -1;
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("d5.in", "r", stdin);
#endif
ll n, k, x;
scanf("%lli %lli %lli", &n, &k, &x);
priority_queue<P, vector<P>, greater<P> > q;
ll negative_count = 0;
ll a;
for (int i = 0; i < n; ++i) {
scanf("%lli", &a);
sign[i] = checksign(a);
if (sign[i] == -1) negative_count++;
q.push(make_pair(a * sign[i], i));
}
P current = q.top();
ll min = current.first;
if (negative_count % 2 == 0 && min >= k * x) { // positive case: no 0 exists and we cannot make total product as 0 or negative
q.pop();
q.push(make_pair(current.first - k * x, current.second));
} else {
if (negative_count % 2 == 0) { // Make negative_count as odd
ll repeat = min / x + 1;
q.pop();
q.push(make_pair(-(current.first - repeat * x), current.second));
k -= repeat;
if (sign[current.second] == 1) {
sign[current.second] = -1;
negative_count++;
} else {
sign[current.second] = 1;
negative_count--;
}
}
while (k > 0) {
current = q.top(); q.pop();
q.push(make_pair(current.first + x, current.second));
k--;
}
}
while (!q.empty()) {
P current = q.top(); q.pop();
ans[current.second] = sign[current.second] * current.first;
}
for (int i = 0; i < n; ++i) {
printf("%lli%c", ans[i], i==n-1 ? '\n' : ' ');
}
return 0;
}