头像

lmzOuO

永远不要失去敢于质疑的勇气




离线:9分钟前


最近来访(1143)
用户头像
bre
用户头像
皮蛋solo粥捏
用户头像
MyloXyloto
用户头像
renaissance.
用户头像
明天见@
用户头像
牛神2
用户头像
风绝
用户头像
hzh..
用户头像
我看青山多妩媚
用户头像
Ponziptr
用户头像
新年快乐_3
用户头像
烛之武
用户头像
violet_garden
用户头像
bwd
用户头像
yrf_zwh
用户头像
无名小子
用户头像
llllllllll
用户头像
sailei
用户头像
种花家的兔兔
用户头像
-浪漫主义狗-

分享 st板子

lmzOuO
2天前
const int N=2e5+10,M=log2(N);
int a[N];
int f[2][N][M];
void st()
{
    for(int j=0;(1<<j)<=n;j++)
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
            if(!j)f[0][i][j]=f[1][i][j]=a[i];
            else 
            {
                f[0][i][j]=max(f[0][i][j-1],f[0][i+(1<<(j-1))][j-1]);
                f[1][i][j]=min(f[1][i][j-1],f[1][i+(1<<(j-1))][j-1]);
            }
    }
}
int query(int l,int r,bool s)
{
    int len=r-l+1;
    int q=log2(len);
    if(s)return max(f[0][l][q],f[0][r-((1<<q)-1)][q]);
    else return min(f[1][l][q],f[1][r-((1<<q)-1)][q]);
}



lmzOuO
8天前

分层图

/*
    悲观看待成功,乐观看待失败。 
    author:leimingze 
*/
#include<bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
const int base=131;
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define x first
#define y second
#define int long long
#define lb long double
#define pb push_back
#define endl '\n'//交互题删掉此 
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){return (a%mod+mod)%mod;}
int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){return qmi(a,mod-2,mod);}
int lcm(int a,int b){return a*b/__gcd(a,b);}
const int N=110010,M=2500010;
int n,m,k;
int st,ed;
bool vis[N];
int dist[N];
int h[N],e[M],ne[M],w[M],idx;
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void dijkstra(int st)
{
    memset(dist,0x3f,sizeof dist);
    priority_queue<PII,vector<PII>,greater<PII>>heap;
    heap.push({0,st});
    dist[st]=0;
    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();
        if(vis[t.y])continue;
        vis[t.y]=true;
        for(int i=h[t.y];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t.y]+w[i])
            {
                dist[j]=dist[t.y]+w[i];
                heap.push({dist[j],j});
            }
        }
    }
}
void solve()
{
    memset(h,-1,sizeof h);
    cin>>n>>m>>k;
    cin>>st>>ed;
    rep(i,1,m)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
        rep(j,1,k)
        {
            add(a+(j-1)*n,b+j*n,0),add(b+(j-1)*n,a+j*n,0);
            add(a+j*n,b+j*n,c),add(b+j*n,a+j*n,c);
        }
    }
    rep(i,1,k)
        add(ed+(i-1)*n,ed+i*n,0);
    dijkstra(st);
    cout<<dist[ed+k*n]<<endl;
}
signed main()
{
    io;
    int _;_=1;
    //cin>>_;
    while(_--)solve();
}



lmzOuO
9天前
#define x first
#define y second
class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        vector<vector<int>>v(26);
        for(int i=0;i<s.size();i++)
            v[s[i]-'a'].push_back(i);
        int res=0;
        for(int i=0;i<words.size();i++)
        {
            int idx=-1;
            bool f=false;
            for(int j=0;j<words[i].size();j++)
            {
                int l=0,r=v[words[i][j]-'a'].size();
                while(l<r)
                {
                    int mid=l+r>>1;
                    if(v[words[i][j]-'a'][mid]>idx)r=mid;
                    else l=mid+1;
                }
                if(r==v[words[i][j]-'a'].size())
                {
                    f=true;
                    break;
                }
               idx=v[words[i][j]-'a'][r];
            }
            if(!f)res++;
        }
        return res;
    }
};



lmzOuO
10天前
class Solution {
public:
    int maxPalindromes(string s, int k) {
        int n=s.size();
        vector<vector<bool>>g(n+1,vector<bool>(n+1));
        for(int len=1;len<=n;len++)
        {
            for(int i=1;i+len-1<=n;i++)
            {
                int j=i+len-1;
                if(s[i-1]==s[j-1]&&(len<=2||g[i+1][j-1]))
                    g[i][j]=true;
            }
        }
        vector<int>f(n+1);
        for(int i=1;i<=n;i++)
        {
            f[i]=f[i-1];
            for(int j=i-k;j>=0;j--)
            {
                if(g[j+1][i])
                    f[i]=max(f[i],f[j]+1);
            }
        }
        return f[n];
    }
};



lmzOuO
11天前
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
#define x first
#define y second
typedef pair<int,int>PII; 
class Solution {
public:
    static const int N=1e5+10;
    int f[N],cnt[N];
    int find(int x)
    {
        if(x!=f[x])f[x]=find(f[x]);
        return f[x];
    }
    void unite(int x,int y)
    {
        int a=find(x),b=find(y);
        if(a!=b)
        {
            cnt[a]+=cnt[b];
            f[b]=a;
        }
    }
    int bfs(TreeNode *root)
    {
        queue<TreeNode*>q;
        q.push(root);
        int res=0;
        while(q.size())
        {
            int sz=q.size();
            vector<int>v;
            for(int i=0;i<sz;i++)
            {
                auto t=q.front();
                q.pop();
                v.push_back(t->val);
                if(t->left)q.push(t->left);
                if(t->right)q.push(t->right);
            }
            vector<PII>p;
            for(auto x:v)p.push_back({0,x});
            sort(v.begin(),v.end());
            for(int i=0;i<v.size();i++)p[i].x=v[i];
            for(auto x:p)unite(x.x,x.y);
            for(auto x:p)
                if(f[x.x]==x.x)
                    res+=cnt[x.x]-1;
        }
        return res;
    }
    int minimumOperations(TreeNode* root) {
        for(int i=0;i<N;i++)f[i]=i,cnt[i]=1;
        return bfs(root);
    }
};



lmzOuO
11天前
class Solution {
public:
    int subarrayLCM(vector<int>& nums, int k) {
        int n=nums.size();
        int res=0;
        for(int i=0;i<n;i++)
        {
            int x=nums[i];
            for(int j=i;j<n;j++)
            {
                x=x*nums[j]/gcd(x,nums[j]);
                if(x==k)res++;
                else if(x>k)break;
            }
        }
        return res;
    }
};


活动打卡代码 LeetCode 2469. 温度转换

lmzOuO
11天前
class Solution {
public:
    vector<double> convertTemperature(double celsius) {
        return {celsius+273.15,celsius*1.8+32};
    }
};



lmzOuO
11天前
class Solution {
public:
    vector<int>p;
    vector<string> splitMessage(string message, int limit) {
        if(limit<=5)return{};
        int n=message.size();
        p.resize(n+1);
        for(int i=1;i<10&&i<=n;i++)p[i]=p[i-1]+1;
        for(int i=10;i<100&&i<=n;i++)p[i]=p[i-1]+2;
        for(int i=100;i<1000&&i<=n;i++)p[i]=p[i-1]+3;
        for(int i=1000;i<10000&&i<=n;i++)p[i]=p[i-1]+4;
        vector<string>res;
        for(int i=1;i<=n;i++)//枚举段数
        {
            string s2=to_string(i);
            if(3+s2.size()*2>limit)break;
            int sz=message.size()+i*(3+s2.size())+p[i];
            if(limit*(i-1)<sz&&limit*i>=sz)
            {
                int scnt=limit-(3+s2.size());//a+message的长度
                for(int j=1,idx=0;j<=i;j++)
                {
                    string s1=to_string(j);
                    int t=scnt-s1.size();//message的长度
                    string s;
                    s=message.substr(idx,t)+'<'+s1+'/'+s2+'>';
                    res.push_back(s);
                    idx+=t;
                }
                break;
            }
        }
        return res;
    }
};



lmzOuO
11天前
#define x first
#define y second
typedef pair<int,int>PII;
class Solution {
public:
    bool splitArraySameAverage(vector<int>& nums) {
        int n=nums.size();
        int s=0;
        for(int i=0;i<n;i++)
            s+=nums[i];
        int m=n/2;
        set<PII>st;
        for(int i=0;i<(1<<m);i++)
        {
            int sum=0,cnt=0;
            for(int j=0;j<m;j++)
            {
                if(i&(1<<j))
                {
                    sum+=nums[j];
                    cnt++;
                }
            }
            st.insert({sum,cnt});
        }
        for(int i=0;i<(1<<(n-m));i++)
        {
            int sum=0,cnt=0;
            for(int j=m;j<n;j++)
            {
                if(i&(1<<(j-m)))
                {
                    sum+=nums[j];
                    cnt++;
                }
            }
            for(int c=max(1,cnt);c<n;c++)
            {
                if(c*s%n==0)
                {
                    int t=c*s/n;
                    PII left={t-sum,c-cnt};
                    if(st.find(left)!=st.end())return true;
                }
            }
        }
        return false;
    }
};



lmzOuO
12天前
class Solution {
public:
    static const int N=1e5+10;
    int h[N],e[N<<1],ne[N<<1],idx;
    int outd[N];
    int w[N];
    vector<int>p;
    map<int,int>mp;
    int maxv=-1e5;
    int n;
    void add(int a,int b)
    {
        e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    }
    void dfs(int u,int fa,vector<int>&v)
    {
        v.push_back(u);
        if(u==0)
        {
            p=v;
            return;
        }
        for(int i=h[u];~i;i=ne[i])
        {
            int j=e[i];
            if(j==fa)continue;
            dfs(j,u,v);
        }
        v.pop_back();
    }
    void dfs(int u,int fa,int sum,int cnt)
    {
        int t=0;
        if(cnt<p.size()&&u==p[cnt])t=w[u]/2;//同时
        else if(!mp[u]||cnt>=p.size())t=w[u];
        sum+=t;
        if(cnt<p.size())mp[p[cnt]]++; 
        if(outd[u]<2&&u)maxv=max(maxv,sum);
        for(int i=h[u];~i;i=ne[i])
        {
            int j=e[i];
            if(j==fa)continue;
            dfs(j,u,sum,cnt+1);
        }
        if(cnt<p.size())mp[p[cnt]]--;
        sum-=t;
    }
    int mostProfitablePath(vector<vector<int>>& edges, int bob, vector<int>& amount) {
        memset(h,-1,sizeof h);
        n=edges.size();
        for(int i=0;i<edges.size();i++)
        {
            int a=edges[i][0],b=edges[i][1];
            add(a,b),add(b,a);
            outd[a]++,outd[b]++;
        }
        for(int i=0;i<amount.size();i++)w[i]=amount[i];
        vector<int>v;
        dfs(bob,-1,v);
        for(auto x:p)cout<<x<<' ';
        dfs(0,-1,0,0);
        return maxv;
    }
};