2017-3-25 360C++笔试

第二题：偶串

#include <bits/stdc++.h>
int arr[100010];
char str[100010];
int _hash(char c){
    return 1<<(c-'0');
}
int main()
{
      scanf("%s",str);
      int n = strlen(str);
      for(int i = 1 ; i <= n ; i ++)
      {
            arr[i] = arr[i-1]^_hash(str[i-1]);
      }
      std::sort(arr,arr+n+1);
      long long sum = 0,cnt = 1;
      for(int i = 1 ; i <= n ; i ++)
            if(arr[i] == arr[i-1]) cnt ++;
              else{
                  sum += cnt*(cnt-1)/2;
                  cnt = 1;
            }
      sum += cnt*(cnt-1)/2;
      printf("%lld\n",sum);
      return 0;
}

第三题：任务列表

#include <bits/stdc++.h>
using namespace std;
int ti[100100];
int qi[100100];
int all[400100],top = 0;
int rest[400100];
int mx = 0;
void init()
{
    int temp = 1;
    for(int i = 1 ; i < top ; i ++)
        if(all[i] != all[i-1])
            all[temp++]=all[i];
    top = temp;
}
int _hash(int x){
    int l = 0,r = top-1;
    while(l<=r){
        int mid = (l+r)/2;
        if(all[mid] == x) return mid;
        if(all[mid] > x) r = mid - 1;
        else l = mid + 1;
    }
    return 0;
}
int r_hash(int x){
    if(x == -1) return mx+1;
    return all[x];
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);

    for(int i = 0; i < n ; i ++)
    {
          scanf("%d",&ti[i]);
          all[top++] = ti[i];
          all[top++] = ti[i]+1;
          if(ti[i]>mx)mx = ti[i];
    }
    sort(ti,ti+n);
    for(int i = 0 ; i < m ; i ++){
        scanf("%d",&qi[i]);
        all[top++] = qi[i];
        all[top++] = qi[i]+1;
        if(qi[i]>mx)mx = qi[i];
    }
    sort(all,all+top);
    init();
    for(int i = 0 ; i < n ; i ++)
        ti[i] = _hash(ti[i]);
    for(int i = 0 ; i < m ; i ++)
        qi[i] = _hash(qi[i]);
    int temp = 0;
    memset(rest,-1,sizeof(rest));
    for(int i = 0 ; i < top ; i ++)
    {
        if(ti[temp] == i){
            temp++;
        }else{
            rest[i] = i;
        }
    }
    temp = -1;
    for(int i = top-1 ; i >= 0 ;i --)
    {
        if(rest[i] != -1) temp = i;
        rest[i] = temp;
    }
    for(int i = 0 ; i < m ; i ++)
        printf("%d\n",r_hash(rest[qi[i]]));
    return 0;
}