Monday
蓝桥杯模拟赛 1
A题（补题）
这个要求构成带分数的数字不能重复，也就是全排列，并且这题时间限制为3s，可以枚举全部的全排列再枚举每个全排列的可能性，全排列可以使用深搜或者next_permutation的全排列函数
全排列函数
#include<bits/stdc++.h>
using namespace std;
int n,ans;
int num[9]{1,2,3,4,5,6,7,8,9};
int main() {
cin >> n;
do {
int a = 0;
for (int i = 0; i < 7; i++) {
a = a * 10 + num[i];
int b = 0;
for (int j = i + 1; j < 8; j++) {
b = b * 10 + num[j];
int c = 0;
for (int k = j + 1; k < 9; k++) {
c = c * 10 + num[k];
}
if (b % c == 0 && (a + b / c) == n)ans++;
}
}
} while (next_permutation(num, num + 9));
cout << ans;
return 0;
}
深度优先搜索求全排列
#include<bits/stdc++.h>
using namespace std;
int n,ans;
int num[100];
int vis[100];
void dfs(int u){
if(u>9){
int a=0;
for(int i=1;i<=7;i++){
a=a*10+num[i];
int b=0;
for(int j=i+1;j<=8;j++){
b=b*10+num[j];
int c=0;
for(int k=j+1;k<=9;k++){
c=c*10+num[k];
}
if(b%c==0&&(a+b/c)==n)ans++;
}
}
//for(int i=1;i<=9;i++)cout<<num[i];cout<<'\n';
}
for(int i=1;i<=9;i++){
if(!vis[i]){
num[u]=i;
vis[i]=1;
dfs(u+1);
vis[i]=0;
}
}
}
int main()
{
cin>>n;
dfs(1);
cout<<ans;
return 0;
}
B题（补题）
比赛时主要存在问题就是对数据的输入，因为题没有变量控制输入的结束，有两种输入方式：1.使用读到文件结尾的方式while(cin>>x)或while(scanf("%d",&x)!=EOF)。2.以一行一行输入每行用回车'\n'作为结束标记。然后就是用sort排序后，遍历一遍，当前后两个数的值差为0是重号的，差为2是断号的。
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int n,ans,res,t;
char c;
int a[10010];
int main() {
cin >> n;
while(cin>>a[t++]);
sort(a, a + t);
for (int i = 0; i < t; i++) {
if (a[i + 1] == a[i])ans = a[i];
if (a[i + 1] - a[i] == 2)res = a[i] + 1;
}
cout << res << ' ' << ans;
return 0;
}
C题
直接遍历一遍两个字符串，相同的地方就跳过，不相同就翻一次，翻一次就加一，最后就是变成相同字符串所需最少的次数
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int n,m;
string a,b;
int main() {
IOS;
cin>>a>>b;
for(int i=0;i<a.size();i++){
if(a[i]==b[i])continue;
else {
if(a[i]=='*')a[i]='o';
else a[i]='*';
if(a[i+1]=='*')a[i+1]='o';
else a[i+1]='*';
m++;
}
}
cout<<m<<'\n';
return 0;
}
D题（补题）
思路：我们可以发此进行操作以后就是交换了此项的前缀和和前一项的前缀和，并且要保证它单调的时候就是最优解
#include<bits/stdc++.h>
using namespace std;
#define N 300005
typedef long long ll;
ll s[N], res[N];
bool v[N];
int t, n;
int main() {
cin >> t;
while (t--) {
cin >> n;
memset(s, 0, sizeof(s));
memset(res, 0, sizeof(res));
memset(v, 0, sizeof(v));
for (int i = 1; i <= n; i++) {
cin >> s[i];
s[i] += s[i - 1];
}
ll s0 = s[0], s1 = s[n];
if (s0 > s1) swap(s0, s1);
sort(s, s + n + 1);
for (int i = 0; i <= n; i++)
if (s0 == s[i]) {
s0 = i;
break;
}
for (int i = 0; i <= n; i++)
if (s1 == s[i]) {
s1 = i;
break;
}
int l = 0, r = n;
for (int i = s0; i >= 0; i -= 2) {
res[l++] = s[i];
v[i] = 1;
}
for (int i = s1; i <= n; i += 2) {
res[r--] = s[i];
v[i] = 1;
}
for (int i = 0; i <= n; i++)
if (!v[i]) {
res[l++] = s[i];
v[i] = 1;
}
ll ans = 0;
for (int i = 1; i <= n; i++)
ans = max(ans, abs(res[i] - res[i - 1]));
cout << ans << '\n';
}
return 0;
}
F题（补题）
这题我比赛时想为将全部排序，求他们两个数之间差的最小值即可（蠢了蠢了），其实是不对的，例如一个差为2，一个差为3，1 3 6，但让他们出现再一个等差数列里则公差应该为6，所以这题应该是求两个数差的最大公约数，而求最大公约数可以直接使用c++库函数__gcd(int a,int b)，返回两个数的最大公约数，但速度较慢，也可以自己手写一个，gcd1 gcd2
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,ans;
int a[100010];
int main()
{
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
int gcd=a[1]-a[0];
if(gcd==0)cout<<n<<'\n';
else{
for(int i=2;i<n;i++){
gcd=__gcd(gcd,a[i]-a[i-1]);
}
cout<<(a[n-1]-a[0])/gcd+1<<'\n';
}
return 0;
}
G题
直接判断枚举每个数，判断每个数的各个数位上只要要有一个是2或0或1或9就加到sum总和里，枚举结束后输出sum即可
#include<bits/stdc++.h>
using namespace std;
int n,sum,t,k;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
k=i;
while (k > 0) {
t = k % 10;
if (t == 2 || t == 0 || t == 1 || t == 9) {
sum += i;
break;
}
k /= 10;
}
}
cout << sum << '\n';
return 0;
}
H题（补题）
二叉树是每个节点都有两个儿子，比赛时将题目意思理解错了，认为一个节点就是一个深度，导致题目做错。其实题目的意思是每层是一个深度，每个节点有一个值，每个深度的值就是每层所以节点的值之和，下标从1开始由图可以知道规律，第i层的节点数为2^(i-1)个，每层从下标为2^(i-1)开始，每次求完每层的值就更新一下最大值和层数，最后输出答案即可
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
int n,m,im,pos=1;
int a[100100];
int b[100100];
int main() {
IOS;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;;i++){
int k=pow(2,i-1);
if(k>n)break;
for(int j=k;j<2*k&&j<=n;j++){//j=k+k=k*2,j<n可能最后一层没有排满，所以只能加到题目所给的n
b[i]+=a[j];
}
if(im<b[i]){
im=b[i];
pos=i;
}
}
cout<<pos;
}
Tuesday
SMU Winter 2023 Round #1 (Div.2)
A题
比较两个数的大小即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ll n,m;
cin>>n>>m;
if(n>m)cout<<"NO";
if(m>n)cout<<"YES";
if(n==m)cout<<"equal probability";
return 0;
}
B题
很简单，计算各位数上的数字和的1，2，3次方
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ll n;
cin>>n;
ll a,b,c;
a=n/100;
b=n%100/10;
c=n%10;
int sum=a+b+c;
cout<<sum<<'\n'<<pow(sum,2)<<'\n'<<pow(sum,3)<<'\n';
return 0;
}
我觉得字符串更简单
#include<bits/stdc++.h>
using namespace std;
string s;
int main()
{
cin>>s;
int k=0;
for(int i=0;i<s.size();i++)k+=s[i]-'0';
cout<<k<<'\n'<<k*k<<'\n'<<k*k*k<<'\n';
}
C题 拱猪计分（补题）
这题目满足一看就不是什么好题,hhhh 思路：按照题目的意思模拟一下就好了，就是代码很长，各种情况都要考虑,且不支持动态输出，要把每四行的答案存下来最后在输出，还要带着符号输出。
#include<bits/stdc++.h>
using namespace std;
vector<string>s;
int cnt0,cnt,n;
int H[14]{0,-50,-2,-3,-4,-5,-6,-7,-8,-9,-10,-20,-30,-40};
struct S {
int a, b, c, d;
}score[10010];
int Fs() {
int cntH=0, cntS=0, cntD=0, cntC=0,cntSD=0,ans=0;
for (int i = 0; i < n; i++) {
if(s[i][0]=='H')cntH++;
if(s[i][0]=='S')cntS++;
if(s[i][0]=='D')cntD++;
if(s[i][0]=='C')cntC++;
}
if(cntH==13&&(cntS==0||cntD==0))ans+=200;
if(cntS&&cntD==0)ans-=100;
if(cntD&&cntS==0)ans+=100;
if(cntH<13){
for(int i=0;i<n;i++){
if(s[i][0]=='H'&&s[i][1]=='1'&&s[i].size()==2)ans+=H[1];
if(s[i][0]=='H'&&s[i][1]=='2'&&s[i].size()==2)ans+=H[2];
if(s[i][0]=='H'&&s[i][1]=='3'&&s[i].size()==2)ans+=H[3];
if(s[i][0]=='H'&&s[i][1]=='4'&&s[i].size()==2)ans+=H[4];
if(s[i][0]=='H'&&s[i][1]=='5'&&s[i].size()==2)ans+=H[5];
if(s[i][0]=='H'&&s[i][1]=='6'&&s[i].size()==2)ans+=H[6];
if(s[i][0]=='H'&&s[i][1]=='7'&&s[i].size()==2)ans+=H[7];
if(s[i][0]=='H'&&s[i][1]=='8'&&s[i].size()==2)ans+=H[8];
if(s[i][0]=='H'&&s[i][1]=='9'&&s[i].size()==2)ans+=H[9];
if(s[i][0]=='H'&&s[i][2]=='0'&&s[i].size()==3)ans+=H[10];
if(s[i][0]=='H'&&s[i][2]=='1'&&s[i].size()==3)ans+=H[11];
if(s[i][0]=='H'&&s[i][2]=='2'&&s[i].size()==3)ans+=H[12];
if(s[i][0]=='H'&&s[i][2]=='3'&&s[i].size()==3)ans+=H[13];
}
}
if(cntH==13&&cntS&&cntD)ans+=500;
if(s.size()==1&&cntC)ans+=50;
if(s.size()>1&&cntC)ans*=2;
return ans;
}
int main()
{
while(1) {
cnt++;cnt0=0;
for (int i = 0; i < 4; i++) {
s.clear();
cin >> n;
if (n == 0)cnt0++;
for (int j = 0; j < n; j++) {
string str;
cin >> str;
s.push_back(str);
}
if (i == 0)score[cnt].a = Fs();
if (i == 1)score[cnt].b = Fs();
if (i == 2)score[cnt].c = Fs();
if (i == 3)score[cnt].d = Fs();
}
if (cnt0 == 4)break;
}
for(int i=1;i<cnt;i++){
if(score[i].a>0)cout<<'+'<<score[i].a<<' ';
if(score[i].a<=0)cout<<score[i].a<<' ';
if(score[i].b>0)cout<<'+'<<score[i].b<<' ';
if(score[i].b<=0)cout<<score[i].b<<' ';
if(score[i].c>0)cout<<'+'<<score[i].c<<' ';
if(score[i].c<=0)cout<<score[i].c<<' ';
if(score[i].d>0)cout<<'+'<<score[i].d<<' ';
if(score[i].d<=0)cout<<score[i].d<<' ';
cout<<'\n';
}
return 0;
}
D题
从1开始枚举并输出直到超过和就停止
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sum;
int main() {
ll n;
cin>>n;
for(int i=1;;i++){
sum+=i;
if(sum>n)break;
cout<<i<<'\n';
}
return 0;
}
E题
就是在a数组里找b数组里的数字并把它当为断电，然后看看被切割后有多少片段，片段就是0和0之间至少有一个数字，有一个有一个重复数字就将片段加1，最后再把最后一个位置的元素特判一下就可以，但是本题如果一个一个从b数组中找的话复杂度就是O(n^2)，本题的数据规模会超时，所以我们可以用二分
手写二分函数
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int a[N*5],b[N*5];
int res;
bool binary_search(int k) {
int l=1,r=m,mid;
while(l<r){
mid=(l+r)/2;
if (k<=b[mid])r=mid;
else l=mid+1;
}
if(b[l]==k)return true;
return false;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=m;i++)scanf("%d",&b[i]);
sort(b+1,b+m+1);
if(!binary_search(a[n]))res++;
for(int i=1;i<n;i++){
if(!binary_search(a[i])&&binary_search(a[i+1]))res++;
}
cout<<res;
return 0;
}
直接使用c++内置的二分函数binary_search，找到返回真，没找到返回假
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int a[N*5],b[N*5];
int res;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=m;i++)scanf("%d",&b[i]);
sort(b+1,b+m+1);
int k,t;
k= binary_search(b+1,b+m+1,a[n]);
if(!k)res++;
for(int i=1;i<n;i++){
k=binary_search(b+1,b+m+1,a[i]);
t=binary_search(b+1,b+m+1,a[i+1]);
if(k&&!t)res++;
}
cout<<res;
return 0;
}
F题
只是数据范围变大，全部开long long就可以
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
ll n,m;
ll a[N*5],b[N*5];
ll res;
bool binary_search(ll k) {
ll l=1,r=m,mid;
while(l<r){
mid=(l+r)/2;
if (k<=b[mid])r=mid;
else l=mid+1;
}
if(b[l]==k)return true;
return false;
}
int main(){
cin>>n>>m;
for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);
for(ll i=1;i<=m;i++)scanf("%lld",&b[i]);
sort(b+1,b+m+1);
if(!binary_search(a[n]))res++;
for(ll i=1;i<n;i++){
if(!binary_search(a[i])&&binary_search(a[i+1]))res++;
}
cout<<res;
return 0;
}
I题 毕业后
题意：如果有两门e等的科目就不能毕业，怎么控制e等学生的比例使全部人都可毕业，并且比例尽可能的大。 思路：比例尽可能大并且要让全部学生都毕业，所以如果让全部的学生都有一门科目不及格求出来的比例就是最大的所以用人数除以科目数就是每个科目不及格的人数，总的加起来就是确保每个人都有一门科目不及格还能都毕业，但题目要求向下取整，直接整数相除就可以了，每个科目平均不及格的人数再除以总人数就是所求的比例
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int a,b;
cin>>a>>b;
int k=b/a;
printf("%.15f",k*1.0/b);
return 0;
}
J题 旋转排列
题意：p 的长度为n，1, 2, 3。1,2,3,…n 这n个数在p中均恰好出现一次,每次操作就是把最后一个元素放到第一位，其他的依次往后移，并输出该序列，直到最后一位的元素等于目标数字时，结束循环，不会出先死循环的情况，因为每个数子恰好出现一次。 思路：把数字存储到数组里，每次都遍历一遍数组，让前一个数字等于后面一个执行了后移的操作，在执行前要先记录最后一个的数值，不然会被前面的覆盖，执行完以后让第一个等于记录的最后一个的值就完成一次操作了，循环直到满足条件。
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int n,m;
string a,b;
int main() {
IOS;
int num[2010];
cin >> n;
for (int i = 0; i < n; i++)cin >> num[i];
//for (int i = 0; i < n; i++)cout << num[i] << ' ';
do {
int k = num[n - 1];
for (int i = n-2; i >= 0; i--) {
num[i + 1] = num[i];
}
num[0] = k;
for (int i = 0; i < n; i++)cout << num[i] << ' ';
cout << '\n';
} while (num[n - 1] != n);
return 0;
}
K题 标题计数
题意：给你一些字符串，只有满足特定格式才能算标题，第一个#后面有空格，并且空格后面还有其他内容
思路：遍历一遍字符串,如果遇到空格就跳过，如果遇到除空格和#的其他字符标记一下，如果遇到第一个#标记一下，只有当是第一个#并且前面没有其他字符（除了空格），才进行判断，#后面是不是至少有一个空格并且后面的字符串还有除空格外的其他字符，满足才算一个一级标题。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int ans;
int main() {
int n;
cin >> n;
string s;
getchar();
for (int i = 0; i < n; i++) {
getline(cin,s);
int ret = 0;
int res = 0;
for (int j = 0; j < s.size(); j++) {
int k=s.size();
if (s[j] == ' ') continue;
if (s[j] != '#') res = 1;
if (s[j] == '#' && ret == 0 && res == 0) {
ret = 1;
if (s[j + 1] == ' ') {
for(int l=j+2;l<k;l++){
if(s[l]!=' '){
ans++;
break;
}
}
}
}
}
}
cout << ans;
return 0;
}
Friday
SMU Winter 2023 Round #2 (Div.2)
A题Medium Number
签到题，三个数找出中间数就可以，放到数组排个序就出来了
#include<bits/stdc++.h>
using namespace std;
int a[10010];
int main()
{
int t;
cin>>t;
while(t--){
for(int i=0;i<3;i++)cin>>a[i];
sort(a,a+3);
cout<<a[1]<<'\n';
}
return 0;
}
B题Yes-Yes?
题意：是给你一个YesYesYes......的字符串，再给你一个字符串让你判断是不是它的字串，给出字串的长度最大为五十。
思路：先定义一个60的YesYesYes.....的字符串，在遍历一遍，使用substr判断是不是字串就可以了
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
string s1, s = "YesYesYesYesYesYesYesYesYesYesYesYesYesYesYes"
"YesYesYesYesYesYesYes";
cin >> s1;
int ret=0;
for(int i=0;i<s.size();i++) {
if (s.substr(i, s1.size()) == s1){
ret=1;
cout<<"YES"<<'\n';
break;
}
}
if(ret==0)cout<<"NO"<<'\n';
}
return 0;
}
C题## Atilla's Favorite Problem
题意：就是找出字符串里最大的字母所对应的值。 思路：用sort排个序，第一个在转化为值就可以了
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
getchar();
string s;
cin >> s;
sort(s.begin(), s.end(), greater<char>());
cout<<s[0]-'a'+1<<'\n';
}
return 0;
}
D题Lost Permutation
题意：是给i个数a[i]，和一个s,能不能添加几个和为s的数到a数组里面使它成为满足题目的要求（就是这几个数有且只能出现一个，不重不漏），例如1，3，4不是，缺少2，6，3，4，2不是，缺少1和5。
思路：先找出i个数的最大值，把出现的的数用vis数组标记，在遍历一遍把从一到最大值之内没有用过的数加起来，如果等于s证明可以，如果大于s证明肯定找不出满足题目的数，如果小于s，证明前面加完了还不够，在从最大值往后加，加到等于s是说明可以了，如果大于s证明加了这个数就大不加就小，所以也不可以
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--) {
int vis[60]{};
int n, s, ma = 0;
cin >> n >> s;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
ma=max(ma,x);
vis[x] = 1;
}
int sum=0;
for (int j = 1;j<=ma; j++) {
if (!vis[j]) {
sum+=j;
}
}
if(sum==s)cout<<"YES"<<'\n';
else if(sum>s)cout<<"NO"<<'\n';
else {
for(int i=ma+1;;i++){
sum+=i;
if(sum==s){
cout<<"YES"<<'\n';
break;
}
if(sum>s){
cout<<"NO"<<'\n';
break;
}
}
}
}
return 0;
}
E题 Challenging Valleys
题意：求给出的几个数是否满足只有一个谷。 思路：那么就只能一直上升或者一直下降，或者先下降后上升，如果先上升后下降端点两侧就都是谷，我们可以看出只要出现一个山峰那么谷就一定多余1，所以我们只要找到一个先上升后下降的点就可以判断必定不满足题目，找不到就满足
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N];
int n;
int main() {
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t;
cin >> t;
while (t--) {
int ans1 = 0, ans2 = 0;
cin >> n;
for (int i = 0; i < n; i++)cin >> a[i];
for (int i = 0; i < n - 1; i++) {
if (a[i] < a[i + 1] && ans1 == 0)ans1 = 1;//记录处于上升状态
if (ans1 && a[i] > a[i + 1]) {
ans2 = 1;
break;
}//记录处于上升状态下，然后出现了下降的点，就是一个峰，就至少有两个谷
}
if (ans2)cout << "NO" << '\n';
else cout << "YES" << '\n';
}
return 0;
}
F题 Binary Inversions
题意：给一个01的字符串，只能进行一次操作也就是改变其中的一个字符，要么把0变成1，要么把1变成0，求改变以后逆序对的数量(i<j,a[i]>a[j])。 思路：要使改变以后逆序对的数量最多，要么将第一个0变成1，要么将最后一个1变成0，求两种改变方式的最大值。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[200010],n;
int num[200010];
ll solve()//判断逆序对的数量
{
memset(num,0,sizeof(num));
ll ans=0,cnt=0;
for(int i=n;i>=1;i--){
if(a[i]==0)cnt++;
else num[i]=cnt;
}
for(int i=1;i<=n;i++)ans+=num[i];
return ans;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t;cin>>t;
while(t--){
cin>>n;
int pos1=0,pos0=0,ret=0;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]==0&&ret==0){
ret=1;
pos0=i;//记录第一个0的位置
}
if(a[i]==1)pos1=i;记录最后一个1的位置
}
ll x,y,z;
x=solve();//没有改变逆序对的数量
a[pos0]=1;
y=solve();//将第一个0变成1后逆序对的数量
a[pos0]=0;//把原先改变的数组还原
a[pos1]=0;
z=solve();//将最后一个0变成1后的逆序对数量
cout<<max(x,max(y,z))<<'\n';//求三种方式的最大值
}
return 0;
}
G题 Quests（补题）
思路：分三种情况，k取任意大，k=0，k大于0。第一种，就是把在给定天数的范围内吧所有任务的硬币都加起来，如果大于目标硬币数就可以。第二种情况，k=0，此时取所有硬币中的最大值乘以天数看看是否大于等于目标硬币数。第三种找k，k肯定在天数的范围内，对它进行二分，如果算出来的sum小于目标硬币数，说明k取小了，缩减区间，直到两侧相等即为答案。
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
ll n, d , c;
ll a[N];
int main() {
IOS;
int t;
cin >> t;
while (t--) {
cin >> n >> c >> d;
for (int i = 1; i <= n; i++)cin >> a[i];
sort(a + 1, a + 1 + n, greater<int>());
if (a[1] * d < c) {
cout << "Impossible" << '\n';
continue;
}
ll sum = 0;
for (int i = 1; i <= min(n, d); i++)sum += a[i];
if (sum >= c) {
cout << "Infinity" << '\n';
continue;
}
ll l = 1, r = d, mid, k;
while (l <= r) {
mid = (l + r) >> 1;
ll all = 0;
for (int i = 1; i <= min(mid, n); i++)all += a[i];
ll res = d % mid;
ll re = d / mid;
all *= re;
for (int i = 1; i <= min(res, n); i++)all += a[i];
if (all >= c) {
k = mid;
l = mid + 1;
} else r = mid - 1;
}
k--;
cout << k << endl;
}
return 0;
}
I题 The Humanoid（补题）
题目的意思就是，给你n个数a[n]，还有一个h值，有三瓶药（两蓝一绿），蓝的用了让h值翻两倍，绿的使h值翻三倍，只有当h大于a[n]的时候才可以击败这个数，问最多可以击败多少个数。
思路：击败之后可以获得这个数的一半向下取整，每次击败之后让计数器加一。那么我们肯定是从最小的开始，遇到a[n]小于h时就使用药让自己翻倍，当全部的药使用完了以后遇到a[n]小于h时就不能击败了，最后统计的个数就是答案。但是这个题还有一个问题，就是药的使用顺序，不一定翻两倍的要比翻三倍的先用，所以我们把药水所有的使用顺序枚举一遍，最后求每一种使用药水顺序的最大值就是答案，可以使用全排列函数或者自己枚举（因为可能性少，只有三种）或者使用深度优先搜索,特别注意虽然数据范围没有超过int，但是在翻倍的过程中可能会爆int，使用用long long
全排列函数
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N];
int b[N]{2,2,3};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
while (t--) {
long long n, h,mx=0;
cin >> n >> h;
for (int i = 0; i < n; i++)cin >> a[i];
sort(a, a + n);
do{
long long res=h,ans=0;
for(int i=0,j=0;i<n;){
if(res>a[i]){
res=res+a[i++]/2;
ans++;
}
else if(j<3)res=res*b[j++];
else break;
}
mx=max(mx,ans);
}while(next_permutation(b,b+3));
cout<<mx<<'\n';
}
return 0;
}
暴力枚举，自己枚举三种可能性
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
while (t--) {
long long n, h;
cin >> n >> h;
for (int i = 0; i < n; i++)cin >> a[i];
sort(a, a + n);
long long res = h, blue, green;
blue = 0, green = 0;
long long ans1 = 0;
for (int i = 0; i < n;) {
if (res > a[i]) {
res = res + a[i++] / 2;
ans1++;
} else if (blue < 2) {
res = res * 2;
blue++;
} else if (green < 1) {
res = res * 3;
green++;
} else break;
}
blue = 0, green = 0, res = h;
long long ans2 = 0;
for (int i = 0; i < n;) {
if (res > a[i]) {
res = res + a[i++] / 2;
ans2++;
} else if (green < 1) {
res = res * 3;
green++;
} else if (blue < 2) {
res = res * 2;
blue++;
} else break;
}
long long blue1 = 0, blue2 = 0;
green = 0, res = h;
long long ans3 = 0;
for (int i = 0; i < n;) {
if (res > a[i]) {
res = res + a[i++] / 2;
ans3++;
} else if (blue1 < 1) {
res = res * 2;
blue1++;
} else if (green < 1) {
res = res * 3;
green++;
} else if (blue2 < 1) {
res = res * 2;
blue2++;
} else break;
}
cout << max({ans1, ans2, ans3}) << '\n';
}
return 0;
}
K题 Thermostat(补题)
题意：给你五个数l,r,x,a,b，问能不能实现通过操作将a变成b，操作的限制是在a上加或者减的数必须是大于等于x，问最少的操作步骤，如果不能就输出-1。 思路：可以分为几种情况，如果a=b，那么一步都不用操作就可以，输出0。如果a和b之间的距离大于等于x的话，那么一步操作就可以了。我们还可以先把a移到l再移到b，就是两步，但a和b到l的距离必须大于等于x，同理将l改成r也是两步。还可以先把a移到l，再把l移到r，再从r移到b，那么就要保证a和l的距离大于等于x，b和r的距离大于等于x，因为a，b都在l到r的范围以内。否则就不可能做到。
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int l, r, x, a, b;
cin >> l >> r >> x >> a >> b;
if (a == b) {
cout << '0' << '\n';
continue;
} else if (abs(a - b) >= x) {
cout << '1' << '\n';
continue;
} else if (abs(l - a) >= x && abs(l - b) >= x) {
cout << "2" << '\n';
continue;
} else if (abs(r - a) >= x && abs(r - b) >= x) {
cout << "2" << '\n';
continue;
} else if (abs(l - a) >= x && abs(r - b) >= x) {
cout << "3" << '\n';
continue;
} else if (abs(r - a) >= x && abs(l - b) >= x) {
cout << "3" << '\n';
continue;
} else cout << "-1" << '\n';
}
return 0;
}
L题Advantage
题意：给你几个数，输出这个数减去除了这个数之外最大数的值
思路：用两个数组，a数组存储数字，b数组找最大值和第二大的值，因为除了最大值之外，每个数除了这个数的最大值就是整个数组的最大值，而出最大值之外的最大值就是数组的第二大的值，找出来遍历一遍a数组，一边循环一边计算即可
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int a[200100],b[200100];
int t;
cin >> t;
while (t--) {
int n,ma=0;
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cin>>x;
ma=max(x,ma);
a[i]=b[i]=x;
}
sort(b+1,b+n+1);
for(int i=1;i<=n;i++){
if(a[i]==ma){//等于最大值的时候特殊处理
cout<<b[n]-b[n-1]<<' ';
continue;
}
cout<<a[i]-b[n]<<' ';
}
cout<<'\n';
}
return 0;
}
京公网安备 11010502036488号