携手创造,一起生长!这是我参加「日新计划 8 月更文挑战」的第30天,点击检查活动概况

AcWing:第66场周赛

4606. 奇偶判别

问题解析

虽然是16进制,可是题目让咱们看的是转成10进制后的最终一位数,那么实际上咱们只用看16进制下的最终一位数,由于16进制下的最终一位数才是决议奇偶性的,前面的数只是决议数得大小。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>//#pragma GCC optimize(3)#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 1e5 + 50, MOD = 1e11 + 3;
​
void solve()
{
   string s;
   cin >> s;
   int n = s.size() - 1;
   if ((s[n] - '0') & 1) cout << 1 << endl;
   else cout << 0 << endl;
​
}
​
signed main()
{
​
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cout.tie(nullptr);
   int t = 1;
   while (t--)
   {
     solve();
   }
   return 0;
}

AcWing 4607. 字母补全

问题解析

前置常识:滑动窗口

首先,假如字符串s的长度小于26,那么肯定是契合条件的,直接输出-1.

然后咱们维护一个长度为26的滑动窗口,初始下标是:0~25。

记载每次滑动窗口中每个字符的呈现次数,假如有哪个字符呈现了两次及以上,那么肯定是不契合条件的。由于咱们长度一共是26,要想每个字符都呈现一次,那么肯定每个字符只能呈现1次。

假如滑动窗口中所有字符都只呈现了一次,那么阐明这个滑动窗口便是契合条件的子串,咱们记载下没有呈现过的字符,然后将它们放在窗口中’?’字符的方位上。假如窗口之外的当地还有问号字符,将他们都变成恣意的字母即可(我这里是全变成’A’.

假如没有一个窗口是契合条件的,阐明这个字符串不合格,咱们输出-1.

时刻复杂度

滑动窗口一共会跑n-25次,每次跑26的长度,时刻复杂度O(n*26)

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>//#pragma GCC optimize(3)#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 1e5 + 50, MOD = 1e11 + 3;
​
int mymap[26];
void solve()
{
   string s;
   cin >> s;
   int n = s.size();
   if (n < 26)
   {
     cout << -1 << endl;
     return;
   }
   int l = 0, r = 25;
   for (int i = 0; i < 26; i++)
   {
     if (s[i] != '?')
       mymap[s[i]-'A']++;
   }
   //看是否有合格的窗口呈现过
   bool st = false;
   while (r < n)
   {
     vector<char>v;
     //判别当时窗口是否契合条件
     bool flag = true;
     for (int i = 0; i < 26; i++)
     {
       if (mymap[i] > 1)
       {
         //不契合,停止遍历
         flag = false;
         break;
       }
       //记载下没呈现过的字符
       else if (mymap[i] == 0)
       {
         v.push_back(i + 'A');
       }
     }
     //假如当时窗口契合条件
     if (flag)
     {
       int ans = 0;
       //将记载在v数组中的未呈现字符替换掉窗口中的问号字符
       for (int i = l; i <= r; i++)
       {
         if (s[i] == '?')s[i] = v[ans++];
       }
       st = true;
       break;
     }
     //当时窗口不契合条件,持续移动
     else
     {
       mymap[s[l] - 'A']--;
       r++;
       mymap[s[r] - 'A']++;
       l++;
​
     }
   }
   //假如有契合的窗口,咱们把剩余的问号随机赋值成恣意字母
   if (st)
   {
     for (int i = 0; i < n; i++)
       if (s[i] == '?')s[i] = 'A';
     cout << s << endl;
   }
   else cout << -1 << endl;
}
​
signed main()
{
​
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cout.tie(nullptr);
   int t = 1;
   while (t--)
   {
     solve();
   }
   return 0;
}

4608. 整数分组

问题解析

题目是让咱们把数组分红两份,使得两头的数组中只呈现一次的数的个数相等。

咱们能够先遍历一遍数组,记载所稀有的呈现次数,且记载下只呈现一次的数的个数cnt,然后咱们根据cnt的奇偶性来分类评论:

  1. 假如cnt为偶数,则阐明咱们能够直接将数组中的超级数均匀的放在两头的数组里,那么咱们能够直接找出cnt/2个只超级数,把它都设成a数组,再把剩余的数设成b数组。
  2. 假如cnt为奇数,且数组中稀有呈现两次以上,咱们能够从中拿出一个,在拿出cnt/2(向下取整)个超级数来组成a数组,剩余的悉数设成b即可。(咱们把呈现两次的数拿出一个放到a,那么这个数在a中就只呈现了一次,所以它就变成了一个超级数);
  3. 假如cnt为奇数,且数组中没稀有呈现两次以上,咱们就无法将超级数均匀分配,由于此时数组中的数只有两种状况:呈现了一次、呈现了两次。呈现一次的便是咱们的超级数,他们的呈现次数是cnt,而假如咱们想通过分类评论2的办法,从呈现两次的数中拿出一个数放在a里,那么这个数不仅在a中变成了超级数,在b中也变成了超级数,相当于cnt+2,此时cnt仍是奇数,无法均匀分配。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>//#pragma GCC optimize(3)#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 1e5 + 50, MOD = 1e11 + 3;
​
//记载每个数的呈现次数
unordered_map<int, int>mymap;
void solve()
{
   int n;
   cin >> n;
   vector<int>v(n);
   int cnt = 0;
   for (int i = 0; i < n; i++)
   {
     cin >> v[i];
     mymap[v[i]]++;
     //记载呈现了一次的数,即记载超级数
     if (mymap[v[i]] == 1)cnt++;
     //假如这个数呈现了两次,则它不是超级数了
     else if (mymap[v[i]] == 2)cnt--;
   }
   string s;
   //假如超级数是偶数
   if (cnt % 2 == 0)
   {
     //咱们把一半的超级数变成a数组
     int x = cnt / 2;
     for (int i = 0; i < n; i++)
     {
       if (x != 0 && mymap[v[i]] == 1)
       {
         s += 'A';
         x--;
       }
       else s += 'B';
     }
     cout<<"YES"<<endl;
     cout << s << endl;
   }
   else
   {
     //num记载恣意一个呈现了两次以上的数
     int num = -1;
     for (auto i : mymap)
     {
       if (i.second > 2)
       {
         num = i.first;
         break;
       }
     }
     //假如没有,输出no
     if (num == -1)
     {
       cout << "NO" << endl;
     }
     else
     {
       //假如有,则仿照上面的操作
       int x = cnt / 2, pos = 0;
       for (int i = 0; i < n; i++)
       {
​
         if (x != 0 && mymap[v[i]] == 1)
         {
           s += 'A';
           x--;
         }
         //假如呈现了咱们记载的数,把它变成a数组的
         else if (num != -1 && num == v[i])
         {
           //只变这一次,变完后把num从头变成-1
           num = -1;
           s += 'A';
         }
         else s += 'B';
       }
       while (s.size() < n)s += 'B';
       cout<<"YES"<<endl;
       cout << s << endl;
     }
   }
}
​
signed main()
{
​
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cout.tie(nullptr);
   int t = 1;
   while (t--)
   {
     solve();
   }
   return 0;
}