头像

FUJANG


访客:233

在线 


新鲜事 原文

FUJANG
9天前
图片


新鲜事 原文

FUJANG
10天前
我是傻逼
图片


新鲜事 原文

FUJANG
24天前
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊


新鲜事 原文

FUJANG
25天前
图片


新鲜事 原文

FUJANG
27天前
我要女装!!!!!!!!


新鲜事 原文

FUJANG
30天前
acmer 没有周末 上午leetcode周赛 下午看书 深夜div2



FUJANG
30天前

对顶栈



class BrowserHistory {
    stack<string> l;
    stack<string> r;
public:
    BrowserHistory(string homepage) {
        l.push(homepage);
    }

    void visit(string url) {
        l.push(url);
        while (!r.empty()) {
            r.pop();
        }
    }

    string back(int steps) {
        while (steps > 0 && l.size() > 1) {
            string x = l.top();
            l.pop();
            r.push(x);
            steps--;
        }
        return l.top();
    }

    string forward(int steps) {
        while (steps > 0 && !r.empty()) {
            string x = r.top();
            r.pop();
            l.push(x);
            steps--;
        }
        return l.top();
    }
};

/**
 * Your BrowserHistory object will be instantiated and called as such:
 * BrowserHistory* obj = new BrowserHistory(homepage);
 * obj->visit(url);
 * string param_2 = obj->back(steps);
 * string param_3 = obj->forward(steps);
 */


新鲜事 原文

FUJANG
1个月前
为啥y总丢眼镜你们都很开心的样子


活动打卡代码 AcWing 91. 最短Hamilton路径

FUJANG
1个月前

最短Hamilton路径

分析

我们可以采用朴素算法,其时间复杂度为O(n*n!)n!为枚举n个点的全排列,n代表枚举路径的长度求得结果,这个算法的时间复杂度太高,不符合。而我们可以用二进制状态压缩DP来把时间复杂度优化到O((n^2)*(2^n)),我们用F[i,j]表示点被经过的状态对应二进制数i,且目前处于点j的最短路径

在起点时F[1,0]=0,即目前处于点0且只经过了点0的最短路径为0。为方便起见,我们将数组中其他元素设为无穷大,最终目的是求F[(1<<n),n-1]的值,即经过所有点且最终处于n-1的最短路径

在任意时刻,有公式F[i,j]=min(F[i,j],F[i^(1<<j),k]+weight[k,j]),根据分析可得k一定是倒数第二个经过的点。我们枚举k,当k对应在i的二进制为1时,我们讨论这种情况并比较

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 20, M = 1 << 20;
int weight[N][N], F[M][N];

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

    memset(F, 0x3f, sizeof F);
    F[1][0] = 0;
    for (int i = 1; i < 1 << n; i++)
        for (int j = 0; j < n; j++)
            if (i >> j & 1)
                for (int k = 0; k < n; k++)
                    if ((i ^ 1 << j) >> k & 1)
                        F[i][j] = min(F[i][j], F[i ^ 1 << j][k] + weight[k][j]);

    printf("%d", F[(1 << n) - 1][n - 1]);
}


活动打卡代码 AcWing 90. 64位整数乘法

FUJANG
1个月前

64位整数乘法

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL power(LL a, LL b, LL c) {
    LL ans = 0;
    for (; b; b >>= 1) {
        if (b & 1) ans = (ans + a) % c;
        a = a * 2 % c;
    }
    return ans;
}
int main() {
    LL a, b, p;
    scanf("%lld%lld%lld", &a, &b, &p);
    LL ans = power(a, b, p);
    printf("%lld", ans);
}

复杂度

我们可以用b&1运算表示b的二进制下的最低位,并用b>>1来舍去最低位。在递归的过程中把>>&结合,其时间复杂度为O(logb),与上一题不同的是位数问题,但是每次%p之后都能保证不超过2*10^18,在long long的范围内