macat

6.6万

hellozmc

M_400
Penguin.66
oldmomsimith
._314
becklee
-浪漫主义狗-

19sm

iamswz

smcsurvey

macat
2022-01-08 10:32

### 二分

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <string>

using namespace std;
const int N = 50010;
string name[N];
string low[N], high[N];
string l[N], h[N];
int n;

int main() {
ios::sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> name[i];
low[i] = name[i];
sort(low[i].begin(), low[i].end());
high[i] = low[i];
reverse(high[i].begin(), high[i].end());
l[i] = low[i], h[i] = high[i];
}
sort(l + 1, l + 1 + n);
sort(h + 1, h + 1 + n);
for(int i = 1; i <= n; ++i) {
int pl = lower_bound(h + 1, h + 1 + n, low[i]) - h;
int pr = upper_bound(l + 1, l + 1 + n, high[i]) - l - 1;
// cout << high[i] << " " << pr << endl;
// if(pl > n) pl = n;
// if(pr > n) pr = n;
cout << pl << " " << pr << endl;
}

return 0;
}



macat
2022-01-07 12:56

### 爆搜

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;
const int N = 10;
char g[N][N];
char path[N * N];
int n;
bool st[N][N];
int ans = 0;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int l, r;

void print(int idx) {
for(int i = 1; i <= idx; ++i) putchar(path[i]);
putchar('\n');
}

bool check(int idx) {
int l = 0, r = 0;
int i = 1;
while(i <= idx && path[i] == '(') i++, l++;
while(i <= idx && path[i] == ')') i++, r++;
if(i <= idx) return false;
if(l == r) ans = max(ans, l + r);
if(l < r) return false;
return true;
}
void dfs(int x, int y, int idx) {
st[x][y] = true;
path[idx] = g[x][y];

// cout << x << " " << y << endl;
// print(idx);
// int t = check(idx);
// cout << t << endl;
if(!check(idx)) {
st[x][y] = false;
return;
}
for(int i = 0; i < 4; ++i) {
int r = x + dx[i], c = y + dy[i];
if(r <= 0 || c <= 0 || r > n || c > n || st[r][c]) continue;
dfs(r, c, idx + 1);
}
st[x][y] = false;
}

int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%s", g[i] + 1);
dfs(1, 1, 1);
printf("%d\n", ans);
return 0;
}


macat
2022-01-06 11:01

### 差分

1. 连续的相同的高度只能产生一种贡献，故可以缩为一点
2. 对于中间的元素，一个谷会对答案增加一个贡献，一个峰会减少一个贡献
3. 边界上的元素(i = 1 或 i = n) 为峰时减少一个贡献
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int n, m;
int c[N];

int main() {
scanf("%d", &n);
int minv = 0x3f3f3f3f;
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(b + 1, b + 1 + n);
m = unique(b + 1, b + 1 + n) - b - 1;
// 缩点
int idx = 0;
for(int i = 1; i <= n; ++i) {
if(i < n && a[i] == a[i + 1]) {
while(i < n && a[i] == a[i + 1]) i++;
}
a[++idx] = lower_bound(b + 1, b + 1 + m, a[i]) - b;;
}
n = idx;
// for(int i = 1; i <= n; ++i) printf("%d ", a[i]);
// puts("");

for(int i = 1; i <= n; ++i) {
int t = a[i];
if(i != 1 && i != n){
if(a[i] < a[i - 1] && a[i] < a[i + 1]) c[t]++;
else if(a[i] > a[i - 1] && a[i] > a[i + 1]) c[t]--;
}
else if(i == 1) {
if(a[i] > a[i + 1]) c[t]--;
}
else if(i == n) {
if(a[i] > a[i - 1]) c[t]--;
}
}
int ans = 1, s = 1;
for(int i = 1; i <= m; ++i) {
s += c[i];
ans = max(ans, s);
}
printf("%d\n", ans);
return 0;
}


macat
2022-01-05 09:09

### BFS

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second

using namespace std;
const int N = 1010;
typedef pair<int, int> PII;
bool g[N][N];
int n, m;
int x1, y1;
bool st[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
queue<PII> q;
int dist[N][N];

void dfs(int x, int y, int d) {
for(int i = 0; i < 4; ++i) {
int r = x + dx[i], c = y + dy[i];
if(r < 0 || c < 0 || r > n || c > n || st[r][c]) continue;
if(!g[r][c]) {
dist[r][c] = d;
st[r][c] = true;
dfs(r, c, d);
}
else {
dist[r][c] = d + 1;
st[r][c] = true;
q.push(make_pair(r, c));
}
}
}

int bfs() {
q.push(make_pair(0, 0));
st[0][0] = true;
while(q.size()) {
PII t = q.front();
q.pop();
dfs(t.x, t.y, dist[t.x][t.y]);
}
// for(int i = 1; i <= n; ++i){
//     for(int j = 1; j <= n; ++j) {
//         printf("%d %d %d\n", i, j, dist[i][j]);
//     }
// }
return dist[x1][y1];
}

int main() {
scanf("%d%d%d", &m, &x1, &y1);
while(m--) {
int x, y;
scanf("%d%d", &x, &y);
g[x][y] = true;
n = max(n, x);
n = max(n, y);
}
n++;
printf("%d\n", bfs());
return 0;
}


macat
2022-01-04 09:02

### BFS

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>
#define x first
#define y second

using namespace std;
const int N = 55;
typedef pair<int, int> PII;
char g[N][N];
bool st[N][N];
int dist[N][N];

int n, m;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
queue<PII> q;
void init(int x, int y) {
st[x][y] = true;
dist[x][y] = 0;
q.push(make_pair(x, y));
for(int i = 0; i < 4; ++i) {
int r = x + dx[i], c = y + dy[i];
if(r <= 0 || c <= 0 || r > n || c > m || g[r][c] == '.' || st[r][c]) continue;
init(r, c);
}
}

int bfs(int x, int y) {
init(x, y);
while(q.size()) {
PII t = q.front();
q.pop();
for(int i = 0; i < 4; ++i) {
int r = t.x + dx[i], c = t.y + dy[i];
if(r <= 0 || c <= 0 || r > n || c > m || st[r][c]) continue;
if(g[r][c] == '.') {
dist[r][c] = dist[t.x][t.y] + 1;
q.push(make_pair(r, c));
st[r][c] = true;
}
else return dist[t.x][t.y];
}
}
return -1;
}

int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) scanf("%s", g[i] + 1);
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(g[i][j] == 'X') {
printf("%d\n", bfs(i, j));
return 0;
}
}
}
printf("%d\n", -1);

return 0;
}


macat
2022-01-03 09:58

### 1. 差分

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;
const int N = 1e6 + 10;
int a[N];
int n, k;

int main() {
scanf("%d%d", &n, &k);
int l, r;
while(k--) {
scanf("%d%d", &l, &r);
a[l]++, a[r + 1]--;
}
for(int i = 1; i <= n; ++i) a[i] += a[i - 1];
sort(a + 1, a + 1 + n);
printf("%d\n", a[n + 1 >> 1]);

return 0;
}


### 2. 树状数组

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;
const int N = 1e6 + 10;
typedef long long LL;
int tr[N];
int n, k;
int a[N];

int lowbit(int x) {
return x & -x;
}
void add(int pos, int x) {
for(int i = pos; i <= n; i += lowbit(i)) tr[i] += x;
}
int query(int pos) {
LL ans = 0;
for(int i = pos; i; i -= lowbit(i)) ans += tr[i];
return ans;
}
int main() {
scanf("%d%d", &n, &k);
int l, r;
while(k--) {
scanf("%d%d", &l, &r);
}
for(int i = 1; i <= n; ++i) a[i] = query(i);
sort(a + 1, a + 1 + n);
printf("%d\n", a[n + 1 >> 1]);
return 0;
}


macat
2022-01-02 08:52

### 暴力

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100;
typedef long long LL;
char a[N], b[N];
int n, m;

LL cal(char s[], int n, int base, int add, int pos) {
LL ans = 0;
for(int i = 1; i <= n; ++i) {
char c = s[i] - '0';
if(pos == i) c = (c + add) % base;
ans = ans * base + c;
}
return ans;
}

bool check(int x, int y) {
LL t1 = cal(a, n, 2, 1, x);
LL t2 = cal(b, m, 3, 1, y);
LL t3 = cal(b, m, 3, 2, y);
return t1 == t2 || t1 == t3;
}

LL cal() {
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(check(i, j)) {
return cal(a, n, 2, 1, i);
}
}
}
return -1;
}

int main() {
scanf("%s%s", a + 1, b + 1);
n = strlen(a + 1);
m = strlen(b + 1);
printf("%d\n", cal());

return 0;
}


macat
2021-12-12 19:25
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 1e5 + 10;

struct Node {
int son[2], p;
int v;
int size, lazy;
void init(int _v, int _p) {
v = _v;
p = _p;
size = 1;
}
}tr[N];
int root, idx;
int n, m;

void pushup(int u) {
int l = tr[u].son[0], r = tr[u].son[1];
tr[u].size = tr[l].size + tr[r].size + 1;
}

void pushdown(int u) {
if(tr[u].lazy) {
int& l = tr[u].son[0];
int& r = tr[u].son[1];
swap(l, r);
tr[l].lazy ^= 1;
tr[r].lazy ^= 1;
tr[u].lazy = 0;
}
}

void rotate(int x) {
int y = tr[x].p, z = tr[y].p;
int k = x == tr[y].son[1];// k = 0, x是左子节点，k = 1, x是右子节点

tr[z].son[y == tr[z].son[1]] = x, tr[x].p = z;
tr[y].son[k] = tr[x].son[k ^ 1], tr[tr[x].son[k ^ 1]].p = y;
tr[x].son[k ^ 1] = y, tr[y].p = x;

pushup(y);
pushup(x);
}

// 将结点x旋转成k的子节点
void splay(int x, int k) {
while(tr[x].p != k) {
int y = tr[x].p, z = tr[y].p;
if(z != k) {
// 折线关系两次x
// 直线关系一次y一次x
if((tr[y].son[1] == x) == (tr[z].son[1] == y)) rotate(y);
else rotate(x);
}
rotate(x);
}
if(!k) root = x;// 0号结点的子节点是根节点
}

void insert(int v) {
int u = root, p = 0;
// 寻找值v的真实位置
while(u) p = u, u = tr[u].son[v > tr[u].v];

u = ++idx;
if(p) tr[p].son[v > tr[p].v] = u;
tr[u].init(v, p);
splay(u, 0);// 新结点旋转到0的下面
}
// 寻找序列种的第k个点，即中序遍历中第k个点
int get_k(int k) {
int u = root;
while(true) {
pushdown(u);
int l = tr[u].son[0], r = tr[u].son[1];
if(tr[l].size >= k) u = l;
else if(tr[l].size + 1 == k) return u;
else k -= tr[l].size + 1, u = r;
}
return -1;
}
void print(int u) {
pushdown(u);
// 输出中序遍历
if(tr[u].son[0]) print(tr[u].son[0]);
if(tr[u].v >= 1 && tr[u].v <= n) printf("%d ", tr[u].v);
if(tr[u].son[1]) print(tr[u].son[1]);
}

int main() {
scanf("%d%d", &n, &m);
// 多插入0和n+1作为哨兵
for(int i = 0; i <= n + 1; ++i) insert(i);
while(m--) {
int l, r;
scanf("%d%d", &l, &r);
// 前面多了一个哨兵0，所以翻转的区间的[l + 1, r + 1], 哨兵为l和r+2
l = get_k(l);
r = get_k(r + 2);
// 将目标区间成r的左子树
splay(l, 0);// 将l旋转成根
splay(r, l); // 将r旋转到l下面
//反转整棵左子树即可
tr[tr[r].son[0]].lazy ^= 1;
}
print(root);
return 0;
}



macat
2021-12-03 09:17

### CDQ分治

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;

struct Data{
int a, b, c;
int cnt;
int ans;
bool operator < (const Data& rhs) const{
if(a != rhs.a) return a < rhs.a;
if(b != rhs.b) return b < rhs.b;
return c < rhs.c;
}

bool operator == (const Data& rhs) const {
return a == rhs.a && b == rhs.b && c == rhs.c;
}
}a[N], t[N];
int n, m;
int ans[M];
int tr[M];

int lowbit(int x) {
return x & -x;
}

void add(int pos, int x) {
for(int i = pos; i <= m; i += lowbit(i)) {
tr[i] += x;
}
}

int query(int pos) {
int ans = 0;
for(int i = pos; i; i -= lowbit(i)) {
ans += tr[i];
}
return ans;
}

void cdq(int l, int r) {
if(l >= r) return;
int mid = l + r >> 1;
cdq(l, mid);
cdq(mid + 1, r);
int k = 0;
int i = l, j = mid + 1;
while(i <= mid && j <= r) {
if(a[i].b <= a[j].b) {
t[k++] = a[i++];
}
else {
// 计算前面有多少个i满足要求
a[j].ans += query(a[j].c);
t[k++] = a[j++];
}
}
while(i <= mid) {
t[k++] = a[i++];
}
while(j <= r) {
a[j].ans += query(a[j].c);
t[k++] = a[j++];
}
// 恢复现场
for(int i = l; i <= mid; ++i) add(a[i].c, -a[i].cnt);
// 归并
for(int i = l, j = 0; i <= r; ++i, ++j) a[i] = t[j];
}

int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].c), a[i].cnt = 1;
sort(a + 1, a + 1 + n);
int k = 0;
for(int i = 1; i <= n; ++i) {
if(a[i] == a[i - 1]) a[k].cnt++;
else a[++k] = a[i];
}
// n = k;
cdq(1, k);
for(int i = 1; i <= k; ++i) ans[a[i].ans + a[i].cnt - 1] += a[i].cnt; // 相同的点也要记录
for(int i = 0; i < n; ++i) printf("%d\n", ans[i]);

return 0;
}


macat
2021-12-01 16:54

### dsu on tree

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, M = N * 2;
typedef long long LL;
int n;
int color[N], son[N], sz[N], cnt[N];
int h[N], e[M], ne[M], idx;
LL ans[N];
int mx;
LL sum;

void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}

void dfs_son(int u, int fa) {
sz[u] = 1;
for(int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if(j == fa) continue;
dfs_son(j, u);
sz[u] += sz[j];
if(sz[j] > sz[son[u]]) son[u] = j;
}
// cout << u << " " << son[u] << endl;
}

void update(int u, int fa, int sign, int pson) {
int c = color[u];
cnt[c] += sign;
if(cnt[c] > mx) mx = cnt[c], sum = c;
else if(cnt[c] == mx)sum += c;
for(int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if(j == fa || j == pson) continue;
update(j, u, sign, pson);
}
}

void dfs(int u, int fa, int type) {
for(int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if(j == fa || j == son[u]) continue;
dfs(j, u, 0);
}
if(son[u]) dfs(son[u], u, 1);
update(u, fa, 1, son[u]);
ans[u] = sum;
// cout << u << " " << sum << endl;
if(type == 0) update(u, fa, -1, 0), sum = mx = 0;
}

int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%d", &color[i]);
memset(h, -1, sizeof h);
for(int i = 1; i < n; ++i) {
int a, b;
scanf("%d%d", &a, &b);