DQS 捡石子
今年开始上学的 DQS 非常喜欢石子， 她总是会收集很多不同类型
的石子来卖钱， 这个世界的石子只有两种——蓝色和白色（用
01 表示） 并且都是连在一起的， 不能移动， 因此 DQS 只好使用
她的神力来解除石子不能移动的封印， 但是由于某些原因 DQS 希
望让自己消耗更多的神力， 因此她许愿黑暗之神让她可以转换连
在一起的石子中的一颗。 消耗的神力计算方法为这一串石子中相
邻相同的石子个数的平方和。 DQS 想知道， 如何改变其中一个石
子的种类， 使得整个石子串的消耗最大（含多组数据）
输入描述 一个数 T
接下来 T 行， 每行一个长度为 N 的 01 串
输出描述 一个数 p 表示 DQS 消耗的神力
样例输入 2
000011
0101
样例输出 26
10
数据范围及提示 1<=T<=50
60%:1<=N<=1000
100%:1<=N<=100000
思路：贪心，先把每个连续子段分别预处理出来，每次遇到不同的就更新最大值。
直接上代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
char s[100000+10];
struct cc{
char zl;
int num;
}sum[100000+10];
int main()
{
int T;
scanf("%d",&T);
while(T)
{
T--;
memset(sum,0,sizeof(sum));
memset(s,0,sizeof(s));
scanf("%s",&s);
int l=strlen(s);
for(int i=l;i>=1;i--)
{
s[i]=s[i-1];
}
for(int i=1;i<=l;i++)
{
sum[i].zl=s[i];
if(s[i]==s[i-1])
{
sum[i].num=sum[i-1].num+1;
}
else
{
sum[i].num=1;
}
}
for(int i=l;i>=1;i--)
{
if(sum[i-1].zl==sum[i].zl)
{
sum[i-1].num=sum[i].num;
}
}
int ans=0;
int cnt=1;
for(int i=1;i<=l;i++)
{
if(s[i]==s[i+1])
{
cnt++;
}
else
{
ans+=cnt*cnt;
cnt=1;
}
}
int sum1=ans,sum2=ans,sum3=ans;
for(int i=1;i<=l;i++)
{
if(sum[i].zl!=sum[i+1].zl&&i+1<=l)//当前石子颜色和下一个石子颜色不同且不是最后一个石子
{
if(sum[i+1].zl==sum[i-1].zl&&i-1>=1)
{
sum1=max(sum1,ans-sum[i+1].num*sum[i+1].num-sum[i-1].num*sum[i-1].num-1+(sum[i+1].num+sum[i-1].num+1)*(sum[i+1].num+sum[i-1].num+1)); //夹在中间一个石子的情况
}
sum2=max(sum2,ans-sum[i].num*sum[i].num-sum[i+1].num*sum[i+1].num+(sum[i].num-1)*(sum[i].num-1)+(sum[i+1].num+1)*(sum[i+1].num+1));//将当前石子变为下一个石子的颜色
sum3=max(sum3,ans-sum[i+1].num*sum[i+1].num-sum[i].num*sum[i].num+(sum[i].num+1)*(sum[i].num+1)+(sum[i+1].num-1)*(sum[i+1].num-1)); //将下一个石子变为当前石子颜色
}
}
ans=max(ans,sum1);
ans=max(ans,sum2);
ans=max(ans,sum3);
printf("%d\n",ans);
}
return 0;
}低买高卖
给你N天股票的行情，你可以每天选择买进一份股票或者卖出一份股票，或者什么都不做，要求最后一天股票数为0。起始时股票数为0，问最大收益是多少。
思路：贪心思想，开一个小根堆，每次将当天股票价格与堆顶元素比较，如果比堆顶元素大，将堆顶元素去掉，加入当前元素。相当于买进堆顶元素，卖出当前元素，赚的钱为当前元素减去堆顶元素，这样n次后，得到的答案为最优解，且不用考虑是否最后一天持有股票数为0。因为就算之前买错了，也可以由后面的更优解来更新。
举个例子：
3
3 5 10
第一次我们将3放入堆中，第二次放入5发现比3大，答案+2，拿走3，放进5，再放进10发现10比5大，则答案——5，拿走5。
题解：
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
priority_queue<long long>q;
int main()
{
int n;
scanf("%d",&n);
long long ans=0;
for(int i=1;i<=n;i++)
{
long long x;
scanf("%lld",&x);
if(!q.empty()&&(-q.top()<x))
{
ans+=x+q.top();
q.pop();
q.push(-x);
}
q.push(-x);//就算满足更新答案的条件也要再放进堆一次，相当于存在买进和卖出两种状态。
}
printf("%lld",ans);
return 0;
}星际牛仔
“就像做梦一样呢…”
“嗯.一场噩梦罢了。 ”
题目描述
当 Spike 只身杀入红龙总部，寻找着宿敌 Vicious 时，遇到了过去组织中好友
林的弟弟真。
真告诉 Spike 了 Vicious 的地点，在总部大厦的最顶层。 想要到达那里则必须
经过面前的迷宫防御系统——迷宫如真手中的地图所示：
在一张 N×M 格的矩形迷宫中， Spike 开始时从左上角的格子进入迷宫，出口则
位于右下角的格子。当处于迷宫中时， 可以选择上， 下，左， 右四个方向移动
到相邻的格子中。
可是等等！迷宫中的每一个格子都有一种颜色， 每种颜色代表不同的属性！
• 如果格子是红色的， 说明有红龙*镇守， 是无法通行的。
• 如果格子是粉红色的，则可以正常行走。
• 如果格子是橙色的， 为红龙*确认没有入侵者的区域。 可以正常行走，且
经过者会被染上安全标记。
• 如果格子是蓝色的， 为特殊通行区域，仅允许染有安全标记的人通过。
• 如果格子是紫色的， 为快速通行区域， Spike 将沿该方向滑动到下一个格子
（除非他无法穿过）。如果这个格子也是一个紫色的格子，那么将继续滑动，
直到他落在一个非紫色的格子上，或者击中一个无法通行的格子。 同时，若
经过紫色的格子，则会清除身上的安全标记。
（如果你对紫色格子感到困惑，下面的样例将说明它们的用途。）
请帮助 Spike 经尽可能少的移动步数从左上角到达右下角。
输入格式
输入文件 cowboy.in
第一行有两个整数 N 和 M， 表示迷宫的行数（rows） 和列数（columns）。
接下来的 N 行每行各有 M 个整数， 代表迷宫。
• “0”代表是一个红色的格子
• “1”代表是一个粉红色的格子
• “2”代表是一个橙色的格子
• “3”代表是一个蓝色的格子
• “4”代表是一个紫色的格子
左上角和右下角的整数将始终为“1”。
输出格式
输出文件 cowboy.out
一个整数，代表 Spike 必须用来穿过迷宫的最小移动步数，如果不可能穿过，
则输出“-1” 。
样例输入4 4
1 0 2 1
1 1 4 1
1 0 4 0
1 3 1 1
样例输出
10
样例说明
在这个例子中， Spike 向下走一个格子，向右走两个格子（然后向右滑动一个
格子）。他向上走一个格子，向左走一格，向下走一格（再往下滑两个方块），
再向左走一格。这共有 10 个动作（DRRRULDDDR）。
数据范围及提示
对于 100%的数据： 1<=n,m<=1000
思路：bfs+判重，对于每一个需要入队的元素我们判断是否该点已经被相同方向、相同标记标记过。此外对于紫色格子，要一直滑到不能再滑，无解输出-1。
题解：
#include<cstdio>
#include<queue>
#include<iostream>
using namespace std;
int n,m;
struct cc{
int x,y,step,color,fx;
};
queue<cc>q;
int map[1005][1005];
int dx[5]={0,-1,1,0,0};
int dy[5]={0,0,0,-1,1};
bool vis[1005][1005][5][2];//x坐标，y坐标，方向，标记。
int ans=-1;
void bfs(int s1,int s2)
{
q.push((cc){s1,s2,0,0,0});
while(!q.empty())
{
cc u=q.front(); q.pop();
if(u.x==n&&u.y==m)
{
ans=u.step;
return;
break;
}
if(map[u.x][u.y]==4)
{
int mx=u.x+dx[u.fx],my=u.y+dy[u.fx];
if(mx>=1&&mx<=n&&my>=1&&my<=m&&map[mx][my]!=0&&map[mx][my]!=3)
{
if(map[mx][my]==2&&!vis[mx][my][u.fx][1])
{
q.push((cc){mx,my,u.step+1,1,u.fx});
vis[mx][my][u.fx][1]=1;
}
else if(!vis[mx][my][u.fx][u.color])
{
q.push((cc){mx,my,u.step+1,u.color,u.fx});
vis[mx][my][u.fx][u.color]=1;
}
continue;
}
}
for(int i=1;i<=4;i++)
{
int mx=dx[i]+u.x,my=dy[i]+u.y;
if(mx>=1&&mx<=n&&my>=1&&my<=m&&map[mx][my]!=0)
{
if(map[mx][my]==1&&!vis[mx][my][i][u.color])
{
q.push((cc){mx,my,u.step+1,u.color,i});
vis[mx][my][i][u.color]=1;
}
if(map[mx][my]==2&&!vis[mx][my][i][1])
{
q.push((cc){mx,my,u.step+1,1,i});
vis[mx][my][i][1]=1;
}
if(map[mx][my]==3&&u.color==1&&!vis[mx][my][i][1])
{
q.push((cc){mx,my,u.step+1,1,i});
vis[mx][my][i][1]=1;
}
if(map[mx][my]==4&&!vis[mx][my][i][0])
{
q.push((cc){mx,my,u.step+1,0,i});
vis[mx][my][i][0]=1;
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&map[i][j]);
}
}
bfs(1,1);
printf("%d",ans);
return 0;
}