Codeforces Round 898 (Div. 4) （E~H）
1873E - Building an Aquarium
题意：给定一个数组a和一个整数x，进行无限次操作，每次操作可以对数组a中任意一个数进行加法，加数的总和不超过x。求整个数组最小值的最大值。
思路：直接二分找答案。
// Problem: E. Building an Aquarium
// Contest: Codeforces - Codeforces Round 898 (Div. 4)
// URL: https://codeforces.com/contest/1873/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include
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=2e05+10;
const LL mod=1e09+7;
typedef pairpl;
priority_queue, greater >t;
priority_queue q;
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 h[N];
int x;
int n;
bool check(int th){int tot = x;for(int i = 0 ; i < n ; i ++){int t = th - min(h[i] , th);tot -= t;if(tot < 0){return false;}}return true;
}
void solve()
{cin>>n>>x;for(int i = 0 ; i < n ; i ++){cin>>h[i];}long long l = 0 , r = 2e9;while(l < r){int mid = (l + r)/2 + 1; if(check(mid)){l = mid;}else{r = mid - 1;}}cout<>t;while(t--){solve();}return 0;
}
1873F - Money Trees
题意：现有n棵果树和一个整数k，其中每棵树的高度为 , 每棵树上有
个果子。现在规则如下：起初选中第 i 棵树，摘走全部果子，接下来若下一棵树的高度能够整除当前树的高度，则能且只能摘走树上所有果实，以此类推。但是，需要注意总共摘的果子不能超过k。求最多能够连续摘多少棵树上的果子。
思路：用双指针，其中 l 表示最起始的那棵树，r表示最终的树，r 依次递增，看l是否能满足条件，记录( r - l + 1 ) 的最大值。注意果子不超过k即可。
// Problem: F. Money Trees
// Contest: Codeforces - Codeforces Round 898 (Div. 4)
// URL: https://codeforces.com/contest/1873/problem/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include
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=2e05+10;
const LL mod=1e09+7;
typedef pairpl;
priority_queue, greater >t;
priority_queue q;
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 h[N] , a[N] , k , n;
void solve()
{cin>>n>>k;for(int i = 1 ; i <= n ; i ++){cin>>a[i];}for(int i = 1 ; i <= n ; i ++)cin>>h[i];int l = 1;int ans = a[1] > k ? 0 : 1;int tot = a[1];for(int r = 2 ; r <= n ; r ++){if(h[r - 1] % h[r]== 0){tot += a[r];}else{l = r;tot = a[r];}while(tot > k){tot -= a[l];l ++;}ans = max(ans , r - l + 1);} cout<>t;while(t--){solve();}return 0;
}
1873G - ABBC or BACB
题意：现有一个只含有“A”“B”的字符串，起初拥有0枚硬币，接下来能够进行如下操作：
1、选择连续的“AB” ， 将其改为“BC” ，然后获得一枚硬币。
2、选择连续的“BA” ， 将其改为 “CB” ，然后获得一枚硬币。
求能够获得硬币的最大值。
思路：最值问题直接考虑 dp[n][3] ，共有三种状态 ： 1、当前字母不发生改变。2、当前位置的"B"通过情况1变成了“C” 。 3 、当前位置的"A” 通过情况2变成了“B”。
三种状态转移：1、若不改变，则直接从前一位的三种状态取最值转移。2、如果当前位置是“B”且前一位是“A”，需要注意的是：例如“AAB”的情况，变成了“ABC”之后，上一位也能变成“BBC”，这样就能多一枚硬币，所以转移的时候需要一直往前找连续的A直到发现“B”或者起点为止。3、当前位置是“A”时， 如果前一位本来是"B" , 直接从dp[i - 1][0]转移过来 ， 或者前一位通过操作2变成了"B"，从dp[i - 1][2]转移过来。最终输出dp[n + 1][0]即可。
// Problem: G. ABBC or BACB
// Contest: Codeforces - Codeforces Round 898 (Div. 4)
// URL: https://codeforces.com/contest/1873/problem/G
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include
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=1e05+10;
const LL mod=1e09+7;
typedef pairpl;
priority_queue, greater >t;
priority_queue q;
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;
}
void solve()
{string s;cin>>s;int n = s.size();int dp[n + 5][3];//不变 AB-BC BA-CBmemset(dp , -0x3f3f , sizeof dp);dp[0][0] = 0;for(int i = 1 ; i <= n ; i ++){dp[i][0] = max(dp[i - 1][0] , max(dp[i - 1][1] , dp[i - 1][2]));if(i == n)break;if(s[i] == 'B' && s[i - 1] == 'A'){int len = 0;for(int l = i - 1 ; l >= 0 ; l --){if(s[l] == 'A') len++;else break;}dp[i][1] = max(dp[i][1] , dp[i - len][0] + len);}if(s[i] == 'A'){if(s[i - 1] == 'B')dp[i][2] = max(dp[i][2] , dp[i - 1][0] + 1);dp[i][2] = max(dp[i][2] , dp[i - 1][2] + 1);}} cout<>t;while(t--){solve();}return 0;
}
1873H - Mad City
题意：有一个n个点，n条边的图。其中 Valeriu 和 Marcel 在玩游戏，Valeriu 需要逃脱 Marcel的追踪 ，每回合当中，他们能够选择走到相邻的点或者停留在原点。因为 Valeriu 十分了解 Marcel ，所以他能够知道Marcel在本回合当中会往哪里走，从而做出应对。判断 Valeriu 能否 不被 Marcel抓住。
思路：n个点n条边，可以得出这是一颗基环树，若 Valeriu 起初在环上面，那么由于他可以预知对方的行动，他就能够永远的不被 Marcel 抓住。现考虑不在环上的情况： Valeriu 需要走到环上面，这样才能确保自己不会被抓住。若不走到环上面，那么迟早会走到树的叶子结点，那么此时将会无路可走，最终被抓住。因此需要判断的是：Valeriu 到环上所有点的距离和 Marcel 到环上所有点的距离，若其中有一个点Valeriu 小于 Marcel ，那么代表 Valeriu 能够提前到达环上面，这样就能永远不被抓住了。
找环可以用拓扑排序来做，时间复杂度O（n） ， 而距离可以直接BFS一遍做，时间复杂度也是O（n），整体时间复杂度为O（3 * n）。
// Problem: H. Mad City
// Contest: Codeforces - Codeforces Round 898 (Div. 4)
// URL: https://codeforces.com/contest/1873/problem/H
// Memory Limit: 256 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include
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=1e05+10;
const LL mod=1e09+7;
typedef pairpl;
priority_queue, greater >t;
priority_queue q;
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;
}
void solve()
{int n , a , b;cin>>n>>a>>b;vectortr[n + 5];int in[n + 5];memset(in , 0 ,sizeof in);int x , y;for(int i = 1 ; i <= n ; i++){cin>> x >> y;tr[x].pb(y);tr[y].pb(x);in[x] ++;in[y] ++;} unordered_map ishuan;queueq;for(int i = 1 ; i <= n ; i ++){if(in[i] == 1){q.push(i);}}vectorpos;while(!q.empty()){int x = q.front();q.pop();for(auto it : tr[x]){in[it]--;if(in[it] == 1){q.push(it);}}}for(int i = 1 ; i <= n ; i ++){if(in[i] > 1){ishuan[i] = 1;pos.pb(i);}}if(a == b){cout<<"NO\n";}else if(ishuan[a] && ishuan[b]){cout<<"YES\n";}else if(ishuan[b]){cout<<"YES\n";}else{int disa[n + 5];disa[a] = 0;queueq;int vis[n + 5];memset(vis , 0 , sizeof vis);q.push(a);while(!q.empty()){int x = q.front();vis[x] = 1;q.pop();for(auto it : tr[x]){if(!vis[it]){disa[it] = disa[x] + 1;vis[it] = 1;q.push(it);}}}int disb[n + 5];disb[b] = 0;memset(vis , 0 , sizeof vis);q.push(b);while(!q.empty()){int x = q.front();vis[x] = 1;q.pop();for(auto it : tr[x]){if(!vis[it]){disb[it] = disb[x] + 1;vis[it] = 1;q.push(it);}}}int len = pos.size();int f = 0;for(int i = 0 ; i < len ; i ++){if(disb[pos[i]] < disa[pos[i]])f = 1;}if(f){cout<<"YES\n";}elsecout<<"NO\n";}
}
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;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！