寒假菜鸟先飞系列赛题目选讲

第1场 Prob 07

s[a] + s[b] + s[c] == s[d]
看到这个东西，一般尝试采用套路：meet in the middle（中间相遇法）
具体来说，枚举所有s[a]+s[b]，统计每种可能的结果有几个组合方式
然后枚举s[d]-s[c]（把s[c]移项即可得到），去前面s[a]+s[b]的统计结果中找。

这样，你暴力的枚举O($n^4$)，变成了O($n^2$+$n^2 \times x$)，这个x取决于查找方式

注意到$0<=s[i]<=100000$，那么$0<=s[a]+s[b]<=200000$
20万啊，好小啊，我们开个int数组 int count[200001]，直接计数，然后再枚举s[d]-s[c]，去找，就行了。

这样，这个查找方式是O(1)的，于是总体时间复杂度就是O($n^2$)

int arr[1005];
int cnt[200005];
int main(){
    int T,n;
    for(scanf("%d",&T);T--;){
        scanf("%d",&n);
        memset(cnt,0,sizeof(cnt));
        for(int i=0;i<n;i++)scanf("%d",&arr[i]);
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cnt[arr[i]+arr[j]]++;
            }
        }
        ll ans=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(arr[i]-arr[j]>=0)
                    ans+=cnt[arr[i]-arr[j]];
            }
        }
        out(ans);puts("");
    }
    return 0;
}

第2场 Prob 03

我没试过暴力，但是记得hdoj上有个题，类似的，找这种可以循环移位的串的最小表示（给cab，输出abc，反正移位方法和这题一样的），我是瞎剪枝的暴力搞过去的。

反正你们这里很多人说暴力过了，我也不管了。
但是正解一定要说一句：
这种 循环字符串的最小表示法的问题 ，是有优秀的算法的，时间复杂度O(n)。
说实话，我也不会推导，但是加入你的模板是没错的。

具体做法，请参考博客：
http://blog.csdn.net/cclsoft/article/details/5467743
反正，用上述做法，找出2个字符串的最小表示，然后比较大小，输出比较结果，完事。

第2场 Prob 04

推荐前置知识：广度优先搜索（BFS）、拓扑排序

然后其实我的idea的确脱胎于拓扑排序：
在类bfs实现拓扑排序的时候，我们当一个点未访问的前置点个数为0（或者说，删点和相应的边以后，某个点在新图中的入度为0）的时候，加入拓扑序列，把这个点删去。

那么这里也是类似的道理：
我们开一个数组，统计每个人有多少种球的数量<=Watano 手中相应种类的球的个数。当种类数==K的时候，这个人可以离场，把所有的球都给Watano 了。

那么现在的主要矛盾点是，怎么快速的知道，一个人的一种球的数量，< Watano手上的相应的求的数量呢？

不妨采取以下方法：
对每种球，记录球的数量，和相应的人的id，然后按球的数量从小到大排序。
同时每种球，维护一个“指针”，记录之前已经知道有多少个人手上的，这种球的数量小于Watano所有的了。

那么，一开始，我们就推进所有种类求的“指针”，相应的更新那个人有多少种球的数量<=Watano 手中相应种类的球的个数，这样有一些人就要给出他手上的所有球了。这些人加入队列，然后每个人给出球，继续往后推指针，直到队列里没人为止。

时间复杂度：上面有个排序，$Kn \log n$，然后对每人每种球，只会扫过一次，$Kn$，所以整体时间复杂度$O(Kn \log n)$

所以啊，代码有点长……

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
template <class T>
inline void scan(T &ret) {
    char c; ret=0;
    while((c=getchar())<'0'||c>'9');
    while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar();
}
int n,K;
int d[10005][11];
int cnt[10005];
struct Pair{
    Pair(){}
    Pair(int a,int b):val(a),idx(b){}
    int val,idx;
    bool operator<(const Pair&b)const{
        return val<b.val;
    }
}p[11][10005];
int pt[11];
int main(){
    while(~scanf("%d%d",&n,&K)){
        for(int i=0;i<K;i++)scan(d[0][i]);
        for(int i=1;i<=n;i++){
            cnt[i]=0;
            for(int j=0;j<K;j++){
                scan(d[i][j]);
                p[j][i-1]=Pair(d[i][j],i);
            }
        }
        for(int j=0;j<K;j++)sort(p[j],p[j]+n);
        queue<int> q;
        memset(pt,0,sizeof(pt));
        for(int j=0;j<K;j++){
            while(pt[j]<n&&p[j][pt[j]].val<d[0][j]){
                int y=p[j][pt[j]].idx;
                cnt[y]++;
                if(cnt[y]==K)q.push(y);
                pt[j]++;
            }
        }
        while(!q.empty()){
            int x=q.front();q.pop();
            for(int j=0;j<K;j++)d[0][j]+=d[x][j];
            for(int j=0;j<K;j++){
                while(pt[j]<n&&p[j][pt[j]].val<d[0][j]){
                    int y=p[j][pt[j]].idx;
                    cnt[y]++;
                    if(cnt[y]==K)q.push(y);
                    pt[j]++;
                }
            }
        }
        for(int j=0;j<K;j++){
            printf(j==K-1?"%d\n":"%d ",d[0][j]);
        }
    }
    return 0;
}

第2场 Prob 06

一个个比对过去太慢了……
我们不妨搞成一个很方便比较的形式，比如，数串，甚至就一个数？
比如
*2*
111
000
记成2111000，

大矩阵中的
1234
5006
7089
我们有2个小矩阵：
123
500
708
和
234
006
089
我们分别记作：2500708 和 3006089

这样，我们对查询、对小矩阵都有统一的表示方法了。
然后呢？各显神通的时候到了。

比如我的干法：
把查询按值排序，然后枚举小矩阵，在查询中二分查找，相等的都答案+1，最后查询恢复输入顺序，输出。
（下面的实现的时间复杂度不是很对，相等的都加1应该也是结合upper_bound 和 lower_bound，确定上下界，然后用前面+1，后面-1，最后前缀和确定结果的方法，这样时间复杂度才是真O(nm log q了)）

你还可以，把小矩阵排序，然后对每个查询，二分查找相等的数量（upper_bound 和 lower_bound的结合使用），就是答案。

（题目输入似乎有问题，小矩阵好像不保证左上角和右上角不为数字，你就硬生生当做星号吧……）

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;
char str[4][4];
struct Query{
    Query(){}
    Query(int a):val(a){}
    int idx,val,cnt;
    void get(){
        val=cnt=0;
        for(int i=0;i<3;i++){
            scanf("%s",str[i]);
        }
        val=str[0][1]-'0';
        for(int i=1;i<3;i++){
            for(int j=0;j<3;j++){
                val=val*10+(str[i][j]-'0');
            }
        }
    }
    bool operator<(const Query&b)const{
        return val<b.val;
    }
}q[1005];
bool cmp(const Query&a,const Query&b){
    return a.idx<b.idx;
}
int qcnt;
int T,n,m,Case=1;
char mp[1005][1005];
int main(){
    for(scanf("%d",&T);Case<=T;Case++){
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)scanf("%s",mp[i]);
        scanf("%d",&qcnt);
        for(int i=0;i<qcnt;i++){
            q[i].get();q[i].idx=i;
        }
        sort(q,q+qcnt);
        for(int i=0;i<n-2;i++){
            for(int j=0;j<m-2;j++){
                int val=mp[i][j+1]-'0';
                for(int k=1;k<3;k++){
                    for(int l=0;l<3;l++){
                        val=val*10+(mp[i+k][j+l]-'0');
                    }
                }
                int idx=lower_bound(q,q+qcnt,Query(val))-q;
                while(idx<qcnt && q[idx].val==val){
                    q[idx].cnt++;
                    ++idx;
                }
            }
        }
        sort(q,q+qcnt,cmp);
        printf("Case %d:\n",Case);
        for(int i=0;i<qcnt;i++)printf("%d\n",q[i].cnt);
    }
    return 0;
}

第2场 Prob 07

一维的版本做过吧？
一个直线上n个点，坐标各异，现在请找一个位置，使得n个点移动到那个位置的距离和最小。
（呃，是小学奥数题吗？忘了……）
反正正解就是中位数，偏离（奇数个情况下的）中位数/（偶数个情况下的）中间两个数那一段之外，都会导致距离和变大。

现在，这里要求，定n个x位置。
那么，我们先每条横线上的点从左到右排序，然后每行的第1、2、3、...个点取中位数，作为新的位置即可。

只有一列就不多说了，和一维版本一样。
多列的时候，要说明：定的n个位置各不相同。
然而，输入保证没有2个点在同一个位置上，也就是说，第二列的点的x坐标只会至少整体往后移动一个单位，也就是，中位数至少+1，那么就不会选出一样的坐标了（只要你在偶数个点的情况下，选择中位数的策略不变的话。）

（不是郑钧尹说我都没注意到，我的代码里忘了先每行的点排个序了，然后居然过了，醉了。）

int T,y,n;
int x[1005][1005];
int main(){
    for(scanf("%d",&T);T--;){
        scanf("%d%d",&y,&n);
        for(int j=0;j<y;j++){
            for(int i=0;i<n;i++){
                scan(x[i][j]);
            }
        }
        ll ans=0;
        for(int i=0;i<n;i++){
            sort(x[i],x[i]+y);
            int mark=x[i][y/2];
            for(int j=0;j<y;j++)ans+=abs(x[i][j]-mark);
        }
        out(ans);puts("");
    }
    return 0;
}

第2场 Prob 09

先纸上看看。
考虑枚举 N=xxxx，这后面一串，由多少个数组成。
比如N=4
后面1个数4=4
后面4个数4=1+1+1+1
很简单。
后面2个数，每个数不为0呢？
4=1+3 4=2+2 4=3+1
后面3个数，每个数不为0呢？
4=2+1+1 4=1+2+1 4=1+1+2

……………………^_^
等等，有没有觉得很熟悉？
高中做过吗？x个相同的球，放入y个相同的盒子，每个盒子不能为空的题？
这不就是高中的排列组合的经典题吗？还记得吗？
那么，对于N=4的情况，方案数，用组合表示，为：
$C_{3}^{0} + C_{3}^{1} + C_{3}^{2} +C_{3}^{3}$

我们再复习一下高中的知识：
$\sum_{i=0}^n C_{n}^i$，结果是多少啊？
记住了：
$\sum_{i=0}^n C_{n}^i = 2^n$
（通俗大白话：杨辉三角的某一整行的和，是2的幂次
具体来说，开头是$1 \space \space x$的，这一整行的和为$2^x$）

然后我就不多说了。
除了写代码的时候。
表示2的x次方，位运算可以写成1<<n，但是对于long long的范围的，1<<(long long)n是不对的，要写成1LL<<n