头像

HimenoSena




离线:5小时前


最近来访(4)
用户头像
棉花糖SR
用户头像
我是sun
用户头像
滑稽_ωノ


log函数和ln函数的复杂度是多少???

 cout << log(23455678) << '\n';
 cout << ln(21412466) << '\n';




活动打卡代码 AcWing 164. 可达性统计


**拓扑排序后用Bitset位运算**
#include<bits/stdc++.h>

using namespace std;
int vis[30010], in[30010], ans[30010];
int head[30010], nex[30010], to[30010], tot = 0;
int n, m;
bitset<30010> f[30010];
void add(int a, int b){
    nex[++tot] = head[a];
    to[tot] = b;
    head[a] = tot;
}
bool toposort(){
    int cnt = 0;
    queue<int> q;
    for(int i = 1;i <= n; i++)  if(in[i] == 0) q.push(i);
    while(!q.empty()){
        auto t = q.front(); q.pop();
        ans[++cnt] = t;
        for(int i = head[t]; i; i = nex[i]){
            int y = to[i];
            if(--in[y] == 0) q.push(y);
        }
    }
    return n == cnt;
}

int main(){
cin >> n >> m;
for(int i = 1; i <= m; i++){
    int u, v; cin >> u >> v;
    in[v]++;
    add(u, v);
}
toposort();
for(int i = n; i >= 1; i--){
    int x = ans[i];
    f[x].reset(); f[x][x] = 1;
    for(int j = head[x]; j; j = nex[j]){
        f[x] |= f[to[j]];
    }
}
for(int i = 1; i <= n; i++)
cout << f[i].count() << '\n';

}


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

状压DP
#include<bits/stdc++.h>

using namespace std;

int maps[20][20];
int f[1 << 20][20];

int main(){
int n; cin >> n;
for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        cin >> maps[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] + maps[k][j]);
            }
        }
    }
}
cout << f[(1 << n) - 1][n-1] <<'\n';

}



#include<bits/stdc++.h>

using namespace std;
int vis[11];
int ans[11];
int n;
void finds(int k){
    if(k == n + 1){
        for(int i = 1; i <= n; i++){
            cout << ans[i] <<' ';
        }
        cout <<'\n';
        return;
    }
    for(int i = 1; i <= n; i++){
        if(vis[i]) continue;
        vis[i] = 1;
        ans[k] = i;
        finds(k+1);
        vis[i] = 0;
        ans[k] = 0;
    }
}

int main(){
    cin >> n;
    finds(1);


}






92题剪枝版本
#include<bits/stdc++.h>

using namespace std;

vector<int> num;
int n, m;

void solve(int x){
     如果已经超过m个或者剩下的全取了还不够m个就剪枝
    if(int(num.size()) > m || (n - x + 1) < (m - int(num.size()))) return;
    if(x == n + 1){
        for(auto c : num){
            cout << c << " ";
        }
        cout << '\n';
        return;
    }
    先取后不取
    num.push_back(x);
    solve(x + 1);
    num.pop_back();

    solve(x + 1);
}


int main(){
cin >> n >> m;
solve(1);



}




#include<bits/stdc++.h>

using namespace std;

vector<int> num;
int n;
void solve(int x){
    if(x == n + 1){
        for(auto c : num){
            cout << c << " ";
        }
        cout << '\n';
        return;
    }
    在选和不选之间先不选,而后在是选
    solve(x + 1);

    num.push_back(x);
    solve(x + 1);
    num.pop_back();
}


int main(){
cin >> n;
solve(1);
}


#include<bits/stdc++.h>

using namespace std;

vector<int> num;
int n;

void solve(int x){
    if(x == n + 1){
        for(auto c : num){
            cout << c << " ";
        }
        cout << '\n';
        return;
    }
    在选和不选之间选择先选,然后再是不选
    num.push_back(x);
    solve(x + 1);
    num.pop_back();

    solve(x + 1);

}


int main(){
cin >> n;
solve(1);



}





活动打卡代码 AcWing 178. 第K短路


先求一遍终点到其他点的最短路,利用最短路小于等于第K短路的估值函数,Astar求第K短路。
求终点到其他点的最短路需要反向建边。 注意用不同的数组区分
如果终点和起点一样 要舍去搜索一开始加入的dis[s] = 0的情况。
#include<bits/stdc++.h>

using namespace std;
struct node{
    int r, val;
    bool operator<(const node b)const{
        return val > b.val;
    }
};
int dis[1010];
int vis[1010];
int head1[1010], nex1[200100], to1[200100], val1[200100],  tot1 = 0;
int head2[1010], nex2[200100], to2[200100], val2[200100],  tot2 = 0;
void add1(int u, int v, int d){
    nex1[++tot1] = head1[u];
    to1[tot1] = v; 
    val1[tot1] = d;
    head1[u] = tot1;
}
void add2(int u, int v, int d){
    nex2[++tot2] = head2[u];
    to2[tot2] = v; 
    val2[tot2] = d;
    head2[u] = tot2;
}
void dijkstra(int s){
    memset(vis, 0, sizeof vis);
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0;
    priority_queue<node> q;
    q.push(node{s, 0});
    while(!q.empty()){
        auto t = q.top(); q.pop();
        if(vis[t.r]) continue;
        vis[t.r] = 1;
        for(int i = head1[t.r]; i; i = nex1[i]){
            int y = to1[i], v = val1[i];
            if(dis[y] > dis[t.r] + v){
                dis[y] = dis[t.r] + v;
                q.push(node{y, dis[y]});
            }
        }
    }
    return;
}
int Astar(int s, int t, int cnt){
    typedef pair<int, pair<int, int>> piii;
    memset(vis, 0, sizeof vis);
    priority_queue<piii, vector<piii>, greater<piii>> q;
    q.push({dis[s],{0,s}});
    while(!q.empty()){
        auto x = q.top(); q.pop();
        int ver = x.second.second, d = x.second.first;
        vis[ver]++;
        if(ver == t && vis[ver] == cnt){
            return d;
        }
        for(int i = head2[ver]; i; i = nex2[i]){
            int y = to2[i], v = val2[i];
            if(vis[y] < cnt){
            q.push({d + v + dis[y] , {d + v, y}});
            }
        }
    }
    return -1;
}

int main(){
int n, m;
cin >> n >> m;
for(int i = 1; i <= m; i++){
    int u, v, l; cin >> u >> v >> l;
    add1(v, u, l); add2(u, v, l);
}
int s, t, k; cin >> s >> t >> k;
dijkstra(t);
if(s == t) k++;
cout << Astar(s, t, k);

}

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 177. 噩梦

双向搜索 
#include<bits/stdc++.h>

using namespace std;
int n, m, ct;
char maps[880][880];
int k[880][880];
int dx[4]={1, -1, 0, 0}, dy[4]={0, 0, -1, 1};
struct node{
    int x, y;
};
node M, G, Z[2];
bool check1(int x, int y){
    return (x >= 1 && y >= 1 && x <= n && y <= m && (maps[x][y] == '.' || maps[x][y] =='G'|| maps[x][y] =='M'));
}
bool check2(int x, int y, int t){
    for(int i = 0; i <= 1; i++){
        if(abs(Z[i].x - x) + abs(Z[i].y - y) <= 2 * t) return false;
    }
    return true;
}
int bfs(){
    queue<node> boy, girl;
    memset(k, 0, sizeof k);
    boy.push(M); girl.push(G);
    int time = 0;
    while(!boy.empty() || !girl.empty()){
        time++;
        for(int i = 1;  i <= 3; i++){   控制boy队列更新三次
            for(int j = 1, len = int(boy.size()); j <= len; j++){
                auto t = boy.front();  boy.pop();
                if(!check2(t.x, t.y, time) || !check1(t.x, t.y)) continue;
                for(int z = 0; z <= 3; z++){
                    int x = t.x + dx[z], y = t.y + dy[z];
                    if(!check2(x, y, time) || !check1(x, y)) continue;
                    if(k[x][y] == 2) return time;
                    else if(k[x][y] == 0){
                        k[x][y] = 1;
                        boy.push(node{x,y});
                    }
                }
            }
        }
        for(int j = 1, len = int(girl.size()); j <= len; j++){控制girl队列更新1次
        auto t = girl.front(); girl.pop();
        if(!check2(t.x, t.y, time) || !check1(t.x, t.y)) continue;   每次取出来的点都要判断是否已经在范围内
        for(int i = 0; i <= 3; i++){
            int x = t.x + dx[i], y = t.y + dy[i];
            if(!check2(x, y, time) || !check1(x, y)) continue;
            if(k[x][y] == 1) return time; 因为一个点可能会被重复走到所以不能用计数的办法
            else if(k[x][y] == 0){
                k[x][y] = 2;
                girl.push(node{x,y});
            }
        }
        }
    }
    return -1;
}

int main(){
int T;cin >> T;
while(T--){
ct = 0;
cin >> n >> m;
for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
        cin >> maps[i][j];
        if(maps[i][j] == 'M') {
            M.x = i; M.y = j;
        }
        if(maps[i][j] == 'G'){
            G.x = i; G.y = j;
        }
        if(maps[i][j] == 'Z'){
            Z[ct].x = i; Z[ct++].y = j;
        }
    }
}

int ans = bfs();
cout << ans <<'\n';
}



}



活动打卡代码 AcWing 176. 装满的油箱


 拆点的思想。一个点有多个状态
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int p[1010];
int head[1010], to[20100], nex[20100], val[20200], tot = 0;   双向建边,数组要开两倍
int vis[1010][110];
int dist[1010][110];
void add(int u, int v, int d){
    nex[++tot] = head[u];
    to[tot] = v; 
    val[tot] = d;
    head[u] = tot;
}

struct node{
    int cost, u, c;
    bool operator<(const node &b)const{
        return cost > b.cost;
    }
};

int dijkstra(int C, int st, int ed){
priority_queue<node> q;
q.push({0, st, 0});
memset(dist, 0x3f, sizeof (dist));
memset(vis, 0, sizeof(vis));
dist[st][0] = 0;
while(!q.empty()){
    auto t = q.top(); q.pop();
    if(t.u == ed) return t.cost;
    if(vis[t.u][t.c] == 1) continue;  重复入队的排除掉
    vis[t.u][t.c]  = 1;     记录入队
    if(t.c < C && t.cost + p[t.u] < dist[t.u][t.c + 1]){    只有加油后的花费比原先的低才有资格更新。
        dist[t.u][t.c + 1] = t.cost+p[t.u];
        q.push(node{dist[t.u][t.c+1], t.u, t.c+1});
    }
    for(int i = head[t.u]; i; i = nex[i]){
        if(t.c >= val[i])
        if(dist[to[i]][t.c-val[i]] > t.cost){
            dist[to[i]][t.c-val[i]] = t.cost;
            q.push(node{t.cost, to[i], t.c-val[i]});
        }
    }
}
    return -1;
}


int main(){
int n, m, o;
cin >> n >> m;
for(int i = 0; i < n; i++){
    cin >> p[i];
}
while(m-- ){
    int u, v, d;   cin >> u >> v >> d;
    add(u, v, d);
    add(v, u, d);
}
cin >> o;
while(o -- ){
    int c, s, t;
    cin >> c >> s >> t;
    int ans = dijkstra(c, s, t);
    if(ans == -1) puts("impossible");
    else cout << ans << '\n';
}


}


活动打卡代码 AcWing 175. 电路维修

维护Dijkstra 双端队列  因为本题中边权值只存在两种 0,1 所以直接使用双端队列而不是优先队列 
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
struct node{
    int x, y;
};
int dx[4] = {-1, -1, 1, 1}, dy[4] = {-1, 1, 1, -1};
int ix[4] = {-1, -1, 0, 0}, iy[4] = {-1, 0, 0, -1};
char cs[]= "\\/\\/";
int  t, n, m;
char mp[550][550];
int dis[550][550];
bool check(int x, int y){
    if(x >= 0 && y >= 0 && x <= n && y <= m) return true;
    return false;
}

int bfs(){
    memset(dis, 0x3f, sizeof(dis));
    deque<node> q;
    dis[0][0] = 0;
    q.push_back({0, 0});
    while(!q.empty()){
        auto x = q.front();
        q.pop_front();
        for(int i = 0; i <= 3; i++){
            int nx = x.x + dx[i], ny = x.y + dy[i];
            int a  = x.x + ix[i], b = x.y + iy[i];
            if(!check(nx, ny)) continue;
            int w = 0; 
            if(mp[a][b] != cs[i]) w = 1;
            if(dis[nx][ny] > dis[x.x][x.y] + w){
                dis[nx][ny] = dis[x.x][x.y] + w;
                if(w == 1) q.push_back({nx, ny});
                else q.push_front({nx, ny});
            }
        }
    }
    if(dis[n][m] == 0x3f3f3f3f) return -1;
    return dis[n][m];
}



int main(){
cin >> t;
while(t--){
cin >> n >> m;
for(int i = 0; i < n; i++){
    scanf("%s", mp[i]);
}
int ans = bfs();
if(ans == -1) puts("NO SOLUTION");
else cout << dis[n][m] << '\n';
}

}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~