头像

fwyize




离线:1小时前


最近来访(16)
用户头像
和以烨琛
用户头像
Verney_the_Bear
用户头像
DreamDimo
用户头像
ckcyi
用户头像
没人比我更懂暴力算法
用户头像
刘镛干净又卫生
用户头像
incra
用户头像
早起吃小面
用户头像
leaver
用户头像
wanghai673
用户头像
Enjoycode
用户头像
将军JOE
用户头像
森罗万象
用户头像
张伟豪
用户头像
AvariceZhao


fwyize
1天前

单调栈二分思路

C++ 代码

# include<iostream>
# include<cstring>
# include<algorithm>

using namespace std;
const int N = 100010;
int w[N];
int stk[N],top;
int ans[N];
int n;

int main(){
    cin >> n;
    for(int i=0;i<n;++i){
        cin >> w[i];
    }

    for(int i=n-1;i>=0;--i){
        if(!top || w[i] <= w[stk[top]]){
            ans[i] = -1;
        }else{
            // 单调栈二分 找到第一个比w[i]小的元素对应下标
            int l = 1,r = top;
            while(l < r){
                int mid = (l + r) >> 1;
                if(w[stk[mid]] < w[i]) r = mid;
                else l = mid + 1;
            }
            ans[i] = stk[l] - i - 1;
        }
        // 更新单调栈  等于时不需要更新 维护严格单调递减
        if(!top || w[i] < w[stk[top]]){
            stk[++top] = i;
        }
    }

    for(int i=0;i<n;++i) cout << ans[i] << " ";
    cout << endl;
    return 0;
}

哈希表+二分

# include<iostream>
# include<cstring>
# include<algorithm>
# include<map>

using namespace std;
const int N = 100010;
int w[N];
int stk[N],top;
map<int,int> mp;
int ans[N];
int n;

int main(){
    cin >> n;
    for(int i=0;i<n;++i){
        cin >> w[i];
    }

    // 维护一个单调递增的map (负数,索引)
    for(int i=n-1;i>=0;--i){
        // 二分查找 第一个比当前值大的元素
        auto it = mp.upper_bound(-w[i]);
        if(it == mp.end()) ans[i] = -1;
        else ans[i] = it->second - i - 1;
        if(mp.empty() || -(mp.rbegin()->first) > w[i]){
            mp.insert({-w[i],i});
        }
    }

    for(int i=0;i<n;++i) cout << ans[i] << " ";
    cout << endl;
    return 0;
}



活动打卡代码 AcWing 197. 阶乘分解

fwyize
1天前

线性筛预处理+容斥原理计数

# include<iostream>
# include<cstring>
# include<algorithm>

using namespace std;
const int N = 1000010;
bool st[N];
int primes[N],cnt;
int n;

void init(int n){
    for(int i=2;i<=n;++i){
        if(!st[i]) primes[cnt++] = i;
        for(int j=0;primes[j]<=n/i;++j){
            st[primes[j]*i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int main(){
    cin >> n;
    // 1.一步一步分解1 * 2 * 3 * ... * n
    // 2.可以考虑预处理质因数 用筛法的思想进行计数
    // 3.例如 针对质数2   2的倍数都包含质因子2  同时2的平方的倍数都包含两个质因子2
    init(n);

    for(int i=0;i<cnt;++i){
        int p = primes[i];
        int num = 0;
        int t = n;
        while(t){
            num += t / p;
            t /= p;
        }
        if(num) cout << primes[i] << " " << num << endl;
    }
    return 0;
}


活动打卡代码 AcWing 196. 质数距离

fwyize
1天前

优化枚举+区间筛思想

# include<iostream>
# include<cstring>
# include<algorithm>
# include<cmath>

using namespace std;
typedef long long ll;
const int N = 50010,M = 1000010;
bool st[N];
int primes[N],cnt;

int l,r;
bool vis[M];
ll nums[M];
int idx;

void init(int n){
    for(int i=2;i<=n;++i){
        if(!st[i]) primes[cnt++] = i;
        for(int j=0;primes[j]<=n/i;++j){
            st[primes[j]*i] = true;
            if(i % primes[j] == 0) break;  // 此时的primes[j]一定是i的最小质数  分类讨论证明即可
        }
    }
}

// 由于值域很大 并且区间大小满足条件  使用区间筛的思想
// 区间筛 先预处理出sqrt(U)的所有质数 使用埃式筛法 筛掉区间内的合数即可
int main(){
    init(50000);

    // l和r对于primes[i]来说
    while(cin >> l >> r){
        memset(vis,false,sizeof vis);
        idx = 0;

        for(int i=0;i<cnt;++i){
            ll p = primes[i];
            // 一开始这里nyx了 (l + p - 1) / p * p写成了p*(l+p-1)/p
            for (ll j = max(p * 2, (l + p - 1) / p * p); j <= r; j += p)
                vis[j - l] = true;
        }

        for(int i=0;i<=r-l;++i){
            if(!vis[i] && i + l >= 2) nums[idx++] = 1ll * i + l;
        }
        if(idx < 2){
            puts("There are no adjacent primes.");
            continue;
        }
        int maxv = 0,minv = 0;
        for(int i=0;i<idx-1;++i){
            if(nums[i+1] - nums[i] > nums[maxv+1] - nums[maxv]){
                maxv = i;
            }
            if(nums[i+1] - nums[i] < nums[minv+1] - nums[minv]){
                minv = i;
            }
        }
        printf("%lld,%lld are closest, %lld,%lld are most distant.\n",nums[minv],nums[minv+1],nums[maxv],nums[maxv+1]);
    }
    return 0;
}



fwyize
4天前

找规律+线性筛法

# include<iostream>
# include<cstring>
# include<algorithm>

using namespace std;
const int N = 100010;
bool st[N];
int primes[N],cnt;
int n;

int main(){
    cin >> n;
    // 2~n+1范围的数  本身是质数 质数的倍数累加k
    if(n <= 2){
        cout << "1" << endl;
        for(int i=1;i<=n;++i) cout << "1" << " ";
        cout << endl;
    }else{
        cout << "2" << endl;
        n ++;
        for(int i=2;i<=n;++i){
            if(!st[i]){
                primes[cnt++] = i;
                cout << "2" << " ";
            }else{
                cout << "1" << " ";
            }
            for(int j=0;primes[j]<=n/i;++j){
                st[primes[j]*i] = true;
                if(i % primes[j] == 0) break;  // 此时的primes[j]一定是i的最小质数  分类讨论证明即可
            }
        }
        cout << endl;
    }
    return 0;
}


活动打卡代码 AcWing 1292. 哥德巴赫猜想

fwyize
4天前

裸的线性筛+枚举

# include<iostream>
# include<cstring>
# include<algorithm>

using namespace std;
int n;
const int N = 1000010;
bool st[N];
int primes[N],cnt;

void get_prime(int n){
    for(int i=2;i<=n;++i){
        if(!st[i]) primes[cnt++] = i;
        for(int j=0;primes[j]<=n/i;++j){
            st[primes[j]*i] = true;
            if(i % primes[j] == 0) break;  // 此时的primes[j]一定是i的最小质数  分类讨论证明即可
        }
    }
}

int main(){
    get_prime(1e6);
    while(cin >> n,n){
        for(int i=1;i<cnt;++i){
            int a = primes[i];
            int b = n - a;
            if(!st[b]){
                printf("%d = %d + %d\n",n,a,b);
                break;
            }
        }
    }
    return 0;
}



fwyize
4天前

思路

主要思路就是断环成链优化一维暴力枚举的时间复杂度,之后就是一个典型的区间dp问题.
注意赋初值以及负数对于乘法的影响即可.细节见代码:

C++ 代码

# include<iostream>
# include<algorithm>
# include<cstring>
typedef long long ll;

using namespace std;
const int N = 110;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int a[N],b[N]; // a存储数字  b存储运算符其中1表示加法 2表示乘法
ll f[N][N][2]; // 维护区间的最大值和最小值
int n;

int main(){
    cin >> n;
    // 预处理输入
    char ops[2];
    for(int i=1;i<=n<<1;++i){
        if(i & 1){
            cin >> ops;
            if(ops[0] == 't'){
                b[i / 2] = 1;
                b[i / 2 + n] = 1;
            }else{
                b[i / 2] = 2;
                b[i / 2 + n] = 2;
            }
        }else{
            cin >> a[i / 2];
            a[i / 2 + n] = a[i / 2];
        }
    }

    // 这里需要分别赋初值  因为可能存在负数
    for(int i=1;i<=2*n;++i){
        for(int j=1;j<=2*n;++j){
            f[i][j][0] = -INF;
            f[i][j][1] = INF;
        }
    }
    // 赋初值
    for(int i=1;i<=2*n;++i){
        f[i][i][0] = f[i][i][1] = a[i];
    }

    // 区间dp递推
    for(int len=2;len<=n;++len){
        for(int i=1;i<=2*n-len+1;++i){
            int j = i + len - 1;
            for(int k=i;k<j;++k){
                // 加法操作负数不影响最大最小值判定
                if(b[k] == 1){
                    f[i][j][0] = max(f[i][j][0],f[i][k][0]+f[k+1][j][0]);
                    f[i][j][1] = min(f[i][j][1],f[i][k][1]+f[k+1][j][1]);
                }else{
                    // 乘法运算的最大值可能是两个最大正数的乘积或者两个最小负数的乘积
                    // 最小值可能是最大正数*最小负数的乘积/最小正数的乘积
                    f[i][j][0] = max(f[i][j][0],max(f[i][k][0]*f[k+1][j][0],f[i][k][1]*f[k+1][j][1]));
                    f[i][j][1] = min(f[i][j][1],min({f[i][k][0]*f[k+1][j][1],f[i][k][1]*f[k+1][j][1],f[i][k][1]*f[k+1][j][0]}));
                }
            }
        }
    }

    ll res = -INF;
    vector<int> ans;
    for(int i=1;i<=n;++i){
        if(f[i][i+n-1][0] > res){
            res = f[i][i+n-1][0];
            ans.clear();
            ans.push_back(i);
        }else if(f[i][i+n-1][0] == res){
            ans.push_back(i);
        }
    }

    cout << res << endl;
    for(auto& v:ans) cout << v << " ";
    cout << endl;
    return 0;
}




活动打卡代码 AcWing 1185. 单词游戏

fwyize
7天前

无向图欧拉路径+并查集判断连通性

# include<iostream>
# include<cstring>
# include<algorithm>

using namespace std;
const int N = 100010;
int t;
int indeg[N],outdeg[N],p[N];
bool st[N];
int n;

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}


void init(){
    memset(indeg,0,sizeof indeg);
    memset(outdeg,0,sizeof outdeg);
    memset(st,false,sizeof st);
    for(int i=0;i<26;++i) p[i] = i;
}

int main(){
    cin >> t;

    char str[1010];
    while(t--){
        init();
        cin >> n;
        for(int i=0;i<n;++i){
            cin >> str;
            int len = strlen(str);
            int a = str[0] - 'a', b = str[len - 1] - 'a';
            st[a] = st[b] = true;
            outdeg[a] ++, indeg[b] ++ ;
            p[find(a)] = find(b);
        }

        // 判断入度和出度关系
        int start = 0,end = 0;
        bool ok = true;
        for(int i=0;i<26;++i){
            if(indeg[i] == outdeg[i] + 1){
                end ++;
            }else if(outdeg[i] == indeg[i] + 1){
                start ++;
            }else if(indeg[i] != outdeg[i]){
                ok = false;
                break;
            }
        }
        if(!ok || !(!start && !end || start == 1 && end == 1)){
            printf("The door cannot be opened.\n");
            continue;
        }
        // 判断图连通性
        int t = -1;
        for(int i=0;i<26;++i){
            if(st[i]){
                if(t == -1){
                    t = find(i);
                }else{
                    if(t != find(i)){
                        ok = false;
                        break;
                    }
                }
            }
        }

        if(!ok) printf("The door cannot be opened.\n");
        else{
            printf("Ordering is possible.\n");
        }
    } 

    return 0;
}


活动打卡代码 AcWing 1184. 欧拉回路

fwyize
7天前

欧拉回路

# include<cstring>
# include<algorithm>
# include<iostream>

using namespace std;
const int N = 100010,M = 400010;
int h[N],e[M],ne[M],idx;
bool used[M];         // 标记边是否被使用
int ans[M / 2],cnt;   // 存储逆序欧拉回路
int n,m;
int type;
int indeg[N],outdeg[N];

void add(int a,int b){
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;    
}

void dfs(int u){
    // 这里加引用使得删除的边应用于全局
    for(int &i=h[u];i!=-1;){
        if(used[i]){
            i = ne[i];
            continue;
        }
        used[i] = true;
        // 无向图 将编号i的边和编号i^1的边都置为访问过
        if(type == 1) used[i ^ 1] = true;

        int t;

        if(type == 1)
        {
            t = i / 2 + 1;        // 边的编号下标从1开始
            if (i & 1) t = -t;    // 如果i是偶数说明应该输出正数 否则是对称边输出负数
        }
        else t = i + 1;

        int j = e[i];
        i = ne[i];
        dfs(j);
        ans[++cnt] = t;
    }
}

int main(){
    cin >> type;
    cin >> n >> m;
    memset(h, -1, sizeof h);

    for(int i=0;i<m;++i){
        int a,b;cin >> a >> b;
        add(a, b);
        if(type == 1) add(b,a);
        indeg[b] ++,outdeg[a] ++;
    }

    if(type == 1){
        for(int i = 1;i <= n;i ++){
            if((indeg[i] + outdeg[i]) & 1){
                printf("NO\n");
                return 0;
            }
        }
    }else{
        for(int i = 1;i <= n;i ++){
            if(indeg[i] != outdeg[i]){
                printf("NO\n");
                return 0;
            }
        }
    }

    // 从某一个起点开始
    for(int i=1;i<=n;++i){
        if(h[i] != -1){
            dfs(i);
            break;
        }
    }

    if(cnt < m){
        printf("NO\n");
        return 0;
    }

    cout << "YES" << endl;
    for(int i=cnt;i;i --) printf("%d ", ans[i]);
    cout << endl;
    return 0;
}



活动打卡代码 AcWing 1124. 骑马修栅栏

fwyize
7天前

邻接矩阵+欧拉回路+字典序最小路径

# include<iostream>
# include<cstring>
# include<algorithm>

using namespace std;
const int N = 510;
int n = 500,m;
int g[N][N];
int ans[1100],cnt;
int deg[N];

void dfs(int u){
    for(int i=1;i<=n;++i){
        if(g[u][i]){
            g[u][i] --,g[i][u] --;
            dfs(i);
        }
    }
    ans[++cnt] = u;
}

int main(){
    int m;
    cin >> m;
    for(int i=0;i<m;++i){
        int a,b;
        cin >> a >> b;
        g[a][b] ++,g[b][a] ++;
        deg[a] ++,deg[b] ++;
    }
    int start = 1;
    while(!deg[start]) start ++;
    for(int i=1;i<=n;++i){
        if(deg[i] & 1){
            start = i;
            break;
        }
    }

    dfs(start);

    // 输出欧拉路径
    for(int i=cnt;i>=1;--i) cout << ans[i] << endl;
    return 0;
}


活动打卡代码 AcWing 1123. 铲雪车

fwyize
7天前

欧拉回路问题

# include<iostream>
# include<cstring>
# include<algorithm>
# include<cmath>

using namespace std;

int main(){
    double x1,y1,x2,y2;
    cin >> x1 >> y1;

    double sum = 0.0;
    while(cin >> x1 >> y1 >> x2 >> y2){
        double x = x1 - x2;
        double y = y1 - y2;
        sum += sqrt(x * x + y * y) * 2;    // 无向边视为两条有向边
    }

    int minutes = round(sum / 1000 / 20 * 60);  // 四舍五入计算分钟数
    int hours = minutes / 60;
    minutes %= 60;

    printf("%d:%02d\n",hours,minutes);
    return 0;
}