DATE #:20241017

ITEM #:DOC

WEEK #:THURSDAY

DAIL #:玖月拾伍

TAGS

<iframe border="0" frameborder="no" height="86" marginheight="0" marginwidth="0" src="//music.163.com/outchain/player?type=2&id=1843285799&auto=0&height=66" width="330"></iframe>
< BGM = “呼唤落花之名 - MoreanP” >
< oi-contest >
< [NULL] >
< [空] > 
< [空] >

我携落花与浪漫给予你，给予温柔本身。

距2024CSP-S 还有\(\textbf{0x8}\)天！！！

比赛主页 - 20241017高一csp模拟赛

A. 城市建设

时间限制: 1 s   内存限制: 128 MB   测评类型: 传统型

---

题目描述

交通运输网的建设是城市建设的重要部分. 现有\(n\) 个城市，编号为 \(1,2,...,n\)，每个城市 i\(i\) 有一个值 \(w_i\)（意义之后会用到），由于城市间没有铁路，交通十分不便，因此计划在城市间依次修建 m\(m\) 条铁路.

已知第\(i\) 条铁路（\(1\le i\le m\)）连接城市 \(a_i\) 和 \(b_i\)，在第 \(t_i\) 天修建完成，也就是在第 \(t_i\) 天之后（含第 \(t_i\) 天）城市 \(a_i\) 和 \(b_i\) 间将有铁路连接.

定义某一天的交通量为

\[\sum_{i=1}^n\sum_{j=i+1}^nC(i,j)w_iw_j \]

其中 \(C(i,j)\) 表示当天城市 \(i\) 和\(j\) 能否互相到达，如果能则 \(C(i,j)=1\)，否则 \(C(i,j)=0\). 上式的意义即所有满足 \(i < j\) 且编号为 i,j\(i,j\) 的城市可相互到达的数对 (i,j)\((i,j)\) 的 wiwj\(w_iw_j\) 之和.

给出 q\(q\) 个询问，每次询问给出一个 \(t\)，你需要回答第 \(t\) 天的交通量是多少.

输入格式

第一行三个由空格分隔的正整数 \(n\)，\(m\)，\(q\)，分别表示城市数、计划修建的铁路数和询问数.

第二行 \(n\) 个由空格分隔的正整数，表示 \(w_1,w_2,...,w_n\).

接下来 \(m\) 行，第 i\(i\) 行为三个由空格分隔的正整数 \(t_i\)，\(a_i\)，\(b_i\)，描述第i\(i\) 条铁路，意义如题目所示.

接下来 q\(q\) 行，每行一个整数 t\(t\) 表示一个询问.

输出格式

输出 \(q\) 行，每行一个整数，依次表示每个询问的答案，即第 \(t\) 天的交通量.

C/C++ 输入输出 long long 时请用 %lld. C++ 可以直接使用 cin/cout 输入输出.

样例输入

【样例输入1】

4 3 5
2 5 3 1
2 1 2
4 2 3
1 1 4
1
2
5
4
0

【样例输入2】

见样例数据下载。

样例输出

【样例输出1】

2
17
41
41
0

【样例输出2】

见样例数据下载。

【样例说明】

对于第 \(1\) 个询问，\(t=1\)，此时修建的铁路有 \((1,4)\)，可以相互到达的城市对有 \((1,4)\)，交通量为\(w_1w_4=2\times 1=2\).

对于第 \(2\) 个询问，\(t=2\)，此时修建的铁路有 \((1,2)\)，\((1,4)\)，可以相互到达的城市对有 \((1,2)\)，\((1,4)\)，\((2,4)\)，交通量为 \(w_1w_2+w_1w_4+w_2w_4=2\times 5+2\times 1+5\times 1=17\).

对于第 \(3\) 个询问，\(t=5\)，此时修建的铁路有 \((1,2)\)，\((2,3)\)，\((1,4)\)，因此可以相互到达的城市对有 \((1,2)\)，\((1,3)\)，\((1,4)\)，\((2,3)\)，\((2,4)\)，\((3,4)\)，交通量为 \(w_1w_2+w_1w_3+w_1w_4+w_2w_3+w_2w_4+w_3w_4=41\).

对于第 \(4\) 个询问，\(t=4\)，可以发现此时的铁路和第 \(3\) 个询问是一样的，交通量为 41\(41\).

对于第 \(5\) 个询问，\(t=0\)，没有任何铁路，交通量为 \(0\).

数据规模与约定

【数据范围】

对于 30% 的数据，\(n=4\)，\(m\le 6\)，\(q=1\).

对于 50% 的数据，\(n,m,q\le 100\).

另外有 10% 的数据，对每个询问 t\(t\)，保证第 t\(t\) 天所有城市可相互到达.

另外有 10% 的数据，\(q=1\).

对于 100% 的数据，\(n,m,q\le 10^5\)，\(w_i\le 100\)，\(1\le a_i,b_i\le n\)，\(t\le 10^9\)，不存在连接两个相同城市的铁路.

【下载】

样例数据下载

非常并查集的题，其实只要注意到两个连通块连接时就是权值和相乘的贡献就好做很多

//2024.10.17
//by white_ice
#include<bits/stdc++.h>
// #include"../../../need.cpp"
using namespace std;
#define int long long 
#define itn long long 
constexpr int oo = 100005;
int n,m,q;int out;
itn st[oo];
struct nod{int a,b,t;
__inline bool operator<(const nod b){return t<b.t;}}sp[oo];
struct ned{int res,t,id;}que[oo];
bool cmp1(ned a,ned b){return a.t<b.t;}
bool cmp2(ned a,ned b){return a.id<b.id;}
itn fa[oo];
__inline int find(int a){return fa[a]==a?a:fa[a]=find(fa[a]);}
main(void){
    // fre();
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> q;
    for (int i=1;i<=n;i++)cin >> st[i];
    for (int i=1;i<=m;i++)cin >> sp[i].t >> sp[i].a >> sp[i].b;
    sort(sp+1,sp+m+1);
    for (itn i=1;i<=q;i++)cin >> que[i].t,que[i].id = i;
    sort(que+1,que+q+1,cmp1);
    for (itn i=1;i<=n;i++)fa[i] = i;
    int top = 1;
    for (itn i=1;i<=q;i++){
        itn t = que[i].t;
        while (sp[top].t<=t&&top<=m){
            int a = sp[top].a;
            int b = sp[top].b;
            // p_(true,a,b);
            int fat = find(a);
            int fbt = find(b);
            if (fat==fbt) {top++;continue;}
            out += st[fat]*st[fbt];
            fa[fat] = fbt;
            st[fbt] += st[fat];
            top++;
        }
        que[i].res = out;
    }
    sort(que+1,que+q+1,cmp2);
    for(itn i=1;i<=q;i++)cout << que[i].res << '\n';
    exit (0);
}

B. 排列

时间限制: 1 s   内存限制: 128 MB   测评类型: 传统型

---

题目描述

小明今天突然对某种特殊的序列特别感兴趣，请教你一个问题。

对于序列长度为 \(n\) 的自然数序列 \(\{a\}\)，若序列中的每个数都为 \(1\) 到 \(n\) 自然数且互不相同，则称序列 \(\{a\}\) 为好的序列。

形式化地讲，好的序列是指对任意整数 \(1\le i,j \le n\;(i\ne j)\)，有 \(1\le a_i\le n, a_i\in \mathbb N^*\) 且 \(a_i \ne a_j\)。

给定自然数 \(n\)，我们称所有长度为 \(n\) 的好的序列 \((p_1,p_2, \ldots,p_n)\) 中满足序列中任意相邻两数以及尾首两数产生的 \(n\) 对有序二元对中，前面的数字模后面的数字的结果不超过 \(2\)，为完美的序列。

形式化地讲，完美的序列即：

• 对所有的 \(i\;(1\le i \le n)\) 有 \(p_i \textrm{ mod } p_{i+1} \le 2 \;(p_{n+1}=p_1)\)。
• 序列 \(p_1,p_2, \ldots,p_n\) 是一个好的序列。

现在需要你统计所有长度为 \(n\) 的好的序列中，有多少个是完美的序列。

输出满足条件的序列个数对 \(10^9+7\) 取模的结果。

输入描述

一行一个整数 \(n\) 代表序列的长度。

输出描述

一行一个整数代表完美的序列的数量。

样例 #1

样例输入 #1

4

样例输出 #1

16

满足条件的排列有：

1 2 4 3 
1 3 2 4 
1 4 2 3 
1 4 3 2 
2 1 4 3 
2 3 1 4 
2 4 1 3 
2 4 3 1 
3 1 2 4 
3 1 4 2 
3 2 1 4 
3 2 4 1 
4 1 3 2 
4 2 3 1 
4 3 1 2 
4 3 2 1

样例 #2

样例输入 #2

5000

样例输出 #2

223385586

样例 #3

样例输入 #3

500000

样例输出 #3

891419318

数据范围

• 对 \(20\%\) 的数据，\(n\le 10\) ;
• 对另外 \(40\%\) 的数据，\(n\le 5\times 10^3\) ;
• 对另外 \(20\%\) 的数据，\(n\le 5\times 10^5\) ;
• 对所有数据，\(1\le n \le 10^6\).

原题：P10744 [SEERC2020] Modulo Permutations

首先我们发现下面几条关键性质：

• 1,2 前面可以填任意数（其实 3 也可以）。
• 用1,2 分割排列，每一部分单调递减。

第一个性质是平凡的，第二个性质可以用反证法。假如存在 p**i<p**i+1，则 pi mod pi+1=pip**imodp**i+1=p**i，又因为 p**i>2，所以 p**imodp**i+1>2，不合法，故每一部分单调递减。

于是我们可以对类似 xx...xx1yy...yy2 的排列计数。我们称 x 部分为第一部分，y 部分为第二部分。

然后可以 dp，枚举第一部分的最前面的元素 i，然后尝试添加比它大的元素 j 到前面去。根据题目的约束，需要满足jmodi≤2，这样的 (i,j) 总数数量类似调和级数，为 O(nlogn) 级别。

然后考虑j−1∼i 这一部分是一个递减，只能放到第二部分去。那么这个时候发现第一部分的第一个元素为 j，第二部分的第一个元素为j−1，并且这种情况出现频繁。

考虑我们就设f(i) 表示第一部分第一个元素是 i，第二部分第一个元素是 i−1，可以按照前面的思路枚举 j 去刷表。

然后考虑如何求出答案，对于每一个方法，我们都有一种决策就是将i∼n 的元素都放到第一部分去。所以我们需要求：

k∑f(k*)

然后我们注意，可以对排列轮换，会得到另一个合法的排列，并且在之前的计算中没有出现（注意 2 的位置）。所以最后还需要乘上 nn。

注意一下转移的细节。时间复杂度 O(nlogn)。

//2024.10.17
//by white_ice
//P10744 [SEERC2020] Modulo Permutations
#include<bits/stdc++.h>
// #include"../../../need.cpp"
using namespace std;
#define int long long
#define itn long long
constexpr int oo = 5010000;
constexpr int mod = 1e9+7;
int n;int f[oo];
main(void){
    // fre();
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    if(n==1) {cout<<1; exit (0);}
    else if(n==2){cout<<2; exit (0);}
    f[0]=2;
    for(int i=n;i>2;i--){
        (f[i+1]+=f[0])%=mod;
        for(int dlt=0;dlt<=2;dlt++)
            for(int pet=i;pet+dlt<=n;pet+=i)
                if(pet+dlt>=i+2)
                    (f[i+1]+=f[pet+dlt])%=mod;
    }
    int out = f[0];
    for(int i=4;i<=n;i++) out=(out+f[i])%mod;
    cout << (out*n)%mod << '\n';
    exit(0);
}

C. B - Game

时间限制: 1 s   内存限制: 128 MB   测评类型: 传统型

---

题目描述

众所周知，zfy2006 切题就像切小菜，他的同学 ShuKuang 担心他的身体状况，奉劝 zfy2006 不要再卷了，没想到 zfy2006 说：“我就不休息能把我咋的，我卷死你。” 秉持着卷不过就加入的原则，ShuKuang 决定和他一起切题 (?)。

现在有 \(n\) 道题，第 \(i\) 道题有一个难度系数 ai\(a_i\)，一个题只能被切一次。ShuKuang 和 zfy2006 轮流行动，ShuKuang 先手。每次行动 ShuKuang 需要切掉至少一道题，zfy2006 需要切掉恰好一道题，直到所有题都被切完。

每个人最终的得分是自己切掉的题的难度系数之和。为了让 zfy2006 少卷一点，ShuKuang 想最大化自己的得分，然而 zfy2006 也想最大化自己的得分。请你告诉 ShuKuang，他最终能得多少分呢？

输入格式

从标准输入读入数据。

第一行一个正整数 \(n\) 。

第二行包含 \(n\) 个整数，第 \(i\) 个整数表示 \(a_i\) 。

输出格式

输出到标准输出。

一行一个整数，表示 ShuKuang 的最终得分。

样例输入1

5
7 10 -5 -2 -4

样例输出1

13

样例解释1

切题的过程如下：

ShuKuang 切掉 \(\{7, 10\}\)

zfy2006 切掉 \(-2\)

ShuKuang 切掉 \(\{-4\}\)

zfy2006 切掉 \(-5\)

ShuKuang 的得分为 \(7 + 10 + (-4) = 13\)

样例输入2

5
-6 -2 10 -7 -9

样例输出2

1

数据范围

对于 \(100\%\) 的数据，保证 \(1 \leq n \leq 10 ^ 5\)，\(-10 ^ 9 \leq a_i \leq 10 ^ 9\)。

• Subtask 1（10 分）：\(1\le n \le 10\)；
• Subtask 2（20 分）：\(1\le n \le 1000\)；
• Subtask 3（10 分）：\(1\le n \le 10^6\)，\(0 \le a_i \le 10^6\)；
• Subtask 4（20 分）：\(1\le n \le 10^6\)，\(-10^6 \le a_i \le 0\)；
• Subtask 5（40 分）：\(1\le n \le 10^6\)，\(-10^9 \le a_i \le 10^9\)。

奇妙小博弈，考虑总和不变，取最大就是对方取最小，直接dp一下负数中不连续的最小和即可

//2024.10.17
//by white_ice
#include<bits/stdc++.h>
// #include"../../../need.cpp"
using namespace std;
#define int long long 
#define itn long long 
constexpr itn oo = 1000006;
int n;
itn st[oo];
itn sum;
int sp[oo],cnt;
int f[oo];
main(void){
    // fre();
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;for (int i=1;i<=n;i++)cin >> st[i],sum+=st[i];
    if (n==1) {cout << st[1] << '\n';exit (0);}
    sort(st+1,st+n+1,greater<int>());
    itn i;
    for (i=2;i<=n;i++)if (st[i]<=0) break;
    for (i;i<=n;i++)sp[++cnt] = st[i];
    sort(sp+1,sp+cnt+1);
    priority_queue<int,vector<int>,greater<int>> que;
    f[1] = sp[1];
    f[2] = sp[2];
    que.push(f[1]);
    for (int i=3;i<=cnt;i++){
        f[i] = que.top()+sp[i];
        que.push(f[i-1]);
    }
    int minn = 0x3f3f3f;
    for (itn i=1;i<=cnt;i++){minn = min(f[i],minn);}
    cout << sum-minn << '\n';
    exit (0);
}

D. 加冕

时间限制: 1 s   内存限制: 256 MB   测评类型: 传统型

---

题目描述

小 Y 最近加冕为西班牙皇帝了！

小 Y 想跟你分享他多年奋斗的人生经验，虽然你表示完全不想理他，但还是被拖了过去。具体来说，小 Y 有一个威望值的属性，初始为 \(1\)，为了成为皇帝，他需要达到 \(K\) 的威望值。获得威望值的方法如下：假设小 Y 现在的威望值为 W，那么小 Y 每次会宣称一个数 \(V\)，满足 \(W · V | K\)，之后付出\(f(V)\) 的代价，并将 \(W\) 变成 \(W · V\)。当 \(W = K\) 时，小 Y 就胜利了。

\(f(V)\) 是攻下 \(V\) 的代价，定义\(p\) 为 \(V\) 的十进制各位数字之和加上 \(5\)，\(q\) 为\(V\) 的十进制各位数字之积加上 \(233\)，\(S\) 为 \(V\) 的质因子集合。每次可以付出 \(10\) 的代价使 \(q\) 变成 \(q + 1\)，或者选定 \(x ∈ S\) 并付出 \(1\) 的代价使 \(q\) 变成 \(q · x\)，直到 \(p|q\)，完成这个过程所需的最小代价就是\(f(V)\)。

这实在是太复杂了，你深刻地体会到皇帝不好当，现在你只想知道成为皇帝的最小代价是多少。

特别地，本题中 \(|\mu(K)| = 1\)，且为了方便，\(K\) 的最大质因子 \(≤ 10^6\)。

输入格式

一个数 \(K\)。

输出格式

一个数表示答案。

样例输入

2

样例输出

22

数据范围

子任务一（30pts）：\(K ≤ 100\)。

子任务二（30pts）：\(K\) 是质数。

子任务三（40pts）：无特殊限制。

对于所有的数据，\(K ≤ 10^{18}\)，\(|\mu(K)| = 1\)。

2 加冕 由于 10^18 内不同质因子个数最多只有 15，所以可以状压，那么只需要考虑子问题怎么做就行了。 显然可以按照 mod p 意义下的加法和乘法建立一个有向带权图，那么 “最小花费”=“到0 号点的最短路”，直接跑就可以了。

//2024.10.17
//by white_ice
#include<bits/stdc++.h>
// #include"../../../need.cpp"
using namespace std;
#define itn long long 
#define int long long
constexpr itn oo = 1003;
constexpr int op = 1000006;
int n,m;
itn pri_t[oo];
itn st_p[op],st_t[op],f[op];
itn g[oo],p[oo];
main(void){
    // fre();
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int i=2;i<=1000000;i++)
        if(n%i==0){n/=i;pri_t[++m]=i;}
    for(int i=0;i<(1<<m);i++){
        int x=1;
        for(int j=1;j<=m;j++)
            if(i&(1<<(j-1)))x=x*pri_t[j];
        st_t[i]=1;
        while(x){
            st_p[i]+=x%10;
            st_t[i]=st_t[i]*(x%10);
            x/=10;
        }
        st_p[i]+=5;
        (st_t[i]+=233)%=st_p[i];
        memset(g,0x3f3f3f,sizeof(g));
        g[st_t[i]]=0;
        for(int j=1;j<=4;j++){
            memcpy(p,g,sizeof(p));
            int tag=1;
            for(int k_2=1;k_2<=m;k_2++){
                if(!(i&(1<<(k_2-1)))) continue;
                for(int k=0;k<st_p[i];k++){
                    g[(k*pri_t[k_2])%st_p[i]]=min(g[(k*pri_t[k_2])%st_p[i]],g[k]+1);
                }
            }
            for(int k=0;k<st_p[i];k++)
                g[(k+1)%st_p[i]]=min(g[(k+1)%st_p[i]],g[k]+10);
            for(int k=0;k<st_p[i];k++) if(g[k]<p[k])tag=0;
            if(tag) break;
        }
        f[i] = g[0];
    }
    for(int i=0;i<(1<<m);i++)
        for(int j=(i-1)&i;j;j=(j-1)&i)
            f[i]=min(f[i],f[i^j]+f[j]);
    cout << f[(1<<m)-1] << '\n';
    exit (0);
}