第一题：音量调节 (changingsounds)
时间限制：1秒
空间限制：64 MB
输入：changingsounds.in
输出：changingsounds.out
问题描述
一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都要改变一次音量。在演出开始之前，他已经做好了一个列表，里面写着在每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选择调高也可以调低。
音量用一个整数描述。输入文件中给定整数beginLevel，代表吉他刚开始的音量，以及整数maxLevel，代表吉他的最大音量。音量不能小于0也不能大于maxLevel。输入文件中还给定了n个整数，表示在第i首歌开始之前吉他手想要改变的音量是多少。
吉他手想以最大的音量演奏最后一首歌，你的任务是找到这个最大音量是多少。
输入
第一行依次为三个整数：n, beginLevel, maxlevel。
第二行依次为n个整数：。
限制：，，，。
输出
输出演奏最后一首歌的最大音量。如果吉他手无法避免音量低于0或者高于maxLevel，输出-1。
样例输入
3 5 10
5 3 7
样例输出
10
样例输入
4 8 20
15 2 9 10
样例输出
-1
dp就好了，边界注意一下
#include<iostream> #include<cstdlib> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int dp[51][1001],n,be,maxl,c[51]; inline void Jimmy(){ scanf("%d%d%d",&n,&be,&maxl); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) scanf("%d",&c[i]); dp[0][be]=1; for(int i=1;i<=n;i++){ for(int j=maxl;j>=0;j--){ if(dp[i-1][j]==1 && j+c[i]<=maxl && j+c[i]>=0) dp[i][j+c[i]]=1; if(dp[i-1][j]==1 && j-c[i]<=maxl && j-c[i]>=0) dp[i][j-c[i]]=1; } } int Flag=0; for(int j=maxl;j>=1;j--) if(dp[n][j]==1){ Flag=j; break; } if(Flag) printf("%d ",Flag); else printf("-1 "); } int main(){ freopen("changingsounds.in","r",stdin); freopen("changingsounds.out","w",stdout); Jimmy(); return 0; }
第二题：旅行(journey)
时间限制：1秒
内存限制：256MB
输入：journey.in
输出：journey.out
问题描述
给定一个n行m列的字符矩阵，’.’代表空地，’X’代表障碍。移动的规则是：每秒钟以上下左右四个方向之一移动一格，不能进入障碍。计算：在空地中随机选择起点和终点（可以重合，此时最短耗时为0），从起点移动到终点最短耗时的平均值。
每一行每一列至多有1个障碍，并且障碍不在对角线方向相邻。以下矩阵是不合法的：
.X
X.
输入
第一行两个整数n, m。。
接下来n行，每行m个字符’.’或’X’。在50%的数据中，保证每个字符都是’.’。
输出
平均耗时，保留4位小数，四舍五入。数据保证在范围之内输出一致，Ans是标准答案。
样例输入
2 2
..
.X
样例输出
0.8889
先解决前50%：所有两点间的曼哈顿距离和。
之间的曼哈顿距离等于。先计算前一部分（的和。枚举两行i,j。观察到：随便从这两行中各取一个点，这两点的x坐标之差相同。因此，这两行所有点对的就等于：{第i行空地的数量}*{第j行空地的数量}*|i-j|*2。
计算的方法完全相同，略过。两部分答案相加，最后除以空地总数的平方，就得到最终答案。
要解决后50%，关键是要观察到，从A走到B的耗时，要么等于AB的曼哈顿距离，要么等于AB的曼哈顿距离+2。也就是至多绕行一次。这是由题目中的条件“不会有两个X封锁住对角线”保证的。
那么，怎样的点对需要绕行呢，观察：
III….
IIX…
II..X.
IX….
I….X
X…..
S…..
S到所有的I需要绕行
根据以上规律，统计出需要+2的点对数加入答案即可AC本题。上图中红点到蓝点需要绕行。从直观上来看，一个X下方的点到这个X上方的点需要绕行。如果这个X右边一列（或者左边一列）包含X且本列X之上方，那么到这个X上方的点也需要绕行。横过来考虑是类似的。
然后注意如果是直接算分数，分子分母都直接开double吧，int再*1.0转换会苟。。。不知道为什么，或者把分子分母分开int最后除也是滋磁的，就是不要过程一直用分数算又int*1.0转换，容易苟
#include<iostream> #include<cstdlib> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; int a[1001][1001]; int sumi[1001],sumj[1001],n,m,h[1001],l[1001]; double num,tot,s; inline void Jimmy(){ memset(h,127,sizeof(h)); memset(l,127,sizeof(l)); scanf("%d%d ",&n,&m); char c; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ cin>>c; if(c=='.'){ sumi[i]++; sumj[j]++; tot++; } if(c=='X'){ h[i]=j; l[j]=i; } } for(int i=1;i<=n-1;i++) for(int j=i+1;j<=n;j++) num+=sumi[i]*sumi[j]*2*abs(i-j)/(tot*tot); for(int i=1;i<=m-1;i++) for(int j=i+1;j<=m;j++) num+=sumj[i]*sumj[j]*2*abs(i-j)/(tot*tot); for(int i=1;i<=m;i++){ if(l[i]!=2139062143){ s=l[i]-1; for(int j=i-1;j>=1;j--){ if(l[j]<l[j+1]) s+=l[j]-1; else break; } for(int j=i+1;j<=m;j++){ if(l[j]<l[j-1]) s+=l[j]-1; else break; } num+=s*(n-l[i])*4*1.0/(tot*tot); } } for(int i=1;i<=n;i++){ if(h[i]!=2139062143){ s=h[i]-1; for(int j=i-1;j>=1;j--){ if(h[j]<h[j+1]) s+=h[j]-1; else break; } for(int j=i+1;j<=n;j++){ if(h[j]<h[j-1]) s+=h[j]-1; else break; } num+=s*(m-h[i])*4*1.0/(tot*tot); } } printf("%.4lf",num); } int main(){ freopen("journey.in","r",stdin); freopen("journey.out","w",stdout); Jimmy(); return 0; }
第三题：舞蹈课(dancingLessons)
时间限制：1秒
内存限制：256MB
输入：dancingLessons.in
输出：dancingLessons.out
问题描述
有n个人参加一个舞蹈课。每个人的舞蹈技术由整数来决定。在舞蹈课的开始，他们从左到右站成一排。当这一排中至少有一对相邻的异性时，舞蹈技术相差最小的那一对会出列并开始跳舞。如果不止一对，那么最左边的那一对出列。一对异性出列之后，队伍中的空白按原顺序补上（即：若队伍为ABCD，那么BC出列之后队伍变为AD）。舞蹈技术相差最小即是的绝对值最小。
你的任务是，模拟以上过程，确定跳舞的配对及顺序。
输入
第一行为正整数：队伍中的人数。下一行包含n个字符B或者G，B代表男，G代表女。下一行为n个整数。所有信息按照从左到右的顺序给出。在50%的数据中，。
输出
第一行：出列的总对数k。接下来输出k行，每行是两个整数。按跳舞顺序输出，两个整数代表这一对舞伴的编号（按输入顺序从左往右1至n编号）。请先输出较小的整数，再输出较大的整数。
样例输入
4
BGBG
4 2 4 3
样例输出
2
3 4
1 2
样例输入
4
BGBB
1 1 2 3
样例输出
1
1 2
双向链表+堆。
堆中存储：相邻异性的编号及之差。按照之差为第一关键字，编号为第二关键字排序。
双向链表用来快速寻找i号左边的人和右边的人。
算法的流程：
- 将所有相邻的异性加入堆
- 当堆中还有元素时，取出并删除堆顶，否则结束
- 如果堆顶的两个人(a,b)有一个已经出列或者都出列了，跳到2
- 将a和b标记为已出列并加入答案，检查a左边和b右边的人是否为异性，如果是的就加入堆
- 将a和b从双向链表中删除，跳到2
不用双向链表像我一样标记一下访问过也是可以的。。。堆的关键字运用题（终于填上系统堆的坑了，存一下 http://blog.csdn.net/xiaoquantouer/article/details/52015928）
字符串如果是从0开始的话中间记得l,r时分清楚。。。不要忘记这俩东西起始点不一样了
#include<iostream> #include<cstdlib> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> using namespace std; int n,a[200001],v[200001],num; char s[200001]; struct nee{ int x,y,w; }e[200001]; bool operator >(nee k,nee kk){ if(k.w==kk.w) return k.x>kk.x; return k.w>kk.w; } priority_queue<nee,vector<nee>,greater<nee> > q; inline void push_(int x,int y){ nee now; now.x=x; now.y=y; now.w=abs(a[x]-a[y]); q.push(now); } inline void Jimmy(){ scanf("%d %s",&n,s); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n-1;i++) if(s[i-1]!=s[i]) push_(i,i+1); while(!q.empty()){ nee now=q.top(); q.pop(); if(v[now.x]||v[now.y]) continue; v[now.x]=1;v[now.y]=1; e[++num]=now; int l=now.x-1,r=now.y+1; if(l<1 || r>n) continue; while(l>1 && v[l]) l--; while(r<n && v[r]) r++; if(v[l] || v[r]) continue; if(s[l-1]!=s[r-1]) push_(l,r); } printf("%d ",num); for(int i=1;i<=num;i++) printf("%d %d ",e[i].x,e[i].y); } int main(){ freopen("dancingLessons.in","r",stdin); freopen("dancingLessons.out","w",stdout); Jimmy(); return 0; }