头像

HH123_




离线:9小时前


最近来访(27)
用户头像
不成大神不改名
用户头像
zwling
用户头像
zdca
用户头像
RyanMoriarty
用户头像
孙学者
用户头像
_IFear
用户头像
Rubisco
用户头像
从未看过满天繁星
用户头像
Loneker
用户头像
xueli
用户头像
slytherin
用户头像
樊景
用户头像
于于
用户头像
xiusike1
用户头像
一只奇怪的小魔女
用户头像
soccoder
用户头像
空号AcWing
用户头像
algobot76
用户头像
Sopher
用户头像
limie


HH123_
1天前

这题挺好的,用都了并查集和环的知识
补:看了别人写的,自己的写麻烦了,用不着一个一个环的判断。
刚开始想用BFS枚举出所有的状态,不出所料超时了,但是算法应该是正确的

BFS(超时)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <map>

using namespace std;
int main() {
    int n;
    cin >> n;
    int target[n], dis[n];
    for(int i = 0; i < n; ++i) 
        cin >> target[i];
    for(int i = 0; i < n; ++i)
        cin >> dis[i];

     vector<int> init;
     for(int i = 1; i <= n; ++i) init.push_back(i);

     set<vector<int>> s;
     deque<vector<int>> q;
     q.push_back(init);
     s.insert(init);
     bool isok = false;
     while(!q.empty()) {
         auto e = q.front();
         q.pop_front();
         int i = 0;
         for(i = 0; i < n && e[i] == target[i]; ++i);
         if(i == n) {
             isok = true;
             break;
         }
         for(int i = 0; i < n; ++i) {
             if(i + dis[i] < n) {
                 vector<int> tmp(e);
                 swap(tmp[i], tmp[i + dis[i]]);
                 if(s.find(tmp) == s.end()) {
                    q.push_back(tmp);
                    s.insert(tmp);
                 }    
             }
             if(i - dis[i] >= 0) {
                 vector<int> tmp(e);
                 swap(tmp[i], tmp[i - dis[i]]);
                 if(s.find(tmp) == s.end()) {
                    q.push_back(tmp);
                    s.insert(tmp);
                 }    
             }

         }
     }
     if(isok) cout << "YES" << endl;
     else cout << "NO" << endl;
     return 0;
}

并查集

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <map>

using namespace std;
int find(int *tree, int i) {
    if(tree[i] == i) return i;
    tree[i] = find(tree, tree[i]);
    return tree[i];
}
void Union(int *tree, int u, int v) {
    int r1 = find(tree, u);
    int r2 = find(tree, v);
    if(r1 != r2) tree[r1] = r2; 
}
int main() {
    int n;
    cin >> n;
    int target[n+1], dis[n+1];
    for(int i = 1; i <= n; ++i)
        cin >> target[i];
    for(int i = 1; i <= n; ++i)
        cin >> dis[i];

    int tree[n + 1];
    for(int i = 0; i <= n; ++i) tree[i] = i;
    for(int i = 1; i <= n; ++i) {
        if(i + dis[i] <= n) Union(tree, i, i + dis[i]);
        if(i - dis[i] >= 1) Union(tree, i, i - dis[i]);
    }

    bool isok = true;
    for(int i = 1; i <= n && isok; ++i) {
        if(target[i] == 0) continue;
        int next = target[i];
        target[i] = 0;
        int r1 = find(tree, i);
        while(target[next] != 0) {
            int r = find(tree, next);
            if(r != r1) {
                isok = false;
                break;
            }
            next = target[next];
            target[next]= 0;
        }
    }
    if(isok) cout << "YES" << endl;
    else cout << "NO" << endl;
}

修改一下

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <map>

using namespace std;
int find(int *tree, int i) {
    if(tree[i] == i) return i;
    tree[i] = find(tree, tree[i]);
    return tree[i];
}
void Union(int *tree, int u, int v) {
    int r1 = find(tree, u);
    int r2 = find(tree, v);
    if(r1 != r2) tree[r1] = r2; 
}
int main() {
    int n;
    cin >> n;
    int target[n+1], dis[n+1];
    for(int i = 1; i <= n; ++i)
        cin >> target[i];
    for(int i = 1; i <= n; ++i)
        cin >> dis[i];

    int tree[n + 1];
    for(int i = 0; i <= n; ++i) tree[i] = i;
    for(int i = 1; i <= n; ++i) {
        if(i + dis[i] <= n) Union(tree, i, i + dis[i]);
        if(i - dis[i] >= 1) Union(tree, i, i - dis[i]);
    }
    bool isok = true;
    for(int i = 1; i <= n && isok; ++i) 
        if(find(tree,i) != find(tree, target[i])) {
            isok = false;
            break;
        }
    if(isok) cout << "YES" << endl;
    else cout << "NO" << endl;
}


活动打卡代码 AcWing 100. IncDec序列

HH123_
1天前
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    long long a, pos = 0, neg = 0, last;
    for(int i = 0; i < n;  ++i)  {
        cin >> a;
        if(i > 0) {
            if(a - last > 0) pos += a - last;
            else neg -= a - last;
        }
        last = a;
    }
    // cout << pos << " " << neg << endl;
    // min(pos, neg) + abs(pos - neg)
    // abs(pos - neg) + 1
    cout << min(pos, neg) + abs(pos - neg) << endl;
    cout << abs(pos - neg) + 1 << endl;
}



HH123_
2天前

原题题目:
原题目说是摧毁一个变成为R的正方形,边上不摧毁。
边长为R的正方型有 (R + 1) x (R + 1) 个点,边上不摧毁,故有 R x R点被摧毁。
023.PNG



活动打卡代码 AcWing 99. 激光炸弹

HH123_
2天前
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int sum[5005][5005];
int main() {
    int n, R;
    cin >> n >> R;

    for(int i = 0; i < n; ++i) {
        int x, y, w;
        cin >> x >> y >> w;
        sum[x][y] += w; 
    }
    for(int i = 0; i <= 5000; ++i) {
        for(int j = 0; j <= 5000; ++j) {
            if(i == 0 && j == 0) continue;
            if(i == 0) sum[0][j] += sum[0][j-1];
            else if(j == 0) sum[i][0] += sum[i-1][0];
            else sum[i][j] += sum[i][j-1] + sum[i - 1][j] - sum[i-1][j-1];
        }
    }
    long long maxvalue = 0;
    if(R > 5000) maxvalue = sum[5000][5000];
    else 
    for(int i = R - 1; i <= 5000; ++i) {
        for(int j = R - 1; j <= 5000; ++j) {
            long long t = sum[i][j];
            if(i - R >= 0) t -= sum[i - R][j];
            if(j - R>= 0) t -= sum[i][j-R];
            if(i - R >= 0 && j - R >= 0) t += sum[i - R][j - R];
            if(t > maxvalue) maxvalue = t;
        }
    }
    cout << maxvalue << endl;
}


活动打卡代码 AcWing 98. 分形之城

HH123_
2天前
#include <iostream>
#include <cmath>
using namespace std;
pair<long long, long long> calc(int n, long long m) {
    if(n == 0) return make_pair(0, 0);
    long long len = 1ll<<(n-1), cnt = 1ll<<(2*n - 2);
    pair<long long, long long> pos = calc(n-1, m%cnt);
    long long x = pos.first, y = pos.second;
    long long z = m / cnt;
    if(z == 0) return make_pair(y, x);
    if(z == 1) return make_pair(x, y + len);
    if(z == 2) return make_pair(x + len, y + len);
    if(z == 3) return make_pair(2 * len - y - 1, len -x - 1);
}
int main() {
    int T;
    cin >> T;
    while(T--) {
        long long N, A, B;
        cin >> N >> A >> B;
        auto pos1 = calc(N, A - 1);
        auto pos2 = calc(N, B - 1);
        long long x =  pos1.first - pos2.first, y = pos1.second - pos2.second;
        double ans = sqrt(x * x + y * y); 
        cout << (long long) (ans * 10 + 0.5)<< endl;
    }
}




活动打卡代码 AcWing 97. 约数之和

HH123_
4天前
#include <iostream>
using namespace std;
const int mod = 9901;
int pow(int p, int c) {
    p %= mod;
    int ans = 1;
    while(c) {
        if(c&1) ans = ans * p % mod; 
        c >>= 1;
        p = p * p % mod;
    }
    return ans;
}
int sum(int p, int k) {
    if(k == 0) return 1;
    if(k&1) return ((1 + pow(p, (k+1)>>1)) % mod * sum(p, (k-1)>>1)) % mod;
    return (((1 + pow(p, k>>1)) % mod * sum(p,(k>>1) - 1)) % mod + pow(p, k)) % mod;
}
int main() {
    int A, B;
    cin >> A >> B;
    int res = 1;
    for(int i = 2; i <= A; ++i) {
        int cnt = 0;    
        while(A%i == 0) {
            ++cnt;
            A /= i;
        }
        res = res * sum(i, cnt * B) % mod;
    }
    if(!A) res = 0;
    cout << res << endl;
    return 0;
}



活动打卡代码 AcWing 96. 奇怪的汉诺塔

HH123_
5天前
#include <iostream>
using namespace std;
int main() {
    int n = 12;
    // dp[i] = dp[i - 1] * 2 + 1
    // F[n] = min 2 * F[i] + dp[n - i] 0 <= i < n
    // detail:
    // dp[1] = 1
    // F[1] = 1
    int dp[n+1], F[n + 1];
    dp[1] = 1, F[1] = 1;
    for(int i = 2; i <= n; ++i)
        dp[i] = dp[i-1] * 2 + 1;
    for(int i = 2; i  <= n; ++i) {
        F[i] = 0x3f3f3f3f;
        for(int k = 1; k < i; ++k)
            F[i] = min(F[i], 2 * F[k] + dp[i - k]);
    }
    for(int i = 1; i <= n; ++i)
        cout << F[i] << endl;
}



HH123_
6天前

因为最近在看stevens写的《网络编程》,光看印象不深,效果不好,兴趣也不太大,想找一个相关的项目,看看书上知识到底是如何应用的,学习效果应该好一些。



活动打卡代码 AcWing 95. 费解的开关

HH123_
9天前
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int n;
vector<vector<int>> A(5, vector<int>(5, 0));
int cal() {
    int mincnt = INT_MAX;
    for(int i = 0; i < 1<<5; ++i) {
        vector<vector<int>> a = A;
        int cnt = 0;
        for(int j = 0; j < 5; ++j) 
            if(i>>j&1) {
                ++cnt;
                a[0][j] ^= 1;
                a[1][j] ^= 1;
                if(j + 1 < 5) a[0][j+1] ^= 1;
                if(j - 1 >= 0) a[0][j-1] ^= 1;
            }
        int flag = 0;
        for(int j = 1; j < 5; ++j) {
            for(int k = 0; k < 5; ++k) {
                if(a[j-1][k] == 0) {
                    ++cnt;
                    if(cnt > 6) {
                        flag = 1;
                        break;
                    }
                    a[j-1][k] ^= 1;
                    a[j][k] ^= 1;
                    if(k + 1 < 5) a[j][k+1] ^= 1;
                    if(k - 1 >= 0) a[j][k-1] ^= 1;
                    if(j + 1 < 5) a[j + 1][k] ^= 1;
                }
            }
            if(flag == 1)
                break;
        }
        if(flag == 1) continue;
        for(int k = 0; k < 5; ++k)
            if(a[4][k] == 0) {
                flag = 1;
                break;
            }
        if(flag == 0) mincnt = min(cnt, mincnt);

    }
    return mincnt == INT_MAX ? -1 : mincnt;
}
int main() {
    int n;
    cin >> n;
    while(n--) {
        string s[5];
        for(int i = 0; i < 5; ++i)
            cin >> s[i];
        for(int i = 0; i < 5; ++i)
            for(int j = 0; j < 5; ++j)
                A[i][j] = s[i][j] - '0';
        cout << cal() << endl;
    }
}



HH123_
9天前

递归实现指数型枚举

1 ~n的指数枚举
1. 选择1 + [2 ~ n]的指数枚举
2. 不选择1 + [2 ~ n]的指数枚举
终止条件 当获取[n+1 ~ n]的指数枚举时

#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> chose;
void cal(int x) {
    if(x == n + 1) {
        int flag = 0;
        for(auto &e:chose)
            if(flag == 0) {
                cout << e;
                flag = 1;
            }else cout << " " << e;
        cout << endl;
        return;
    }
    chose.push_back(x);
    cal(x + 1);
    chose.pop_back();
    cal(x + 1);
}
int main() {
    cin >> n;
    cal(1);
}

递归实现组合型枚举

组合型枚举是指数型枚举的子集,长度限制在m
只要输出长度为m的即可,剪枝
if(si + n - x + 1 < m || si > m) return;

#include <iostream>
#include <vector>
using namespace std;
int n, m;
vector<int> chose;
void cal(int x) {
    int si = chose.size();
    if(si + n - x + 1 < m || si > m) return;
    if(x == n + 1) {
        int flag = 0;
        for(auto &e:chose)
            if(flag == 0) {
                cout << e;
                flag = 1;
            }else cout << " " << e;
        cout << endl;
        return;
    }
    chose.push_back(x);
    cal(x + 1);
    chose.pop_back();
    cal(x + 1);
}
int main() {
    cin >> n>> m;
    cal(1);
}

递归实现排列型枚举

1 2 3 4 … n 的有序全排列:
1. 1 + [2 3 4 … n的有序全排列]
2. 2 + [1 2 3 … n的有序全排列]
3. ....

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
vector<int> pm;
void cal(int x) {
    if(x == n - 1) {
        int flag = 0;
        for(auto &e:pm)
            if(flag == 0) {
                cout << e;
                flag = 1;
            }else cout << " " << e;
        cout << endl;
        return;
    }
    for(int i = x; i < n; ++i) {
        swap(pm[x], pm[i]);
        cal(x + 1);
    }
    for(int i = x; i < n - 1; ++i)
        swap(pm[i], pm[i+1]);
}
int main() {
    cin >> n;
    for(int i = 1; i <= n; ++i)
        pm.push_back(i);
    cal(0);
}