Codeforces Round #686 (Div. 3)
A. Special Permutation
Solution：
偶数直接倒序，奇数将前(n - 1)个倒序，最后将1和n互换位置。
Code：
#include <iostream>
using namespace std;
int main()
{
int t; cin >> t;
while(t--) {
int n; cin >> n;
if(n & 1) {
for(int i = n - 1; i >= 2; --i) cout << i << " ";
cout << n << " " << 1 << endl;
}
else {
for(int i = n; i >= 1; --i) cout << i << " ";
cout << endl;
}
}
return 0;
}
B. Unique Bid Auction
Solution：
模拟即可
Code：
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 211111;
int vis[maxn], n, a[maxn];
int main()
{
int t; cin >> t;
while(t--) {
memset(vis, 0, sizeof(vis));
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
vis[a[i]]++;
}
int ans = -1, mid = n + 1;
for(int i = 1; i <= n; ++i) {
if(vis[a[i]] == 1) {
if(a[i] < mid) {
mid = a[i];
ans = i;
}
}
}
cout << ans << endl;
}
return 0;
}
C. Sequence Transformation
Solution：
先对数列去重，之后判断每个数字将数列分成几段即可
Code：
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 211111;
int a[maxn], n;
vector<int> wh[maxn];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t; cin >> t;
while(t--) {
for(int i = 0; i <= n; ++i) wh[i].clear();
cin >> n;
int ans = n;
for(int i = 0; i < n; ++i) cin >> a[i];
int len = int(unique(a, a + n) - a);
for(int i = 0; i < len; ++i) {
wh[a[i]].push_back(i);
}
for(int i = 1; i <= n; ++i) {
if(wh[i].size()) {
int k = wh[i].size() + 1;
if(wh[i][0] == 0) k--;
if(wh[i].back() == len - 1) k--;
ans = min(ans, k);
}
}
cout << ans << endl;
}
return 0;
}
D. Number into Sequence
Solution：
DFS搜索因数即可。
Code：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll ans, n;
ll arry[111], mid[111];
void dfs(ll lft, ll k, ll la)
{
// cout << lft << " " << k << " " << la << endl;
if(lft % la == 0) {
mid[k] = lft;
if(k + 1 > ans) {
ans = k + 1;
for(int i = 0; i < ans; ++i) {
arry[i] = mid[i];
}
}
}
for(ll i = la; i * i <= lft; i += la) {
if(lft % i == 0 && i > 1) {
mid[k] = i;
dfs(lft / i, k + 1, i);
}
}
return;
}
int main()
{
int t; cin >> t;
while(t--) {
cin >> n;
ans = 0;
dfs(n, 0, 1);
cout << ans << endl;
for(int i = 0; i < ans; ++i) cout << arry[i] << " ";
cout << endl;
}
return 0;
}
E. Number of Simple Paths
Solution：
有n个节点的无向图，图中有n条边，因为对于无向图，如果有(n-1)条边，那么这个图可以看成一棵树（无自环和重边）,显然此题描述的图是在树的基础上增加了一条边，这样会产生一个环，而新的图就可以看成为一个环和环上所连的几棵树，知道了这个结构我们就可以分块计算简单路径数，对于一棵有(cnt)个节点的树，因为每两点之间只有一条路径，因此该树中有(frac{cnt*(cnt-1)}{2})条边，而对于与不同的两棵树，在这个图中会有两条路径可相互到达（因为中间经过一个环），因此位于不同树上的点都有两条路径可达，因此计算点的组合即可(cnt1*cnt2)，因为环上的点被计算进了树中（根节点），所以不再需要单独计算。
Code：
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 211111;
int vis[maxn], n, deg[maxn];
vector<int> mp[maxn];
vector<int> circle;
long long ans;
void topsort()
{
queue<int> box;
for(int i = 1; i <= n; ++i) {
if(deg[i] == 1) {
box.push(i);
deg[i]--;
}
}
while(!box.empty()) {
int fr = box.front(); box.pop();
for(auto k : mp[fr]) {
deg[k]--;
if(deg[k] == 1) {
box.push(k);
deg[k]--;
}
}
}
for(int i = 1; i <= n; ++i) {
if(deg[i] > 1) {
circle.push_back(i);
vis[i] = 1;
}
}
return;
}
int getSize(int root)
{
int ans = 1;
queue<int> box; box.push(root);
while(!box.empty()) {
int fr = box.front(); box.pop();
for(auto k : mp[fr]) {
if(vis[k] == 0) {
box.push(k);
ans++;
vis[k] = 1;
}
}
}
return ans;
}
int main()
{
int t; cin >> t;
while(t--) {
cin >> n;
memset(vis, 0, sizeof(vis));
memset(deg, 0, sizeof(deg));
circle.clear();
for(int i = 0; i <= n; ++i) mp[i].clear();
for(int i = 0; i < n; ++i) {
int u, v; cin >> u >> v;
mp[u].push_back(v); mp[v].push_back(u);
deg[u]++; deg[v]++;
}
ans = 0;
long long sum = 0;
topsort();
for(auto k : circle) {
long long cnt = getSize(k);
// cout << k << "**" << cnt << endl;
ans += 1LL * (cnt * (cnt - 1) / 2 + sum * cnt * 2);
sum += 1LL * cnt;
}
cout << ans << endl;
}
return 0;
}
/*
1
11
9 1
1 2
7 1
4 10
8 5
4 6
4 2
7 5
2 5
3 1
11 6
*/
F. Array Partition
Solution：
因为是将数列分为三块，分别取(max)，(min)，(max)，所以当枚举第一个位置后，后面的一个位置的从左到右会导致(min)，(max)均递减，所以是单调的，因此可以用二分的方法枚举第二个合法位置，只要美剧到一个合法位置即可输出，因为会反复计算区间最值，所以可以用线段树，RMQ等数据结构维护区间最值。
Code：
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 411111;
int a[maxn], pmx[maxn], bmx[maxn], dp[maxn][20], n;
int findmin(int l, int r)
{
int k = 0;
while((1 << (k + 1)) <= (r - l + 1)) {
k++;
}
return min(dp[l][k], dp[r - (1 << k) + 1][k]);
}
int main()
{
int t; cin >> t;
while(t--) {
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
pmx[i] = max(a[i], pmx[i - 1]);
}
for(int i = 1; i <= n; ++i) {
bmx[i] = max(bmx[i - 1], a[n - i + 1]);
dp[i][0] = a[i];
}
for(int j = 1; (1 << (j - 1)) <= n; ++j) {
for(int i = 1; i <= n; ++i) {
dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}
}
bool fl = false;
for(int i = 1; i + 2 <= n; ++i) {
int l = i + 1, r = n - 1;
while(l <= r) {
int mid = (l + r) >> 1;
int k = findmin(i + 1, mid);
int s = bmx[n - mid];
if(k > pmx[i] || s > pmx[i]) {
l = mid + 1;
}
else if(k < pmx[i] || s < pmx[i]) {
r = mid - 1;
}
else {
cout << "YES" << endl;
cout << i << " " << mid - i << " " << n - mid << endl;
fl = true;
}
if(fl) break;
}
if(fl) break;
}
if(!fl) cout << "NO" << endl;
}
return 0;
}