Day1
蓝桥杯模拟赛
A.带分数
题意大致是用[1,9]之间的数来构造一个带分数，而且[1,9]必须每个都出现一次
这不就是全排列吗？
1.我们可以用c++的stl函数，也可dfs深搜
2.将这个全排列函数分成三个部分，整数部分，分子部分，分母部分
3.不要求输出构造的函数，只要求输出结果总数ans
贪图省事的 Qinna用了最简单的库函数法。
方法一：net_permutation()函数
#include<bits/stdc++.h>
using namespace std;
int a[10]={0,1,2,3,4,5,6,7,8,9};
int make_num(int x,int y) //将下标为x~y的数字连成y-x位的整数
{
int sum=0;
for(int i=x;i<=y;i++)
sum=sum*10+a[i];
return sum;
}
int main()
{
int n,ans=0;
cin>>n;
do{
for(int i=1;i<=7;i++) //题目给出的范围10^6，整数最多6位
{
for(int j=i+1;j<=8;j++) //分子的数最多7位
{
int num1=make_num(1,i);//整数
int num2=make_num(i+1,j);//分子
int num3=make_num(j+1,9);//分母
if(num1+(num2/num3)==n&&(num2%num3==0))
ans++;
}
}
}while(next_permutation(a+1,a+10));
cout<<ans<<endl;
return 0;
}
B.错误票据
录入 ID 号的时候发生了一处错误，造成了某个 ID 断号，另外一个 ID 重号,找出断号的 ID 和重号的 ID。
这题不难，主要是要想到将所有数存起来……
有两种方法：
第一种稍显麻烦，需要考虑换行和空格
第二种虽然也需要考虑，但是很巧妙,因为输入一个数后面必然要跟着一个空格或者换行
Qinna太笨了，比赛的时候只想到第一种。
方法一：
#include<bits/stdc++.h>
using namespace std;
int a[100000] = {0};
int main(){
int n=0,pos=0;
cin>>n;
while(n--)
{
while(cin>>a[pos]) //用cin.get()吸收回车和换行
{
pos++;
if(cin.get()=='\n') //当cin.get()等于回车的时候读下一行数据
break;
}
}
sort(a,a+pos);
int re,cr;
for(int i = 0; i < pos; i++)
{
if(a[i] == a[i+1])
re= a[i];
else if(a[i+1]-a[i] == 2)
cr= a[i]+1;
}
cout<<cr<<" "<<re;
return 0;
}
方法二：
#include<bits/stdc++.h>
using namespace std;
int a[100000] = {0};
int main(){
int n=0,pos=0;
cin>>n;
while(cin>>m){ //读到结尾就自动结束了
a[pos++]=m;
}
sort(a,a+pos);
int re,cr;
for(int i = 0; i < pos; i++)
{
if(a[i] == a[i+1])
re= a[i];
else if(a[i+1]-a[i] == 2)
cr= a[i]+1;
}
cout<<cr<<" "<<re;
return 0;
}
C.翻硬币
每次只能同时翻转相邻的两个硬币，求最小操作步数。
找到不同的就翻这枚和下一枚就好
#include <bits/stdc++.h>
using namespace std;
string s1,s2;
int main()
{
cin>>s1>>s2;
int sum=0;
for(int i=0;i<s1.length()-1;i++)
{
if(s1[i]!=s2[i])
{
sum++;
s1[i]=s2[i];
if(s1[i+1]=='*')
s1[i+1]='o';
else
s1[i+1]='*';
}
}
cout<<sum<<endl;
}
D.灵能传输
古怪的题目，求max（s[i]-s[i-1])最小
1.前缀和
2.贪心
3.排序
这题愣是没搞懂怎么写，之前没了解过前缀和，因此只好把前缀和的代码奉上了
求[l,r]的和
#include<bits/stdc++.h>
using namespace std;
const long long N=100005;
long long a[N];
long long s[N];
long long m,n;
int main()
{
scanf("%lld%lld",&n,&m);
for(long long i=1;i<=n;i++) scanf("%lld",&a[i]);
for(long long i=1;i<=n;i++) s[i]=s[i-1]+a[i];
while(m--){
long long l,r;
scanf("%lld%lld",&l,&r);
printf("%lld\n",s[r]-s[l-1]);
}
return 0;
}
E.后缀表达式
首先我们得了解负号是可以相互抵消的，一个负号和很多个负号的效果其实是一样的
1.没有负号时，直接相加
2.有负号时：
可以表示成这样：
（……+……+……)-(……+……+……)； //负号为奇数时
或者这样：
（……+……+……)-(……+……-……)； //负号为偶数时
因此，只要最大的数-最小的数+其他数绝对值就OK
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN=1e5+10;
int n,m,k;
LL a[2*MAXN];
int main(){
scanf("%d%d",&n,&m);
k=n+m+1;
for(int i=1;i<=k;i++) scanf("%lld",&a[i]);
LL sum=0;
if(!m){
for(int i=1;i<=k;i++) sum+=a[i];
printf("%lld\n",sum);
return 0;
}
sort(a+1,a+k+1);
sum+=a[k];sum-=a[1];m--;
for(int i=2;i<k;i++) sum+=abs(a[i]);
printf("%lld\n",sum);
return 0;
}
F.等差数列
这题很具有迷惑性格，一开始我以为公差是最小的就好了，但是如果有四个数，差值为2，3。我们不能取2作为公差，因为中间无论插入什么数，都不能构成等差数列。
因此，正确的想法应该是求后面各项与第一项所有差值的最大公约数，这样能保证数列中的数最少，并且一定能构成等差数列。
最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。
例如：
2，3的最大公因数是1，因此公差为1
c++库函数中有个专门求最大公约数的函数__gcd()
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int a[N];
int main(){
int n;
scanf("%d", &n);
for(int i = 0; i < n; i ++){
scanf("%d", &a[i]);
}
sort(a, a + n);
//求后面各项与第一项所有差值的最大公约数
int d = 0;
for(int i = 1; i<n;i++) d=__gcd(d,a[i]-a[0]);
if(!d) printf("%d\n", n);
else printf("%d\n", (a[n-1]-a[0])/d+1);
return 0;
}
G.特别数的和
直接按照题目要求把数给拆分判断就OK
#include <bits/stdc++.h>
using namespace std;
bool Is(int x){
int t;
while(x){
t=x%10;
if (t== 2||t==0||t==9||t==1) return true;
else x/=10;
}
return false;
}
int main(){
int n;
cin>>n;
int sum=0;
for(int i= 1;i<=n;++ i){
if(Is(i))
sum +=i;
}
cout<<sum<<endl;
return 0 ;
}
H.完全二叉树的权值
就是一个模拟题，一层一层的算。确定每一层的头和尾，记录深度。
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
int maxd=0;//记最大的那层深度为maxd
long long max=-100005;//记最大深度
//每层第一个数i是2的n次方
//每层最后一个数为下一层的前一个数。
int d=1;
for(int i=1;i<=n;i*=2,d++)
{
long long sum=0;
for(int j=i;j<=2*i-1&&j<=n;j++)
{
sum+=a[j];
}
if(sum>max) //找到最大的那层
{
max=sum;
maxd=d;
}
}
cout<<maxd<<endl;
}
Day2
二分法补题
分巧克力
每个小朋友至少1x1
输出切出的正方形巧克力最大可能的边长。
#include<bits/stdc++.h>
using namespace std;
int const N = 100010;
int w[N], h[N];//存储长、宽
int n, k;
bool chack(int a)
{
int num = 0;//记录分成长度为 a 的巧克力数量
for (int i = 0; i < n; i++)
{
num += (w[i] / a) * (h[i] / a);//每一大块可以分成的边长为 a 的巧克力数量
if (num >= k) return true;//大于要求数量，返回真
}
return false;
}
int main()
{
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> h[i] >> w[i];
int l = 1, r = 1e5;//小巧克力数量边长一定在 1 -- 100000 之间
while (l < r)//二分小巧克力边长范围，找到符合要求的最大值
{
int mid = l + (r - l + 1 >> 1);//因为l = mid ，所以 mid 取 l + r + 1 >> 1,为了防止加和越界，改写成 l + (r - l + 1 >> 1)
if (chack(mid)) l = mid;
else r = mid - 1;
}
cout << r;
}
Day3
SMU Winter 2023 Round #1 (Div.2)~ACM
A.不可以，总司令
满足条件输出
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,y;
cin>>n>>y;
if(n>y){
cout<<"NO"<<endl;
}
else if(n<y){
cout<<"YES"<<endl;
}
else{
cout<<"equal probability"<<endl;
}
return 0;
}
B.计算
将三位数拆分
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long n;
cin>>n;
long long ge,shi,bai;
ge=n%10;
bai=n/100;
shi=n/10%10;
long long sum1,sum2,sum3;
sum1=ge+shi+bai;
cout<<sum1<<endl;
sum2=sum1*sum1;
cout<<sum2<<endl;
sum3=sum1*sum1*sum1;
cout<<sum3<<endl;
return 0;
}
C.拱猪计分
考察细心和耐力的题目，写到吐血
发现一个很有用的库函数pair<T,T>,对付拱猪计分的那题非常有帮助
#include<bits/stdc++.h>
using namespace std;
char s[5];
const int shuzilue[16]={0,-50,-2,-3,-4,-5,-6,-7,-8,-9,-10,-20,-30,-40,-100,+100};
struct shabi
{
char fl;//花色
int shuzi;//数字
} f[5][21];
int sum[5];
int main()
{
while (1)
{
memset(f,0,sizeof(f));
memset(sum,0,sizeof(sum));
bool flag=true;//是否文件结束
for (int i=1;i<=4;i++)
{
int n;
scanf("%d",&n);
if (n!=0) flag=false;
for (int j=1;j<=n;j++)
{
scanf("%s",s); //字符串
f[i][j].fl=s[0]; //花色
f[i][j].shuzi=s[1]-48; //数字
if (strlen(s)==3)
f[i][j].shuzi=f[i][j].shuzi*10+s[2]-48;//最多两位数
if (f[i][j].fl=='C')
f[i][17].shuzi++;//花色数量
else if (f[i][j].fl=='S') f[i][18].shuzi++;
else if (f[i][j].fl=='D') f[i][19].shuzi++;
else f[i][20].shuzi++;
}
if (n==0) {sum[i]=0;continue;}//若未持有这 1616 张牌之任一张则以得零分计算
if (n==16) {sum[i]=1000;continue;}//若有一玩家持有所有 16 张计分牌，则得 +1000 分
if (f[i][20].shuzi==13) //全H
{
sum[i]+=200;
if (f[i][18].shuzi==1 && f[i][19].shuzi==1) sum[i]+=500;
else if (f[i][18].shuzi==1) sum[i]-=100;
else if (f[i][17].shuzi==1) sum[i]+=100;
}
else
for (int j=1;j<=n;j++) //普通牌
if (f[i][j].fl=='H') sum[i]+=shuzilue[f[i][j].shuzi];
else if (f[i][j].fl=='S') sum[i]+=shuzilue[14];
else if (f[i][j].fl=='D') sum[i]+=shuzilue[15];
if (n==1 && f[i][17].shuzi==1) sum[i]=50;//只有1张牌且是C牌
else if (f[i][17].shuzi==1) sum[i]*=2;//不只1张牌但是有C牌
}
if (flag)
return 0; //4个都是0
for (int i=1;i<=4;i++)
if (sum[i]>0) printf("+%d ",sum[i]);
else printf("%d ",sum[i]);
printf("\n");
}
return 0;
}
D.数字口袋
只要注意不要超过sum的最大值就好
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long n;
cin>>n;
long long sum=0;
long long i=1;
while(sum<n){
sum=sum+i;
if(sum<=n){//一定要有这判断哇
cout<<i<<endl;
}
i++;
}
return 0;
}
E\F狠狠地切割(Easy\hard Version)
esay版本有两种解法，离散和二分，hard直接二分。
easy:
#include<bits/stdc++.h>
#define N 5000006
using namespace std;
int a[N],b[N],c[N];
bool iscut[N];
int main()
{
ios::sync_with_stdio(false);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
for(int i=1;i<=m;i++)
c[b[i]]=1; //将b的值保存在c中
for(int i=1;i<=n;i++)
if(c[a[i]])
iscut[i]=true; //如果a中的值等于b，此点为割点，将下标值标记为true
iscut[0]=true; //a的头也是割点
int cnt=0;
for(int i=1;i<=n;i++)
if(!iscut[i]&&iscut[i-1])
cnt++;
cout<<cnt<<endl;
return 0;
}
hard:
#include<bits/stdc++.h>
using namespace std;
vector<long long>a,b;
int n,m;
bool check(long long k)
{
long long l=0,r=m-1,mid;
while(l<=r){
mid=(l+r)>>1;
if(k>b[mid]) l=mid+1;
else if(k<b[mid]) r=mid-1;
else return true; //找到
}
return false; //找不到
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
long long x,y;
for(long long i=0;i<n;i++) cin>>x,a.push_back(x);
for(long long i=0;i<m;i++) cin>>y,b.push_back(y);
sort(b.begin(),b.end()); //vector的迭代器
long long ans=0;
if(!check(a[0])) //第一个数据不是断点，说明是个片段
ans++;
for(long long i=1;i<n;i++){
if(!check(a[i])&&check(a[i-1])) //这个数据不是断点，但是前一个数据是断点
ans++;
}
cout<<ans<<endl;
}
hard不用stl容器写法：
#include<bits/stdc++.h>
#define N 5000006
using namespace std;
int a[N],b[N],c[N];
bool iscut[N];
int main()
{
ios::sync_with_stdio(false);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
for(int i=1;i<=m;i++)
c[b[i]]=1; //将b的值保存在c中
for(int i=1;i<=n;i++)
if(c[a[i]])
iscut[i]=true; //如果a中的值等于b，此点为割点，将下标值标记为true
iscut[0]=true; //a的头也是割点
int cnt=0;
for(int i=1;i<=n;i++)
if(!iscut[i]&&iscut[i-1])
cnt++;
cout<<cnt<<endl;
return 0;
}
另外，我发现stl可以快速解决去重的问题：
vector
sort(alls.begin(),alls.end()); //将所有值排序
alls.erase(unique(alls.begin(),alls.end()),alls.end()); //去掉重复元素
其中unique的作用时将所有重复元素放在数组的后面，并返回重复元素之前的最后一个数组下标，之后erase掉后面的重复元素就ok
G.如何得到npy
emmm实在是不好意思，写这题的时候我还不会图论和dfs，因此我不打算解这题，我把关于图论和dfs的知识先了解一波。
dfs代码：
dfs进行全排列
//DFS入门小题：打印全排列
#include<bits/stdc++.h>
using namespace std;
const int N=10000005;
int path[N];//存路径
bool st[N];//存状态
int n;//1~n的全排列
void dfs(int u){
if(u==n){
for(int i=0;i<n;i++)
printf("%d ",path[i]);
cout<<endl;
}
else{
for(int i=1;i<=n;i++){
if(!st[i]){ //没有记录过i
path[u]=i; //记录u这个位置可放的数
st[i]=true; //标记i被记录
dfs(u+1);//进入下一层
st[i]=false; //在这一层恢复现场
}
}
}
}
int main()
{
cin>>n;
dfs(0);//从0开始
return 0;
}
H.做不完的作业
有n个任务，每个有时间ti
Eric 前 i天要睡rxi小时，每天至少睡1小时，每天只能在做完所做的任务后睡觉。
问至少需要多少天才能完成任务。
那么我们可以 O(1) 求出完成这个任务需要先睡多少天，再完成任务即可
乐，，我还是没搞懂，直接复制大佬的代码，哭辽~
#include<bits/stdc++.h>
using namespace std;
long long n,x,p,q,i=1,sum,t,w;
int main(){
cin>>n>>x>>p>>q;
while(n--){
cin>>w;
if((x-t-w+sum)*q>=i*p*x&&x-t>w)t+=w;
else{
sum+=x-t;
i++;
long long l=ceil((q*(sum+x-w)-p*i*x)*1.0/(x*p-x*q));
if(l>0){
sum+=x*l;
i+=l;
}
t=w;
}
}
cout<<i;
}
I.毕业后
见代码
#include<bits/stdc++.h>
using namespace std;
//E每个学生最多拿到一个
//最大比例 ,向下取整floor()
int main()
{
double a,b; //a科目，b人数
cin>>a>>b;
double w;
w=1.0/a; //a种科目有一个为E的概率为1.0/a
w=floor(w*b)/b; //b学生中有一个科目为E的学生人数/b学生总人数
printf("%.16lf",w);
return 0;
}
J.旋转排列
将 p 里的每一个数字都依次向后移动一位，并把 p 的最后一个数字移动到开头去。
#include<bits/stdc++.h>
using namespace std;
vector<int>a;
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++){
int x;
cin>>x;
a.push_back(x);
}
while(1){
a.insert(a.begin(),a[n-1]);//头部插入
a.pop_back(); //尾部删除
for(int i=0;i<n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
if(a[n-1]==n){
break;
}
}
return 0;
}
K.标题计数
数题解中有多少个一级标题
若一行的第一个非空白字符是井号（#），且紧跟着若干个空格，则这一行剩余的非空白内容将会按照一级标题渲染。
#include<bits/stdc++.h>
using namespace std;
int n,pos;
int main(){
cin>>n;
cin.get();
while(n--){
char a[1000];
fgets(a,1000,stdin); //读入一行数据
int f=0;
for(int i=0;a[i+1]!='\0';i++){
if(f==1&&a[i]!=' '){
pos++; //一级标题个数+1
break;
}//可能有首字符是空格的情况
if(a[i]!='#'&&a[i]!=' ') //不是一级标题，直接break
break;
if(a[i]=='#'){ //判断是不是一级标题
if(a[i+1]==' ')
f=1; //是标记为true
else
break; //不是直接break
}
}
}
cout<<pos;
return 0;
}
Day4
补题
用数组实现链表
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少
// cur 存储当前已经用到了哪个点
int cur=1,e[N],ne[N];
//注意：头结点为cur=0
void add_k(int k, int x) //将x插到第k个插入的元素后面
{
e[cur]=x; //将x值存入head之后的结点
ne[cur]=ne[k]; //将x结点指向k结点的下一个结点
ne[k]=cur; //将k结点的下一个结点指向x结点
cur++; //cur变到下一个位置
}
void del_k(int k) //删除第k个插入的元素后面的数
{
ne[k] = ne[ne[k]]; //k的下一个结点，指向k下一个结点的下一个结点。
//即掠过k的下一个结点
}
int main()
{
int m;
cin >> m;
while (m--) { //m组测试用例
char op;
int k,x;
cin >> op;
if (op == 'H') { //特殊判断，H的时候头结点cur=0
cin >> x;
add_k(0,x);
}
else if (op == 'I') { // 执行insert操作
cin >> k >> x;
add_k(k,x);
} else {
cin >> k;
del_k(k);
}
}
for (int j = ne[0]; j ; j = ne[j]) cout << e[j] << ' ';
cout << endl;
return 0;
}
Day5
SMU Winter 2023 Round #2 (Div.2)
A Medium Number
给三个数求中位数
1.可以排序之后取中间值
#include<bits/stdc++.h>
using namespace std;
int a[5];
int main()
{
int t;
cin>>t;
while(t--)
{
memset(a,0,sizeof(a));
for(int i=0;i<3;i++)
cin>>a[i];
sort(a,a+3);
cout<<a[1]<<endl;
}
return 0;
}
2.也可以直接无脑找出中间值、
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t, a, b, c;
scanf("%d", &t);
while (scanf("%d%d%d", &a, &b, &c) != EOF)
{
if (a > b)
{
t = a; //b>a
a = b;
b = t;
}
if (a > c)//c>a
{
t = a;
a = c;
c = t;
}
if (b > c)//c>b
{
t = b;
b = c;
c = t;
}
printf("%d\n", b);
}
return 0;
}
B Yes-Yes?
用c++的stl寻找字串
#include<bits/stdc++.h>
using namespace std;
string s1;
int main(void)
{
int t;
cin >> t;
while(t--)
{
string s = "YesYesYesYesYesYesYesYesYesYesYesYesYesYesYesYesYesYesYesYesYesYesYesYesYesYesYesYesYesYesYesYesYesYesYes";
cin >> s1;
if(s.find(s1)!=-1)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}
C.Atilla's Favorite Problem
字符以'\0'为结束标志
特别记住：
小写字母-'a'=0~25
方法一：C风格的写法
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t,n,max;
scanf("%d ",&t);
while(t--)
{
max = 0;
scanf("%d ", &n);
int c;
while ((c=getchar())!= '\n') //用'\0'就用担心找不到结尾
{
if (max< c- 'a' + 1)
{
max= c- 'a' + 1;
}
}
printf("%d\n", max);
}
return 0;
}
方法二：C++风格的写法
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t,n,max;
scanf("%d ",&t);
while(t--)
{
max=0;
scanf("%d ",&n);
string s;
int a[100005];
cin>>s; //读入字符串
for(int i=0;i<s.size();i++)
a[i]=s.at(i)-'a'+1; //将字符串化成的数组赋值给整型数组
sort(a,a+s.size(),greater<int>()); //排序找最大的
printf("%d\n",a[0]); //输出最大
}
return 0;
}
D.Lost Permutation
全排列，先想到暴力bf
1.暴力的时候慢慢加都超过和，肯定不行
2.暴力完之后检查一遍，如果前面暴力枚举的数没有达到m+res个数，也就是说暴力枚举得到的数列个数不够，那也是没有完成全排列。
#include<bits/stdc++.h>
#define N 110
typedef long long ll;
using namespace std;
bool b[N];
int main(void)
{
int t;
cin >> t;
while(t--)
{
memset(b,0,sizeof(b));
ll m,s;
cin >> m >> s;
for(int i=1;i<=m;i++)
{
int num;
cin >> num;
b[num] = 1; //离散化
}
ll sum=0;
int flag=0;
int res=0;
for(int i=1;i<=N;i++) //bf
{
if(!b[i]) //当没有i这个数时
{
sum+=i;
res++; //记录bf添加多少个数
b[i] = 1;
}
if(sum==s) //正好等于和
{
break;
}
else if(sum>s) //大于和慢慢累加都不行你没救了
{
flag=1;
break;
}
}
for(int i=1;i<=m+res;i++)
{
if(!b[i]) //遍历一遍全排所有元素,看看是不是全排列
{
flag=1; //如果有一个没有被1的元素混入，说明前面bf没有枚举到他就已经超了或者等于s
break;
}
}
if(!flag)
cout << "YES" << endl;
else
cout << "NO" <<endl;
}
return 0;
}
E.Challenging Valleys
有坑点
1.只能有一个波谷，刚开始我以为题目判断的是有没有波谷，于是wrong on test 2
于是，我只能转换思路，判断是否只有一个波谷。
2.但是，没想到中间会有想通过的元素，于是判断左右两边是否存在波谷就显得蛮烦。
于是，当元素相同的时候直接把指针移向相同元素的后一位。
#include <bits/stdc++.h>
using namespace std;
long long a[200005];
int main(void)
{
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
int cnt=0;
int l=1,r=1;//刚开始l和r相等
a[0] = 1e9+10; //为了不越界多围一圈
a[n+1] = 1e9+10; //左右边界一定满足，不论大小
for(int i=1;i<=n;i++)
{
//如果满足l小于左边，r小于右边，则是山谷，cnt++即可
if(a[l]<a[l-1]&&a[r]<a[r+1])
{
l = r+1;
r = l;
cnt++;
continue;
}
//如果r跟r+1相等,则证明它们是相同元素，所以r++
if(a[r]==a[r+1])
{
r++;
continue;
}
//保证左右仍然相等
l = r+1;
r = l;
}
if(cnt==1)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}
F.Binary Inversions
本题只能改变一次：You are allowed to perform one operation on it at most once.
为了使0前面的1最多。
有两种改法：
1.将最前面的0改成1
2.将最后面的1改成0
本题还有一个坑点，也许改过之后的0前面的1不如不改的情况，所以要记得比较不改的情况。
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 2e5+10;
ll a[N],b[N],c[N];
int main(void)
{
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> a[i];
b[i] = a[i];
c[i] = a[i];
}
ll res=0;
for(int i=1;i<=n;i++)
{
if(a[i]==0) //0变成1
{
a[i] = 1;
break;
}
}
ll sum1=0,c1=0;
for(int i=1;i<=n;i++)
{
if(a[i]) //每个0前的1有几个
{
c1++;
}
else
{
sum1 += c1;//将第一个0改成1的sum
}
}
res = max(res,sum1);
for(int i=n;i>=1;i--)
{
if(b[i]) //1改为0
{
b[i] = 0;
break;
}
}
sum1=0,c1=0;
for(int i=1;i<=n;i++)
{
if(b[i])
{
c1++; //复制粘贴
}
else
{
sum1 += c1;
}
}
res = max(sum1,res);
sum1=0;
c1 = 0;
for(int i=1;i<=n;i++)
{
if(c[i]) //不变
{
c1++;
}
else
{
sum1 += c1;
}
}
res = max(sum1,res);
cout << res << endl;
}
return 0;
}
G.Quests
规则是这样的，你回答问题，你可以得到奖励，但是不能在k天内继续回答同一个问题。
1.如果某一天最大的奖励大于c。说明k无论取何值，都能满足奖励大于c->输出Infinity
2.如果所有天的最大奖励加起来都不大于c。说明k无论取何值，都不会满足奖励大于c->Impossible
3.用二分的方法，找出k。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll arr[200005];
bool check(int mid, ll c, int d, int n){
ll sum = arr[0];
for(int i = 1; i <= mid && i<min(d,n); i++){
sum += arr[i];
}
ll ans = d / (mid + 1); //运用倍数关系，直接将前面的循环步骤省略
int cnt = d % (mid + 1);
sum *= ans;
for(int i = 0; i < cnt && i < n; i++){
sum += arr[i];
}
if(sum >= c){
return true;
}
return false;
}
int main(){
int t;
cin >> t;
while(t--){
int n;
ll c;
int d;
cin >> n >> c >> d;
for(int i = 0; i < n; i++){
cin >> arr[i];
}
sort(arr, arr + n, greater<ll>());
ll sum = 0;
for(int i = 0; i < min(n, d); i++){
sum += arr[i];
}
if(sum >= c){
cout << "Infinity" << endl;
continue;
}
if(arr[0] * d < c){
cout << "Impossible" << endl;
continue;
}
int l = 0, r = max(d,n);
while(l <= r){
int mid = (l + r) / 2;
if(check(mid, c, d, n)){
l = mid + 1;
}else{
r = mid - 1;
}
}
cout << r << endl; //输出哪一边都ok
}
return 0;
}
H.SlavicG's Favorite Problem
emm由于dfs是真的不会，只能先放下这题去学深搜。。于是就把大佬的代码放上来
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<queue>
using namespace std;
vector<pair<int,int>> p[100050];
int n,a,b;
int f = 0;
int dis[100050];
int vis[100050];
int dis1[100050];
int vis1[100050];
map<int,int> rr,ll;
void bfs()
{
queue<int> q;
q.push(a);
dis[a] = 0;
while(q.size())
{
auto ver = q.front();
q.pop();
if(vis[ver])
continue;
vis[ver] = 1;
for(int i = 0;i < p[ver].size();i++)
{
auto j = p[ver][i];
int ne = j.first;
int ww = j.second;
if(!vis[ne])
{
if(ne != b)
{
dis[ne] = ww^dis[ver];
q.push(ne);
}
}
}
}
}
void bfs1()
{
queue<int> q;
q.push(b);
dis1[b] = 0;
while(q.size())
{
auto ver = q.front();
q.pop();
if(vis1[ver])
continue;
vis1[ver] = 1;
for(int i = 0;i < p[ver].size();i++)
{
auto j = p[ver][i];
int ne = j.first;
int ww = j.second;
if(!vis1[ne])
{
dis1[ne] = ww^dis1[ver];
rr[dis1[ne]] = 1;
q.push(ne);
}
}
}
}
void solve()
{
f = 0;
cin >> n >> a >>b;
rr.clear();
ll.clear();
for(int i = 1;i <= n;i++)
{
p[i].clear();
vis[i] = 0;
dis[i] = 0;
vis1[i] = 0;
dis1[i] = 0;
}
for(int i = 1;i < n;i++)
{
int l,r,w;
cin >> l>>r>>w;
p[l].push_back({r,w});
p[r].push_back({l,w});
}
bfs();
bfs1();
for(int i = 1;i <= n;i++)
{
if(rr[dis[i]])
{
cout<<"YES\n";
return ;
}
}
cout<<"NO\n";
}
signed main()
{
int t = 1;
cin >> t;
while(t--)
{
solve();
}
}
I.The Humanoid
怪兽的血量越多越难吸收，所以要先从血量小的开始吸收，如果一个怪兽开始不可以被吸收了，后面的大血量怪兽都不可以被吸收。
我们可以发现一共就三瓶药,两种,我们把所有喝药的顺序情况枚举出来,找最大值即可
一、3,2,2
二、2,3,2
三、2,2,3
#include<bits/stdc++.h>
using namespace std;
long long a[200500];
void solve()
{
long long n,hh;
cin >> n >> hh;
for(int i = 0;i < n;i++)
cin >> a[i];
sort(a,a+n); //排序找最弱的人
int ans = 0;
//k=0,up=0 3,2,2
//k=1,up=0 2,3,2
//k=2,up=0 2,2,3
for(int k = 0;k <3;k++)
{
int up = 0;
int i = 0;
long long h = hh;
while(i < n)
{
if(h > a[i]) //h的血量大于人的血量
{
h += a[i]/2; //只能提升a[i]/2
i++;
}
else if(up == 3)
{
break;
}
else
{
if(up == k)
{
h = h*3;
}
else
{
h = h*2;
}
up++;
}
}
ans = max(ans,i); //吸收最多的人
}
cout<<ans<<"\n";
}
int main()
{
int t = 1;
cin >> t;
while(t--)
{
solve();
}
}
J.Make It Round
给定n,m,我们可以把n变为n×k（1<=k<=m,k为正整数)，如果存在，请输出末尾0的个数最多的n×k，否则输出n×m。
为了出现0，我们需要有10，也就是2×5。
有几个0就是有多少个2×5
#include<bits/stdc++.h>
using namespace std;
char a[105][105];
void solve()
{
long long n,m;
cin >>n >> m;
int cnt2 = 0,cnt5 = 0;//记录5的个数和2的个数
int k = n;
while(k%2 == 0) //记录2的个数
{
cnt2 ++;
k = k/2;
}
while(k%5 == 0) //记录5的个数
{
cnt5 ++;
k = k /5;
}
while(cnt5 > cnt2&& m/2) //5的个数>2的个数，想办法在[1,m]中搞出2，凑成10
{
cnt5--;
n*=2;
m/=2;
}
while(cnt2 > cnt5&& m/5)//同理
{
cnt2--;
n *=5;
m/=5;
}
long long ans = 1;
while(ans*10 <= m)//找10的数目，找到不能找为止,当然,最后虽然可能不为10
{
ans = ans*10;
}
ans = m/ans*ans;
cout<<ans*n<<"\n"; //新的n已经保证为圆润的数了
}
int main()
{
int t = 1;
cin >> t;
while(t--)
{
solve();
}
}
K.Thermostat
见代码：
分三种情况
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
int l,r;
int x,a,b;
signed main()
{
cin>>t;
while(t--)
{
int k=5; //k不会大于3
cin>>l>>r>>x>>a>>b;
if(a==b) //相同不用改变
{
cout<<0<<endl;
continue;
}
if(abs(a-b)>=x) //ab距离已经大于x，直接移到b
{
cout<<1<<endl;
continue;
}
if(abs(l-b)<x&&abs(r-b)<x) //b这个位置不能由两头到达，a不管怎么移动都到不了b
{
cout<<-1<<endl;
continue;
}
if(abs(l-a)>=x&&abs(l-b)>=x){
k=2;
}
else{
k=3;
}
if(abs(r-a)>=x&&abs(r-b)>=x){
k=2;
}
else{
k=k<3?k:3;
}
if(k>3)
{
cout<<-1<<endl;
}
else
{
cout<<k<<endl;
}
}
return 0;
}
L.Advantage
1.如果不是最大值，那就只能减去第最大
2.如果使最大值，那就减去第二大
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll t;
scanf("%lld",&t);
while(t--){
vector<ll>a,b;
ll n;
scanf("%lld",&n);
for(ll i=0;i<n;i++){
ll x;
scanf("%lld",&x);
a.push_back(x);
b.push_back(x);
}
sort(a.begin(),a.end(),greater<ll>());
for(ll i=0;i<n;i++){
if(b[i]!=a[0]) //不等于最大值，做差
printf("%d ",b[i]-a[0]);
else printf("%d ",b[i]-a[1]);//等于，减倒数第二大的
}
printf("\n");
}
}