Educational Codeforces Round 72 (Rated for Div. 2)

亦凉 2023-06-01 11:14 85阅读 0赞

链接：[http://codeforces.com/contest/1217][http_codeforces.com_contest_1217]

A. Creating a Character

题意：将自由点分配给力量或者智力，要求力量必须大于智力，自由点必须全部分配，问有几种分配方案。

思路：先将自由点全部给力量，然后算出和智力的差值，将差值加一的一半 和 n + 1 去最小即可。

AC代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 int main()
     5 {
     6     std::ios::sync_with_stdio(false);
     7     int t;
     8     cin >> t;
     9     while(t--)
    10     {
    11         ll a, b, n;
    12         ll ans = 0;
    13         cin >> a >> b >> n;
    14         a += n;
    15         ans += (a - b + 1) / 2;
    16         ans = min(n + 1, ans);
    17         if(a <= b) cout << 0 << endl;
    18         else cout << ans << endl;
    19     }
    20     return 0;
    21 }

--------------------

B. Zmei Gorynich

题意：T组数据。第一行输入n,x。n,x分别代表技能种类和头的初始数量。n行数据，代表技能的攻击力和恢复力。求砍完头的最小次数。

思路：求出每次最大有效攻击 和攻击最大值，如果它生命小于攻击最大值则一次就能击杀，否则用最大有效攻击消耗，如果最大有效攻击为负，则无法击杀。

AC代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 int main()
     5 {
     6     std::ios::sync_with_stdio(false);
     7     int t;
     8     cin >> t;
     9     while(t--)
    10     {
    11         int n;
    12         ll x, d, h;
    13         ll a = 0;
    14         ll maxd = 0;
    15         cin >> n >> x;
    16         for(int i = 0;i < n;i++)
    17         {
    18             cin >> d >> h;
    19             a =max(d - h, a);
    20             maxd = max(maxd, d);
    21         }
    22         if(x <= maxd) cout << 1 << endl;
    23         else if(a <= 0) cout << -1 <<endl;
    24         else {
    25             ll t = x - maxd;
    26             ll ans = t / a + (t % a ? 1LL : 0LL) + 1LL;
    27             cout <<  ans << endl;
    28         }
    29 
    30     }
    31     return 0;
    32 }

--------------------

C. The Number Of Good Substrings

题意：求01字符串长度等于字符串在十进制的值的有多少个。

思路：暴力，只有1才可能对答案产生贡献，并且前导的0也会产生影响。

AC代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 int main()
     5 {
     6     std::ios::sync_with_stdio(false);
     7     int t;
     8     string a;
     9     cin >> t;
    10     while(t--)
    11     {
    12         int zero =  0;
    13         int ans = 0;
    14         cin >> a;
    15         int n = a.size();
    16         for(int i = 0;i < n;i++)
    17         {
    18             if(a[i] == '0') zero++;
    19             else {
    20                 ans ++;
    21                 ll sum = 1;
    22                 for(int j = i + 1;j < n;j++)
    23                 {
    24                     sum *= 2LL;
    25                     sum += (a[j] - '0');
    26                     if(sum <= j - i + 1 + zero) ans ++;
    27                     else{
    28                         break;
    29                     }
    30                 }
    31                 zero = 0;
    32                 //cout << ans << endl;
    33             }
    34         }
    35         cout << ans << endl;
    36     }
    37     return 0;
    38 }

--------------------

D. Coloring Edges

题意：给你个有向图，给所有边染色，使得没有一个环包含的边只有一种颜色，输出最小颜色数及染色方案。

思路：产生环得染2 其余都是1；

AC代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 typedef long long ll;
     3 using namespace std;
     4 const int maxn = 5e3 + 5;
     5 int vis[maxn];
     6 int ans[maxn];
     7 int last[maxn << 1],Next[maxn << 1],to[maxn << 1], cnt;
     8 void add(int u,int v){
     9     Next[++cnt] = last[u];
    10     last[u] = cnt;
    11     to[cnt] = v;
    12 }
    13 int color = 1;
    14 void dfs(int v){
    15     if(vis[v]) return;
    16     vis[v] = 1;
    17     for(int i = last[v];i;i = Next[i]){
    18         int u = to[i];
    19         dfs(u);
    20     }
    21 }
    22 int main()
    23 {
    24     std::ios::sync_with_stdio(false);
    25     int n,m;
    26     cin >> n >> m;
    27     for(int i = 1;i <= m;i++){
    28         int u,v;
    29         cin >> u >> v;
    30         memset(vis, 0, sizeof(vis));
    31         dfs(v);
    32         if(vis[u]) ans[i] = 2,color = 2;
    33         else ans[i] = 1,add(u,v);
    34     }
    35     cout << color << endl;
    36     for(int i = 1;i <= m;i++) cout << ans[i] <<endl;
    37     return 0;
    38 }

转载于:https://www.cnblogs.com/Carered/p/11478858.html

[http_codeforces.com_contest_1217]: http://codeforces.com/contest/1217
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/b4af08c22117477791272e584a19d0e7.png