A EhAb AnD gCd
题目大意
给定一个整数 $x（2\leq x \leq 10^9)$
求 $a,b$ 满足 $\gcd(a,b) + \operatorname{lcm}(a,b) = x$
多组解输出任意一个
Code
这有啥说的，随便找个质因数让后输出 $p, x$ 就可以
// Woshiluo Luo<[email protected]>
// 2020/03/14 22:36:48
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }
int t, x;
int main() {
scanf( "%d", &t );
while( t -- ) {
scanf( "%d", &x );
int sq = std::sqrt(x) + 1;
for( int i = 1; i <= sq; i ++ ) {
if( x % i == 0 ) {
int tmp = ( x / i ) - 1;
if( tmp == 0 )
continue;
printf( "%d %d\n", i, tmp * i );
break;
}
}
}
}B CopyCopyCopyCopyCopy
题目大意
给你一个长度为 $n$ 的数列 $a$, 现在你可以复制无数个 $a$ 接到原来的数列后面
问这样接完后，最长严格上升子序列的长度
Code
因为可以接无限次，所以直接输出数字个数就可以了
// Woshiluo Luo<[email protected]>
// 2020/03/14 22:42:47
#include <cstdio>
#include <cstring>
#include <algorithm>
template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }
const int N = 1e5 + 1e4;
int t;
int n;
int a[N];
int main() {
scanf( "%d", &t );
while( t -- ) {
scanf( "%d", &n );
for( int i = 1; i <= n; i ++ ) {
scanf( "%d", &a[i] );
}
std::sort( a + 1, a + n + 1 );
int cnt = 0, la = 0;
for( int i = 1; i <= n; i ++ ) {
if( i == 1 || a[i] != la ) {
la = a[i];
cnt ++;
}
}
printf( "%d\n", cnt );
}
}C Ehab and Path-etic MEXs
题目大意
给一棵节点数为 $n$ 的树
现在你要给每条边一个边权，要求：
- 边权为一个整数 $v(0\leq v \leq n – 2)$
- 每条边的边权不能和别的边的相同
现在定义 $MEX(u,v)$ 为 $u,v$ 之间的最短简单路径上没有出现的边权中的最小值
请给出一种边权方案，最小化 $\max{MEX(u,v)}$
思路
考虑每条边会被算进去多少次，记为每条边的贡献
贡献越大给越大的边就可以了
实际上可以更加简化，因为无论如何一定有一个 $MEX \geq 2$
所以我们尽可能避免 $0,1,2$ 出现在一条边上即可
随便找一个度数 $\geq 2$ 的点，把这三个数字放上去即可
如果没有这种点，那么怎么摆都会有一条 $MEX=n-1$ 的路径
Code
// Woshiluo Luo<[email protected]>
// 2020/03/14 22:52:18
#include <cstdio>
#include <cstring>
#include <algorithm>
template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }
const int N = 1e5 + 1e4;
// Edge Start
struct edge {
int to, next, val;
} e[ N << 1 ];
int ehead[N], ecnt;
inline void add_edge( int now, int to, int val ) {
ecnt ++;
e[ecnt].to = to;
e[ecnt].next = ehead[now];
e[ecnt].val = val;
ehead[now] = ecnt;
}
// Edge End
struct node { long long val; int id; } max[N];
bool cmp( node _a, node _b ) { return _a.val < _b.val; }
int n, x, y;
int son[N], val[N];
void dfs( int now, int la ) {
son[now] = 1;
for( int i = ehead[now]; i; i = e[i].next ) {
if( e[i].to == la )
continue;
dfs( e[i].to, now );
son[now] += son[ e[i].to ];
max[ e[i].val ].val = ( 1LL * son[ e[i].to ] * ( n - son[ e[i].to ] ) );
}
}
int main() {
#ifdef woshiluo
freopen( "c.in", "r", stdin );
freopen( "c.out", "w", stdout );
#endif
scanf( "%d", &n );
for( int i = 1, u, v; i < n; i ++ ) {
max[i].id = i;
scanf( "%d%d", &u, &v );
add_edge( u, v, i );
add_edge( v, u, i );
}
dfs( 1, 0 );
std::sort( max + 1, max + n, cmp );
for( int i = 1; i < n; i ++ ) {
val[ max[i].id ] = i - 1;
}
for( int i = 1; i < n; i ++ ) {
printf( "%d\n", val[i] );
}
}D Ehab the Xorcist
给定两个整数 $u,v$ 求最短的数列 $a$ 满足
- $$ \sum a = v $$
- xor 和为 $u$
多解输出任意一个
无解输出 $-1$
题目大意
这题感觉的 C 简单啊
满足 $xor$ 容易，满足 $v$ 的话需要难度
考虑最后 $xor$ 的结果受每个二进制位的和的奇偶性影响
因此可以确定每一位的奇偶性
然后随便搞一下满足 $v$ 就可以了
Code
// Woshiluo Luo<[email protected]>
// 2020/03/14 23:39:20
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }
unsigned long long u, v;
int bit_u[110], bit_less[110], bit_cnt[110];
std::vector<unsigned long long> ans;
inline void noans() {
printf( "-1\n" );
exit(0);
}
void to_bit( unsigned long long a, int bit[] ) {
int cnt = 0;
while( a ) {
bit[ ++ cnt ] = a & 1;
a >>= 1;
}
}
int main() {
scanf( "%llu%llu", &u, &v );
if( v < u )
noans();
to_bit( v - u, bit_less );
to_bit( u, bit_u );
for( int i = 1; i <= 100; i ++ ) {
bit_cnt[i] = bit_u[i];
}
int p = 64;
int cnt = 0;
while( p ) {
bit_cnt[p] += ( cnt - ( cnt & 1 ) );
cnt = cnt & 1;
if( bit_less[p] )
cnt ++;
p --; cnt <<= 1;
}
if( cnt != 0 )
noans();
bool flag = true;
while( flag ) {
flag = false;
unsigned long long out = 0;
unsigned long long p = 1;
for( int i = 1; i <= 64; i ++, p <<= 1 ) {
if( bit_cnt[i] ) {
out = out | p;
bit_cnt[i] --;
flag = true;
}
}
if( flag )
ans.push_back(out);
}
cnt = ans.size();
printf( "%d\n", cnt );
for( int i = 0; i < cnt; i ++ ) {
printf( "%llu ", ans[i] );
}
}E Ehab’s REAL Number Theory Problem
题目大意
给你一个长度为 $n$ 的数列，保证数列中每个数字有不超过 $7$ 个因数
请求出最短的子序列，使子序列成绩为完全平方数
思路
这题比 F 题难吧…
首先由 保证数列中每个数字有不超过 $7$ 个因数 得每个数不会有超过两个 $1$ 和其本身以外的质因数
然后我们可以先把每个数里的完全平方数因子先除掉，因为这些不会对答案造成影响
这样下来每个数的因子只有 1 和其本身以及两个质因数（前提是这个数不是质数）
然后建图，如果这个数是质数，将其和 $1$ 连接，如过不是将其的两个质因数连接
剩下就是求最小环
Code
// Woshiluo Luo<[email protected]>
// 2020/03/15 22:08:53
#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }
const int N = 1e6 + 1e4;
const int M = 1100;
const int INF = 0x3f3f3f3f;
int n, ans = INF;
int dis[N], fa[N];
bool marked[N], pool[N];
// Edge Start
struct edge {
int cur, to, next;
} e[ N << 1 ];
int ehead[N], ecnt = 1;
inline void add_edge( int now, int to ) {
ecnt ++;
e[ecnt].cur = now;
e[ecnt].to = to;
e[ecnt].next = ehead[now];
ehead[now] = ecnt;
}
// Edge End
int bfs( int st ) {
memset( dis, INF, sizeof(dis) );
memset( fa, 0, sizeof(fa) );
std::queue<int> q;
q.push(st); dis[st] = 0;
while( !q.empty() ) {
int cur = q.front(); q.pop();
for( int i = ehead[cur]; i; i = e[i].next ) {
if( e[i].to == fa[cur] )
continue;
if( dis[ e[i].to ] >= INF ) {
fa[ e[i].to ] = cur;
dis[ e[i].to ] = dis[cur] + 1;
q.push( e[i].to );
}
else {
return dis[cur] + dis[ e[i].to ] + 1;
}
}
}
return INF;
}
int main() {
scanf( "%d", &n );
for( int i = 1, x; i <= n; i ++ ) {
scanf( "%d", &x );
std::vector<int> a;
int cnt = std::sqrt(x) + 1;
while(cnt > 1) {
int cnt_pow = cnt * cnt;
while( x % cnt_pow == 0 )
x /= cnt_pow;
cnt --;
}
if( x == 1 )
chk_Min( ans, 1 );
if( pool[x] )
chk_Min( ans, 2 );
pool[x] = true;
int tmp = std::sqrt(x);
for( int j = 2; j <= tmp; j ++ ) {
if( x % j == 0 ) {
a.push_back(j);
a.push_back( x / j );
break;
}
}
if( a.size() == 0 ) {
add_edge( 1, x );
add_edge( x, 1 );
}
else if( a.size() != 0 ) {
add_edge( a[0], a[1] );
add_edge( a[1], a[0] );
}
}
if( ans != INF ) {
printf( "%d\n", ans );
return 0;
}
for( int i = 1; i <= 1000; i ++ ) {
if( ehead[i] )
chk_Min( ans, bfs(i) );
}
if( ans >= INF )
ans = -1;
printf( "%d\n", ans );
}F Ehab’s Last Theorem
题目大意
给定一个 $n$ 个节点的图
令 $glo=\lceil\sqrt{n}\rceil$
你要么找到一个长度和 $glo$ 相等的环
要么找到一个比 $glo$ 小的独立集
Code
先试图找环，找不到肯定有独立集
// Woshiluo Luo<[email protected]>
// 2020/03/15 15:49:32
#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }
const int N = 1e5 + 1e4;
const int M = 2e5 + 1e4;
int n, m, need;
int dep[N];
bool vis[N];
std::stack<int> st;
// Edge Start
struct edge { int to, next; } e[ M << 1 ];
int ehead[N], ecnt;
inline void add_edge( int now, int to ) {
ecnt ++;
e[ecnt].to = to;
e[ecnt].next = ehead[now];
ehead[now] = ecnt;
}
// Edge End
void dfs( int now ) {
st.push(now);
dep[now] = st.size();
for( int i = ehead[now]; i; i = e[i].next ) {
if( dep[ e[i].to ] == 0 )
dfs( e[i].to );
else if( dep[now] - dep[ e[i].to ] + 1 >= need ) {
int size = dep[now] - dep[ e[i].to ] + 1;
printf( "%d\n%d\n", 2, size );
for( int i = 1; i <= size; i ++ ) {
printf( "%d ", st.top() );
st.pop();
}
exit(0);
}
}
if( !vis[now] ) {
for( int i = ehead[now]; i; i = e[i].next ) {
vis[ e[i].to ] = true;
}
}
st.pop();
}
int main() {
#ifdef woshiluo
freopen( "f.in", "r", stdin );
freopen( "f.out", "w", stdout );
#endif
scanf( "%d%d", &n, &m );
while( need * need < n )
need ++;
while( m -- ) {
int u, v;
scanf( "%d%d", &u, &v );
add_edge( u, v ); add_edge( v, u );
}
dfs(1);
printf( "%d\n", 1 );
int cnt = 0;
for( int i = 1; i <= n; i ++ ) {
if( vis[i] == false ) {
printf( "%d ", i );
cnt ++;
}
if( cnt == need )
break;
}
}
