T68402 扫雷
题目链接：传送门
题目描述
扫雷，是一款单人的计算机游戏。游戏目标是找出所有没有地雷的方格，完成游戏；要是按了有地雷的方格，游戏失败。现在 Bob 正在玩扫雷游戏，你作为裁判要判断他是否游戏失败。
具体来说，Bob 正在玩的扫雷游戏有 n×m 个格子，拥有上帝视角的你知道所有的雷埋在哪些方格。Bob 告诉你他会按哪些格子。如果他按的某个格子有地雷，那么他游戏失败，你需要输出是哪一步导致他游戏失败的；如果他按的所有格子都没有地雷，那么他游戏未失败，你只需输出“Good Game.”。
输入输出格式
输入格式：
第一行两个整数 n,m，意义如上所述。
接下来 n 行，每行 m 个整数，表示格子的情况。对于一个位置，如果是 0 表示这个位置没有地雷，如果是 1 表示有地雷。
接下来一行一个整数 k，表示 Bob 的操作次数。
接下来 kk 行，其中的第 i 行有两个整数 xi,yi(1≤xi≤n,1≤yi≤m)，表示 Bob 的第 i 步按的位置。我们规定左上角的格子为 (1,1)，右下角的格子为 (n,m)。
你可以通过样例进一步理解输入格式。
输出格式：
如果游戏失败，输出是哪一步导致游戏失败。如果没有失败，输出“Good Game.”
输入输出样例
输入样例#1：
3 4
0000
0000
0000
1
1 1
输出样例#1：
Good Game.
输入样例#2：
3 4
1000
0000
0000
1
1 1
输出样例#2：
1
输入样例#3：
3 4
1000
0000
0000
2
2 2
1 1
输出样例#3：
2
【题解】： 简单模拟即可，注意的是输入按照字符串输入。
【代码】：
#include<bits/stdc++.h>
using namespace std;
const int N = ;
int n,m,k;
char a[N][N];
int x[N],y[N],F=;
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%s",a[i]+);
}
scanf("%d",&k);
for(int i=;i<=k;i++){
scanf("%d%d",&x[i],&y[i]);
}
for(int i=;i<=k;i++){
if(a[x[i]][y[i]]==''){
F = ;
printf("%d\n",i);
return ;
}
}
if(F){
puts("Good Game.");
}
return ;
}
扫雷
T68401 烤串
题目链接：传送门
题目描述
经历了艰辛的扫雷之后，Bob 感到体力不支。他来到了一个烤串店，发现烤串店正在大促销。促销策略如下：
1、1 根烤串不卖。
2、2 根烤串卖 5 块钱。
3、7 根烤串卖 10 块钱。
4、12 根烤串卖 17 块钱。
现在 Bob 有 nn 块钱，他想知道他最多可以买多少串烤串。
输入输出格式
输入格式：
第一行一个整数 T，表示数据组数。
接下来 T 行，每行一个整数 n，意义如上所述。
输出格式：
输出 T 行，第 i 行表示第 i 组数据的答案。
输入输出样例
输入样例#1：
1
34
输出样例#1：
24
输入样例#2：
2
34
15
输出样例#2：
24
9
说明
对于50% 的数据，满足1≤n≤100。
对于100% 的数据，满足 1≤n≤10^9,1≤T≤200。
【题解】：
经典的题目，就是大范围贪心，小范围暴力枚举，或者用完全背包处理。
同时注意边界，之前因为边界问题错了好几回主要是，边界一定要是所有价钱的公倍数，不然会出错。
【代码】：
#include<bits/stdc++.h>
using namespace std;
const int N = 4e6+;
typedef long long ll;
int Val[] = { , , , };
int Cost[] = { , , , };
ll dp[N];
void Init(){
memset(dp,-0x7f,sizeof dp );
dp[] = dp[] = ;
for(int i=;i<;i++){
for(int j=Cost[i];j<=N-;j++){
dp[j] = max( dp[j] , dp[j-Cost[i]] + Val[i] );
}
}
}
ll solve( ll n ){
if( n < N ) {
return dp[n];
}
ll cnt = ( (n-+)/ ) ; return dp[n - cnt* ] + cnt * ;
}
int main()
{
Init();
ll n;
int T;
scanf("%d",&T);
while(T--){
scanf("%lld",&n);
ll ans = solve(n);
printf("%lld\n",ans);
}
return ;
}
烤串
T68263 排序
题目链接：传送门
题目描述
Bob 吃完烤串之后又充满了精力，现在 Alice 给了他一个难题：
有一个长度为 n 的序列 a1,a2,⋯,an，保证 ai≥ai−1(2≤i≤n)。但是 Alice 修改了其中某 kk 个位置的值，得到新序列 b1,b2,⋯,bn。Bob 拿到序列 b 之后，希望可以改不超过 k 个位置的值，使得 b 序列也满足bi≥bi−1(2≤i≤n)。
这个问题对他来说太难了，他想寻求你的帮助。你需要告诉他如何修改使得满足要求。
输入输出格式
输入格式：
第一行两个整数n,k，意义如上所述。
接下来一行 n 个整数，第 ii 个整数表示 bi。
输出格式：
第一行一个整数 t，表示你要修改的次数。需要满足 t≤k。
接下来 t 行，第 i 行两个整数 pi,vi，表示将 bpi 修改为 vi。需要满足 1≤pi≤n,0≤vi≤10^9。
如果有多组解符合要求，输出任意一组即可。你不必最小化 t，只要满足 t≤k 即可。
输入输出样例
输入样例#1：
5 1
1 2 7 4 5
输出样例#1：
1
3 3
输入样例#2：
5 2
1 2 3 4 5
输出样例#2：
0
说明
对于 50% 的数据，满足 1≤n≤100。
对于 100% 的数据，满足 1≤n≤5000,0≤k≤n,0≤bi≤10^9。
【题解】：
这个题目也比较经典，涉及的知识点是：最长上升子序列，以及dp记录路径问题。
真的非常精妙的题目，以前做过类似的，但是没有记录路径
1、首先求出LIS的长度为多少。
2、然后求出LIS哪一个为终点，在过程中注意要记录路径。
3、以终点往前跑，把对应的位置改为前一个子序列中元素的值即可。
例如：
序列为：1 、 2 、 7 、 4 、5
1、找出LIS，最长为4.
2、以5为终点时达到最大值。
3、然后进行标记。
1 、 2 、 7 、 4 、5 4、最后把对应的位置改成前一个位置的值。
1 、 2 、 2 、 4 、5
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+;
int a[N],vis[N],dp[N],from[N];
int n,k;
int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
}
int First , cnt ,tot;
for(int i=;i<=n;i++){
dp[i] = ;
from[i] = ;
for(int j=;j<i;j++)if( a[j] <= a[i] ){
if( dp[j] + > dp[i] ){
dp[i] = dp[j] + ;
from[i] = j ;
}
}
}
int Max_dp = , Max_dp_pos = - ;
for(int i=;i<=n;i++){
if( dp[i] > Max_dp){
Max_dp = dp[i];
Max_dp_pos = i;
}
}
//printf("%d %d\n",Max_dp,Max_dp_pos);
for(int i = Max_dp_pos; i ; i = from[i] ){
//printf("%d %d\n",i,from[i]);
vis[i] = ;
}
printf("%d\n",n-Max_dp);
int pre = ;
for(int i=;i<=n;i++){
if( vis[i] == ){
printf("%d %d\n",i,pre);
}else{
pre = a[i] ;
}
}
return ;
}
排序
T79670 麻将
题目链接：传送门
题目描述
高呼三声 csfnb 后，Alice 和 Bob 开始打牌。
和一般的牌不同，他们打的牌上面有两个点数，分别设为 a,b。如果 Alice 获得这张牌，她会获得 a 分数；如果 Bob 获得这张牌，他会获得 b 分数。
游戏开始后，Alice 和 Bob 轮流从牌堆里拿牌，Alice 先手，直到牌堆的牌被拿完时游戏结束。Alice 的策略很简单，她每次选牌堆里 a 最大的那张牌据为己有，如果同时有多张牌有同样的 a，那么她会取 b 最大的那一张。现在 Bob 想知道他如何选可以获得最大的分数。
输入输出格式
输入格式：
第一行一个整数 n，意义如上所述。
接下来 n 行，第 i 行两个整数 ai,bi，表示第 i 张牌的点数。
输出格式：
一行一个整数，表示 Bob 按最优策略取的话，可以获得的最大分数。
输入输出样例
输入样例#1：
1
1 23333
输出样例#1：
0
输入样例#2：
2
1 23333
2 1
输出样例#2：
23333 【题解】：这个题目非常精妙，我觉得真的不错。
首先我们已经可以预知的Alice怎么选择，我们只需要在Alice选择前 ，对于Bob进行预测最优值即可。
这个题目涉及的知识点为：贪心，排序，堆优化。 首先我们已经预测到Alice怎么选择，我们直接可以用Alice的想法进行排序。
这里用到库函数Sort()进行排序即可。 然后第二步就是分析Bob的想法，
1、Alice先手，Bob选择只有比Alice少，不会比Alice多选牌。
2、然后对于Bob来说，对于排序后，偶数张牌是他必选的，奇数时是贪心决策的。
这个就是把大问题变成小问题处理，选第i张牌时，确保第i-1张牌为最优往后延伸。 举例子：
排序后的结果
A： 10 9 8 8
B： 5 3 7 2
首先第一张牌肯定是给了Alice
选择第2张牌时，Bob肯定只能选第二张牌，得到的价值为3.
选择第3张牌时，Bob看到第3张牌了。
当前他是可以优先选择第3张牌，同时把第2张牌放回去（因为前3张牌只能选1张，Alice先手），得到的价值为 7
选择第4张牌时，只能选择第4张牌，因为Alice 先手，已经拿去第1,2张牌了。
所以最优策略下，Bob的答案就是9. 在选择时为了能找出最小值，然后重新放入的动作，用了Priority_queue优先队列（堆）来优化。 附上代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+;
typedef long long ll;
typedef pair<ll,ll> PII;
priority_queue < ll , vector<ll>,greater<ll> > Q;
PII C[N];
int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%lld%lld",&C[i].first,&C[i].second);
} sort( C+ , C++n , greater<PII>() ); long long ans = ,t;
if( n>= )
Q.push(C[].second),ans=C[].second;
for(int i=;i<=n;i++){
if( i& ){
t = Q.top();
if( !Q.empty() && t < C[i].second ){
ans = ans - Q.top() + C[i].second;
Q.pop();
Q.push(C[i].second);
}
}else{
ans += C[i].second;
Q.push(C[i].second);
}
}
return *printf("%lld\n",ans);
}
麻将
