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

点个赞谢谢喽

​​​​​​​

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<=t;l++)
	{
		int x,y;
        cin>>x>>y;
		if (y%x!=0)
			cout<<0<<" "<<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<=n;l++)
	{
		char a,b;
		cin>>a>>b;
		int x=a-97,y=b-96;
		if (b>a)
			cout< 
 
C题 
https://codeforces.com/problemset/problem/1674/C
 
这个题要考虑的情况不少，大概6种：
 
T="a"
T里有a
T=没有a
S="a"
1
INF
2
S=多个a
1
INF
*
*处表示
 
 
这样就可以写出代码了，分情况做即可：
 
注意组合数的计算要用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<=m;i++) 
        {
            if (j==0)
                mat[i][j]=1;
            else
                mat[i][j]=mat[i-1][j-1]+mat[i-1][j];
        } // 计算Cmn
    }
    return mat[m][n];
}

int main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	for (int l=1;l<=n;l++)
	{
		string s,ss,t;
		int x=0;
		cin>>s>>t;
		if (t=="a")
		{
			cout<<"1"< 
 
D题 
https://codeforces.com/problemset/problem/1674/D
 
主要思路就是要想着，什么样的b可以变成c，同样什么样的a可以变成b，找到规律就能做了，看看代码就明白了：
 
//CF1674D 22-05-03
#include
using namespace std;
int a[200005],b[200005];

void solve()
{
	int n;
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		cin>>a[i];b[i]=a[i];
	}
	if (n<=2)
		cout<<"YES"<a[i+1])
					swap(a[i],a[i+1]);//交换
				if (a[i]!=b[i] || a[i+1]!=b[i+1])//判断b的换的情况
				{
					cout<<"NO"<a[i+1])
					swap(a[i],a[i+1]);
				if (a[i]!=b[i] || a[i+1]!=b[i+1])
				{
					cout<<"NO"<>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 
 
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 < m; j++) {
            char c;
            std::cin >> c;
            if (c == '*') {
                if (a[cnt]) {
                    o++;
                }
                cnt++;
                a[j * n + i] = 1;
                if (j * n + i < cnt) {
                    o++;
                }
            }
        }
    }
    
    while (q--) {
        int x, y;
        std::cin >> 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> adj(n);
    std::vector in(n), out(n), cur(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        std::cin >> 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;
}