头像

y1丶星辰_

南京大学




离线:7天前


最近来访(20)
用户头像
Gerchart
用户头像
SmiLeeeee
用户头像
生在逢时
用户头像
学会DP
用户头像
垫底抽風
用户头像
北海没有WA
用户头像
Gift
用户头像
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表 —> 折叠刀

题目描述

建模成算法描述即: 做M次查询
每次查询[L,R]区间中的最大值


算法1

(线段树) $O(nlogn)$

线段树—工具箱 提着很重,但是里面工具很全
代码长 初学容易Seg fault,(一定要把区间合并和区间划分的思想理解透彻,这是写出线段树的关键)
但是可拓展性非常强 (工具箱内什么工具都能放)
非常适合维护一些具有区间划分合并性质的变量

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

(拓展树状数组) $O(nlogn)$

树状数组是手术刀 非常轻便 代码量小
面对一些特定的问题 能够非常迅速地解决
但是对于一些更为繁杂的问题 就显得有点力不从心了~~haha

树状数组最快的当然还是1-x的前缀和查询
但是树状数组同样可以拓展区间查询

但是这样的话本来logN的前缀操作
拓展成区间查询之后 时间复杂度 会变成常数非常大的logN

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;
}
void add(int x ,LL c){
    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];
        add(i , 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

(模拟栈消除) $O(n)$

我们发现基本操作只需要考虑连续的2个数
消除不掉的数会影响后面的操作
那么我们用栈来模拟

时间复杂度

参考文献

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丶星辰_
3个月前

算法1

(BFS) $O(n^2)$

参考flood fill算法

时间复杂度

参考文献

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

(并查集) $O(n^2)$

被一个小细节坑了好几次
就是memset()函数
这个函数只能赋值 0 和 -1
解释如下:

假如我们想赋值1的话
写成memset(s,1,sizeof s);
会发现结果全为: 16843009
这是因为memset是以字节为单位来完成赋值的,而一个int有四个字节,也就是说在上面的例子中其实我们赋的值是十六进制的0x01010101,即二进制数0000 0001 0000 0001 0000 0001 0000 0001,换算成十进制为16843009,最终得出我们上面的结果。

因此如果我们想将数组置为我们要的十进制值,只能置为0或-1,因为0的二进制表示全为0,-1的二进制表示全为1,按字节为单位完成赋值的结果可以保持不变。

时间复杂度

参考文献

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;
}