内容：并查集，堆，栈，队列
总结：听课状态良好，但是，并查集的一些地方模模糊糊没有听懂，堆也是模模糊糊，栈和队列简单点的东西可以理解并应用，但一旦遇到稍微复杂点的题就懵。总之，还是需要以后多加练习。
下午的测试：
总结：答的一塌糊涂。本来第一题AC是准了。然而没有注意的把两个重要的int型变量，设置成了char型，导致了整个题的RE。考试后十分痛惜，但在平常练习中犯的错误总要比考试的时候犯的错误要好的多。这次的教训痛击了我，得到的结论是，无论测试数据通过与否，一定要回头从新检查一下自己的代码。一定不能因为自己感觉对了就放到哪里不管。
OIER密码
【问题描述】
吉林省的OIER们保密意识很强，总是将信息加密。
有一个仅含小写字母的字符串，我们把它按如下方法加密：
步骤1：把所有连续的相同字母都用一个字母代替。比如 aaabbbb 被替换为 ab。
步骤2：在随机的位置插入两个相同的小写字母。重复 步骤2 很多次。
下面是一个加密的实例
初始字符串 jjjlloooiieerr
执行步骤1 之后变成 jloier
插入 aa 之后变成jloiaaer
插入 bb 之后变成jloiabbaer
插入 ll 之后变成jllloiabbaer
现在我们给定加密后的字符串，求执行 步骤1 之后的字符串是什么。
【输入格式】
从文件password.in中输入数据。
一个字符串，表示加密后的字符串。
【输出格式】
输出到文件password.out中。
一个字符串，表示执行步骤1 之后的字符串。
【样例输入】
jllloiabbaer
【样例输出】
jloier
【数据规模与约定】
对于30%数据, 加密后的字符串的长度<=1000
对于70%数据, 加密后的字符串的长度<=100000
对于100%数据, 加密后的字符串的长度<=1000000
1 #include <cstdio> 2 #include <cstring> 3 #include <stack> 4 #include <queue> 5 using namespace std; 6 char str[1000010]; 7 int main() 8 { 9 freopen("password.in","r",stdin); 10 freopen("password.out","w",stdout); 11 char k; 12 int top=0,list=1; 13 while(scanf("%c",&k)!=EOF) 14 { 15 if(str[top]==k) 16 { 17 top--; 18 list--; 19 } 20 else 21 { 22 str[list++]=k; 23 top++; 24 } 25 26 } 27 for(int i=1;i<list;i++) 28 printf("%c",str[i]); 29 fclose(stdin); 30 fclose(stdout); 31 return 0; 32 }
思路：运用栈的思想，每一读一个字符压入栈中一个，遇到相同的字符时弹出栈顶。
投资
【问题描述】
吉林省的OIER们投资了一支股票，大家都知道股票有赚有赔，现给出n天里这支股票的涨跌情况，都为整数，涨为正，跌为负。OIER们想知道天数在s到e之间的这只股票涨跌的最大连续和。
【输入格式】
从文件invest.in中输入数据。
第一行有三个正整数n、s和e ，同上描述。
接下来有n行，每行一个整数ai，组成数列，数列的顺序不可以变换。
【输出格式】
输出到文件invest.out中。
输出长度在s和e之间连续的数列数的和的最大值。
【样例输入】
6 2 4
4
-3
9
12
-8
9
【样例输出】
22
【数据规模与约定】
对于30%数据，1<=s<=e<=n<=100
对于100%数据，1<=s<=e<=n<=100000
对于 100%数据，-10000<=ai<=10000
总结：这道题是上午讲过的题，运用了队列，上午的时候这道题就每一听懂，考试的时候想，不能空着啊，写个暴力吧，结果ML。内存炸了。教训就是下次开数组最好算好内存大小。
先放上正确代码，回头再仔细研究一下。
1 #include<stdio.h> 2 int a[100002],k[100002]; 3 int max(int x,int y) 4 { 5 return x>y?x:y; 6 } 7 int qin() 8 { 9 char ch; 10 int in=0; 11 bool flag=0; 12 while(ch!=‘-‘&&!(ch>=‘0‘&&ch<=‘9‘)) 13 ch=getchar(); 14 if(ch==‘-‘) 15 { 16 flag=1; 17 ch=getchar(); 18 } 19 do 20 { 21 in=in*10+ch-‘0‘; 22 ch=getchar(); 23 } 24 while(ch>=‘0‘&&ch<=‘9‘); 25 if(flag) 26 in*=-1; 27 return in; 28 } 29 int co() 30 { 31 freopen("invest.in","r",stdin); 32 freopen("invest.out","w",stdout); 33 int n,i,t,head,tail,s,ans=-10000000,j; 34 scanf("%d%d%d",&n,&s,&t); 35 for(i=1;i<=n;i++) 36 a[i]=a[i-1]+qin(); 37 head=tail=1; 38 for(i=s;i<=n;i++) 39 { 40 while(head<tail&&i-k[head]>t) head++; 41 while(head<tail&&a[i-s]<a[k[tail-1]]) tail--;//k[a[i]]????? 42 k[tail++]=i-s; 43 ans=max(ans,a[i]-a[k[head]]); 44 } 45 printf("%d\n",ans); 46 } 47 int ccc=co(); 48 int main(){; 49 }
学习计划
【问题描述】
吉林省OIER们都是爱学习的同学，所以他们想学习更多的课程。长春市教育局开设了“云课程”网络学习平台，一共有n门课程，但这个平台有个弊端，就是每门课程在时间Ti之后将不再开放，并且每门课程要想学会需要Ci的时间，聪明的你帮助吉林省OIER们计划一下，使他们能够学习最多的课程。
【输入格式】
从文件plan.in中输入数据。
第一行，一个整数n
下面n行，每行两个数Ti和Ci
【输出格式】
输出到文件plan.out中。
一行一个整数，完成的最多任务数。
【样例输入】
4
5 1
3 2
7 6
1 1
【样例输出】
3
【数据规模与约定】
对于 30%数据，n<=100
对于 100%数据，n<=100000
总结：开始的时候有些思路，但越往后想越偏，最后就放弃了，胡乱的写了一个代码。考后讲题的时候想了想，想明白了，敲了一遍，也算是有了这种题的经验，但要想加强的话，还需要多加练习。
1 #include <cstdio> 2 #include <vector> 3 #include <queue> 4 #include <algorithm> 5 using namespace std; 6 priority_queue<int>q; 7 struct st 8 { 9 int a; 10 int b; 11 }; 12 bool cmp(st x,st y) 13 { 14 return x.a<y.a; 15 } 16 st m[100010]; 17 int main() 18 { 19 freopen("plan.in","r",stdin); 20 freopen("plan.out","w",stdout); 21 int n,s=0,k=0; 22 scanf("%d",&n); 23 for(int i=0;i<n;i++) scanf("%d%d",&m[i].a,&m[i].b); 24 sort(m,m+n,cmp); 25 for(int i=0;i<n;i++) 26 { 27 if(m[i].a<m[i].b) continue; 28 if(m[i].b+s<=m[i].a) 29 { 30 q.push(m[i].b); 31 s+=m[i].b; 32 k++; 33 } 34 else 35 if(m[i].b<q.top()) 36 { 37 s-=q.top(); 38 s+=m[i].b; 39 q.pop(); 40 q.push(m[i].b); 41 42 } 43 } 44 printf("%d",k); 45 return 0; 46 }
收获：
通过一天的学习，初步了解了并查集等数据结构。学到了很多不会的东西。发现了很多平时自己做题没有意识到的问题。
原文：http://www.cnblogs.com/zby-ccsygz/p/6275026.html