Gym 101911F “Tickets”

传送门

题意：

　　给你一个由六位数字组成的门票编码x，并定义F(x) = | 前三位加和 - 后三位加和|；

　　求出给定的门票编码 x 之前并且 F(i) < F(x) 的 i 的总个数。

题解：

　　为方便描述，先定义一个虚拟的数组 a[ i ][ j ] : 表示前 i 个数中，经过 F() 函数映射成数 j 的整数的总个数；

　　首先，我先将门票编码转化成整数，然后按升序排列。

　　从 0 开始便利所有的整数 num，对于某个整数 num ，判断当前的 num 是否 == 某一门票编码x，如果等于，

　　那么在x之前并且经F()映射后值小于F(x)的整数的总个数为 Σ(a[ i ][ 0 ] + a[ i ][ 1 ] + a[ i ][ F(x)-1 ])，其中 0 ≤ i < x ；

　　当然，为了提高求和效率，我使用了树状数组来存储答案，具体细节看代码；

AC代码：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<algorithm>
  5 using namespace std;
  6 #define lowbit(x) (x&-x)
  7 const int maxn=2e5+50;
  8 
  9 int n;
 10 struct Date
 11 {
 12     int val;
 13     int id;
 14     int ans;
 15 }_date[maxn];
 16 struct BIT
 17 {
 18     int bit[50];
 19     void Add(int t)
 20     {
 21         while(t < 50)
 22         {
 23             bit[t]++;
 24             t += lowbit(t);
 25         }
 26     }
 27     int Sum(int t)
 28     {
 29         int sum=0;
 30         while(t > 0)
 31         {
 32             sum += bit[t];
 33             t -= lowbit(t);
 34         }
 35         return sum;
 36     }
 37 }_bit;
 38 int Trans(char *s)
 39 {
 40     return (s[0]-'0')*100000+(s[1]-'0')*10000+
 41            (s[2]-'0')*1000+(s[3]-'0')*100+
 42            (s[4]-'0')*10+(s[5]-'0');
 43 }
 44 int F(int val)
 45 {
 46     int sum=0;
 47     int index=1;
 48     while(index <= 3 && val)
 49     {
 50         sum += val%10;
 51         val /= 10;
 52         index++;
 53     }
 54     while(val)
 55     {
 56         sum -= val%10;
 57         val /= 10;
 58     }
 59     return abs(sum);
 60 }
 61 
 62 bool cmp1(Date _a,Date _b)
 63 {
 64     return _a.val < _b.val;
 65 }
 66 bool cmp2(Date _a,Date _b)
 67 {
 68     return _a.id < _b.id;
 69 }
 70 
 71 void Solve()
 72 {
 73     sort(_date+1,_date+n+1,cmp1);
 74     int index=1;
 75     int zero=0;
 76 
 77     for(int i=0;index <= n;++i)
 78     {
 79         int x=F(i);
 80         int val=_date[index].val;
 81 
 82         //处理某一门票编码出现多次的情况
 83         while(val == i && index <= n)
 84         {
 85             int t=F(val);//将val映射为F(val)
 86             _date[index].ans=_bit.Sum(t-1)+(t > 0 ? zero:0);
 87             index++;
 88             val=_date[index].val;
 89         }
 90 
 91         //因为树状数组不能处理0，所以0单独用变量zero记录
 92         if(x == 0)
 93             zero++;
 94         else
 95             _bit.Add(x);
 96     }
 97     sort(_date+1,_date+n+1,cmp2);
 98 
 99     for(int i=1;i <= n;++i)
100         printf("%d
",_date[i].ans);
101 }
102 int main()
103 {
104     scanf("%d",&n);
105     for(int i=1;i <= n;++i)
106     {
107         char s[10];
108         scanf("%s",s);
109         _date[i].val=Trans(s);//将字符串 s 转化为整数
110         _date[i].id=i;
111 
112     }
113     Solve();
114 
115     return 0;
116 }

View Code