anti-

$\huge{\color{#FF1493}{\mathscr{Atcoder}}}$

2933

AhNorth

acwing_23961
cpy2010

kkaa
Samuely
ljh_lxy
alan69359
yexc

Moyou

18910310021
violet_garden

lpq1234

anti-
7天前
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 120;
int g[N][N];
int d[N][N];
int dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };
int n, m;
void bfs() {

memset(d, -1, sizeof d);
d[0][0] = 0;
queue<pair<int, int>> q;
q.push({ 0,0 });
while (!q.empty()) {
auto top = q.front();
for (int i = 0; i < 4; i++) {

int x = top.first + dx[i], y = top.second + dy[i];
if (x < n && x >= 0 && y >= 0 && y < m && d[x][y] == -1 && g[x][y] == 0) {

d[x][y] = d[top.first][top.second] + 1;
q.push({ x,y });
}
}
q.pop();
}

cout << d[n - 1][m - 1];
}
int main() {

ios::sync_with_stdio(false);

cin.tie(NULL);
cin >> n >> m;

for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> g[i][j];
bfs();
return 0;
}


anti-
7天前
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define LL long long
const int N = 20;
int n;
char g[N][N];
bool col[N], dg[N], udg[N];
bool row[N];
/*void dfs(int deep)
{
if (deep == n) {

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << g[i][j];
}
cout << '\n';
}
cout << '\n';
return;
}
for (int i = 0; i < n; i++)
{

if (!col[i] && !dg[deep + i] && !udg[n - deep + i]) {

g[deep][i] = 'Q';
col[i] = dg[deep + i] = udg[n - deep + i] = true;
dfs(deep + 1);
col[i] = dg[deep + i] = udg[n - deep + i] = false;
g[deep][i] = '.';
}

}

}
*/

void dfs(int x, int y, int s)
{
if (s > n) return;
if (y == n) y = 0, x++;

if (x == n)
{
if (s == n)
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << g[i][j];
}
cout << '\n';
}
cout << '\n';

}
return;
}
g[x][y] = '.';
//不放皇后
dfs(x, y + 1, s);
//放皇后
if (!row[x] && !col[y] && !dg[x + y] && !udg[n - y + x])
{
g[x][y] = 'Q';
row[x] = col[y] = dg[x + y] = udg[n - y + x] = true;
dfs(x, y + 1, s + 1);
row[x] = col[y] = dg[x + y] = udg[n - y + x] = false;
g[x][y] = '.';

}

}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);

cin >> n;
//初始化
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
g[i][j] = '.';
//dfs(0);
dfs(0, 0, 0);

return 0;
}


anti-
8天前
#include<iostream>
#include<algorithm>
using namespace std;
int n;
const int N = 10;
int a[N];
bool b[N];
void dfs(int kk)
{
if (kk == n) {

for (int i = 0; i < n; i++) cout << a[i] << ' ';
cout << '\n';
return;
}

for (int i = 1; i <= n; i++)
{
if (!b[i]) {

a[kk] = i;
b[i] = true;
dfs(kk+1);
a[kk] = 0;
b[i] = false;
}

}

}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);

cin >> n;

dfs(0);
return 0;
}


anti-
8天前
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);

vector<pair<int,int>> a(10+1);
for (int i = 1; i <= 10; i++) cin >> a[i].second;

sort(a.begin() + 1, a.end(), [](const auto& b1, const auto& b2)->bool {

return b1.second < b2.second;
});
//cout << &a[0].second << ' ' << &a[1].second << ' ';
//for (auto c : a) cout << c.second << ' ';
for (int i = 1; i <= 10; i++) cout << a[i].second << ' ';
cout << '\n';

return 0;
}



anti-
9天前
#include<iostream>
typedef unsigned long long ULL;
using namespace std;
const int N = 1e6 + 10;
const int P = 131;
char str[N];
ULL p[N], h[N];
ULL cp(int a, int b) {

return h[b] - h[a - 1] * p[b - (a - 1)];

}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);

int n, m;
cin >> n >> m;
cin >> str + 1;
p[0] = 1;
for (int i = 1; i <= n; i++)
{
h[i] = h[i - 1] * P + str[i];

p[i] = p[i - 1] * P;

}

while (m--) {

int a, b, c, d;
cin >> a >> b >> c >> d;
if (cp(a, b) == cp(c, d)) cout << "Yes\n";
else cout << "No\n";
}

return 0;
}


anti-
11天前
#include<iostream>

using namespace std;
const int N = 100003;
int ne[N], e[N], h[N], idx;
void insert(int kk) {

int kk_1 = (kk % N + N) % N;

e[idx] = kk;
ne[idx] = h[kk_1];
h[kk_1] = idx;
idx++;

}
bool find(int kk) {

int kk_1 = (kk % N + N) % N;
for (int i = h[kk_1]; i != -1; i = ne[i])
if (e[i] == kk) return true;

return false;

}
int main() {

ios::sync_with_stdio(false);
cin.tie(nullptr);

for (int i = 0; i < N; i++) h[i] = -1;
int m;
cin >> m;
string s;
int x;
while (m--)
{
cin >> s;
cin >> x;
if (s == "I") {

insert(x);
}
else {

if (find(x)) cout << "Yes\n";
else cout << "No\n";
}

}

return 0;
}


anti-
12天前
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int h[N], ph[N], hp[N];
int cnt;
int m;//m用来记录第几个插入的数
void h_swap(int a, int b) {

swap(h[a], h[b]);//交换值
//交换两个映射
//这个时候h的坐标是a,b所对应的p的坐标是hp[a],hp[b]
swap(hp[a], hp[b]);

swap(ph[hp[a]], ph[hp[b]]);

}
void down(int u) {

int t = u;

if (u * 2 <= cnt && h[t] > h[u * 2]) t = u * 2;
if (u * 2 + 1 <= cnt && h[t] > h[u * 2 + 1]) t = u * 2 + 1;

if (t != u) {

h_swap(t, u);
down(t);
}

}
void up(int u) {

while (u / 2 != 0 && h[u] < h[u / 2]) {

h_swap(u, u / 2);

u /= 2;

}

}
int main() {

ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
while (n--) {

string s;
cin >> s;
if (s == "I") {

int a;
cin >> a;
h[++cnt] = a;
ph[++m] = cnt;
hp[cnt] = m;
up(cnt);
}
else if (s == "PM") cout << h[1] << "\n";
else if (s == "DM") {

h_swap(1, cnt);
cnt--;
down(1);
}
else if (s == "D") {

int a;
cin >> a;
a = ph[a];
h_swap(a, cnt);
cnt--;
up(a);
down(a);
}
else {
int a;
cin >> a;
int b;
cin >> b;
a = ph[a];

h[a] = b;
down(a);
up(a);

}
}

return 0;
}


anti-
14天前
#include<iostream>
#include<algorithm>
using namespace std;
using i64 = long long;
const int N = 100010;
int n, m;
int h[N], size_h;//h->heap
void down(int u) {
int t = u;//t存的是三个点中最小点的编号,一开始假设要down的点是最小值
//判断左子节点
if (u * 2 <= size_h && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= size_h && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t) {//这也是为什么要开t的原因,因为要判断与原来的点是否相同,如果kk!=t的话说明一开始认为的点不是最小值点的编号

swap(h[u], h[t]);
down(t);//要全部都比较过才算把位置正确分配
}
}
int main() {
ios::sync_with_stdio(false);;
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> h[i];
size_h = n;
for (int i = n / 2; i; i--) down(i);
while (m--) {

cout << h[1] <<' ';
h[1] = h[size_h];
size_h--;
down(1);
}
return 0;
}


anti-
15天前
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e6 + 10;
int q[N];
int n, m;
int find(int kk) {

if (q[kk] != kk) q[kk] = find(q[kk]);
return q[kk];
}
int main() {
ios::sync_with_stdio(false);;
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < n; i++) {

q[i] = i;
}
while (m--) {
int b, c;
char a;
cin >> a;
if (a == 'M') {

cin >> b >> c;
q[find(b)] = find(c);
}
else {
cin >> b >> c;
if (find(b) == find(c)) cout << "Yes\n";
else cout << "No\n";
}
}
return 0;
}


anti-
27天前
#include<iostream>

using namespace std;

const int N = 100010;

int son[N][26], cnt[N], idx;
//cnt存储的是以当前这个点单词有多少个,idx表示当前用到了哪个下标
char str[N];
void insert(char str[]) {//插入一个字符串

int p = 0;//从根节点开始

for (int i = 0; str[i]; i++)
{
int u = str[i] - 'a';//将字母映射成数字
if (!son[p][u]) son[p][u] = ++idx; //如果这个节点不存在就创建出来

p = son[p][u]; //走到下一个点
}
cnt[p]++;//表示以这个点结尾的单词数量多了一个
}
int query(char str[])
{
int p = 0;
for (int i = 0; str[i]; i++)
{
int u = str[i] - 'a';
if (!son[p][u]) return 0;//查询不出来就返回0
p = son[p][u]; //否则就走过去
}
return cnt[p];//返回以p节点的单词数量
}
int main() {

ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
while (n--)
{
char op[2];
cin >> op >> str;
if (op[0] == 'I') insert(str);
else printf("%d\n", query(str));
}

return 0;
}