Codeforces Round #786 (Div.3) 题解 [A-G]

先说说总体情况，难度还行，不过E题好像非常坑啊，我好几个同学都没有过

这次难度比Atcoder Beginner Contest (ABC)稍简单 

点个赞谢谢喽

​​​​​​​😀😀😀😀😀

下面开始题解

A题

https://codeforces.com/problemset/problem/1674/A

这个A题嘛，题目描述简单说就是给两个数，a和b，现在让你把 b / a 写成幂的形式。

更简单的说，就是看y%x是否为0。

但是这道题根本不是题目说的随便输出一种答案，而是一个给定的数。（它甚至不是Special Judge）

下面直接上代码：

//CF1674A 22-05-02#include using namespace std;int main() {ios::sync_with_stdio(0);cin.tie(0);int t;cin>>t;for (int l=1;l>x>>y;if (y%x!=0)cout<<0<<" "<<0<<endl;elsecout<<1<<" "<<y/x<<endl;}return 0;}

B题

https://codeforces.com/problemset/problem/1674/B

很简单，但要注意别把题目看错了，aa, bb, cc, dd 等等都不算的，下面代码：

//CF1674B 22-05-02#include using namespace std;int main() {ios::sync_with_stdio(0);cin.tie(0);int n;cin>>n;for (int l=1;l>a>>b;int x=a-97,y=b-96;if (b>a)cout<<x*26+y-x-1<<endl;else cout<<x*26+y-x<<endl;}return 0;}

C题

https://codeforces.com/problemset/problem/1674/C

这个题要考虑的情况不少，大概6种：

*处表示

这样就可以写出代码了，分情况做即可：

注意组合数的计算要用long long！

//CF1674C 22-05-02#include using namespace std; long long mat[100][100]; long long com(int m,int n) {    if (n==0 || m==n) return 1;    for (int j=0;j<=n;j++)     { // 只要计算n列就行了，不用计算后面的 mat[j][j]=1; for (int i=j+1;i>n;for (int l=1;l>s>>t;if (t=="a"){cout<<"1"<<endl;continue;}for (int i=0;i<t.length();i++) if (t[i]=='a') {cout<<"-1"<<endl;x=1;break;}if (x==0){long long sum=0;for (int i=0;i<=s.length();i++)sum+=com(s.length(),i);cout<<sum<<endl;}}return 0;}

D题

https://codeforces.com/problemset/problem/1674/D

主要思路就是要想着，什么样的b可以变成c，同样什么样的a可以变成b，找到规律就能做了，看看代码就明白了：

//CF1674D 22-05-03#includeusing namespace std;int a[200005],b[200005];void solve(){int n;cin>>n;for (int i=1;i>a[i];b[i]=a[i];}if (n<=2)cout<<"YES"<<endl;//2个不管是哪两个数都行else{sort(b+1,b+n+1);//排序if (n%2==0)//模拟插入{for (int i=1;ia[i+1])swap(a[i],a[i+1]);//交换if (a[i]!=b[i] || a[i+1]!=b[i+1])//判断b的换的情况{cout<<"NO"<<endl;//判断不行，退出return;}}cout<<"YES"<<endl;return;//退出}else{if (a[1]!=b[1]) //中间不相等直接退出{cout<<"NO"<<endl;return;}for (int i=2;ia[i+1])swap(a[i],a[i+1]);if (a[i]!=b[i] || a[i+1]!=b[i+1]){cout<<"NO"<<endl;return;}}cout<<"YES"<>t;while(t--)solve();exit(0);}

E题

https://codeforces.com/problemset/problem/1674/E

解释：

20    ans=min(ans,max(((a[i]+1)/2,(a[i+1]+1)/2,a[i]+a[i+1]+2/3)));

表示在相邻的两个里面去最小：（共3种情况）

第一种：命中 a[i] 打，一次攻击力2

第二种：命中 a[i+1] 打，一次攻击力2

第三种：打一会儿 a[i] ，打一会儿 a[i+1] ，一次攻击力3

注意：向上取整！

22    ans=min(ans,1+a[i]/2+a[i+2]/2);

这里是隔一个打，命中中间，两边每次-1

与 ans 取最小

这样算出来真的是最小

附上代码：

//CF1674E 22-05-03#include using namespace std;int main() {    ios::sync_with_stdio(0);    cin.tie(0);    int n;    cin>>n;      vector a(n),b(n);    for (int i=0;i>a[i]; b[i]=(a[i]+1)/2;    }    nth_element(b.begin(), b.begin()+2, b.end());      int ans=b[0]+b[1];    for (int i=0;i<n-1;i++)  ans=min(ans,max(((a[i]+1)/2,(a[i+1]+1)/2,a[i]+a[i+1]+2/3)));    for (int i=0;i<n-2;i++) ans=min(ans,1+a[i]/2+a[i+2]/2);     cout<<ans<<endl;    return 0;}

F题

https://codeforces.com/problemset/problem/1674/F

jiangly:

//CF1674F 22-05-03#include using i64 = long long;int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr); int n, m, q;    std::cin >> n >> m >> q; int o = 0, cnt = 0; std::vector a(n * m);    for (int i = 0; i < n; i++) { for (int j = 0; j > c;     if (c == '*') {  if (a[cnt]) {      o++;  }  cnt++;  a[j * n + i] = 1;  if (j * n + i > x >> y; x--; y--; int i = y * n + x;  if (!a[i]) {     if (a[cnt]) {  o++;     }     cnt++;     a[i] = 1;     if (i < cnt) {  o++;     } } else {     if (i < cnt) {  o--;     }     a[i] = 0;     cnt--;     if (a[cnt]) {  o--;     } } std::cout << cnt - o << "\n";    } return 0;}

G题

https://codeforces.com/problemset/problem/1674/G

jiangly:

//CF1674G 22-05-03#include using i64 = long long;int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr); int n, m;    std::cin >> n >> m; std::vector<std::vector> adj(n);    std::vector in(n), out(n), cur(n);    for (int i = 0; i > u >> v; u--; v--; adj[u].push_back(v); in[v]++; out[u]++; cur[v]++;    } std::queue q;    for (int i = 0; i < n; i++) { if (!cur[i]) {     q.push(i); }    } int ans = 1;    std::vector f(n, 1); while (!q.empty()) { int u = q.front(); q.pop();  ans = std::max(ans, f[u]);  for (auto v : adj[u]) {     if (out[u] > 1 && in[v] > 1) {  f[v] = std::max(f[v], f[u] + 1);     }     if (!--cur[v]) {  q.push(v);     } }    } std::cout << ans << "\n"; return 0;}