第四周
1. A还是B
第一种思路
统计 A, B 字符出现的次数即可
代码如下
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int a, b;
char c;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
cin >> c;
c == 'A'?a ++: b ++;
}
if (a == b) puts("T");
else a > b?puts("A"):puts("B");
return 0;
}
2. 扩充序列
第一种思路
观察示例 $[1,2,1,3,1,2,1,4,1,2,1,3,1,2,1]$,
可以明显的看出序列分为几层
分别是奇数位上的 1, 去掉 1 之后奇数位的 2, 去掉 2 之后奇数位上的 3,…以及 4
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
long long n, k, ans;
int main()
{
scanf("%lld %lld", &n, &k);
while (k % 2 == 0)
{
k /= 2;
ans ++;
}
printf("%lld", ans + 1);
return 0;
}
第二种思路
递归模拟。
复杂度 $O(n)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL dfs(LL n, LL k)
{
if (k == 1ll << (n - 1)) return n;
if (k < 1ll << (n - 1)) return dfs(n - 1, k);
else return dfs(n - 1, k - (1ll << (n - 1)));
}
int main()
{
LL n, k, ans;
scanf("%lld %lld", &n, &k);
printf("%lld", dfs(n, k));
return 0;
}
3. 构造有向无环图
第一种思路
简化题意,如果确认过的有向边是拓扑图,则按照拓扑序从前往后添加边即可。
因为,可以将确定方向理解为加边,毕竟条件成立后,拓扑序排后的边是没有连向排前面的拓扑序的出边的。
所以不影响图的拓扑性质。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int T;
int n, m, k;
int h[N], e[N], ne[N], idx;
int d[N];
int q[N];
int pos[N];
struct Edge
{
int a, b;
}edges[N];
void add(int a, int b) // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool topsort()
{
int hh = 0, tt = -1;
// d[i] 存储点i的入度
for (int i = 1; i <= n; i ++ )
if (!d[i])
q[ ++ tt] = i;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (-- d[j] == 0)
q[ ++ tt] = j;
}
}
// 如果所有点都入队了,说明存在拓扑序列;否则不存在拓扑序列。
return tt == n - 1;
}
int main()
{
scanf("%d", &T);
while (T -- )
{
scanf("%d%d", &n, &m);
memset(d, 0, (n + 1) * 4);
memset(h, -1, (n + 1) * 4);
idx = k = 0;
for (int i = 1; i <= m; i ++ )
{
int t, a, b;
scanf("%d %d %d", &t, &a, &b);
if (t == 1)
{
add(a, b);
d[b] ++;
}
else edges[k ++ ] = {a, b};
}
if (!topsort()) puts("NO");
else
{
puts("YES");
for (int i = 1; i <= n; i ++ )
for (int j = h[i]; j != -1; j = ne[j])
{
printf("%d %d\n", i, e[j]);
}
for (int i = 0; i < n; i ++ ) pos[q[i]] = i;
for (int i = 0; i < k; i ++ )
{
int a = edges[i].a, b = edges[i].b;
if (pos[a] > pos[b]) swap(a, b);
printf("%d %d\n", a, b);
}
}
}
return 0;
}