牛客练习赛59

A.
题意：给你一个字符串s 问里面是否存在子序列 XiaoHuiHui 和 XiaoQiao
思路：暴力分别找两个是否存在就行

#include using namespace std;#define LL long long
#define pb(x) push_back(x)
#define debug(x) cout<<"..........."<
#define fi first
#define se secondconst int N = 1e5+5;
const int M = 1e3+5;
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f;bool getsubstr(string str1, string str2)
{int len1 = str1.size();int len2 = str2.size();if(len2 > len1)return false;for(int i = 0, j = 0; i < len1; i++){if( str1[i] == str2[j] && j < len2){j++;}if(j > len2)return false;}return true;
}int main()
{string s;cin >> s;string t = "XiaoQiao";string v = "Xiaohuihui";bool flag1 = getsubstr(s,t);bool flag2 = getsubstr(s,v);if(flag1 && flag2)cout << "Happy";elsecout << "emm";cout << '\n';return 0;
}

B.牛能和小镇
题意:给你n个点的二维坐标x,y 问联通这n个点的权值最小是多少
思路：看数据范围 n在1e5 跑最小生成树的话是肯定不行的，首先如果你O(n^2)去建边的话 可能边都没建完就超时了 其次 就算建好了边 如何存储也是一个问题 vector可能还有戏搞搞 普通结构体数组
1e5*1e5/2存不下 所以选择别的思路 我们化简公式发现 每个点对答案的贡献是独立的 我们只要对这n个点按照权值排序 之后两两相连就一定是最小的答案 复杂度O（nlogn）

#include 
#include 
#include #define LL long longusing namespace std;const int N = 1e5+5;int n,m;struct node
{LL x,y;LL sum;
}a[N];bool cmp(node a, node b)
{return a.sum < b.sum;
}int main()
{int n;scanf("%d",&n);for(int i = 0; i < n; i ++)scanf("%lld%lld",&a[i].x,&a[i].y),a[i].sum = a[i].y*(a[i].x - a[i].y)*(a[i].x - a[i].y);sort(a,a+n,cmp);LL res = 0;//    for(int i = 0;i < n;i ++)
//        printf("%lld %lld\n",a[i].x,a[i].y);for(int i = 1;i < n;i ++){//printf("%lld %lld\n",a[i].sum,a[i-1].sum);res += abs(a[i].sum - a[i-1].sum);}printf("%lld\n",res);return 0;
}

C.装备合成
题意：给出x个a 和 y个b 你可以用3个a 和 两个b 合成 也可以用4个a 和 1个b 合成 问最多能合成多少个
思路：考虑贪心 如果x:y >= 4:1 或者 x:y <= 2:3 那么我们按照比例全部转换过去即可 还有第三种情况
假设我们先用第一种方法合成了n个 直到他们的比为4:1 （a的消耗肯定比b的大） 那么就有
（x - 3n）/（y - 2n） = 4 / 1 化简一下 n = (4y - x) / 10 但是有可能出现小数 我们第二种比第一种多一个 和反之 但都是消耗5 所以 n = (4y - x +5 )/ 10

#include using namespace std;#define LL long longint main()
{int t;cin >> t;while(t --){LL x,y;cin >> x >> y;if(4 * y < x)printf("%lld\n",y);else if((double)x/(double)y <= 2.0/3.0)printf("%lld\n",x / 2);else{LL res = (4*y - x + 5)/10;x -= 2*res;y -= 3*res;printf("%lld\n",res + min(x / 4,y));}}return 0;
}

D. 小灰灰和小乔在玩取石子游戏，一堆石子有{n}n个石子，小灰灰和小乔轮流操作，小灰灰先手，每次操作的人可以进行以下操作：
假设当前石子数量为{k}k，如果{k>=2}k>=2，那么将石子分为{f(k)}f(k)和{k-f(k)}k−f(k)两堆，然后选择其中任意一堆石子取走。否则当前操作的人输。
其中{f(k)=x}f(k)=x，{x}x为满足满足{x*2<=k}x∗2<=k的最大整数。
小灰灰和小乔都非常聪明，所以都会采用最优的策略，你知道最后小灰灰和小乔谁能赢得游戏吗？
思路:打表发现规律谁赢是按阶段式相互递增的

#include using namespace std;#define LL long longint main()
{int t;cin >> t;while(t --){LL n;cin >> n;if(n == 1){printf("XiaoQiao\n");continue;}LL sum = 1,k = 2;int cnt = 0;while(sum < n){if(cnt&1)sum = sum+k,k = 2*k+1;elsesum = sum+k,k = 2*k-1;cnt ++ ;}if(!(cnt&1))puts("XiaoQiao");elseputs("XiaoHuiHui");}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！