头像

FIGHT




离线:1天前


最近来访(1)
用户头像
棒子面白周

活动打卡代码 AcWing 128. 编辑器

FIGHT
1天前
//对顶栈,头一次见
#include<iostream>

using namespace std;

const int N=1e6+10;
int stka[N],stkb[N];
int topa=0,topb=0;
int sum[N],f[N];
int n;

void update(int x)
{
    sum[topa]=sum[topa-1]+x;
    f[topa]=max(sum[topa],f[topa-1]);
}

int main()
{
    cin>>n;
    f[0]=-0x3f3f3f3f;
    while(n--)
    {
        string s;cin>>s;
        int x;
        if(s=="I"){
            cin>>x;
            stka[++topa]=x;
            update(x);
        }
        else if(s=="Q"){
            cin>>x;
            cout<<f[x]<<endl;
        }
        else if(s=="L"){
            if(topa<1);
            else{
                x=stka[topa];
                stkb[++topb]=x;
                topa--;

            }

        }
        else if(s=="R"){
            if(topb<1);
            else{
                x=stkb[topb];
                stka[++topa]=x;
                topb--;

                update(x);    
            }

        }
        else if(s=="D"){
            if(!topa);
            else
                topa--;
        }
    }
    return 0;
}



FIGHT
1天前
class MinStack {
public:
    /** initialize your data structure here. */
    int hh,tt;
    int stk_a[1000],stk_b[1000];
    MinStack() {
        hh=0,tt=-1;
    }

    void push(int x) {
        stk_a[++tt]=x;
        if(tt-1>=0)
            stk_b[tt]=min(x,stk_b[tt-1]);
        else
            stk_b[tt]=x;
    }

    void pop() {
        tt--;
    }

    int top() {
        return stk_a[tt];
    }

    int getMin() {
        return stk_b[tt];
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */


活动打卡代码 AcWing 141. 周期

FIGHT
2天前
#include<iostream>
#include<cstring>

using namespace std;

const int N=1e6+10;

char a[N];
int n,cnt;
int ne[N];
int main()
{
    while(cin>>n,n)
    {
        printf("Test case #%d\n",++cnt);
        cin>>a+1;
        for(int i=2,j=0;i<=n;i++){
            while(j&&a[j+1]!=a[i])j=ne[j];
            if(a[j+1]==a[i])j++;
            ne[i]=j;
        }

        for(int i=2;i<=n;i++)
        {
            int t=i-ne[i];//最小循环元长度;
            if(i!=t&&i%t==0)
            {
                cout<<i<<" "<<i/t<<endl;
            }
        }
        puts("");
    }
}


活动打卡代码 AcWing 274. 移动服务

FIGHT
26天前
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#define pb push_back 
#define in insert
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){for(auto c:v)os<<c<<" ";return os;}

typedef pair<int,int>PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=210,M=1e9+7;
ll n,m,_;
int c[N][N],q[1100];

int f[1100][N][N];

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>c[i][j];

    for(int i=1;i<=m;i++)
        cin>>q[i];

    mem(f,0x3f);

    f[0][1][2]=0;

    q[0]=3;

    for(int i=0;i<m;i++)
    {
        for(int x=1;x<=n;x++)
        {
            for(int y=1;y<=n;y++)
            {
                int z=q[i];
                if(x==y||x==z||z==y)continue;
                // puts("123");
                f[i+1][x][y]=min(f[i+1][x][y],f[i][x][y]+c[z][q[i+1]]);
                f[i+1][z][y]=min(f[i+1][z][y],f[i][x][y]+c[x][q[i+1]]); 
                f[i+1][x][z]=min(f[i+1][x][z],f[i][x][y]+c[y][q[i+1]]);     
            }
        }

    }

    int res=0x3f3f3f3f;
    for(int x=1;x<=n;x++)
        for(int y=1;y<=n;y++)   
        {
            int z=q[m];
            if(x==y||x==z||z==y)continue;
            res=min(res,f[m][x][y]);
        }


    cout<<res<<endl;
}

int main()
{
    solve();
    return 0;
}



活动打卡代码 AcWing 2714. 左偏树

FIGHT
27天前
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=2e5+10;

int val[N],dis[N],l[N],r[N],idx;
int fa[N],n;

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

bool cmp(int x,int y)//idx之间的比较
{
    if(val[x]!=val[y])return val[x]<val[y];
    return x<y;
}

int merge(int x,int y)
{
    if(!x||!y)return x+y;
    if(cmp(y,x))swap(x,y);
    r[x] = merge(r[x],y);
    if(dis[l[x]]<dis[r[x]])
        swap(l[x],r[x]);
    dis[x]=dis[r[x]]+1;
    return x;
}

int main()
{
    cin>>n;
    val[0]=2e9;//防止第4步0作为根节点
    while(n--)
    {
        int a,x,y;cin>>a>>x;
        if(a==1)
        {
            val[++idx]=x;
            fa[idx]=idx;
        }
        else if(a==2)
        {
            cin>>y;
            int pa=find(x),pb=find(y);
            if(pa!=pb)
            {
                if(cmp(pb,pa))swap(pa,pb);  
                fa[pb]=pa;
                merge(pa,pb);
            }

        }
        else if(a==3)
        {
            cout<<val[find(x)]<<endl; 
        }
        else
        {
            x=find(x);
            if(cmp(r[x],l[x]))swap(l[x],r[x]);//r[x],l[x]可能为空,
            // 此时l[x]作为新的根节点
            fa[x]=l[x],fa[l[x]]=l[x];
            merge(l[x],r[x]);

        }
    }
    return 0;
}


活动打卡代码 AcWing 273. 分级

FIGHT
28天前
关于B中任意元素一定是A中原有元素的证明
对于Ai'~Ai+1'这段长方形中所有的点,对于每个Bi~Bj,统计X、Y
如果Ai小于Ai'那么Y++,否则X++,如果X==Y,不移动,X>Y,下移,X<Y上移动,直到所有的点均在线上为止.
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#define pb push_back 
#define in insert
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){for(auto c:v)os<<c<<" ";return os;}

typedef pair<int,int>PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=2100,M=1e9+7;
ll n,m,_;

int a[N],b[N];
int f[N][N];
/*
f[i][j]已经给a[1~i]分配了元素,且最后一个元素是a[j]的所有方案的集合

划分a[i-1]分配的是a[1],a[2]...a[j-1];

f[i][j]=min(f[i-1][1],f[i-1][2],f[i-1][3])+abs(a[i]-b[j])
*/
int res=0x3f3f3f3f;
void solve()
{
    cin>>n;
    fo(i,1,n)cin>>a[i],b[i]=a[i];

    sort(b+1,b+n+1);

    for(int i=1;i<=n;i++)
    {
        int minn=0x3f3f3f3f;
        for(int j=1;j<=n;j++)
        {
            minn=min(minn,f[i-1][j]);
            f[i][j]=minn+abs(a[i]-b[j]);
        }
    }


    for(int i=1;i<=n;i++)
    {
        res=min(res,f[n][i]);
    }
}
int main()
{
    solve();
    reverse(a+1,a+n+1);
    solve();
    cout<<res<<endl;
    return 0;
}




FIGHT
29天前
/*
最长严格上升子序列

f[i]表示以a[i]结尾的所有严格上升的子序列的最长长度

最长公共子序列
f[i][j] 表示以a[i]和b[j]结尾的所有公共子序列的最大长度

f[i][j]= 
    if(a[i]==b[j])  f[i][j]=f[i-1][j-1]+1;
    else 
        f[i][j]=max(f[i-1][j],f[i][j-1]);


LCIS
f[i][j]表示以a[i]和b[j]结尾的所有单调上升公共子序列的集合中的最大长度

不对!

f[i][j]表示从a[1~i]和b[1~j]中以b[j]结尾的所有单调上升公共子序列的集合

if(a[i]==b[j])
     f[i][j]=f[i-1][j];
else
    根据last属性,划分b中倒数第二个元素的位置k
    k从(1~j-1)

    因为a[i]==b[j],所以 if(b[k]<a[i])
        f[i][j]=max(f[i][j],f[i-1][k]+1);
    定义 maxn=max(maxn,f[i-1][k]+1)

    maxn是



*/
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=3010;

int a[N],b[N],n;
int f[N][N];
int main()
{
    cin>>n; 
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];


    for(int i=1;i<=n;i++)
    {
        int maxn=1;
        for(int j=1;j<=n;j++)
        {
            f[i][j]=f[i-1][j];

            if(a[i]>b[j])//NB的优化,前缀最大值!
                maxn=max(maxn,f[i-1][j]+1);

            if(a[i]==b[j])
            {
                f[i][j]=max(f[i][j],maxn);
            }

        }
    }

    int res=0;
    for(int i=1;i<=n;i++)
        res=max(res,f[n][i]);
    cout<<res;

    return 0;
}




FIGHT
29天前
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#define pb push_back 
#define in insert
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){for(auto c:v)os<<c<<" ";return os;}

typedef pair<int,int>PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=2e5+10,M=31;
ll n,m,_;

ll f[M][M][M][M][M];

void solve()
{
    int k;

    while(cin>>k,k!=0)
    {
        int a[5]={0};
        for(int i=0;i<k;i++)
            cin>>a[i];

        mem(f,0);

        //初始化边界情况,而不是初始化内部情况
        f[0][0][0][0][0]=1;

//      for(int i=0;i<=a[0];i++)
//          f[i][0][0][0][0]=1;


        for(int i=0;i<=a[0];i++)
        {
            for(int j=0;j<=min(i,a[1]);j++)
            {

                for(int k=0;k<=min(j,a[2]);k++)
                {

                    for(int l=0;l<=min(k,a[3]);l++)
                    {

                        for(int m=0;m<=min(l,a[4]);m++)
                        {           
                            if(i&&i-1>=j)
                                f[i][j][k][l][m]+=f[i-1][j][k][l][m];
                            if(j&&j-1>=k)
                                f[i][j][k][l][m]+=f[i][j-1][k][l][m];
                            if(k&&k-1>=l)
                                f[i][j][k][l][m]+=f[i][j][k-1][l][m];
                            if(l&&l-1>=m)
                                f[i][j][k][l][m]+=f[i][j][k][l-1][m];   
                            if(m)
                                f[i][j][k][l][m]+=f[i][j][k][l][m-1];
                        }
                    }
                }
            }
        }

        cout<<f[a[0]][a[1]][a[2]][a[3]][a[4]]<<endl;
    }       
}

int main()
{
    solve();
    return 0;
}



活动打卡代码 AcWing 287. 积蓄程度

FIGHT
1个月前
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define pb push_back 
#define in insert
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){for(auto c:v)os<<c<<" ";return os;}

typedef pair<int,int>PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=2e5+10,M=1e9+7;
ll n,m,_;

int h[N],e[N*2],ne[N*2],idx,c[N*2];

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

int dp[N];
int f[N];
int deg[N];
int ans;
void dfs(int u,int fa)
{
    dp[u]=0;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j==fa)continue;

        dfs(j,u);

        if(deg[j]==1)
            dp[u]+=c[i];
        else
            dp[u]+=min(dp[j],c[i]);
    }
}

void dfs_up(int u,int fa)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j==fa)continue;

        if(deg[j]==1)
            f[j]=dp[j]+c[i];
        else
        f[j]=dp[j]+min(c[i],f[u]-min(dp[j],c[i]));

        dfs_up(j,u);//又犯了同样的错误了
    }
}

void solve()
{
    mem(h,-1);
    idx=0;
    ans=0;
    mem(deg,0);
    cin>>n;
    fo(i,0,n-2){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w),add(v,u,w);
        deg[u]++,deg[v]++;
    }   

    int root=1;
    while(root<=n&&deg[root]==1)root++;

    if(root>n)//只有远点和汇点,也就是所有点的度数全是1
    {
        cout<<c[0]<<endl;
        return ;
    }
    dfs(root,-1);
    f[root]=dp[root];
    dfs_up(root,-1);

    for(int i=1;i<=n;i++)
    {
       // cout<<i<<" "<<dp[i]<<" "<<f[i]<<endl;
        ans=max(ans,f[i]);
    }

    cout<<ans<<endl;
}

int main()
{
    cin>>_;
    while(_--)
    {
        solve();
    }
    return 0;
}



活动打卡代码 AcWing 1077. 皇宫看守

FIGHT
1个月前
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define pb push_back 
#define in insert
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){for(auto c:v)os<<c<<" ";return os;}

typedef pair<int,int>PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=1510,M=1e9+7;
ll n,m,_;
int h[N],e[N*2],ne[N*2],idx,w[N*2];

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

bool st[N];

int dp[N][3];
/*
dp[i][0]表示i点没有放置守卫,i被其父节点看到的所有摆放情况的最小花费
dp[i][1]表示i点没有放置守卫,i至少被其某个子节点看到的。。。的最小花费
dp[i][2]表示在i点放置守卫的。。。最小花费 

u节点为i的子节点

dp[i][0]+=min(dp[u][2],dp[u][1]);
dp[i][2]+=min(dp[u][2],dp[u][1],dp[u][0]);
dp[i][1]+=枚举是哪一个子节点看到了i节点,
*/

void dfs(int u)
{
    dp[u][2]=w[u];
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        dfs(j);
        dp[u][0]+=min(dp[j][1],dp[j][2]);
        dp[u][2]+=min(dp[j][0],min(dp[j][1],dp[j][2]));
    }
    dp[u][1]=0x3f3f3f3f;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        dp[u][1]=min(dp[u][1],dp[j][2]+dp[u][0]-min(dp[j][1],dp[j][2]));
    }
}
void solve()
{
    cin>>n;
    mem(h,-1);
    for(int i=1;i<=n;i++)
    {
        int id,W,num;
        cin>>id>>W>>num;
        w[id]=W;
        while(num--)
        {
            int v;scanf("%d",&v);
            add(id,v);
            st[v]=1;
        }
    }
    int root=1;
    while(st[root])root++;
    dfs(root);
    cout<<min(dp[root][1],dp[root][2])<<endl;

}

int main()
{
    solve();
    return 0;
}