长乐集训DAY11

上午
状压DP-原题链接
T1 看不出来哪里有状压DP，但是能过就行吧。思路还是比较奇怪的。观察到数据范围a_i<=2¹³，一般情况下输入的数都不用压得这么小，这里才到8192一定有什么用。所以考虑对a_i进行枚举，然后就可以分别统计输入数据中或与其相同的和异或与其相同的数据的数量，其中或相同的直接枚举，二异或相同的考虑用DP解决。但。。。这貌似是普通的统计用DP而不是状压DP吧？感觉此题和状压没有一点关系。思路还是比较奇怪的，而且今天上午的专题时状压DP，这就更奇怪了。
源代码

#include<bits/stdc++.h>
using namespace std;
int n,a[55],mx,s,b[55];
unsigned long long int ans,dp[55][10005];
int pf()
{
    int ret=1;
    while(1)
    {
        ret*=2;
        if(ret>mx)
        {
            return ret;
        }
    }
}
int main()
{
    freopen("orandxor.in","r",stdin);
    freopen("orandxor.out","w",stdout);
    cin>>n;
//  mx=pf(n);
//  cout<<mx<<endl;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        mx=max(a[i],mx);
    }
    mx=pf();
    dp[0][0]=1;
    for(int i=1;i<mx;i++)
    {
        s=1;
        for(int j=1;j<=n;j++)
        {
            if((a[j]|i)==i)
            {
                b[s]=j;
                s++;
            }
        }
        s--;

        for(int j=1;j<=s;j++)
        {
            for(int k=i;k>=0;k--)
            {
//              cout<<"DP  ---   "<<i<<" "<<j<<endl;
                dp[j][k]=dp[j-1][k]+dp[j-1][k^a[b[j]]];
            }
        }
//      cout<<s<<"    "<<dp[s][i]<<endl;
        ans+=dp[s][i];
    }
    cout<<ans<<endl;
}

T2 T3 暴力一分没拿到
下午
题目链接
T1 没什么好说的，就单纯单调队列（赛时现学的新算法）
代码如下

#include
using namespace std;
int n,a[1000005][2],now,t,ans;
dequeA;
int main()
{
    freopen("tem.in","r",stdin);
    freopen("tem.out","w",stdout);
    cin>>n;
    for(int i=1;i>a[i][0]>>a[i][1];
    }
    if(n<=100)
    {
        for(int i=1;i<n;i++)
        {
            now=a[i][0];
            t=1;
            for(int j=i+1;j<=n;j++)
            {
                if(a[j][0]<=now&&now<=a[j][1])
                {
                    t++;
                }
                if(nowa[j][1])
                {
                    break;
                }
            }
            ans=max(ans,t);
        }
    }
    else
    for(int i=1;ia[i][1])
            {
                A.pop_front();

            }
            else
            {
                break;
            }
        }
        if(!A.empty())
        {
            ans=max(ans,i-A.front()+1);
        }
        t=i;
        while(1)
        {
            if(!A.empty()&&a[i][0]>a[A.back()][0])
            {
                t=A.back();
                A.pop_back();
            }
            else
            {
                break;
            }
        }
        a[t][0]=a[i][0];
        A.push_back(t);
    }
    cout<<ans<<endl;
}

T3 数据太水了，参（~照~）考（~抄~）题解爆彩虹了。彩虹 然后在cqr的不懈努力下我终于跳出来了。要命的初始化。最后还是AC了。（~然而数据加强版非紫即黑~）。
代码如下

#include
using namespace std;
int n,m,a,b,c,mx,ans=1147482647;
int dp[100005][1005];
struct tni
{
    int x,y,p,q;
};
int cmp(tni aa,tni bb)
{
    return aa.p>n>>m>>a>>b>>c;
    for(int i=1;i>s[i].x>>s[i].y>>s[i].p>>s[i].q;
        mx=max(mx,s[i].q);
    }
    sort(s+1,s+1+m,cmp);
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=mx;j++)
        {
            dp[i][j]=1147483647;
        }
    }
    dp[1][0]=0;
    for(int i=1;i<=m;i++)
    {
        for(int j=0;j<=s[i].p;j++)
        {
//          cout<<s[i].x<<" "<<j<<" "<<dp[s[i].x][j]<<" "<   "<<dp[s[i].y][s[i].q]<<endl;
            }
//          else
//            continue;

        }
    }
    for(int i=0;i<=mx;i++)
    {
        ans=min(ans,dp[n][i]+i);
    }
    cout<<ans<<endl;
}

最后的最后，