• 牛客-模拟、枚举、贪心 2022.11.15


    月月查华华的手机

    按照字母A-Z的顺序,分别按照下标的从小到大记录每个字母的位置。之后对于每个名字的查询,从名字的第一个字母出现的第一个位置开始,二分查找之后每个字母的位置是否大于当前的位置,如果大于,更新当前位置,直至名字数组结束,说明存在子序列,否则不存在。

    对于第一个字母是否存在的情况在遍历之前进行特判。

    1. #include
    2. using namespace std;
    3. int main() {
    4. string A;
    5. cin >> A;
    6. vectorint>> p;
    7. for(int i = 0; i < 26; i++) {
    8. vector<int> tmp;
    9. p.emplace_back(tmp);
    10. }
    11. for(int i = 0; i < A.size(); i++)
    12. p[A[i] - 'a'].emplace_back(i);
    13. int n;
    14. cin >> n;
    15. for(int i = 0; i < n; i++) {
    16. string B;
    17. cin >> B;
    18. if(p[B[0] - 'a'].size() == 0) {
    19. cout << "No\n";
    20. continue;
    21. }
    22. int start = p[B[0] - 'a'][0];
    23. bool flag = true;
    24. for(int j = 1; j < B.size(); j++) {
    25. int idx = upper_bound(p[B[j] - 'a'].begin(), p[B[j] - 'a'].end(), start) - p[B[j] - 'a'].begin();
    26. if(idx == p[B[j] - 'a'].size()) {
    27. flag = false;
    28. break;
    29. }
    30. start = p[B[j] - 'a'][idx];
    31. }
    32. if(flag)
    33. cout << "Yes\n";
    34. else
    35. cout << "No\n";
    36. }
    37. return 0;
    38. }

    ranko的手表

    遍历所有的时间,记录所有符合的开始时间和结束时间,遍历符合条件的开始时间数组和符合条件的结束时间数组,两者时间不能相等,记录最大差值和最小差值即可。

    1. #include
    2. using namespace std;
    3. int main() {
    4. string s1, s2;
    5. cin >> s1 >> s2;
    6. vector<int> res1;
    7. for(int i = 0; i <= 1439; i++) {
    8. int tenhour = (i / 60) / 10, gehour = (i / 60) % 10;
    9. int tenmin = (i % 60) / 10, gemin = (i % 60) % 10;
    10. if(s1[0] != '?' && tenhour != (s1[0] - '0'))
    11. continue;
    12. if(s1[1] != '?' && gehour != (s1[1] - '0'))
    13. continue;
    14. if(s1[3] != '?' && tenmin != (s1[3] - '0'))
    15. continue;
    16. if(s1[4] != '?' && gemin != (s1[4] - '0'))
    17. continue;
    18. res1.emplace_back(i);
    19. }
    20. vector<int> res2;
    21. for(int i = 0; i <= 1439; i++) {
    22. int tenhour = (i / 60) / 10, gehour = (i / 60) % 10;
    23. int tenmin = (i % 60) / 10, gemin = (i % 60) % 10;
    24. if(s2[0] != '?' && tenhour != (s2[0] - '0'))
    25. continue;
    26. if(s2[1] != '?' && gehour != (s2[1] - '0'))
    27. continue;
    28. if(s2[3] != '?' && tenmin != (s2[3] - '0'))
    29. continue;
    30. if(s2[4] != '?' && gemin != (s2[4] - '0'))
    31. continue;
    32. res2.emplace_back(i);
    33. }
    34. int min1 = INT_MAX, max1 = INT_MIN;
    35. for(int i = 0; i < res1.size(); i++) {
    36. for(int j = 0; j < res2.size(); j++) {
    37. if(res1[i] >= res2[j])
    38. continue;
    39. min1 = min(min1, res2[j] - res1[i]);
    40. max1 = max(max1, res2[j] - res1[i]);
    41. }
    42. }
    43. cout << min1 << " " << max1 << endl;
    44. return 0;
    45. }

    牛妹和01串

    模拟遍历01串即可。

    1. #include
    2. using namespace std;
    3. int main() {
    4. string s;
    5. cin >> s;
    6. int res = 0, start = 0;
    7. while(start < s.size()) {
    8. bool flag = false;
    9. for(int j = start + 1; j < s.size(); j++) {
    10. if(s[j] == s[start])
    11. continue;
    12. else {
    13. flag = true;
    14. start = j;
    15. break;
    16. }
    17. }
    18. if(flag) {
    19. res += 1;
    20. start += 1;
    21. } else
    22. break;
    23. }
    24. cout << res << endl;
    25. return 0;
    26. }

    兔子的区间密码

    异或运算+大数据规模,考虑采用位运算,位运算需要记录64位二进制数。可以观察一下样例的几组数据的规律,如果区间最大值的二进制位数相较于最小值要高出一位以上,即最大值二进制最高位为一,而最小值的该位置为零,最小值在下一位才为一,这种情况是大一位;如果是最小值的该位置后几个位置才存在第一个一,说明更小。则说明存在两个数字,可以使得异或值为所有二进制位值都为一,只从二进制最低位到最大值的二进制最高位。

    最大值二进制:1000 最小值二进制:0100 说明存在 1000 ^ 0111  = 1111

    最大值二进制:1001 最小值二进制:0010 同理

    如果二者最高位相同,则比较下一位,直到出现不同的二进制位置,那么从这一位置开始往后到二进制的最低位,存在全为一的最大值,之前的高位置都相同,异或结果为0。

    最大值二进制:110010 最小值二进制:110001 说明存在异或结果为110011

    1. #include
    2. using namespace std;
    3. int main() {
    4. int t;
    5. cin >> t;
    6. for(int i = 0; i < t; i++) {
    7. long long l, r;
    8. cin >> l >> r;
    9. if(l == r)
    10. cout << 0 << endl;
    11. else if((l + 1) == r)
    12. cout << (l^r) << endl;
    13. else {
    14. vector<int> left(64, 0);
    15. vector<int> right(64, 0);
    16. vector<long long> num(64, 0);
    17. long long sum = 1;
    18. int lidx = 0, ridx = 0;
    19. while(r) {
    20. num[ridx] = sum;
    21. right[ridx++] = r % 2;
    22. r /= 2;
    23. sum *= 2;
    24. }
    25. while(l) {
    26. left[lidx++] = l % 2;
    27. l /= 2;
    28. }
    29. long long res = 0;
    30. while(ridx >= 0) {
    31. if(right[ridx] == left[ridx])
    32. ridx -= 1;
    33. else {
    34. while(ridx >= 0) {
    35. res = res + num[ridx];
    36. ridx -= 1;
    37. }
    38. break;
    39. }
    40. }
    41. cout << res << endl;
    42. }
    43. }
    44. return 0;
    45. }

     [USACO 2007 Nov G]Sunscreen

    每头奶牛都有一个区间范围,有一些数量的药剂,这些药剂使用后可以使奶牛的数值保持在一个值,问最多可以有多少头奶牛的数值保持在自身规定的区间范围

    对于药剂的数值,按照从大到小排序,对于奶牛的区间,按照区间最小值从大到小排序,之后遍历奶牛,对于每头奶牛,遍历药剂看是否存在符合条件的药剂,记录结果即可。

    1. #include
    2. using namespace std;
    3. struct node {
    4. int min;
    5. int max;
    6. };
    7. struct ss{
    8. int spf;
    9. int cov;
    10. };
    11. bool cmp1(struct node& a, struct node& b) {
    12. return a.min > b.min;
    13. }
    14. bool cmp2(struct ss& a, struct ss& b) {
    15. return a.spf > b.spf;
    16. }
    17. int main() {
    18. int c, l;
    19. cin >> c >> l;
    20. vector p;
    21. for(int i = 0; i < c; i++) {
    22. struct node tmp;
    23. cin >> tmp.min >> tmp.max;
    24. p.emplace_back(tmp);
    25. }
    26. sort(p.begin(), p.end(), cmp1);
    27. vector z;
    28. for(int i = 0; i < l; i++) {
    29. struct ss tmp;
    30. cin >> tmp.spf >> tmp.cov;
    31. z.emplace_back(tmp);
    32. }
    33. sort(z.begin(), z.end(), cmp2);
    34. int res = 0;
    35. for(int i = 0; i < c; i++) {
    36. for(int j = 0; j < l; j++) {
    37. if(z[j].spf >= p[i].min && z[j].spf <= p[i].max && z[j].cov >= 1) {
    38. res += 1, z[j].cov -= 1;
    39. break;
    40. }
    41. }
    42. }
    43. cout << res << endl;
    44. return 0;
    45. }

  • 相关阅读:
    setContextProperty qmlRegisterType qRegisterMetaType等区别
    Spring --- AOP 操作 - AspectJ注解
    反射的机制
    我如何使用工具学习网络技术?
    supOS APP开发者课程练习册
    这两款简洁好看的软件你确定不想要吗
    B站UP主发布视频,助力会员救园
    mfc 疑难杂症之一
    stable diffusion本地部署教程
    push apk到真机出现remote couldn‘t create file: Read-only file system
  • 原文地址:https://blog.csdn.net/Ls_attack/article/details/127876169