携手创造，一起生长！这是我参加「日新计划 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的奇偶性来分类评论：
- 假如cnt为偶数，则阐明咱们能够直接将数组中的超级数均匀的放在两头的数组里，那么咱们能够直接找出cnt/2个只超级数，把它都设成a数组，再把剩余的数设成b数组。
- 假如cnt为奇数，且数组中稀有呈现两次以上，咱们能够从中拿出一个，在拿出cnt/2（向下取整）个超级数来组成a数组，剩余的悉数设成b即可。（咱们把呈现两次的数拿出一个放到a，那么这个数在a中就只呈现了一次，所以它就变成了一个超级数）;
- 假如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;
}
