#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;
}
给一个和，构造一个最短的数组，使得数组所有元素的异或和为，和为。若没有输出-1。
in: 2 4
out:
2
3 1
in: 1 3
out:
3
1 1 1
首先记，显然不行，当只考虑二进制最低位时，异或和加法等价，所以，的奇偶性应该相同，所以时也不行。
然后开始构造合法的情况，考虑让数组第一个数，显然，但不一定等于，我们知道对于任意，有。考虑让，而总是偶数，这样用三个数，总是能构造出来异或和为，和为。
考虑能不能把数组个数减小一点，可以把不加在上(去掉)，而是直接加在上，但是这里是不能随便加的，当的二进制表示的所有是1的地方，在的二进制表示中恰好是0，这样加进去不会不会产生进位，同时和异或时会重新得到。这样的情况下长度被我们缩短到了。
之后考虑一点细节，到时，，直接输出即可。
#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;
}
给一个和个数，，，，每个不超过7个因子，找一个长度最小的非空子序列，使得序列中的所有数的积是一个完全平方数，输出序列长度。
3
1 4 6
1
4
2 3 6 6
2
因为因子个数不超过7个，所以最多能有两个不相同的质因数。考虑形式的数，它要凑成一个完全平方数，我们期待的是有一个，注意到和，都是需要一个来凑成平方数，所以次数是偶数的质因子是没有作用，这个时候对于每个，把其中的次数是偶数的质因子全部拿掉，所有的数都可以表示为
当存在1时，答案很显然就是这个1，所以长度就为1。
当遇到时，将和0号点连边。
当遇到时，将和连边。
之后的问题就是寻找一个最小环，输出最小环长度即可。
固定一个点找最小环的话直接可以做到，边权都是1，所以需要的时间，但这里再移动固定的点的话就会是平方的复杂度肯定会超时。
注意到连边的时候中有一个一定是，也就是，所以只需要移动以下的质数来寻找最小环即可，若没找到则输出-1。
#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;
}
给一张个点条边的图，问图中存不存在大小为的独立集，或者长度大于的简单环。输出其中一种可以，若要输出独立集，先输出1，再输出独立集中元素， 若要输出简单环先输出2再输出环的长度，再输出环中元素。
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
首先直接,利用一个栈来保存过的路径，当一个点产生回边时，检查这条回边的两个端点在原树上距离是否大于等于（因为环的长度还需要再加上1)。有则直接找到了环。没有则记录下到该点的深度。
之后可以将每个点的深度模一个，
当
若，之间有一条回边。则在第一步的时候就会被判环了，因为两者之间的距离等于。所以在模数相同的情况下，，可以放在一个独立集之中，而由于，是任意的，所以所有模结果相同的数都可以放在一个独立集中，而因为模数是，一共有个点，所以总存在一个独立集中元素个数是符合条件的。找到一个符合条件的输出即可。
#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;
}
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-03-31，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录