Category: USACO题解


好吧好久没写,果然变懒了 = = 简略点好了

N x N 方阵,左上角入,左下角出,只能上下左右相邻移动,每格仅访问一次遍历所有格,求遍历方法数。

暴力 + 剪枝,没想出什么别的方法。最多就位运算优化一下:

   Test 1: TEST OK [0.000 secs, 2900 KB]
   Test 2: TEST OK [0.000 secs, 2900 KB]
   Test 3: TEST OK [0.000 secs, 2900 KB]
   Test 4: TEST OK [0.000 secs, 2900 KB]
   Test 5: TEST OK [0.000 secs, 2900 KB]
   Test 6: TEST OK [0.000 secs, 2900 KB]
   Test 7: TEST OK [0.162 secs, 2900 KB]

All tests OK.

N = 7 的时候在 0.162 秒貌似还不错,嗯。

代码嘛……算了不贴了。在 wordpress 上贴代码各种麻烦。研究一下再说

Advertisements

USACO 5.2.3 Wisconsin Squares

好长时间没做题了,拿这个来练练手…
 
时限居然有 5s ,看来得做好极限优化的准备。
开始想的是用一个 int [4][4][5] 数组记录每格周围有同种羊的格数,然后 dfs 时每放一格就改变周围 8 格的数字。运行下貌似很慢,在我的机器上都 10s 多。
于是想到以前写过五子棋的位运算优化,这题一共 16 格,每格数字最多不大于 4,因此可用一个 64位 unsigned int 放下,每格数字只用 4 bit 表示即可。位运算的优点是可同时操作 64 位,这样只用一句便可同时改变周围 8 格的数据。
可惜在我的机器上依然跑到了 6s,考虑到还开着耗 CPU 的 APE 在听,正常应该能跑进 5s 吧。结果提交一看在评测机上只用了 2.1s 。。。哦 … 咱的机器看来该淘汰了 = = 按 6:2 来算不加位运算优化的估计也能进 5s 了…
 
TASK: wissqu
LANG: C++
 
Compiling…
Compile: OK
 
Executing…
   Test 1: TEST OK [2.117 secs, 2940 KB]
 
All tests OK.
 
#include<cstdlib>
#include<fstream>
#include<iterator>
#include<algorithm>
using namespace std;

class farm{
    int cnt, cowat[16], cowleft[5];
    bool nochange[16];
    unsigned long long ajtcnt[5];
    const unsigned long long mask, maskl, maskr;
    pair<int, int> putorder[16];
    int dfscow[16], dfspos[16];

    void addcow(int cowidx, int posidx){
        switch(posidx){
            /*
                0  1  2  3
                4  5  6  7
                8  9 10 11
               12 13 14 15
            */
            case 0:
            case 4:
                ajtcnt[cowidx] += maskl >> (5 posidx) * 4;
                break;
            case 3:
                ajtcnt[cowidx] += maskr >> (5 posidx) * 4;
                break;
            case 1:
            case 2:
                ajtcnt[cowidx] += mask >> (5 posidx) * 4;
                break;
            case 5:
            case 6:
            case 9:
            case 10:
            case 13:
            case 14:
                ajtcnt[cowidx] += mask << (posidx 5) * 4;
                break;
            case 8:
            case 12:
                ajtcnt[cowidx] += maskl << (posidx 5) * 4;
                break;
            case 7:
            case 11:
            case 15:
                ajtcnt[cowidx] += maskr << (posidx 5) * 4;
                break;
        }
        cowat[posidx] = cowidx;
    }
    int replace(int newcow, int posidx){
        int oldcow = cowat[posidx];
        unsigned long long m;
        switch(posidx){
            case 0:
            case 4:
                m = maskl >> (5 posidx) * 4;
                ajtcnt[newcow] += m;
                ajtcnt[oldcow] -= m;
                break;
            case 3:
                m = maskr >> (5 posidx) * 4;
                ajtcnt[newcow] += m;
                ajtcnt[oldcow] -= m;
                break;
            case 1:
            case 2:
                m = mask >> (5 posidx) * 4;
                ajtcnt[newcow] += m;
                ajtcnt[oldcow] -= m;
                break;
            case 5:
            case 6:
            case 9:
            case 10:
            case 13:
            case 14:
                m = mask << (posidx 5) * 4;
                ajtcnt[newcow] += m;
                ajtcnt[oldcow] -= m;
                break;
            case 8:
            case 12:
                m = maskl << (posidx 5) * 4;
                ajtcnt[newcow] += m;
                ajtcnt[oldcow] -= m;
                break;
            case 7:
            case 11:
            case 15:
                m = maskr << (posidx 5) * 4;
                ajtcnt[newcow] += m;
                ajtcnt[oldcow] -= m;
                break;
        }
        cowat[posidx] = newcow;
        return oldcow;
    }
    bool putable(int cowidx, int posidx) const {
        return !((ajtcnt[cowidx] >> posidx*4) & 0xF);
    }
    void dfs(int idx){
        int oldcow;
        if(idx == 16){
            if(!(cnt++)){
                for(int i = 0; i < 16; ++i)
                    putorder[i] = make_pair(dfscow[i], dfspos[i]);
            }
            return;
        }
        int &cow(dfscow[idx]), &pos(dfspos[idx]);
        for(cow = 0; cow < 5; ++cow)if(cowleft[cow]){
            cowleft[cow];
            for(pos = 0; pos < 16; ++pos)if(nochange[pos] && putable(cow, pos)){
                nochange[pos] = false;
                oldcow = replace(cow, pos);
                dfs(idx + 1);
                replace(oldcow, pos);
                nochange[pos] = true;
            }
            ++cowleft[cow];
        }
    }
public:
    template<class Iter>
    farm(Iter beg, Iter end): cnt(0), mask (0x011101110111ULL),
        maskl(0x011001100110ULL), maskr(0x001100110011ULL){
        fill_n(ajtcnt, 5, 0);
        fill_n(cowleft, 5, 3);
        fill_n(nochange, 16, true);
        for(int i=0; beg != end; ++beg, ++i)
            addcow(*beg ‘A’, i);
    }
    void calput(void){
        int oldcow, &pos(dfspos[0]);
        dfscow[0] = 3;
        for(pos = 0; pos < 16; ++pos)if(putable(3, pos)){
            nochange[pos] = false;
            oldcow = replace(3, pos);
            dfs(1);
            replace(oldcow, pos);
            nochange[pos] = true;
        }
    }
    ostream& output(ostream& os){
        for(int i=0; i<16; ++i){
            div_t pos = div(putorder[i].second, 4);
            os << char(putorder[i].first + ‘A’) << ‘ ‘
                << pos.quot + 1 << ‘ ‘ << pos.rem + 1 << ‘\n’;
        }
        os << cnt << ‘\n’;
        return os;
    }
};

int main(){
    ifstream fin("wissqu.in");
    farm wissqu((istream_iterator<char>(fin)), istream_iterator<char>());
    fin.close();
    ofstream fout("wissqu.out");
    wissqu.calput();
    wissqu.output(fout);
    fout.close();
}

USACO 4.3.2 The Primes

够BT的一道题,改了几遍才过 – –

一开始没想费太多内存觉得稍微预存几种结果应该就差不多了,结果完全低估了数据规模。
只好把所有可能用到的模式全预算出来再循环。结果弄了快300行ORZ…
还有一次犯傻没排序就跑去提交了
 
TASK: prime3

LANG: C++
 
Compiling…
Compile: OK
 
Executing…
   Test 1: TEST OK [0.065 secs, 2984 KB]
   Test 2: TEST OK [0.054 secs, 2988 KB]
   Test 3: TEST OK [0.065 secs, 2984 KB]
   Test 4: TEST OK [0.065 secs, 2988 KB]
   Test 5: TEST OK [0.076 secs, 2984 KB]
   Test 6: TEST OK [0.140 secs, 2984 KB]
   Test 7: TEST OK [0.119 secs, 2988 KB]
   Test 8: TEST OK [0.130 secs, 2988 KB]
   Test 9: TEST OK [0.205 secs, 2988 KB]
   Test 10: TEST OK [0.259 secs, 2988 KB]
 
All tests OK.
Your program (‘prime3’) produced all correct answers!  This is your
submission #5 for this problem.  Congratulations!
 
要速度,貌似只能模拟填表的过程,并且每步选限制尽可能多的行或列来填。
第1行和第1列限制最多,开头第1位已定,且各位都不能出现0,先把他们填了。
然后选辅对角线(左下到右上),因为开头结尾两位都已定。
再填主对角线,第1位和第3位已定。
下面是第二行、第二列、第四行、第四列,这四种情况都是 1、2、4 位已定
然后第三行和第三列都只剩下最后一位空缺了。最后检查一下第五行和第五列即可。
 
从上面过程看出要预先计算的是:
(1) 所有5位质数且各位数字和满足条件的数
(2) 第1位已知且满足(1),各位都不为0的组合
(3) 1、5位已知且满足(1)的组合
(4) 1、3位已知且满足(1)的组合
(5) 1、2、3、4位已知且满足(1)的组合
 
其他好像有提出先填第5行和第5列的,因为这两行除了满足质数与数字和外 各位只能是 1、3、7、9 四选一。不过我觉得这没有用,例如只要第一列填了质数,则第5行第一位自然就只会是 1、3、7、9 之一了,先填第5行对第1列来说也并没有其他额外限制作用。但仅是猜测,也没试验过。
 
预先开个100000的数组,第一遍求所有质数(顺便将不是质数的值存为下标方便遍历),然后筛选数字和满足条件的数,同样使下标形成链表方便遍历。同时选出各位数字满足条件的组合预先存起来,剩下只用循环便是。排序嘛,就每位挨个判断了,也没几个数。
上一篇在这里
 
虽然SPFA已经得出了比较满意的结果,但现在又发现了优化算法,这样一来SPFA就把Dijkstra甩开了一大截。
下面直接引用我在上一篇的留言:
对于APSP问题如果用单源最短路径算法的话,曾考虑过用先求出的最短路径优化,使得在后面求新源点的最短路径时对已求过的点之间可以一次优化到最终结果避免多次进入队列更新,这个优化对SPFA算法尤其明显。不过这样一来就需要用邻接矩阵储存边,对稀疏图来说需要空间比较多,也可以看成是一种DP的思想吧(空间换时间)。虽然最短路存在了邻接矩阵中,但对稀疏图计算时还是用邻接表算,这个效率依然是最高的(实践验证过,用时相差10倍以上)。
 
今天实践了一下,发现具体实现和开始想的优化方法还有些不同:只能在求过的点中取一点进行优化(多了效果不升反降)

#include<fstream>
#include<vector>
#include<list>
#include<queue>
using namespace std;
 
const int infinite=1000000000;
int nCow,nPasture,nConnect;
vector<int> vCowsAt;
vector< list< pair<int,int> > > vPasAjt;
vector< vector<int> > vDistMatrix;
 
inline bool relax(int u, int v, int weight, vector<int> &d){
    int newlength=d[u]+weight;
    if(newlength<d[v]){
        d[v]=newlength;
        return true;
    }
    return false;
}
 
int CalPathSum(int iSource){
    queue<int> Q;
    vector<bool> IsInQ(nPasture);
 
// optimizing begin:
    if(iSource>0){
        int iShort=0;
        for(int k=1;k<iSource;++k)if(vDistMatrix[k][iSource]<vDistMatrix[iShort][iSource])
            iShort=k;
        for(int iDes=0;iDes<nPasture;++iDes)
            vDistMatrix[iSource][iDes]=vDistMatrix[iShort][iSource]+vDistMatrix[iShort][iDes];
    }
// optimizing end.
 
    vDistMatrix[iSource][iSource]=0;
    Q.push(iSource);
    IsInQ[iSource]=true;
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        IsInQ[u]=false;
        for(list< pair<int,int> >::iterator itr=vPasAjt[u].begin();itr!=vPasAjt[u].end();++itr){
            int v=itr->first;
            if(relax(u,v,itr->second,vDistMatrix[iSource]) && !IsInQ[v]){
                Q.push(v);
                IsInQ[v]=true;
            }
        }
    }
 
    int sum=0;
    for(int i=0;i<nCow;++i)sum+=vDistMatrix[iSource][vCowsAt[i]];
    return sum;
}
 
int main(){
    ifstream fin("butter.in");
    ofstream fout("butter.out");
    fin>>nCow>>nPasture>>nConnect;
    vCowsAt.resize(nCow);
    vPasAjt.resize(nPasture);
    vDistMatrix.resize(nPasture);
    for(int i=0;i<nPasture;++i)
        vDistMatrix[i].resize(nPasture,infinite);
    for(int i=0;i<nCow;++i){
        int iPasture;
        fin>>iPasture;
        vCowsAt[i]=iPasture-1;
    }
    for(int i=0;i<nConnect;++i){
        int u,v,distance;
        fin>>u>>v>>distance;
        vPasAjt[u-1].push_back(pair<int,int>(v-1,distance));
        vPasAjt[v-1].push_back(pair<int,int>(u-1,distance));
    }
 
    int minpath=infinite;
    for(int i=0;i<nPasture;++i)
        minpath=min(minpath,CalPathSum(i));
    fout<<minpath<<endl;
}


程序变化不大,只是多了对 vDistMatrix 矩阵的处理,并加上了优化部分(已标出)。由于使用了动态空间分配,内存占用没有想象的增加那么多。
下面是运行结果:


TASK: butter

LANG: C++
 
Compiling…
Compile: OK
 
Executing…
   Test 1: TEST OK [0.022 secs, 2852 KB]
   Test 2: TEST OK [0.000 secs, 2856 KB]
   Test 3: TEST OK [0.000 secs, 2856 KB]
   Test 4: TEST OK [0.000 secs, 2852 KB]
   Test 5: TEST OK [0.011 secs, 2856 KB]
   Test 6: TEST OK [0.011 secs, 2988 KB]
   Test 7: TEST OK [0.043 secs, 3512 KB]
   Test 8: TEST OK [0.065 secs, 4308 KB]
   Test 9: TEST OK [0.086 secs, 5364 KB]
   Test 10: TEST OK [0.108 secs, 5360 KB]
 
All tests OK.


时间几乎缩短了一半,可惜最后一个测试点差点突破 0.1secs …

USACO 3.2.6 Sweet Butter 题解

一个农场有很多块牧场(<=800),这些牧场间有很多条(<=1450)道路相连,一些牛分散在这些牧场中。在这些牧场中寻找一个牧场,使得所有的牛到达该牧场所走的路程和最小,当然牛牛们会自己寻找到达该牧场的最短路径。

题目意图很明确,显然需要寻找每两个牧场间的最短路径,自然想到Floyd算法。不过该算法时间复杂度为O(V^3),对此题来说就是 800*800*800=512000000,超时是必然的。之后就可以考虑 Heap 优化的 Dijkstra 算法和 SPFA 算法了。此题中是稀疏图,考虑先用一下 SPFA 看看情况。


#include<fstream>
#include<vector>
#include<list>
#include<queue>
using namespace std;

const int infinite=1000000000;
int nCow,nPasture,nConnect;
vector<int> vCowsAt;
vector< list< pair<int,int> > > vPasAjt;

inline bool relax(int u, int v, int weight, vector<int> &d){
    int newlength=d[u]+weight;
    if(newlength<d[v]){
        d[v]=newlength;
        return true;
    }
    return false;
}

int CalPathSum(int iSource){
    queue<int> Q;
    vector<bool> IsInQ(nPasture);
    vector<int> d(nPasture,infinite);

    d[iSource]=0;
    Q.push(iSource);
    IsInQ[iSource]=true;

    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        IsInQ[u]=false;
        for(list< pair<int,int> >::iterator itr=vPasAjt[u].begin();itr!=vPasAjt[u].end();++itr){
            int v=itr->first;
            if(relax(u,v,itr->second,d) && !IsInQ[v]){
                Q.push(v);
                IsInQ[v]=true;
            }
        }
    }

    int sum=0;
    for(int i=0;i<nCow;++i)sum+=d[vCowsAt[i]];
    return sum;
}

int main(){
    ifstream fin("butter.in");
    ofstream fout("butter.out");
    fin>>nCow>>nPasture>>nConnect;
    vCowsAt.resize(nCow);
    vPasAjt.resize(nPasture);

    for(int i=0;i<nCow;++i){
        int iPasture;
        fin>>iPasture;
        vCowsAt[i]=iPasture-1;
    }
    for(int i=0;i<nConnect;++i){
        int u,v,distance;
        fin>>u>>v>>distance;
        vPasAjt[u-1].push_back(pair<int,int>(v-1,distance));
        vPasAjt[v-1].push_back(pair<int,int>(u-1,distance));
    }

    int minpath=infinite;
    for(int i=0;i<nPasture;++i)
        minpath=min(minpath,CalPathSum(i));

    fout<<minpath<<endl;
}


果然不错,一次就通过了:

TASK: butter

LANG: C++
 
Compiling…
Compile: OK
 
Executing…
   Test 1: TEST OK [0.011 secs, 2848 KB]
   Test 2: TEST OK [0.011 secs, 2848 KB]
   Test 3: TEST OK [0.000 secs, 2848 KB]
   Test 4: TEST OK [0.011 secs, 2848 KB]
   Test 5: TEST OK [0.011 secs, 2852 KB]
   Test 6: TEST OK [0.011 secs, 2852 KB]
   Test 7: TEST OK [0.065 secs, 2852 KB]
   Test 8: TEST OK [0.108 secs, 2852 KB]
   Test 9: TEST OK [0.184 secs, 2848 KB]
   Test 10: TEST OK [0.194 secs, 2848 KB]
 
All tests OK.
YOUR PROGRAM (‘butter’) WORKED FIRST TIME!  That’s fantastic

— and a rare thing.  Please accept these special automated
congratulations.
 
之后看了下标程,用的是 Dijkstra + Heap ,写起来果然很复杂,花了150多行……就用标程也运行了一下做个比较:
Executing…

   Test 1: TEST OK [0.000 secs, 9416 KB]
   Test 2: TEST OK [0.011 secs, 9416 KB]
   Test 3: TEST OK [0.000 secs, 9420 KB]
   Test 4: TEST OK [0.000 secs, 9420 KB]
   Test 5: TEST OK [0.000 secs, 9420 KB]
   Test 6: TEST OK [0.011 secs, 9420 KB]
   Test 7: TEST OK [0.043 secs, 9420 KB]
   Test 8: TEST OK [0.108 secs, 9416 KB]
   Test 9: TEST OK [0.216 secs, 9420 KB]
   Test 10: TEST OK [0.205 secs, 9420 KB]
 
All tests OK.
 
从最后两个测试时间来看,两个算法相差不大。不过 SPFA 要稍稍快一些。嗯,现在至少在稀疏图上验证了 SPFA 的效率,下次遇到稠密图再试一下吧。