Spring camp div1每日一题

Day 1

单调栈

#436. 子串的最大差

#include
using namespace std;
typedef long long ll;
const int maxn=5e5+10;
const int inf=0x3f3f3f3f;
int stk[maxn];
ll a[maxn];
ll add[maxn],del[maxn];
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    ll sum=0,top=0;
    for(int i=1;i<=n;i++)
    {
        while(top&&a[i]>=a[stk[top]])
        {
            add[stk[top]]=add[stk[top]]*(i-stk[top]);
            top--;
        }
        stk[++top]=i;
        if(top-1==0)add[i]=i;
        else
        add[i]=i-stk[top-1];
    }
    // cout< 
Day 2
 
DP
 
#437. no crossing
 
#include
using namespace std;
typedef long long ll;
const int maxn=1e2+10;
ll dp[2][maxn][maxn][2];
ll dis[maxn][maxn];
int id;
int main()
{
    int n,K,m;
    cin>>n>>K;
    cin>>m;
    memset(dis,1,sizeof(dis));
    while(m--)
    {
        int a,b;ll c;cin>>a>>b>>c;
        dis[a][b]=min(dis[a][b],c);
    }
    memset(dp[0],1,sizeof(dp[0]));
    for(int i=1;i<=n;i++)dp[0][0][i][1]=dp[0][i][n+1][0]=0;
    while(--K)
    {
        id^=1;
        memset(dp[id],1,sizeof(dp[id]));
        for(int i=0;i<=n-1;i++)
        for(int j=i+2;j<=n+1;j++)
        for(int k=i+1;k(1<<20))res=-1;
    cout< 
 
Day 3
 
#451. Dis
 
LCA 板子题
 
#include
using namespace std;
const int maxn=2e5+10;
vector e[maxn];
int depth[maxn];
int q[maxn];
int f[maxn][23];
int n,m;
int w[maxn];
void bfs(int root)
{
    memset(depth,0x3f,sizeof(depth));
    depth[0]=0;
    depth[root]=1;
    int hh=0,tt=0;
    q[0]=root;
    while(hh<=tt)
    {
        int t=q[hh++];
        for(auto j:e[t])
        {
            if(depth[j]>depth[t]+1)
            {
                depth[j]=depth[t]+1;
                q[++tt]=j;
                f[j][0]=t;
                for(int k=1;k<=18;k++)
                {
                    f[j][k]=f[f[j][k-1]][k-1];
                }
            }
        }
    }
}
int lca(int a,int b)
{
    if(depth[a]=0;i--)
    if(depth[f[a][i]]>=depth[b])
    a=f[a][i];
    if(a==b) return b;
    for(int i=18;i>=0;i--)
    {
        if(f[a][i]!=f[b][i])
        {
            a=f[a][i];
            b=f[b][i];
        }
    }
    return f[a][0];
}
int x,y;
int s[maxn];
void dfs(int u,int fa)
{
    s[u]=w[u]^s[fa];
    for(auto v:e[u])
    {
        if(v==fa)continue;
        dfs(v,u);
    }
}
int res;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    for(int i=1;i 
 
Day 4
 
抽屉原理，for一遍就好了
 
#include
using namespace std;
const int maxn=1e5+10;
typedef long long ll;
int s[maxn],a[maxn],n;
bool st[maxn];
int ls[maxn];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i]%=n;
    for(int i=1;i<=n;i++)s[i]=(a[i]+s[i-1])%n;
    st[0]=true;ls[0]=0;
    for(int i=1;i<=n;i++)
    {if(st[s[i]])
    {
        printf("%dn",i-ls[s[i]]);
        for(int j=ls[s[i]]+1;j<=i;j++)printf("%d ",j);
        return 0;
    }
    else
    {
        ls[s[i]]=i;
        st[s[i]]=true;
    }}
}