# #628 DIV2 题解

## 组样例，每组样例给一个，构造一组，使得。

```2
2
14
```
```1 1
6 4
```

```#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
int t = 0;
scanf("%d", &t);
while(t--) {
ll x = 0;
scanf("%lld", &x);
printf("1 %lld\n", x - 1);
}
return 0;
}
```

```2
3
3 2 1
6
3 1 4 1 5 9
```
```3
5
```

```#include <bits/stdc++.h>
using namespace std;

int a[maxn];
map<int, int> mii;

int main(){
int t = 0;
scanf("%d", &t);
while(t--) {
mii.clear();
int n = 0, cnt = 0;
scanf("%d", &n);
for(int i = 1;i <= n;i++) {
scanf("%d", a + i);
if(mii.count(a[i]) == 0) cnt++;
mii[a[i]]++;
}
printf("%d\n", cnt);
}
return 0;
}
```

```6
1 2
1 3
2 4
2 5
5 6
```
```0
3
2
4
1
```

```#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5+5;

pii E[maxn];
int deg[maxn], flag[maxn];

int main(){
int n = 0, tag = 0;
memset(flag, -1, sizeof(flag));
scanf("%d", &n);
for(int i = 1;i < n;i++) {
int u, v;
scanf("%d %d", &u, &v);
E[i] = {u, v};
deg[u]++, deg[v]++;
}
for(int i = 1;i <= n;i++) {
if(deg[i] >= 3) {
tag = i; break;
}
}
if(tag == 0) {
for(int i = 1;i < n;i++) {
printf("%d\n", i - 1);
}
} else {
int cnt = 0, num = 0;
for(int i = 1;i <= n;i++) {
if(E[i].first == tag || E[i].second == tag) {
flag[i] = cnt++;
}
if(cnt == 3) break;
}
for(int i = 1;i < n;i++) {
if(flag[i] == -1) {
printf("%d\n", cnt++);
} else {
printf("%d\n", flag[i]);
}
}
}
return 0;
}
```

```in: 2 4
```
```out:
2
3 1
```
```in: 1 3
```
```out:
3
1 1 1
```

```#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100;

int flag[maxn];

int main(){
ll u, v;
scanf("%lld %lld", &u, &v);
ll d = v - u;
if(v == u && v != 0) {
puts("1");
printf("%lld\n", u);
}
else if(v == 0 && u == 0) {
puts("0");
} else if(d % 2 == 1 || d < 0) {
puts("-1");
} else {
ll tmp = u, ans = 0;
int cnt = 0, f = 0;
while(tmp) {
flag[cnt++] = tmp % 2;
tmp /= 2;
}
cnt = 0, tmp = d / 2ll;
while(tmp) {
flag[cnt++] += tmp % 2;
tmp /= 2;
}
for(int i = 0;i < 64;i++) {
if(flag[i] >= 2) {
f = 1; break;
}
}
if(f == 1) {
puts("3");
printf("%lld %lld %lld\n", u, d / 2ll, d / 2ll);
} else {
puts("2");
printf("%lld %lld\n", u + d / 2ll, d / 2ll);
}
}
return 0;
}
```

```3
1 4 6
```
```1
```
```4
2 3 6 6
```
```2
```

```#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int maxn = 1e6+5;
#define INF 0x3f3f3f3f

int a[maxn], prime[maxn], pp[maxn], pos[maxn];
pii pr[maxn];
bool is_prime[maxn];

int sieve(int n){
int p = 0;
for(int i = 0;i <= n;i++) is_prime[i] = true;
is_prime[0] = is_prime[1] = false;
for(int i = 2;i <= n;i++){
if(is_prime[i]) prime[p++] = i;
for(int j = 0;j < p;j++){
if(prime[j] * i > n) break;
is_prime[prime[j] * i] = false;
if(i % prime[j] == 0) break;
}
}
return p;
}
vector<int> G[maxn];
int dis[maxn], vis[maxn], flag[maxn], pre[maxn];
int bfs(int u) {
queue<int> q;
memset(vis, 0, sizeof(vis));
dis[u] = 0, vis[u] = 1;
q.push(u);
while(q.size()) {
int v = q.front();
q.pop();
for(int i = 0;i < G[v].size();i++) {
int to = G[v][i];
if(vis[to] == 0) {
vis[G[v][i]] = 1;
dis[to] = dis[v] + 1;
pre[to] = v;
q.push(to);
} else {
if(to == pre[v]) continue;
return dis[v] + dis[to] + 1;
}
}
}
return INF + 5;
}

int main(){
int n;
scanf("%d", &n);
int cnt = sieve(1000000 + 5);
for(int i = 0;i < cnt;i++) {
pos[prime[i]] = i;
}
for(int i = 0;i < 200;i++) {
pp[i] = prime[i] * prime[i];
}
for(int i = 1;i <= n;i++) {
scanf("%d", a + i);
for(int j = 0;j < 200;j++) {
while(a[i] % pp[j] == 0) {
a[i] /= pp[j];
}
if(a[i] < prime[j]) break;
}
if(is_prime[a[i]]) flag[a[i]] = 1;
else {
flag[a[i]] = 2;
for(int j = 0;j < 200;j++) {
if(a[i] % prime[j] == 0) {
pr[a[i]] = {prime[j], a[i] / prime[j]}; break;
}
}
}
}
for(int i = 1;i <= n;i++) {
if(a[i] == 1) {
puts("1"); return 0;
} else {
if(flag[a[i]] == 1) {
int u = pos[a[i]] + 1;
G[u].push_back(0), G[0].push_back(u);
} else {
int u = pos[pr[a[i]].first] + 1, v = pos[pr[a[i]].second] + 1;
G[u].push_back(v), G[v].push_back(u);
}
}
}
int ans = INF;
for(int i = 0;i < 200;i++) {
ans = min(ans, bfs(i));
}
if(ans == INF) {
puts("-1"); return 0;
}
printf("%d\n", ans);
return 0;
}
```

```6 6
1 3
3 4
4 2
2 6
5 6
5 1
```
```1
1 6 4
```
```6 8
1 3
3 4
4 2
2 6
5 6
5 1
1 4
2 5
```
```2
4
1 5 2 4
```

```#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;

vector<int> G[maxn];
vector<int> st;
vector<int> ans[maxn];
int res, vis[maxn], ins[maxn], dep[maxn];

int fun(int n) {
for(int i = 1; i <= n;i++) {
if(1ll * i * i >= n) return i;
}
}

void dfs(int u) {
st.push_back(u); ins[u] = 1;
for(int i = 0;i < G[u].size();i++) {
int v = G[u][i];
if(dep[v] == 0) {
dep[v] += dep[u] + 1;
dfs(v);
} else {
if(dep[u] - dep[v] + 1 >= res) {
puts("2");  printf("%d\n", dep[u] - dep[v] + 1);
int len = st.size(), cnt = 0;//assert(len - 1 >= dep[v] - 1);
for(int i = len - 1;i >= 0;i--) {
cnt++; printf("%d", st[i]);
if(cnt == dep[u] - dep[v] + 1) {
puts(""); break;
} else {
printf(" ");
}
}
exit(0);
}
}
}
st.pop_back();
ins[u] = 0;
}

void dfs2(int u, int num) {
if(vis[u]) return;
vis[u] = 1;
ans[num % (res - 1)].push_back(u);
for(int i = 0;i < G[u].size();i++) {
int v = G[u][i];
dfs2(v, num + 1);
}
}

int main(){
int n, m;
scanf("%d %d", &n, &m);
res = fun(n);
for(int i = 1;i <= m;i++) {
int u, v;
scanf("%d %d", &u, &v);
G[u].push_back(v), G[v].push_back(u);
}
dep[1] = 1;
dfs(1); dfs2(1, 1);
puts("1");
for(int i = 0;i < res;i++) {
if(ans[i].size() >= res) {
int len = ans[i].size(), cnt = 0;
for(int j = 0;j < res;j++) {
printf("%d%c", ans[i][j], j == res - 1 ? '\n' : ' ');
}
exit(0);
}
}
return 0;
}
```

0 条评论

• ### 水果Fruit（母函数） - HDU 2152

转眼到了收获的季节，由于有TT的专业指导，Lele获得了大丰收。特别是水果，Lele一共种了N种水果，有苹果，梨子，香蕉，西瓜……不但味道好吃，样子更是好看。 ...

• ### leetcode题解 | 78. 子集

这个题目很容易想到使用DFS的方式来解决，因为组合的题容易产生转移方程，这样也是没有什么问题的。

• ### 力扣 526.优美的排序（next_permutation?)

链接：https://leetcode-cn.com/problems/beautiful-arrangement

• ### 09-排序3 Insertion or Heap Sort (25分)

Insertion sort iterates, consuming one input element each repetition, and growin...

• ### P2658 汽车拉力比赛

题目描述 博艾市将要举行一场汽车拉力比赛。 赛场凹凸不平，所以被描述为M*N的网格来表示海拔高度(1≤ M,N ≤500)，每个单元格的海拔范围在0到10^9之...

• ### 1545 最简单排序

个人博客：double.win 1545 最简单排序  时间限制: 1 s  空间限制: 1000 KB  题目等级 : 青铜 Bronze 题解 题目描述 D...

• ### vs---错误收集并自己解决后归纳

1。C++编译时，出现这样的错误 d:\program files\microsoft visual studio\vc98\include\stdio.h(3...

• ### leetcode 204题求素数个数

Count the number of prime numbers less than a non-negative number, n

• ### cf1000F. One Occurrence(线段树 set)

首先把询问离线，预处理每个数的\(pre, nxt\)，同时线段树维护\(pre\)(下标是\(pre\)，值是\(i\))，同时维护一下最大值

• ### 洛谷P3763 [TJOI2017]DNA(后缀数组 RMQ)

具体来说，每次比较当前后缀和\(S_0\)的lcp，如果长度\(< N\)的话就从不合法的位置继续匹配