rookie升职记

359

### 不要用ios::sync_with_stdio(false);的范例，真的要被坑死了

#include <iostream>
#include <cmath>

using namespace std;

const int N = 300010;

int f[N], d[N], si[N];

void init(int n) {
for (int i = 1; i <= n; i ++ ) {
f[i] = i;
d[i] = 0;
si[i] = 1;
}
}
/*

*/
int get(int x) {
if (x == f[x]) return x;
int root = get(f[x]);//递归计算集合代表，啥叫集合代表，就是能代表这个集合的元素，那不就是头结点嘛
d[x] += d[f[x]];//维护d数组，对边权求和
return f[x] = root;//路径压缩
}
/*

*/
/*

*/
void merge(int x, int y) {
x = get(x), y = get(y);
f[x] = y;
d[x] = si[y];
si[y] += si[x];
}

int main() {
//ios::sync_with_stdio(false);
int T; cin >> T;
init(N);
while (T -- ) {
char op[2]; int a, b;
cin >> op >> a >> b;
if (*op == 'M') {
if (get(a) == get(b)) continue;
merge(a, b);
}
else {
if (get(a) == get(b)) {
cout << abs(d[a] - d[b]) - 1 << endl;
}
else puts("-1");
}
}
}


#include <iostream>

using namespace std;

const int N = 110;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int q[N][N];

int main() {
int n, m; cin >> n >> m;
int x = 0, y = 0, d = 1;
for (int i = 1; i <= n * m; i ++  ) {
q[x][y] = i;
int a = x + dx[d], b = y + dy[d];
if (a < 0 || a >= n || b < 0 || b >= m || q[a][b]) {
d = (d + 1) % 4;
a = x + dx[d], b = y + dy[d];
}
x = a, y = b;
}

for (int i = 0; i < n; i ++ ) {
for (int j = 0; j < m; j ++ )
cout << q[i][j] << ' ';
cout << endl;
}

return 0;
}


#include <iostream>

using namespace std;

const int N = 10010;

int n;
int f[N][N];

int main() {
cin >> n;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= i; j ++ )
cin >> f[i][j];

for (int i = n; i >= 1; i -- )
for (int j = 1; j <= i; j ++ )
f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);

cout << f[1][1] << endl;

return 0;
}


#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1000010;

int n;
int a[N];

int main() {
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

sort(a, a + n);

int res = 0;
for (int i = 0; i < n; i ++ ) {
res += abs(a[i] - a[n / 2]);
}

cout << res << endl;

return 0;
}


class MinStack {
public:
/** initialize your data structure here. */
stack<int> stk;
stack<int> stk_min;

MinStack() {

}

void push(int x) {
stk.push(x);
if (stk_min.size()) x = min(x, stk_min.top());
stk_min.push(x);
}

void pop() {
//因为前面每次都往里面插入x，所以，可以直接弹掉
//这是你没有想到的
stk.pop();
stk_min.pop();
}

int top() {
return stk.top();
}

int getMin() {
return stk_min.top();
}
};

/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/


/*
*@author SunLakeWalk
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>

using namespace std;

#define x first
#define y second

typedef long long ll;
typedef pair<ll, ll> PLL;

const int N = 100010, C = 1010, inf = 0x3f3f3f3f;

ll primes[N], cnt;
bool st[N];
//存一下b1的质因子，和质因子的个数
PLL factor[N];
ll cntf;
//存一下y约数
ll divider[N], cntd;

void get_primes(ll n) {
for (ll i = 2; i <= n; i ++ ) {
if (!st[i]) primes[cnt ++ ] = i;

for (ll j = 0; primes[j] * i <= n; j ++ ) {
st[i * primes[j]] = true;
if (i % primes[j] == 0) break;
}
}
}
//求出b1的所有质因子，和质因子的个数
void divide(ll n) {
for (ll i = 0; primes[i] <= n / primes[i]; i ++ ) {
int p = primes[i];
if (n % primes[i] == 0) {
ll s = 0;
while (n % primes[i] == 0) s ++, n /= p;
factor[++ cntf] = {p, s};
}
}
if (n > 1) factor[++ cntf] = {n, 1};
}

ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}

void dfs(ll u, ll p) {
if (u > cntf) {
divider[cntd ++ ] = p;
return;
}

for (ll i = 0; i <= factor[u].y; i ++ ) {
dfs(u + 1, p);
p *= factor[u].x;
}
}
void work() {
get_primes(N);
ll T; cin >> T;
while (T -- ) {
ll a0, a1, b0, b1; cin >> a0 >> a1 >> b0 >> b1;

cntf = 0;
divide(b1);

cntd = 0;
dfs(1, 1);

ll res = 0;
for (ll i = 0; i < cntd; i ++ ) {
int d = divider[i];
if (gcd(a0, d) == a1 && b0 * d / gcd(b0, d) == b1)
res ++;

}

cout << res << endl;
}
}

int main() {

work();

return 0;
}



#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;

const int N = 1 << 24;

int n, m, k;
int g[50], weights[N];
int cnt, ans;

void dfs(int u, int s) {
if (u == k) {//k为边界，搜到k不向下执行
weights[cnt ++ ] = s;//搜到边界，赋值
return;
}

if ((ll)s + g[u] <= m) dfs(u + 1, s + g[u]);//选当前
dfs(u + 1, s);//不选当前
}

void dfs2 (int u, int s) {
if (u == n) {
int l = 0, r = cnt - 1;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (weights[mid] + (ll)s <= m) l = mid;
else r = mid - 1;
}

if (weights[l] + (ll)s <= m) ans = max(ans, weights[l] + s);

return;
}

if ((ll)s + g[u] <= m) dfs2(u + 1, s + g[u]);//选当前
dfs2(u + 1, s);//不选当前
}
int main() {
cin >> m >> n;
for (int i = 0; i < n; i ++ ) cin >> g[i];

sort(g, g + n, greater<int>());//从大到小排序

k = n / 2 + 2;//后半搜索有二分，这里多分配两个
dfs(0, 0);

sort(weights, weights + cnt);//将打包好后排个序

int t = 1;
for (int i = 1; i < cnt; i ++ )//去重
if (weights[i] != weights[i - 1])
weights[t ++ ] = weights[i];

cnt = t;//去重后t个包

dfs2(k, 0);//从k开始搜

cout << ans << endl;

return 0;
}



/*

1 2 4 8 16 32 64 128

*/
#include <iostream>
#include <cstdio>

using namespace std;

const int N = 110;

int n;
int path[N];

bool dfs(int u, int depth){
//如果已经迭代到了当前最深，判断最后一次是否达到n
if (u == depth) return path[u - 1] == n;//当前层u为未进行确定下path值的层数，这里使边界条件

bool st[N] = {false};//将所有元素置为false

//剪枝1，优化搜索顺序，我们求的是最短的序列长度，所以我们搜的时候，让i和j尽可能得大，更快得接近m，（x[m]=n）
for (int i = u - 1; i >= 0; i -- )
for (int j = i; j >= 0; j -- ) {
int s = path[i] + path[j];//和
/*
剪枝2
题目里有了：
x[1] < x[2] < x[3] < ... < x[m - 1] < x[m]
对于每个k(2 <= k <= m)都存在两个整数i和j(1 <= i , j <= k - 1, i和j可以相等)，是的x[k] = x[i] + x[j]
所以我们这里i最大为u-1，j最大为i。
同样，s 即 x[k] 因为x[m] = n;且k <= m；所以s是不能大于n的。
同样，序列x[1], x[2], ... , x[m]是一个严格单调递增的序列，s为x[m] 一定要大于前面出现过的任何的数
同样，对于不同的i和j，x[i] + x[j]的值可能相同，这是我们就要运用到剪枝当中的第二个方法，排除等效冗余。因为相同的s，效果
是相同的，只需要搜s一次就可以了，所以我们可以用bool数组对s = x[i] + x[j] 进行判重避免之后搜索到同一个和s
*/
if (s > n || s <= path[u - 1] || st[s]) continue;
path[u] = s;
st[s] = true;
if (dfs(u + 1, depth)) return true;//如果搜到了n，就返回true
}
//cout << "----------------" << endl;
return false;//如果都没有搜到就返回false
}
int main() {
while (cin >> n, n) {
path[0] = 1;//路径从0开始计算

int depth = 1;
//迭代加深
//每次搜索从第一个数也就是第一层开始搜索，然后迭代depth次，如果没有得到答案，将深度加一，重新搜索
while (!dfs(1, depth)) depth ++;

for (int i = 0; i < depth; i ++ ) printf("%d ", path[i]);
puts("");
}

return 0;
}