526互联

AtCoder Beginner Contest 309

发布时间 2023-07-09 15:07:37作者: 江上舟摇

A:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<string>
 6 #include<vector>
 7 #include<stack>
 8 #include<bitset>
 9 #include<cstdlib>
10 #include<cmath>
11 #include<set>
12 #include<list>
13 #include<deque>
14 #include<map>
15 #include<queue>
16 #include <iomanip>
17 #include<ctime>
18 using namespace std;
19 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
20 #define TLE (double)clock()/CLOCKS_PER_SEC<=0.95
21 #define int long long 
22 #define double long double
23 #define endl '\n'
24 #define inf LLONG_MAX
25 #define iinf INT_MAX
26 typedef pair<int,int> PII;
27 const double PI = acos(-1.0);
28 const double eps = 1e-6;
29 const int INF = 0x3f3f3f3f;
30 const int N = 5;
31 signed main()
32 {
33     IOS;
34     int x,y;
35     cin>>x>>y;
36     if((x+1==y||y+1==x)&&x!=3&&x!=6&&x!=9)
37     {
38         cout<<"Yes"<<endl;
39     }
40     else
41     {
42         cout<<"No"<<endl;
43     }
44     return 0;
45 }

B:毒瘤题

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<iostream>
  5 #include<string>
  6 #include<vector>
  7 #include<stack>
  8 #include<bitset>
  9 #include<cstdlib>
 10 #include<cmath>
 11 #include<set>
 12 #include<list>
 13 #include<deque>
 14 #include<map>
 15 #include<queue>
 16 #include <iomanip>
 17 #include<ctime>
 18 using namespace std;
 19 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 20 #define TLE (double)clock()/CLOCKS_PER_SEC<=0.95
 21 #define int long long 
 22 #define double long double
 23 #define endl '\n'
 24 #define inf LLONG_MAX
 25 #define iinf INT_MAX
 26 typedef pair<int,int> PII;
 27 const double PI = acos(-1.0);
 28 const double eps = 1e-6;
 29 const int INF = 0x3f3f3f3f;
 30 const int N = 1e2+10;
 31 int n,b[N][N];
 32 int c[N][N];
 33 char a[N][N];
 34 signed main()
 35 {
 36     IOS;
 37     cin>>n;
 38     for(int i=1;i<=n;i++)
 39     {
 40         for(int j=1;j<=n;j++)
 41         {
 42             cin>>a[i][j];
 43             b[i][j]=a[i][j]-'0';
 44             c[i][j]=a[i][j]-'0';
 45         }
 46     }
 47     for(int i=1;i<=n;i++)
 48     {
 49         for(int j=1;j<=n;j++)
 50         {
 51             // if(i==1||i==n||j==1||j==n)
 52             // {
 53                 // if(j==1)
 54                 // {
 55                     // if(i+1<=n)    b[i][j]=c[i+1][j];
 56                 // }
 57                 // else if(j==n&&i-1>=1)    b[i][j]=c[i-1][j];
 58                 // else     
 59                 // {
 60                     // if(j-1>=1)
 61                     // b[i][j]=c[i][j-1];        
 62                     // else    b[i][j]=c[i][j];
 63                 // }
 64             // }
 65             // if(i==1&&j==1)    b[i][j]=c[i+1][j];
 66             // else if(i==1&&j==n)    b[i][j]=c[i][j-1];;
 67             // if(i==1)
 68             // {
 69                 // if(j==1)
 70                 // {
 71                     // b[i][j]=c[i+1][j];
 72                 // }
 73                 // else if(j==n)
 74                 // {
 75                     // b[i][j]=c[i][j-1];
 76                 // }
 77                 // else b[i][j]=c[i][j-1];
 78             // }
 79             if(i==1&&j==1)    b[i][j]=c[i+1][j];
 80             else if(i==1&&j==n)    b[i][j]=c[i][j-1];
 81             else if(i==n&&j==1)    b[i][j]=c[i][j+1];
 82             else if(i==n&&j==n)    b[i][j]=c[i-1][j];
 83             // else if(i==n)
 84             // {
 85                 // if(j==1)
 86                 // {
 87                     // b[i][j]=c[i][j+1];
 88                 // }
 89                 // else if(j==n)
 90                 // {    
 91                     // b[i][j]=c[i-1][j];
 92                 // }
 93                 // else b[i][j]=c[i][i+1];
 94             // }
 95             // else if(j==1)
 96             // {
 97                 // if(i==1)
 98                 // {
 99                     // b[i][j]=c[i+1][j];
100                 // }
101                 // else if(i==n)
102                 // {
103                     // b[i][j]=c[i][j+1];
104                 // }
105                 // else b[i][j]=c[i][j+1];
106             // }    
107         // else if(j==n)
108         // {
109             // if(i==n)    b[i][j]=c[i-1][j];
110             // else if(i==1)    b[i][j]=c[i][j-1];
111             // else b[i][j]=c[i][j-1];
112         // }
113         else if(i==1)    b[i][j]=c[i][j-1];
114         else if(i==n)    b[i][j]=c[i][j+1];
115         else if(j==1)    b[i][j]=c[i+1][j];
116         else if(j==n)    b[i][j]=c[i-1][j];
117         }
118     }
119     for(int i=1;i<=n;i++)
120     {
121         for(int j=1;j<=n;j++)
122         {
123             cout<<b[i][j];
124         }
125         cout<<endl;
126     }
127     return 0;
128 }

C：给定n种食用的天数和片数，规定从医生给他开药的那天算起，哪一天第一次可以吃小于等于k片剂量的药片

我们尽量让能吃的药先吃完，然后统计总的药片数量，因为你吃的话就得从这些药片中来吃，然后就找具体哪一天就可以了

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<string>
 6 #include<vector>
 7 #include<stack>
 8 #include<bitset>
 9 #include<cstdlib>
10 #include<cmath>
11 #include<set>
12 #include<list>
13 #include<deque>
14 #include<map>
15 #include<queue>
16 #include <iomanip>
17 #include<ctime>
18 using namespace std;
19 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
20 #define TLE (double)clock()/CLOCKS_PER_SEC<=0.95
21 #define int long long 
22 #define double long double
23 #define x first
24 #define y second 
25 #define endl '\n'
26 #define inf LLONG_MAX
27 #define iinf INT_MAX
28 typedef pair<int,int> PII;
29 const double PI = acos(-1.0);
30 const double eps = 1e-6;
31 const int INF = 0x3f3f3f3f;
32 const int N = 3e5+10;
33 int n,k;
34 PII a[N];
35 signed main()
36 {
37     IOS;
38     int sum=0;
39     cin>>n>>k;
40     for(int i=1;i<=n;i++)
41     {
42         cin>>a[i].x>>a[i].y;
43         sum+=a[i].y;
44     }
45     sort(a+1,a+1+n);
46     int cnt=0;
47     if(sum<=k)
48     {
49         cout<<1<<endl;
50         return 0;
51     }
52     for(int i=1;i<=n;i++)
53     {
54         if(sum<=k)
55         {
56             cout<<a[i-1].x+1<<endl;//因为开药的那一天也算
57             return 0;
58         }
59         sum-=a[i].y;
60     }
61     cout<<a[n].x+1<<endl;
62     return 0;
63 }

D：给定两个不连通的无向图，可以连接一条边，使得这两个图连通且最短路的距离最大

这里可以简单证明一下，部分采取了离散数学的知识：

假设有两个不连通的图G1和G2，它们之间通过一条边连接起来。我们希望计算出连接后的图中两个顶点之间的最短路径的最大距离。

首先，我们来考虑两个图各自的最大最短路径。

对于图G1，最大最短路径是指G1中任意两个顶点之间的最短路径中的最大值。设G1中最大最短路径的长度为d1。

同样地，对于图G2，最大最短路径的长度为d2。

现在我们将G1和G2通过一条边连接起来，形成一个新的图G。

当我们连接两个图时，连接的边的长度为1。因此，连接后的图G中，连接两个图的边所连接的两个顶点之间的最短路径的长度为1。

我们需要找到连接后的图G中两个顶点之间的最短路径的最大距离。这个距离可以是连接两个图的边的长度加上两个图各自的最大最短路径的长度，即d1+d2+1。

为什么是d1+d2+1呢？

考虑一种情况，我们从图G1中的某个顶点出发，经过连接的边到达图G2中的某个顶点，然后再到达图G1中的另一个顶点。这条路径的长度是d1+d2+1。

我们需要注意的是，在连接的边上只有一个顶点，所以在这条路径上最远的两个顶点分别位于图G1和图G2中。因此，d1+d2+1是连接后的图G中两个顶点之间的最短路径的最大距离。

综上所述，连接两个不连通图后的最短路径的最大距离是两个图各自的最大最短路径之和再加上1，即d1+d2+1。

所以说就可以先分别求出初始点到每个点的最短距离，对于第二个图来说，从顶点u->n1+n2和n1+n2->u是一样的，所以可以从n1+n2开始求最短路，

结果就很明显了，max(d1)+max(d2)+1就可以了

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<string>
 6 #include<vector>
 7 #include<stack>
 8 #include<bitset>
 9 #include<cstdlib>
10 #include<cmath>
11 #include<set>
12 #include<list>
13 #include<deque>
14 #include<map>
15 #include<queue>
16 #include <iomanip>
17 #include<ctime>
18 using namespace std;
19 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
20 #define TLE (double)clock()/CLOCKS_PER_SEC<=0.95
21 #define int long long 
22 #define double long double
23 #define endl '\n'
24 #define inf LLONG_MAX
25 #define iinf INT_MAX
26 typedef pair<int,int> PII;
27 const double PI = acos(-1.0);
28 const double eps = 1e-6;
29 const int INF = 0x3f3f3f3f;
30 const int N = 6e5+10;
31 int n1,n2,m;
32 int e[N],idx,ne[N],h[N];
33 int dis1[N];
34 int dis2[N];
35 void add(int a, int b)  // 添加一条边a->b
36 {
37     e[++idx] = b, ne[idx] = h[a], h[a] = idx  ;
38 }
39 void bfs1(int x)
40 {
41     memset(dis1,0x3f,sizeof dis1);
42     dis1[x]=0;
43     queue<int>q;
44     q.push(x);
45     while(!q.empty())
46     {
47         int a=q.front();
48         q.pop();
49         for(int i=h[a];~i;i=ne[i])
50         {
51             int v=e[i];
52             if(dis1[v]>dis1[a]+1)
53             {
54                 dis1[v]=dis1[a]+1;
55                 q.push(v);
56             }
57         }
58     }
59 }
60 signed main()
61 {
62     IOS;
63     memset(h,-1,sizeof h);
64     cin>>n1>>n2>>m;
65     for(int i=1;i<=m;i++)
66     {
67         int u,v;
68         cin>>u>>v;
69         add(u,v);
70         add(v,u);
71     }
72     bfs1(1);
73     int ans=0;
74     ans+=*max_element(dis1+1,dis1+1+n1);
75     bfs1(n1+n2);
76     ans+=*max_element(dis1+1+n1,dis1+1+n1+n2);
77     ans++;
78     cout<<ans<<endl;
79     return 0;
80 }

E：给定n个人和他们的父节点，现在规定第x[i]个人购买的保险可以恩泽到y[i]代，现在询问多少人可以至少得到一份保险

可以这样考虑，我们要求的至少得到一份实际上就是不断去找其父兄代所能延申的最大恩泽，并且他本身的恩泽是不可能大于其父亲的恩泽范围，对我们来说，如果找的到，就将其本身设置为他父节点所能延申的最大恩泽，如果找不到那就从其兄弟节点中找符合的就可以，最后恩泽所获得的人的数量为正就表明这个人有保险，统计cnt就可以了

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<string>
 6 #include<vector>
 7 #include<stack>
 8 #include<bitset>
 9 #include<cstdlib>
10 #include<cmath>
11 #include<set>
12 #include<list>
13 #include<deque>
14 #include<map>
15 #include<queue>
16 #include <iomanip>
17 #include<ctime>
18 using namespace std;
19 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
20 #define TLE (double)clock()/CLOCKS_PER_SEC<=0.95
21 #define int long long 
22 #define double long double
23 #define endl '\n'
24 #define inf LLONG_MAX
25 #define iinf INT_MAX
26 typedef pair<int,int> PII;
27 const double PI = acos(-1.0);
28 const double eps = 1e-6;
29 const int INF = 0x3f3f3f3f;
30 const int N = 3e5+10;
31 int n,m;
32 vector<int>g[N];
33 int mx[N];
34 int cnt;
35 bool vis[N];
36 // void dfs(int p,int d)
37 // {
38     // d=max(d,mx[p]);
39     // if(d)    vis[p]=true;
40     // for(int i=0;i<g[p].size();i++)
41     // {
42         // dfs(g[p][i],d-1);
43     // }
44 // }
45 void dfs(int x,int y)
46 {
47     if(mx[x]>=y)    return ;
48     if(y==0)    return ;
49     mx[x]=y;
50     for(auto &it:g[x])    dfs(it,y-1);
51 }
52 signed main()
53 {
54     IOS;
55     cin>>n>>m;
56     for(int i=2;i<=n;i++)
57     {
58         int x;
59         cin>>x;
60         g[x].push_back(i)    ;
61     }
62     for(int i=1;i<=m;i++)
63     {
64         int x,y;
65         cin>>x>>y;
66         mx[x]=max(mx[x],y+1);//因为这里所能延申的范围也包括他自己
67     }
68     for(int i=1;i<=n;i++)
69     {
70         for(auto &it:g[i])
71         {
72             dfs(it,mx[i]-1);//去掉他自己
73         }
74     }
75     for(int i=1;i<=n;i++)
76     {
77         if(mx[i])    cnt++;
78     }
79     cout<<cnt<<endl;
80     return 0;
81 }