Codeforces Round 894 (Div. 3)
A. Gift Carpet
题意：判断一列一个字母有没有“vika”
思路：挨个枚举每一列
#include<bits/stdc++.h>
using namespace std;
char mp[25][25];
char x[]={'v','i','k','a'};
void solve()
{
int m,n;
cin>>m>>n;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cin>>mp[i][j];
}
}
if(n<4){
cout<<"NO"<<endl;
return;
}
int res=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mp[j][i]==x[res]){
res++;
break;
}
}
}
if(res==4) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
int main()
{
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
B. Sequence Game
题意：操作：删除a[i]；结果：给的数组满足a[i]<=a[i+1]
思路：找到a[i]>a[i+1]插入1
#include <bits/stdc++.h>
using namespace std;
const int MAX=4e5;
int a[MAX];
void solve()
{
int n,old,res=1;
cin>>n>>old;
a[0]=old;
for(int i=1;i<n;i++){
int ne;
cin>>ne;
if(old>ne){
a[res]=1;
res++;
}
old=ne;
a[res]=old;
res++;
}
cout<<res<<endl;
for(int i=0;i<res;i++){
cout<<a[i]<<" ";
}
cout<<endl;
}
int main()
{
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
C. Flower City Fence
题意：n个宽为1长为a[i]的长方形组成了一个大图，他对称是否重合
思路：只需要他的高度和数量相同就行（画个图就理解了）
#include <bits/stdc++.h>
using namespace std;
const int MAX=2e5+10;
int a[MAX],b[MAX];
void solve()
{
memset(b,0,sizeof(b));
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for (int i = 1; i <= n; ++i)
{
if (a[i] > n)
{
cout<<"NO\n";
return;
}
b[a[i]] = i;
}
for (int i = n; i >= 1; --i)
{
b[i] = max(b[i], b[i + 1]);
if (a[i] != b[i])
{
cout<<"NO\n";
return;
}
}
cout<<"YES\n";
}
int main()
{
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
D. Ice Cream Balls
题意：选择n个数使得两两组合的方案数为n
思路：两个不同的数可组成的方案数是s*(s-1);后面再加入和之前集合中的数相同的数（增加的方案是(s,s)）,先二分找到s然后再相加
#include <bits/stdc++.h>
using namespace std;
void solve() {
long long int n;
cin >> n;
long long int l = 2, r = 2e+10;
while (l < r) {
long long int mid = (l + r) / 2;
if (mid * (mid - 1) / 2 < n)
l = mid + 1;
else
r = mid;
}
if (l * (l - 1) / 2 == n)
cout << l << "\n";
else {
long long int t = l - 1, s = t * (t - 1) / 2;
cout << t+n-s << "\n";
}
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
E. Kolya and Movie Theatre
题意：满意度：(y-x+1)*d，求最大满意度是多少
思路：假设你看的电影场次分别为x,y,z;总要减去的满意度=(x-0)+(y-x)+(z-y)=z;即可得只需要枚举最后一场
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
multiset<int> st;
int a[200010];
void solve()
{
LL n, m, d, ans = 0, sum = 0;
scanf("%lld%lld%lld", &n, &m, &d);
st.clear();
for (int i = 1; i <= n; ++i)
{
scanf("%lld", &a[i]);
if (a[i] > 0 && st.size() < m)
{
st.insert(a[i]);
sum += a[i];
}
else if (*st.begin() < a[i])
{
sum -= *st.begin();
st.erase(st.begin());
sum += a[i];
st.insert(a[i]);
}
ans = max(ans, sum - i * d);
}
printf("%lld\n", ans);
}
signed main()
{
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
F. Magic Will Save the World
题意：一秒可以生成w个水魔法，f个火魔法，初值均为0，第i个怪兽有si点力量，要想打败它需要至少si点火魔法或者水魔法。求出至少要多少分钟来打败这n个怪兽
思路：在某一秒之后，水魔法和火魔法可以瞬间消灭所有的怪兽，其中水魔法消灭了若干只怪兽，火魔法消灭了若干怪兽，我们只要算出两种魔法分别消灭的怪兽的力量和，除以每秒产生的魔法数，分别向上取整，取大就能得到，当前怪兽分配的最小时间。
#include <bits/stdc++.h>
using namespace std;
bitset<1000005> bt;
void solve() {
bt.reset();
int w, f;
cin >> w >> f;
int ans = 0x3f3f3f3f;
int n;
cin >> n;
bt[0] = 1;
vector<int> s(n);
int tot = 0;
for (int i = 0; i < n; i++) {
cin >> s[i];
tot += s[i];
}
for (int i = 0; i < n; i++) {
bt |= bt << s[i];
}
for (int i = 0; i <= tot; i++) {
if (bt[i]) {
ans = min(ans, max((i + w - 1) / w, (tot - i + f - 1) / f));
}
}
cout << ans << '\n';
}
int main() {
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}