练习地址
点此前往练习
小美的书架
小美的书架上有很多书。小美是个爱读书的新时代好青年。
小团虽然也喜欢看书，但小团大多数时候都更喜欢来小美家蹭书读。
这就导致小美的书架上很多书都会被小团借走。
小美很烦这一点，就想出了一个招数，小美的书架是一行一行的，他会对一些行加锁，这样小团就借不走了。
现在小团想要借书，请你帮忙看看小团能不能借到书，如果可以借到的话在哪一行书架上有这本书。
为了简单起见，每本书将用一个正整数进行编号，小美的书架一共有N行。
输入描述:
第一行两个正整数N，M，Q，表示小美书架有N行编号1到N，书本编号从1到M，接下来有Q个操作接下来Q行，每行是下列操作中的一种：
1 x y : x是书本的编号，y是书架的行编号，代表小美将编号为x的书本放置到y行上。若该书本在小团手上则放置无效，若原来该书在书架上且原行上锁则放置无效，若该书被放置到一个锁了的行上则放置无效。
2 y : y是书架的行编号，代表小美将行编号为y的书架加锁，对已经上锁的书架行该操作无效。
3 y : y是书架的行编号，代表小美将行编号为y的书架锁去掉，对无锁的书架行该操作无效。
4 x : x是书本的编号，代表小团想借编号为x的书本，对该操作若可以借到输出一行正整数在哪一行，借不到输出一行-1
5 x : x是书本的编号，代表小团还回来编号为x的书本。若该书本不在小团手上该操作无效。
输出描述:
对于每个操作4，若可以借到输出一行正整数在哪一行，借不到输出一行-1
输入例子1:
5 5 10
1 1 4
1 2 3
1 3 1
2 1
4 1
5 2
4 3
4 5
3 1
4 2
输出例子1:
4
-1
-1
3
思路：
参考评论区中被玩坏的小人偶的思路：
分别构建一个书架结构体和书的结构体，其中书架中的有个lock变量用于检测对应行的书是否被上锁，每一行的书存入一个集合中，方便管理；书中有一个书籍编号以及书存放的行数。
接下来根据题目要求模拟对应操作即可。需要注意的是对应不同的操作数，输入是不同的。
代码：
#include<bits/stdc++.h>
using namespace std;
struct Shelf
{
bool lock;
set<int> book;
}shelf[10000];
struct Book
{
int num;
int line;
}book[10000];
int main()
{
int n,m,q;
cin>>n>>m>>q;
int op,x,y;
for(int i=0;i<q;i++)
{
cin>>op;
if(op==1)
{
cin>>x>>y;
if(book[x].num||shelf[book[x].line].lock||shelf[y].lock)
continue;
shelf[y].book.insert(x);
book[x].line=y;
}
else if(op==2)
{
cin>>y;
shelf[y].lock=1;
}
else if(op==3)
{
cin>>y;
shelf[y].lock=0;
}
else if(op==4)
{
cin>>x;
if(book[x].num||shelf[book[x].line].lock||book[x].line==0)
cout<<-1<<endl;
else
{
cout<<book[x].line<<endl;
book[x].num=1;
book[x].line=0;
shelf[book[x].line].book.erase(x);
}
}
else
{
cin>>x;
if(book[x].num==0)
continue;
book[x].num=0;
book[x].line=0;
}
}
return 0;
}
偏爱字母
小美喜欢字母E，讨厌字母F。在小美生日时，小团送了小美一个仅包含字母E和F的字符串，小美想从中选出一个包含字母E数量与字母F数量之差最大的子串。
*子串：从字符串前面连续删去若干个字符，从后面连续删去若干个字符剩下的字符串（也可以一个都不删），例如abcab是fabcab的子串，而不是abcad的子串。我们将空串看作所有字符串的子串。
输入描述:
第一行一个正整数n表示字符串的长度。第二行长度为n，且仅包含大写字母’E’,’F’的字符串（不含引号）
输出描述:
输出一个整数，表示最大的差值
输入例子1:
5
EFEEF
输出例子1:
2
例子说明1:
选择子串EE,此时有2个E，0个F,有最大差值2-0=2另外，选择子串EFEE也可以达到最大差值。
思路：
参考评论区中零葬的思路：
把E看成1，F看成-1。对数组遍历，当所有的E都被F平衡完了，就从0开始重新计算，即从当前位置重新开启一段子数组计算E和F的个数差值。
代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
string s;
cin>>s;
int sum=0,max=0;
for(int i=0;i<n;i++)
{
char tmp=s[i];
s[i]=(tmp=='E'?1:-1);
}
for(int i=0;i<n;i++)
{
sum+=s[i];
if(sum<0)
sum=0;
max=max>sum?max:sum;
}
cout<<max;
return 0;
}
搭配出售
服装店新进了a条领带，b条裤子，c个帽子，d件衬衫，现在要把这些搭配起来售卖。有三种搭配方式，一条领带和一件衬衫，一条裤子和一件衬衫，一个帽子和一件衬衫。卖出一套领带加衬衫可以得到e元，卖出一套裤子加衬衫可以得到f元，卖出一套帽子加衬衫可以得到g元。现在你需要输出最大的获利方式
输入描述:
一行7个整数分别表示a,b,c,d,e,f,g。
输出描述:
最大获利。
输入例子1:
2 3 4 5 6 7 8
输出例子1:
39
例子说明1:
4个帽子加4件衬衫获利32元，1条裤子加1件衬衫获利7元，一共得到39元。
思路：
使用贪心策略，首先对三个套餐价格进行升序排序，由于每个套餐中都有衬衫，因此组合套餐时只需要组合除衬衫以外的搭配和套餐价格即可。接着根据价格由高至低组合以得到最大的收益。需要注意每次搭配完需要减少相应组合中的搭配以及衬衫的数量。
代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a,b,c,d,e,f,g;
cin>>a>>b>>c>>d>>e>>f>>g;
vector<int> price={e,f,g};
sort(price.begin(),price.end(),less<int>());
unordered_map<int,int> map={{e,a},{f,b},{g,c}};
long long profit=0;
int min=price[0];
int mid=price[1];
int max=price[2];
while(d&&map[max])
{
profit+=max;
map[max]--;
d--;
}
while(d&&map[mid])
{
profit+=mid;
map[mid]--;
d--;
}
while(d&&map[min])
{
profit+=min;
map[min]--;
d--;
}
cout<<profit;
return 0;
}
十字路口
在小美和小团生活的城市中，有n行m列共计n*m个十字路口，第i行j列的十字路口有两个属性aij，b-ij。当行人处在i行j列的路口，对于任意非负整数k:
当时间处在[k * aij+k * b-ij), (k+1) * aij+k * bij)时，行人可以选择走到i±1行j列的路口。
当时间处在[(k+1) * aij+k * bij), (k+1) * aij+(k+1) * b-ij)时，行人可以选择走到i行j±1列的路口。
每次移动花费的时间为1，且要保证将要去的十字路口存在，即属于n*m个路口当中。可以选择原地静止不动。
在第0时刻，小美处在xs行ys列的十字路口处，要去xt行yt列的十字路口找小团。小团原地不动等小美，请问小美所花费的时间最少是多少?
输入描述:
第一行六个正整数n，m，xs，ys，xt，yt，含义如上文所示。以样例第一行【5、5、2、4、4、3】 共计6个数字为例，前两位数字代表有5 * 5的二维数组，三、四位数字代表小美处在2行4列的十字路口处，五、六位数字代表要去4行3列的十字路口找小团。
接下来n行每行m个正整数，在样例中为第一个5 * 5的二维数组，第i行第j个数代表i行j列十字路口的属性aij。
接下来n行每行m个正整数，在样例中为第二个5 * 5的二维数组，第i行第j个数代表i行j列十字路口的属性bij。对于100%的数据，1≤n，m，xs，ys，xt，yt，aij，bij≤100。
输出描述:
输出1行1个整数代表答案。
输入例子1:
5 5 2 4 4 3
2 1 1 3 1
1 4 2 3 1
4 4 4 2 1
3 1 1 2 4
5 1 5 5 1
5 3 4 1 3
1 1 2 2 2
2 1 4 4 5
1 1 5 3 3
3 2 1 3 3
输出例子1:
3
思路：
参考评论区中零葬的思路：
使用BFS进行求解，每个时刻都对可能移动的方向进行尝试，将下一个时刻可能到达的位置放入到一个队列中。但是在移动的过程中需要注意：由于移动受到所处时间段的限制，有可能为了花费更少的时间，本时刻决定不移动，等到下一时刻往更高效的方向进行移动。在这种情况下，下一个时刻仍然在现在的位置。而时间对于移动操作的约束，可以表达如下：
(1) 对于区间[k*aij+k*b-ij), (k+1)*aij+k*bij)，左端点是aij+bij的整数倍，右端点是一个开区间，比左端点多了不到aij，因此当时刻除以aij+bij的余数小于aij时，所处的时刻应该满足这个约束。
(2) 对于区间[(k+1)*aij+k*bij), (k+1)*aij+(k+1)*bij)，紧邻(1)中区间的右侧，所以aij<=余数<aij+bij时就是这种情况。
使用一个结构体node存储x和y。
cost作为当前已经花费的时间，每一次bfs的循环处理当前cost可能能走的几个位置。
当前cost是x加还是y加由题目判断，即reminder=cost%(a[x][y]+b[x][y])。
如果加完以后的x和y是没有访问过的，那么入队作为下一秒的情况。
那么当某一次now.x == xt&&now.y == yt时，cost就可以返回了。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,xs,ys,xt,yt;
int a[101][101];
int b[101][101];
bool visited[101][101];
vector<int> direction={0,-1,1};
struct node
{
int x,y;
node(){}
node(int a,int b):x(a),y(b){}
};
int bfs()
{
queue<node> q;
q.push(node(xs,ys));
int cost=0;
while(!q.empty())
{
int len=q.size();
for(int i=0;i<len;i++)
{
node now=q.front();
if(now.x==xt&&now.y==yt)
return cost;
q.pop();
visited[now.x][now.y]=1;
for(int j=0;j<direction.size();j++)
{
int x=now.x,y=now.y;
if(x<1||x>n||y<1||y>m)
continue;
int remainder=cost%(a[x][y]+b[x][y]);
if(remainder<a[x][y])
x+=direction[j];
else
y+=direction[j];
if(j==0||!visited[x][y])
{
q.push(node(x,y));
visited[x][y]=1;
}
}
}
cost++;
}
return cost;
}
int main()
{
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(visited, 0, sizeof(visited));
int cost=0;
cin>>n>>m>>xs>>ys>>xt>>yt;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cin>>a[i][j];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cin>>b[i][j];
}
cost=bfs();
cout<<cost;
return 0;
}
|