A. Diverse Strings
非法情况：某个字符出现超过一次或者出现的字母不连续.
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
int n;
string str;
int main()
{
IOS;
int __;
cin >> __;
while(__ -- )
{
cin >> str;
map<char, int> mp;
for(int i = 0; i < (int)str.size(); ++ i) mp[str[i]] ++;
int flag = 0;
vector<int> v;
for(auto x : mp)
{
if(x.second > 1) flag = 1;
v.push_back((int)x.first);
}
sort(v.begin(), v.end());
for(int i = 1; i < (int)v.size(); ++ i)
if(v[i] - v[i - 1] != 1) flag = 1;
if(!flag) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
B. Parity Alternated Deletions
假设奇数个数和偶数个数分别为(x)和(y)，答案即为数量较多的一组中的最小的(abs(y - x) - 1)项的和.
#include <bits/stdc++.h>
using namespace std;
int n;
int main()
{
scanf("%d", &n);
std::vector<int> v1, v2;
for(int i = 1; i <= n; ++ i)
{
int x; scanf("%d", &x);
if(x % 2) v1.push_back(x);
else v2.push_back(x);
}
sort(v1.begin(), v1.end(), greater<int>());
sort(v2.begin(), v2.end(), greater<int>());
int res = 0;
if(v1.size() > v2.size() + 1)
for(int i = (int)v2.size() + 1; i < (int)v1.size(); ++ i)
res += v1[i];
else if(v2.size() > v1.size() + 1)
for(int i = (int)v1.size() + 1; i < (int)v2.size(); ++ i)
res += v2[i];
printf("%d
", res);
return 0;
}
C. Two Shuffled Sequences
某个数字出现次数大于2不合法，对于合法情况：排序后，只出现一次的全放入同一个序列中，出现两次的分别放入两个序列中，一个正序输出，一个倒序输出即可.
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
const int N = 2e5 + 20;
int n, a[N];
int main()
{
IOS;
cin >> n;
map<int, int> mp;
for(int i = 1; i <= n; ++ i)
{
cin >> a[i];
mp[a[i]] ++;
}
for(auto x : mp)
if(x.second > 2)
{
cout << "NO" << endl;
return 0;
}
cout << "YES" << endl;
sort(a + 1, a + n + 1);
vector<int> v1, v2;
v1.push_back(a[1]);
for(int i = 2; i <= n; ++ i)
if(a[i] == a[i - 1]) v2.push_back(a[i]);
else v1.push_back(a[i]);
cout << (int)v1.size() << endl;
for(int i = 0; i < (int)v1.size(); ++ i)
cout << v1[i] << ' ';
cout << endl;
cout << (int)v2.size() << endl;
for(int i = (int)v2.size() - 1; i >= 0; -- i)
cout << v2[i] << ' ';
cout << endl;
return 0;
}
D. Equalize Them All
找到出现最多的数字和它的某一个出现位置，然后向左向右扩展，把所有数字都改成出现最多的数字即可.
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
const int N = 2e5 + 20;
int n, a[N];
int main()
{
IOS;
cin >> n;
map<int, int> mp;
int id = 0, pos;
for(int i = 1; i <= n; ++ i)
{
cin >> a[i];
mp[a[i]] ++;
if(mp[a[i]] >= mp[id])
{
id = a[i];
pos = i;
}
}
cout << n - mp[id] << endl;
for(int i = pos - 1; i >= 1; -- i)
{
if(a[i] == id) continue;
if(a[i] > a[i + 1])
cout << "2 " << i << " " << i + 1 << endl;
else cout << "1 " << i << " " << i + 1 << endl;
a[i] = id;
}
for(int i = pos + 1; i <= n; ++ i)
{
if(a[i] == id) continue;
if(a[i] > a[i - 1])
cout << "2 " << i << " " << i - 1 << endl;
else cout << "1 " << i << " " << i - 1 << endl;
a[i] = id;
}
return 0;
}
E. Median String
二十六进制下做加法和除2.
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
int n;
string a, b;
int main()
{
IOS;
cin >> n;
cin >> a >> b;
std::vector<int> v;
int t = 0;
for(int i = a.size() - 1; i >= 0; -- i)
{
v.push_back((b[i] - 'a' + a[i] - 'a' + t) % 26);
t = (b[i] - 'a' + a[i] - 'a' + t) / 26;
}
v[v.size() - 1] += 26 * t;
for(int i = (int)v.size() - 1; i >= 0; -- i)
{
if(v[i] % 2 && i - 1 >= 0) v[i - 1] += 26;
v[i] /= 2;
}
for(int i = (int)v.size() - 1; i >= 0; -- i)
printf("%c", v[i] + 'a');
puts("");
return 0;
}
F. Graph Without Long Directed Paths
给每个点标记成入点和出点，相邻的点不能都是入点，也不能都是出点，然后对于输入的边，判断是否和出点到入点的方向相同即可.
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
const int N = 2e5 + 20;
int n, m;
int id[N], fist[N], idx;
struct Edge
{
int to, nxt;
}line[N * 2];
void add(int x, int y)
{
line[idx] = (Edge){y, fist[x]};
fist[x] = idx ++;
}
bool bfs()
{
queue<int> q;
q.push(1);
id[1] = 0;
while(!q.empty())
{
int u = q.front(); q.pop();
for(int i = fist[u]; i != -1; i = line[i].nxt)
{
int v = line[i].to;
if(id[u] == id[v]) return 0;
if(id[v] == -1) id[v] = (id[u] ^ 1), q.push(v);
}
}
return 1;
}
int main()
{
memset(fist, -1, sizeof fist);
memset(id, -1, sizeof fist);
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++ i)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
add(b, a);
}
if(bfs())
{
puts("YES");
for(int i = 0; i < idx; i += 2)
{
if(id[line[i].to] == 1 && id[line[i ^ 1].to] == 0) printf("0");
else printf("1");
}
puts("");
}
else puts("NO");
return 0;
}
G. Two Merged Sequences
维护一个递增，一个递减序列，判断当前元素可以放入哪个序列，如果只能放入一个序列，则放入该序列，如果放入两个序列都可以，则看下一个元素，如果下一个元素比当前元素大，则把这个元素放入递增序列，这样弱化了这个元素的作用，对后面的影响小，同理，如果下一个元素比当前元素小，则放入递减序列.
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 20;
int n, a[N];
int main()
{
std::vector<int> res;
int up = -1, down = INF;
IOS;
cin >> n;
for(int i = 1; i <= n; ++ i) cin >> a[i];
for(int i = 1; i <= n; ++ i)
{
if(a[i] <= up && a[i] >= down) { cout << "NO" << endl; return 0; }
if(a[i] > up && a[i] < down)
{
if(i + 1 <= n)
{
if(a[i + 1] == a[i])
{
up = a[i];
down = a[i];
res.push_back(0);
res.push_back(1);
i ++;
}
else if(a[i + 1] > a[i])
{
up = a[i];
res.push_back(0);
}
else if(a[i + 1] < a[i])
{
down = a[i];
res.push_back(1);
}
}
else res.push_back(0);
}
else if(a[i] > up)
{
up = a[i];
res.push_back(0);
}
else if(a[i] < down)
{
down = a[i];
res.push_back(1);
}
}
cout << "YES" << endl;
for(auto x: res) cout << x << " ";
cout << endl;
return 0;
}
2021.1.11