L2-1

STL模拟

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define nep(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
typedef long long ll;
void sc(int &x){scanf("%d",&x);}
void sc(int &x,int &y){scanf("%d%d",&x,&y);}
void sc(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}
void sc(ll &x){scanf("%lld",&x);}
void sc(ll &x,ll &y){scanf("%lld%lld",&x,&y);}
void sc(ll &x,ll &y,ll &z){scanf("%lld%lld%lld",&x,&y,&z);}
void out(int x){printf("%d\n",x);}
void out(int x,int y){printf("%d %d\n",x,y);}
const int N=105;
int n,m,smx;
queue<char>q[N];
stack<char>s;
string ans="";
void del()
{
    if(s.size())
    {
        ans+=s.top();
        s.pop();
    }
}
void ins(char c)
{
    if(s.size()==smx) del();
    s.push(c);
}
int main()
{
    sc(n,m,smx);
    if(smx<=0) return 0;
    rep(i,1,n)
    {
        string t;cin>>t;
        for(int j=0;j<t.size();j++)
            q[i].push(t[j]);
    }
    while(true)
    {
        int x;sc(x);
        if(x==-1) break;
        if(x==0) del();
        else if(q[x].size()) ins(q[x].front()),q[x].pop();
    }
    cout<<ans;
}

L2-2

拓扑排序

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define nep(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
typedef long long ll;
void sc(int &x){scanf("%d",&x);}
void sc(int &x,int &y){scanf("%d%d",&x,&y);}
void sc(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}
void sc(ll &x){scanf("%lld",&x);}
void sc(ll &x,ll &y){scanf("%lld%lld",&x,&y);}
void sc(ll &x,ll &y,ll &z){scanf("%lld%lld%lld",&x,&y,&z);}
void out(int x){printf("%d\n",x);}
void out(int x,int y){printf("%d %d\n",x,y);}
const int N=1e4+5;
int n,d[N],len[N],nex[N];
vector<int>e[N],re[N];
queue<int>q;
int main()
{
    sc(n);
    rep(i,0,n-1)
    {
        int k;sc(k);
        d[i]=k;
        while(k--)
        {
            int x;sc(x);
            e[i].push_back(x);
            re[x].push_back(i);
        }
    }
    rep(i,0,n-1) if(d[i]==0) q.push(i),len[i]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int v:re[u])
        {
            if(len[v]<len[u]+1)
            {
                len[v]=len[u]+1;
                nex[v]=u;
            }
            else if(len[v]==len[u]+1) nex[v]=min(nex[v],u);
            d[v]--;
            if(d[v]==0) q.push(v);
        }
    }
    int mx=0,p=-1;
    rep(i,0,n-1) if(len[i]>mx) mx=len[i],p=i;
    out(mx);
    rep(i,1,mx)
    {
        printf(i==mx?"%d\n":"%d ",p);
        p=nex[p];
    }
}

L2-3

排序比较方法的重载

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define nep(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
typedef long long ll;
void sc(int &x){scanf("%d",&x);}
void sc(int &x,int &y){scanf("%d%d",&x,&y);}
void sc(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}
void sc(ll &x){scanf("%lld",&x);}
void sc(ll &x,ll &y){scanf("%lld%lld",&x,&y);}
void sc(ll &x,ll &y,ll &z){scanf("%lld%lld%lld",&x,&y,&z);}
void out(int x){printf("%d\n",x);}
void out(int x,int y){printf("%d %d\n",x,y);}
const int N=1e4+5;
int n,m,p[N];
vector<int>a[N];
bool cmp(int x,int y)
{
    for(int i=0;i<m;i++)
        if(a[x][i]!=a[y][i])
        return a[x][i]<a[y][i];
    return false;
}
bool eq(int x,int y)
{
    for(int i=0;i<m;i++)
        if(a[x][i]!=a[y][i]) return false;
    return true;
}
vector<int>ans[N];
int main()
{
    sc(n,m);
    rep(i,1,n)
        rep(j,1,m)
        {
            int x;sc(x);
            a[i].push_back(x);
        }
    rep(i,1,n) p[i]=i;
    sort(p+1,p+1+n,cmp);
    int res=0;
    for(int i=1;i<=n;i++)
    {
        int j=i;
        while(j+1<=n&&eq(p[i],p[j+1])) j++;
        ans[j-i+1].push_back(p[i]);
        i=j;
        res++;
    }
    out(res);
    for(int i=n;i>=1;i--)
        for(int x:ans[i])
    {
        printf("%d",i);
        for(int j=0;j<m;j++)
            printf(" %d",a[x][j]);
        printf("\n");
    }
}

L2-4

模拟

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define nep(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
typedef long long ll;
void sc(int &x){scanf("%d",&x);}
void sc(int &x,int &y){scanf("%d%d",&x,&y);}
void sc(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}
void sc(ll &x){scanf("%lld",&x);}
void sc(ll &x,ll &y){scanf("%lld%lld",&x,&y);}
void sc(ll &x,ll &y,ll &z){scanf("%lld%lld%lld",&x,&y,&z);}
void out(int x){printf("%d\n",x);}
void out(int x,int y){printf("%d %d\n",x,y);}
const int N=2e5+5;
int n,m,s[N];
vector<int>e[N];
int main()
{
    sc(n,m);
    rep(i,1,n)
    {
        int k;sc(k);
        while(k--)
        {
            int x;sc(x);
            e[i].push_back(x);
        }
    }
    int now=1;
    while(m--)
    {
        int op,x;
        sc(op,x);
        if(op==0)
            now=e[now][x-1];
        else if(op==1)
        {
            out(now);
            s[x]=now;
        }
        else now=s[x];
    }
    out(now);
}

L3-1

迪杰斯特拉+优先队列

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define nep(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
typedef long long ll;
void sc(int &x){scanf("%d",&x);}
void sc(int &x,int &y){scanf("%d%d",&x,&y);}
void sc(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}
void sc(ll &x){scanf("%lld",&x);}
void sc(ll &x,ll &y){scanf("%lld%lld",&x,&y);}
void sc(ll &x,ll &y,ll &z){scanf("%lld%lld%lld",&x,&y,&z);}
void out(int x){printf("%d\n",x);}
void out(int x,int y){printf("%d %d\n",x,y);}
const int N=2e5+5;
int n,m,k,a[N];
ll dis[2][N];
vector<pair<int,int>>e[2][N];
struct node
{
    int u;ll dis;
    node(int u=0,ll dis=0):u(u),dis(dis){}
    bool operator<(const node&o)const
    {
        return dis>o.dis;
    }
};
priority_queue<node>q;
bool vis[N];
void dij(int u,vector<pair<int,int>>e[N],ll dis[N])
{
    memset(vis,false,sizeof(vis));
    rep(i,1,n) dis[i]=inf;
    dis[u]=0;
    q.push(node(u,dis[u]));
    while(!q.empty())
    {
        int u=q.top().u;q.pop();
        if(vis[u]) continue;
        vis[u]=true;
        for(pair<int,int>x:e[u])
        if(dis[x.first]>dis[u]+x.second)
        {
            dis[x.first]=dis[u]+x.second;
            q.push(node(x.first,dis[x.first]));
        }
    }
}
priority_queue<ll,vector<ll>,greater<ll>>ans,del;
ll cal(int u)
{
    if(dis[0][u]==inf||dis[1][u]==inf) return inf;
    return dis[0][u]+dis[1][u]/a[u]+(dis[1][u]%a[u]!=0);
}
int main()
{
    sc(n,m,k);
    while(m--)
    {
        int u,v,c,d;
        sc(u,v);sc(c,d);
        e[0][u].push_back({v,c});
        e[1][v].push_back({u,d});
    }
    rep(i,1,n) sc(a[i]);
    dij(1,e[0],dis[0]);
    dij(n,e[1],dis[1]);
    rep(u,1,n) ans.push(cal(u));
    while(k--)
    {
        int u,y;sc(u,y);
        del.push(cal(u));
        a[u]=y;
        ans.push(cal(u));
        while(del.size()&&del.top()==ans.top()) del.pop(),ans.pop();
        printf("%lld\n",ans.top());
    }
}

L3-2

暴力+搜索

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define nep(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
typedef long long ll;
void sc(int &x){scanf("%d",&x);}
void sc(int &x,int &y){scanf("%d%d",&x,&y);}
void sc(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}
void sc(ll &x){scanf("%lld",&x);}
void sc(ll &x,ll &y){scanf("%lld%lld",&x,&y);}
void sc(ll &x,ll &y,ll &z){scanf("%lld%lld%lld",&x,&y,&z);}
void out(int x){printf("%d\n",x);}
void out(int x,int y){printf("%d %d\n",x,y);}
const int N=2e5+5,mod1=998244353,mod2=1e9+7;
const int b1=233,b2=2992;
int ib1,ib2;
ll qpow(ll a,ll n,ll mod)
{
    ll ans=1;
    for(;n;n>>=1,a=a*a%mod)
        if(n&1) ans=ans*a%mod;
    return ans;
}
int n,m,a[N],k[N],las[N];
ll hh1[N],hh2[N],gh1[N],gh2[N];
ll f1[N],f2[N],if1[N],if2[N],hs1[N],hs2[N];
vector<int>e[N];
int top,s[N];
bool inq[N];
void dfs(int cur,int len,ll h1,ll h2)
{
    if(h1!=hs1[len]||h2!=hs2[len]) return;
    if(len==n)
    {
        for(int i=1;i<=top;i++)
            printf(i==top?"%d\n":"%d ",s[i]);
        exit(0);
    }
    for(int nex:e[las[cur]])
    if(!inq[nex])
    {
        inq[s[++top]=nex]=true;
        dfs(nex,len+k[nex]-1,(h1+gh1[nex]*f1[len]%mod1)%mod1,(h2+gh2[nex]*f2[len]%mod2)%mod2);
        inq[s[top--]]=false;
    }
}
int main()
{
    ib1=qpow(b1,mod1-2,mod1);
    ib2=qpow(b2,mod2-2,mod2);
    f1[0]=f2[0]=1;
    rep(i,1,N-1)
    {
        f1[i]=f1[i-1]*b1%mod1;
        f2[i]=f2[i-1]*b2%mod2;
        if1[i]=if1[i-1]*ib1%mod1;
        if2[i]=if2[i-1]*ib2%mod2;
    }
    sc(n);
    rep(i,1,n) sc(a[i]),a[i]++;
    rep(i,1,n)
    {
        hs1[i]=(hs1[i-1]+a[i]*f1[i])%mod1;
        hs2[i]=(hs2[i-1]+a[i]*f2[i])%mod2;
    }
    sc(m);
    rep(i,1,m)
    {
        sc(k[i]);
        rep(j,1,k[i])
        {
            int x;sc(x);x++;
            hh1[i]=(hh1[i]+x*f1[j])%mod1;
            hh2[i]=(hh2[i]+x*f2[j])%mod2;
            if(j==1) e[x].push_back(i);
            else
            {
                gh1[i]=(gh1[i]+x*f1[j-1])%mod1;
                gh2[i]=(gh2[i]+x*f2[j-1])%mod2;
            }
            las[i]=x;
        }
    }
    for(int i=1;i<=m;i++)
    {
        inq[s[++top]=i]=true;
        dfs(i,k[i],hh1[i],hh2[i]);
        inq[s[top--]]=false;
    }
}