2019-07-17  2024-09-15    466 字  1 分钟

MINA-4236 JOIOJI

用 J, O, I 来记录到当前位置一共有多少个 J, O, I。

假设 A[i] B[i] C[i] 表示到第i个位置一共有多少个 J, O, I。

那么只要找到一对 A[j]-B[j]==A[i]-B[i] && C[j]-B[j]==C[i]-B[i] 即可

Code
/**
 *    author: Akvicor
 *    created: 2019-07-17 10-09-13
**/
 
#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef DEBUG
string to_string(string s) {
    return '"' + s + '"';
}
 
string to_string(const char* s) {
    return to_string((string) s);
}
 
string to_string(bool b) {
return (b ? "true" : "false");
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto &x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}
#endif
 
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 17
#endif
 
#ifdef DEBUG
#define FAST_IO 17
#else
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#endif
 
#define LL long long
#define ULL unsigned long long
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define reep(i, n) for(int i = 0; i <= (n); ++i)
#define lop(i, a, n) for(int i = a; i < (n); ++i)
#define loop(i, a, n) for(int i = a; i <= (n); ++i)
#define ALL(v) (v).begin(), (v).end()
#define PB push_back
#define VI vector<int>
#define PII pair<int,int>
#define FI first
#define SE second
#define SZ(x) ((int)(x).size())
 
const double EPS = 1e-6;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const LL LINF = 0x7f7f7f7f7f7f7f7f;
const int MAXN = (int)1e6 + 10;
const int MOD = (int)1e9 + 7;
 
string s;
map<pair<int, int>, int> m;
int ans, J, O, I, n;
 
int main(){
    FAST_IO;
 
    ans = J = O = I = n = 0;
 
    cin >> n >> s;
 
    m[make_pair(0, 0)] = -1;
 
    rep(i, n){
        J += s[i]=='J';
        O += s[i]=='O';
        I += s[i]=='I';
        // 如果出现了两次相同的 (J-O, I-O) 
        // 那么就说明这两次之间的 J、O、I 的数量一定相等,符合题目要求,只需用 当前i-上次的i 即可
        if(m.find(make_pair(J-O, I-O))==m.end()) m[make_pair(J-O, I-O)] = i;
        else ans = max(ans, i-m[make_pair(J-O, I-O)]);
    }
 
    cout << ans << endl;
 
    return 0;
}