第十一周 11.8-11.14

11.8

闲来无事补CF。

题目比较简单。点在于有一个大数比较可以用log弄掉。

算LCM要先除再乘。算log要先强转double。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cmath>
 5 using namespace std;
 6 typedef long long LL;
 7 
 8 LL gcd(LL a,LL b)
 9 {
10     return b?gcd(b,a%b):a;
11 }
12 
13 int main(void)
14 {
15     LL t,w,b;
16     scanf("%I64d%I64d%I64d",&t,&w,&b);
17     LL x,GCD=gcd(w,b),LCM=b/GCD*w;
18     if(log(double(w))+log(double(b))>log(double(t))+log(double(GCD))) x=min(min(w-1,b-1),t);
19     else x=t/LCM*min(w,b)+min(t%LCM,min(w-1,b-1));
20     GCD=gcd(x,t);
21     printf("%I64d/%I64d
",x/GCD,t/GCD);
22     return 0;
23 }

Aguin

11.9

什么都没干。

11.10

CF 592 D Super M

在树上找包含标记节点的最小子树。dfs最远点对。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 # define maxn 150100
 7 int cnt,headlist[maxn];
 8 int is[maxn],val[maxn];
 9 int d=0,A=maxn,B=maxn;
10 
11 struct node
12 {
13     int to,pre;
14 } edge[2*maxn];
15 
16 void add(int from,int to)
17 {
18     cnt++;
19     edge[cnt].pre=headlist[from];
20     edge[cnt].to=to;
21     headlist[from]=cnt;
22 }
23 
24 void dfs1(int pos,int fa,int dep)
25 {
26     for(int i=headlist[pos];i;i=edge[i].pre)
27     {
28         int to=edge[i].to;
29         if(to==fa) continue;
30         dfs1(to,pos,dep+1);
31         if(is[to]||val[to]) val[pos]+=2;
32         val[pos]+=val[to];
33     }
34     if(is[pos]||val[pos])
35     {
36         if(dep>d) {d=dep; A=pos;}
37         else if(dep==d) A=min(A,pos);
38     }
39     return;
40 }
41 
42 void dfs2(int pos,int fa,int dep)
43 {
44     if(dep>d) {d=dep; B=pos;}
45     else if(dep==d) B=min(B,pos);
46     for(int i=headlist[pos];i;i=edge[i].pre)
47     {
48         int to=edge[i].to;
49         if(to==fa||!is[to]&&!val[to]) continue;
50         dfs2(to,pos,dep+1);
51     }
52     return;
53 }
54 
55 int main(void)
56 {
57     int m,n;
58     scanf("%d%d",&n,&m);
59     for(int i=1;i<n;i++)
60     {
61         int u,v;
62         scanf("%d%d",&u,&v);
63         add(u,v); add(v,u);
64     }
65     int s;
66     for(int i=1;i<=m;i++)
67     {
68         int x; scanf("%d",&x);
69         is[s=x]=1;
70     }
71     dfs1(s,0,0);
72     d=0; dfs2(A,0,0);
73     printf("%d
%d
",min(A,B),val[s]-d);
74     return 0;
75 }

Aguin

11.11-11.13

什么都没干。

11.14

补个BC。

HDU 5564 Clarke and digits

每次都是用到矩阵去搜板。这样不好- -

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 typedef long long LL;
 6 const LL mod=1e9+7;
 7 const int n=77;
 8 int a[77]={
 9     0,0,0,0,0,0,0,
10     0,1,0,0,0,0,0,
11     0,0,1,0,0,0,0,
12     0,0,0,1,0,0,0,
13     0,0,0,0,1,0,0,
14     0,0,0,0,0,1,0,
15     0,0,0,0,0,0,1,
16     1,0,0,0,0,0,0,
17     0,1,0,0,0,0,0,
18     0,0,1,0,0,0,0,
19     1,2,2,1,1,1,1
20 };
21 
22 struct Mat {
23     LL mat[77][77];
24     Mat(){memset(mat,0,sizeof(mat));}
25 };
26 
27 Mat operator * (Mat a, Mat b) {
28     Mat c;
29     int i, j, k;
30     for(k = 0; k < n; ++k) {
31         for(i = 0; i < n; ++i) {
32             for(j = 0; j < n; ++j) {
33                 c.mat[i][j] += a.mat[i][k] * b.mat[k][j] % mod ;
34                 c.mat[i][j] %= mod ;
35             }
36         }
37     }
38     return c;
39 }
40 
41 Mat operator ^ (Mat a, int k) {
42     Mat c;
43     int i, j;
44     for(i = 0; i < n; ++i)
45         for(j = 0; j < n; ++j)
46             c.mat[i][j] = (i == j);
47 
48     for(; k; k >>= 1) {
49         if(k&1) c = c*a;
50         a = a*a;
51     }
52     return c;
53 }
54 
55 int main(void)
56 {
57     int T; scanf("%d",&T);
58     while(T--)
59     {
60         int l,r,k;
61         scanf("%d%d%d",&l,&r,&k);
62         Mat t;
63         for(int i=0;i<=6;i++) t.mat[70+i][70+i]++;
64         for(int i=0;i<=9;i++)
65         {
66             for(int j=0;j<=6;j++)
67             {
68                 for(int p=0;p<=9;p++)
69                 {
70                     if(i+p==k) continue;
71                     int q=(j*3%7+p)%7;
72                     int pos1=7*i+j,pos2=7*p+q;
73                     t.mat[pos2][pos1]++;
74                     t.mat[70+q][pos1]++;
75                 }
76             }
77         }
78         Mat L,R=t^(r-1);
79         if(l!=1) L=t^(l-2);
80         LL ans1=0,ans2=0;
81         for(int i=0;i<n;i++)
82         {
83             ans1=(ans1+L.mat[70][i]*a[i]%mod)%mod;
84             ans2=(ans2+R.mat[70][i]*a[i]%mod)%mod;
85         }
86         printf("%I64d
",(ans2-ans1+mod)%mod);
87     }
88     return 0;
89 }

Aguin