飞机票： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4879

分析：搞了一天的2-sat了。。。感觉还是迷迷糊糊真是菜比~~~好了。。。不扯了。。。直接正题：

题意：题意就是给你个矩阵。。。然后求是否有数组满足那段程序的。。。程序自己看啊。。。请点击飞机票。。。这种题怎么变成2-sat。。。烧脑烧力啊。。。，先预处理对角线是否为0和对称点是否一样。。然后只要把每个位单独处理即可~~~。。。坦白地说：对于矩阵的一个元素b[i][j]。。。如果i%2==0&&j%2==0则a[i]&a[j]=b[i][j]。。。这里就可以用到前面文章的内容了。。。就是说a[i]的第k为&a[j]的第k位=b[i][j]的第k位（注：2进制下）然后运用前面文章的信息。不妨设当前点i为1则是i*2,为0则是i*2+1那么就可以建图了

AND 结果为1：建边 x*2+1->x*2,y*2+1->y*2 （两个数必须全为1）

AND 结果为0：建边 y*2->x*2+1,x*2->y*2+1 （两个数至少有一个为0）

OR 结果为1：建边 x*2+1->y*2,2*y+1->x*2 （两个数至少有一个为1）

OR 结果为0：建边 x*2->x*2+1,y*2->y*2+1 （两个数必须全为0）

XOR 结果为1：建边 x*2->y*2+1,y*2->x*2+1,y*2+1->x*2,x*2+1->y*2 （两个数必须不同）

XOR 结果为0：建边 x*2->y*2,y*2->x*2,x*2+1->y*2+1,y*2+1->x*2+1 （两个数必须相同）

这样要处理最多30次。。。因为b[i][j]有范围限制，然后每一次都跑一遍。。。只要有不符合就直接啪啦：NO，如果都想。。YES！啪啪啪~但是速度不快啊。。。不过AC还是轻轻松松的~~~

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
const int maxn=1234;
vector<int> V[maxn];
int ai[567][567];
int n;
void init()
{
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            scanf("%d",&ai[i][j]);
        }
    }

}
bool instack[maxn];
int dfn[maxn],low[maxn],sta[maxn],belong[maxn],indexx,scnt,cntnum;
void tarjan(int u)
{
    dfn[u]=low[u]=indexx++;
    instack[u]=1;
    sta[++scnt]=u;
    for(int i=0; i<V[u].size(); i++)
    {

        int v=V[u][i];
        if(dfn[v]==-1)
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v])low[u]=min(dfn[v],low[u]);
    }
    if(dfn[u]==low[u])
    {
        for(int v=-1; v!=u; scnt--)
        {
            v=sta[scnt];
            instack[v]=0;
            belong[v]=cntnum;
        }
        cntnum++;
    }
}
void play()
{
    for(int i=0; i<n; i++)
    {
        if(ai[i][i]!=0)
        {
            printf("NO\n");
            return;
        }
    }
    int MAX=0;
    for(int i=0; i<n; i++)
    {
        for(int j=i+1; j<n; j++)
        {   MAX=max(MAX,ai[i][j]);
            if(ai[i][j]!=ai[j][i])
            {
                printf("NO\n");
                return;
            }
        }
    }
    int o=(1<<30);
    while(o>MAX){
        o=o>>1;
    }
    for(int i=1; i<=100; i++)
    {
        if(o==0)break;
        for(int j=0; j<2*n; j++)V[j].clear();
        bool ju=0;
        for(int j=0; j<n; j++)
        {
            for(int k=0; k<n; k++)
            {
                if(j==k)continue;
                int u=(j)*2;
                int v=(k)*2;
                int c=0;
                if(ai[j][k]-o>=0)
                {
                    ju=1;
                    ai[j][k]-=o;
                    c=1;
                }
                if(j%2==0&&k%2==0)
                {
                    if(c==0)
                    {
                        V[u].push_back(v^1);
                        V[v].push_back(u^1);
                    }
                    else
                    {
                        V[u^1].push_back(u);
                        V[v^1].push_back(v);
                    }
                }
                else if(j%2==1&&k%2==1)
                {
                    if(c==0)
                    {
                        V[u].push_back(u^1);
                        V[v].push_back(v^1);
                    }
                    else
                    {
                        V[u^1].push_back(v);
                        V[v^1].push_back(u);
                    }
                }
                else
                {
                    if(c==0)
                    {
                        V[u].push_back(v);
                        V[v].push_back(u);
                        V[u^1].push_back(v^1);
                        V[v^1].push_back(u^1);
                    }
                    else
                    {
                        V[u].push_back(v^1);
                        V[v].push_back(u^1);
                        V[v^1].push_back(u);
                        V[u^1].push_back(v);
                    }
                }
            }
        }
        o=o>>1;
        if(!ju)
        {
            continue;
        }
        indexx=cntnum=0;
        scnt=-1;
        memset(dfn,-1,sizeof(dfn));
        memset(instack,0,sizeof(instack));
        for(int j=0; j<2*n; j++)
        {
            if(dfn[j]==-1)tarjan(j);
        }
        for(int j=0; j<n; j++)
        {
            if(belong[j*2]==belong[j*2+1])
            {
                printf("NO\n");
                return;
            }
        }
    }
    printf("YES\n");
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        init();
        play();
    }
    //  cout << "Hello world!" << endl;
    return 0;
}

飞机票：http://poj.org/problem?id=3678

分析：题意。。。就是说给你个有向图，然后给你变a b 且a b有个值为c 要求a的值op b的值=c 其中op为（&，|，^）位运算，求解是否可以求出这样的解。继续2-sat。。。这题怎么搞呢。。。其实只要知道为位运算相互间的限制然后建图求解即可。。。那么关系是什么呢。。。不妨设当前点i为1则是i*2,为0则是i*2+1那么就可以建图了

AND 结果为1：建边 x*2+1->x*2,y*2+1->y*2 （两个数必须全为1）

AND 结果为0：建边 y*2->x*2+1,x*2->y*2+1 （两个数至少有一个为0）

OR 结果为1：建边 x*2+1->y*2,2*y+1->x*2 （两个数至少有一个为1）

OR 结果为0：建边 x*2->x*2+1,y*2->y*2+1 （两个数必须全为0）

XOR 结果为1：建边 x*2->y*2+1,y*2->x*2+1,y*2+1->x*2,x*2+1->y*2 （两个数必须不同）

XOR 结果为0：建边 x*2->y*2,y*2->x*2,x*2+1->y*2+1,y*2+1->x*2+1 （两个数必须相同）

然后建边就可以AC了

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
const int maxn=2345;
vector<int> V[maxn];
int n,m;
char ch[100];
void init()
{
    for(int i=0; i<=2*n; i++)V[i].clear();
    int u,v,c;
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d%s",&u,&v,&c,ch+1);
        u=u*2;
        v=v*2;
        if(ch[1]=='A')
        {
            if(c==0)
            {
                V[u].push_back(v^1);
                V[v].push_back(u^1);
            }
            else
            {
                V[u^1].push_back(u);
                V[v^1].push_back(v);
            }
        }
        else if(ch[1]=='O')
        {
            if(c==0)
            {
                V[u].push_back(u^1);
                V[v].push_back(v^1);
            }
            else
            {
                V[u^1].push_back(v);
                V[v^1].push_back(u);
            }
        }
        else
        {
            if(c==0)
            {
                V[u].push_back(v);
                V[v].push_back(u);
                V[u^1].push_back(v^1);
                V[v^1].push_back(u^1);
            }
            else
            {
                V[u].push_back(v^1);
                V[v].push_back(u^1);
                V[v^1].push_back(u);
                V[u^1].push_back(v);
            }

        }
    }
}
bool instack[maxn];
int dfn[maxn],low[maxn],sta[maxn],belong[maxn],indexx,scnt,cntnum;
void tarjan(int u)
{
    dfn[u]=low[u]=indexx++;
    instack[u]=1;
    sta[++scnt]=u;
    for(int i=0; i<V[u].size(); i++)
    {

        int v=V[u][i];
        if(dfn[v]==-1)
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v])low[u]=min(dfn[v],low[u]);
    }
    if(dfn[u]==low[u])
    {
        for(int v=-1; v!=u; scnt--)
        {
            v=sta[scnt];
            instack[v]=0;
            belong[v]=cntnum;
        }
        cntnum++;
    }
}
void play()
{
    indexx=cntnum=0;
    scnt=-1;
    memset(dfn,-1,sizeof(dfn));
    memset(instack,0,sizeof(instack));
    for(int i=0; i<2*n; i++)
    {
        if(dfn[i]==-1)tarjan(i);
    }
    for(int i=0; i<n; i++)
    {
        if(belong[i*2]==belong[i*2+1])
        {
            printf("NO\n");
            return;
        }
    }
    printf("YES\n");
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        play();
    }
    //  cout << "Hello world!" << endl;
    return 0;
}

飞机票： http://poj.org/problem?id=3207

分析：题目有点难懂。。。但还是2-sat 。。题目的意思就是按顺时针给定圆上n个点。标号0~n-1.然后m个连接。。。注意：连接可以连接在圆内也可以在圆外。。。这里提示我们不一定是直线。。。然后判断是否可以不相交在圆内或圆外。。可以相交在圆上。。。

题目都看晕了。。。其实很简单。。。假如当前是的i个连接且坐标为li ri,如果有个连接k。且lk>li&&lk<ri&&rk>ri 或则

rk>li&&rk<lr&&lk<li 这样就代表这两条不能在一侧。否则相交。。画个图你就懂了

这里有个判断我很喜欢

  int cnt=0;
  if((JLJ[i].l>JLJ[j].l&&JLJ[i].l<JLJ[j].r))cnt++;
  if((JLJ[i].l>JLJ[j].l&&JLJ[i].r<JLJ[j].r))cnt++;

如果cnt=1就相交。。。为什么呢cnt=1时就说明前面满足了一个条件。另一个不满足。。就是说只有一个点在里面。另个在外面。。怎么画肯定都相交。。。简单易懂。。然后就是2-sat 啪啪啪~~~oh，no！好像还有个问题。。就是这里要添加4条边。。因为互相制约。。然后就可以AC啦

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
const int maxn=1234;
vector<int> V[maxn];
int n,m;
struct he
{
    int l,r;
} JLJ[567];
void init()
{
    for(int i=0; i<=2*m; i++)V[i].clear();
    int u,v;
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&u,&v);
        if(u>v)swap(u,v);
        JLJ[i].l=u;
        JLJ[i].r=v;
    }
    for(int i=1; i<=m; i++)
    {
        for(int j=i+1; j<=m; j++)
        {
            int cnt=0;
            if((JLJ[i].l>JLJ[j].l&&JLJ[i].l<JLJ[j].r))cnt++;
            if((JLJ[i].l>JLJ[j].l&&JLJ[i].r<JLJ[j].r))cnt++;
            if(cnt==1)
            {
                int u=2*(i-1);
                int v=2*(j-1);
                V[u].push_back(v+1);
                V[u+1].push_back(v);
                V[v].push_back(u+1);
                V[v+1].push_back(u);
            }
        }
    }
}
bool instack[maxn];
int dfn[maxn],low[maxn],sta[maxn],belong[maxn],indexx,scnt,cntnum;
void tarjan(int u)
{
    dfn[u]=low[u]=indexx++;
    instack[u]=1;
    sta[++scnt]=u;
    for(int i=0; i<V[u].size(); i++)
    {

        int v=V[u][i];
        if(dfn[v]==-1)
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v])low[u]=min(dfn[v],low[u]);
    }
    if(dfn[u]==low[u])
    {
        for(int v=-1; v!=u; scnt--)
        {
            v=sta[scnt];
            instack[v]=0;
            belong[v]=cntnum;
        }
        cntnum++;
    }
}
void play()
{
    indexx=cntnum=0;
    scnt=-1;
    memset(dfn,-1,sizeof(dfn));
    memset(instack,0,sizeof(instack));
    for(int i=0; i<2*m; i++)
    {
        if(dfn[i]==-1)tarjan(i);
    }
    for(int i=0; i<m; i++)
    {
        if(belong[i*2]==belong[i*2+1])
        {
            printf("the evil panda is lying again\n");
            return;
        }
    }
    printf("panda is telling the truth...\n");
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        play();
    }
    //  cout << "Hello world!" << endl;
    return 0;
}

飞机票： http://acm.hdu.edu.cn/showproblem.php?pid=1824

其实这个题意好像有点模糊。。。比如第一个样例。。。如果0留下，那么1肯定要回家。。。则2肯定要留下。。。或则是1留下。。。那么2和0肯定要回家。。。或则是2留下，那么1肯定要回家，0肯定要留下。。。然而题意的意思是，0留下则1，2都的回家。或则1，2留下，0回家。。。而情况就只有 0，2回家，1留下，0，2留下，1回家， 跟题意不符。。。但是网上说是2-sat了。。那就2-sat吧。练练手。。。其实很简单。。。只要把两名队员看成一个正题就可以解决了

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
const int maxn=2345;
vector<int> V[maxn];
int can[maxn*2];
int n,m;
void init()
{
    for(int i=0; i<=2*n; i++)V[i].clear();
    int o,p,q;
    for(int i=0; i<n; i++)
    {
        scanf("%d%d%d",&o,&p,&q);
        can[o]=i*2;
        can[p]=i*2+1;
        can[q]=i*2+1;
    }
    int u,v;
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&u,&v);
        V[u].push_back(v^1);
        V[v].push_back(u^1);
    }
}
bool instack[maxn];
int dfn[maxn],low[maxn],sta[maxn],belong[maxn],indexx,scnt,cntnum;
void tarjan(int u)
{
    dfn[u]=low[u]=indexx++;
    instack[u]=1;
    sta[++scnt]=u;
    for(int i=0; i<V[u].size(); i++)
    {

        int v=V[u][i];
        if(dfn[v]==-1)
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v])low[u]=min(dfn[v],low[u]);
    }
    if(dfn[u]==low[u])
    {
        for(int v=-1; v!=u; scnt--)
        {
            v=sta[scnt];
            instack[v]=0;
            belong[v]=cntnum;
        }
        cntnum++;
    }
}
void play()
{
    indexx=cntnum=0;
    scnt=-1;
    memset(dfn,-1,sizeof(dfn));
    memset(instack,0,sizeof(instack));
    for(int i=0; i<2*n; i++)
    {
        if(dfn[i]==-1)tarjan(i);
    }
    for(int i=0; i<n; i++)
    {
        if(belong[i*2]==belong[i*2+1])
        {
            printf("no\n");
            return;
        }
    }
    printf("yes\n");
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        play();
    }
    //  cout << "Hello world!" << endl;
    return 0;
}

飞机票： http://acm.hdu.edu.cn/showproblem.php?pid=3062

开始学习2-sat了

其实2-sat原理很简单，简单来说，有2个组。每个组里有2个人。定义为A1,A2,B1,B2.如果选择A1不能选择B1。则在A1，B2连一条边，A2，B1连一条边。。。然后强联通一下。判断下A1和A2是否属于同一个块。如果是的话，那方案不可行，不是的话反之~然后这题是个入门题。把没对夫妻分为2*i和 2*i+1 然后建边，tarjan一下。。判断2*i和2*i+1是否属于同一个块即可。。。

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
const int maxn=2345;
vector<int> V[maxn];
int n,m;
void init()
{
    for(int i=0; i<=2*n; i++)V[i].clear();
    int a,b,c,d,u,v;
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d%d",&a,&b,&c,&d);
        u=2*a+c;
        v=2*b+d;
        V[u].push_back(v^1);
        V[v].push_back(u^1);
    }
}
bool instack[maxn];
int dfn[maxn],low[maxn],sta[maxn],belong[maxn],indexx,scnt,cntnum;
void tarjan(int u)
{
    dfn[u]=low[u]=indexx++;
    instack[u]=1;
    sta[++scnt]=u;
    for(int i=0; i<V[u].size(); i++)
    {

        int v=V[u][i];
        if(dfn[v]==-1)
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v])low[u]=min(dfn[v],low[u]);
    }
    if(dfn[u]==low[u])
    {
        for(int v=-1; v!=u; scnt--)
        {
            v=sta[scnt];
            instack[v]=0;
            belong[v]=cntnum;
        }
        cntnum++;
    }
}
void play()
{
    indexx=cntnum=0;
    scnt=-1;
    memset(dfn,-1,sizeof(dfn));
    memset(instack,0,sizeof(instack));
    for(int i=0; i<2*n; i++)
    {
        if(dfn[i]==-1)tarjan(i);
    }
    for(int i=0; i<n; i++)
    {
        if(belong[i*2]==belong[i*2+1])
        {
            printf("NO\n");
            return;
        }
    }
    printf("YES\n");
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        play();
    }
    //  cout << "Hello world!" << endl;
    return 0;
}

飞机票： http://acm.hdu.edu.cn/showproblem.php?pid=5154

很好理解的题。。。

题目分析：最多100个点 跑一边floyd 看是否有环 复杂度 0（n^3）。一个trick就是自己到自己有环也是NO

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
const int maxn=123;
int ai[maxn][maxn];
int n,m;
void init()
{
    int u,v;
    memset(ai,0,sizeof(ai));
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&u,&v);
        ai[u][v]=1;
    }
}
void play()
{
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(ai[i][k]&&ai[k][j])
                {
                    ai[i][j]=1;
                }
            }
        }
    }   
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(ai[i][j]&&ai[j][i])
            {
                printf("NO\n");
                return;
            }
        }
    }

    printf("YES\n");
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        play();
    }
    return 0;
}

题目链接： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3273

自从湖南旅游回来之后整个人真的是不佳啊~~~一天就做了这么一个题。。。感觉自己的越来越弱了。。。好了进入正题

分析：首先，这种题先找规律

当n=1时，只有1个根节点，则只能组成1种形态的二叉树，令n个节点可组成的二叉树数量表示为h(n)，
则h(1)=1; 
当n=2时，1个根节点固定，还有n-1个节点，可以作为左子树，也可以作为右子树， 即：h(2)=h(0)*h(1)+h(1)*h(0)=2，则能组成2种形态的二叉树。这里h(0)表示空，所以只能算一种形态，即h(0)=1; 
当n=3时，1个根节点固定，还有n-1=2个节点，可以在左子树或右子树， 即：h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=5，则能组成5种形态的二叉树。 
以此类推，当n>=2时，可组成的二叉树数量为h(n)=h(0)*h(n-1)+h(1)*h(n-2)+...+h(n-1)*h(0)种。
 
即符合Catalan数的定义，可直接利用通项公式得出结果。 递归式： 
  h(n)=h(n-1)*(4*n-2)/(n+1);  该递推关系的解为： 
  h(n)=C(2n,n)/(n+1) (n=1,2,3,...)

然后就啪啪啪、、、Wa了尼玛。。。作为弱者的我不知道怎么错了。。。后来看看递推里面带了除法。。。我去。。。我不会带除法的取余果断百度了一下。。。soga。。看了下要变乘法。。。ok直接套取余模版。。。然后就AC了

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <stack>
#define LL long long
using namespace std;
const int maxn=123456;
int n,m;
//LL ai[maxn];
int sm[1000],p;//将m分解质因数
int sa[1000];//4*i-2 和 i+1 分解质因数
//素数筛选
int flag[50000],pri[50000],pl;
void prime()
{
    for(int i=2; i<50000; i++)
    {
        if(flag[i]==0) pri[pl++]=i;
        for(int j=0; j<pl&&i*pri[j]<50000; j++)
        {
            flag[i*pri[j]]=1;
            if(i%pri[j]==0) break;
        }
    }
}
int extgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int r=extgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return r;
}
LL over;
void init()
{
    over=1%m;
    LL res=1;//n=1时 sum=1 后面从2开始
    p=0;
    int tm=m;//将m分解质因数
    for(int i=0; pri[i]*pri[i]<=tm; i++)
    {
        if(tm%pri[i]==0)
        {
            sm[p++]=pri[i];
            while(tm%pri[i]==0) tm/=pri[i];
        }
    }
    if(tm>1) sm[p++]=tm;//important
    memset(sa,0,sizeof(sa));
    for(int i=2; i<=n; i++)
    {
        int t;
        t=4*i-2;
        for(int j=0; j<p; j++)
        {
            while(t%sm[j]==0)
            {
                sa[j]++,t/=sm[j];
            }
        }
        res=res*t%m;
        t=i+1;
        for(int j=0; j<p; j++)
        {
            while(t%sm[j]==0)
            {
                sa[j]--,t/=sm[j];
            }
        }
        if(t>1)
        {
            int x,y;
            int r=extgcd(t,m,x,y);
            x=(x%m+m)%m;
            res=res*x%m;
        }
        LL tmp=res;
        for(int j=0; j<p; j++)
        {
            for(int k=0; k<sa[j]; k++)
            {
                tmp=tmp*sm[j]%m;
            }
        }
        over=(over+tmp)%m;
    }
}
void play()
{

    printf("%lld\n",over);
}
int main()
{
    prime();
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0&&m==0)break;
        init();
        play();
    }
    return 0;
}

题目链接： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3374

题意就是说有n棵树，每棵树有个初始值a个金币，而且每过一天会增加b个金币，求m天最多可以得到金币，而且必须每天都要砍一棵树

刚开始以为是贪心。。。Wa，后来举了个反例才发现自己的贪心是错的。。。那么应该怎么做这道题呢？？DP。。。除了贪心我只能想到DP，该怎么DP呢。。。后来想到来个数组dp[i][j]表示前i棵树在j天最大可以产生多少。。。但是有个特别的值。。就是b。。。好像又把我卡住了。。。想一下，就是怎么来确定顺序呢。。。根据b排序。。。把b最小的放前面。。。这样到后面的时候，b已经是最优的了。。。所以这道题的大致感觉就是。当前要放那个哪个地方的话。。。前面的得先放好而且是最优的

 ai[i][j]=max(ai[i-1][j],ai[i-1][j-1]+JLJ[i].b*(j-1)+JLJ[i].a);

这样答案就出来了

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
const int maxn=250+10;
struct he
{
    int a,b;
} JLJ[maxn];
int ai[maxn][maxn];
int n,m;
int T;
bool cmp(he a,he b)
{
    return a.b<b.b;
}
void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&JLJ[i].a);
    }
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&JLJ[i].b);
    }
}
void play()
{   sort(JLJ+1,JLJ+1+n,cmp);
    memset(ai,0,sizeof(ai));
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {   if(j<=i)
            ai[i][j]=max(ai[i-1][j],ai[i-1][j-1]+JLJ[i].b*(j-1)+JLJ[i].a);
            else break;
        }
    }
    printf("%d\n",ai[n][m]);
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
    //cout << "Hello world!" << endl;
    return 0;
}

链接 http://acm.hdu.edu.cn/showproblem.php?pid=5150

Bestcoder的一道题。。。直接暴力即可。。。但是看见被hack的好多。。。原来是在1这里出了问题。。。后面几个题没几个做的出来。看来这场的题偏难了

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
const int maxn=1234;
int n;
int ai[maxn];
int bi[maxn];
void init()
{
    for(int i=1; i<=n; i++)scanf("%d",&bi[i]);
}
void play()
{
    int over=0;
    for(int i=1; i<=n; i++)
    {
        if(!ai[bi[i]])over+=bi[i];
    }
    printf("%d\n",over);
}
int main()
{
    memset(ai,0,sizeof(ai));
    for(int i=1; i<=1000; i++)
    {
        for(int j=2; j<i; j++)
        {
            if(i%j==0)ai[i]=1;
        }
    }
    while(scanf("%d",&n)!=EOF)
    {
        init();
        play();
    }
    return 0;
}

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1505

题目大意：就是有最多1024个魔法棒放在一排，按照时间顺序对第i个魔法棒改变状态，问最长的连续子序列且都是奇数次改变多长。

题目分析：网上说是暴力。。。我暴力了一发。。。过了。。。但是这题明显是线段树啊，虽然暴力出奇迹。

怎么个线段法？？就是每个区间记录最大值和是否是连续的区间。。怎么定义？？一个节点定义lval，rval，link，max，l,r 其中l，r不用说了，lval就是左边的长度，val同理，max最大值，link是否连续，如果连续，那么lva=rval;如果不连续当然也可能相等，但是不可能是区间的长度，这样我们就好搞了，每次更新子节点，则父节点判断是否连续，如果两个子节点都连续，则父节点lval=左节点的lva+右节点的rval，且max就是当前区间长~~~link当然是连接的啊~~不想等呢》》

那好办了，如果左节点是连得，那父节点lval=左节点lval+右节点lval，且rval=右节点rval，link当然为false了，max就是lmax+rmax

如果右节点是连得，同理哈。。。最后一种情况左右都不连。。。那父节点lval=左节点lval，父节点rval=右节点val，max还是lmax+rmax，link必然false，OK了，讨论完毕。。。AC啦

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=4097;
struct he
{
    int l,r,MAX;
    int lval,rval;
    int link;
} JLJ[maxn*2];
void BuildTree(int l,int r,int now)
{
    JLJ[now].l=l;
    JLJ[now].r=r;
    JLJ[now].link=0;
    JLJ[now].MAX=0;
    JLJ[now].lval=0;
    JLJ[now].rval=0;
    if(l==r)return;
    int mid=(l+r)/2;
    BuildTree(l,mid,now*2);
    BuildTree(mid+1,r,now*2+1);

}
void Update(int l,int now)
{
    if(JLJ[now].l==l&&JLJ[now].r==l)
    {
        if(JLJ[now].MAX==0)JLJ[now].MAX=1;
        else JLJ[now].MAX=0;
        JLJ[now].lval=JLJ[now].rval=JLJ[now].MAX;
        if(JLJ[now].MAX==1)
            JLJ[now].link=1;
        else JLJ[now].link=0;
        return;
    }
    int mid=(JLJ[now].l+JLJ[now].r)/2;
    if(l<=mid)
    {
        Update(l,now*2);
    }
    else
    {
        Update(l,now*2+1);
    }
    int j1=JLJ[now*2].link;
    int j2=JLJ[now*2+1].link;
    if(j1&&j2)
    {
        JLJ[now].link=1;
        JLJ[now].lval=JLJ[now].rval= JLJ[now].MAX=JLJ[now*2].MAX+JLJ[now*2+1].MAX;
    }
    else if(j1)
    {
        JLJ[now].link=0;
        JLJ[now].lval=JLJ[now*2].MAX+JLJ[now*2+1].lval;
        JLJ[now].rval=JLJ[now*2+1].rval;
        JLJ[now].MAX=max(JLJ[now].lval,max(JLJ[now*2+1].MAX,JLJ[now*2].MAX));
    }
    else if(j2)
    {   JLJ[now].link=0;
        JLJ[now].lval=JLJ[now*2].lval;
        JLJ[now].rval=JLJ[now*2].rval+JLJ[now*2+1].MAX;
        JLJ[now].MAX=max(JLJ[now*2].MAX,max(JLJ[now].rval,JLJ[now*2+1].MAX));
    }
    else
    {   JLJ[now].link=0;
        JLJ[now].lval=JLJ[now*2].lval;
        JLJ[now].rval=JLJ[now*2+1].rval;
        JLJ[now].MAX=max(JLJ[now*2].MAX,max(JLJ[now*2+1].MAX,JLJ[now*2].rval+JLJ[now*2+1].lval));
    }
}
int T,n;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        BuildTree(1,4096,1);
        int l;
        int MAX=0;
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&l);
            Update(l,1);
            MAX=max(MAX,JLJ[1].MAX);
        }
        printf("%d\n",MAX);
    }
    //cout << "Hello world!" << endl;
    return 0;
}