8.12总结前日和今日

今天是组队赛的第三天，第一次打div2的比赛，表示真的有点难，还是有很长的路要走啊

D题：（最小生成树）

题意：

n个点，每个点有一个权值，每两条边的权值为边的两个点的权值的gcd，求这幅图的最大生成树

解法：

首先处理出每个点权值的所有公因数，以所有的公因数为点，建一条点编号与其公因数的边，之后从大到小枚举每条边，跑一遍最大生成树即可

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<vector>
 4 #include<cmath>
 5 using namespace std;
 6 typedef long long ll;
 7 const int maxn = 1e5 + 5;
 8 vector<int>g[maxn];
 9 int p[maxn];
10 int n;
11 
12 int find(int x) {
13     return (p[x] == x) ? x : (p[x] = find(p[x]));
14 }
15 
16 int main() {
17     freopen("dream.in", "r", stdin);
18     int T; scanf("%d", &T);
19     int kase = 1;
20     while (T--) {
21         for (int i = 0; i <= maxn; i++) {
22             g[i].clear();
23             p[i] = i;
24         }
25 
26         scanf("%d", &n);
27         for (int i = 1; i <= n; i++) {
28             int x; scanf("%d", &x);
29             for (int j = 1; j <= sqrt(x); j++) {
30                 if (x%j == 0) {
31                     g[j].push_back(i);
32                     if (x / j != j)g[x / j].push_back(i);
33                 }
34             }
35         }
36 
37         ll ans = 0;
38         for (int i = maxn - 5; i >= 1; i--) {
39             if (g[i].empty())continue;
40             for (int j = 0; j < g[i].size()-1; j++) {
41                 int x = find(g[i][j]);
42                 int y = find(g[i][j + 1]);
43                 if (x != y) {
44                     p[y] = x;
45                     ans += i;
46                 }
47             }
48         }
49         printf("Case %d: %d
", kase++, ans);
50     }
51     return 0;
52 }

8.12场地址

J题：（二次剩余定理）

题意：有一个位数超过1e6的数，问这个数是否是完全平方数

解法：

取20个大质数，然后检查 $x^{2} mod p == n$ 是否有解即可。

根据二次剩余，这等价于 $n^{frac{p-1}{2}} mod p==1$ 。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cstdlib>
 5 using namespace std;
 6 typedef long long ll;
 7 const int N=1000010;
 8 int n,i,cnt;char a[N];
 9 bool isprime(int n){
10     for(int i=2;i<=n/i;i++)if(n%i==0)return 0;
11     return 1;
12 }
13 ll powmod(ll a,ll b,ll P){
14     ll t=1;
15     for(;b;b>>=1,a=a*a%P)if(b&1)t=t*a%P;
16     return t;
17 }
18 bool work(ll n,ll p){
19     if(n==0||n==1)return 1;
20     if(powmod(n,p>>1,p)!=1)return 0;
21     return 1;
22 }
23 bool check(int P){
24     ll ret=0;
25     for(int i=1;i<=n;i++)ret=(ret*10+a[i]-'0')%P;
26     return work(ret,P);
27 }
28 int main(){
29     scanf("%s",a+1);
30     n=strlen(a+1);
31     for(i=1000000000;;i++)if(isprime(i)){
32         if(!check(i))return puts("No"),0;
33         cnt++;
34         if(cnt>=20)return puts("Yes"),0;
35     }
36 }

题意：（打印）

有一个长为L的母串和若干个长为n的子串，每次向前移动会增加一个单位的时间，换行也会增加一个单位的时间，问需要多个单位的时间才可以将整篇文章打印完

解法：

预处理出 $large f[i][j]$ 表示模式串第 $large i$ 个位置之后第一个字符 $large j$ 的位置，对于每一行计算需要的最大时间即可。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=1000010;
 6 typedef long long ll;
 7 int L,n,i,j,cur,f[100010][130];
 8 char a[N],b[N];
 9 ll ans;
10 int main(){
11     gets(a);
12     L=strlen(a);
13     for(i=L-1;~i;i--)f[L][a[i]]=i;
14     for(i=L-1;~i;i--){
15         for(j=0;j<130;j++)f[i][j]=f[i+1][j];
16         f[i][a[i]]=i;
17     }
18     while(gets(b)){
19         n=strlen(b);
20         int tmp=0;
21         for(i=0;i<n;i++){
22             char x=b[i];
23             if(x==' ')continue;
24             int nxt=((f[(cur+i)%L][x]-(cur+i))%L+L)%L;
25             if(nxt>tmp)tmp=nxt;
26         }
27         tmp++;
28         ans+=tmp;
29         cur=(cur+tmp)%L;
30     }
31     printf("%lld",ans);
32 }