个人空间 - AcWing

巷港

关注数

粉丝数

阅读量

3.5万

+关注发消息

离线：17小时前

最近来访(395)

夏夜的风

mhmh

well188

Kazimierz

shade43

啼莺修竹

不学会数据结构不改名

豆豆的小酷儿

123121s

L-China

初衷.c

upuuuuuu

一芝小鲨鱼

Pobz

黎笑涵

别偷我台灯

长夜未央

安九turbo

会写HelloWorld吗

Hello杰

活动打卡代码 AcWing 841. 字符串哈希

巷港
2天前

                #include <bits/stdc++.h>
using namespace std;
const int N = 100010,P = 13331; // P== 131或13331
typedef unsigned long long ull;// 无符号长整型，自动实现溢出取模
ull p[N],h[N]; // p数组为了初始化求p的次幂，便于求解区间和的时候直接使用
int n,m;
char s[N];
void init()
{
    p[0]=1,h[0]=0;
    for (int i=1;i<=n;i++)
    {
        p[i]=p[i-1]*P;
        h[i]=h[i-1]*P+s[i];
    }
}
ull get(int l,int r)
{
    return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
    scanf("%d%d%s",&n,&m,s+1);
    init();

    while (m--)
    {
        int l1,r1,l2,r2;
        scanf("%d%d%d%d",&l1,&l2,&r1,&r2);
        if (get(l1,l2)==get(r1,r2))
            puts("Yes");
        else puts("No");
    }

    return 0;
}

            

活动打卡代码 AcWing 839. 模拟堆

巷港
3天前

```#include [HTML_REMOVED]
using namespace std;
const int N = 100010;
int heap[N];
int ph[N],hp[N];
int n,cnt;
int idx;
void heap_swap(int u,int v)
{
swap(ph[hp[u]],ph[hp[v]]);
swap(hp[u],hp[v]);
swap(heap[u],heap[v]);
}
void down(int u)
{
int t = u;
if (u2<=cnt && heap[u2]<heap[t]) t=u2;
if (u2+1<=cnt && heap[u2+1] <heap[t]) t=u2+1;
if (t!=u)
{
heap_swap(t,u);
down(t);
}
}

void up(int u)
{
while (u/2>=1 && heap[u/2] > heap[u])
{
heap_swap(u,u/2);
u>>=1;
}
}
int main()
{
scanf(“%d”,&n);
while (n–)
{
char op[5];
scanf(“%s”,op);
if (op[0]==’I’)
{
int x;
scanf(“%d”,&x);
heap[cnt]=x;
idx;
ph[idx]=cnt;
hp[cnt]=idx;
up(cnt);
}
else if (op[0]==’P’)
{
cout<<heap[1]<<endl;
}
else if (op[0]==’D’ && op[1]==’M’)
{
heap_swap(1,cnt);
cnt–;
down(1);
}
else if (op[0]==’D’)
{
int k;
scanf(“%d”,&k);
// swap不会改变数组下标，down、up参数是下标，要调整的是交换后cnt对应的值的下标。如果用ph[k]则下标是cnt
k = ph[k];
heap_swap(k,cnt);
cnt–;
down(k);
up(k);
}
else
{
int k,x;
scanf(“%d%d”,&k,&x);
k=ph[k];
heap[k]=x;
down(k);
up(k);
}

}

return 0;

}
```

活动打卡代码 AcWing 3302. 表达式求值

巷港
10天前

                #include <bits/stdc++.h>
#include <cctype>
#include <stack>
#include <unordered_map>
using namespace std;
stack<int>num;
stack<char>op;
unordered_map<char, int>h{{'+',1},{'-',1},{'*',2},{'/',2}};

void calculator()
{
    int a = num.top();
    num.pop();
    int b = num.top();
    num.pop();
    char p = op.top();
    op.pop();

    int ans = 0;
    // 这里有坑！计算顺序是b(+-*/)a！
    if (p=='+') ans=a+b;
    if (p=='-') ans=b-a;
    if (p=='*') ans=a*b;
    if (p=='/') ans=b/a;

    num.push(ans);
}
int main()
{
    string s;
    cin>>s;
    for (int i=0;i<s.size();i++)
    {
        if (isdigit(s[i]))
        {
            int x=0,j=i;
            while (j<s.size()&&isdigit(s[j]))
            {
                x = x*10+(s[j]-'0');
                j++;
            }
            num.push(x);
            i=j-1;
        }
        else if (s[i]=='(')
            op.push(s[i]);
        else if (s[i]==')')
        {
            while (op.top()!='(')
                calculator();
            op.pop();
        }
        else
        {
            while (!op.empty()&&h[op.top()]>=h[s[i]])
                calculator();
            op.push(s[i]);
        }
    }

    while (!op.empty()) calculator();

    cout<<num.top()<<endl;
    return 0;
}

            

题解 AcWing 3693. 括号匹配

巷港
11天前

                /*
用栈的思想实现，只要栈顶元素和当前元素是匹配，就弹出栈顶元素；若当前元素和栈顶元素不匹配，则当前元素入栈，继续判断下一个。
最后只要栈为空，说明是匹配成功的，否则是失败的。
*/
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    stack<char>S;
    cin>>s;
    for (auto c:s)
    {
        if (!S.empty())
        {
            if (c==')'&&S.top()=='('||(c==']'&&S.top()=='[')||(c=='>'&&S.top()=='<')||(c=='}'&&S.top()=='{'))
                S.pop();
            else S.push(c);
        }
        else {
            S.push(c);
        }
    }
    if (S.empty()) puts("yes");
    else puts("no");

    return 0;
}

            

活动打卡代码 AcWing 828. 模拟栈

巷港
14天前

                数组模拟
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int stk[N];
int top=-1;
int n;
int main()
{
    cin>>n;
    while (n--)
    {
        string op;
        cin>>op;
        if (op=="push")
        {
            int x;
            cin>>x;
            stk[++top]=x;
        }
        else if (op=="pop")
            top--;
        else if (op=="empty")
        {
            if (top>=0) puts("NO");
            else puts("YES");
        }
        else
            cout<<stk[top]<<endl;
    }

    return 0;
}



            

活动打卡代码 AcWing 222. 青蛙的约会

巷港
14天前

扩欧的经典应用：求解线性方程的最小正整数特解。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,n,m,L;
int extcd(ll a,ll b,ll &x,ll &y)
{
    if (b==0)
    {
        x=1,y=0;
        return a;
    }

    ll x1,y1,d;
    d = extcd(b,a%b,x1,y1);
    x = y1,y = x1-a/b*y1;

    return d;
}
int main()
{
    cin>>a>>b>>m>>n>>L;
    ll x,y,d;
    d = extcd(m-n,L,x,y);
    if ((b-a)%d) puts("Impossible");
    else
    {
        x*=(b-a)/d;
        ll t = abs(L/d);
        x = (x%t+t)%t;
        cout<<x<<endl;
    }
    return 0;

}

活动打卡代码 AcWing 203. 同余方程

巷港
14天前

                扩展gcd的基本应用
求解$ax+by = gcd(a,b)$ 的特解
求解$ax + by = c$ 的特解（前提是c被gcd(a,b)整除，即一定有解）
求解$ax \equiv 1(mod b)$ 的解，即求解a的最小乘法逆元

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b;
int extcd(ll a,ll b,int &x,int &y)
{
    if (b==0)
    {
        x=1,y=0;
        return a;
    }

    int x1,y1,d;
    d = extcd(b,a%b,x1,y1);
    x = y1,y = x1-a/b*y1;

    return d;
}
int main()
{
    cin>>a>>b;
    int x,y;
    int d = extcd(a,b,x,y);
    x = (x%b+b)%b;
    cout<<x<<endl;
    return 0;
}

            

问题最大公约数的思考与疑问

巷港
18天前

给定两个数的最大公约数和最小公倍数，问：这两个数的和最大和最小可能是多少？

想问下大家的想法，我感觉只能确定和的最小值，最大值是不是不能确定啊

4 评论

不学会数据结构不改名 18天前

这两玩意加起来不是定值吗？这两个知道一个就可以求另一个了，我不知道你的问题是什么

巷港 18天前

emm就是已知两个数的GCD和LCM，然后分析这两个数的和的最大值和最小值分别可能是多少

不学会数据结构不改名 18天前回复了巷港的评论

那我只能想到基本不等式，这个最大值好像不能确定

巷港 18天前回复了不学会数据结构不改名的评论

嗯嗯我也感觉，最大值要么就暴力枚举所有合法方案求一下？

查看更多评论

活动打卡代码 AcWing 4309. 消灭老鼠（每日一题）

巷港
1个月前

本质是已知原点，求解最少用多少经过原点的直线，经过所有的点。

思路也很清晰，我们求解每个点与原点的相对向量，并使得相对向量的横纵坐标同时除以他们的最大公约数，再用set来维护和存储，那么就可以实现了唯一存储的去重功能。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int main()
{
    int n,x0,y0;
    cin>>n>>x0>>y0;
    set<PII>S;
    while (n--)
    {
        int x,y;
        cin>>x>>y;
        x-=x0,y-=y0;
        int d = gcd(x,y);
        x/=d,y/=d;
        if (x<0) x*=-1,y*=-1;
        S.insert({x,y});
    }

    cout<<S.size()<<endl;
    return 0;
}

活动打卡代码 AcWing 844. 走迷宫（算法基础课）

巷港
1个月前

bfs 板子复习

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n,m;
int dist[N][N];
int g[N][N];
typedef pair<int,int>PII;
#define x first
#define y second
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
void bfs()
{
    queue<PII>q;
    q.push({1,1});
    memset(dist,-1,sizeof dist);
    dist[1][1]=0;
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        if (t.x==n&&t.y==m) return;
        for (int i=0;i<4;i++)
        {
            int a = t.x+dx[i];
            int b = t.y+dy[i];
            if (a>0 && a<=n && b>0 && b<=m && dist[a][b]==-1 && g[a][b]==0)
            {
                dist[a][b]=dist[t.x][t.y]+1;
                q.push({a,b});
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            cin>>g[i][j];

    bfs();

    cout<<dist[n][m]<<endl;
    return 0;
}

0 评论

0 评论

0 评论

0 评论

数组模拟

0 评论

0 评论

扩展gcd的基本应用

0 评论

4 评论

0 评论

0 评论