Codeforces Round #186 (Div. 2)

A 題水題,如果n<0刪除最後一位或倒數第二位的數，找數最大的刪除！

[cpp] 
#include <cstdio>  
#include <algorithm>  
 
using namespace std; 
 
int main() 
{ 
    int n,ans; 
    scanf("%d",&n); 
    if(n>=0) printf("%d\n",n); 
    else 
    { 
        n=-n; 
        ans=-(n/100*10+min(n%10,n/10%10)); 
        printf("%d\n",ans); 
    } 
    return 0; 
} 

#include <cstdio>
#include <algorithm>

using namespace std;

int main()
{
 int n,ans;
 scanf("%d",&n);
 if(n>=0) printf("%d\n",n);
 else
 {
  n=-n;
  ans=-(n/100*10+min(n%10,n/10%10));
     printf("%d\n",ans);
 }
 return 0;
}
 

B 題給你一個字符串判斷在{L,R) 區間內 si = si + 1.的個數，水水的遍歷就好。

[cpp] 
#include <cstring>  
#include <string>  
#include <cstdio>  
#include <iostream>  
 
using namespace std; 
 
const int maxn =100000 +10; 
 
int ans[maxn],m; 
 
int main() 
{ 
    string s; 
    cin>>s; 
    ans[0]=0; 
    for(int i=1;i<s.length();i++) 
        ans[i]=ans[i-1]+(s[i-1]==s[i]); 
    scanf("%d",&m); 
    while(m--) 
    { 
        int l, r;  
        scanf("%d %d",&l,&r); 
        printf("%d\n",ans[r-1]-ans[l-1]); 
    } 
    return 0; 
} 

#include <cstring>
#include <string>
#include <cstdio>
#include <iostream>

using namespace std;

const int maxn =100000 +10;

int ans[maxn],m;

int main()
{
 string s;
 cin>>s;
 ans[0]=0;
 for(int i=1;i<s.length();i++)
     ans[i]=ans[i-1]+(s[i-1]==s[i]);
 scanf("%d",&m);
 while(m--)
 {
  int l, r;
  scanf("%d %d",&l,&r);
  printf("%d\n",ans[r-1]-ans[l-1]);
 }
 return 0;
}

 C題  給你4^n個數，讓你放進那個2^n * 2^n的矩陣裡讓這個矩陣beauty值最大，beauty值的計算方法題裡說了。。。

The beauty of a 2n × 2n-sized matrix is an integer, obtained by the following algorithm:

Find the maximum element in the matrix. Let's denote it as m.
If n = 0, then the beauty of the matrix equals m. Otherwise, a matrix can be split into 4 non-intersecting 2n - 1 × 2n - 1-sized submatrices, then the beauty of the matrix equals the sum of number m and other four beauties of the described submatrices.

As you can see, the algorithm is recursive.

貪心吧，貪心就行，排個序解決了~

[cpp] 
#include <cstdio>  
#include <iostream>  
#include <algorithm>  
 
using namespace std; 
 
const int maxn = 2000000 + 10 ; 
 
typedef long long LL; 
 
LL a[maxn]; 
 
bool cmp(LL a,LL b) 
{ 
    return a>b; 
} 
 
int main() 
{ 
    int n; 
    while(~scanf("%d",&n)) 
    { 
        LL sum=0; 
        for(int i=0;i<n;i++) 
            scanf("%lld",&a[i]); 
        sort(a,a+n,cmp); 
        while(n) 
        { 
            for(int i=0;i<n;i++) 
              sum+=a[i]; 
            n/=4; 
        } 
        printf("%lld\n",sum); 
    } 
    return 0; 
}  

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 2000000 + 10 ;

typedef long long LL;

LL a[maxn];

bool cmp(LL a,LL b)
{
 return a>b;
}

int main()
{
 int n;
 while(~scanf("%d",&n))
 {
  LL sum=0;
  for(int i=0;i<n;i++)
      scanf("%lld",&a[i]);
  sort(a,a+n,cmp);
  while(n)
  {
   for(int i=0;i<n;i++)
     sum+=a[i];
   n/=4;
  }
  printf("%lld\n",sum);
 }
 return 0;
}