A题：DFS搜索
直接遍历字符串s，判断是否依次出现过dfs和DFS
#include<bits/stdc++.h>
using namespace std;
int t,n;
string s;
bool st[6];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--)
{
memset(st,0,sizeof st);
bool flag1=false;
bool flag2=false;
cin>>n;
cin>>s;
for(int i=0;i<n;i++)
{
if(s[i]=='D') st[0]=true;
else if(s[i]=='F'&&st[0]==true) st[1]=true;
else if(s[i]=='S'&&st[0]==true&&st[1]==true)
{
st[2]==true;
flag1=true;
}
else if(s[i]=='d') st[3]=true;
else if(s[i]=='f'&&st[3]==true) st[4]=true;
else if(s[i]=='s'&&st[3]==true&&st[4]==true)
{
st[5]==true;
flag2=true;
}
}
if(flag1==true) cout<<1<<' ';
else cout<<0<<' ';
if(flag2==true) cout<<1<<endl;
else cout<<0<<endl;
}
}
B题：关鸡
利用mp1存第一行有火的列，mp2存第二行有火的列。再遍历mp1，用flag1，flag2，flag3，flag4标记左右是否堵住，左右是否有火。分类讨论当中间(2,0)有火时的情况，当中间没有火的情况。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int t,n;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--)
{
int res=0;//答案
//mp1[-3]=1表示(1,-3)有火，mp2[-3]=1表示(2,-3)有火
unordered_map<int,int>mp1,mp2;
//记录左边是否堵住，右边是否堵住，左边是否有火，右边是否有火
bool flag1=0,flag2=0,flag3=0,flag4=0;
//输入
cin>>n;
for(int i=0;i<n;i++)
{
int a,b;
cin>>a>>b;
if(a==1) mp1[b]=1;
else mp2[b]=1;
}
//遍历mp1
for(auto x : mp1)
{
int a=x.first;
if(a<0)
{
flag3=true;//左边有火
if(mp2[a]==1||mp2[a-1]==1||mp2[a+1]==1) flag1=true;//左边堵住
}
else if(a>0)
{
flag4=true;//右边有火
if(mp2[a]==1||mp2[a-1]==1||mp2[a+1]==1)
{
flag2=true;//右边堵住
//cout<<"here"<<endl;
}
}
}
for(auto x : mp2)
{
if(x.second==1)
{
int a=x.first;
if(a<0)
{
flag3=true;//左边有火
if(mp1[a]==1||mp1[a-1]==1||mp1[a+1]==1) flag1=true;//左边堵住
}
else if(a>0)
{
flag4=true;//右边有火
if(mp1[a]==1||mp1[a-1]==1||mp1[a+1]==1) flag2=true;//右边堵住
}
}
}
if(mp2[0]==1)//中间堵住
{
if(flag1==1&&flag2==1) res=0;//左右都堵住
else if(mp1[-1]==1&&mp1[1]==1) res=0;//鸡相邻左右都有火
else if(mp1[-1]==1&&flag2==true) res=0;//左边堵住，鸡相邻右边有火
else if(mp1[1]==1&&flag1==true) res=0;//右边堵住，鸡相邻左边有火
//左边堵住，右边堵住，鸡相邻左边有火，鸡相邻右边有火，四种情况其中之一
else if(mp1[-1]==1||mp1[1]==1||flag1==true||flag2==true) res=1;
else res=2;//其他情况需在鸡相邻左右加火
}
else
{
if(flag1==true&&flag2==true) res=0;//左右都堵住
else if(flag1==true&&flag4==true) res=1;//左边堵住，右边有火
else if(flag2==true&&flag3==true) res=1;//右边堵住，左边有火
else if(mp1[-1]==1&&mp1[1]==1) res=1;
else if(mp1[-1]==1||mp1[1]==1) res=2;
else if(flag1==true)
{
res=2;//左边堵住，右边无火
}
else if(flag2==true)
{
res=2;//右边堵住，左边无火
//cout<<"this"<<endl;
}
else if(flag3==true&&flag4==true)
{
res=2;//左右都没堵住，但都有火
}
else res=3;//其他情况，将鸡相邻左右和下方添加火
}
cout<<res<<endl;
}
}
C题：按闹分配
按照办事时间从小到大排序，总不满意度最小。二分插入位置mid，插入后其前面人员不满意度不变，其后人员每人不满意度都加上tc，插队后总不满意度为sm+(n-x)*tc
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,q,tc,t[N];
long long m;
long long sm,sum;
bool check(int x)
{
long long sc=0;
sc=sm+(n-x)*tc;//插队后n个人的总不满意度
if(sc-sm<=m) return true;
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>q>>tc;
for(int i=0;i<n;i++)
{
cin>>t[i];
}
sort(t,t+n);
for(int i=0;i<n;i++)
{
sum+=t[i];
sm+=sum;//总不满意度之和
}
while(q--)
{
long long res=0;
cin>>m;
int l=0,r=1e5;//二分查找应插队下标
while(l<r)
{
int mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
for(int i=0;i<l;i++)//前l个人的时间
{
res+=t[i];
}
res+=tc;//鸡办事的时间
cout<<res<<endl;
}
}
E题：这题又使用了贪心
暴力搜索，dfs搜索所有可能情况
#include<bits/stdc++.h>
using namespace std;
int a[15];
pair<int,int>p[15];
int t,n,m,res;
void dfs(int u)
{
if(u==m+1)//m场比赛完毕
{
int t=1;
for(int i=1;i<=n;i++)
{
if(a[i]>a[1]) t++;
}
res=min(res,t);
return;
}
int x=p[u].first,y=p[u].second;
//x号选手赢
a[x]+=3;
dfs(u+1);
a[x]-=3;
//y号选手赢
a[y]+=3;
dfs(u+1);
a[y]-=3;
//平局
a[x]+=1;
a[y]+=1;
dfs(u+1);
a[x]-=1;
a[y]-=1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--)
{
res=15;//最终名次
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
p[i].first=x;
p[i].second=y;
}
dfs(1);//遍历k场比赛的结果，取排名最高的赋值给res
cout<<res<<endl;
}
}
G题：why外卖
首先处理特殊数据，如果bi大于等于ai的话，相当于白送bi元钱，即m+=bi。其余数据按照ai从大到小排序。用sum存储ai及其后优惠卷的bi总和。接下来遍历ai，假设当前能够使用该优惠卷，则接下来所有的比当前ai小的优惠价都能使用，则此时可用总现金m+sum>=ai。即只要满足m+sum>=ai，则可购买的最大食物原价为m+sum。如果当前不满足m+sum>=ai，则当前优惠卷的bi将无法使用，则更新sum=sum-bi。特判如果遍历所有优惠卷后没有优惠卷可以使用，已有现金m即为可购买的最高原价商品。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
pair<int, int> p[N]; // 存储优惠券信息
int T, n;
long long m;
long long x;
bool cmp(pair<int,int>a , pair<int,int>b)
{
return a.first>b.first;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> T;
while(T--)
{
cin >> n >> m;
int cnt=1;
for(int i = 1; i <= n; i++)
{
int a,b;
cin>>a>>b;
if(a>b)
{
p[cnt].first=a;
p[cnt].second=b;
//cout<<a<<' '<<b<<endl;
//cout<<cnt<<endl;
cnt++;
}
else
{
m+=b;
}
}
// a[i]从大到小排序
sort(p+1, p + cnt, cmp);
long long sum=0;
for(int i=1;i<=cnt-1;i++)
{
sum+=p[i].second;
}
bool flag=0;
//cout<<"sum="<<sum<<endl;
//cout<<"m="<<m<<endl;
for(int i = 1; i <=cnt-1; i++)
{
if(m>=p[i].first-sum)
{
//cout<<x<<endl;
x=m+sum;
flag=1;
break;
}
else
{
sum-=p[i].second;
}
}
if(flag==1) cout << x << "\n";
else cout<<m<<endl;
}
return 0;
}
L题：要有光
当光源无限接近x轴时，能使得绿墙w在平面xoy轴上的投影最大，面积为梯形面积2wc
#include<cstdio>
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<vector>
#include<bitset>
#include<deque>
#include<cctype>
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=0;
cin>>t;
while(t--)
{
double c,d,h,w;
cin>>c>>d>>h>>w;
cout << fixed << setprecision(6)<< 3*c*w << endl;
}
}
M题：牛客老粉才知道的密码
起初是A~F，每次向右可以显示下六道题，如果不足六道就显示最后六题。然后从最后六题开始，每次向左可以显示前六题，如果不足六题显示最前面六题，所以如果n是六的倍数，一共有n/6种显示结果，如果n不是6的倍数，从头到尾有n/6+1种显示结果，从尾到头n/6-2种结果（因为首位两者已经被计算过），一共有2*n/6种结果
#include<bits/stdc++.h>
using namespace std;
int T;
long long n;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> T;
while(T--) {
cin >> n;
long long result;
if(n % 6 == 0) {
// n是6的倍数，直接计算
result = n / 6;
} else {
// n不是6的倍数，计算头尾的不同起始位置
result = 2 * (n / 6); // 根据新理解修正
}
cout << result << endl;
}
}
京公网安备 11010502036488号