SRM 545 DIV2

SRM 545

250pt

題意：給定一組數，求這組數中是否存在一個數等于所有其它的數按位與(&)的值。

分析：因為a&b<=min(a,b)h和a&a=a,是以就是求這組數所有的數按位與之後的是否等于最小值。

View Code

class ANDEquation 
{ 
        public: 
        int restoreY(vector <int> A) 
        { 
                int i,m,k,n=A.size();
                m=*max_element(A.begin(),A.end());
                for(k=0,i=1;i<n;i++)
                    if(A[i]<A[k])
                        k=i;
                  for(i=0;i<n;i++)
                      if(i!=k)
                          m&=A[i];
                return m==A[k]?m:-1;        
        } 
        
 
};       

550pt

題意：給定一個字元串S，minRev和n，求逆序數不小于minRev，字典序不小于S和由前n個小寫字母組成的字元串T.

分析：因為字典序要大于S,是以考慮在補全S字元的基礎上交換字母的位置來增加逆序數

如果s的字典序不小于minRev，那s就是答案。

否則貪心，對于長度為n的字母組成的字元串，逆序數最大為n*(n-1)/2;

因為要使T字典序最小，是以從要末尾開始修改，修改的位數越多，可增加的逆序數也越多。

PS.在類中自定義比較函數時要放到類外

View Code

int Cmp(char a,char b)
{
    return a>b;
}

class StrIIRec 
{ 
        public:
        string recovstr(int n, int minInv, string s) 
        { 
            int i,j,k,m,rev[22]={0};
            bool used[22]={false};
            m=(int)s.size();
            for(i=0;i<m;i++)
                   used[s[i]-'a']=true;
               for(i=0;i<n;i++)
                   if(!used[i])
                       s.push_back('a'+i);
            for(i=n-2;i>=0;i--)
            {
                for(j=i+1;j<n;j++)
                       if(s[i]>s[j])
                       rev[i]++;
                   rev[i]+=rev[i+1];
            }
            m=rev[0];
            if(m>=minInv)
                   return s;
            for(i=n-2;i>=0;i--)
                   if(m-rev[i]+(n-i)*(n-i-1)/2>=minInv)
                       break;
            k=minInv-m+rev[i]-(n-i-1)*(n-i-2)/2;
            sort(s.begin()+i,s.end(),Cmp);
            swap(s[i],s[n-1-k]);
            sort(s.begin()+i+1,s.end(),Cmp);
            return s;
        } 
        

 
};       

1000pt

題意：給定一張長為L+1,高為H+1的網格圖,求符合下列條件的集合有多少種

1，包含K個格點

2，K個點必須在一條直線上;

3，有且僅有一個點的高度為0;

分析：枚舉步差步差來代表某個集合，用最大公約數判斷是否是最小步差，即集合是否枚舉過

 PS:有O(L*H)算法，沒看懂

View Code

#define MAX 1000000007

class SpacetskE 
{ 
        public:
        int gcd(int a,int b)
        {
            return b?gcd(b,a%b):a;
        }
        int countsets(int L, int H, int K) 
        { 
            int i,j,n,m,a,b,x2,x1,y2;
            int c[222][222]={0};
            for(i=0;i<222;i++)
                c[i][0]=c[i][i]=1;
            for(i=2;i<222;i++)
                for(j=1;j<=i;j++)
                    c[i][j]=(c[i-1][j-1]+c[i-1][j])%MAX;
            if(K==1)
                return (L+1)*(H+1);
            for(m=i=0;i<=L;i++)
                m=(m+c[H+1][K])%MAX;
            for(x1=0;x1<=L;x1++)
                for(x2=0;x2<=L;x2++)
                    if(x1!=x2)
                        for(y2=1;y2<=H;y2++)
                        {
                            a=abs(x2-x1);
                            b=y2;
                            if(gcd(a,b)>1)
                                continue;
                            if(x2>x1)
                                n=min((L-x1)/a,H/b);
                            else
                                n=min(x1/a,H/b);
                            n++;
                            if(K<=n)
                                m=(m+c[n][K])%MAX;
                        }
            return m;
        }   
};       

轉載于:https://www.cnblogs.com/xchaos/archive/2012/06/15/2550486.html