myhalfsea's Blog

#include <iostream>

#include <string>

#include<algorithm>

using namespace std;

class node{

public:

    int a, b, c;

};

bool cmp(node x, node y){

    return x.c < y.c;

}

node  p[1000005];

bool  mark[1010]; 

int   rank[1002]; 

int   parent[1002];

int Find(int x){

     if( x != parent[x] )

        parent[x] = Find(parent[x]);

     return parent[x];

}

void Union(int root1, int root2){

     int x = Find(root1), y = Find(root2);

     if( x == y ) return ;

     if( rank[x] > rank[y] ) parent[y] = x;

     else{

         parent[x] = y;

         if( rank[x] == rank[y] ) ++rank[y];

     }

}

void initi(void){

     memset(rank, -1, sizeof(rank));

     for( int i=0; i < 1001; ++i ) parent[i] = i;

}

void hexie( void ){

    int n, m;

    int i, res, k;

    scanf( "%d %d", &n, &m );

    initi();

    for( i = 0; i < m; i++ )

        scanf( "%d %d %d", &p[i].a, &p[i].b, &p[i].c );

    sort(p, p+m, cmp);

    res = k = 0;

    for( i = 0; i < m; i++ ) {

         if( Find(p[i].a) != Find(p[i].b) ) {

             Union(p[i].a, p[i].b);

             res += p[i].c;

             ++k;

             if( k == m-1 ) break;

         }

     }

     printf("%d\n", res);

}

int main()

{

    int t;

    scanf("%d", &t);

    while( t-- )

        hexie();

    return 0;

}

1、如果没有交叉，总时间应该是多少？
2、影响搬运时间的因素是什么？
3、如果每趟处理都包含最大重叠，处理后的效果是什么？
4、得出什么结论？

#include<stdio.h>
#include<algorithm>

int main()
{
     int t, n, i, a, b, min, c[201];
     scanf("%d", &t);
     while( t-- ){
         memset( c, 0, sizeof(c));
         scanf("%d", &n);
         while( n-- ){
             scanf("%d %d", &a, &b);
             if( a > b ){
                 i = a;
                 a = b;
                 b = i;
             }
             for( i = (a+1)/2; i <= (b+1)/2; i++ )  c[i]++;
         }
         min = c[1];
         for( i = 2; i <= 200; i++)
             if( min < c[i] )
                 min = c[i];
         printf("%d\n", min*10);
     }

     return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;

struct node{
    int s, e;
};

bool cmp( node a, node b){
    return a.e < b.e;
}

node p[105];

int main()
{
    int n;
    int i, j, k, num;

    while( scanf("%d", &n) != EOF && n != 0 ){
        for( i = 0; i < n; i++ )
            scanf("%d %d", &p[i].s, &p[i].e);
        sort(p, p+n, cmp);
        num = 1;
        j = 0;
        for( i = 1; i < n; i++ ){
            if( p[i].s >= p[j].e ){
                j = i;
                num++;
            }
        }
        printf("%d\n", num);
    }

    return 0;
}

状态转移方程：

if( dp[j-coin[i].w] != MAX && dp[j] > dp[j-coin[i].w] + coin[i].c )
                    dp[j] = dp[j-coin[i].w] + coin[i].c;

#include<iostream>
using namespace std;

#define MAX 0X7ffffff
struct node{
    int w;
    int c;
};
node coin[505];
int dp[10005];

int main()
{
    int t, e, f, n;
    int i, j;
    scanf( "%d", &t );
    while( t-- ){
        scanf( "%d %d", &e, &f );
        f -= e;
        scanf( "%d", &n );
        for( i = 0; i < n; i++ )
            scanf( "%d %d", &coin[i].c, &coin[i].w );
        for( dp[0] = 0, i = 1; i <= f; i++ )
            dp[i] = MAX;
        for( i = 0; i < n; i++ )
            for( j = coin[i].w; j <= f; j++ )
                if( dp[j-coin[i].w] != MAX && dp[j] > dp[j-coin[i].w] + coin[i].c )
                    dp[j] = dp[j-coin[i].w] + coin[i].c;
        if( dp[f] == MAX )
            printf("This is impossible.\n");
        else
            printf("The minimum amount of money in the piggy-bank is %d.\n", dp[f]);
    }

    return 0;
}

在优先队列中，优先级高的元素先出队列。
标准库默认使用元素类型的<操作符来确定它们之间的优先级关系。
优先队列的第一种 用法，也是最常用的用法：

priority_queue<int> qi;

通过<操作符可知在整数中元素大的优先级高。
故示例1中输出结果为：9 6 5 3 2

第二种方法：
在示例 1中，如果我们要把元素从小到大输出怎么办呢？
这时我们可以传入一个比较函数，使用functional.h函数对象作为比较函数。

priority_queue<int, vector<int>, greater<int> >qi2;

其中
第二个参数为容器类型。
第二个参数为比较函数。
故示例2中输出结果为：2 3 5 6 9

第三种方 法：
自定义优先级。

struct node
{
    friend bool operator< (node n1, node n2)
    {
        return n1.priority < n2.priority;
    }
    int priority;
    int value;
};

在该结构中，value为值，priority为优先级。
通过自定义operator<操作符来比较元素中的优先级。
在示例 3中输出结果为：
优先级  值
9          5
8          2
6          1
2          3
1          4
但 如果结构定义如下：

struct node
{
    friend bool operator> (node n1, node n2)
    {
        return n1.priority > n2.priority;
    }
    int priority;
    int value;
};

则会编译不过（G++编译器）
因为标准库默认使用元素类型的<操作符来确定它们之间的优先级关系。
而且自定义类型的< 操作符与>操作符并无直接联系，故会编译不过。

//代码清单

#include<iostream>
#include<functional>
#include<queue>
using Namespace stdnamespace std;
struct node
{
    friend bool operator< (node n1, node n2)
    {
        return n1.priority < n2.priority;
    }
    int priority;
    int value;
};
int main()
{
    const int len = 5;
    int i;
    int a[len] = {3,5,9,6,2};
    //示 例1
    priority_queue<int> qi;
    for(i = 0; i < len; i++)
        qi.push(a[i]);
    for(i = 0; i < len; i++)
    {
        cout<<qi.top()<<" ";
        qi.pop();
    }
    cout<<endl;
    //示 例2
    priority_queue<int, vector<int>, greater<int> >qi2;
    for(i = 0; i < len; i++)
        qi2.push(a[i]);
    for(i = 0; i < len; i++)
    {
        cout<<qi2.top()<<" ";
        qi2.pop();
    }
    cout<<endl;
    //示 例3
    priority_queue<node> qn;
    node b[len];
    b[0].priority = 6; b[0].value = 1; 
    b[1].priority = 9; b[1].value = 5; 
    b[2].priority = 2; b[2].value = 3; 
    b[3].priority = 8; b[3].value = 2; 
    b[4].priority = 1; b[4].value = 4; 

    for(i = 0; i < len; i++)
        qn.push(b[i]);
    cout<<"优 先级"<<'\t'<<"值"<<endl;
    for(i = 0; i < len; i++)
    {
        cout<<qn.top().priority<<'\t'<<qn.top().value<<endl;
        qn.pop();
    }
    return 0;
}

学C++的时候，这几个输入函数弄的有点迷糊；这里做个小结，为了自己复习，也希望对后来者能有所帮助，如果有差错的地方还请各位多多指教（本文所 有程序均通过VC 6.0运行）转载请保留作者信息；
1、cin
1、cin.get()
2、cin.getline()
3、getline()
4、gets()
5、getchar()

1、cin>>          

用法1：最基本，也是最常用的用法，输入一个数字：

#include <iostream>
using namespace std;
main ()
{
int a,b;
cin>>a>>b;
cout<<a+b<<endl;
}

输入：2[回车]3[回车]
输出：5

用法2：接受一个字符串，遇“空格”、“TAB”、“回车”都结束

#include <iostream>
using namespace std;
main ()
{
char a[20];
cin>>a;
cout<<a<<endl;
}

输入：jkljkljkl
输出：jkljkljkl

输入：jkljkl jkljkl       //遇空格结束
输出：jkljkl

2、cin.get()

用法1： cin.get(字符变量名)可以用来接收字符

#include <iostream>
using namespace std;
main ()
{
char ch;
ch=cin.get();               //或者cin.get(ch);
cout<<ch<<endl;
}

输入：jljkljkl
输出：j

用法2：cin.get(字符数组名,接收字符数目)用来接收一行字符串,可以接收空格

#include <iostream>
using namespace std;
main ()
{
char a[20];
cin.get(a,20);
cout<<a<<endl;
}

输入：jkl jkl jkl
输出：jkl jkl jkl

输入：abcdeabcdeabcdeabcdeabcde （输入25个字符）
输出：abcdeabcdeabcdeabcd              （接收19个字符+1个'\0'）

用法3：cin.get(无参数)没有参数主要是用于舍弃输入流中的不需要的字符,或者舍弃回车,弥 补cin.get(字符数组名,接收字符数目)的不足.

这个我还不知道怎么用，知道的前辈请赐教；

3、cin.getline()   // 接受一个字符串，可以接收空格并输出

#include <iostream>
using namespace std;
main ()
{
char m[20];
cin.getline(m,5);
cout<<m<<endl;
}

输入：jkljkljkl
输出：jklj

接受5个字符到m中，其中最后一个为'\0'，所以只看到4个字符输出；

如果把5改成20：
输入：jkljkljkl
输出：jkljkljkl

输入：jklf fjlsjf fjsdklf
输出：jklf fjlsjf fjsdklf

//延伸：
//cin.getline()实际上有三个参数，cin.getline(接受字符串的看哦那间m,接受个数5,结束字符)
//当第三个参数省略时，系统默认为'\0'
//如果将例子中cin.getline()改为cin.getline(m,5,'a');当输入jlkjkljkl时输出jklj，输入 jkaljkljkl时，输出jk

当用在多维数组中的时候，也可以用cin.getline(m[i],20)之类的用法：

#include<iostream>
#include<string>
using namespace std;

main ()
{
char m[3][20];
for(int i=0;i<3;i++)
{
cout<<"\n请输入第"<<i+1<<"个字符串："<<endl;
cin.getline(m[i],20);
}

cout<<endl;
for(int j=0;j<3;j++)
cout<<"输出m["<<j<<"]的值:"<<m[j]<<endl;

}

请输入第1个字符串：
kskr1

请输入第2个字符串：
kskr2

请输入第3个字符串：
kskr3

输出m[0]的值:kskr1
输出m[1]的值:kskr2
输出m[2]的值:kskr3

4、getline()     // 接受一个字符串，可以接收空格并输出，需包含 “#include<string>”

#include<iostream>
#include<string>
using namespace std;
main ()
{
string str;
getline(cin,str);
cout<<str<<endl;
}

输入：jkljkljkl
输出：jkljkljkl

输入：jkl jfksldfj jklsjfl
输出：jkl jfksldfj jklsjfl

和cin.getline()类似，但是cin.getline()属于istream流，而getline()属于string流，是不一样的两 个函数

5、gets()        // 接受一个字符串，可以接收空格并输出，需包含“#include<string>”

#include<iostream>
#include<string>
using namespace std;
main ()
{
char m[20];
gets(m);                       //不能写成m=gets();
cout<<m<<endl;
}

输入：jkljkljkl
输出：jkljkljkl

输入：jkl jkl jkl
输出：jkl jkl jkl

类似cin.getline()里面的一个例子，gets()同样可以用在多维数组里面：

#include<iostream>
#include<string>
using namespace std;

main ()
{
char m[3][20];
for(int i=0;i<3;i++)
{
cout<<"\n请输入第"<<i+1<<"个字符串："<<endl;
gets(m[i]);
}

cout<<endl;
for(int j=0;j<3;j++)
cout<<"输出m["<<j<<"]的值:"<<m[j]<<endl;

}

请输入第1个字符串：
kskr1

请输入第2个字符串：
kskr2

请输入第3个字符串：
kskr3

输出m[0]的值:kskr1
输出m[1]的值:kskr2
输出m[2]的值:kskr3

自我感觉gets()和cin.getline()的用法很类似，只不过cin.getline()多一个参数罢了；

这里顺带说明一下，对于本文中的这个kskr1,kskr2,kskr3的例子，对于cin>>也可以适用，原因是这里输入的没有空 格，如果输入了空格，比如“ks kr jkl[回车]”那么cin就会已经接收到3个字符串，“ks,kr,jkl”；再如“kskr 1[回车]kskr 2[回车]”，那么则接收“kskr,1,kskr”；这不是我们所要的结果！而cin.getline()和gets()因为可以接收空格，所以不会产 生这个错误；

6、getchar()   //接受一个字符，需包含“#include<string>”

#include<iostream>
#include<string>
using namespace std;
main ()
{
char ch;
ch=getchar();                        //不能写成getchar(ch);
cout<<ch<<endl;
}

输入：jkljkljkl
输出：j

//getchar()是C语言的函数，C++也可以兼容，但是尽量不用或少用；

#include<iostream>
using namespace std;

#define max 0x70ffffff
int map[105][105];
int visit[105];
int dis[105];

int main()
{
    int n, m, a, b, c;
    int i, j, k;
    int min;
    while ( scanf("%d%d", &n, &m) && !( n ==0 && m == 0) ) {
        for ( i = 1; i <= n; i++ ) {
            for ( j = 0; j <= n; j++ )
                map[i][j] = max;
            visit[i] = 0;
        }
        for ( i = 0; i < m; i++ ) {
            scanf( "%d%d%d", &a, &b, &c );
            map[a][b] = map[b][a] = c;
        }
        for ( i = 1; i <= m; i++ )
            dis[i] = map[1][i];
        visit[1] = 1;
        dis[1] = 0;
        for ( i = 1; i <= m; i++ ) {
            min = max;
            for ( j = 1; j <= m; j++ ) {
                if ( dis[j] < min && !visit[j] ) {
                    min = dis[j];
                    k = j;
                }
            }
            if ( min == max ) break;
            visit[k] = 1;
            for( j = 1; j <= n; j++ ) {
                  if( min + map[k][j] < dis[j] && !visit[j] )
                      dis[j] = min + map[k][j];
            }
        }
        printf("%d\n", dis[n]);
    }

    return 0;
}

#include<iostream>
using namespace std;

//素数表,加快后续判断
int prime[38] = {0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1}; 
int n, cas = 1;
int vis[21], num[21];

void dfs( int cur ) {
    int i;
    if ( cur == n && prime[num[0] + num[n-1]] ){ //递归边界,测试第一个数和最后一个数
        cout << num[0] ;
        for ( i = 1; i < n; i++ )
            cout << " "<< num[i];
         cout << endl;
    }
    else {
         for(int i = 2;i <= n; ++i) //尝试放置每一个数i
         if( !vis[i] && prime[i + num[cur-1]]) //如果i没有用过，并且与前面一个数之和为素数
         { 
             num[cur] = i;  //将该数放进A中
             vis[i] = 1;    //设置使用标志
             dfs(cur + 1);  //递归调用
             vis[i] = 0;    //将标志改回来,清除标志
         }
     }
}

int main()
{
    num[0] = 1;  //1的位置不变
    while ( cin >> n ) {
        memset(vis, 0, sizeof(vis) );  //标记数组清零
        cout << "Case " << cas++ <<":\n";
        dfs(1); 
        cout << endl; 
    }

    return 0;
}

STL之顺 序容器用法总结

顺序容器主要包括vector、list、deque，分别在头文件<vector>、<list> 和<deque>中定义。

1.容器创建

C<T>  c;               //创建空容器，适用于所有容器

C<T>  c(c2);         //创建c2的副本，c和c2必须是同类型容器和元素，适用所有容器

C<T>  c(b, e);       //容器类型和元素类型可兼容即可，

但是根据实验，貌似不行

C<T>  c(n, t);        //n个t值元素，t必须是T类型或可转为T类型，适用于顺序容器

C<T>  c(n);           //n个使用初始化值的元素，适用于顺序容器，一般是0

2.迭代器操作

*iter

iter->mem

++iter

iter++

--iter

iter--

iter1 == iter2

iter1 != iter2

--------------------------

iter + n                   //只有vector和deque支持算术运算和关系运算，list不支持

iter – n 

iter1 += iter2 

iter1 -= iter2 

iter1 – iter2 

iter1 > iter2 

iter1 < iter2 

iter1 <= iter2 

iter1 >= iter2

3.内 置类型

C<T>::size_type 

C<T>::iterator 

C<T>::const_iterator                //注意与const C<T>::iterator不同 

C<T>::reverse_iterator 

C<T>::const_reverse_iterator 

C<T>::value_type 

C<T>::reference                     //左值类型，即value_type& 

C<T>::const_reference           //const value_type&

4.基本操作

void  c.push_back(t); 

void  c.push_front(t);        //只适用list、deque

void  c.insert(p, n ,t); 

void  c.insert(p, b, e); 

C<T>::iterator  c.insert(p, t); 

C<T>::size_type  c.size(); 

C<T>::size_type  c.max_size();   //最多可容纳的元素，与类型有关，总存储空间固定 

bool  c.empyt(); 

void  c.resize(n); 

void  c.resize(n, t);                   //重调c的大小，新添加的元素值使用t值 

c[n]                                        //只适用于vector、deque容器 

C<T>::value_type  c.at(n);      //只适用于vector、deque容器，

防止越界

C<T>::iterator  c.erase(p); 

C<T>::iterator  e.erase(b, e); 

void  c.clear(); 

void  c.pop_back(); 

void  c.pop_front();               //只适用于list、deque容器 

c1 = c2                          //重设，要求c1和c2类型相同，元素类型相同 

void  c1.assign(b, e);      //重设，b、e不能是c1中的迭代器，类型兼容即可 

void  c1.assign(n, t);       //重设 

void  c1.swap(c2);        //c1和c2类型必须相同，且迭代器不失效

容 器适配器包括queue、priority_queue、stack。 

stack默认基于deque容器实现，也可以建立在vector、 list和deque上； 

queue默认基于deque容器实现，也可以建立在list和deque上； 

priority_queue默 认基于vector上，也可以建立在vector和deque上。 

stack<string, vector<string> >  a; 

stack<string, vector<string> >  a(c);

1. 内置类型

C<T>::size_type 

C<T>::value_type 

C<T>::container_type

2.stack 的操作

bool  s.empty(); 

C<T>::size_type  s.size(); 

void s.pop();                   //删除不返回 

C<T>::value_type  s.top();      //返回但不删除 

void s.push(value);

3.queue和 priority_queue的操作

void  q.empty(); 

C<T>::size_type  q.size(); 

void  q.pop();                         //删除队首，不返回 

C<T>::value_type  q.front();   //返回队首，不删除，只适用于queue 

C<T>::value_type  q.back();   //返回队尾，不删除，只适用于queue 

C<T>::value_type  q.top();    //返回最高优先级的元素，不删除，只适用于priority_type 

void  q.push(value);               //对queue是在队尾压入，对priority_queue是适当位置插入