算法日志篇 week2

A - Swap and Delete （CodeForces - 1913B）

You are given a binary string s(a string consisting only of 0-s and 1-s).

You can perform two types of operations on s:

1.delete one character from s. This operation costs 1 coin;

2.swap any pair of characters in s. This operation is free (costs 0 coins).

You can perform these operations any number of times and in any order.

Let’s name a string you’ve got after performing operations above as t. The string t is good if for each i from 1 to |t| ti≠si (|t| is the length of the string t). The empty string is always good. Note that you are comparing the resulting string t with the initial string s.

What is the minimum total cost to make the string t good?

题解

此题的中文大致意思是给出一个字符串，然后用两种方式来生成另一个字符串，新字符串t要和旧的字符串s前几位上的每一位都相反（0-1或1-0），第一种方式为删掉原字符串中的某几位，第二种方式为交换原字符串中的某几位。

此题的解法为：先统计出原字符串内有几个‘0’与‘1’，进行存储，随后对字符串进行遍历，包含如下三种情况：

1.原字符串大小为一，此时直接输出1就行。ps：删去

2.原字符串大小已经为 num_0 = num_1此时直接输出0即可，因为不需要进行删除操作，只需要交换就可以达到目的。

3.遍历原字符串，遇1减num_0，遇0减num_1,直到出现负值，此时输出原字符串位数-已经遍历的个数，则为需要删去的字符数量。

代码如下：

#includeusing namespace std;
void solve(){ long long n;
    cin >> n;
    while(n --){ string s;
        cin >> s;
        long long num_0 = count(s.begin(),s.end(),'0');
        long long num_1 = count(s.begin(),s.end(),'1');
        long long n0 = num_0;
        long long n1 = num_1;
        if(s.size() == 1)cout << 1 << endl;
        else if(num_0 == num_1){ cout << 0 < for(long long i = 0;i <= s.size();i ++){ if(n0 < 0 || n1 < 0){ cout << s.size() - i + 1<< endl;
                    break;
                }
                if(s[i] == '0'){ n1 --;
                }
                else if(s[i] == '1'){ n0 --;
                }
            }
        }
    }
}
int main(){ solve();
    return 0;
}

B - Square （CodeForces - 1921A）

A square of positive (strictly greater than 0) area is located on the coordinate plane, with sides parallel to the coordinate axes. You are given the coordinates of its corners, in random order. Your task is to find the area of the square.

Input

Each test consists of several testcases. The first line contains one integer t (1≤t≤100) — the number of testcases. The following is a description of the testcases.

Each testcase contains four lines, each line contains two integers xi,yi

(−1000≤xi,yi≤1000), coordinates of the corners of the square.

It is guaranteed that there is a square with sides parallel to the coordinate axes, with positive (strictly greater than 0) area, with corners in given points.

Output

For each test case, print a single integer, the area of the square.

题解

简单的逻辑题，因为时正方形所以更简单了，求面积只需求一边的边长。

#include using namespace std;
void solve(){ int n;
    cin >> n;
    while(n --){ vector> squared;
        int x = 4;
        int res;
        while(x --){ int a,b;
            cin >> a >> b;
            squared.emplace_back(a,b);
        }
        int length = 0;
        for(int i = 0;i < squared.size();i ++){ if(squared[i].first != squared[i + 1].first){ length = abs(squared[i].first - squared[i + 1].first);
                break;
            }
        }
        cout << length * length << endl;
    }
}
int main(){ solve();
    return 0;
}

C - Easy As ABC （CodeForces - 1906A ）

题解：

寻找三个位置相邻，包括斜向的最小连续串，可以采用DFS

#includeusing namespace std;
vector v;
int mark[4][4];
char c[4][4];
int dx[8]={-1,-1,0,1,1,1,0,-1},dy[8]={0,1,1,1,0,-1,-1,-1};
int check(int x,int y)
{if(mark[x][y] || x < 1 || x > 3 || y < 1 || y > 3)  return 0;
	return 1;
}
void dfs(int x,int y,string s)
{if(s.length() == 3)
	{v.push_back(s);
		return;
	}
	mark[x][y] = 1;
	for(int i = 0;i < 8;i ++)
	{int nx = x + dx[i],ny = y + dy[i];
		if(check(nx,ny)){ dfs(nx,ny,s + c[nx][ny]);
        } 
	}
	mark[x][y]=0;
}
void solve(){for(int i = 1;i <= 3;i ++)
	{for(int j = 1;j <= 3;j ++){ cin >> c[i][j];
        }
	}
	for(int i = 1;i <= 3;i ++){ for(int j = 1;j <= 3;j ++){ dfs(i,j,"");
        }
    }
	sort(v.begin(),v.end());
	cout << v[0];
}
int main(){ solve();
    return 0;
}

D - 2023 （2023）

题解：

在乘积等于 2023 的序列 a 中，删除了 k 个数字，留下长度为 n 的序列 b。 给定结果序列 b，找到任何合适的序列 a 并输出从中删除了哪些 k 个元素，或者声明这样的序列不可能存在。

2023的因子只有1、7、17、119、289 、2023，先求出给出元素之积，然后判断这个数是不是2023的因子，如果是就直接输出2023除以这个数的值，剩下的数直接输出1.

#includeusing namespace std;
void solve()
{int n,k;
	int s[100000];
	cin >> n >> k;
	int cj = 1;
	int ans = 2023;
	for(int i = 0;i < n;i ++)
	{cin >> s[i];
		cj *= s[i];
	}
	if(cj == 1 || cj == 7 || cj == 17 || cj == 119 || cj == 289 || cj == 2023)
	{cout << "YES" << endl;
		if(cj == 1)
		{cout << "2023 ";
			for(int i = 0;i < k - 1;i ++)
			{cout << "1 ";
			}
			cout << "\n";
			return;
		}
		if(cj == 7)
		{cout<<"289 ";
			for(int i=0;icout<<"1 ";
			}
			cout<<"\n";
			return;
		}
		if(cj==17)
		{cout<<"119 ";
			for(int i=0;icout<<"1 ";
			}
			cout<<"\n";
			return;
		}
		if(cj==119)
		{cout<<"17 ";
			for(int i=0;icout<<"1 ";
			}
			cout<<"\n";
			return;
		}
		if(cj==289)
		{cout<<"7 ";
			for(int i=0;icout<<"1 ";
			}
			cout<<"\n";
			return;
		}
		if(cj==2023)
		{for(int i=0;icout<<"1 ";
			}
			cout<<"\n";
			return;
		}
	}
	else
	{cout<<"NO"<<"\n";
	}
}
signed main()
{int t;
	cin>>t;
	while(t--)
	{solve();
	}
	return 0;
}

E - Two Out of Three （CodeForces - 1894B）

题解：

统计相同元素的个数和位置，然后判断是否大于等于2然后前两个放1，2和1，3，其余放1即可。

#includeusing namespace std;
const int N = 110;
struct Node { int a, b;
} nd[N];
bool st[N];
int last[N];
void solve() { memset(st, 0, sizeof st);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> nd[i].a;
    bool flag = false;
    bool a[4] = {false};
    for (int i = 0; i < n; i++) { if (!st[nd[i].a]) 
            nd[i].b = 1, st[nd[i].a] = true, last[nd[i].a] = 1;
        else { if (last[nd[i].a] == 1) { if (!flag) 
                    nd[i].b = 2, flag = true;
                else 
                    nd[i].b = 3;
                last[nd[i].a] = nd[i].b;
            } 
            else 
                nd[i].b = last[nd[i].a];
        }
        a[nd[i].b] = true;
    }
    int cnt = 0;
    for (int i = 1; i <= 3; i++) 
        if (a[i]) 
            cnt++;
    if (cnt <= 2) { cout << "-1" << endl;
        return;
    } 
    else { for (int i = 0; i < n; i++) 
            cout << nd[i].b << ' ';
    }
    cout << endl;
}
int main() { int T;
    cin >> T;
    while (T--) { solve();
    }
    return 0;
}

F - YetnotherrokenKeoard （CodeForces - 1907B）

题解：

当出现b或者B的是，他删除的是他前面的字符，所以我们要从后面往前面遍历，这样统计到B或者b的数字了，就可以去跟他前面的字符判断这个会不会删除，所以这里面有2个变量来存储这两个字符的数量。

#includeusing namespace std;
void solve(const string& s) { int cb = 0, cB = 0;
    string sb;
    for (int i = s.length() - 1; i >= 0; i--) { char c = s[i];
        if (c == 'b') { cb++;
        } else if (c == 'B') { cB++;
        } else if (c >= 'A' && c <= 'Z' && cB > 0) { cB--;
        } else if (c >= 'a' && c <= 'z' && cb > 0) { cb--;
        } else { sb.push_back(c);
        }
    }
    reverse(sb.begin(), sb.end());
    cout << sb << endl;
}
int main() { int t;
    cin >> t;
    while (t--) { string s;
        cin >> s;
        solve(s);
    }
    return 0;
}

G - Helmets in Night Light （CodeForces - 1876A）

题解：

对pair进行排序，按bi数组从小到达进行遍历，如果比k小，就将其能够传播的人数*代价加入结果，直到所有人都知道公告内容，如过在比k大之前能够传播的人的个数不够，则通过神奇头盔直接发送，发送次数为剩余未知人数。

#includeusing namespace std;
void solute(){ long long a,b;
    cin >> a >> b;
    long long c = 1;
    long long res = b;
    long long ai[a];
    long long bi[a];
    for(long long i = 0;i < a;i ++){ cin >> ai[i];
    }
    for(long long i = 0;i < a;i ++){ cin >> bi[i];
    }
    vector> person;
    for(long long i = 0;i < a;i ++){ person.emplace_back(ai[i],bi[i]);
    }
    sort(person.begin(), person.end(), [](const auto& lhs, const auto& rhs) { return lhs.second < rhs.second;
    });
    for(long long i = 0;i < person.size();i ++){ if(person[i].second < b){ c += person[i].first;
            if(c < a)
            res += person[i].first * person[i].second;
            else{ c = c - person[i].first;
                res += (a - c) * person[i].second;
                c = a;
            }
        }
        else break;
    }
    if(c < a)res += (a - c) * b; 
    cout << res << endl;
}
int main(){ int n;
    cin >> n;
    while(n --){ solute();
    }
    return 0;
}

H - Odd One Out （CodeForces - 1915A）

题解：

简单的直接判断。

#includeusing namespace std;
int turn_flag(int i){ if(i == 1)return 0;
    else return 1;
}
void solve(){ int a[3];
    int flag = 0;
    cin >> a[0];
    for(int i = 1;i < 3;i ++){ cin >> a[i];
        if(a[i] != a[i - 1]){ flag = turn_flag(flag);
        }
    }
    if(flag == 0)cout << a[1] < int n;
    cin >> n;
    while (n --)
    { solve();
    }
    return 0;
}

I - The Man who became a God （CodeForces - 1847A）

题解：

求出相邻两个元素的差值，去掉前m个大的差值以后的差值和即位答案。此题使用了优先队列来对元素进行排序插入。

#include using namespace std;
void solve(){ int n,m; 
    long long res = 0;
    cin >> n >> m;
    vector a(n + 1);
    priority_queue q;//默认状态为大顶堆，基于堆排序
    for(int i = 1;i <= n;i ++){ cin >> a[i];
        if(i != 1){q.push(abs(a[i] - a[i - 1]));}
    }
    for(int i = 1; i < m; i ++){q.pop();
	}
    while(!q.empty()){ long long t = q.top();
        q.pop();
        res += t;
    }
    cout << endl;
    cout << res << endl;
}
int main(){ int n;
    cin >> n;
    while(n --){ solve();
    }
    return 0;
}

J - Olya and Game with Arrays （CodeForces - 1859B）

题解：

对元素进行排列，筛选出每个数组中的元素的最小值和次小值，要想使移动一个元素让所有数组中的最小值之和达到最大，只需要判断每个元素的次小值的大小，将其他数组的最小值移入元素次小值最小的数组内，即可得到题目要求的答案。

#includeusing namespace std;
void solve(){ long long x;
    long long t;
    long long res = 0;
    cin >> x;
    long long one_min[x];
    long long two_max[x];
    vector> arraylist(x);
    for(int i = 0;i < x;i ++){ long long y;
        cin >> y;
        for(int j = 0;j < y;j ++){ cin >> t;
            arraylist[i].push_back(t);
        }
    }
    for(int i = 0;i < x;i ++){ sort(arraylist[i].begin(),arraylist[i].end());
        two_max[i] = arraylist[i][1];
        one_min[i] = arraylist[i][0];
    }
    sort(one_min,one_min + x);
    sort(two_max,two_max + x);
    res += one_min[0];
    for(int i = x - 1;i > 0;i --)
    res += two_max[i];
    cout << res << endl;
}
int main(){ int n;
    cin >> n;
    while(n --){ solve();
    }
    return 0;
}

K - Two Binary Strings （CodeForces - 1861B）

题解：

考虑枚举字符串的位置 i 。首先如果遇到了两个串第i位都是1，那么可以直接覆盖中间的片段，一定能成功。如果遇到不同的位置，考虑找到最近的0与第一位的0做操作。如果找不到就肯定无解。

#includeusing namespace std;
typedef long long ll;
void solve(){ int flag = 0;
    string s1,s2;
    cin >> s1 >> s2;
    for(int i = 1;i < s1.length();i ++){ {if(s1[i] == '1' && s2[i] == '1'){break;}
			if(s1[i] != s2[i])
			{int flag2 = 0;
				for(int j = i + 1;j < s1.length();j ++)
					if(s1[j] == s2[j] && s1[j] == '0')
					{flag2 = 1;
                        i = j;
                        break;
					}
				if(!flag2)
				{flag = 1;
                    break;
				}
			}
		}
    }
    if(flag)cout << "NO" << "\n";
    else cout << "YES" << "\n";
}
int main(){ int n;
    cin >> n;
    while (n -- )
    { solve();
    }
    return 0;
}

L - Tiles Comeback （CodeForces - 1851C）

题解：

给你 n ，k ，再给你长度为 n 的数组代表瓷砖颜色。现在你站在第一块瓷砖上，要走到最后一块瓷砖。问你是否可以找到一个子串，满足以下要求：

①字串必须第一位和末位

②字串长度 p 是 k 的倍数

③字串可以被分为多个连续块，每个块长度为 k

④每个块中的颜色必须相同，相邻的块颜色可以不同

如果第一块瓷砖和最后一块瓷砖颜色相同，只需要在这之中存在k个瓷砖即可，若颜色不同，只需要找到与第一块瓷砖相同的k块此状以及与最后一块瓷砖颜色相同的k块此状，并且比较前者的最后一块和后者的第一块的坐标，如果前者<后者，则输出YES。

#includeusing namespace std;
void solve(){ int n, k;
    cin >> n >> k;
    int st = 0;
    vector c(n + 2);
    for (int i = 1; i <= n; i ++ ) { cin >> c[i];
        st += (c[i] == c[1]);
    }
    if (c[1] == c[n] && st >= k) { puts("YES");
        return ;
    }
    int num = 0, id1 = 0, id2 = 0;
    for (int i = 1; i <= n; i ++ ) { if (c[i] == c[1]) { num ++ ;
            if (num == k) { id1 = i;
                break;
            }
        }
    }
    num = 0;
    for (int i = n; i >= 1; i -- ) { if (c[i] == c[n]) { num ++ ;
            if (num == k) { id2 = i;
                break;
            }
        }
    }
    if (id1 == 0 || id2 == 0 || id1 > id2) puts("NO");
    else puts("YES");
}
int main(){ int n;
    cin >> n;
    while(n --){ solve();
    }
    return 0;
}

M - Arranging Cats （CodeForces - 1921B）

题解：

如果将 一个0转换成1那就对答案产生一花费

如果将 一个1转换成0那就对答案产生一花费

如果将 一个1移动到另一个位置 产生一花费

移动可以同时完成前两者的操作，所以有限选择移动操作一共可以操作min(O1,O2)次，剩下的一定时O1或O2操作，所以最大的花费就是max(O1,O2)。

#includeusing namespace std;
void solve(){ int n, m;
    cin >> n;
    string s, f;
    cin >> s >> f;
    int a = 0, b = 0;
    for (int i = 0; i < n; i++) { if (s[i] == '0' and f[i] == '1') a++;
        if (s[i] == '1' and f[i] == '0') b++;
    }
    cout << max(a, b) << "\n";
}
int main(){ int n;
    cin >> n;
    while (n --)
    { solve();
    }
    return 0;
}

N - Yet Another Permutation Problem （CodeForces - 1858C）

题解：

计算不同的di的个数，该个数的最大值取决于di的值

di的最大值不超过n/2，假设超过了n/2，一个为di，另一个最起码时2di

根据经验式，创造最大值为n/2的全排列即可。

#includeusing namespace std;
void solve(){ int n;
    cin >> n;
    for(int i = 1;i <= n;i += 2){ for(int j = 1;j * i <= n;j *= 2){ cout < int t;
    cin >> t;
    while (t --)
    { solve();
    }
    return 0;
}

#includeusing namespace std;
typedef long long LL;
int n, m;
void solve() { int n, a, b; LL f;
    cin >> n >> f >> a >> b;
    int last = 0;
    for(int i = 0; i < n; i++){ int x;
        cin >> x;
        f -= min((LL)1 * b, (LL)1 * a * (x - last));
        last = x;
    }
    cout << (f > 0 ? "YES" : "NO") << '\n';
}
int main(){ int x;
    cin >> x;
    while(x --){ solve();
    }
    return 0;
}

#includeusing namespace std;
typedef long long LL;
int n, m;
void solve() { char m[3][3];
    int a = 0,b = 0,c = 0;
    char t;
    for(int i = 0;i < 3;i ++){ for(int j = 0;j < 3;j ++){ cin >> t;
            if(t == 'A')a ++;
            else if(t == 'B')b ++;
            else if(t == 'C')c ++;
        }
    }
    if(a < 3)cout << "A\n";
    else if(b < 3)cout << "B\n";
    else cout << "C\n";
}
int main(){ int x;
    cin >> x;
    while(x --){ solve();
    }
    return 0;
}

#includeusing namespace std;
typedef long long LL;
void solve() { int n;
    LL sum = 0;
	cin >> n;
	for(int i = 0 ; i < n ; i ++){int x;
		cin >> x;
		sum += x;
	}	
	LL t = sqrt(sum);
	for(LL i = t - 1 ; i <= t + 1 ; i ++){if(i < 0)
			continue;
		if(i * i == sum){cout <<"YES\n";
			return;
		}
	}
	cout <<"NO\n";
}
int main(){ int x;
    cin >> x;
    while(x --){ solve();
    }
    return 0;
}

#includeusing namespace std;
typedef long long LL;
void solve() { int len,i=2;
		cin >> len;
		string s;
		cin >> s;
		cout << s[0];
		if (len > 1)
			cout << s[1];
		while (iif (s[i + 1] == 'a' || s[i + 1] == 'e' || s[i + 1] == 'u' || s[i + 1] == 'i' || s[i + 1] == 'o')
			{cout << '.' << s[i] << s[i + 1];
				i += 2;
			}
			else
			{cout << s[i] ;
				i ++;
			}
		}
		if (s[len - 1] != 'a' && s[len - 1] != 'e' && s[len - 1] != 'u' && s[len - 1] != 'i' && s[len - 1] != 'o')
			cout << s[len - 1];
		cout << "\n";
}
int main(){ int x;
    cin >> x;
    while(x --){ solve();
    }
    return 0;
}