Codeforces Round #751 (Div. 2)
A. Two Subsequences
思路分析：
- x实际上就是字符串里最小的字符。
- 剩下的便是y。
代码
#include
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
string s;
cin >> s;
char ch = 'z';
int pos = 0;
for (int i = 0; i < s.size(); i++)
{
if (s[i] < ch)
{
pos = i;
ch = s[i];
}
}
cout << ch << ' ';
for (int i = 0; i < s.size(); i++)
{
if (i != pos)
{
cout << s[i];
}
}
cout << endl;
}
return 0;
}
B. Divine Array
思路分析：
- 这题我想复杂了，实际上不需要像我这么麻烦（比赛时的代码太复杂了，就不放了），因为不管怎么样，进行(1000)轮后都不会再进行改变。
- 所以我们对于每一个序列都操作1000次，然后储存答案，查询时间就是O(1)，当然，算法主体时间是O(1000 *(n^2))。
代码
#include
using namespace std;
const int maxn = 1000;
vector v[maxn];
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
for (int i = 1; i > x;
v[0].push_back(x);
}
int i;
for (i = 1;; i++)
{
int flag = 0;
for (int j = 0; j < n; j++)
{
int t = count(v[i - 1].begin(), v[i - 1].end(), v[i - 1][j]);
v[i].push_back(t);
if (v[i][j] != v[i - 1][j])
{
flag = 1;
}
}
if (!flag)
{
break;
}
}
int q;
cin >> q;
while (q--)
{
int a, b;
cin >> a >> b;
if (b >= i)
cout << v[i][a - 1] << endl;
else
cout << v[b][a - 1] << endl;
}
for (int j = 0; j
C. Array Elimination
思路分析：
- 这题一开始没想法，最后猜了一下按位做，然后推了一下，发现确实有道理就写上了。
- 首先，对于每一位，看有多少个(1)，如果有(n)个(1)的话，那么只要选择(n)的因子个当前位为(1)的数即可（假如是(3)，那么只能选(1)或者(3)，如果是(4)，那么只能选(1)，(2),(4)，对于其他的数也是这样的，推一下就可以知道），那么我们对于每一位都是这样的操作的话，那么我们只需要求每一位(1)的个数的gcd的因子即可。
- 证明如下：
代码
#include
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn];
int cnt[30];
int main()
{
int t = read();
while (t--)
{
for (int i = 0; i = 0; j--)
{
for (int i = 1; i > j) & 1)
{
cnt[j]++;
}
}
}
int gcd = 0;
for (int j = 30; j >= 0; j--)
{
gcd = __gcd(gcd, cnt[j]);
}
if (gcd == 0)
{
for (int i = 1; i ans;
for (int i = 1; i
D. Frog Traveler
思路分析：
- 这题没想到可以用BFS，因为我们要求最小步数，所以在每一轮中保证了步数是一致的，并且我们可以知道，不可能往后退。
- 所以是线性的，每个位置只走一遍，具体看代码注释。
代码
#include
using namespace std;
const int maxn = 3e5 + 10;
int a[maxn], b[maxn];
//题目给的
int minh, n;
//我们把上一轮最大高度记录一下
int pre[maxn];
//记录当前位置的前面一个位置
int dis[maxn];
//记录步数
int ans[maxn];
//记录当前位置前面位置的答案
int bfs()
{
queue q;
memset(pre, -1, sizeof(pre));
memset(dis, 0x3f, sizeof(dis));
memset(ans, 0, sizeof(ans));
q.push(n);
minh = n;
dis[n] = 0;
//初始化
while (!q.empty())
{
int h = q.front();
q.pop();
if (h == 0)
return dis[h];
//如果出现了0，那么直接return即可
for (int x = a[h]; x > 0; x--)
{
int now = h - x, temp = 0;
//now是指跳了x高的高度，temp用来储存跳完之后的高度
if (now >= minh)
{
break;
}
if (now > 0)
{
temp = now, now += b[now];
//now变成跳完之后掉下来的高度
}
else
now = 0;
if (dis[now] > dis[h] + 1)//如果当前高度之前没有枚举到
{
dis[now] = dis[h] + 1;
pre[now] = h;
//掉下来的高度的前驱为h
ans[now] = temp;
//掉下来的高度的前面位置的高度
q.push(now);
}
}
minh = min(minh, h - a[h]);
//更新最低高度
}
return -1;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i > a[i];
}
for (int i = 1; i > b[i];
}
minh = n;
cout << bfs() << endl;
stack s;
int x = 0;
while (pre[x] != -1)
{
s.push(x);
x = pre[x];
//找前驱
}
while (!s.empty())
{
int now = s.top();
cout << ans[now] << ' ';
s.pop();
}
cout << endl;
return 0;
}
Original: https://www.cnblogs.com/csu-yuuki/p/15496350.html
Author: zhy-cx
Title: Codeforces Round #751 (Div. 2)
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/713466/
转载文章受原作者版权保护。转载请注明原作者出处！