欧美激情一区在线,国产精品一区免费在线观看,久久亚洲综合

[usaco]2.2 Subset Sums

付翔 — Thu, 26 Jul 2012 15:16:00 GMT

大概的题意是�Q?�l�定一个序�?1 。。N �Q�假讑օ�集�ؓ(f��)U那么存在多少�U�情�?�Q?两个子集A B其中A∩B=∅ �Q�A∪B=U �Q�A元素的和== B元素的和�?/p>
开始写了个递归�Q�枚举，提交��时�Q?span style="font-size: 13px; color: #0000ff; ">void work(int deep,int start)

{
    if(deep >= n)    return;
    if(ans > (sum -ans)) return ;
    if(ans == sum-ans)
    {
        gcount ++;
        /FOR_1(i,1,n){
            if(used[i] == 1)
            fout<
        }
        fout</
        return ;
    }

    FOR_1(i,start + 1,n){
        if(used[i] == 0){
            used[i] = 1;
            ans += i;
            work(deep + 1,i);
            used[i] = 0;
            ans -= i;
        }
    }

}

之后改用另外一�U�思�\�Q�f(n,ans) = f(n-1,ans-n) + f(n-1,ans) ,�q�个有点分治的思�\�Q�把问题的规模逐渐�~�小�Q�从而得到解。中间加了个优化�Q�用一个二�l�数�l�存下中间计��的�l�果�Q�这样就不会(x��)��时�?br />

/*
ID:fuxiang2
PROG: subset
LANG: C++
*/
#include
#include
#include
#include <string>
#include
#include
#include
#include
#include
#include <set>
#include
#include
#include

#define REP(i, n) for (int i=0;i #define FOR(i, a, b) for (int i=int(a);i #define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)
#define REP_1(i, n) for (int i=1;i<=int(n);++i)
#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)
#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)
#define EACH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)

using namespace std;
ofstream fout ("subset.out");
ifstream fin ("subset.in");

const int N = 40;
int used[N];
int n ;
int sum;
int ans ;
int gcount ;
int data[40][800];
void work(int deep,int start)
{
    if(deep >= n)    return;
    if(ans > (sum -ans)) return ;
    if(ans == sum-ans)
    {
        gcount ++;
        /*FOR_1(i,1,n){
            if(used[i] == 1)
            fout<
        }
        fout<*/
        return ;
    }

    FOR_1(i,start + 1,n){
        if(used[i] == 0){
            used[i] = 1;
            ans += i;
            work(deep + 1,i);
            used[i] = 0;
            ans -= i;
        }
    }

}

int solve(int n ,int ans)
{
    int msum = (n+1)*n/2;
    if(ans <= 0) return 0;
    if(msum < ans) return 0 ;
    else if(msum == ans ) return 1 ;

    if(data[n][ans] )
        return data[n][ans] ;

    data[n-1][ans-n] = solve(n-1,ans-n);
    data[n-1][ans] = solve(n-1,ans);

    return data[n-1][ans-n] + data[n-1][ans];
}
int main()
{
    fin>>n;
    sum = (1+n)*n/2;
    ans = 0;
    if(sum%2 ==1){
        fout<<"0"<     }
    else {
        //work(0,0);
        //fout<
        int re = solve(n,sum/2);
        fout<     }

    //int re = solve(n,sum/2);
    //fout<
    return 0;

}

原始博客地址�Q�http://www.fuxiang90.com/2012/07/usaco2-2-subset-sums/

付翔 2012-07-26 23:16 发表评论

[usaco]2.1 Ordered Fractions

付翔 — Wed, 18 Jul 2012 01:54:00 GMT

水题�Q�枚�?�Q�只是我在判重的时候用 set �q�个在usaco 得出的结果和本地vs �q�行的结果不同。最后改用gcd 判断分子除以分母是否可约�?/span>

/*
ID:fuxiang2
PROG: frac1
LANG: C++
*/
#include
#include
#include
#include <string>
#include
#include
#include
#include
#include
#include <set>
#include
#include
#include

#define REP(i, n) for (int i=0;i#define FOR(i, a, b) for (int i=int(a);i#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)
#define REP_1(i, n) for (int i=1;i<=int(n);++i)
#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)
#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)
#define EACH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)

using namespace std;
ofstream fout ("frac1.out");
ifstream fin ("frac1.in");

class Node{
public:
    int a;//分子
    int b;// 分母
    double val;
    Node() {}
    Node(int _a,int _b ,double _val) :a(_a),b(_b),val(_val){}

    bool operator < (const Node & m)const {
        return val < m.val;
    }
};
set<double> sd;
vector vn;
int gcd(int a,int b)
{
    if(b == 1)
        return b;
    if(b == 0)
        return a;
    return gcd(b,a%b);
}
void worik(int n)
{
    double ans ;
    FOR_1(i,1,n)
        FOR_1(j,1,n){
            if(i < j)
            {
                ans = i*1.0/j;
                //if(sd.find(ans) == sd.end())
                if(gcd(j,i) == 1)
                {
                    Node  node(i,j,ans);
                    vn.push_back(node);
                    sd.insert(ans);
                }
            }
        }

    sort(vn.begin() ,vn.end());

    fout<< "0/1" << endl;
    for(vector  ::iterator iter = vn.begin() ; iter != vn.end() ; iter ++){
        fout << (iter)->a << "/" << (iter)->b <    }
    fout<<"1/1"<
}

int main()
{
    int n;
    fin>>n;
    worik(n);
    return 0;

}

原始博客地址�Q?nbsp;http://www.fuxiang90.com/2012/07/usaco2-1-ordered-fractions/

付翔 2012-07-18 09:54 发表评论

[usaco]1.5 Checker Challenge

付翔 — Tue, 10 Jul 2012 02:41:00 GMT

原始博客地址�Q?http://www.fuxiang90.com/2012/07/usaco1-5-checker-challenge/拿到题目我的�W�一反应是八皇后问题�Q�顺利的写出了递归解法�Q�弄完这个，感觉自己写递归和回溯有了一定的�q�步�?��x��W�一章做完了�Q�再接再厉�?/p>

但是提交后，�?3 �q�个��试样例��时�Q�然后就在想怎么剪枝

之前在判断放��子是否冲突的时候，是在攄��位置往四个方向拓展�Q�如果没有冲�H�就�?。现在改�q��ؓ(f��)直接判断和之前放�|�的��子是否冲突�?/li>
对称剪枝�Q�这个在癑ֺ�之后才知道的 �Q�这个是关键�Q�直接砍掉一般的旉��

�q�有说是用位�q�算�Q�这个不熟，下次��d��一下�?/div>

/*
ID:fuxiang2
PROG: checker
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <list>
#include <algorithm>
#include <set>
#include <cmath>
#include <cstring>
#include <cstdlib>
 
#define REP(i, n) for (int i=0;i
#define FOR(i, a, b) for (int i=int(a);i
#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)
#define REP_1(i, n) for (int i=1;i<=int(n);++i)
#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)
#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)
#define EACH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)
 
using namespace std;
ofstream fout ("checker.out");
ifstream fin ("checker.in");
 
const int N = 14;
int graph[N][N];
int n;
int ans ;
int result ;
// �c�M��八皇后问�?/span>
int used[N];
//list path;
int path[N];
 
bool isok(int x,int y)
{
    if(x >=1 && x<= n && y >= 1 && y <= n)
        return true;
    return false;
}
int dir[4][2] = { {-1,-1} ,{-1,1},{1,1},{1,-1} };
bool check(int x,int y )
{
    int nx = x;
    int ny = y;
    int n = x -1;
    if(n == 0)
        return true;
 
    FOR_1(i,1,n){
        nx = i;
        ny = path[i];
        if( abs(x-nx) == abs(y-ny))
            return false;
    }
    return true;
 
    //FOR_1(i,0,3){
    //    nx = x +  dir[i][0];
    //    ny = y +  dir[i][1];
    //    while(isok(nx,ny) ){
    //        if(graph[nx][ny] == 1)
    //            return false;
    //        nx += dir[i][0];
    //        ny += dir[i][1];
    //    }
    //}
    //return true;
 
}
 
void place(int col,int row)
{
    graph[row][col] = 1;
    if(row== n){
        ans ++;
        if(result + ans <= 3){
            //list::iterator iter = path.begin();
            //fout<< *iter;
            fout<<path[1];
            //for(iter ++ ; iter != path.end() ; iter ++)
            for(int i = 2 ; i <= n ; i ++)
                fout <<" "<< path[i];
            fout<<endl;
        }
        graph[row][col] = 0;
        return ;
    }
    FOR_1(i,1,n){
        if(used[i] == 0 && check(row+1,i ) == true )
        {
            path[row+1] = i;//path.push_back(i);
            used[i] = 1;
            place(i,row+1);
            //path.pop_back();
            used[i] = 0;
        }
    }
    graph[row][col] = 0;
 
}
void work(int n)
{
    result = 0;
 
    FOR_1(j,1,n/2) {// �?/span>
        path[1] = j;//path.push_back(j);
        used[j]  = 1;
        place(j,1);
        //path.pop_back();
        used[j] = 0;
    }
    int re =  ans;
    result = ans;
    if(re <3 || n%2 == 1){
        int t = n/2 + 1;
        ans = 0;
        path[1] = t;//path.push_back(j);
        used[t]  = 1;
        place(t,1);
 
    }
    if( n% 2 == 1)
        result += re + ans;
    else
        result += re;
}
 
int main()
{
    fin>>n;
    work(n);
    fout<< result<<endl;
    return 0;
 
}


原始博客地址�Q?http://www.fuxiang90.com/2012/07/usaco1-5-checker-challenge/

付翔 2012-07-10 10:41 发表评论

[usaco]1.4 Mother’s Milk

付翔 — Tue, 10 Jul 2012 02:39:00 GMT

分析�?和之前的�c�M��Q�每一步有六种状态�{�Uȝ��方式 �Q?c->a ;c->b; a->c;b->c�Q�a->b ;b->a
那每个状态是 a,b,c 的牛奶数量，因�ؓ(f��)是是�? -20 �Q�那么等于是�?0^3�U�状态�?/span>

和之前的clock 很像�Q�标记状态hash 判重�Q�遍历所有的情况��可以�?/span>

1 /*
2 ID:fuxiang2
3 PROG: ariprog
4 LANG: C++
5 */
6 #include
7 #include
8 #include <string>
9 #include
10 #include
11 #include
12 #include <set>
13 #include
14
15 #define REP(i, n) for (int i=0;i16 #define FOR(i, a, b) for (int i=int(a);i17 #define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)
18 #define REP_1(i, n) for (int i=1;i<=int(n);++i)
19 #define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)
20 #define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)
21
22 using namespace std;
23 ofstream fout ("ariprog.out");
24 ifstream fin ("ariprog.in");
25
26 int n,m;
27 //set si;
28
29 int hash[62510 * 2];
30
31 class node
32 {
33 public:
34     int a;
35     int b;
36
37     node(int _a, int _b){
38         a = _a;
39         b = _b;
40     }
41     bool operator < (const node & m )const {
42         if(m.b == b) return a < m.a;
43         return b < m.b;
44     }
45 };
46 vector vn;
47
48 //应该是这里比较费旉��
49 void work(int a,int b)
50 {
51     int ans = a;
52     if(hash[ans]  == 0)
53         return ;
54     FOR(i,0,n-1){
55         ans += b;
56         if(hash[ans] == 0)
57             return ;
58     }
59     node t(a,b);
60     vn.push_back(t);
61
62 }
63 int main()
64 {
65     fin >> n >> m;
66     FOR_1(i,0,m)
67         FOR_1(j,0,m){
68             int ii = i*i;
69             int jj = j*j;
70             hash[ii + jj] = 1;
71         }
72     int end = m*m ;
73     FOR_1(i,0,end)
74         FOR_1(j,1,end){
75             if(  (i + (n-1)*j) <= 2*end)
76                 work(i,j);
77             else
78                 break;
79     }
80     sort(vn.begin(),vn.end());
81     if(vn.empty())
82         fout << "NONE"<83     else
84         for(vector::iterator  iter =  vn.begin() ; iter != vn.end() ; iter ++ ){
85             fout << iter->a << " "<< iter ->b<86         }
87
88         return 0;
89 }

原始博客地址�Q?a style="color: #336699; text-decoration: none; ">http://www.fuxiang90.com/2012/06/usaco1-4-mothers-milk/

付翔 2012-07-10 10:39 发表评论

catalan �?证明

付翔 — Fri, 22 Jul 2011 10:05:00 GMT

定理�Q�n�? 和n�?1 构成�?n��?a1,a2�?a2n ,光��分和

满�� a1 + a2 + …aK >= 0 (k = 1 2 �?2n ) �q�个的条件的个数 �?/p>

证明�Q��o(h��)An 为其中可以接受的�p�d��Bn ��Z��可接受的�p�d��

那么 An + Bn = .An 是我们要求的�Q�我们可以通过求出Bn来得到An �?/p>

我们假设存在一个最��的K 使得a1 + a2 +�?ak ��Q�那�?可以肯定 a1+�?ak-1 = 0,且ak = -1.k 为奇整数�?/p>

对于每一�U�不�W�合条�g的序列a1 + a2 +�?ak +�?a2n ��a1 a2 ak 都用-a1 –a2 –ak 代替�Q�那么新的数�?/p>

a1�?a2�?�?a2n�?��有 n+1 �?+1 �?n-1 �?�? 。即每一�U?不符合条件的数列�l�过上述�q�程都将变�ؓ(f��)

n+1 �?+1 �?n-1 �?�? 的排�?�?strong>那么现在要证�?n+1 �?+1 �?n-1 �?�? 的排列数 == Bn

n+1 �?+1 �?n-1 �?�? 的排�?肯定存在一�?最��的k 使得 a1 + a2 + …aK < 0 而将�q�部分也�?a1 –a2 –ak 代替 �Q�也��成��Z�� n�? 和n�?1 构成�?n��?a1,a2�?a2n 而Bn的排列就好求�?/strong>

==�?a href="http://www.shnenglu.com/images/cppblog_com/397993401/WindowsLiveWriter/catalan_F7D5/clip_image002%5B8%5D.gif">

应用�Q?�?n个�h要去剧场�Q�入�?角，有n个�h�?元，n个�h�?角，剧场的卖��处刚开始没有零钱，那么存在多少�U�队列方式�?/p>
�_�体的证�?�Q�我感觉有些牵强�Q�呵�?大家有好的方法，��h��正�?/p>
我独立博客地址 http://www.fuxiang90.me/?p=286

付翔 2011-07-22 18:05 发表评论

付翔 — Sat, 16 Jul 2011 10:27:00 GMT

ubuntu�|�络�q�接昄��”讑֤�未托��?#8221;解决�Ҏ(gu��)��
之前��遇到过�q�个问题�Q�一直都没有去解冻I��q�次是因��着用虚拟机宽带�q�接�q�行上网讄��Q�没有成功，后来��D��NAT 也不行，�q�且发现 �|�络�q�接昄��”讑֤�未托��?#8221; , 一直以为是虚拟机的�|�络讄��的问题，后来证实�Q�之前宽带连接我讄��?nbsp;pppoeconf �Q�因为pppoe修改了dns��D��的�?/p>

造成问题的原�?/strong>�Q?/strong>
Linux里面有两套管理网�l�连接的�Ҏ(gu��)��Q?/strong>
1�?etc/network/interfaces�Q?etc/init.d/networking�Q?br style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; " />2、Network-Manager
两套�Ҏ(gu��)��是冲�H�的�Q�不能同时共存�?/span>
�W�一个方�?/strong>适用于没有X的环境，如：(x��)服务器；或者那些完全不需要改动连接的场合�?br style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; " />�W�二套方�?/strong>使用于有桌面的环境，特别是笔记本�Q�搬来搬去，�|�络�q�接情况随时�?x��)变的�?/p>
�Q�－�Q�－�Q�－�Q�－�Q�－�Q�－�Q?br style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; " />他们两个��Z��避免冲突�Q�又能共享配�|�，��有了下面的解决�Ҏ(gu��)��Q?br style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; " />1�?strong style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; font-size: 13px; vertical-align: baseline; ">�?/strong>Network-Manager发现/etc/network/interfaces被改动的时候，则关闭自己（昄��为未托管�Q�，除非managed讄��成真�?/strong>
2、当managed讄��成真�Ӟ��/etc/network/interfaces�Q�则不生效�?/p>
ubuntu�|�络昄��讑֤�未托��的解决办法
在终端下执行
sudo gedit /etc/NetworkManager/nm-system-settings.conf
“managed=false”改�ؓ(f��)“managed=true”�Q�重启电(sh��)脑就可以�?真的是坑爹啊
同时我之前一��文�?nbsp;http://www.fuxiang90.me/2011/07/vm-linux%E8%99%9A%E6%8B%9F%E6%9C%BA-%E5%92%8C%E4%B8%BB%E6%9C%BA%E8%BF%9B%E8%A1%8Cftp%E8%BF%9E%E6%8E%A5/
虚拟��Z��|�要�q�行
�q�一�?其实也是没有必要�?。伤不�v�?/strong>
参考：(x��) http://tieba.baidu.com/f?kz=740913480
http://www.ubuntuhome.com/ubuntu-networkmanager.html

付翔 2011-07-16 18:27 发表评论

putty如何支持中文

付翔 — Sat, 16 Jul 2011 10:25:00 GMT

今天开始跟着�|�络视频学习(f��n)�Q�之前说�q��用putty�q�程��d��linux�Q�但是发��C��文是��q��Q?/p>
解决办法�Q�首先登�?输入 echo $LANG 查看linux所使用的中文字体，然后再窗口的标题上单机右键，修改配置 �H�口->转换->�q�程字符集，选择和linux相对应的字体�Q�一般都是uft-8.
puttycn 中文下蝲 �Q?a style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; font-size: 13px; vertical-align: baseline; color: #333333; text-decoration: underline; outline-style: none; outline-width: initial; outline-color: initial; ">点击
参考：(x��)
http://wenku.baidu.com/view/c590eb8ca0116c175f0e484e.html
http://linux.chinaunix.net/techdoc/desktop/2009/03/31/1106396.shtml

独立博客地址 http://www.fuxiang90.me/2011/07/putty%E5%A6%82%E4%BD%95%E6%94%AF%E6%8C%81%E4%B8%AD%E6%96%87/

付翔 2011-07-16 18:25 发表评论

redhat ifconfig不能用的解决办法

付翔 — Sat, 16 Jul 2011 10:23:00 GMT

今天赶星老师讲解了在centos下网�l�配�|�文件的修改 == �Q�ubuntu 下有些不一��P��于是下午我就打开redhat 的虚拟机�Q�准备尝试下�Q�结果发�?ifconfig 不能用，切换到root 也不能用�?/p>
后来发现 �?sbin 目录下有ifconfig �Q�表明bash 没有去这里找,那么 export PATH=$PATH:/sbin
或�?�?etc/profile �?加上PATH=$PATH:/sbin �Q�这样就可以执行 ifconfig �?br />
独立博客 http://www.fuxiang90.me/2011/07/redhat-ifconfig%E4%B8%8D%E8%83%BD%E7%94%A8%E7%9A%84%E8%A7%A3%E5%86%B3%E5%8A%9E%E6%B3%95/
�Ƣ迎讉K��交流

付翔 2011-07-16 18:23 发表评论

ssh ��d��虚拟机linux

付翔 — Sat, 16 Jul 2011 08:41:00 GMT

之前写过如何和主机xp 建立局域网�Q��ƈ且NAT �׃�n上网 �Q?a >详情点击 �?/p>
自己的电(sh��)脑只有１�Q?的内存，有时学习(f��n)看视频还是喜�Ƣ在ｘｐ下弄�Q�然后用ｓｓ�?��d��ｌｉｎｕｘ系�l�进行操作，我发现ubuntu 10 每次跑的时�?也只是需�?00M的内存，当然是没有运行时候大�E�序�Q�所以我配置linux的虚拟内存�ؓ(f��)312 M �Q�实践证明够用�?/p>

下次试试开两个虚拟机，准备跟着�|�上的教�E?�Q�赶星老师�Q?�Q�进行学�?f��n)，如果不��用putty,老是要切换到虚拟机界面进行操作，�?sh��)脑反应有时会(x��)比较迟钝。所以��用putty �q�行��d��操作�Q�确实不错�?/p>

付翔 2011-07-16 16:41 发表评论