Discretization

From EOJ Wiki
Revision as of 12:48, 22 March 2018 by Ultmaster (talk | contribs) (Created page with "== Discrete on strings == <syntaxhighlight lang='cpp'> #include <bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 300; map<string, int> M; string M...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Discrete on strings

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 300;
map<string, int> M;
string MM[maxn];
int ID(const string &s) {
    if (M.find(s) == M.end()) {
        int m = M.size();
        M[s] = ++m;
        MM[m] = s;
    } return M[s];
}

int main() {
    string s, t;
    int is = ID(s), it = ID(t);
    int n = M.size();  // size
    cout << MM[n] << endl;  // reverse query
    return 0;
}

Discrete on points

const int maxn = 1e4 + 10;
map<int, int> M;
int MM[maxn], M_size;
void discrete(const vector<int> &raw) {
    vector<int> V(raw.begin(), raw.end());
    sort(V.begin(), V.end());
    M.clear();
    V.erase(unique(V.begin(), V.end()), V.end());
    for (unsigned i = 0; i < V.size(); ++i) {
        MM[i + 1] = V[i];
        M[V[i]] = i + 1;
    }
    M_size = M.size();
}

Version 2

void discrete(int* a, int n) {
    static int t[maxn];
    static map<int, int> mp;
    memcpy(t, a, n * sizeof(int)); mp.clear();
    sort(t, t + n);
    int sz = int(unique(t, t + n) - t);
    for (int i = 0; i < sz; ++i)
        mp[t[i]] = i + 1;
    for (int i = 0; i < n; ++i)
        a[i] = mp[a[i]];
}