Boleyn Su's Blog

数学题，设a[1]=x，然后由题意得递推式a[i]=(a[i-1]+c[i-1])*2-a[i-2]，然后将a[n+1]表示为x的线性表达式，然后解一元一次方程，这个就不用高斯消元了。可以参见URAL1046的解法，有点像。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-26

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

#include <cmath>

#include <iomanip>

 

class Application

{

      typedef double Type;

      struct Data

      {

             typedef double Type;

             Type x,C;

             void set(Type _x,Type _C)

             {

                  x=(_x),C=(_C);

             }

             void print()

             {

                  cout<<floor(x+0.5)<<” “<<floor(C+0.5)<<endl;

             }

      };

      int N;

      Type Astart,Aend;

      vector<Type> c;

      public:

      Application()

      {

                    cin>>N;

                    cin>>Astart>>Aend;

                    c.resize(N);

                    for (int i=0;i<N;i++) cin>>c[i];

      }

      int run()

      {

          //a[i]=(a[i-1]+a[i+1])/2-c[i]

          //a[i+1]=(a[i]+c[i])*2-a[i-1]

          //a[i]=(a[i-1]+c[i-1])*2-a[i-2]

          vector<Data> a(N+2);

          a[0].set(0,Astart);

          a[1].set(1,0);

          for (int i=2;i<=N+1;i++)

          {

              a[i].x=a[i-1].x*2-a[i-2].x;

              a[i].C=(a[i-1].C+c[i-1–1])*2-a[i-2].C;

          }

          cout<<std::setiosflags(std::ios::fixed)<<std::setprecision(2);

          cout<<(Aend-a[N+1].C)/a[N+1].x<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

数学题，看我的程序吧。我的注释打得很全。

还有，就是最后有用到高斯消元来解方程。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-26

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

#include <cmath>

using std::cin;

using std::cos;

//using std::M_PI;

#define M_PI 3.141592653589793238462643383279f

#include <iomanip>

 

template<typename Type>

class Function

{

      int n;

      vector<vector<Type> > matrix;

      vector<Type> answer;

      static Type abs(Type a)

      {

             return a>=0?a:-a;

      }

      void smaller(int step)

      {

           for (int i=step+1;i<n;i++)

               if (abs(matrix[i][step])>abs(matrix[step][step]))

                  matrix[step].swap(matrix[i]);

           for (int i=step+1;i<n;i++)

           {

               Type mul=matrix[i][step];

               Type div=matrix[step][step];

               for (int j=step;j<=n;j++)

                   matrix[i][j]-=matrix[step][j]*mul/div;

           }

      }

      void back(int step)

      {

           if (step==n-1)

              answer[step]=matrix[step][n]/matrix[step][step];

           else

           {

               answer[step]=matrix[step][n];

               for (int i=step+1;i<n;i++)

                   answer[step]-=matrix[step][i]*answer[i];

               answer[step]/=matrix[step][step];

           }

      }

      public:

      void read(vector<vector<Type> >& get)

      {

           n=get.size();

           matrix=get;

           answer.resize(get.size());

      }

      void solve()

      {

           for (int i=0;i<n-1;i++) smaller(i);

           for (int i=n-1;i>=0;i–) back(i);

      }

      void write(vector<Type>& put)

      {

           put=answer;

      }

};

 

class Application

{

      typedef double Type;

      struct Data

      {

             typedef double Type;

             Type x,y,C;

             void set(Type _x,Type _y,Type _C)

             {

                  x=(_x),y=(_y),C=(_C);

             }

             void print()

             {

                  cout<<floor(x+0.5)<<” “<<floor(y+0.5)<<” “<<floor(C+0.5)<<endl;

             }

      };

      int N;

      vector<pair<Type,Type> > M;

      vector<Type> a;

      public:

      Application()

      {

                    cin>>N;

                    M.resize(N);

                    for (int i=0;i<N;i++)

                        cin>>M[i].first>>M[i].second;

                    a.resize(N);

                    for (int i=0;i<N;i++)

                    {

                        cin>>a[i];

                        a[i]=a[i]/180.0*M_PI;

                    }

      }

      int run()

      {

          /*

          O为原点 旋转均为顺时针

          O->Ai+1= Mi->Ai 转ai度后 + O->Mi

          Ai+1=(Ai-Mi)转ai度 + Mi

         

          然后，关于旋转：

          若(x,y)旋转a度成为了(x’,y’)

          可以用极坐标

          令x’=R*cos(A),y’=R*sin(A)

            x=R*cos(B),y=R*cos(B)

          则A-B=a

          所以cos(A)=cos(B+a)

              sin(A)=sin(B+a)

          那么cos(A)=cos(B)cos(a)-sin(B)sin(a)

              sin(A)=sin(B)cos(a)+cos(B)sin(a)

          所以x’=x*cos(a)-y*sin(a)

              y’=y*cos(a)+x*sin(a)

         

          所以x(Ai+1)=(x(Ai)-x(Mi))*cos(a)-(y(Ai)-y(Mi))*sin(a)+x(Mi)

              y(Ai+1)=(y(Ai)-y(Mi))*cos(a)+(x(Ai)-x(Mi))*sin(a)+y(Mi)

          所以x(Ai+1)=x(Ai)*cos(a)-y(Ai)*sin(a)-x(Mi)*cos(a)+y(Mi)*sin(a)+x(Mi)

              y(Ai+1)=y(Ai)*cos(a)+x(Ai)*sin(a)-y(Mi)*cos(a)-x(Mi)*sin(a)+y(Mi)

          */

          vector<pair<Data,Data> > A(N+1);

          A[0].first.set(1.0,0,0);

          A[0].second.set(0,1.0,0);

          for (int i=0;i<N;i++)

          {

              double x,y,C;

             

              //x(Ai+1)=x(Ai)*cos(a)  -y(Ai)*sin(a)

              x=A[i].first.x*cos(a[i])-A[i].second.x*sin(a[i]);

              y=A[i].first.y*cos(a[i])-A[i].second.y*sin(a[i]);

              C=A[i].first.C*cos(a[i])-A[i].second.C*sin(a[i])

              //-x(Mi)*cos(a)        +y(Mi)*sin(a)         +x(Mi)

                -M[i].first*cos(a[i])+M[i].second*sin(a[i])+M[i].first;

             

              A[i+1].first.set(x,y,C);

             

              //y(Ai)*cos(a)          +x(Ai)*sin(a)

              x=A[i].second.x*cos(a[i])+A[i].first.x*sin(a[i]);

              y=A[i].second.y*cos(a[i])+A[i].first.y*sin(a[i]);

              C=A[i].second.C*cos(a[i])+A[i].first.C*sin(a[i])

              //-y(Mi)*cos(a)         -x(Mi)*sin(a)        +y(Mi)

                -M[i].second*cos(a[i])-M[i].first*sin(a[i])+M[i].second;

             

              A[i+1].second.set(x,y,C);

          }

          Function<Type> f;

          vector<vector<double> > matrix(2,vector<double>(3));

          vector<double> answer(2);

          //x=A[N].first.x*x+A[N].first.y*y+A[N].first.C

          //y=A[N].second.x*x+A[N].second.y*y+A[N].first.C

         

          //  x               y               C

          //  1-A[N].first.x  -A[N].first.y    A[N].first.C

          //  -A[N].second.x  1-A[N].second.y  A[N].second.C

          matrix[0][0]=1-A[N].first.x;

          matrix[0][1]=-A[N].first.y;

          matrix[0][2]=A[N].first.C;

          matrix[1][0]=-A[N].second.x;

          matrix[1][1]=1-A[N].second.y;

          matrix[1][2]=A[N].second.C;

          f.read(matrix);

          f.solve();

          f.write(answer);

          double X=answer[0];

          double Y=answer[1];

          cout<<std::setiosflags(std::ios::fixed)<<std::setprecision(2);

          for (int i=0;i<N;i++)

          {

              cout<<A[i].first.x*X+A[i].first.y*Y+A[i].first.C<<” “

                  <<A[i].second.x*X+A[i].second.y*Y+A[i].second.C<<endl;

          }

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

是极大极小搜索（true大false小），然后还是树形动规，还是博弈论，很有意思的题目（指NOCOW上的翻译）。

然后，提醒一下，有解时输出的L为与K连接且是必胜态的最小编号。我开始没读懂，输的不是这样的点，结果WA了两三次。无语。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-25

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

 

class Application

{

      int N,K;

      vector<vector<int> > link;

      vector<bool> win;

      void go(int node,bool isMe,int father=-1)

      {

           for (int i=0;i<link[node].size();i++)

               if (link[node][i]!=father)

                  go(link[node][i],!isMe,node);

           if (isMe)

           {

              win[node]=false;

              for (int i=0;i<link[node].size();i++)

                  if (link[node][i]!=father)

                     win[node]=win[node] or win[link[node][i]];

           }

           else

           {

               win[node]=true;

               for (int i=0;i<link[node].size();i++)

                   if (link[node][i]!=father)

                      win[node]=win[node] and win[link[node][i]];

           }

      }

      public:

      Application()

      {

                    cin>>N>>K;

                    link.resize(N);

                    for (int i=1,v,u;i<N;i++)

                        cin>>v>>u,link[v-1].push_back(u-1),link[u-1].push_back(v-1);

      }

      int run()

      {

          win.resize(N,false);

          go(K-1,true);

          if (win[K-1])

          {

             int gohere=N;

             for (int i=0;i<link[K-1].size();i++)

                 if (win[link[K-1][i]])

                    if (gohere>link[K-1][i])

                       gohere=link[K-1][i]+1;

             cout<<“First player wins flying to airport “<<gohere<<endl;

          }

          else cout<<“First player loses”<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

水水的DP，就如题目说的那样。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-25

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

 

class Application

{

      int N;

      public:

      Application()

      {

                    cin>>N;

      }

      int run()

      {

          int forward=N/2;

          int backward=N-forward;

          const int MAX=N*9+1;

          vector<vector<int> > f(N+1,vector<int>(MAX,0));

          //f[i][j]表示不超过i位和为j一共有几种可能

          //f[i][j]=sum{f[i-1][k],0<=j-k<=9}

          //边界f[0][0]=1

          //answer=sum{f[forward][i]*f[backward][i]}}

          f[0][0]=1;

          for (int i=1;i<=N;i++)

              for (int j=0;j<MAX;j++)

                  for (int k=0;k<MAX;k++)

                      if (j-k>=0 && j-k<=9)

                         f[i][j]+=f[i-1][k];

          int answer=0;

          for (int i=0;i<MAX;i++)

              answer+=f[forward][i]*f[backward][i];

          cout<<answer<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

数学题，看代码吧，我的注释写得很全。还有注意浮点误差，无语的误差！
CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-25

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

#include <cmath>

using std::sqrt;

using std::floor;

using std::ceil;

 

template<typename Type>

class Function

{

      int n;

      vector<vector<Type> > matrix;

      vector<Type> answer;

      static Type abs(Type a)

      {

             return a>=0?a:-a;

      }

      void smaller(int step)

      {

           for (int i=step+1;i<n;i++)

               if (abs(matrix[i][step])>abs(matrix[step][step]))

                  matrix[step].swap(matrix[i]);

           for (int i=step+1;i<n;i++)

           {

               Type mul=matrix[i][step];

               Type div=matrix[step][step];

               for (int j=step;j<=n;j++)

                   matrix[i][j]-=matrix[step][j]*mul/div;

           }

      }

      void back(int step)

      {

           if (step==n-1)

              answer[step]=matrix[step][n]/matrix[step][step];

           else

           {

               answer[step]=matrix[step][n];

               for (int i=step+1;i<n;i++)

                   answer[step]-=matrix[step][i]*answer[i];

               answer[step]/=matrix[step][step];

           }

      }

      public:

      void read(vector<vector<Type> >& get)

      {

           n=get.size();

           matrix=get;

           answer.resize(get.size());

      }

      void solve()

      {

           for (int i=0;i<n-1;i++) smaller(i);

           for (int i=n-1;i>=0;i–) back(i);

      }

      void write(vector<Type>& put)

      {

           put=answer;

      }

};

 

class Application

{

      static const int POINTNUMBER=3;

      static const int oo=1000;

      vector<pair<int,int> > p;

      double cross(double x1,double y1,double x2,double y2,double x3,double y3)

      {

             /*

                  1———–2

                 /

                /

               /

              3

              return 1->2 X 1->3

             */

             double dx12=x2-x1,dy12=y2-y1,

                    dx13=x3-x1,dy13=y3-y1;

             return dx12*dy13-dx13*dy12;

      }

      bool sameside(double x1,double y1,double x2,double y2,

                    double px1,double py1,double px2,double py2)

      {

           return cross(x1,y1,x2,y2,px1,py1)*cross(x1,y1,x2,y2,px2,py2)>0;

      }

      public:

      Application()

                   :p(POINTNUMBER)

      {

                   for (int i=0;i<POINTNUMBER;i++)

                       cin>>p[i].first>>p[i].second;

      }

      int run()

      {

          vector<vector<double> > v(POINTNUMBER,vector<double>(POINTNUMBER+1));

          Function<double> f;

          vector<double> answer;

          for (int i=0;i<POINTNUMBER;i++)

          {

              //x^2+y^2+Cx+Dy+E=0

              //x y 1 (-x^2-y^2)

              v[i][0]=p[i].first;

              v[i][1]=p[i].second;

              v[i][2]=1;

              v[i][3]=-(p[i].first*p[i].first+p[i].second*p[i].second);

          }

          f.read(v);

          f.solve();

          f.write(answer);

          //C=answer[0]

          //D=answer[1]

          //E=answer[2]

          //(x+C/2)^2+(y+D/2)^2=(C^2+D^2)/4-E

          //O(-C/2,-D/2) R=sqrt((C^2+D^2)/4-E)

          double C=answer[0],

                 D=answer[1],

                 E=answer[2];

          double Ox=-C/2,

                 Oy=-D/2,

                 R=sqrt((C*C+D*D)/4-E);

          /*

          圆心O; 起点S; 终点E; 中间过M

                          O———–S

                         / \

                        /   \

                       /     \

                      /       \

                     /         \

                    E           M

          */

          double Sx=p[0].first,Sy=p[0].second,

                 Ex=p[1].first,Ey=p[1].second,

                 Mx=p[2].first,My=p[2].second;

          int t=-oo,b=oo,l=oo,r=-oo;

          #define line(x1,y1,x2,y2) x1,y1,x2,y2

          #define point(x,y) x,y

          #define ZERO 0.0000001

          #define update(x,y)\

          {\

                  double X=x,Y=y;\

                  if (floor(X+ZERO)<l) l=floor(X+ZERO);\

                  if (ceil(X-ZERO)>r) r=ceil(X-ZERO);\

                  if (floor(Y+ZERO)<b) b=floor(Y+ZERO);\

                  if (ceil(Y-ZERO)>t) t=ceil(Y-ZERO);\

          }

          #define check_and_update(X,Y)\

          if (sameside(line(Sx,Sy,Ex,Ey),point(Mx,My),point(X,Y)))\

             update(X,Y);

          update(Sx,Sy);

          update(Ex,Ey);

          update(Mx,My);

          check_and_update(Ox+R,Oy);

          check_and_update(Ox-R,Oy);

          check_and_update(Ox,Oy+R);

          check_and_update(Ox,Oy-R);

          #undef check_and_update

          #undef update

          #undef ZERO

          #undef point

          #undef line

          if (r>oo) r=oo;

          if (l<-oo) l=-oo;

          if (t>oo) t=oo;

          if (b<-oo) b=-oo;

          cout<<(r-l)*(t-b)<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

高斯消元。然后把xor当成加号和减号，把and当成乘号就行了。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-25

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

 

class Application

{

      int N;

      vector<vector<bool> > v;

      vector<bool> answer;

      public:

      Application()

      {

                    cin>>N;

                    v.resize(N,vector<bool>(N+1,false));

                    for (int i=0;i<N;i++)

                    {

                        int get;

                        for (cin>>get;get!=-1;cin>>get)

                            v[get-1][i]=true;

                    }

                    for (int i=0;i<N;i++)

                        v[i][N]=true;

      }

      int run()

      {

          bool nosolution=false;

          for (int i=0;i<N-1;i++)

          {

              for (int j=i+1;j<N;j++)

                  if (v[j][i]>v[i][i])

                     v[i].swap(v[j]);

              if (v[i][i]==false)

              {

                 nosolution=true;

                 break;

              }

              for (int j=i+1;j<N;j++)

              {

                  bool mulj=v[i][i];

                  bool muli=v[j][i];

                  for (int k=i;k<=N;k++)

                      v[j][k]=((v[j][k] and mulj) xor (v[i][k] and muli));

              }

          }

          answer.resize(N);

          for (int i=N-1;i>=0;i–)

          {

              bool total=v[i][N];

              for (int j=i+1;j<N;j++)

                  total=total xor (answer[j] and v[i][j]);

              answer[i]=total and v[i][i];

          }

          if (nosolution) cout<<“No solution”<<endl;

          else

          {

              vector<int> print;

              for (int i=0;i<N;i++)

                  if (answer[i])

                     print.push_back(i+1);

              for (int i=0;i<print.size();i++)

                  cout<<print[i]<<char(i+1==print.size()?’\n’:’ ‘);

          }

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

恩，可以看一下LRJ黑书讲贪心那部分，在讲矩阵胚时有提到。
CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-24

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

 

class Application

{

      typedef long long int Type;

      int M,N;

      vector<vector<Type> > v;

      vector<pair<int,int> > p;

      static Type abs(Type n)

      {

             return n>=0?n:-n;

      }

      static Type gcd(Type a,Type b)

      {

             return b?gcd(b,a%b):a;

      }     

      bool push(vector<vector<Type> >& get,vector<Type> add)

      {

           vector<int> first(N);

           for (int i=0;i<get.size();i++)

               for (int j=0;j<N;j++)

                   if (get[i][j]!=0)

                   {

                      first[i]=j;

                      break;

                   }

           for (int i=0;i<get.size();i++)

           {

               static const Type BIGPRIME=549979;

               Type _gcd=gcd(abs(add[first[i]]),abs(get[i][first[i]]));

               //assert(_gcd!=0);

               if (_gcd)

               {

               Type mulj=get[i][first[i]]/_gcd;

               Type mulget=add[first[i]]/_gcd;

               for (int j=0;j<N;j++)

                   add[j]=(add[j]*mulj-get[i][j]*mulget)%BIGPRIME;

               }

               bool can=false;

               for (int j=0;j<N;j++)

                   if (add[j]!=0) can=true;

               if (!can) return false;

           }

           get.push_back(add);

           return true;

      }

      public:

      Application()

      {

                    cin>>M>>N;

                    v.resize(M,vector<Type>(N));

                    for (int i=0;i<M;i++)

                        for (int j=0;j<N;j++)

                            cin>>v[i][j];

                    p.resize(M);

                    for (int i=0;i<M;i++)

                    {

                        cin>>p[i].first;

                        p[i].second=i;

                    }

      }

      int run()

      {

          sort(p.begin(),p.end());

          int total=0;

          vector<int> answer;

          vector<vector<Type> > get;

          for (int i=0;i<M;i++)

          {

              if (push(get,v[p[i].second]))

              {

                 total+=p[i].first;

                 answer.push_back(p[i].second);

              }

              if (get.size()==N) break;

          }

          if (get.size()==N)

          {

             cout<<total<<endl;

             sort(answer.begin(),answer.end());

             for (int i=0;i<answer.size();i++)

                 cout<<answer[i]+1<<endl;

          }

          else cout<<0<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

URAL1041要用到高斯消元，所以找了这道VIJOS上的纯粹的高斯消元来练习。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-23

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

template<typename Type>

class Function

{

      int n;

      vector<vector<Type> > matrix;

      vector<Type> answer;

      static Type abs(Type a)

      {

             return a>=0?a:-a;

      }

      void smaller(int step)

      {

           for (int i=step+1;i<n;i++)

               if (abs(matrix[i][step])>abs(matrix[step][step]))

                  matrix[step].swap(matrix[i]);

           for (int i=step+1;i<n;i++)

           {

               Type mul=matrix[i][step];

               Type div=matrix[step][step];

               for (int j=step;j<=n;j++)

                   matrix[i][j]-=matrix[step][j]*mul/div;

           }

      }

      void back(int step)

      {

           if (step==n-1)

              answer[step]=matrix[step][n]/matrix[step][step];

           else

           {

               answer[step]=matrix[step][n];

               for (int i=step+1;i<n;i++)

                   answer[step]-=matrix[step][i]*answer[i];

               answer[step]/=matrix[step][step];

           }

      }

      public:

      bool read()

      {

           cin>>n;

           matrix.resize(n,vector<Type>(n+1));

           answer.resize(n);

           for (int i=0;i<n;i++)

               for (int j=0;j<=n;j++)

                   cin>>matrix[i][j];

           return true;

      }

      void solve()

      {

           for (int i=0;i<n-1;i++) smaller(i);

           for (int i=n-1;i>=0;i–) back(i);

      }

      template<typename Print_Type>

      void print()

      {

           for (int i=0;i<n;i++)

               cout<<Print_Type(answer[i])<<char((i+1==n)?’\n’:’ ‘);

      }

};

struct Integer

{

       long long int data;

       Integer(double get)

                      :data((long long int)(get+0.5))

       {

       }

       operator long long int()

       {

                return data;

       }

};

class Application

{

      public:

      Application()

      {

      }

      int run()

      {

          Function<double> f;

          f.read();

          f.solve();

          f.print<Integer>();

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

看了题解做的，题解大意是，DFS标记边的时候依次标1到M，这样任何一个点连到的边若超过1条，就必定有两条的标号相差1。所以满足条件（并且一定有解，所以输NO骗分是无用的）。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-22

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

 

class Application

{

      static const int NOMARK=-1;

      int N,M;

      vector<pair<pair<int,int>,int> > flight;

      void dfs(int node,int& mark)

      {

           for (int i=0;i<M;i++)

           {

               if (flight[i].second==NOMARK)

               {

                  if (flight[i].first.first==node)

                  {

                     flight[i].second=mark;

                     mark++;

                     dfs(flight[i].first.second,mark);

                  }

                  if (flight[i].first.second==node)

                  {

                     flight[i].second=mark;

                     mark++;

                     dfs(flight[i].first.first,mark);

                  }

               }

           }

      }

      public:

      Application()

      {

                    cin>>N>>M;

                    flight.resize(M);

                    for (int i=0;i<M;i++)

                    {

                        cin>>flight[i].first.first

                           >>flight[i].first.second;

                        flight[i].second=NOMARK;

                    }

      }

      int run()

      {

          int mark=1;

          for (int i=1;i<=N;i++)

              dfs(i,mark);

         

          cout<<“YES”<<endl;

          for (int i=0;i<M;i++)

              cout<<flight[i].second<<char(i+1==M?’\n’:’ ‘);

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

树形动规。

然后，若上司去了，那么下属一定不能去；若上司不去，那么下属可去可不去。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-22

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

 

class Application

{

      static const int oo=~(1<<31);

      int N;

      vector<int> happy;

      vector<vector<int> > children;

      vector<vector<int> > f;

      int dp(int parent,bool join)

      {

          if (f[parent][join]!=-oo) return f[parent][join];

          int max=-oo;

          //CASE 1 MY PARENT WANNA JOIN THE PARTY

          if (join)

          {

             int get=happy[parent];

             for (int i=0;i<children[parent].size();i++)

                 get+=dp(children[parent][i],false);

             if (get>max) max=get;

          }

          //CASE 2 MY PARENT HATE PARTIES

          else

          {

             int get=0;

             for (int i=0;i<children[parent].size();i++)

             {

                 int joinit=dp(children[parent][i],true);

                 int hateit=dp(children[parent][i],false);

                 if (joinit>hateit) get+=joinit;

                 else get+=hateit;

             }

             if (get>max) max=get;        

          }

          return f[parent][join]=max;

      }

      public:

      Application()

      {

                    //WE WANNA A ROOT, SO WE ADD A NODE 0.

                    cin>>N;

                    happy.resize(N+1);

                    happy[0]=0;

                    for (int i=1;i<=N;i++)

                        cin>>happy[i];

                    children.resize(N+1);

                    vector<bool> haveParent(N+1,false);

                    for (;;)

                    {

                        int L,K;

                        cin>>L>>K;

                        if (L==0&&K==0) break;

                        children[K].push_back(L);

                        haveParent[L]=true;

                    }

                    for (int i=1;i<=N;i++)

                        if (!haveParent[i])

                           children[0].push_back(i);

      }

      int run()

      {

          f.resize(N+1,vector<int>(2,-oo));

          cout<<dp(0,false)<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}