坐牢一个半小时...D、E待补(太菜了,做的题还是太少了)
A - Constructive 问题集
思路:手画一下发现:n个城市最多能重建n * n 的城市,所以n * m 需要重建max(n , m)个城市。
// Problem: A. Constructive Problems
// Contest: Codeforces - Codeforces Round 915 (Div. 2)
// URL: https://codeforces.com/contest/1905/problem/0
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){
return b > 0 ? gcd(b , a % b) : a;
}
LL lcm(LL a , LL b){
return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){
for(int i = 0 ; i <= n ; i ++){
a[i] = 0;
}
}
void solve()
{
cin >> n >> m;
cout << max(n , m) << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cout.precision(10);
int t=1;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
B - Begginer's Zelda
题意:给定一棵树,能够进行如下操作:选择两个点u , v 。将u到v的简单路径上的所有点缩成一个点,并将与简单路径上相连的边连到那个点上面。
思路:最佳策略必然是选择两个叶子结点,即度为1的点。这样每次操作就能够使得结点数减少2。
因此最小次数为(叶子结点个数 + 1) / 2。
// Problem: B. Begginer's Zelda
// Contest: Codeforces - Codeforces Round 915 (Div. 2)
// URL: https://codeforces.com/contest/1905/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){
return b > 0 ? gcd(b , a % b) : a;
}
LL lcm(LL a , LL b){
return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){
for(int i = 0 ; i <= n ; i ++){
a[i] = 0;
}
}
void solve()
{
cin >> n;
vector<int>deg(n + 5 , 0);
for(int i = 1 ; i < n ; i ++){
int u , v;
cin >> u >> v;
deg[u]++;
deg[v]++;
}
int cnt = 0;
for(int i = 1 ; i <= n ; i ++){
if(deg[i] == 1){
cnt ++;
}
}
cout << (cnt + 1) / 2 << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cout.precision(10);
int t=1;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
C - Largest Subsequence
题意:给定一个字符串,每次操作将选中字符串中最大子序列,并且将他们相对位置循环右移。求最终字符串有序的最小操作数,或输出-1。
题意:考虑如何选最大子序列:按照字母大小从大到小选,当前字母选完之后才选下一个字母,而下一个字母从前一个字母的右端开始选。
然后发现:每一轮操作选择的子序列都是前一个操作的子集(因为最后一个到了第一位,不再选择了,其余都照常选)。因此最终的操作数即为使得第一轮选择的子序列变为有序的操作数。
然后再考虑最终操作完了能否使得整个字符串有序即可。
// Problem: C. Largest Subsequence
// Contest: Codeforces - Codeforces Round 915 (Div. 2)
// URL: https://codeforces.com/contest/1905/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){
return b > 0 ? gcd(b , a % b) : a;
}
LL lcm(LL a , LL b){
return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){
for(int i = 0 ; i <= n ; i ++){
a[i] = 0;
}
}
// z n m i g e c
void solve()
{
set<int>pos[26];
cin >> n;
string s;
cin >> s;
vector<int>change;
vector<int>c(n , 0);
vector<int>vis(n , 1);
for(int i = 0 ; i < n ; i ++){
a[i] = s[i] - 'a';
pos[a[i]].insert(i);
}
int st = -1;
for(int i = 25 ; i >= 0 ;i --){
for(auto it : pos[i]){
if(it > st){
change.pb(it);
vis[it] = 0;
st = it;
}
}
}
int num = 0;
int len = change.size();
for(int i = 0 ; i < len ; i ++){
if(a[change[0]] == a[change[i]])
num++;
}
int op = change.size() - num;
int l = change.size() - 1;
for(int i = 0 ; i < n ; i ++){
if(vis[i]){
c[i] = a[i];
}
else{
c[i] = a[change[l]];
l--;
}
}
for(int i = 1 ; i < n ; i ++){
if(c[i] < c[i - 1]){
cout << -1 << endl;
return;
}
}
cout << op << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cout.precision(10);
int t=1;
cin>>t;
while(t--)
{
solve();
}
return 0;
}