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 <bits/stdc++.h> | |
using namespace std; | |
const int N = 8, M = (1 << 24) + 100; | |
int n; | |
double memo[M]; | |
void compress(vector<int>& a) { |
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 <bits/stdc++.h> | |
using namespace std; | |
long long dp[20][2][2]; | |
string s; | |
long long solve(int idx = 0, int carry = 0, int needCarry = 0) { | |
if (idx * 2 == (int) s.size()) | |
return needCarry == carry; | |
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
// Returns the Bezout's coefficients of the smallest positive linear combination of a and b | |
// using the extended Euclidean algorithm. | |
// (i.e. GCD(a, b) = s.a + t.b). | |
// O(GCD(a, b)) = O(log(n)) | |
pair<int, int> extendedEuclid(int a, int b) { | |
/* PROOF: | |
------ | |
gcd(a, b) = s.a + t.b -->(1) | |
= gcd(b, a mod b) = s'.b + t'.(a mod b), a mod b = a - q.b, q = floor(a/b) |
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
/** | |
* The problem can be solved greedly with the help of segment tree or other data strucutres. | |
* | |
* The idea is to find the segment with the minimum total sum, then flip (negate) it. | |
* We keep doing so for k times, or until all the values in the array become non-negative. | |
* | |
* One key observation about this problem is that it does not matter whether | |
* the segments are overlapping or not. | |
* | |
* I used segment tree in order to find and flip segments quickly. |
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
/** | |
* I used DP to solve this problem. | |
* I try to minimize the the sum of the sequence, so I do the following for every element: | |
* 1. Just leave it positive as is. | |
* 2. Negate it if possible and go to the next valid position (i.e. the position where another negation can occur). | |
* | |
* Why linear iterations in {@function next} will not result in TLE ?! | |
* Because in order to iterating in the while loop we need every element is greater than or equal the sum of all the previous | |
* elements. Such sequence will be with length of at most log2(10^9). | |
*/ |
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 <bits/stdc++.h> | |
using namespace std; | |
const int N = 100100, K = 55, MOD = 5000000; | |
int n, k, a[N], BIT[K][N]; | |
int val, tmp, cnt, id; | |
map<int, int> mp; | |
int fix(int x) { |
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 <bits/stdc++.h> | |
using namespace std; | |
const int N = 100100, K = 55, MOD = 5000000; | |
int n, k, a[N], BIT[K][N]; | |
void update(int tid, int idx, int val) { | |
while (idx < N) { | |
BIT[tid][idx] = (BIT[tid][idx] + val) % MOD; |
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 <bits/stdc++.h> | |
using namespace std; | |
typedef long long Long; | |
const int N = 100100, M = 200200; | |
int T, n, u, v, w; | |
int edgeId; | |
int head[N], cnt[N], nxt[M], to[M], weight[M]; |
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 <bits/stdc++.h> | |
using namespace std; | |
const int N = 101; | |
// Direction arrays in spiral order { Right, Down, Left, Up } | |
const int dx[] = { 0, 1, 0, -1 }; | |
const int dy[] = { 1, 0, -1, 0 }; | |
int n, m, a[N][N]; |
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 <bits/stdc++.h> | |
using namespace std; | |
const int N = 33, M = N * 105; | |
int n, a[N]; | |
char sign[N]; | |
bool vis[N][M * 2][N]; | |
string s; | |
set<int> st; |
NewerOlder