A.Musical Puzzle
題意：
用最少的長度為2的字串按一定規則拼出s，規則是：前一個字串的尾與后一個字串的首相同，
分析：
統計s中長度為2的不同字串數量，
代碼：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
unordered_map<string, bool> mp;
int n;
cin >> n;
string s;
cin >> s;
int cnt = 0;
for (int i = 0; i < n - 1; i ++)
{
string s2 = s.substr(i, 2);
if (!mp[s2])
{
cnt ++;
mp[s2] = true;
}
}
cout << cnt << endl;
}
return 0;
}
B. Restore the Weather
題意：
給定陣列a[n]和b[n]，重排b后，令任意|ai?bi|≤k成立(1≤k≤n)資料保證一定有解，
分析：
將a和b分別按從小到大的順序匹配便是最優的，一定能滿足|ai?bi|≤k成立，只需注意要恢復原來的順序輸出，
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
struct Node
{
int id, v, v2;
}a[N];
int b[N];
bool cmp(Node A, Node B)
{
return A.v < B.v;
}
bool cmp2(Node A, Node B)
{
return A.id < B.id;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i ++)
{
a[i].id = i;
cin >> a[i].v;
}
for (int i = 0; i < n; i ++)
cin >> b[i];
sort(b, b + n);
sort(a, a + n, cmp);
for (int i = 0; i < n; i ++)
a[i].v2 = b[i];
sort(a, a + n, cmp2);
for (int i = 0; i < n; i ++)
cout << a[i].v2 << " ";
cout << endl;
}
return 0;
}
C. Vlad Building Beautiful Array
題意:
給定一個a序列，你要構造一個b序列：所有元素均為正數，且要么全是偶數要么全是奇數
構造的方式：令bi = ai - aj (1≤j≤n)
分析:
2只有減奇數才能改變奇偶性，值得注意的是，根據題目要求我們無法將一個奇數序列變成偶數序列，因此只有以下三種情況：
①原本全是奇數
②原本全是偶數
③有奇有偶：這時只能將偶序列變成奇序列，我們將每一個偶數與最小的奇數消減，只要最后的結果全為正數則有解，否則無解，
代碼:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5;
int a[N];
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n;
cin >> n;
bool check = false;
for (int i = 0; i < n; i ++)
cin >> a[i];
int cnt1 = 0, min_odd = 0x3f3f3f3f;
for (int i = 0; i < n; i ++)
{
if (a[i] & 1)
{
cnt1 ++;
min_odd = min(min_odd, a[i]);
}
}
if (cnt1 == 0 || cnt1 == n)
{
check = true;
}
if (!check)
{
bool flag = true;
for (int i = 0; i < n; i ++)
{
if (a[i] % 2 == 0 && a[i] <= min_odd)
{
flag = false;
break;
}
}
check = flag;
}
if (check)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}
D. Flipper
題意:
分析：
在解空間中，以n/n-1開頭的排列字典序比其他可行解大，因此最優解在以n/n-1開頭的解空間里，
所以本題右端點是固定的，若元素n不在開頭，則r在元素n所在的位置，若n在開頭，則r在元素n - 1所在的位置，
固定了r后我們再去列舉左端點l，在所有可行解中取字典序最大的那個排列即可，
代碼：
#include <bits/stdc++.h>
using namespace std;
vector<int> a;
int n;
vector<int> get(int l, int r)
{
vector<int> res(n);
int m = 0;
for (int i = r + 1; i < n; i ++)
res[m ++] = a[i];
for (int i = r; i >= l; i --)
res[m ++] = a[i];
for (int i = 0; i < l; i ++)
res[m ++] = a[i];
return res;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
cin >> n;
a.resize(n, 0);
vector<int> res(n, 0);
for (int i = 0; i < n; i ++)
cin >> a[i];
int r;
for (int i = 0; i < n; i ++)
{
if (a[i] == n)
{
r = i;
break;
}
}
if (r == 0)
{
for (int i = 0; i < n; i ++)
{
if (a[i] == n - 1)
{
r = i;
break;
}
}
}
if (r != n - 1)
r --;
for (int i = 0; i <= r; i ++)
{
auto tmp = get(i, r);
if (tmp > res)
res = tmp;
}
for (int i = 0; i < n; i ++)
cout << res[i] << " ";
cout << endl;
}
return 0;
}
E. Round Dance
題意:
給定一個序列a[n]，這個序列描述的是，編號為i(1<=i<=n)的節點與編號為a[i]的節點之間有一條無向邊，問能構造出的聯通塊最少是多少和能構造出的連通塊最多是多少？
分析:
最多的連通塊數便是不加任何操作，當前圖的連通塊數，
要構造出最少的連通塊，我們可以將那些不存在環的連通塊合并在一起拉成一條鏈，
因此我們可以統計出當前圖中，連通塊的數量m1，存在環的連通塊的數量m2，則最少的連通塊的數量為m2 + 1，最多的連通塊的數量為m1
統計連通塊的數量有很多方法，這里用的是dfs，建圖時要處理重邊，map處理二元元素比較麻煩，可以采用將兩個int變數哈希成一個long long值的方式來處理：value = https://www.cnblogs.com/scoxty/p/((LL)a << 32) + (LL)b
代碼：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e6 + 5, M = 4e6 + 5;
int h[N], e[M], ne[M], idx;
bool st[N];
int m1, m2;
bool flag;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u, int fa)
{
st[u] = true;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (j != fa)
{
if (st[j])
{
flag = true;
}
else
dfs(j, u);
}
}
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n;
cin >> n;
for (int i = 1; i <= n; i ++)
h[i] = -1;
idx = m1 = m2 = 0;
unordered_map<LL, bool> mp;
for (int i = 1; i <= n; i ++)
{
st[i] = false;
int j;
cin >> j;
LL H = ((LL)i << 32) + (LL)j, H2 = ((LL)j << 32) + (LL)i;
if (!mp[H] && !mp[H2])
{
add(i, j), add(j, i);
mp[H] = mp[H2] = true;
}
}
for (int i = 1; i <= n; i ++)
{
if (!st[i])
{
flag = false;
dfs(i, -1);
if (flag)
m2 ++;
m1 ++;
}
}
if (m2 < m1)
cout << m2 + 1 << " " << m1 << endl;
else
cout << m1 << " " << m1 << endl;
}
return 0;
}
F. Ira and Flamenco
題意：
給定一個a序列，求優美子序列總數對1e9 + 7取模的結果，優美子序列應滿足：
子序列的大小為m
子序列中的元素各不相同
子序列中任意兩個元素差的絕對值嚴格小于m
分析：
我們不妨先從小到大將其排個序，記錄每個元素的個數并去重，子序列abcd出現的次數即子序列中每個元素出現次數的累乘，由于每個元素各不相同，因此任意兩個元素至少相差1，所以我們選擇的方案在排序去重后實際上時連續的，因此我們可以維護一個前綴積，在新序列里列舉長度為m的連續序列，只要最大值與最小值差的絕對值小于m則統計，
代碼：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
LL qmi(LL m, LL k)
{
LL res = 1, t = m;
while (k)
{
if (k & 1)
res = res * t % mod;
t = t * t % mod;
k >>= 1;
}
return res;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n, m;
cin >> n >> m;
vector<int> a(n + 1);
vector<LL> f(n + 1);
unordered_map<int, int> mp;
for (int i = 1; i <= n; i ++)
{
cin >> a[i];
mp[a[i]] ++;
}
sort(a.begin() + 1, a.begin() + n + 1);
a.erase(unique(a.begin() + 1, a.end()), a.end());
f[0] = 1;
for (int i = 1; i < a.size(); i ++)
f[i] = f[i - 1] * mp[a[i]] % mod;
LL res = 0;
for (int i = m; i < a.size(); i ++)
{
if (a[i] - a[i - m + 1] < m)
{
res = (res + f[i] * qmi(f[i - m], mod - 2) % mod) % mod;
}
}
cout << res << endl;
}
return 0;
}
G. Ksyusha and Chinchilla
題意：
給定一個含有n個頂點的樹，求一個合法的刪邊方案保證刪完這些邊后為若干個長度為3的鏈，輸出合法的刪邊方案或告訴這是不可能的，
分析：
我們可以自下向上去維護子樹的節點總數，合法的情況只有：
倘若當前子樹節點總數為3，則將其與父節點的邊砍掉并記錄，
代碼：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5, M = 4e5 + 5;
int h[N], e[M], ne[M], idx;
int k;
LL res[N];
bool check;
bool cut[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int dfs(int u, int fa)
{
int cnt = 1;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (j != fa)
{
cnt += dfs(j, u);
if (cut[j])
res[k ++] = ((LL)u << 32) + (LL)j;
}
}
if (cnt > 3)
{
check = true;
return 0;
}
else if (cnt == 3 && u != 1)
{
cut[u] = true;
return 0;
}
return cnt;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n;
cin >> n;
memset(h, -1, sizeof h);
memset(cut, false, sizeof cut);
idx = k = 0;
check = false;
unordered_map<LL, int> mp;
for (int i = 1; i < n; i ++)
{
int a, b;
cin >> a >> b;
LL H1 = ((LL)a << 32) + (LL)b, H2 = ((LL)b << 32) + (LL)a;
mp[H1] = mp[H2] = i;
add(a, b), add(b, a);
}
int remain = dfs(1, -1);
if (check || remain != 3)
cout << -1 << endl;
else
{
cout << k << endl;
if (k == 0)
cout << " " << endl;
else
{
for (int i = 0; i < k; i ++)
{
cout << mp[res[i]] << " ";
}
cout << endl;
}
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/552977.html
標籤：其他
上一篇：CodeForces1061C Multiplicity
下一篇：返回列表