USACO 3.1 Contact-白红宇

USACO 3.1 Contact

阅读量：4444 次

发布时间：2019-06-07

本文共 4487 字，大约阅读时间需要 14 分钟。

http://www.nocow.cn/index.php/Translate:USACO/contact

题目大意：给一个只含0和1的序列，统计每个子序列的重复次数，并按次数递减来输出

考虑子序列时将序列前面加一个'1'然后转化成二进制整数，这样每个子序列与整数一一对应，统计二进制整数出现次数，按要求输出即可（ps：usaco老是喜欢在输出上做文章）代码如下（未提交）：

1 /**********************************************  2 ***    Problem:  3 ***    Author:        JKL  4 ***    University:    CSUST  5 ***    Team:          __Dream  6 ***    Email:          1451108308@QQ.COM  7 ***    My Blog:        http://www.cnblogs.com/jklongint/  8 ***********************************************/  9 //=================================================== 10 #include 
      
        11 #include 
       
         12 #include 
        
          13 #include 
         
           14 #include 
          
            15 #include 
           
             16 #include 
            
              17 #include 
             
               18 #include 
              
                19 #include 
               
                 20 #include 
                
                  21 #include 
                 
                   22 #include 
                  
                    23 #include 
                   
                     24 #include 
                    
                      25 #include 
                      26 #include 
                      
                        27 #include 
                       
                         28 #include 
                        
                          29 #include 
                         
                           30 #include 
                          
                            31 using namespace std; 32 //--------------------------------------------------- 33 #define mem(a,b) memset(a,b,sizeof(a)) 34 #define GO cout<<"HelloWorld!"<
                           
                            = 1; i--) 38 #define fin freopen("input.txt","r",stdin); 39 #define fout freopen("output.txt","w",stdout) 40 #define lson l, m, rt << 1 41 #define rson m + 1, r, rt << 1 | 1 42 43 #define sqr(a) ((a)*(a)) 44 #define abs(a) ((a>0)?(a):-(a)) 45 #define pii pair
                            
                              46 47 #define fmax(a,b) max(a,b) 48 #define fmin(a,b) min(a,b) 49 #define fmax3(a,b,c) (fmax(a,fmax(a,b))) 50 #define fmin3(a,b,c) (fmin(a,fmin(a,b))) 51 52 #define sfi(x) scanf("%d",&x) 53 #define sfL(x) scanf("%I64d",&x) 54 #define sfc(x) scanf("%c",&x) 55 #define sfd(x) scanf("%lf",&x) 56 #define sfs(x) scanf("%s",x) 57 #define sfii(a,b) scanf("%d%d",&a,&b) 58 #define sfLL(a,b) scanf("%I64d%I64d",&a,&b) 59 #define sfcc(a,b) scanf("%c%c",&a,&b) 60 #define sfdd(a,b) scanf("%lf%lf",&a,&b) 61 #define sfss(a,b) scanf("%s%s",a,b) 62 63 #define pfi(x) printf("%d",x) 64 #define pfL(x) printf("%I64d",x) 65 #define pfs(x) printf("%s",x) 66 #define pfd(x) printf("%lf",x) 67 #define pfc(x) print("%c",x) 68 #define newLine pfs("\n") 69 #define space pfs(" ") 70 71 //-------------------------------------------------------- 72 typedef __int64 LL; 73 typedef unsigned long long ULL; 74 //typedef __int64 __LL; 75 typedef unsigned __int64 __ULL; 76 77 typedef vector
                             
                               vi; 78 typedef vector
                              
                                vL; 79 typedef vector
                               
                                 vs; 80 typedef set
                                
                                  si; 81 typedef map
                                 
                                   mii; 82 typedef map
                                  
                                    mLL; 83 typedef map
                                   
                                     msi; 84 typedef map
                                    
                                      mci; 85 //-------------------------------------------------------- 86 const int dx[4]={ 1,-1,0,0}; 87 const int dy[4]={ 0,0,1,-1}; 88 const int day[13]={ 0,31,28,31,30,31,30,31,31,30,31,30,31}; 89 const int N6=1000006; 90 const int N5=100006; 91 const int N4=10006; 92 const int N3=1006; 93 const int N2=106; 94 const int N=200009; 95 const int MOD=1000000007; 96 const LL LMAX=0x7fffffffffffffff; 97 const LL IMAX=0x3fffffff; 98 const double PI=3.14159265359; 99 //--------------------------------------------------------100 template< class T > T gcd(T a, T b) { return (b != 0 ? gcd
                                     
                                      (b, a%b) : a); }101 template< class T > T lcm(T a, T b) { return (a / gcd
                                      
                                       (a, b) * b); }102 103 //------------------------------------------------------------104 struct TreeNode{105 LL sum;106 };107 struct Node{108 int id, s;109 };110 char sbuf[20];111 //=================================================================112 Node node[N4];113 int cnt[N4], f[N4];114 char s[N];115 int getState(int n, int len)116 {117 int c = 1;118 foru(i, len) c = c * 2 + s[n + i- 1] - 48;119 return c;120 }121 char *getString(int a)122 {123 int c = 0;124 mem(sbuf, 0);125 while(a > 0){126 sbuf[c++] = (a & 1) + 48;127 a = a >> 1;128 }129 c--;130 sbuf[c] = 0;131 int cc = c / 2, l = 0;132 c--;133 foru(i, cc){134 swap(sbuf[l++], sbuf[c--]);135 }136 return sbuf;137 }138 int cmp(Node i, Node j)139 {140 return i.s > j.s || i.s == j.s && i.id < j.id;141 }142 int main()143 {144 //fin;145 //fout;146 //freopen("contact.in","r",stdin);147 //freopen("contact.out","w",stdout)148 int a, b, n;149 cin>> a>> b>> n;150 sfs(s);151 int len = strlen(s);152 for(int i = len - 1; i >= 0; i--){153 for(int j = a; j <= b; j++){154 if(i + j > len)break;155 int t = getState(i, j);156 f[t] ++;157 }158 }159 int m = (1 << (b + 1)) - 1, q = b + 1;160 foru(i, m){161 node[i].s = f[i];162 node[i].id = i;163 }164 sort(node + 1, node + 1 + m, cmp);165 //foru(i, m)cout<
                                       
                                        <
                                        
                                          n)break;171 if(i > 1)cout<

View Code

转载于:https://www.cnblogs.com/jklongint/p/3892033.html

你可能感兴趣的文章