首页/小白筆記

div1和div2，Codeforces Round #327 div2

 2023-10-18 阅读 25 评论 0

摘要：Problem_A(591A): 題意： 　　有一段長度為l的路，兩個人分別在兩個端點，1, l。 現在已知每個人的速度為p,q. 求第一個人(初始位置在1)在他們第二次相遇的時候的位置。 div1和div2，　　當他們相遇的時候， 他們會掉頭返回走， 走到端點再返回

Problem_A(591A):

題意：

　　有一段長度為l的路，兩個人分別在兩個端點，1, l。 現在已知每個人的速度為p,q. 求第一個人(初始位置在1)在他們第二次相遇的時候的位置。

div1和div2，　　當他們相遇的時候， 他們會掉頭返回走， 走到端點再返回來。

?

思路：

　　首先可以確定的是， 這兩個人每次相遇的地點都是一樣的。

code1083。　　然后， 設他們相遇時時間為t, 所以有：p * t + q * t = l

　　即：t = l / (p + q)

　　第一個人位置即為：t * p = l / (p + q) * p;

?

code-switching。代碼：

　　

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <ctime>
 6 #include <set>
 7 #include <map>
 8 #include <list>
 9 #include <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 0x3f3f3f3f
20 #define MOD 1000000007
21 #define eps 1e-6
22 #define MAXN 1000000
23 #define MAXM 100
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {printf("%d\n", x);}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 int l, p, q;
36 
37 int main()
38 {
39     scanf("%d %d %d", &l, &p, &q);
40     printf("%.4lf\n", (double)(l * 1.0 / (p * 1.0 + q * 1.0)) * (p * 1.0));
41     return 0;
42 }
View Code

?

Problem_B(591B):

codeforces div3、題意：

　　給一個長度為n的字符串， 然后進行m次操作。

　　每次操作(ch_a, ch_b)：將當前字符串中所有的字符ch_a替換成ch_b, 所有的ch_b替換成ch_a

　　求操作完后的字符串。

怎么爬codeforces的數據。?

思路：

　　乍一看是個模擬， 再一看數據量2* 10 ^5 有點大， 不能直接模擬。

　　題目中有個條件：所有字母均為小寫字母！！！

codeforces有幾個div？　　小寫字母只有26個， 每次對這26個字母進行操作即可。

　　設 f[i] = j 為初始字母為i + 'a'的字符 當前變換成j + 'a' 字符

　　每次找出值為ch_a, ch_b的字符， 然后對其進行賦值操作即可。

　　這樣一來就成了O(m * 26) 妥妥的1s

codeforces難度、?

代碼：

　　

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <ctime>
 6 #include <set>
 7 #include <map>
 8 #include <list>
 9 #include <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 0x3f3f3f3f
20 #define MOD 1000000007
21 #define eps 1e-6
22 #define MAXN 200010
23 #define MAXM 30
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {printf("%d\n", x);}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 int n, m;
36 int name[MAXN];
37 int f[MAXM];
38 char read_char()
39 {
40     char ch;
41     while(ch = getchar())
42     {
43         if(ch >= 'a' && ch <= 'z') return ch;
44     }
45 }
46 int find_char(int x)
47 {
48     for(int i = 0; i < MAXM; i ++)
49         if(f[i] == x) return i;
50     return -1;
51 }
52 
53 int main()
54 {
55     scanf("%d %d", &n, &m);
56     for(int i = 0; i < n; i ++)
57         name[i] = (read_char() - 'a');
58     for(int i = 0; i < MAXM; i ++)
59         f[i] = i;
60     char ch_a, ch_b;
61     for(int i = 0;i < m; i ++)
62     {
63         ch_a = read_char();
64         ch_b = read_char();
65         int pos_a = find_char(ch_a - 'a');
66         int pos_b = find_char(ch_b - 'a');
67         f[pos_a] = ch_b - 'a';
68         f[pos_b] = ch_a - 'a';
69     }
70     for(int i = 0; i < n; i ++)
71         printf("%c", f[name[i]] + 'a');
72     printf("\n");
73     return 0;
74 }
View Code

?

codeforces教程、Problem_C(590A):

題意：

　　給一個長度為n的數組a[]， 它有如下變化：

　　　　1：b[0] = a[0], b[n-1] = b[n - 1]

div1，　　　　2：b[i] = （a[i - 1] ， a[i], a[i + 1])的中位數

　　且a[i] = 0 || a[i] = 1

　　求出最少多少次變化之后， 此數組不能再變化(即變化后和變化前一樣)

?

forces。思路：

　　有一個規律不難發現：如果有兩個以上連續相同的數 如11, 00 那么這兩個數在接下來的變化中會保持不變！！！

　　很簡單， 因為是中位數， 而且只有0 1 那么如果a[i]的左右兩邊有一個或以上相同的數 那么a[i]就不會變。

　　然后再來看看那些不連續的數的規律：

　　　　　　　1 1 0 1 0 1 0 1 0 0

　　這個數最后會變成 1 1 1 1 1 0 0 0 0 0！ 對稱了， 再來看一個

　　　　　　　0 0 1 0 1 0 1 0 0

　　變化后： ? 0 0 0 0 0 0 0 0 0 全變成0 了！ 再改變一下兩端連續的那個值找找規律 ?就會發現

　　　　如果不連續串的長度為奇數， 那么它的左右兩端肯定是相等的， 那么它中間的這段不連續的串最后都會變成它。且次數為(len / 2 + len % 2)

　　　　如果不連續串的長度為偶數， 那么它的左右兩端肯定是不等的，最后中間這段不連續的串都會對半變化！ 左邊的與左端點相等， 右邊的與右端點相等。次數為 len /2

?

代碼：

　　

  1 #include <cmath>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <ctime>
  6 #include <set>
  7 #include <map>
  8 #include <list>
  9 #include <stack>
 10 #include <queue>
 11 #include <string>
 12 #include <vector>
 13 #include <fstream>
 14 #include <iterator>
 15 #include <iostream>
 16 #include <algorithm>
 17 using namespace std;
 18 #define LL long long
 19 #define INF 0x3f3f3f3f
 20 #define MOD 1000000007
 21 #define eps 1e-6
 22 #define MAXN 1000000
 23 #define MAXM 100
 24 #define dd {cout<<"debug"<<endl;}
 25 #define pa {system("pause");}
 26 #define p(x) {printf("%d\n", x);}
 27 #define pd(x) {printf("%.7lf\n", x);}
 28 #define k(x) {printf("Case %d: ", ++x);}
 29 #define s(x) {scanf("%d", &x);}
 30 #define sd(x) {scanf("%lf", &x);}
 31 #define mes(x, d) {memset(x, d, sizeof(x));}
 32 #define do(i, x) for(i = 0; i < x; i ++)
 33 #define dod(i, x, l) for(i = x; i >= l; i --)
 34 #define doe(i, x) for(i = 1; i <= x; i ++)
 35 int n;
 36 int a[MAXN];
 37 void read()
 38 {
 39     for(int i = 0; i < n; i ++)
 40         scanf("%d", &a[i]);
 41 }
 42 
 43 void solve()
 44 {
 45     int cnt = 0;
 46     for(int i = 0; i < n;)
 47     {
 48         int j = i;
 49         while(j + 1 < n && a[j] != a[j + 1])
 50             j ++;
 51         j ++;
 52         cnt = max(cnt, (j - i - 2) / 2 + (j - i - 2) % 2);
 53         if((j - i) % 2 == 1)
 54         {
 55             for(int k = i + 1; k < j; k ++)
 56                 a[k] = a[i];
 57         }
 58         else 
 59         {
 60             for(int k = i + 1; k < (i + j) / 2; k ++)
 61                 a[k] = a[i];
 62             for(int k = (i + j) / 2; k < j; k ++)
 63                 a[k] = a[j - 1];
 64         }
 65         i = j;
 66     }
 67     printf("%d\n", cnt);
 68     for(int i = 0; i < n - 1; i ++)
 69         printf("%d ", a[i]);
 70     printf("%d\n", a[n - 1]);
 71 }
 72 int get_ans(int l, int r)
 73 {
 74     if(l == r) return 0;
 75     if(a[l] == a[r])
 76     {
 77         for(int i = l + 1; i < r; i ++)
 78             a[i] = a[l];
 79         return (r - l) / 2;
 80     } 
 81     else 
 82     {
 83         for(int i = l + 1; i < (l + r + 1) / 2; i ++)
 84             a[i] = a[l];
 85         for(int i = (l + r + 1) / 2; i < r; i ++)
 86             a[i] = a[r];
 87         return (r - l - 1) / 2;
 88     }
 89 }
 90 void solve_2()
 91 {
 92     int l = 0, ans = 0;
 93     for(int i = 0; i < n; i ++)
 94         if(i == n - 1 || a[i] == a[i + 1])
 95         {
 96             ans = max(ans, get_ans(l, i));
 97             l = i + 1;
 98         }
 99     printf("%d\n", ans);
100     for(int i = 0; i < n; i ++)
101         printf(i == n - 1? "%d\n" : "%d ", a[i]);
102 }
103 
104 int main()
105 {
106     scanf("%d", &n);
107     read();
108     // solve();
109     solve_2();
110     return 0;
111 }
View Code

?

Problem_D(590B):

題意：

　　在一個二維坐標系上， 給兩個點， 一個起點(x1, y1)， 一個終點(x2, y2).

　　一個時間t, 一個最大速度vmax

　　然后給兩個速度向量（vx, vy）, (wx, wy).

　　從起點飛到終點， 方向和速度可以在任何時刻隨意變換， 速度不超過vmax即可。

　　在前t秒， 會受到風的阻力(vx, vy). t秒風的速度變成(wx, wy)。 求到終點的最短時間。

?

思路：

　　首先， 不考慮方向和風的影響， 以最大速度前進， 那么ts內的移動的距離就是vmax * t。 如果再加上方向呢？

　　是不是就成了一個圓：

　　　　圓心 O = (x1, y1)

　　　　半徑 r = vmax * t

　　再加上風的影響呢？

　　是不就就是將這個圓整體位移(vx*t, vy*t) ？

　　此時圓為：

　　　　圓心 O = (x1 + vx * t, y1 + vy * t)

　　　　半徑 r = vmax * t

　　如果此時， 終點在圓內， 是否代表在ts內可以到達？

　　如果終點在圓外， 那么設時間為w， 此時這個圓:

　　　　圓心O = ?(x1 + vx * t + wx * (w - t), y1 + vy * t + wy * (w - t))

　　　　半徑r = vmax * w

　　

　　所以， 對時間進行二分， 找到最小的滿足終點在圓內的時間即可。

?

代碼：

　　

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <ctime>
 6 #include <set>
 7 #include <map>
 8 #include <list>
 9 #include <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 0x3f3f3f3f
20 #define MOD 1000000007
21 #define eps 1e-6
22 #define MAXN 1000000
23 #define MAXM 100
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {printf("%d\n", x);}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 double x[2], y[2];
36 double v, t;
37 double vx, vy, wx, wy;
38 double sqr(double x)
39 {
40     return x * x;
41 }
42 double dis(double x1, double y1, double x2, double y2)
43 {
44     return sqrt(sqr(x1 - x2) + sqr(y1 - y2));
45 }
46 bool is_ok(double tmp_t)
47 {
48     double tx, ty;
49     if(tmp_t > t)
50     {
51         tx = x[0] + t * vx + wx * (tmp_t - t);
52         ty = y[0] + t * vy + wy * (tmp_t - t);
53     }
54     else 
55     {
56         tx = x[0] + tmp_t * vx;
57         ty = y[0] + tmp_t * vy;
58     }
59     double ans = dis(tx, ty, x[1], y[1]);
60     if(ans < v * tmp_t) return true;
61     return false;
62 }
63 
64 int main()
65 {
66     scanf("%lf %lf %lf %lf", &x[0], &y[0], &x[1], &y[1]);
67     scanf("%lf %lf", &v, &t);
68     scanf("%lf %lf %lf %lf", &vx, &vy, &wx, &wy);
69     double ans_l = 0, ans_r = 1e8, mid;
70     while((ans_r - ans_l) >= eps)
71     {
72         mid = (ans_l + ans_r) / 2.0;
73         if(is_ok(mid)) ans_r = mid;
74         else ans_l = mid;
75     }
76     printf("%.7lf\n", ans_l);
77     return 0;
78 }
View Code

?

Porblem_E(590C):

題意：

　　一個n * m的網格， #代表不能走， .代表沼澤，1 2 3 分別代表一類區域

　　現在要將這三個區域連通， 你可以把沼澤變成路。 求變化最少的沼澤， 使得三個區域連通起來。

?

思路：

　　因為1,2,3 可以看成三個塊， 也可以看成三類起點。

　　將所有的1, 2, 3記錄下來， 以此為起點， 搜索三次。

　　然后枚舉它們三個區域的交點， 算出到三個區域的長度(沼澤數量)，取最小值即可。

?

代碼：

　　

  1 #include <cmath>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <ctime>
  6 #include <set>
  7 #include <map>
  8 #include <list>
  9 #include <stack>
 10 #include <queue>
 11 #include <string>
 12 #include <vector>
 13 #include <fstream>
 14 #include <iterator>
 15 #include <iostream>
 16 #include <algorithm>
 17 using namespace std;
 18 #define LL long long
 19 #define INF 1000100
 20 #define MOD 1000000007
 21 #define eps 1e-6
 22 #define MAXN 1010
 23 #define MAXM 3
 24 #define dd {cout<<"debug"<<endl;}
 25 #define pa {system("pause");}
 26 #define p(x) {printf("%d\n", x);}
 27 #define pd(x) {printf("%.7lf\n", x);}
 28 #define k(x) {printf("Case %d: ", ++x);}
 29 #define s(x) {scanf("%d", &x);}
 30 #define sd(x) {scanf("%lf", &x);}
 31 #define mes(x, d) {memset(x, d, sizeof(x));}
 32 #define do(i, x) for(i = 0; i < x; i ++)
 33 #define dod(i, x, l) for(i = x; i >= l; i --)
 34 #define doe(i, x) for(i = 1; i <= x; i ++)
 35 int n, m;
 36 int step[MAXM][MAXN][MAXN];
 37 int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
 38 int grid[MAXN][MAXN];
 39 int read_ch()
 40 {
 41     char ch;
 42     while(ch = getchar())
 43     {
 44         if(ch >= '1' && ch <= '3') return (int)(ch - '1');
 45         if(ch == '.') return -1;
 46         if(ch == '#') return -2;
 47     }
 48 }
 49 bool check(int i, int j)
 50 {
 51     if(i < 0 || i >= n || j < 0 || j >= m || grid[i][j] == -2) return false;
 52     return true;
 53 }
 54 void bfs(int pos)
 55 {
 56     queue <int> Q;
 57     while(!Q.empty()) Q.pop();
 58     for(int i = 0; i < n; i ++)
 59         for(int j = 0; j < m; j ++)
 60             if(grid[i][j] == pos)
 61             {
 62                 Q.push(i);
 63                 Q.push(j);
 64                 step[pos][i][j] = 0;
 65             }
 66     while(!Q.empty())
 67     {
 68         int x = Q.front();
 69         Q.pop();
 70         int y = Q.front();
 71         Q.pop();
 72 
 73         for(int i = 0; i < 4; i ++)
 74         {
 75             int xx = x + dir[i][0];
 76             int yy = y + dir[i][1];
 77             if(!check(xx, yy)) continue;
 78             if(step[pos][xx][yy] > step[pos][x][y] + (grid[x][y] == -1))
 79             {
 80                 step[pos][xx][yy] = step[pos][x][y] + (grid[x][y] == -1);
 81                 Q.push(xx);
 82                 Q.push(yy);
 83             }
 84         }
 85     }
 86 }
 87 
 88 void show(int pos)
 89 {
 90     printf("%d\n", pos);
 91     for(int i = 0; i < n; i ++, printf("\n"))
 92         for(int j = 0; j < m; j ++)
 93             printf("%d ", step[pos][i][j]);
 94     printf("\n");
 95 }
 96 
 97 int main()
 98 {
 99     mes(grid, 0);
100     for(int k = 0; k < MAXM; k ++)
101         for(int i = 0; i < MAXN; i ++)
102             for(int j = 0; j < MAXN; j ++)
103                 step[k][i][j] = INF;
104 
105     scanf("%d %d", &n, &m);
106     for(int i = 0; i < n; i ++)
107         for(int j = 0; j < m; j ++)
108             grid[i][j] = read_ch();
109 
110     for(int i = 0; i < MAXM; i ++)
111         bfs(i);
112 
113     int ans = INF * 3;
114     for(int i = 0; i < n; i ++)
115         for(int j = 0; j < m; j ++)
116             ans = min(ans, step[0][i][j] + step[1][i][j] + step[2][i][j] + (grid[i][j] == -1));
117     if(ans >= INF) ans = -1;
118     printf("%d\n", ans);
119     return 0;
120 }
View Code

?

轉載于:https://www.cnblogs.com/By-ruoyu/p/5526407.html

版权声明：本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。

原文链接：https://hbdhgg.com/1/147049.html

上一篇：js面試題及答案 高級，Javascript面試題一套
下一篇：Java 繼承——3
标签：div1和div2code1083codeswitchingcodeforces div3怎么爬codeforces的數據codeforces有幾個divcodeforces難度codeforces教程
div1和div2

发表评论:

最新文章
阅读排行
猜你喜欢
热门标签

本站为非赢利网站，部分文章来源或改编自互联网及其他公众平台，主要目的在于分享信息，版权归原作者所有，内容仅供读者参考，如有侵权请联系我们删除！

Copyright © 2022 匯編語言學習筆記 Inc. 保留所有权利。

底部版权信息