Instantly share code, notes, and snippets.

# yodalee/q1.cpp

Last active March 25, 2017 12:21
Show Gist options
• Save yodalee/76040de7957d478ec09a7da50f6bd091 to your computer and use it in GitHub Desktop.
Some algorithm problem solve
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #include #include using namespace std; void peak(vector> &table, int row, int col) { for (int i = 0; i < row; ++i) { for (int j = 0; j < col; ++j) { cout << table[i][j] << " "; } cout << endl; } } //solve position -1 int solver(vector> &table, int n, int k) { if (table[n][k] != -1) { return table[n][k]; } else { if (k > n*(n-1)/2) { table[n][k] = 0; return 0; } else { int sum = 0; //cout << "process: (" << n << "," << k << ")" << endl; // pos is the position that ith number place for (int pos = 1; pos <= n; ++pos) { if (n-pos > k) { // if i-pos > j => place ith in pos will introduce too man inversion continue; } else { //cout << "pos: " << pos << " remainInversion: " << j-(i-pos) << endl; int remainInversion = k-(n-pos); // remain number of Inversion sum += solver(table, n-1, remainInversion); } } table[n][k] = sum; return sum; } } } int solve(int n, int k) { // prepare table vector> table(n+1, vector(k+1, -1)); for (int i = 1; i < n+1; ++i) { table[i][0] = 1; } int ans = solver(table, n, k); return ans; } int main(int argc, char *argv[]) { int n, k; cin >> n >> k; cout << solve(n, k) << endl; return 0; }
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #include #include using namespace std; void printVec(vector> &v) { cout << "peak: "; for (auto i: v) { cout << "(" << i.first << "," << i.second << ") "; } cout << endl; } int query(vector> &peak, unsigned int idx) { for (auto iter = peak.begin(); iter != peak.end(); iter++) { if (iter->first >= idx) { return iter->second; } } } void add(vector> &peak, unsigned int length, int insert) { // update peak list while (peak.size()) { if (peak.back().second < insert) { peak.pop_back(); } else { break; } } peak.push_back(pair(length, insert)); } int main() { int m; char ch[2]; unsigned int mod = 0; unsigned int lastQuery = 0; unsigned int length = 0; vector> peak; cin >> m >> mod; while (m--) { int x; cin >> ch >> x; if (ch[0] == 'I') { int insert = (x+lastQuery) % mod; add(peak, length, insert); length++; //printVec(peak); } else { lastQuery = query(peak, length-x); cout << lastQuery << endl; } } return 0; }
to join this conversation on GitHub. Already have an account? Sign in to comment