文章目录
- 前言
- 一、哟,在玩石头剪刀布呢
- 二、哟,是回文串串文回是
- 三、哟, 我也想参加蓝桥杯
- 四、哟,这就是压轴题了嘛
- 总结
前言
迟来的新风杯补题！大佬出的题很棒哦！
一、哟,在玩石头剪刀布呢
Description
众所周知，石头剪刀布是一款风靡全球的实时竞技类游戏。Herod学长正在观战S249世界总决赛，谁知观战系统出现了bug，现在只知道对战双方(称为红方和蓝方)分别出了多少次石头，多少次剪刀，多少次布。在这紧要关头，Herod学长想请你帮忙编写一个程序，计算红方选手最多能赢多少局，以及最少要输多少局
Input
输入共有3行
第一行1个整数n表示总共对战了多少局
第二行3个整数表示红方出的石头，剪刀，布的次数
第三行3个整数表示蓝方出的石头，剪刀，布的次数
1≤n≤1000
Output
输出一行，包含两个整数，分别表示红方最多能赢的局数和最少要输的局数
Sample Input 1
4
1 2 1
2 1 1
Sample Output 1
3 0Hint
样例解释：
赢3局策略：石头VS剪刀，剪刀VS布，剪刀VS石头，布VS石头
输0局策略：石头VS石头，布VS石头，剪刀VS剪刀，剪刀VS布
Source
Herod
简单贪心。获胜的次数很好求。取 min 就行。至于要输的次数。如果对方出石头，我方肯定出石头和布先，石头和布出完了才出剪刀。这时候就可以算出对方出石头我方要输的次数。三种情况的次数加起来就行。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string.h>
#include<cstdio>
#include<queue>
#include<cmath>
using namespace std;int main()
{int n;cin>>n;int x1,x2,x3,y1,y2,y3;//石头，剪刀，布cin>>x1>>x2>>x3>>y1>>y2>>y3;int win,lose;win=min(x1,y2)+min(x2,y3)+min(x3,y1);lose=max(y1-(x1+x3),0)+max(y2-(x1+x2),0)+max(y3-(x2+x3),0);cout<<win<<" "<<lose<<endl;
}
二、哟,是回文串串文回是
Description
众所周知，形如：abba,aba这样的就是回文串。也就是从左往右看和从右往左看是一样的，就是回文串。现在有一个仅由小写字母组成的字符串，想请你找出字符串中最长的回文串长度是多少。
Input
输入一个字符串s
保证字符串长度小于等于1000
Output
输出一行，包含一个整数，表示最长的回文串长度
Sample Input 1
abbdcdcdacSample Output 1
5Hint
样例解释：最长回文串：dcdcd
Source
Herod
这个思维！！！枚举一个对称中心，然后往两边扫描，直到两边端点的字符不相等。计算每次枚举的长度取max。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string.h>
#include<cstdio>
#include<queue>
#include<cmath>
using namespace std;
const int MAX=1e4;
char s[MAX];
int ans=0;void check(int l,int r)
{int res=0;while(l>=0&&r<strlen(s)){if(s[l]==s[r])res+=2;else return ;if(l==r)res--;ans=max(res,ans);l--;r++;}}
int main()
{gets(s);for(int i=1;i<strlen(s);i++)//也可用len=strlen(s)来简化{check(i,i);check(i,i+1);//两种可能均有考虑}cout<<ans<<endl;
}
三、哟, 我也想参加蓝桥杯
蛇形矩阵
Description
众所周知，蓝桥杯大赛每年举办一次。作为一名计信学子，很大部分人都会选择在大二大三参加蓝桥杯大赛。为了让大一的你们之后也能踊跃参加，于是想让你们提前感受一下蓝桥杯的省赛难度。如下图所示，小明用从1开始的正整数“蛇形”填充无限大的矩阵。
容易看出矩阵第二行第二列中的数是5。请你计算矩阵中第X行第Y列的数是多少？
Input
第一行1个整数t，表示有t组数据
接下来t行，每行两个整数，分别表示X，Y
1≤t≤100
1≤X，Y≤20
Output
输出t行，每行包含一个整数，表示矩阵中第X行第Y列 的数
Sample Input 1
2
2 1
3 3
Sample Output 1
3
13
Source
Herod
按照规律，把数组填满。然后直接O(1) 输出就好了。当然也可以推出一个数学公式 O(1) 计算答案。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string.h>
#include<cstdio>
#include<queue>
#include<cmath>
using namespace std;int main()
{int a[200][200]={0};int t,x,y;cin>>t;int i=0;//rowint j=0;//colonint cnt=1;int flag=1;//方向while(cnt<=40*40/2)//为什么是这个值，我想因该是因为x、y的范围再扩大一点的缘故{a[i][j]=cnt;i-=flag;j+=flag;if(flag==1&&i==-1){flag=-1;i=0;}else if(flag==-1&&j==-1){flag=1;j=0;}cnt++;}while(t--){cin>>x>>y;cout<<a[x-1][y-1]<<endl;}return 0;
}
四、哟,这就是压轴题了嘛
背包问题（dp）
dp还是不熟啊！！！
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string.h>
#include<cstdio>
#include<queue>
#include<cmath>
using namespace std;int a[500],b[500];
int n,ans=0;void solve(int i,int rem,int sum)//i为选取物品的个数，rem为剩余可用的钱，sum为总选物品的价值
{if(i==n){ans=max(ans,sum);return ;}if(rem>=a[i])solve(i+1,rem-a[i],sum+b[i]);solve(i+1,rem,sum);
}
int main()
{int m;cin>>n>>m;for(int i=0;i<n;i++)cin>>a[i];for(int i=0;i<n;i++)cin>>b[i];solve(0,m,0);cout<<ans<<endl;return 0;}
总结
以上题目是自己没能独立思考出，看了解析后才写出来的题目！
