Codeforces Round #751 (Div. 2)
A. Two Subsequences
思路分析：
- x實際上就是字串里最小的字符，
- 剩下的便是y，
代碼
#include <bits/stdc++.h>
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 <bits/stdc++.h>
using namespace std;
const int maxn = 1000;
vector<int> v[maxn];
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
int x;
cin >> 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 <= i; j++)
{
v[j].clear();
}
}
return 0;
}
C. Array Elimination
思路分析：
- 這題一開始沒想法，最后猜了一下按位做，然后推了一下，發現確實有道理就寫上了，
- 首先，對于每一位，看有多少個\(1\)，如果有\(n\)個\(1\)的話，那么只要選擇\(n\)的因子個當前位為\(1\)的數即可（假如是\(3\)，那么只能選\(1\)或者\(3\)，如果是\(4\)，那么只能選\(1\)，\(2\),\(4\)，對于其他的數也是這樣的，推一下就可以知道），那么我們對于每一位都是這樣的操作的話，那么我們只需要求每一位\(1\)的個數的gcd的因子即可，
- 證明如下：
代碼
#include <bits/stdc++.h>
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 <= 29; i++)
{
cnt[i] = 0;
}
int n = read();
for (int i = 1; i <= n; i++)
{
a[i] = read();
}
for (int j = 29; j >= 0; j--)
{
for (int i = 1; i <= n; i++)
{
if ((a[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 <= n; i++)
{
printf("%d ", i);
}
}
else
{
vector<int> ans;
for (int i = 1; i <= gcd; i++)
{
if (gcd % i == 0)
{
ans.push_back(i);
}
}
for (int i = 0; i < ans.size(); i++)
{
printf("%d ", ans[i]);
}
}
puts("");
}
return 0;
}
D. Frog Traveler
思路分析：
- 這題沒想到可以用BFS，因為我們要求最小步數，所以在每一輪中保證了步數是一致的，并且我們可以知道，不可能往后退，
- 所以是線性的，每個位置只走一遍，具體看代碼注釋，
代碼
#include <bits/stdc++.h>
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<int> 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 <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
{
cin >> b[i];
}
minh = n;
cout << bfs() << endl;
stack<int> 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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/343942.html
標籤：其他