POJ 3169 Layout(差分约束)

题目:传送门

题目大意:

当排队等候喂食时,奶牛喜欢和它们的朋友站得靠近些。FJ有N(2<=N<=1000)头奶牛,编号从1到N,沿一条直线站着等候喂

食。奶牛排在队伍中的顺序和它们的编号是相同的。因为奶牛相当苗条,所以可能有两头或者更多奶牛站在同一位置上。即使说,

如果我们想象奶牛是站在一条数轴上的话,允许有两头或更多奶牛拥有相同的横坐标。

一些奶牛相互间存有好感,它们希望两者之间的距离不超过一个给定的数L。另一方面,一些奶牛相互间非常反感,它们希望两者间

的距离不小于一个给定的数D。给出ML条关于两头奶牛间有好感的描述,再给出MD条关于两头奶牛间存有反感的描述。

(1<=ML,MD<=10000,1<=L,D<=1000000)

你的工作是:如果不存在满足要求的方案,输出-1;如果1号奶牛和N号奶牛间的距离可以任意大,输出-2;否则,计算出在满足所有要求的情况下,1号奶牛和N号奶牛间可能的最大距离。

 

刚开始看一脸懵逼😐,上网搜了题解发现是差分约束(不要问我为什么一直搜题解,题目好难)发现这东西大概是一些特定的不等式组

继续阅读POJ 3169 Layout(差分约束)

次短路 POJ 3255

Bessie has moved to a small farm and sometimes enjoys returning to visit one of her best friends. She does not want to get to her old home too quickly, because she likes the scenery along the way. She has decided to take the second-shortest rather than the shortest path. She knows there must be some second-shortest path.

The countryside consists of R (1 ≤ R ≤ 100,000) bidirectional roads, each linking two of the N (1 ≤ N ≤ 5000) intersections, conveniently numbered 1..N. Bessie starts at intersection 1, and her friend (the destination) is at intersection N.

The second-shortest path may share roads with any of the shortest paths, and it may backtrack i.e., use the same road or intersection more than once. The second-shortest path is the shortest path whose length is longer than the shortest path(s) (i.e., if two or more shortest paths exist, the second-shortest path is the one whose length is longer than those but no longer than any other path).

Input

Line 1: Two space-separated integers: N and R
Lines 2.. R+1: Each line contains three space-separated integers: A, B, and D that describe a road that connects intersections A and B and has length D (1 ≤ D ≤ 5000)

Output

Line 1: The length of the second shortest path between node 1 and node N

Sample Input

4 4
1 2 100
2 4 200
2 3 250
3 4 100

Sample Output

450

Hint

Two routes: 1 -> 2 -> 4 (length 100+200=300) and 1 -> 2 -> 3 -> 4 (length 100+250+100=450)

 

题目大意:在一个图上有许多个农场,有个人从1农场出发,到他的朋友n农场去,他不想走一条最短路径,这次他想换条路走,要你帮他找一条次短路径,次短路的定义是,比最短路径长度短(可能有多条),但是不会比其他的路径长度长。而且告诉你数据中一定存在至少一条次短路。

大概思路:求次短路是在最短路的基础上求的。如果到它的最短距离大于当前该点的次短距离,则当前该点已经取到最短距离和次短距离,不进行操作,否则进行两次判断:如果小于最短边,则赋给最短变,并将最短边赋给次短边;或者如果大于最短边且小于次短边,则赋给次短边。两次完成之后均要加入队列,并且同时更新最短边。

代码如下


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
const int R=100000+10;
int first[2*R],next[2*R],u[2*R],v[2*R],w[2*R];
struct node {
    int sht,shr;
    node(){
        sht=(int)1e9;
        shr=(int)1e9;
    }
};
queue<int> q;
int tot;
node dis[5050];
void addedge(int a,int b,int c)
    {
        next[++tot]=first[a];
        first[a]=tot;
        v[tot]=b;
        w[tot]=c;
    }
void SPFA()
    {
        int e,now,value,to;
        q.push(1);
        dis[1].sht=0;
        while (!q.empty())
        {
            now=q.front();
            for ( e=first[now]; e>0; e=next[e])
                {
                    value=dis[now].sht+w[e];
                    to=v[e];
                    if (value<dis[to].sht)
                        dis[to].sht=value,q.push(to);
                    if (value>dis[to].sht && value<dis[to].shr )
                        {
                            dis[to].shr=value;
                            q.push(to);
                        }
                    value=dis[now].shr+w[e];
                    if (value<dis[to].shr && value>dis[to].sht)
                        {
                            dis[to].shr=value;
                            q.push(to);
                        }
                }
            q.pop();
        }
    }
int main(void)
    {
        int n,m;

        scanf("%d%d",&n,&m);
        for (int i=1; i<=m; i++)
            {
                int a,b,c;
                scanf("%d%d%d",&a,&b,&c);
                addedge(a,b,c);
                addedge(b,a,c);
            }
        SPFA();
        printf("%d\n",dis[n].shr);
        return 0;
    }

 

网络流/费用流

【流模型】
如同我们可以把一个实际的道路地图抽象成一个有向图来计算两点之间的最短路径,我们也可以将一个有向图看作一个网流络来解决另一类型的问题。网络流比较适合用来模拟液体流经管道、 电流在电路网络中的运动、 信息网络中信息的传递等等类似的过程。
我们可以将网络流类比成水流, 如下图给出一个有向图 G =(V, E).图中的边可以想象成管道, 顶点则是管道的连接点。 边上的权值我们称之为这条边的流量上限, 可以把它想象成这条管道能通过的水流的多少。 对于图中每条边e我们记它的流量上限为 c(e) .

【最大流模型】
对于有源点s和汇点t的图,则称为网络流图。在这样的图中,源点入度为 0 且可以产生无穷大的流量,汇点出度为 0 且可以吸
收无穷大的流量。
称一条从源点到汇点的,并使除源汇之外所有结点满足流量平衡,所有边满足流量约束的流方案为有源汇网络的可行流。(这里的流方案并不一定只沿一条路流,也可能在多个结点上出现支路,但要保证满足流量约束与流量平衡条件。)
最大的可行流方案为最大流。求解最大流的问题称为最大流问题。

【求解最大流/Dinic算法】
Dinic 算法的主要思想就是每次寻找最短的增广路,并沿着它增广。因为最短增广路的长度在增广过程中始终不会变短,所以无需每次都通过广搜来寻找最短增广路。我们可以先进行一次广搜,然后考虑由近距离顶点指向远距离顶点的边所组成的分层图,在上面进行深搜寻找最短增广路(这里一次深搜就可以完成多次增广的工作)。每增广一条边,就要在其反向边上加上流入的流量,在这条边上减去流入的流量,这样,在找到一条更优的增广路后,便可以直接从反向边进行修改。
如果在分层图上找不到新的增广路了(此时我们得到了分层图所对应的阻塞流),则说明最短增广路的长度变长了或不存在增广路了,于是重新构造新的分层图。
注: 建边时一般从2开始建,这样便于正、反边的互换,只要(^1)便能得到另一条边。
构建分层图的代码:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
queue<int> q;

int bfs()  {
    int v, now;
    for (int i = s;i <= t; i++) cnt[i] = en[i], dir[i] = -1;
    dir[s] = 0;
    while (!q.empty()) q.pop();
    q.push(s);
    while (!q.empty())  {
        for (int e = en[now = q.front()]; e ; e = next[e])
            if (val[e] > 0 && dir[v = gt[e]] == -1)  {
                dir[v] = dir[now] + 1;
                q.push(v);
                if (v == t) return 1;
            }
        q.pop();
    }
    return 0;
}

Dinic代码:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int Dinic(int u, int flow)  {
    if (u == t) return flow;
    int acc = 0, v, del;
    for (int &e = cnt[u]; e ; e = next[e])  
        if (val[e] > 0 && dir[u] + 1 == dir[v = gt[e]] && dir[v] > 0)  {
            del = Dinic(v, min(val[e], flow - acc));
            if (del)  {
                val[e] -= del;
                val[e ^ 1] += del;
                acc += del;
                if (acc == flow) break;
            }
        }
    if (acc != flow) dir[u] = -1;
    return acc;
}

【费用流】
费用流则是在网络流的基础上给每条边多加了个属性,即单位流量的费用,一般在费用流的可行方案中,要求费用与流量平衡。
注意到,在网络流的求解中,每次都是随便选取一条边来进行增广,费用流中由于边多了一个权值,选边的顺序就需要确定了。显而易见,可以贪心地在残余网络上选最小费用的路径进行增广。多了个权值,在建边时反向边的权值便是负值,所以不能Dijkstra来求最小值,要用队列优化的 Bellman-Ford 算法。
实际上,费用流与网络流的差别也就在选取边的顺序上;


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
queue<int> q;

int spfa()  {
    memset(vis, 0, sizeof vis);
    for (int i = 1;i <= 2 * N; i++) dir[i] = INF;
    int nxt, now;
    dir[s] = 0;
    q.push(s);
    vis[s] = 1;
    while (!q.empty())  {
        vis[now = q.front()] = 0;
        for (int e = beg[now]; e ;e = next[e])
            if (cap[e] > 0 && dir[now] + cost[e] < dir[nxt = gt[e]])  {
                dir[nxt] = dir[now] + cost[e];
                if (!vis[nxt])  {
                    vis[nxt] = 1;
                    q.push(nxt);
                }
            }
            q.pop();
    }
    if (dir[t] < INF) return 1;
    return 0;
}

【网络流题目】(两题代码相同)

【POJ】2186Popular Cows

【QZYZ】1238草地排水

继续阅读网络流/费用流

POJ - 3255 Roadblocks

困扰了两天的次短路问题终于在大佬 @C2013ZDX 的帮助下AC了。激动人心😂

传送门:戳我

题目大意:一张无向图,n个点,r条边,求起点1到终点n的次短路。

 

看到题目的时候就懵逼了,最短路好打,可是次短路是什么东东。

后来看了网上的题解,次短路应该是在一段最短路的基础上再加上一段次短路,证明过程不详讲,只要用spfa或dijkstra在记录最短路的时候顺便更新每个点的次短路即可。

 

早上打了个spfa,有时间可以尝试下dijkstra;

由于是无向图所以可以来回走,刚开始没注意到这么gay的条件导致次短路挂掉。。

 

下为code+手打注释

 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;

const int R=100010;
const int N=5010;

struct dist
{
    int first,second;
    dist()  {
        first = (int)1e9;
        second = (int)1e9;
    }
}dis[N];

int num[2*R],next[2*R],val[2*R],f[N],to[2*R],tot;

queue <int> q;

void adde(int u,int v,int w)    //邻接表
{
    next[++tot]=f[u];
    f[u]=tot;
    to[tot]=v;
    val[tot]=w;
}

void spfa(void)
{
    dis[1].first=0; //1的最短路清零,次短路不能
    q.push(1);
    while (!q.empty())
    {
        int nxt;
        int now=q.front();
        q.pop();
        for (int i=f[now];i;i=next[i])
        {
            int com=dis[now].first+val[i];  //1.起点到now点最短路+到to[i]的距离
            if (com<dis[nxt = to[i]].first)     //更新最短路
            {
                int tem=dis[nxt].first;
                dis[nxt].first=com;
                dis[nxt].second=tem;    //原最短路更新为次短路
                q.push(nxt);
            }
            if (com>dis[nxt].first && com<dis[nxt].second)  //更新次短路
            {
                dis[nxt].second=com;
                q.push(nxt);
            }
            com=dis[now].second+val[i]; //2.起点到now点的次短路加上到to[i]点的距离
            if (com>dis[nxt].first && com<dis[nxt].second)  //更新次短路*2
            {
                dis[nxt].second=com;
                q.push(nxt);
            }
        }
    }
}

int main(void)
{
    int n,m,u,v,w;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        adde(u,v,w);
        adde(v,u,w);    //无向图
    }
    spfa();
    printf("%d\n",dis[n].second);
    return 0;
}

 

看到图论就脸黑,还是太过年轻🤣

 

岂曰无衣,与子同袍。

Y.W.             2017/7/11       东海集训

POJ 1182 / NOI 2001 详解

题目    https://cn.vjudge.net/contest/164366#problem/C

http://poj.org/problem?id=1182

 

题目描述:
动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B, B吃C,C吃A。
现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述:
第一种说法是"1 X Y",表示X和Y是同类。
第二种说法是"2 X Y",表示X吃Y。
此人对N个动物,用上述两种说法,一句接一句地说出K句话,这K句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。
1) 当前的话与前面的某些真的话冲突,就是假话;
2) 当前的话中X或Y比N大,就是假话;
3) 当前的话表示X吃X,就是假话。
你的任务是根据给定的N(1 <= N <= 50,000)和K句话(0 <= K <= 100,000),输出假话的总数。

Input

第一行是两个整数N和K,以一个空格分隔。
以下K行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中D表示说法的种类。
若D=1,则表示X和Y是同类。
若D=2,则表示X吃Y。

Output

只有一个整数,表示假话的数目。

Sample Input

100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5

Sample Output

3

 

 

题目的解法为带权并查集,这题算得上是对并查集应用情况最好的考察。

不过题目确实很难,自己并没有什么思路。

后来看了大佬的题解后才懂得解法,并自己手打了一遍,发现WA了,仔细检查发现在处理寻找父节点时写成了找爷爷节点。。绝望🤣🤣

因版权原因,此处给出博客的网址:http://blog.csdn.net/c0de4fun/article/details/7318642/

 

写得很棒😃

最令我惊叹的还是对于关系的处理,异常精妙。。

 

下面是自己打的code加注释


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

struct animal
{
    int num;
    int parent;
    int relation;   //编号,父节点,关系
};
animal ani[500010];

int n,k;
int same=0;
int enemy=1;
int food=2; //关系定义
int ans;

void init(void)
{
    for (int i=1;i<=n;i++)
    {
        ani[i].num=i;
        ani[i].parent=i;
        ani[i].relation=0;  //初始化,编号与父节点==i,关系为同类
    }
}

int findfa(int node)
{
    int t;
    if (ani[node].parent==ani[node].num)
        return ani[node].parent;        //直到找到父节点是自身,返回;
    t=ani[node].parent;     //记录父节点
    ani[node].parent=findfa(t); //将父节点更新为爷爷节点
    ani[node].relation=(ani[node].relation + ani[t].relation)%3; //通过父节点的关系计算出与爷爷节点的关系
    return ani[node].parent;    //返回新的父节点
}

void Union(int x,int y,int a,int b,int d)
{
    ani[b].parent = a;  
    ///rootY.parent = rootX.parent;  
    ani[b].relation =( (3 - ani[y].relation) + (d - 1) + ani[x].relation) % 3;
    //由b与y的关系和y与x的关系和x对a的关系推出b与a的关系;
}

int main(void)
{
    scanf("%d%d",&n,&k);
    init();
    for (int q=1;q<=k;q++)
    {
        int d,x,y;
        scanf("%d%d%d",&d,&x,&y);
        if (x>n || y>n || x<=0 || y<=0) //编号不正确
            ans++;
        else
        {
            if (x==y && d==2)
                ans++;      //自己吃自己
            else
            {
                int a=findfa(x);
                int b=findfa(y);    //根节点
                if (a!=b)
                {
                    Union(x,y,a,b,d);   //不在同一集合就合并
                }
                else
                {
                    if (d==1)       //同类
                    {
                        //若集合中关系不为同类,ans++;
                        if (ani[x].relation != ani[y].relation)
                        {
                            ans++;
                        }
                    }
                    if (d==2)       //敌人
                    {
                        //若集合中关系不为敌人,ans++;
                        if ((ani[y].relation+3-ani[x].relation)%3 != 1)
                        {
                            ans++;
                        }
                    }
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

 

一上午的成果,感觉还是收获颇丰。😀😀

 

 

心情有低谷,人生从未有低谷!

Y.W.            2017/7/10     东海集训

 

分块算法

【思想】  分块思想的核心是将一个集合划分成若干个规模较小的子集。即让连续的序列组成一个块,便于进行处理。
为了便于处理,分块需要满足:
(1) 若子集规模很小, 对每个子集可使用关于子集规模的复杂度较高的算法。
(2) 若子集数目很少, 可以使用与整个集合规模有关的算法分别处理每个子集。
可以发现前两条性质其实是相互矛盾的, 因此为了均衡, 我们既不能让子集规模过大,
也不能让子集数目过大, 通常分块的大小都取n^0.5(根号n)。
通过预处理每一个分块,对于询问的区间,我们可以把其分为完全处于块中的区间与不完全处于块中的区间。完全处于块中的区间可以用预处理的结果得出答案,不完全处于块中的区间采用暴力枚举的方法。由于每个块的大小有限,所以枚举的时间复制度并不大。这样,算法的时间复杂度是O(n^0.5 * n)。
【优点】 分块算法的时间复杂度比一些数据结构的O(n logn)还大,那分块算法有什么用呢。但是,有些数据是普通的数据结构不能合并的,比如BZOJ2724: [Violet 6]蒲公英
题目大意是给定 n 个数, 每次询问区间[L, R]内的众数, 强制在线。
很明显,这题是用线段树不能解决的。分块算法则能很好的完成。
在此题中我们就预处理出两个量: cnt[i][j]表示i 这个元素在前 j 块中的出现次数,以及 ans[i][j] 表示第i 块到第 j 块这个区间的众数。这两个量都是能在 O(n^0.5)的时间内预处理出来的。 cnt[i][j]较为简单就不赘述; 求 ans[i][j] 时我们先枚举并固定 i , 当 i 确定后我们用一个数组来记录每个数字的出现次数, 初始时所有数字出现次数均为 0。 接着我们从第i 块左端点开始, 枚举之后的所有元素, 并更新出现次数的数组, 在这个程中我们是能求出当前众数的。 当枚举到的元素是某个块 j 的右端点时, 我们就知道 ans[i][j] 的值了, 不难发现这个做法复杂度是 O(n^0.5)的。

而对于询问,先找出完全被包含的分块,此时,答案要么是这些分块的众数,要么是不完全被包含的分块中的数。我们可以暴力将它们全部枚举一遍, 记录下它们当前的出现次数, 配合之前预处理的 cnt[i][ j], 我们可以快速的算出一个数在第 L 块到第 R 块间的出现次数, 加上它在那 O( n^0.5) 个单个元素中出现的次数, 就是它在询问区间内出现的总次数, 进而我们可以利用它来更新答案。

代码如下:

继续阅读分块算法

主席树

主席树又称函数式线段树,就是通过函数来实现的线段树,可以处理一些神奇的问题。

【例题】K-th Number

  • 很明显,这题的数据是不允许对于每一个询问进行一次排序的。那么,考虑一种解法,建你n棵线段树,第i棵线段树维护的是1~i中,大小属于[1,m]的数的数量(1 <= m <= max)。对于每次询问的L,R区间中的第k小数,便可以通过log(n)的时间来完成。
  • 显然我们不能直接全部建出来, 这样时空复杂度都不允许。我们发现相邻的两棵线段树的差别只是i比i-1多了a[i]这个数, 而在权值线段树中多出这样一个值, 第 i 棵树
    与第 i -1棵树的差别实际上只有log 个节点。 也就是我们可以看做在第 i -1
    棵权值线段树中插入权值a[i] 得到第 i 棵权值线段树, 而单点插入过程中只会遇到以及修改根到那个叶子路径上的log(n)个节点。
  • 假设我们已经得到了第 i -1棵权值线段树, 现在要在第i -1棵的基础上加入权值
    a[i]来得到第i 棵树。 首先我们新建一个节点来表示第i 棵树的根节点, 接着我们从第i -1棵以及第i棵树的根节点开始考虑。 对于当前节点, 若当前插入的值a[i] 在当前权值区间中的左半部分,说明a[i] 它要影响第 i 棵树当前节点的左子树的值, 则我们新建一个左儿子, 作为第 i 棵树对应的当前节点左儿子; 而第i 棵树对应的当前节点右儿子( 子树) , 它( 们) 并不受新插入的值的影响, 因此它与第 i -1棵树的当前节点的右儿子( 子树) 的信息一模一样, 所以我们考虑直接将第 i 棵树对应的当前节点右儿子设为第i -1棵树的当前节点的右儿子。 反之亦然。
    插入的代码如下:

    
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    void add(int &cnt, int last, int l, int r, int v)  {
        cnt = ++tot;
        tr[cnt] = tr[last];
        tr[cnt].sum++;
        if (l < r)  {
            if (v <= (l + r) / 2) add(tr[cnt].ls, tr[last].ls, l, (l + r) / 2, v);
            else add(tr[cnt].rs, tr[last].rs, (l + r) / 2 + 1, r, v);
        }
    }

那么对于每一个询问,代码就显而易见了:


1
2
3
4
5
6
7
int que(int pas, int now, int l, int r, int k)  {
    if (l == r) return l;
    int s = tr[tr[now].ls].sum - tr[tr[pas].ls].sum;
    if (k <= s) return que(tr[pas].ls, tr[now].ls, l, (l + r) / 2, k);
    return que(tr[pas].rs, tr[now].rs, (l + r) / 2 + 1, r, k - s);

}

具体代码如下:

继续阅读主席树

2017/7/7 东海集训

今日主攻动规

先是将挑战程序竞赛中的例题在泉州一中题库中上交。

vjudge网址:https://cn.vjudge.net/contest/164364

 

战果5T

 

TA    数字金字塔简单dp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

int a[400][400],f[400][400];
int ans,n;

int main(void)
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=i;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=i;j++)
        {
            f[i][j]=a[i][j];
            f[i][j]+=max(f[i-1][j],f[i-1][j-1]);
        }
    }
    for (int i=1;i<=n;i++)
    {
        ans=max(ans,f[n][i]);
    }
    printf("%d\n",ans);
    return 0;
}

 

TB   规律题


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
 
int a[1000010];  
void fun()  
{  
    int i;  
    a[1]=1;  
    a[2]=2;  
    for(i=3;i<=1000010;i++)  
    {  
        if(i&1)  
            a[i]=a[i-1]%1000000000;  
        else  
            a[i]=(a[i-2]+a[i/2])%1000000000;  
    }  
}  
int main()  
{  
    int n;  
    fun();  
    while(scanf("%d",&n)!=EOF)  
    {  
        printf("%d\n",a[n]);  
    }
    return 0;
}

 

TC   捡苹果,原先状态表示用三维,后查看题解使用二维即可AC,可以省去表示在哪棵树的维度;


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

int t,w,a[1010],f[1010][31],ans;

int main(void)
{
    scanf("%d%d",&t,&w);
    for (int i=1;i<=t;i++)
    {
        scanf("%d",&a[i]);
    }
    f[0][0]=0;
    for (int i=1;i<=t;i++)
    {
        f[i][0]=f[i-1][0];
        if (a[i]==1)
        {
            f[i][0]++;
        }
        for (int j=1;j<=i && j<=w;j++)
        {
            f[i][j]=max(f[i-1][j],f[i-1][j-1]);
            if (a[i]==1)
            {
                if (j%2==0)
                    f[i][j]++;
            }
            if (a[i]==2)
            {
                if (j%2==1)
                    f[i][j]++;
            }
            ans=max(ans,f[i][j]);
        }
    }
    printf("%d\n",ans);
    return 0;
}

 

TD  需要用结构体快排,注意两次操作之间需要间隔R,我是判断第一件结尾时间和第二件开头时间相差值,wmf同学直接将结束时间+R,不失为一个好办法。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<cstdio>  
#include<algorithm>  
using namespace std;  
 
int m,n,r,ans,f[1005];
 
struct node  
{
    int s,e,v;
}w[1005];  

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

int main(void)  
{    
    scanf("%d%d%d",&n,&m,&r);  
    w[0].e=-r;  
    for(int i=1;i<=m;i++)  
        scanf("%d%d%d",&w[i].s,&w[i].e,&w[i].v);  
    sort(w+1,w+m+1,cmp);  
    for(int i=1;i<=m;i++)  
    {  
        for(int j=0;j<i;j++)  
            if(w[i].s>=w[j].e+r)  
                f[i]=max(f[i],f[j]+w[i].v);  
        ans=max(ans,f[i]);  
    }  
    printf("%d\n",ans);  
}

 

TE  这题是区间dp较难,看了题解才明白。用dp[i][j]表示将i-j构成回文所需的价值,题目值得注意的是,删去或增加同一个字母意义其实相同,只需要选择代价小的即可。

 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<cstdio>  
#include<cstring>
#include<cmath>
#include<algorithm>  
using namespace std;  
 
int n,m,f[2010][2010];  
int cost[26];
char s[2010],c;

int main(void)  
{    
    scanf("%d%d",&n,&m);
    scanf("%s",s);
    scanf("%c",&c);
    for (int i=1;i<=n;i++)
    {
       int a,b;
       scanf("%c",&c);
       scanf("%d%d",&a,&b);
       cost[c-'a']=min(a,b);
       scanf("%c",&c);
    }
    for (int i=m-1;i>=0;i--)
    {
        for (int j=i+1;j<=m-1;j++)
        {
            f[i][j]=min(f[i+1][j]+cost[s[i]-'a'],f[i][j-1]+cost[s[j]-'a']);
            if (s[i]==s[j])
            {
                f[i][j]=min(f[i+1][j-1],f[i][j]);
            }
        }
    }
    printf("%d\n",f[0][m-1]);
    return 0;
}

 

动规需要想到状态表示和转移方程,题目做多会发现有相似之处,熟能生巧。

(PS:Cow Bessie  和  Farmer John 出现的频率也太高了吧。。。)

 

宣父犹能畏后生,丈夫不可轻年少。

 

 

2017/7/7           Y.W.

STL用法

最全ACM常用STL

STL 中专门用于排列的函数(可以处理存在重复数据集的排列问题)
头文件:#include <algorithm>
using namespace std;
调用: next_permutation(start, end);
注意:函数要求输入的是一个升序排列的序列的头指针和尾指针.
用法:
// 数组
int a[N];
sort(a, a+N);
next_permutation(a, a+N);
// 向量
vector<int> ivec;
sort(ivec.begin(), ivec.end());
next_permutation(ivec.begin(), ivec.end());
例子:
vector<int> myVec;
// 初始化代码
sort(myVec.begin(),myVec.end());
do{
for (i = 0 ;i < size;i ++ ) cout << myVec[i] << " \t " ;
cout << endl;
}while (next_permutation(myVec.begin(), myVec.end()));

ACM/ICPC 竞赛之STL简介
一、关于STL
STL(Standard Template Library,标准模板库)是C++语言标准中的重要组成部分。
STL以模板类和模板函数的形式为程序员提供了各种数据结构和算法的精巧实现,
程序员如果能够充分地利用STL,可以在代码空间、执行时间和编码效率上获得极大的好处。
STL 大致可以分为三大类:算法(algorithm)、容器(Container)、迭代器(iterator)。
STL 容器是一些模板类,提供了多种组织数据的常用方法,例如vector(向量,
类似于数组)、list(列表,类似于链表)、deque(双向队列)、set(集合)、
map(映象)、stack(栈)、queue(队列)、priority_queue(优先队列)等,
通过模板的参数我们可以指定容器中的元素类型。
STL 算法是一些模板函数,提供了相当多的有用算法和操作,从简单如
for_each(遍历)到复杂如stable_sort(稳定排序)。
STL 迭代器是对C 中的指针的一般化,用来将算法和容器联系起来。几乎所有
的STL 算法都是通过迭代器来存取元素序列进行工作的,而STL 中的每一个
容器也都定义了其本身所专有的迭代器,用以存取容器中的元素。有趣的是,
普通的指针也可以像迭代器一样工作。
熟悉了STL 后,你会发现,很多功能只需要用短短的几行就可以实现了。通过
STL,我们可以构造出优雅而且高效的代码,甚至比你自己手工实现的代码效
果还要好。
STL 的另外一个特点是,它是以源码方式免费提供的,程序员不仅可以自由地
使用这些代码,也可以学习其源码,甚至按照自己的需要去修改它。
下面是用STL 写的题Ugly Numbers 的代码:
#include <iostream>
#include <queue>
using namespace std;
typedef pair<unsigned long, int> node_type;
int main()
{
unsigned long result[1500];
priority_queue< node_type, vector<node_type>,
greater<node_type> > Q;
Q.push( make_pair(1, 2) );
for (int i=0; i<1500; i++)
{
node_type node = Q.top();
Q.pop();
switch(node.second){
case 2: Q.push( make_pair(node.first*2, 2) );
case 3: Q.push( make_pair(node.first*3, 3) );
case 5: Q.push( make_pair(node.first*5, 5) );
}
result[i] = node.first;
}
int n;
cin >> n;
while (n>0)
{
cout << result[n-1] << endl;
cin >> n;
}
return 0;
}
在ACM 竞赛中,熟练掌握和运用STL 对快速编写实现代码会有极大的帮助。

二、使用STL
在C++标准中,STL 被组织为以下的一组头文件(注意,是没有.h 后缀的!):
algorithm / deque / functional / iterator / list / map
memory / numeric / queue / set / stack / utility / vector
当我们需要使用STL 的某个功能时,需要嵌入相应的头文件。但要注意的是,
在C++标准中,STL 是被定义在std 命名空间中的。如下例所示:
#include <stack>
int main()
{
std::stack<int> s;
s.push(0);
...
return 0;
}
如果希望在程序中直接引用STL,也可以在嵌入头文件后,用using namespace 语句将std 命名空间导入。如下例所示:
#include <stack>
using namespace std;
int main()
{
stack<int> s;
s.push(0);
...
return 1;
}
STL 是C++语言机制运用的一个典范,通过学习STL 可以更深刻地理解C++
语言的思想和方法。在本系列的文章中不打算对STL 做深入的剖析,而只是想
介绍一些STL 的基本应用。
有兴趣的同学,建议可以在有了一些STL 的使用经验后,认真阅读一下《C++
STL》这本书(电力出版社有该书的中文版)。

ACM/ICPC 竞赛之STL--pair
STL 的<utility>头文件中描述了一个看上去非常简单的模板类pair,用来
表示一个二元组或元素对,并提供了按照字典序对元素对进行大小比较的比较
运算符模板函数。
例如,想要定义一个对象表示一个平面坐标点,则可以:
pair<double, double> p1;
cin >> p1.first >> p1.second;
pair 模板类需要两个参数:首元素的数据类型和尾元素的数据类型。pair 模
板类对象有两个成员:first 和second,分别表示首元素和尾元素。
在<utility>中已经定义了pair 上的六个比较运算符:<、>、<=、>=、==、!=,
其规则是先比较first,first 相等时再比较second,这符合大多数应用的
逻辑。当然,也可以通过重载这几个运算符来重新指定自己的比较逻辑。
除了直接定义一个pair 对象外,如果需要即时生成一个pair 对象,也可以
调用在<utility>中定义的一个模板函数:make_pair。make_pair 需要两
个参数,分别为元素对的首元素和尾元素。
在题1067--Ugly Numbers 中,就可以用pair 来表示推演树上的结点,用
first 表示结点的值,用second 表示结点是由父结点乘以哪一个因子得到的。
#include <iostream>
#include <queue>
using namespace std;
typedef pair<unsigned long, int> node_type;
int main()
{
unsigned long result[1500];
priority_queue< node_type, vector<node_type>,
greater<node_type> > Q;
Q.push( make_pair(1, 2) );
for (int i=0; i<1500; i++)
{
node_type node = Q.top();
Q.pop();
switch(node.second){
case 2: Q.push( make_pair(node.first*2, 2) );
case 3: Q.push( make_pair(node.first*3, 3) );
case 5: Q.push( make_pair(node.first*5, 5) );
}
result[i] = node.first;
}
int n;
cin >> n;
while (n>0)
{
cout << result[n-1] << endl;
cin >> n;
}
return 0;
}
<utility>看上去是很简单的一个头文件,但是<utility>的设计中却浓缩
反映了STL 设计的基本思想。有意深入了解和研究STL 的同学,仔细阅读和
体会这个简单的头文件,不失为一种入门的途径。

ACM/ICPC 竞赛之STL--vector

在STL 的<vector>头文件中定义了vector(向量容器模板类),vector
容器以连续数组的方式存储元素序列,可以将vector 看作是以顺序结构实现
的线性表。当我们在程序中需要使用动态数组时,vector 将会是理想的选择,
vector 可以在使用过程中动态地增长存储空间。
vector 模板类需要两个模板参数,第一个参数是存储元素的数据类型,第二
个参数是存储分配器的类型,其中第二个参数是可选的,如果不给出第二个参
数,将使用默认的分配器。
下面给出几个常用的定义vector 向量对象的方法示例:
vector<int> s;
定义一个空的vector 对象,存储的是int 类型的元素。
vector<int> s(n);
定义一个含有n 个int 元素的vector 对象。
vector<int> s(first, last);
定义一个vector 对象,并从由迭代器first 和last 定义的序列[first,last)中复制初值。
vector 的基本操作有:
s[i] //直接以下标方式访问容器中的元素。
s.front() //返回首元素。
s.back() //返回尾元素。
s.push_back(x) //向表尾插入元素x。
s.size() //返回表长。
s.empty() //当表空时,返回真,否则返回假。
s.pop_back() //删除表尾元素。
s.begin() //返回指向首元素的随机存取迭代器。
s.end() //返回指向尾元素的下一个位置的随机存取迭代器。
s.insert(it, x) //向迭代器it 指向的元素前插入新元素val。
s.insert(it, n, x) //向迭代器it 指向的元素前插入n 个x。
s.insert(it, first, last) //将由迭代器first 和last 所指定的序列[first, last)插入到迭代器it指向的元素前面。
s.erase(it) //删除由迭代器it 所指向的元素。
s.erase(first, last) //删除由迭代器first 和last 所指定的序列[first, last)。
s.reserve(n) //预分配缓冲空间,使存储空间至少可容纳n 个元素。
s.resize(n) //改变序列的长度,超出的元素将会被删除,如果序列需要扩展(原空间小于n),元素默认值将填满扩展出的空间。
s.resize(n, val)
//改变序列的长度,超出的元素将会被删除,如果序列需要扩展(原空间小于n),将用val 填满扩展出的空间。
s.clear() //删除容器中的所有的元素。
s.swap(v) //将s 与另一个vector 对象v 进行交换。
s.assign(first, last)
//将序列替换成由迭代器first 和last 所指定的序列[first, last)。[first, last)不能是原序列中的一部分。要注意的是,resize 操作和clear 操作都是对表的有效元素进行的操作,但
并不一定会改变缓冲空间的大小。
另外,vector 还有其他一些操作如反转、取反等,不再一下列举。
vector 上还定义了序列之间的比较操作运算符(>, <, >=, <=, ==, !=),
可以按照字典序比较两个序列。
还是来看一些示例代码。输入个数不定的一组整数,再将这组整数按倒序输出,
如下所示:
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> L;
int x;
while (cin>>x) L.push_back(x);
for (int i=L.size()-1; i>=0; i--)
cout << L[i] << " ";
cout << endl;
return 0;
}

ACM/ICPC 竞赛之STL--iterator 简介

iterator(迭代器)是用于访问容器中元素的指示器,从这个意义上说,
iterator(迭代器)相当于数据结构中所说的“遍历指针”,也可以把
iterator(迭代器)看作是一种泛化的指针。
STL 中关于iterator(迭代器)的实现是相当复杂的,这里我们暂时不去详细
讨论关于iterator(迭代器)的实现和使用,而只对iterator(迭代器)做一
点简单的介绍。
简单地说,STL 中有以下几类iterator(迭代器):
输入iterator(迭代器),在容器的连续区间内向前移动,可以读取容器内任
意值;
输出iterator(迭代器),把值写进它所指向的容器中;
前向iterator(迭代器),读取队列中的值,并可以向前移动到下一位置
(++p,p++);
双向iterator(迭代器),读取队列中的值,并可以向前向后遍历容器;
随机访问iterator(迭代器), 可以直接以下标方式对容器进行访问,
vector 的iterator(迭代器)就是这种iterator(迭代器);
流iterator(迭代器),可以直接输出、输入流中的值;
每种STL 容器都有自己的iterator(迭代器)子类,下面先来看一段简单的示
例代码:
#include <iostream>
#include <vector>
using namespace std;
main()
{
vector<int> s;
for (int i=0; i<10; i++)
s.push_back(i);
for (vector<int>::iterator it=s.begin(); it!=s.end();it++)
cout << *it << " ";
cout << endl;
return 1;
}
vector 的begin()和end()方法都会返回一个vector::iterator 对象,
分别指向vector 的首元素位置和尾元素的下一个位置(我们可以称之为结束
标志位置)。
对一个iterator(迭代器)对象的使用与一个指针变量的使用极为相似,或者
可以这样说,指针就是一个非常标准的iterator(迭代器)。
再来看一段稍微特别一点的代码:
#include <iostream>
#include <vector>
using namespace std;
main()
{
vector<int> s;
s.push_back(1);
s.push_back(2);
s.push_back(3);
copy(s.begin(), s.end(), ostream_iterator<int>(cout, ""));
cout <<endl;
return 1;
}
这段代码中的copy 就是STL 中定义的一个模板函数,copy(s.begin(),s.end(), ostream_iterator<int>(cout, " "));
的意思是将由s.begin()至s.end()(不含s.end())所指定的序列复制到标准输出流
cout 中,用" "作为每个元素的间隔。也就是说,这句话的作用其实就是将表
中的所有内容依次输出。
iterator(迭代器)是STL 容器和算法之间的“胶合剂”,几乎所有的STL 算
法都是通过容器的iterator(迭代器)来访问容器内容的。只有通过有效地运
用iterator(迭代器),才能够有效地运用STL 强大的算法功能。

ACM/ICPC 竞赛之STL--string

字符串是程序中经常要表达和处理的数据,我们通常是采用字符数组或字符指
针来表示字符串。STL 为我们提供了另一种使用起来更为便捷的字符串的表达
方式:string。string 类的定义在头文件<string>中。
string 类其实可以看作是一个字符的vector,vector 上的各种操作都可以
适用于string,另外,string 类对象还支持字符串的拼合、转换等操作。
下面先来看一个简单的例子:
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s = "Hello! ", name;
cin >> name;
s += name;
s += '!';
cout << s << endl;
return 0;
}
再以题1064--Parencoding 为例,看一段用string 作为容器,实现由P代码还原括号字符串的示例代码片段:
int m;
cin >> m; // P 编码的长度
string str; // 用来存放还原出来的括号字符串
int leftpa = 0; // 记录已出现的左括号的总数
for (int j=0; j<m; j++)
{
int p;
cin >> p;
for (int k=0; k<p-leftpa; k++)
str += '(';
str += ')';
leftpa = p;
}

ACM/ICPC 竞赛之STL--stack/queue

stack(栈)和queue(队列)也是在程序设计中经常会用到的数据容器,STL
为我们提供了方便的stack(栈)的queue(队列)的实现。
准确地说,STL 中的stack 和queue 不同于vector、list 等容器,而是对
这些容器的重新包装。这里我们不去深入讨论STL 的stack 和queue 的实现
细节,而是来了解一些他们的基本使用。

1、stack
stack 模板类的定义在<stack>头文件中。
stack 模板类需要两个模板参数,一个是元素类型,一个容器类型,但只有元
素类型是必要的,在不指定容器类型时,默认的容器类型为deque。
定义stack 对象的示例代码如下:
stack<int> s1;
stack<string> s2;
stack 的基本操作有:
入栈,如例:s.push(x);
出栈,如例:s.pop();注意,出栈操作只是删除栈顶元素,并不返回该元素。
访问栈顶,如例:s.top()
判断栈空,如例:s.empty(),当栈空时,返回true。
访问栈中的元素个数,如例:s.size()
下面是用string 和stack 写的解题1064--Parencoding 的程序。
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main()
{
int n;
cin >> n;
for (int i=0; i<n; i++)
{
int m;
cin >> m;
string str;
int leftpa = 0;
for (int j=0; j<m; j++) // 读入P 编码,构造括号字符串
{
int p;
cin >> p;
for (int k=0; k<p-leftpa; k++)
str += '(';
str += ')';
leftpa = p;
}
stack<int> s;
for (string::iterator it=str.begin();it!=str.end(); it++)
{ // 构造M 编码
if (*it=='(') s.push(1);
else{
int p = s.top(); s.pop();
cout << p << " ";
if (!s.empty()) s.top() += p;
}
}
cout << endl;
}
return 0;
}
2、queue
queue 模板类的定义在<queue>头文件中。

与stack 模板类很相似,queue 模板类也需要两个模板参数,一个是元素类
型,一个容器类型,元素类型是必要的,容器类型是可选的,默认为deque 类
型。
定义queue 对象的示例代码如下:
queue<int> q1;
queue<double> q2;
queue 的基本操作有:
入队,如例:q.push(x); 将x 接到队列的末端。
出队,如例:q.pop(); 弹出队列的第一个元素,注意,并不会返回被弹出元
素的值。
访问队首元素,如例:q.front(),即最早被压入队列的元素。
访问队尾元素,如例:q.back(),即最后被压入队列的元素。
判断队列空,如例:q.empty(),当队列空时,返回true。
访问队列中的元素个数,如例:q.size()

3、priority_queue

在<queue>头文件中,还定义了另一个非常有用的模板类
priority_queue(优先队列)。优先队列与队列的差别在于优先队列不是按
照入队的顺序出队,而是按照队列中元素的优先权顺序出队(默认为大者优先,
也可以通过指定算子来指定自己的优先顺序)。
priority_queue 模板类有三个模板参数,第一个是元素类型,第二个容器
类型,第三个是比较算子。其中后两个都可以省略,默认容器为vector,默
认算子为less,即小的往前排,大的往后排(出队时序列尾的元素出队)。
定义priority_queue 对象的示例代码如下:
priority_queue<int> q1;
priority_queue< pair<int, int> > q2; // 注意在两个尖括号之间
一定要留空格。
priority_queue<int, vector<int>, greater<int> > q3; // 定
义小的先出队
priority_queue 的基本操作与queue 相同。
初学者在使用priority_queue 时,最困难的可能就是如何定义比较算子了。
如果是基本数据类型,或已定义了比较运算符的类,可以直接用STL 的less
算子和greater 算子——默认为使用less 算子,即小的往前排,大的先出队。
如果要定义自己的比较算子,方法有多种,这里介绍其中的一种:重载比较运
算符。优先队列试图将两个元素x 和y 代入比较运算符(对less 算子,调用
x<y,对greater 算子,调用x>y),若结果为真,则x 排在y 前面,y 将先
于x 出队,反之,则将y 排在x 前面,x 将先出队。
看下面这个简单的示例:
#include <iostream>
#include <queue>
using namespace std;
class T
{
public:
int x, y, z;
T(int a, int b, int c):x(a), y(b), z(c){}
};
bool operator < (const T &t1, const T &t2)
{
return t1.z < t2.z; // 按照z 的顺序来决定t1 和t2 的顺序
}
int main()
{
priority_queue<T> q;
q.push(T(4,4,3));
q.push(T(2,2,5));
q.push(T(1,5,4));
q.push(T(3,3,6));
while (!q.empty()){
T t = q.top(); q.pop();
cout << t.x << " " << t.y << " " << t.z << endl;
}
return 0;
}
输出结果为(注意是按照z 的顺序从大到小出队的):
3 3 6
2 2 5
1 5 4
4 4 3
再看一个按照z 的顺序从小到大出队的例子:
#include <iostream>
#include <queue>
using namespace std;
class T
{
public:
int x, y, z;
T(int a, int b, int c):x(a), y(b), z(c)
{
}
};
bool operator > (const T &t1, const T &t2)
{
return t1.z > t2.z;
}
int main()
{
priority_queue<T, vector<T>, greater<T> > q;
q.push(T(4,4,3));
q.push(T(2,2,5));
q.push(T(1,5,4));
q.push(T(3,3,6));
while (!q.empty())
{
T t = q.top(); q.pop();
cout << t.x << " " << t.y << " " << t.z << endl;
}
return 0;
}
输出结果为:
4 4 3
1 5 4
2 2 5
3 3 6
如果我们把第一个例子中的比较运算符重载为:
bool operator < (const T &t1, const T &t2){
return t1.z > t2.z; // 按照z 的顺序来决定t1 和t2 的顺序
}
则第一个例子的程序会得到和第二个例子的程序相同的输出结果。
再回顾一下用优先队列实现的题1067--Ugly Numbers 的代码:
#include <iostream>
#include <queue>
using namespace std;
typedef pair<unsigned long int, int> node_type;
int main( int argc, char *argv[] )
{
unsigned long int result[1500];
priority_queue< node_type, vector<node_type>,
greater<node_type> > Q;
Q.push( make_pair(1, 3) );
for (int i=0; i<1500; i++)
{
node_type node = Q.top();
Q.pop();
switch(node.second){
case 3: Q.push( make_pair(node.first*2, 3) );
case 2: Q.push( make_pair(node.first*3, 2) );
case 1: Q.push( make_pair(node.first*5, 1) );
}
result[i] = node.first;
}
int n;
cin >> n;
while (n>0){
cout << result[n-1] << endl;
cin >> n;
}
return 1;
}

ACM/ICPC 竞赛之STL--map

在STL 的头文件<map>中定义了模板类map 和multimap,用有序二叉树来
存贮类型为pair<const Key, T>的元素对序列。序列中的元素以const Key
部分作为标识,map 中所有元素的Key 值都必须是唯一的,multimap 则允许
有重复的Key 值。
可以将map 看作是由Key 标识元素的元素集合,这类容器也被称为“关联容
器”,可以通过一个Key 值来快速确定一个元素,因此非常适合于需要按照Key
值查找元素的容器。
map 模板类需要四个模板参数,第一个是键值类型,第二个是元素类型,第三
个是比较算子,第四个是分配器类型。其中键值类型和元素类型是必要的。
map 的基本操作有:
1、定义map 对象,例如:
map<string, int> m;
2、向map 中插入元素对,有多种方法,例如:
m[key] = value;
[key]操作是map 很有特色的操作,如果在map 中存在键值为key 的元素对,
则返回该元素对的值域部分,否则将会创建一个键值为key 的元素对,值域为
默认值。所以可以用该操作向map 中插入元素对或修改已经存在的元素对的值
域部分。
m.insert( make_pair(key, value) );
也可以直接调用insert 方法插入元素对,insert 操作会返回一个pair,当
map 中没有与key 相匹配的键值时,其first 是指向插入元素对的迭代器,
其second 为true;若map 中已经存在与key 相等的键值时,其first 是
指向该元素对的迭代器,second 为false。
3、查找元素对,例如:
int i = m[key];
要注意的是,当与该键值相匹配的元素对不存在时,会创建键值为key 的元素
对。
map<string, int>::iterator it = m.find(key);
如果map 中存在与key 相匹配的键值时,find 操作将返回指向该元素对的迭
代器,否则,返回的迭代器等于map 的end()(参见vector 中提到的begin
和end 操作)。
4、删除元素对,例如:
m.erase(key);
删除与指定key 键值相匹配的元素对,并返回被删除的元素的个数。
m.erase(it);
删除由迭代器it 所指定的元素对,并返回指向下一个元素对的迭代器。
看一段简单的示例代码:
#include<map>
#include<iostream>
using namespace std;
typedef map<int, string, less<int> > M_TYPE;
typedef M_TYPE::iterator M_IT;
typedef M_TYPE::const_iterator M_CIT;
int main()
{
M_TYPE MyTestMap;
MyTestMap[3] = "No.3";
MyTestMap[5] = "No.5";
MyTestMap[1] = "No.1";
MyTestMap[2] = "No.2";
MyTestMap[4] = "No.4";
M_IT it_stop = MyTestMap.find(2);
cout << "MyTestMap[2] = " << it_stop->second << endl;
it_stop->second = "No.2 After modification";
cout << "MyTestMap[2] = " << it_stop->second << endl;
cout << "Map contents : " << endl;
for(M_CIT it = MyTestMap.begin(); it != MyTestMap.end();it++)
{
cout << it->second << endl;
}
return 0;
}
程序执行的输出结果为:
MyTestMap[2] = No.2
MyTestMap[2] = No.2 After modification
Map contents :
No.1
No.2 After modification
No.3
No.4
No.5
再看一段简单的示例代码:
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<string, int> m;
m["one"] = 1;
m["two"] = 2;
// 几种不同的insert 调用方法
m.insert(make_pair("three", 3));
m.insert(map<string, int>::value_type("four", 4));
m.insert(pair<string, int>("five", 5));
string key;
while (cin>>key)
{
map<string, int>::iterator it = m.find(key);
if (it==m.end())
{
cout << "No such key!" << endl;
}
else
{
cout << key << " is " << it->second << endl;
cout << "Erased " << m.erase(key) << endl;
}
}
return 0;
}

ACM/ICPC 竞赛之STL--algorithm

<algorithm>无疑是STL 中最大的一个头文件,它是由一大堆模板函数组成
的。
下面列举出<algorithm>中的模板函数:
adjacent_find / binary_search / copy / copy_backward / count
/ count_if / equal / equal_range / fill / fill_n / find /
find_end / find_first_of / find_if / for_each / generate /
generate_n / includes / inplace_merge / iter_swap /
lexicographical_compare / lower_bound / make_heap / max /
max_element / merge / min / min_element / mismatch /
next_permutation / nth_element / partial_sort /
partial_sort_copy / partition / pop_heap / prev_permutation
/ push_heap / random_shuffle / remove / remove_copy /
remove_copy_if / remove_if / replace / replace_copy /
replace_copy_if / replace_if / reverse / reverse_copy /
rotate / rotate_copy / search / search_n / set_difference /
set_intersection / set_symmetric_difference / set_union /
sort / sort_heap / stable_partition / stable_sort / swap /
swap_ranges / transform / unique / unique_copy / upper_bound
如果详细叙述每一个模板函数的使用,足够写一本书的了。还是来看几个简单
的示例程序吧。
示例程序之一,for_each 遍历容器:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int Visit(int v) // 遍历算子函数
{
cout << v << " ";
return 1;
}
class MultInt // 定义遍历算子类
{
private:
int factor;
public:
MultInt(int f) : factor(f){}
void operator()(int &elem) const{
elem *= factor;
}
};
int main(){
vector<int> L;
for (int i=0; i<10; i++) L.push_back(i);
for_each(L.begin(), L.end(), Visit);
cout << endl;
for_each(L.begin(), L.end(), MultInt(2));
for_each(L.begin(), L.end(), Visit);
cout << endl;
return 0;
}
程序的输出结果为:
0 1 2 3 4 5 6 7 8 9
0 2 4 6 8 10 12 14 16 18
示例程序之二,min_element/max_element,找出容器中的最小/最大值:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
vector<int> L;
for (int i=0; i<10; i++) L.push_back(i);
vector<int>::iterator min_it = min_element(L.begin(),
L.end());
vector<int>::iterator max_it = max_element(L.begin(),
L.end());
cout << "Min is " << *min_it << endl;
cout << "Max is " << *max_it << endl;
return 1;
}
程序的输出结果为:
Min is 0
Max is 9
示例程序之三,sort 对容器进行排序:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void Print(vector<int> &L){
for (vector<int>::iterator it=L.begin(); it!=L.end();
it++)
cout << *it << " ";
cout << endl;
}
int main(){
vector<int> L;
for (int i=0; i<5; i++) L.push_back(i);
for (int i=9; i>=5; i--) L.push_back(i);
Print(L);
sort(L.begin(), L.end());
Print(L);
sort(L.begin(), L.end(), greater<int>()); // 按降序排序
Print(L);
return 0;
}
程序的输出结果为:
0 1 2 3 4 9 8 7 6 5
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
示例程序之四,copy 在容器间复制元素:
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
// 先初始化两个向量v1 和v2
vector <int> v1, v2;
for (int i=0; i<=5; i++) v1.push_back(10*i);
for (int i=0; i<=10; i++) v2.push_back(3*i);
cout << "v1 = ( " ;
for (vector <int>::iterator it=v1.begin(); it!=v1.end();
it++)
cout << *it << " ";
cout << ")" << endl;
cout << "v2 = ( " ;
for (vector <int>::iterator it=v2.begin(); it!=v2.end();
it++)
cout << *it << " ";
cout << ")" << endl;
// 将v1 的前三个元素复制到v2 的中间
copy(v1.begin(), v1.begin()+3, v2.begin()+4);
cout << "v2 with v1 insert = ( " ;
for (vector <int>::iterator it=v2.begin(); it!=v2.end();
it++)
cout << *it << " ";
cout << ")" << endl;
// 在v2 内部进行复制,注意参数2 表示结束位置,结束位置不参与复

copy(v2.begin()+4, v2.begin()+7, v2.begin()+2);
cout << "v2 with shifted insert = ( " ;
for (vector <int>::iterator it=v2.begin(); it!=v2.end();
it++)
cout << *it << " ";
cout << ")" << endl;
return 1;
}
程序的输出结果为:
v1 = ( 0 10 20 30 40 50 )
v2 = ( 0 3 6 9 12 15 18 21 24 27 30 )
v2 with v1 insert = ( 0 3 6 9 0 10 20 21 24 27 30 )
v2 with shifted insert = ( 0 3 0 10 20 10 20 21 24 27 30 )

STL in ACM

容器(Container):
迭代器(iterator): 指针
内部实现: 数组 // 就是没有固定大小的数组,vector 直接翻译是向量
vector // T 就是数据类型,Alloc 是关于内存的一个什么东西,一般是使
用默认参数。
支持操作:
begin(), //取首个元素,返回一个iterator
end(), //取末尾(最后一个元素的下一个存储空间的地址)
size(), //就是数组大小的意思
clear(), //清空
empty(), //判断vector 是否为空
[ ] //很神奇的东东,可以和数组一样操作
//举例: vector a; //定义了一个vector
//然后我们就可以用a[i]来直接访问a 中的第i + 1 个元素!和数组的下标
一模一样!
push_back(), pop_back() //从末尾插入或弹出
insert() O(N) //插入元素,O(n)的复杂度
erase() O(N) //删除某个元素,O(n)的复杂度
可以用于数组大小不定且空间紧张的情况
Iterator 用法举例:
int main(){
int n,i;
vector vi; //类似于我们定义一个数组,同 int vi[1000]; 但vector
的大小是自动调整的
vector ::iterator itr; //两个冒号
while (scanf("%d",&n) != EOF) vi.push_back(n);
for (i = 0 ; i < vi.size() ; i++) printf("%d\n",vi[i]);
for (itr = vi.begin() ; itr != vi.end() ; itr++)
printf("%d\n",*itr);
return 0;
}
类似:双端队列,两头都支持进出
支持push_front()和pop_front()
是的精简版:) //栈,只支持从末尾进出
支持push(), pop(), top()
是的精简版 //单端队列,就是我们平时所说的队列,一头进,另一头出
支持push(), pop(), front(), back()
内部实现: 双向链表 //作用和vector 差不多,但内部是用链表实现
list
支持操作:
begin(), end(), size(), clear(), empty()
push_back(), pop_back() //从末尾插入或删除元素
push_front(), pop_front()
insert() O(1) //链表实现,所以插入和删除的复杂度的O(1)
erase() O(1)
sort() O(nlogn),不同于中的sort
//不支持[ ]操作!
内部实现: 红黑树 //Red-Black Tree,一种平衡的二叉排序树
set //又是一个Compare 函数,类似于qsort 函数里的那个Compare 函数,
作为红黑树在内部实现的比较方式
insert() O(logn)
erase() O(logn)
find() O(logn) 找不到返回a.end()
lower_bound() O(logn) 查找第一个不小于k 的元素
upper_bound() O(logn) 查找第一个大于k 的元素
equal_range() O(logn) 返回pair
允许重复元素的
的用法及Compare 函数示例:
struct SS {int x,y;};
struct ltstr {
bool operator() (SS a, SS b)
{return a.x < b.x;} //注意,按C 语言习惯,double 型要写成这样:
return a.x < b.x ? 1 : 0;
};
int main() {
set st;

}
内部实现: pair 组成的红黑树 //map 中文意思:映射!!
map //就是很多pair 组成一个红黑树
insert() O(logn)
erase() O(logn)
find() O(logn) 找不到返回a.end()
lower_bound() O(logn) 查找第一个不小于k 的元素
upper_bound() O(logn) 查找第一个大于k 的元素
equal_range() O(logn) 返回pair
[key]运算符 O(logn) *** //这个..太猛了,怎么说呢,数组有一个下标,
如a[i],这里i 是int 型的。数组可以认为是从int 印射到另一个类型的印
射,而map 是一个任意的印射,所以i 可以是任何类型的!
允许重复元素, 没有[]运算符
内部实现: 堆 //优先队列,听RoBa 讲得,似乎知道原理了,但不明白干
什么用的
priority_queue
支持操作:
push() O(n)
pop() O(n)
top() O(1)
See also: push_heap(), pop_heap() … in
用法举例:
priority_queue maxheap; //int 最大堆
struct ltstr { //又是这么个Compare 函数,重载运算符???不明
白为什么要这么写...反正这个Compare 函数对我来说是相当之神奇。RoBa
说了,照着这么写就是了。
bool operator()(int a,int b)
{return a > b;}
};
priority_queue <INT,VECTOR,ltstr> minheap; //int 最小堆
1.sort()
void sort(RandomAccessIterator first, RandomAccessIterator
last);
void sort(RandomAccessIterator first, RandomAccessIterator
last, StrictWeakOrdering comp);
区间[first,last)
Quicksort,复杂度O(nlogn)
(n=last-first,平均情况和最坏情况)
用法举例:
1.从小到大排序(int, double, char, string, etc)
const int N = 5;
int main()
{
int a[N] = {4,3,2,6,1};
string str[N] = {“TJU”,”ACM”,”ICPC”,”abc”,”kkkkk”};
sort(a,a+N);
sort(str,str+N);
return 0;
}
2.从大到小排序(需要自己写comp 函数)
const int N = 5;
int cmp(int a,int b) {return a > b;}
int main()
{
int a[N] = {4,3,2,6,1};
sort(a,a+N,cmp);
return 0;
}
3. 对结构体排序
struct SS {int first,second;};
int cmp(SS a,SS b) {
if (a.first != b.first) return a.first < b.first;
return a.second < b.second;
}
v.s. qsort() in C (平均情况O(nlogn),最坏情况
O(n^2)) //qsort 中的cmp 函数写起来就麻烦多了!
int cmp(const void *a,const void *b) {
if (((SS*)a)->first != ((SS*)b)->first)
return ((SS*)a)->first – ((SS*)b)->first;
return ((SS*)a)->second – ((SS*)b)->second;
}
qsort(array,n,sizeof(array[0]),cmp);
sort()系列:
stable_sort(first,last,cmp); //稳定排序
partial_sort(first,middle,last,cmp);//部分排序
将前(middle-first)个元素放在[first,middle)中,其余元素位置不定
e.g.
int A[12] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};
partial_sort(A, A + 5, A + 12);
// 结果是 "1 2 3 4 5 11 12 10 9 8 7 6".
Detail: Heapsort ,
O((last-first)*log(middle-first))
sort()系列:
partial_sort_copy(first, last, result_first, result_last,
cmp);
//输入到另一个容器,不破坏原有序列
bool is_sorted(first, last, cmp);
//判断是否已经有序
nth_element(first, nth, last, cmp);
//使[first,nth)的元素不大于[nth,last), O(N)
e.g. input: 7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5
nth_element(A,A+6,A+12);
Output: 5 2 6 1 4 3 7 8 9 10 11 12
2. binary_search()
bool binary_search(ForwardIterator first, ForwardIterator
last, const LessThanComparable& value);
bool binary_search(ForwardIterator first, ForwardIterator
last, const T& value, StrictWeakOrdering comp);
在[first,last)中查找value,如果找到返回Ture,否则返回False
二分检索,复杂度O(log(last-first))
v.s. bsearch() in C
Binary_search()系列
itr upper_bound(first, last, value, cmp);
//itr 指向大于value 的第一个值(或容器末尾)
itr lower_bound(first, last, value, cmp);
//itr 指向不小于valude 的第一个值(或容器末尾)
pair equal_range(first, last, value, cmp);
//找出等于value 的值的范围 O(2*log(last – first))
int A[N] = {1,2,3,3,3,5,8}
*upper_bound(A,A+N,3) == 5
*lower_bound(A,A+N,3) == 3
make_heap(first,last,cmp) O(n)
push_heap(first,last,cmp) O(logn)
pop_heap(first,last,cmp) O(logn)
is_heap(first,last,cmp) O(n)
e.g:
vector vi;
while (scanf(“%d”,&n) != EOF) {
vi.push_back(n);
push_heap(vi.begin(),vi.end());
}
Others interesting:
next_permutation(first, last, cmp)
prev_permutation(first, last, cmp)
//both O(N)
min(a,b);
max(a,b);
min_element(first, last, cmp);
max_element(first, last, cmp);
Others interesting:
fill(first, last, value)
reverse(first, last)
rotate(first,middle,last);
itr unique(first, last);
//返回指针指向合并后的末尾处
random_shuffle(first, last, rand)
头文件
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;

2017/7/6 东海集训

https://vjudge.net/contest/164345#problem

vjudge上的题目2.2一往直前贪心法

今日成果4T

TA 为字符串贪心    刚开始时理解题目不到位,没有考虑前后字母相同的情况就一直W,最后在A.K.Z.的帮助下得以脱困。

下为code


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

char z,c[2001],s[2001];
int l,n;

int main(void)
{
    scanf("%d ",&n);
    int aa=0;
    while (scanf("%c",&z)==1)
    {
        if (z>='A' && z<='Z')
        {
            aa++;
            c[aa]=z;
        }
    }
    int he=1,ta=n,now=0;
    for (int i=1;i<=n;i++)
    {
        int h=he,t=ta;
        while (c[h]==c[t] && h<t)
        {
            h++;
            t--;
        }
        if (c[h]<c[t])
        {
            now++;
            s[now]=c[he];
            he++;
        }
        else
        {
            now++;
            s[now]=c[ta];
            ta--;
        }
    }
    for (int i=1;i<=n;i++)
    {
        printf("%c",s[i]);
        if (i%80==0)
        {
            printf("\n");
        }
    }
    printf("\n");
    return 0;
}

TB 为用最少的线段覆盖点,水题,不多做评论。

下为code


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

int a[1010],vis[1010],p[1010],ans,n,r;

int main(void)
{
    while (1)
    {
        ans=0;
        scanf("%d%d",&r,&n);
        if (r==-1 && n==-1)
        {
            break;
        }
        memset(a,0,sizeof a);
        memset(p,0,sizeof p);
        for (int i=1;i<=n;i++)
        {
            scanf("%d",&p[i]);
        }
        sort(p+1,p+n+1);
        int now=1;
        while (now<=n)
        {
            int nn=now;
            for (int i=now+1;i<=n;i++)
            {
                if (p[i]-p[now]<=r)
                {
                    nn++;
                }
                else
                break;
            }
            now=nn;
            for (int i=now+1;i<=n;i++)
            {
                if (p[i]-p[now]<=r)
                {
                    nn++;
                }
                else
                break;
            }
            now=nn;
            ans++;
            now++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

TC 与合并果子非常相似,由于时间限制为2s,所以刚开始每次暴力查找最小和次小的值然后合并,耗时1s+;后来发现可以使用系统自带的优先队列维护,耗时40ms+。

首先是暴力


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
[cce_cpp]
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

int n;
int c;
long long a[20010],ans;

void swap(int m,int n)
{
    long long cc=a[m];
    a[m]=a[n];
    a[n]=cc;
}

void se(int x)
{
    int q=x;
    for (int i=q+1;i<=n;i++)
    {
        if (a[i]<a[q])
        {
            q=i;
        }
    }
    swap(q,x);
}


int main(void)
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    sort(a+1,a+1+n);
    se(1);
    se(2);
    for (int i=2;i<=n;i++)
    {
        a[i]=a[i-1]+a[i];
        ans+=a[i];
        se(i);
        se(i+1);
    }
    printf("%lld\n",ans);
    return 0;
}
[/cce_cpp]

优先队列


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>  
#include<vector>
using namespace std;

int n;
int c;
long long a[20010];
long long ans;

int main(void)
{
    scanf("%d",&n);
    priority_queue<long long,vector<long long>,greater<long long> > que;
    for (int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        que.push(a[i]);
    }
    while (que.size()>1)
    {
        int m1=que.top();
        que.pop();
        int m2=que.top();
        que.pop();
        ans+=m1+m2;
        que.push(m1+m2);
    }

    printf("%lld\n",ans);
    return 0;
}

TD  为最小区间覆盖问题,用快速排序处理头尾时间,再用贪心for一遍便可得到正解,因为调程序时少删了一行导致W,感谢wmf同学指出错误。(真的很低级Σ( ° △ °|||))

下为code


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

int n,t,ans,a[25010],b[25010];

void qsort(int l,int r)
{
    int i,j,mid,p;
    i=l;
    j=r;
    mid=a[(l+r)/2];
    do
    {
        while (a[i]<mid) i++;
        while (a[j]>mid) j--;
        if (i<=j)
        {
            p=a[i];
            a[i]=a[j];
            a[j]=p;
            p=b[i];
            b[i]=b[j];
            b[j]=p;
            i++;
            j--;
        }
    }while (i<=j);
    if (l<j) qsort(l,j);
    if (i<r) qsort(i,r);
}

int main(void)
{
    scanf("%d%d",&n,&t);
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
        if (a[i]>b[i])
        {
            int te=a[i];
            a[i]=b[i];
            b[i]=te;
        }
    }
    qsort(1,n);
    int maxx=0,now=1;
    while (maxx<t)
    {
        int minn=maxx+1;
        for (int i=now;i<=n;i++)
        {
            if (a[i]<=minn && b[i]>=minn)
            {
                maxx=max(maxx,b[i]);
            }
            else
            if (a[i]>minn)
            {
                now=i;
                break;
            }
        }
        if (minn>maxx)
        {
            break;
        }
        else
        {
            ans++;
        }
    }
    if (maxx<t)
    printf("-1\n");
    else
    {
        printf("%d\n",ans);
    }
    return 0;
}

 

贪心的题目属于比较容易理解的,但需要注意细节,并且要掌握各种技巧(堆,优先队列,字符串,二叉树......)

 

细节决定成败,代码改变人生。

2017/7/6        Y.W.