“华为杯“ 武汉大学21级新生程序设计竞赛错题笔记

目录

• 官网链接
• • D 和谐之树
  • G 寄寄子的生日
  • J 传闻档案

官网链接 D 和谐之树

题目描述
在小马利亚的历史中，和谐之树曾经是大公主和二公主用来甩锅的道具，不过当 M6（暮光闪闪Twilight Sparkle，小蝶Fluttershy 等六位主角）在无尽森林开启它之后，这棵树就一直被暮暮保管着。

这天，暮暮（暮光闪闪）从白胡子星璇留下的资料里学习到了算法的魔法，于是她请小蝶把和谐之树改造成了二叉树的形态，她按照星璇所说，对一段区间建立了这颗树，并且在每个节点上都留下了一个编号。

形式化的，她通过调用Build(1,1,n) 建立了这棵树。

其中，第一个参数 idid 表示当前节点的编号，后两个参数 l,r 表示当前节点所代表的区间。

暮暮突然想考察一下穗龙（Spike）对于二叉树的结构了解的怎么样，于是要求穗龙回答若干次对 [1,n_i] 建立这棵树时，编号最大的节点编号是多少，穗龙不会，只好向你求助。

输入描述:
输入文件的第一行包含一个正整数T(1 ≤ T ≤ 10⁵)，表示测试数据的数目。

每个测试数据占单独的一行，包含一个正整数n(1 ≤ n ≤ 10¹⁸)，表示对区间 [1,n]按如上方式建立改造和谐之树。

输出描述:
对于每个测试数据，在单独的一行内输出结果。

示例一：
输入：
3
2
3
7
输出：
3
5
13
说明：

样例二：
输入：
5
10
18
36
33
20
输出：
25
49
113
65
57

#include

using namespace std;
typedef long long ll;

ll ans;

ll dep(ll x)
{
    int d = 1;
    while (x > 1)
    {
        x = (x + 1) >> 1;
        d++;
    }
    return d;
}

void build(ll l,ll r,ll id)
{
    ans = max(ans,id);
    if(l == r)  return;
    ll mid = l + r >> 1;
    if(dep(mid - l + 1) > dep(r - mid))
        build(l,mid,id << 1);
    else    build(mid + 1,r,id << 1 | 1);
}

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

G 寄寄子的生日

题目描述
"我的梦想是成为马娘偶像！"在逃亡者SISTERS不断发展壮大的同时，醒目飞鹰也在一步步的接近她的梦想。

4 月 4 日，为了庆祝醒目飞鹰的生日，朋友们为她订购了一个大蛋糕。

注视着大快朵颐的醒目飞鹰，联想起她惨淡的文化成绩，荣进闪耀一把抢过蛋糕。

“飞鹰子，答对下面的问题后才可以继续吃蛋糕哦～”
“现在飞鹰子有一串2∼n 的排列 a ，如果两个数 a_i ,a_j互质，你就可以交换它们的位置。

那么飞鹰子你能够在 2 × n 次交换内，将这串排列按从小到大排序吗？”
“寄！”
茫然地抬起头，醒目飞鹰下意识地回答道。

排列：一串 2∼n 的排列指一个长为 n−1 的序列，满足 2 到 n 每个数出现且仅出现一次。

互质：如果两个正整数 a,b 的最大公约数等于 1，那么称这两个正整数是互质的。

输入描述:
第一行一个整数n(2 ≤ n ≤ 10³)，表示给出一个 2∼n 的排列。

第二行 n−1 个整数 a_i(2 ≤ a_i ≤ n)，表示具体的排列。

输出描述:
第一行输出一个整数 m(0 ≤ m ≤ 2 × n) ，表示交换的次数。

接下来 m 行，每行两个整数 i,j(1 ≤ i,j ≤ n−1)，表示交换第 i 个位置上的数和第 j 个位置上的数。

你可以输出任意一个满足上述限制的答案。

注意，你不需要最小化 m.
示例一：
输入：
6
4 5 2 6 3
输出：
5
2 1
1 3
3 2
2 5
5 4
说明：

#include

using namespace std;
typedef pair<int,int> pii;

const int N = 1e3+10;
int n;
int a[N];
pii res[2 * N];//答案数组要开两倍，不然会导致段错误！
int idx;

int gcd(int a,int b)
{
    return b ? gcd(b,a % b) : a;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n;
    for (int i = 2; i <= n; i++)    cin >> a[i];
    for (int i = 2; i <= n; i++)
    {
        if(a[i] != i)
        {
            int pos1 = 0,pos2 = 0;//两个交换位置的下标
            for (int j = i + 1; j <= n; j++)
            {
                if(a[j] == i)   pos1 = j;//找到该位置该放的数的下标
                if(gcd(a[i],a[j]) == 1 && gcd(a[j],i) == 1) pos2 = j;//如果三角关系都互质，可利用中介交换
            }
            if(pos2 != 0)//如果可以采用中介交换，使用是最稳妥的
            {
                res[idx++] = {i - 1,pos2 - 1};
                swap(a[i],a[pos2]);
            }
            swap(a[i],a[pos1]);
            res[idx++] = {i - 1,pos1 - 1};
        }
    }
    cout << idx << endl;
    for (int i = 0; i < idx; i++)
    {
        cout << res[i].first << " " << res[i].second << endl;
    }
    // for(int i = 2;i <= n;i++)   cout << a[i] << " ";
    return 0;
}

J 传闻档案

题目描述
这是发生在Magius之翼刚把鹤乃，大锤和莎奈洗脑后的故事。

成为了队伍的队长，发下了绝不辜负八千代的誓言的彩羽希望能够找到 Magius 的据点，救回三人。

她分析着八千代的神滨传闻档案，漂亮的笔记中有着至今为止打倒的传闻，有着整理过后也没有调查的传闻，有着只知道名字和地点的传闻。

结合着信息的可靠程度与位置关系，彩羽在神滨地图上与八千代一笔一划地标记着。

她们认为，传闻的出现地点共有 n 个，第 i 个地点中传闻有预测魔力值 a_i。

传闻并不是孤立的，其中有 m 对传闻能够单向地传递着魔力，这使得每个地点实际的魔力表现值更强。

具体的，如果第 i 个地点的传闻，能够通过若干条单向魔力通道到达第 j 个地点，它就能够表现出 a_j​的魔力值。

传闻们并不傻，它们总会表现出它们能够通过单向通道得到的最大魔力值，彩羽称这个最大值为表现魔力值。

彩羽想知道所有传闻的表现魔力值之和是多少，象征性的，她把目光投向了身为小qb的你。

输入描述：
第一行输入两个正整数 n,m(1 ≤ n ≤ 10⁵ ,1 ≤ m ≤ 3×10⁵) ，分别表示传闻出现地点个数和魔力通道个数。

第二行输入 n 个正整数a₁,…,a_n(1 ≤ a_i ≤ 10⁹ )，其中 a_i​表示编号为 i 的传闻的预测魔力值。

接下来 m 行，每行两个整数 u_i​,v_i(u_i != v_i)，表示一条魔力通道。

保证不存在两条完全相同的魔力通道。

输出描述:
输出一行，包含一个整数，表示所有传闻的表现魔力值之和。

示例一：
输入：
4 4
2 1 4 3
1 2
1 3
2 4
3 4
输出：
14
示例二：
输入：
8 9
2 1 1 1 1 1 1 1
2 1
2 4
4 3
3 2
5 4
5 7
7 8
8 5
6 8
输出：
16
备注：

#include
#include
#include
#include

typedef long long ll;

using namespace std;

const int N = 3e5+10;

int n,m;
int a[N];
int h[N],e[N],ne[N],idx;
int dfn[N],low[N],timestamp;
int stk[N],top;
bool in_stk[N];
int scc_cnt;

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[++top] = u,in_stk[u] = true;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u],low[j]); 
        }
        else if(in_stk[j])  low[u] = min(low[u],dfn[j]);
        a[u] = max(a[u],a[j]);
    }
    if(dfn[u] == low[u])
    {
        ++scc_cnt;
        int y;
        do{
            y = stk[top--];
            in_stk[y] = false;
            a[y] = a[u];
        }while(y != u);
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++)   scanf("%d",&a[i]);
    memset(h,-1,sizeof(h));
    while (m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    
    for(int i = 1;i <= n;i++)
        if(!dfn[i]) tarjan(i);
    ll ans = 0;
    for(int i = 1;i <= n;i++)   ans += a[i];
    printf("%lld\n",ans);
    return 0;
}