A:Diverse Strings
题意
给定n个字符串，判断每个字符串是否恰好由连续且不重复的字母组成。
关键词
字符串、排序、去重。
思路
对字符串去重再排序，如果处理后的长度没变且最后一个字符与第一个字符恰好相差len-1（字符串长度），则输出YES，否则输出NO。
代码
#include <bits/stdc++.h>
#define Debug 0
#define MAXN 1000056
#define MAXM 2600
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
bool tag[MAXN];
int main ()
{
#ifdef FILE_IN
freopen(FILE_IN, "r", stdin);
#endif
// SYNC
int n;
cin>>n;
for (int i = 0; i < n; ++i)
{
string s;
cin>>s;
memset(tag, 0, sizeof(tag));
bool ans = 1;
sort(s.begin(),s.end());
int r = unique(s.begin(),s.end())-s.begin();
if (r == s.length()&& s.back()-s[0] == s.length()-1)
ans = 1;
else ans = 0;
if(ans)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
#ifdef FILE_IN
fclose(stdin);
#endif
return 0;
}
B:Parity Alternated Deletions
题意
给n个正整数，在其中交替删除奇偶数，再无法继续删除后，求剩下的数之和最小是多少。
关键词
奇偶、排序。
思路
把奇数和偶数分开储存并排序，算出其数量之差cnt，在数量多那个序列中取最小的前cnt-1个数之和。
代码
#include <bits/stdc++.h>
#define Debug 0
#define MAXN 1000056
#define MAXM 2600
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int arr[MAXN];
int main ()
{
#ifdef FILE_IN
freopen(FILE_IN, "r", stdin);
#endif
// SYNC
int n;
cin >> n;
int x = 0, y = 0;
int xx = INT_MAX, yy = INT_MAX;
vector<int> xxx,yyy;
int ans = 0;
for (int i = 0; i < n; ++i)
{
cin >> arr[i];
if (arr[i] & 1)
{
x++;
xx = min(xx, arr[i]);
xxx.push_back(arr[i]);
} else
{
y++;
yy = min(yy, arr[i]);
yyy.push_back(arr[i]);
}
}
int cnt = abs(x - y);
if (cnt <= 1)
ans = 0;
else
{
cnt -= 1;
if(x>y)
{
sort(xxx.begin(), xxx.end());
ans = accumulate(xxx.begin(), xxx.begin()+cnt, 0);
} else{
sort(yyy.begin(), yyy.end());
ans = accumulate(yyy.begin(), yyy.begin()+cnt, 0);
}
}
cout << ans << endl;
#ifdef FILE_IN
fclose(stdin);
#endif
return 0;
}
C:Two Shuffled Sequences
题意
给n个数，如果能拆分成一个绝对升序（不含相等元素）的序列和一个绝对降序的序列，则输出YES和这两个序列，否则输出NO。
关键词
排序，去重。
思路
开两个标记数组标记是否在升序、降序序列中出现过，如果没在升序序列出现，则加入升序序列，否则再判断有没有存在于降序序列中，如果没存在，则加入降序序列，否则不放入这两个序列。
比较两个序列中元素数量之和是否等于n，等于，则有解，对这两个序列按照升序、降序排序后输出，否则无解。
代码
#include <bits/stdc++.h>
#define Debug 0
#define MAXN 1000056
#define MAXM 2600
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int arr[MAXN];
int vis[MAXN] = {0};
int vis2[MAXN] = {0};
int main ()
{
#ifdef FILE_IN
freopen(FILE_IN, "r", stdin);
#endif
// SYNC
int n;
cin >> n;
vector<int> a, b;
bool tag = 1;
for (int i = 0; i < n; ++i)
{
cin >> arr[i];
if (!vis[arr[i]])
{
a.push_back(arr[i]);
vis[arr[i]] = 1;
} else if (!vis2[arr[i]])
{
b.push_back(arr[i]);
vis2[arr[i]] = 1;
}
}
if (a.size() + b.size() != n)
tag = 0;
if (tag)
{
cout << "YES" << endl;
sort(a.begin(), a.end());
cout << a.size() << endl;
for (int i = 0; i < a.size(); ++i)
{
if (i)
cout << " ";
cout << a[i];
}
cout << endl;
cout << b.size() << endl;
sort(b.begin(), b.end(), greater<int>());
for (int i = 0; i < b.size(); ++i)
{
if (i)
cout << " ";
cout << b[i];
}
cout << endl;
} else
cout << "NO" << endl;
#ifdef FILE_IN
fclose(stdin);
#endif
return 0;
}
D:Equalize Them All
题意
给定包含n个数的序列，每一次操作可以把一个数变成相邻的数，问最少需要多少次操作才能把这个序列变成同一个数，输出操作步骤。
关键词
众数、搜索、贪心。
思路
找到序列中的众数（出现次数最多的数）。
假设众数有k个，则要将所有数字都变成众数需要的操作数量最少，为n-k次：每次都将众数左右两边的数变成众数即可，类似于BFS。
将这些众数的位置存入队列中，用类似于BFS的方式去处理并记录操作。
代码
#include <bits/stdc++.h>
#define Debug 0
#define MAXN 1000056
#define MAXM 2600
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int arr[MAXN];
int vis[MAXN] = {0};
int cnt[MAXN] = {0};
int tot = 0;
int ans[MAXN][3];
int main ()
{
#ifdef FILE_IN
freopen(FILE_IN, "r", stdin);
#endif
// SYNC
int n;
cin >> n;
int m_cnt = 0;
int m_num = 0;
for (int i = 0; i < n; ++i)
{
cin >> arr[i];
cnt[arr[i]]++;
if (cnt[arr[i]] > m_cnt)
{
m_cnt = cnt[arr[i]];
m_num = arr[i];
}
}
queue<int> q;
for (int i = 0; i < n; ++i)
{
if (arr[i] == m_num)
{
q.push(i);
vis[i] = 1;
}
}
while (!q.empty())
{
int cur = q.front();
q.pop();
if (cur > 0 && !vis[cur - 1] )
{
q.push(cur - 1);
ans[tot][0] = arr[cur - 1] < m_num ? 1 : 2;
ans[tot][1] = cur - 1;
ans[tot++][2] = cur;
vis[cur-1] = 1;
}
if (cur < n - 1 && !vis[cur + 1])
{
q.push(cur + 1);
ans[tot][0] = arr[cur + 1] < m_num ? 1 : 2;
ans[tot][1] = cur + 1;
ans[tot++][2] = cur;
vis[cur+1] = 1;
}
}
cout<<tot<<endl;
for (int i = 0; i <tot; ++i)
{
printf("%d %d %d\n",ans[i][0], ans[i][1]+1 ,1+ans[i][2]);
}
#ifdef FILE_IN
fclose(stdin);
#endif
return 0;
}
E:Median String
题意
给一个整数n，给出2个长度为n的字符串，求按照字典序在这两个字符串之间的字符串。
关键词
26进制、字典序、数论
思路
先做加法，再求平均。
设连个字符串为a、b。
数a可表示为：a0⋅261+a2⋅26n-2+……+an-1⋅260，b同理。
加法，从最低位开始：
相加：sumi-1+=ai-1+bi-1
进位：sumi-2+=sumi-1/26
求余：sumi-1%=26
除2，从最高位开始：
模二：r = sumi%2
除二：sumi/=2
退位：sumi+1+=r*26
代码
#include <bits/stdc++.h>
#define Debug 0
#define MAXN 200056
#define MAXM 2600
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int sum[MAXN] = {0};
int main ()
{
#ifdef FILE_IN
freopen(FILE_IN, "r", stdin);
#endif
// SYNC
int n;
cin >> n;
string s1, s2;
cin >> s1 >> s2;
for (int i = n; i >= 0; --i)
{
int t = 0;
if(i>0)
t=(s1[i-1] - 'a') + (s2[i-1] - 'a');
sum[i] += t;
if(i)
{
sum[i-1] += sum[i] / 26;
sum[i] %= 26;
}
}
for (int i = 0; i <= n; ++i)
{
int r = sum[i] % 2;
sum[i] /= 2;
if (i < n)
sum[i + 1] += 26 * r;
}
for (int i = 0; i <= n; ++i)
{
if (i == 0 && sum[i] == 0)
continue;
else
cout << (char) (sum[i] + 'a');
}
cout << endl;
#ifdef FILE_IN
fclose(stdin);
#endif
return 0;
}
F:Graph Without Long Directed Paths
题意
给一个由n个点、m条边组成的无图，问是否能给边加上方向，让整个图不存在长度超过一的路径。
关键词
DFS、图染色
思路
要没有长度超过1的路径，在这个图中只有2种点：一种入度为0、一种出度为0，且同一种点不能相邻出现。
就是一个图染色问题，能否用两种颜色对图染色。直接DFS即可。
代码
#include <bits/stdc++.h>
#define Debug 0
#define MAXN 1000056
#define MAXM 2600
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int n, m;
int vis[MAXN] = {0};
vector<Pair> G[MAXN];
int in[MAXN];
int ans[MAXN] = {0};
int tag = 1;
vector<Pair> edges;
void addedge (int a, int b, int i)
{
G[a].pb(Pair(b, i));
G[b].pb(Pair(a, i));
edges.pb(Pair(a, b));
}
void dfs (int u, int _in)
{
if (!tag)
return;
vis[u] = 1;
in[u] = _in;
for (int i = 0; i < G[u].size(); ++i)
{
int v = G[u][i].first;
int index = G[u][i].second;
if (in[v] == -1)
{
dfs(v, 1 - _in);
} else if (in[u] == in[v])
{
tag = 0;
return;
}
}
}
int main ()
{
#ifdef FILE_IN
freopen(FILE_IN, "r", stdin);
#endif
// SYNC
cin >> n >> m;
memset(in, -1, sizeof(in));
for (int i = 0; i < m; ++i)
{
int a, b;
cin >> a >> b;
addedge(a, b, i);
}
dfs(1, 0);
if (tag)
{
cout << "YES" << endl;
for (int i = 0; i < m; ++i)
{
int u = edges[i].first;
int v = edges[i].second;
cout << (in[u]<in[v]);
}
cout << endl;
} else
{
cout << "NO" << endl;
}
#ifdef FILE_IN
fclose(stdin);
#endif
return 0;
}
G:Two Merged Sequences
题意
这道题题意和C题类似，区别就是，在C题中，可以对数组中的数重新排序，而在这题中，要求保持数组中给的顺序。
关键词
贪心、DP
思路
贪心思路：
考虑x和y两个点
如图，贪心的思路，就是让升序序列与降序序列之间，能插入数的范围尽可能大，即能保证尽可能多的数能被插入到两个序列之中，可以求出最优解。
假设维护一个升序序列、一个降序序列，对于当前的待处理的数x以及下一个数y，使用贪心思想分析以下几种情况：
- x即能加入升序序列，又能加入降序序列：如果y>x，则把x加入降序序列，那么y就只能加入升序序列，此时的情况，显然比把x加入升序序列更糟糕。故y>x的情况下，把x加入升序序列，否则加入降序序列。如果x为最后一个元素，则加入哪个序列都行。
- x只能加入其中一个序列：直接加入。
- 两个序列都无法加入：此时无解。
代码
#include <bits/stdc++.h>
#define Debug 0
#define MAXN 200056
#define MAXM 2600
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int arr[MAXN];
vector<int> inc, des;
int ans[MAXN] = {0};
int main ()
{
#ifdef FILE_IN
freopen(FILE_IN, "r", stdin);
#endif
// SYNC
int n;
cin >> n;
bool tag = 1;
for (int i = 0; i < n; i++)
cin >> arr[i];
for (int i = 0; i < n; ++i)
{
if ((inc.empty() && des.empty()) ||
(inc.empty() && arr[i] < des.back()) ||
(des.empty() && arr[i] > inc.back()) ||
(arr[i] > inc.back() && arr[i] < des.back()))
{
if (i < n - 1)
{
if (arr[i + 1] > arr[i])
{
inc.pb(arr[i]);
} else if (des.empty() || arr[i + 1] < des.back())
{
des.pb(arr[i]);
ans[i] = 1;
} else
{
tag = 0;
break;
}
}
} else if (inc.empty() || arr[i] > inc.back())
{
inc.pb(arr[i]);
} else if (des.empty() || arr[i] < des.back())
{
des.pb(arr[i]);
ans[i] = 1;
} else
{
tag = 0;
break;
}
}
if (tag)
{
cout << "YES" << endl;
for (int i = 0; i < n; ++i)
{
cout << ans[i] << (i == n - 1 ? '\n' : ' ');
}
} else
{
cout << "NO" << endl;
}
#ifdef FILE_IN
fclose(stdin);
#endif
return 0;
}
