y1丶星辰_

410

Gerchart
SmiLeeeee

rmhce
BT7274
Juicy
Shaaou
kuso

y1丶星辰_
1个月前
#include <iostream>
#include <algorithm>
using namespace std;
//并查集
const int M = 12;
const int N = 12 * 12 * 12;
int p[N] , s[N];

int find(int x){
if (p[x] != x){
p[x] = find(p[x]);
}
return p[x];
}

int dx[6] = {1 , 0 , -1 , 0 , 0 , 0};
int dy[6] = {0 , 1 , 0 , -1 , 0 , 0};
int dz[6] = {0 , 0 , 0 , 0 , 1 , -1};
//层 行 列
int get(int i ,int j ,int k){
return (12*12)*i + 12 * j + k;
}
char a[M][M][M];

int n , m , q;
int x , y;
int main(){
for (int i = 0;i<=N;++i){
p[i] = i;
s[i] = 1;
}
cin >> q >> n >> m;

for (int k = 1;k<=q;++k){
for (int i = 1;i<=n;++i){
for (int j = 1;j<=m;++j){
cin >> a[k][i][j];
}
}
}
cin >> x >> y;
if (a[1][x][y] == '#'){
cout << "0" << endl;
}else{
for (int k = 1;k<=q;++k){
for (int i = 1;i<=n;++i){
for (int j = 1;j<=m;++j){
if (a[k][i][j] == '#')  continue;

int t = get(k , i , j);

for (int d = 0;d<6;++d){
int zz = k + dz[d];
int xx = i + dx[d];
int yy = j + dy[d];

if (a[zz][xx][yy] == '#')   continue;

if (zz <= 0 || zz > q || xx <= 0 || xx > n || yy <= 0 || yy > m)    continue;

int tt = get(zz , xx , yy);

int b = find(t);
int c = find(tt);

if (b != c){
p[c] = b;
s[b] += s[c];
}
}
}
}
}
cout << s[find(get(1 , x , y))];
}

return 0;
}



y1丶星辰_
1个月前

ST表 —> 折叠刀

### 算法1

#### C++ 代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 2e5 + 10;
typedef long long LL;
int a[N];
struct Node{
int l , r;
LL mx;
}tr[4*N];

int n , m ;

void pushup(int u){
int l = u << 1;
int r = u << 1 | 1;
tr[u].mx = max(tr[l].mx , tr[r].mx);
}
void build(int u ,int l ,int r){
if (l == r){
tr[u] = { l , l , a[l]};
}else{
tr[u] = {l , r};
int mid = l + r >> 1;
build(u << 1 , l , mid);
build(u << 1 | 1 , mid + 1 , r);
pushup(u);
}

}

LL query(int u ,int l , int r){
if (tr[u].l >= l && tr[u].r <= r){
return tr[u].mx;
}else{
int mid = tr[u].l + tr[u].r >> 1;
LL res = -1e15;
if (l <= mid){
res = max(res , query(u << 1 , l , r));
}
if (r > mid){
res = max(res , query(u << 1 | 1 , l , r));
}
return res;
}

}

int main(){
cin >> n;
for (int i = 1 ;i<=n;++i){
scanf("%d",&a[i]);
}
build(1 , 1 , n);
cin >> m;
int l , r;
while (m--){
scanf("%d%d",&l,&r);
LL s = query(1 , l , r);
printf("%lld\n",s);
}

return 0;
}


### 算法2

#### C++ 代码

//树状数组
#include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;
const int N = 2e5 + 10;
int n , m ;
LL tr[N] , a[N];

int lowbit(int x){
return x & -x;
}
for (int i = x;i<=n;i += lowbit(i)){
tr[i] = max(tr[i] , c);
}
}
//求前缀和
LL sum(int x){
LL sum = 0;
for (int i = x; i > 0 ; i -= lowbit(i)){
sum += tr[i];
}
return sum;
}
//求区间最大值
LL mx(int l ,int r){
if (r > l){
if (r - lowbit(r) >= l){
return max(tr[r] , mx(l , r - lowbit(r) ) );
}else{
return max(a[r] , mx(l , r-1 ) );
}
}else if (r == l){
return a[l];
}else{
return -1e15;
}
}

int main()
{
cin >> n;
memset(tr,-0x3f,sizeof tr);
//注意边界处理
for(int i = 1;i <= n;++ i){
cin >> a[i];
}

cin >> m;//询问个数
int l , r ;
while (m--)
{
//询问区间左右端点
cin >> l >> r;
cout << mx(l, r) << endl;
}
return 0;
}



### 算法3

##### (RMQ算法和ST表) $O(nlogn)$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 200010,M = 18;
int a[N];
int n,m;
int f[N][M];

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

for(int j = 0;j<M;j++){
for(int i = 1;i+(1<<j)-1<=n;i++)
if(!j)f[i][j] = a[i];
else f[i][j] = max(f[i][j-1],f[i+(1<<j-1)][j-1]);
}

cin>>m;
while(m--){
int l,r;
cin>>l>>r;
int len = r-l+1;
int k = log(len)/log(2);
cout<< max(f[l][k],f[r-(1<<k)+1][k])<<endl;;
}
return 0;
}


y1丶星辰_
1个月前

y1丶星辰_
2个月前

### 算法1

#### C++ 代码

#include <iostream>
#include <stack>
using namespace std;

const int N = 2e5 + 10;
int a[N];

stack<int> s;

int n;
bool isValid(){
while (s.size() > 1){
int t1 = s.top();
s.pop();
int t2 = s.top();
s.pop();

if (t1 < 0 || t2 < 0){
//说明上次的消除是不合法的 因为不够消的
return false;
}

if ((t1%2) == (t2%2)){
//如果两个数奇偶性相同 那么肯定可以直接消除
}else{
//考虑怎么消去第一个数
if (t1 % 2 == 0){
s.push(t2);
}else{

s.push(t2 - 1);
}
}
}

if (s.size() == 0){
return true;
}
//全部消除完毕

int last = s.top();

//有可能剩下一个

if (last < 0 || last % 2 == 1){
return false;
}

return true;
}
int main(){
cin >> n;
for (int i = 0;i<n;++i){
scanf("%d",&a[i]);
s.push(a[i]);
}

bool k = isValid();

if (k){
puts("YES");
}else{
puts("NO");
}

return 0;
}


y1丶星辰_
4个月前

### 算法1

#### C++ 代码

#include <iostream>
#include <cstring>
using namespace std;
int n, m, x, y, f[30][30], ans;
char Map[30][30];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
queue<pair<int, int> > q;
int main() {
while (scanf("%d%d", &m, &n) != EOF) {
if (m == 0 && n == 0) return 0;
for (int i = 1;i <= n; i++)
for (int j = 1;j <= m; j++) {
cin >> Map[i][j];
if (Map[i][j] == '@') x = i, y = j;
}
ans = 0; memset(f, 0, sizeof f); q.push(make_pair(x, y)); f[x][y] = 1;
while (q.size()) {
pair<int, int> o = q.front(); q.pop(); ans++;
for (int i = 0;i < 4; i++) {
int xx = o.first + dx[i], yy = o.second + dy[i];
if (xx < 1 || xx > n || yy < 1 || yy > m || f[xx][yy] || Map[xx][yy] == '#') continue;
q.push(make_pair(xx, yy)); f[xx][yy] = 1;
}
}
printf("%d\n", ans);
}
}


### 算法2

#### C++ 代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 25;
const int M = N * N;
char  g[N][N];
int p[M];
int s[M];
int  n,  m  ;
int dx[4] = {-1 , 0 , 1 , 0};
int dy[4] = {0 , 1 , 0 , -1};
int get(int i,int j){
return i * m + j;
}
int find(int x){
if (p[x] != x){
p[x] = find(p[x]);
}
return p[x];
}
void unio(){
for (int i = 0;i<n;++i){
for (int j = 0;j<m;++j){
if (g[i][j] =='.' || g[i][j] == '@'){
for (int k = 0;k<4;++k){
int x = i + dx[k];
int y = j + dy[k];
if (x < 0 || x >= n || y < 0 || y >= m) continue;
if (g[x][y] == '#') continue;

int a = find(get(i,j));
int b = find(get(x,y));

if (a != b){
//并查集合并
p[b] = a;
s[a] += s[b];
}

}
}
}
}
}
int main(){
while (scanf("%d%d",&m,&n), n || m){
for (int i = 0;i<n;++i){
scanf("%s",g[i]);
}
for (int i = 0;i<M;++i){
p[i] = i;
s[i] = 1;
}
int xx , yy ;
for (int i = 0;i<n;++i){
for (int j = 0;j<m;++j){
if (g[i][j] == '@'){
xx = i;
yy = j;
}
}
}
unio();
printf("%d\n",s[find(get(xx,yy))]);
}

return 0;
}