杭州做网站的优质公司哪家好/承德网络推广

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;}}//如果没有，输出noif (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重新变成-1num = -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;
}