牛客小白月赛6

 1 /**
 2 同样的遍历，若无特殊要求，用bfs！
 3 dfs要保存、返回函数中间状态，
 4 dfs比bfs慢不少，如一棵有很多分叉的树。
 5 
 6 题解的方法
 7 */
 8 
 9 #include <cstdio>
10 #include <cstdlib>
11 #include <cmath>
12 #include <cstring>
13 #include <time.h>
14 #include <string>
15 #include <set>
16 #include <map>
17 #include <list>
18 #include <stack>
19 #include <queue>
20 #include <vector>
21 #include <bitset>
22 #include <ext/rope>
23 #include <algorithm>
24 #include <iostream>
25 using namespace std;
26 #define ll long long
27 #define minv 1e-6
28 #define inf 1e9
29 #define pi 3.1415926536
30 #define E  2.7182818284
31 const ll mod=1e9+7;//998244353
32 const int maxn=1e6+10;
33 
34 struct node
35 {
36     int d;
37     node* next;
38 }*e[maxn],*p;
39 
40 int q[maxn],l[maxn];
41 bool vis[maxn];
42 int head,tail;
43 
44 void bfs(int d)
45 {
46     head=0,tail=1;
47     q[1]=d,l[1]=1;
48     memset(vis,0,sizeof(vis));
49     while (head<tail)
50     {
51         head++;
52         p=e[ q[head] ];
53         while (p)
54         {
55             if (!vis[p->d])
56             {
57                 vis[p->d]=1;
58                 tail++;
59                 q[tail]=p->d;
60                 l[tail]=l[head]+1;
61             }
62             p=p->next;
63         }
64     }
65 }
66 
67 int main()
68 {
69     int n,i,x,y;
70     scanf("%d",&n);
71     for (i=1;i<=n;i++)
72         e[i]=NULL;
73     for (i=1;i<n;i++)
74     {
75         scanf("%d%d",&x,&y);
76         p=(node*) malloc (sizeof(node*));
77         p->d=y;
78         p->next=e[x];
79         e[x]=p;
80 
81         p=(node*) malloc (sizeof(node*));
82         p->d=x;
83         p->next=e[y];
84         e[y]=p;
85     }
86     bfs(1);
87     bfs(q[tail]);
88     printf("%d",l[tail]);
89 
90     return 0;
91 }

  1 /*
  2 dp
  3 */
  4 #include <cstdio>
  5 #include <cstdlib>
  6 #include <cmath>
  7 #include <cstring>
  8 #include <time.h>
  9 #include <string>
 10 #include <set>
 11 #include <map>
 12 #include <list>
 13 #include <stack>
 14 #include <queue>
 15 #include <vector>
 16 #include <bitset>
 17 #include <ext/rope>
 18 #include <algorithm>
 19 #include <iostream>
 20 using namespace std;
 21 #define ll long long
 22 #define minv 1e-6
 23 #define inf 1e9
 24 #define pi 3.1415926536
 25 #define E  2.7182818284
 26 const ll mod=1e9+7;//998244353
 27 const int maxn=1000000+10;
 28 
 29 //用vector比用node稍微慢一点，但是也许vector更方便
 30 
 31 struct node
 32 {
 33     int d;
 34     node* next;
 35 }*point[maxn];
 36 
 37 //vector<int>e[maxn];
 38 bool vis[maxn]={0};
 39 int r;
 40 
 41 //返回的是目前以d为根节点(之后会变)的最长链
 42 int dfs(int d)
 43 {
 44     int value=0,v1=0,v2=0,v;
 45     int dd;
 46     node* p;
 47 //    vector<int>::iterator i;
 48     vis[d]=1;
 49 //    for (i=e[d].begin();i!=e[d].end();i++)
 50     p=point[d];
 51     while (p)
 52     {
 53 //        dd=*i;
 54         dd=p->d;
 55         if (!vis[dd])
 56         {
 57             v=dfs(dd);
 58             value=max(value,v);
 59             if (v>v1)
 60             {
 61                 v2=max(v1,v2);
 62                 v1=v;
 63             }
 64             else if (v>v2)
 65                 v2=v;
 66         }
 67         p=p->next;
 68     }
 69     //d为根节点，左右各连接一条链，即求以d儿子为根节点的最长的两条链
 70     r=max(r,v1+v2+1);
 71     return value+1;
 72 }
 73 
 74 int main()
 75 {
 76     int n,x,y,i;
 77     node* p;
 78     scanf("%d",&n);
 79     for (i=1;i<=n;i++)
 80         point[i]=NULL;
 81     for (i=1;i<n;i++)
 82     {
 83         scanf("%d%d",&x,&y);
 84         p=(struct node *) malloc (sizeof(node));
 85         p->d=y;
 86         p->next=point[x];
 87         point[x]=p;
 88 
 89         p=(struct node *) malloc (sizeof(node));
 90         p->d=x;
 91         p->next=point[y];
 92         point[y]=p;
 93 //        e[x].push_back(y);
 94 //        e[y].push_back(x);
 95     }
 96     i=dfs(1);
 97     printf("%d",r);
 98     return 0;
 99 }
100 /*
101 4
102 1 2
103 1 3
104 1 4
105 */

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <time.h>
 6 #include <string>
 7 #include <set>
 8 #include <map>
 9 #include <list>
10 #include <stack>
11 #include <queue>
12 #include <vector>
13 #include <bitset>
14 #include <ext/rope>
15 #include <algorithm>
16 #include <iostream>
17 using namespace std;
18 #define ll long long
19 #define minv 1e-6
20 #define inf 1e9
21 #define pi 3.1415926536
22 #define E  2.7182818284
23 const ll mod=1e9+7;//998244353
24 const int maxn=1e6+10;
25 
26 vector<int>st;
27 char mode[10];
28 
29 /*
30 注意对于存在的指纹，相邻指纹距离>k
31 对于一个数x，只有指纹中大于等于x的第一个数y 和 该数y的上一个数z 才有可以与x的距离小于等于k
32 */
33 
34 int main()
35 {
36     vector<int>::iterator pos;
37     int m,k,x;
38     scanf("%d%d",&m,&k);
39     while (m--)
40     {
41         scanf("%s%d",mode,&x);
42         if (strcmp(mode,"add")==0)
43         {
44             //lower_bound*(>=)相当于二分，相当方便！！！ upper_bound(>)
45             pos=lower_bound(st.begin(),st.end(),x);
46             if ((pos>=st.end() || *pos-x>k) &&
47                 ((st.begin()==st.end() || pos-1<st.begin()) || x - *(pos-1)>k))
48                     st.insert(pos,x);
49         }
50         else if (strcmp(mode,"del")==0)
51         {
52             pos=lower_bound(st.begin(),st.end(),x);
53             if (!(pos>=st.end() || *pos-x>k))
54                 st.erase(pos);
55             if (!((st.begin()==st.end() || pos-1<st.begin()) || x - *(pos-1)>k))
56                 st.erase(pos-1);
57         }
58         else
59         {
60             pos=lower_bound(st.begin(),st.end(),x);
61             if ((pos>=st.end() || *pos-x>k) &&
62                 ((st.begin()==st.end() || pos-1<st.begin()) || x - *(pos-1)>k))
63                     printf("No\n");
64             else
65                     printf("Yes\n");
66         }
67     }
68     return 0;
69 }
70 /*
71 14 1
72 add 1
73 add 3
74 add 5
75 add 7
76 add 9
77 query 2
78 del 2
79 query 2
80 query 8
81 del 8
82 query 8
83 query 6
84 del 5
85 query 5
86 */

 1 /*
 2 最小生成树裸题
 3 边少，用Kruskal
 4 */
 5 #include <cstdio>
 6 #include <cstdlib>
 7 #include <cmath>
 8 #include <cstring>
 9 #include <time.h>
10 #include <string>
11 #include <set>
12 #include <map>
13 #include <list>
14 #include <stack>
15 #include <queue>
16 #include <vector>
17 #include <bitset>
18 #include <ext/rope>
19 #include <algorithm>
20 #include <iostream>
21 using namespace std;
22 #define ll long long
23 #define minv 1e-6
24 #define inf 1e9
25 #define pi 3.1415926536
26 #define E  2.7182818284
27 const ll mod=1e9+7;//998244353
28 const int maxn=1e5+10;
29 
30 struct node
31 {
32     int a,b,v;
33 }e[maxn*5];//注意
34 int fa[maxn];
35 
36 int getfather(int d)
37 {
38     if (fa[d]==d)
39         return d;
40     fa[d]=getfather(fa[d]);
41     return fa[d];
42 }
43 
44 int cmp(node a,node b)
45 {
46     return a.v<b.v;
47 }
48 
49 int g=0,b[maxn];
50 
51 int main()
52 {
53     int n,m,i,c=0,x,y,sum=0;
54     scanf("%d%d",&n,&m);
55     for (i=1;i<=n;i++)
56         fa[i]=i;
57     for (i=1;i<=m;i++)
58         scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].v);
59     sort(e+1,e+m+1,cmp);
60     c=n-1;
61     i=0;
62     while (c--)
63     {
64         do
65         {
66             i++;
67             x=getfather(e[i].a);
68             y=getfather(e[i].b);
69         }
70         while (x==y);
71         fa[x]=y;
72         sum+=e[i].v;
73             g++;
74             b[g]=e[i].v;
75     }
76     printf("%d",sum);
77 
78     sort(b+1,b+g+1);
79     printf("\ng=%d\n",g);
80     for (i=1;i<=g;i++)
81         printf("%d\n",b[i]);
82     return 0;
83 }
84 /*
85 4 5
86 1 2 3
87 1 3 1
88 1 2 3
89 2 3 4
90 1 4 5
91 */

  1 /*
  2 最小生成树裸题
  3 Prim + 堆优化
  4 */
  5 #include <cstdio>
  6 #include <cstdlib>
  7 #include <cmath>
  8 #include <cstring>
  9 #include <time.h>
 10 #include <string>
 11 #include <set>
 12 #include <map>
 13 #include <list>
 14 #include <stack>
 15 #include <queue>
 16 #include <vector>
 17 #include <bitset>
 18 #include <ext/rope>
 19 #include <algorithm>
 20 #include <iostream>
 21 using namespace std;
 22 #define ll long long
 23 #define minv 1e-6
 24 #define inf 1e9
 25 #define pi 3.1415926536
 26 #define E  2.7182818284
 27 const ll mod=1e9+7;//998244353
 28 const int maxn=1e5+10;
 29 
 30 int dist[maxn];
 31 struct rec
 32 {
 33     int d,dist;
 34 };
 35 
 36 struct cmp1
 37 {
 38     bool operator() (rec a,rec b)
 39     {
 40         return a.dist>b.dist; //最小堆 > 而不是 <
 41     }
 42 };
 43 
 44 ///注意，若只用d,不用dist，结果不对！！！
 45 priority_queue<rec,vector<rec>,cmp1 >st;
 46 
 47 struct node
 48 {
 49     int d,len;
 50     node* next;
 51 }*e[maxn],*p;
 52 bool vis[maxn]={0};
 53 
 54 int g=0,b[maxn];
 55 
 56 int main()
 57 {
 58     int n,m,i,d,x,y,z,sum=0;
 59     vector<pair<int,int> >::iterator j;
 60     scanf("%d%d",&n,&m);
 61     for (i=1;i<=n;i++)
 62         e[i]=NULL;
 63     for (i=1;i<=m;i++)
 64     {
 65         scanf("%d%d%d",&x,&y,&z);
 66         p=(node*) malloc (sizeof(node));
 67         p->d=y;
 68         p->len=z;
 69         p->next=e[x];
 70         e[x]=p;
 71 
 72         p=(node*) malloc (sizeof(node));
 73         p->d=x;
 74         p->len=z;
 75         p->next=e[y];
 76         e[y]=p;
 77     }
 78     for (i=1;i<=n;i++)
 79         dist[i]=inf;
 80     dist[1]=0;
 81     st.push({1,0});
 82     while (1)
 83     {
 84         while (!st.empty() && vis[st.top().d])
 85             st.pop();
 86         if (st.empty())
 87             break;
 88         d=st.top().d;
 89         st.pop();
 90         vis[d]=1;
 91         sum+=dist[d];
 92         p=e[d];
 93         while (p)
 94         {
 95             if (dist[p->d]>p->len)
 96             {
 97                 dist[p->d]=p->len;
 98                 st.push({p->d,p->len});
 99             }
100             p=p->next;
101         }
102     }
103     printf("%d",sum);
104     return 0;
105 }

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <time.h>
 6 #include <string>
 7 #include <set>
 8 #include <map>
 9 #include <list>
10 #include <stack>
11 #include <queue>
12 #include <vector>
13 #include <bitset>
14 #include <ext/rope>
15 #include <algorithm>
16 #include <iostream>
17 using namespace std;
18 #define ll long long
19 #define minv 1e-6
20 #define inf 1e9
21 #define pi 3.1415926536
22 #define E  2.7182818284
23 const ll mod=1e9+7;//998244353
24 const int maxn=1e5+10;
25 
26 vector<pair<int,int> >e[maxn];
27 int dist[maxn],q[maxn];
28 bool vis[maxn]={0};
29 
30 int main()
31 {
32     int n,m,d,t,i,x,y,z,head,tail;
33     vector<pair<int,int> >::iterator j;
34     scanf("%d%d%d%d",&n,&m,&d,&t);
35     for (i=1;i<=m;i++)
36     {
37         scanf("%d%d%d",&x,&y,&z);
38         e[x].push_back(make_pair(y,z));
39         e[y].push_back(make_pair(x,z));
40     }
41     for (i=1;i<=n;i++)
42         dist[i]=inf;
43     dist[d]=0;
44     //я╜╩╥╤сап
45     head=0,tail=1;
46     q[1]=d;
47     while (head!=tail)
48     {
49         head=(head+1)%n;
50         d=q[head];
51         for (j=e[d].begin();j!=e[d].end();j++)
52             if (dist[j->first]>dist[d]+j->second)
53             {
54                 dist[j->first]=dist[d]+j->second;
55                 if (!vis[j->first])
56                 {
57                     vis[j->first]=1;
58                     tail=(tail+1)%n;
59                     q[tail]=j->first;
60                 }
61             }
62         vis[d]=0;
63     }
64     if (dist[t]==inf)
65         printf("-1");
66     else
67         printf("%d",dist[t]);
68     return 0;
69 }

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <time.h>
 6 #include <string>
 7 #include <set>
 8 #include <map>
 9 #include <list>
10 #include <stack>
11 #include <queue>
12 #include <vector>
13 #include <bitset>
14 #include <ext/rope>
15 #include <algorithm>
16 #include <iostream>
17 using namespace std;
18 #define ll long long
19 #define minv 1e-6
20 #define inf 1e9
21 #define pi 3.1415926536
22 #define E  2.7182818284
23 const ll mod=1e9+7;//998244353
24 const int maxn=1e5+10;
25 
26 struct rec
27 {
28     int d,dist;
29 };
30 
31 struct cmp
32 {
33     bool operator() (rec a,rec b)
34     {
35         return a.dist>b.dist;
36     }
37 };
38 
39 priority_queue<rec,vector<rec>,cmp>st;
40 
41 struct node
42 {
43     int d,len;
44     node* next;
45 }*e[maxn],*p;
46 bool vis[maxn]={0};
47 int dist[maxn];
48 
49 int main()
50 {
51     int n,m,d,t,i,x,y,z;
52     scanf("%d%d%d%d",&n,&m,&d,&t);
53     for (i=1;i<=n;i++)
54         e[i]=NULL;
55     for (i=1;i<=m;i++)
56     {
57         scanf("%d%d%d",&x,&y,&z);
58         p=(node*) malloc (sizeof(node));
59         p->d=y;
60         p->len=z;
61         p->next=e[x];
62         e[x]=p;
63 
64         p=(node*) malloc (sizeof(node));
65         p->d=x;
66         p->len=z;
67         p->next=e[y];
68         e[y]=p;
69     }
70     for (i=1;i<=n;i++)
71         dist[i]=inf;
72     dist[d]=0;
73     st.push({d,0});
74     while (d!=t)
75     {
76         while (!st.empty() && vis[st.top().d])
77             st.pop();
78         if (st.empty())
79             break;
80         d=st.top().d;
81         st.pop();
82         p=e[d];
83         while (p)
84         {
85             if (dist[p->d]>dist[d]+p->len)
86             {
87                 dist[p->d]=dist[d]+p->len;
88                 st.push({p->d,dist[p->d]});
89             }
90             p=p->next;
91         }
92     }
93     if (dist[t]==inf)
94         printf("-1");
95     else
96         printf("%d",dist[t]);
97     return 0;
98 }

 1 /*
 2 t(i)->t(i+1) 一次多元函数 矩阵快速幂是套路
 3 
 4 n个变量和常数，则创建(n+1)*(n+1)的矩阵
 5 t(i+1)=t(i)+f(i)
 6 f(i+1)=f(i)*k+p
 7 见目录图片
 8 */
 9 #include <cstdio>
10 #include <cstdlib>
11 #include <cmath>
12 #include <cstring>
13 #include <time.h>
14 #include <string>
15 #include <set>
16 #include <map>
17 #include <list>
18 #include <stack>
19 #include <queue>
20 #include <vector>
21 #include <bitset>
22 #include <ext/rope>
23 #include <algorithm>
24 #include <iostream>
25 using namespace std;
26 #define ll long long
27 #define minv 1e-6
28 #define inf 1e9
29 #define pi 3.1315926536
30 #define E  2.7182818283
31 const ll mod=1e9+7;//998233353
32 const int maxn=1e5+10;
33 
34 //要加{}
35 ll a[3][3]={
36 {1,0,0},
37 {0,0,0},
38 {0,0,1}
39 };
40 ll b[3][3],c[3][3];
41 
42 int main()
43 {
44     int n,i,j,k;
45     ll K,p;
46     scanf("%d%lld%lld",&n,&K,&p);
47     a[0][1]=a[1][1]=K;
48     a[0][2]=a[1][2]=p;
49     for (i=0;i<3;i++)
50         for (j=0;j<3;j++)
51             b[i][j]=(i==j);
52     n--;
53     while (n)
54     {
55         if (n & 1)
56         {
57             for (i=0;i<3;i++)
58                 for (j=0;j<3;j++)
59                     c[i][j]=b[i][j],b[i][j]=0;
60             for (i=0;i<3;i++)
61                 for (j=0;j<3;j++)
62                     for (k=0;k<3;k++)
63                         b[i][j]=(b[i][j]+c[i][k]*a[k][j])%mod;
64         }
65 
66         for (i=0;i<3;i++)
67             for (j=0;j<3;j++)
68                 c[i][j]=a[i][j],a[i][j]=0;
69         for (i=0;i<3;i++)
70             for (j=0;j<3;j++)
71                 for (k=0;k<3;k++)
72                     a[i][j]=(a[i][j]+c[i][k]*c[k][j])%mod;
73         n>>=1;
74     }
75     printf("%lld",(b[0][0]+b[0][1]+b[0][2])%mod);
76     return 0;
77 }