test

(1)修改后的结果
void findSingle(int array[], int n,int reslut[])
{
    unsigned int a,b,c,d;
    int i;
    c = 0;
    for(i = 0;i < n;i++)
    {
        a = array[i];
        c ^= a;
    }

    for(i = 32;i >= 0;i--)
    {
        if(c& 1<< i)
        {
            d = 1<<i;
            break;
        }
    }
    b = 0;
    c = 0;
    for(i = 0;i < n;i++)
    {
        a = array[i];
        if(a&d)
        {
            b ^= a; 
        }
        else
        {
            c ^= a;
        }
    }
    reslut[0] = b;
    reslut[1] = c;
}

啊 哦

题1：
使用类似quick sort的分治法，平均时间复杂度O(N)。
partition函数未经优化
[code=c]

/**
   get the xor value of ints in array
*/
inline int getXOR(int array[],int start,int end){
    int item = 0;
    for(int idx =start;idx < end;idx++) item ^= array[idx];
    return item;
}
/**
   swaps array[i] with array[j]
*/
inline void swap(int array[],int i,int j){
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}
/**
   returns the index of the median of the three indexed ints
*/
inline int midIndex(int array[],int i,int j,int k){
    return array[i] < array[j] ?
          (array[j] < array[k] ? j : array[i] < array[k] ? k : i) :
          (array[j] > array[k] ? j : array[i] > array[k] ? k : i);
}
inline int partition(int array[],int start,int end){
    int len = end - start;
    int low = start,high = end - 1,mid = (start+end)/2;
    if(len > 40){//magic number..
        int dis = len/8;
        low  = midIndex(array,low,    low+dis, low+2*dis);
        mid  = midIndex(array,mid-dis,mid,     mid+dis);
        high = midIndex(array,high-2*dis,high-dis,high);
    }
    mid = midIndex(array,low,mid,high);
    swap(array,start,mid);
    int val = array[start];
    int pos = end;
    for(int idx = end-1;idx > start;idx --){
        if(array[idx] > val){
            swap(array,--pos,idx);
        }
    }
    return pos;
}
void findSingle0(int array[],int start,int end,int result[]){
    int mid = partition(array,start,end);
    if((mid-start)%2 == 1){
        result[0] = getXOR(array,start,mid);
        result[1] = getXOR(array,mid,end);
    }
    else{
        int ts = (mid-start)<(end-mid)?start:mid;
        int te = (mid-start)<(end-mid)?mid:end;
        int ns,ne;
        if(getXOR(array,ts,te) == 0){
            ns = (ts == start?mid:start);
            ne = (te == mid?end:mid);
        }
        else{
            ns = ts;
            ne = te;
        }
        if(ne - ns == 2){
            result[0] = array[ns];
            result[1] = array[ns+1];
        }
        else{
            findSingle0(array,ns,ne,result);
        }
    }
}
void findSingle(int array[],int size,int result[]){
    findSingle0(array,0,size,result);
}

[/code]

/******************************
***********第一题**************
*******************************/
#include<iostream>
using namespace std;
#define N 100000000
int k=0;
void findSingle(int array[], int n,int result[])
{
    
    int i,j;

 for(i=0;i<n;i++)
     {
        j=0;                        //每次从头开始比较
     while(j<n)
     {  
      if(j==i)                  //不与自身比较           
      {
        j++;
        if(j==n)               //最后一个数的比较
        { cout<<"oj"<<endl;
         result[k]=array[n-1];
         k++;
        }
     continue;
    }
               
       if(array[i]!=array[j])
    { 
       if(j==n-1)            //是否比较到最后一个元素 都不相等 ，则记录
        {
           result[k]=array[i];
           k++;
           j++;
         }
       else
        {
            j++;
            continue;
        }                
    }
        else 
    { j=n;
     continue;
           }
     j++;                 
      }
   }     

}
void main()
{
    int n;
    int array[N];
    int result[2];
    cout<<"shu ru n"<<endl;
    cin>>n;
    cout<<"输入n个数"<<endl;
    for(int i=0;i<n;i++)
      cin>>array[i];
   findSingle( array, n, result);

 cout<<"出现一次的数："<<endl;
   for( i=0;i<k;i++)
       cout<<result[i]<<"  ";
   cout<<endl;
   
}



******************************************/
/*****************************************
******************第二题*****************/
#include<iostream>
#include<string> 
using namespace std;

int MaxPaobing(char landform[][10],int n,int m)
{
    int K=0,i,j;

        if(m<=n)                         //T表示可以部署的炮兵军队
            for(i=1;i<=m;i++)
                landform[i][i]='T';
        else
            for(i=0;i<=n;i++)
                landform[i][i]='T';
    for( i=1;i<=n;i++)
    {
        for( j=1;j<=m;j++)
        {
            if(landform[i][j]=='p')
            {
              if(landform[i][j-1]=='T'||landform[i-1][j]=='T')
              
                    continue;    
            else                
                {
                    landform[i][j]='T';
                    continue;
                }
            }
            else 
                continue;
        }
    }
for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        if(landform[i][j]=='T')
            K++;
        cout<<endl;
    }

cout<<"部署后的地形图，T表示部署的炮兵军队"<<endl;
for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            cout<<landform[i][j]<<"  ";
        cout<<endl;
    }
    return K;
}

void main()
{
    int n,m,i,j;
    char landform[100][10]={0};
    cout<<"输入行数N,列数M"<<endl;
    cin>>n>>m;
    cout<<"输入地形P或H"<<endl;
    for(i=1;i<=n;i++)
    {
        cout<<"输入第"<<i<<"行"<<endl;
        for( j=1;j<=m;j++)
            cin>>landform[i][j];
    }

    cout<<endl<<"此地型图为:"<<endl;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            cout<<landform[i][j]<<"  ";
        cout<<endl;
    }
     int K=MaxPaobing( landform,n,m);
     cout<<"此地型最多可部署的炮兵部队="<<K<<endl;
}

//vc6.0
#include<stdio.h>
#include<malloc.h>
void drawmap();
int calcucost(int i,int j);
void putpoint();
void printfmap();
int * mapdata,* mapbackup,n,m,mincost,total,flag;
main()
{
    int i,j,temp;
    printf("input:");
    scanf("%d%d",&n,&m);
    mapdata=(int *)malloc(sizeof(int)*n*m);
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            scanf("%d",&temp);
            if(temp==0)
                mapdata[i*m+j]=0;
            else
                mapdata[i*m+j]=-1;
        }
        getchar();
    }
    mapbackup=(int *)malloc(sizeof(int)*n*m);
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
            mapbackup[i*m+j]=mapdata[i*m+j];
    }
    while(1)
    {
        drawmap();
        if(flag)
            break;
        putpoint();
    }
    printf("%d\n",total);
    printfmap();
}
void drawmap()
{
    mincost=m*n+1;
    int i,j;
    flag=1;
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            if(mapbackup[i*m+j]!=-1&&mapbackup[i*m+j]!=-2)
            {
                mapbackup[i*m+j]=calcucost(i,j);
                mincost=(mincost>mapbackup[i*m+j]?mapbackup[i*m+j]:mincost);
                flag=0;
            }
        }
    }
}
int calcucost(int i,int j)
{
    int t,cost=0,p,q;
    for(t=1;t<=8;t++)
    {
        p=i+((3-t+t/5*4)%2)*(t/5+1);
        q=j+((2-t+t/5*4)%2)*(t/5+1);
        if(p<0||p>=n||q<0||q>=m||mapbackup[p*m+q]==-1||mapbackup[p*m+q]==-2)
            ;
        else
            cost++;
    }
    return cost;
}
void putpoint()
{
    int i,j,t,p,q;
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            if(mapbackup[i*m+j]==mincost)
            {
                for(t=1;t<=8;t++)
                {
                    p=i+((3-t+t/5*4)%2)*(t/5+1);
                    q=j+((2-t+t/5*4)%2)*(t/5+1);
                    if(p<0||p>=n||q<0||q>=m||mapbackup[p*m+q]==-1||mapbackup[p*m+q]==-2)
                        ;
                    else
                        mapbackup[p*m+q]=-1;
                }
                mapbackup[i*m+j]=-2;
                total++;
                return ;
            }
        }
    }
}
void printfmap()
{
    int i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            if(mapdata[i*m+j]==0)
            {
                if(mapbackup[i*m+j]==-2)
                    printf("p ");
                else
                    printf("0 ");
            }
            else if(mapdata[i*m+j]==-1)
                printf("* ");
        }
        putchar('\n');
    }
}
貌似不太方便看 我说一下我的思路吧
地图的初始值代表 >=0代表可以放坦克的地方 <0代表不可以放坦克的地方（如山地，其他坦克的攻击范围内）
while 仍然有可以放坦克的地方
{依次把地图中可以放坦克的地方的cost（在该点放置坦克会占据周围原本可以放坦克的地方的个数）计算并储存 记下cost的最小值mincost
在地图中的第一个cost为mincost的点放置坦克 （赋值为-2）把其射程内的点赋值-1表示不可放坦克
然后继续上一步
}


我没有对代码进行优化 有点长

第一题：
#include <vector>
#include <assert.h>
void findSingle(int array[], int n,int reslut[])
{
    std::vector <int*> tempArrayV ;
    std::vector<int*>::iterator it ;
    bool norepeat = true ;
    for ( int iCount = 0 ; iCount < n ; ++iCount )
    {
        norepeat = true ;
        for ( it = tempArrayV.begin() ; it != tempArrayV.end() ; ++it )
        {
            if ( *(*it) == array[iCount] )
            {
                tempArrayV.erase(it) ;
                norepeat = false ;
                break ;
            }
        }
        if ( norepeat )
        {
            tempArrayV.push_back( &array[iCount] );
        }
    }
    assert( tempArrayV.size() == 2 ) ;
    reslut[0] = *tempArrayV[0];
    reslut[1] = *tempArrayV[1];
}
第二题：
#include <iostream>
#include <stdio.h>
#include <vector>
#include <conio.h>
using namespace std;
class MapNode
{
public:
    MapNode();
    ~MapNode(){};
    void SetLandform(char landform){ m_landform = landform ;}
    char GetLandform(){ return m_landform;}
    void SetCannon(bool isHaveCannon=true){m_isHaveCannon=isHaveCannon;}
    bool IsHaveCannon(){return m_isHaveCannon;}
private :
    bool m_isHaveCannon ;//是否有炮
    char m_landform ;//地形
};
MapNode::MapNode():m_isHaveCannon(false)
,m_landform('p')
{
}
class Map
{
public:
    Map(){}
    Map(int iLine ,int iRow );
    ~Map(){}
    void SetLandform(char* landform);
    void ShowConnon();
    void SetConnon( int iFlag ,std::vector <MapNode>& tempMapV );
    void SetConnonAthwart( int iFlag ,std::vector <MapNode>& tempMapV );
    int GetMaxConnonNum(){return m_iMaxConnonNum;}
protected:
    bool IsNoCInBound(int iFlag ,std::vector <MapNode>& mapV);
private:
    int m_iLine ;
    int m_iRow ;
    std::vector <MapNode> m_vMap ;
    std::vector <MapNode> m_vTempMap ;
    int m_iMaxConnonNum ;
};
Map::Map(int iLine,int iRow):m_iLine(iLine)
,m_iRow(iRow)
,m_iMaxConnonNum(0)
{
}
void Map::SetLandform(char* landform)
{
    MapNode mapNode ;
    int iCount = 0 ;
    while( *landform != '\0' && iCount < m_iRow )
    {
        mapNode.SetLandform( *landform ) ;
        m_vMap.push_back(mapNode) ;
        ++iCount ;
        ++landform ;
    }
}
bool Map::IsNoCInBound(int iFlag ,std::vector <MapNode>& mapV)
{
    int iRow = iFlag%m_iRow ;
    int iLine = iFlag/m_iRow ;
    if ( iLine - 1 >= 0 && mapV[(iLine-1)*m_iRow+iRow].IsHaveCannon() )
    {
        return false ;
    }
    if ( iLine - 2 >= 0 && mapV[(iLine-2)*m_iRow+iRow].IsHaveCannon() )
    {
        return false ;
    }
    if ( iRow - 1 >= 0 && mapV[iLine*m_iRow+iRow-1].IsHaveCannon() )
    {
        return false ;
    }
    if ( iRow - 2 >= 0 && mapV[iLine*m_iRow+iRow-2].IsHaveCannon() )
    {
        return false ;
    }
    if ( iLine + 1 < m_iLine && mapV[(iLine+1)*m_iRow+iRow].IsHaveCannon() )
    {
        return false ;
    }
    if ( iLine + 2 < m_iLine && mapV[(iLine+2)*m_iRow+iRow].IsHaveCannon() )
    {
        return false ;
    }
    if ( iRow + 1 < m_iRow && mapV[iLine*m_iRow+iRow+1].IsHaveCannon() )
    {
        return false ;
    }
    if ( iRow + 2 < m_iRow && mapV[iLine*m_iRow+iRow+2].IsHaveCannon() )
    {
        return false ;
    }
    return true ;
}

void Map::SetConnon( int iFlag ,std::vector <MapNode>& tempMapV )
{
    int iConnonNum = 0 ;
    tempMapV = m_vMap ;
    int i ;
    for (  i = iFlag ; i < m_iLine*m_iRow ; ++i )
    {
        if ( (tempMapV[i].GetLandform() == 'P'|| tempMapV[i].GetLandform() == 'p')&& IsNoCInBound(i,tempMapV))
        {
            tempMapV[i].SetCannon() ;
            ++iConnonNum;
        }
    }
    for ( i = iFlag - 1 ; i >= 0 ; --i )
    {
        if ( (tempMapV[i].GetLandform() == 'P'|| tempMapV[i].GetLandform() == 'p')&& IsNoCInBound(i,tempMapV))
        {
            tempMapV[i].SetCannon() ;
            ++iConnonNum;
        }
    }
    if ( m_iMaxConnonNum < iConnonNum )
    {
        m_iMaxConnonNum = iConnonNum ;
        m_vTempMap = tempMapV ;
    }
}
void Map::SetConnonAthwart( int iFlag ,std::vector <MapNode>& tempMapV )
{
    int iConnonNum = 0 ;
    tempMapV = m_vMap ;
    int i ;
    for ( i = iFlag ; i >= 0 ; --i )
    {
        if ( (tempMapV[i].GetLandform() == 'P'|| tempMapV[i].GetLandform() == 'p')&& IsNoCInBound(i,tempMapV))
        {
            tempMapV[i].SetCannon() ;
            ++iConnonNum;
        }
    }
    for (  i = iFlag + 1 ; i < m_iLine*m_iRow ; ++i )
    {
        if ( (tempMapV[i].GetLandform() == 'P'|| tempMapV[i].GetLandform() == 'p')&& IsNoCInBound(i,tempMapV))
        {
            tempMapV[i].SetCannon() ;
            ++iConnonNum;
        }
    }
    if ( m_iMaxConnonNum < iConnonNum )
    {
        m_iMaxConnonNum = iConnonNum ;
        m_vTempMap = tempMapV ;
    }
}
void Map::ShowConnon()
{
    cout<<endl ;
    for ( int iLine = 0 ; iLine < m_iLine ; ++iLine )
    {
        for ( int iRow = 0 ; iRow < m_iRow ; ++iRow )
        {
            if ( m_vTempMap[iLine*m_iRow+iRow].IsHaveCannon())
            {
                cout<<"T" ;
                continue ;
            }
            cout<<m_vTempMap[iLine*m_iRow+iRow].GetLandform() ;
        }
        cout<<endl ;
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    int iLine = 0 ;
    int iRow = 0 ;
    cout<<"输入行数:" ;
    cin>>iLine ;
    cout<<endl ;
    cout<<"输入列数:";
    cin>>iRow ;
    cout<<endl;
    cout<<"输入地图数据:";
    cout<<endl;
    Map map(iLine,iRow);
    int iCount = 0 ;
    char * tempStr = new char[iRow+1];
    while ( iCount < iLine )
    {
        ++iCount ;
        cin>>tempStr ;
        map.SetLandform( tempStr );
    }

    if ( NULL != tempStr )
    {
        delete tempStr ;
        tempStr = NULL ;
    }

    std::vector <MapNode> tempMapV;
    for ( int iFlag = 0 ; iFlag < iLine*iRow ; ++iFlag)
    {
        map.SetConnon( iFlag , tempMapV ) ;
        map.SetConnonAthwart( iFlag , tempMapV );
    }
    cout<<"该地图上最多可部署"<<map.GetMaxConnonNum()<<"门大炮!"<<endl;
    map.ShowConnon();
    getch();
    return 0 ;
}

看看高手们的回复

菜鸟也来试试看,我这网通用户还真不是一般的慢啊
第一题:
void findSingle(int array[], int n, int result[])
{
    int temp = 0;
    int flag = 0; 
    int *pArray = array;
    int arrayLen = n;

    while(1)
    {
        result[0] = 0;
        result[1] = 0;  
        flag = rand()%arrayLen;
        
        for(int i=0; i<arrayLen; i++)
        {
            if(*(pArray+i) < *(pArray+flag))
            {
                temp = *(pArray+flag);
                *(pArray+flag) = *(pArray+i);
                *(pArray+i) = temp;
                flag = i;
            }     
        }
        for(int i=0; i<flag; i++)
            result[0] ^= *(pArray+i);
        for(int i=flag; i<n; i++)
            result[1] ^= *(pArray+i);
            
        if(result[0] != 0 && result[1] != 0)
            return;
        if(result[0] == 0) 
        {
            pArray = array+flag;
            arrayLen = n-flag;
        }
        if(result[1] == 0)
            arrayLen = flag;                   
    }        
}