头像

南来北往




离线:11天前


最近来访(30)
用户头像
三分梦_8
用户头像
Hfour9
用户头像
小陌白
用户头像
.南山南
用户头像
全球变冷
用户头像
你回来了
用户头像
小轩喵灬
用户头像
caidd
用户头像
real_caidd
用户头像
来不及了
用户头像
Moyuing
用户头像
蔡币
用户头像
xxxdendaxion
用户头像
_朝暮
用户头像
なし
用户头像
微光_1

活动打卡代码 AcWing 845. 八数码

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
const int N = 8e5 + 10;
unordered_map<string,int> dist;
string s;

void bfs() {
    dist[s] = 0;
    queue<string> q;
    q.push(s);
    string end = "12345678x";
    int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 };
    while (q.size()) {
        string t = q.front();
        int di = dist[t];
        /*cout << t << endl;*/
        q.pop();
        if (t == end) {
            cout << dist[t];
            return;
        }
        int i = 0, j = 0,ind=0;
        ind = t.find('x');
        i = ind / 3, j = ind % 3;
        for (int z = 0; z < 4; z++) {
            int nx = i + dx[z], ny = j + dy[z];

            if ( nx < 0 || nx >= 3 || ny < 0 || ny >= 3)  continue;
            swap(t[ind], t[nx * 3 + ny]);
            if (dist[t] == 0) { dist[t] = di + 1; q.push(t); }
            swap(t[ind], t[nx * 3 + ny]);
        }

    }
    cout << -1;
}
int main() {
    for (int i = 1; i <= 9; i++) {
        char c;
        cin >> c;
        s+=c;
    }
    bfs();
}



C++ 代码

#include<bits/stdc++.h>


using namespace std;
const int N = 1e5 + 10;
int tr[N];
int n, m;
int lowbit(int x) {
    return x & (-x);
}
void add(int a, int c) {
    for (; a <= n; a += lowbit(a))
        tr[a] += c;

}
int sum(int a) {
    int res=0;
    for (; a; a -= lowbit(a)) res += (tr[a]%2+2)%2;
    return (res%2+2)%2;
}


int main() {
    cin >> n >> m;
    while (m--) {
        int q;
        cin >> q;

        if (q == 1) {
            int a, b;
            cin >> a >> b;
            add(a,1);
            add(b + 1, -1);
        }
        else {
            int a;
            cin >> a;
            cout << sum(a) << endl;
        }

    }
}



C++ 代码

#include<bits/stdc++.h>

using namespace std;
const int N = 1E5+10;
int q[N];
int n;
typedef long long ll;
void add(int a,int b,int c){
    q[a]+=c;
    q[b+1]-=c;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int t;
        cin>>t;
        add(i,i,t);
    }
    ll u=0,d=0;
    for(int i=1;i<=n;i++){
        if(q[i]>0) u+=q[i];
        else d-=q[i];
    }
    cout<<max(u,d)<<endl;
    return 0;
}


活动打卡代码 AcWing 346. 走廊泼水节

#include<bits/stdc++.h>


using namespace std;
int n;
const int N = 6010;
struct edg {

    int a, b, c;
}edgs[N];
bool cmp(edg& a, edg& b) {
    return a.c < b.c;
}
int p[N];
int cnt[N];
void init() {
    for (int i = 0; i < N; i++) { p[i] = i; cnt[i] = 1; }
}
int Find(int x) {
    if (p[x] != x) {
        p[x] = Find(p[x]);
    }
    return p[x];
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n;

        for (int i = 0; i < n - 1; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            edgs[i] = { a,b,c };
        }
        sort(edgs, edgs + n-1, cmp);
        init();
        int res = 0;
        for (int i = 0; i < n - 1; i++) {
            int a = edgs[i].a, b = edgs[i].b, c = edgs[i].c;
            int pa = Find(a), pb = Find(b);
            if (pa != pb) {
                res += (cnt[pa] * cnt[pb] - 1) * (c + 1);
                p[pa] = pb;
                cnt[pb] += cnt[pa];
            }
        }
        cout << res << endl;

    }
    return 0;
}



活动打卡代码 AcWing 1145. 北极通讯网络

#include<bits/stdc++.h>

using namespace std;
const int  N = 510;
int n, k;
int h[N], ne[N * N], w[N * N], e[N * N];
int ind;
struct zb {

    int x, y;
}zbs[N];
int cnt1 = 0;
int res[N * N];
struct xyd {

    int a, b, c;
}xyds[N*N];
int p[N];
void init() {
    for (int i = 1; i <= n; i++) p[i] = i;
}
int Find(int x) {
    if (x != p[x]) p[x] = Find(p[x]);
    return p[x];
}
int cnt;
bool cmp(xyd& x, xyd& y) {
    return x.c < y.c;
}
int main() {
    memset(h, -1, sizeof h);
    cin >> n >> k;
    if (k == n) { cout << fixed << setprecision(2) << 0.00 << endl; return 0; }
    for (int i = 1; i <= n; i++) {
        cin >> zbs[i].x >> zbs[i].y;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
        /*  cout << zbs[i].x - zbs[j].x << "??" << zbs[i].y - zbs[j].y << endl;
        */  int di = pow((zbs[i].x - zbs[j].x), 2) + pow((zbs[i].y - zbs[j].y), 2);
            xyds[cnt++] = { i,j,di };
        }
    }
    sort(xyds, xyds + cnt, cmp);
    init();
    for (int i = 0; i < cnt; i++) {
        int a = xyds[i].a, b = xyds[i].b, c = xyds[i].c;
        int pa = Find(a);
        int pb = Find(b);
        if (pa != pb) {
            res[cnt1++] = c;
            p[pa] = pb;
        }
    }
        if(k == 0)  cout << fixed << setprecision(2) << pow(res[cnt1-1],0.5) << endl;
        else cout << fixed << setprecision(2) << pow(res[cnt1-k],0.5) << endl;

    return 0;
}


活动打卡代码 AcWing 1146. 新的开始

#include<bits/stdc++.h>

using namespace std;
const int N = 310;
int g[N][N];
int n;
int res;
bool st[N];
int dist[N];
void prim() {
    memset(dist, 0x3f3f3f3f, sizeof dist);
    for (int i = 0; i <= n; i++) {
        int t = -1;
        for (int j = 0; j <= n; j++) {
            if (!st[j] && (t == -1 || dist[j] < dist[t])) t = j;
        }
        if (i > 0 && dist[t] == 0x3f3f3f3f) return;
        st[t] = true;
        if (i) res += dist[t];
        for (int j = 1; j <= n; j++) {
            if (!st[j]) dist[j] = min(dist[j], g[t][j]);
        }
    }
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> g[0][i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) cin >> g[i][j];
    }
    prim();
    cout << res << endl;
}


活动打卡代码 AcWing 1307. 牡牛和牝牛

#include<bits/stdc++.h>


using namespace std;
const int N =2e5 + 20;
typedef long long ll;
ll mod = 5000011;
int n, k;
ll fact[N], infact[N];
ll qmi(ll a, ll  k, ll p) {
    ll res = 1 % p;
    while (k) {
        if (k & 1) {
            (res *= a) %= p;
        }
        (a *= a) %= p;
        k >>= 1;
    }
    return res;
}
void init() {
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i++) {
        (fact[i] = (ll)fact[i - 1] * i) %= mod;
    }
    for (int i = 1; i < N; i++) {
        (infact[i] = (ll)infact[i - 1] * qmi(i, mod - 2, mod)) %= mod;
    }
}
int main() {
    cin >> n >> k;
    n += k;
    int z = 1 + k;
    ll res = 0;
    init();
    /*  for (int i = 1; i <= n; i++) cout << "in: " << infact[i] << endl;
    */  for (int i = 0; i * z <= n; i++) {
        int fm = n - i * z + i;

        (res += ((ll)fact[fm] * infact[i]) % mod * infact[fm - i] % mod) %= mod;

    }
    cout << res << endl;

    ### dp
    #include<bits/stdc++.h>

using namespace std;

const int N = 1e5+10;
int mod = 5000011;
int f[N];
int n,k;
int main(){
    cin>>n>>k;
    for(int i=1;i<=k+1;i++) f[i]= (i+1) % mod;
    for(int i = k+2;i<=n;i++){

        f[i] = (f[i-1] + f[i-k-1]) % mod;
    }
    cout<<f[n];

}
}


活动打卡代码 AcWing 217. 绿豆蛙的归宿

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;
const int M = 2 * N;
int cnt[N];
int h[N], ne[M], e[M], w[M];
int ind;
int n, m;
int fenmu;
int fenzi;
double res;
void add(int a, int b, int c) {
    e[ind] = b;
    ne[ind] = h[a];
    w[ind] = c;
    h[a] = ind++;
}
void dfs(int u,int di,double c) {
    if (u == n) {
        res += (di * 1.0 / c);
        return;
    }
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (cnt[e[i]] != 0) {
            dfs(j, w[i] + di, c * cnt[e[i]]);
        }
        else {
            dfs(j, w[i] + di, c); 
        }

    }
}

int main() {
    memset(h, -1, sizeof h);

    cin >> n >> m;
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        cnt[a]++;
    }
    //for (int i = 1; i <= ind; i++) cout << w[i] << endl;
    dfs(1,0,cnt[1]);
    //cout << fenmu << endl;
    //cout << fenzi << endl;
    /*cout << fixed << setprecision(2) << fenzi * 1.0 / fenmu << endl;*/
    cout << fixed << setprecision(2) << res<< endl;
}


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

#include<bits/stdc++.h>


using namespace std;
const int N = 30010;
int h[N], ne[N], e[N];
int ind;
int n, m;
deque<int > re;
void add(int a, int b) {
    e[ind] = b;
    ne[ind] = h[a];
    h[a] = ind++;
}
bitset<N> q[N];
int d[N];
void topsort() {
    queue<int> qu;
    for (int i = 1; i <= n; i++){
        if (d[i] == 0) qu.push(i);
    }
    while (qu.size()) {
        int u = qu.front();
        re.push_front(u);
        qu.pop();
        for (int i = h[u]; i != -1; i = ne[i]) {

            d[e[i]] --;
            if (d[e[i]] == 0) qu.push(e[i]);
        }
    }
}
int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        q[a][b] = 1;
        d[b]++;
    }
    for (int i = 1; i <= n; i++) q[i][i] = 1;
    topsort();

    for (auto r : re) {
        for (int i = h[r]; i != -1; i = ne[i]) {
            q[r] |= q[e[i]];
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << q[i].count() << endl;
    }
}


### dfs
#include<bits/stdc++.h>


using namespace std;
const int N = 30010;
int h[N], ne[N], e[N];
int ind;
int n, m;
deque<int > re;
bool st[N];
void add(int a, int b) {
    e[ind] = b;
    ne[ind] = h[a];
    h[a] = ind++;
}
bitset<N> q[N];
int d[N];
void topsort() {
    queue<int> qu;
    for (int i = 1; i <= n; i++){
        if (d[i] == 0) qu.push(i);
    }
    while (qu.size()) {
        int u = qu.front();
        re.push_front(u);
        qu.pop();
        for (int i = h[u]; i != -1; i = ne[i]) {

            d[e[i]] --;
            if (d[e[i]] == 0) qu.push(e[i]);
        }
    }
}
void dfs(int u) {
  /*  cout<<u<<endl;*/
    for (int i = h[u]; i != -1; i = ne[i]) {
        if(!st[e[i]]) dfs(e[i]);
        q[u] |= q[e[i]];
    }
    st[u] = true;
}
int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        q[a][b] = 1;
        d[b]++;
    }
    for (int i = 1; i <= n; i++) q[i][i] = 1;
    for (int i = 1; i <= n; i++) {
        if(!st[i]) dfs(i);
    }
    for (int i = 1; i <= n; i++) {
        cout << q[i].count() << endl;
    }
    /*topsort();

    for (auto r : re) {
        for (int i = h[r]; i != -1; i = ne[i]) {
            q[r] |= q[e[i]];
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << q[i].count() << endl;
    }*/
}


活动打卡代码 AcWing 1144. 连接格点

#include<bits/stdc++.h>

using namespace std;
int n, m;
const int N = 1010, M = 2010;
struct edg {
    int a, b, c;
}edgs[M * N];
bool cmp(edg& x, edg& y) {

    return x.c < y.c;
}
long long cnt;
int res;
int p[N * M];
int Find(int x) {
    if (p[x] != x) p[x] = Find(p[x]);
    return p[x];
}
void kruskal() {
    /*sort(edgs, edgs + cnt, cmp);*/
    for (int i = 0; i < cnt; i++) {
        int pa = Find(edgs[i].a);
        int pb = Find(edgs[i].b);
        if (pa != pb) {
            res += edgs[i].c;
        /*  cout << edgs[i].c << endl;*/
            p[pa] = pb;
        }
    }
}

void init() {
    for (int i = 1; i <= n * m; i++) p[i] = i;



    for (int i = 0; i < m - 1; i++) {
        for (int j = 1; j <= n; j++) {
            edgs[cnt++] = { i * n + j,i * n + j + n,1 };
        }
    }
    for (int i = 0; i < m; i++) {
    /*  cout << i << endl;
    */  for (int j = 1; j < n; j++) {

            edgs[cnt++] = { i * n + j,i * n + j + 1,2 };
        }
    }

}
int main() {
    cin >> m >> n;; //m行n列

    init();
    /*  for (int i = 0; i < cnt; i++) {
            cout << edgs[i].a << " " << edgs[i].b << " " << edgs[i].c << endl;
        }*/
    int x1, y1, x2, y2;
    while (cin >> x1 >> y1 >> x2 >> y2) {
        x1--;
        x2--;

        //  cout<<x1*n+y1<<" "<<x2*n+y2<<endl;
        p[Find(x1 * n + y1)] = Find(x2 * n + y2);
    }
    /*  for(int i=1;i<=n*m;i++) cout<<Find(i)<<" ";
        cout<<endl;*/
    kruskal();
    cout << res << endl;

}