A. Gifi Carpet
给一个n行m列的字符矩阵，问能否找到四列，第一列中要有字符'v' , 第二列要有字符'i' , 第三列要有字符'k',第四列要有字符'a'.
\(1 <= n,m <= 20\)
题解
签到题。
#include<iostream>
using namespace std;
char s[30][30];
void Solve()
{
int n , m , a , b , c , d;
cin >> n >> m;
for(int i = 1 ; i <= n ; ++i)
cin >> (s[i] + 1);
a = b = c = d = 0;
for(int i = 0 + 1 ; i <= m ; ++i)
{
for(int j = 1 ; j <= n ; ++j)
if(s[j][i] == 'v') { a = i; break; }
if(a) break;
}
for(int i = a + 1 ; i <= m ; ++i)
{
for(int j = 1 ; j <= n ; ++j)
if(s[j][i] == 'i') { b = i; break; }
if(b) break;
}
for(int i = b + 1 ; i <= m ; ++i)
{
for(int j = 1 ; j <= n ; ++j)
if(s[j][i] == 'k') { c = i; break; }
if(c) break;
}
for(int i = c + 1 ; i <= m ; ++i)
{
for(int j = 1 ; j <= n ; ++j)
if(s[j][i] == 'a') { d = i; break; }
if(d) break;
}
if(a && b && c && d)
cout << "YES" << '\n';
else
cout << "NO" << '\n';
}
int main()
{
int T; cin >> T; while(T--) Solve(); return 0;
}
B.Sequence Game
初始有一个长度为m的序列A，然后经过一种变换之后得到序列B。
变换规则如下。
初始B为空，然后第一步写下（加入）\(a_1\)
然后对于\(a_i ， (2<=i<=m)\)，如果\(a_i >= a_{i-1}\)则写下。
例如 \(A = [4 , 3 , 2 , 6 , 3 , 3]\)，则\(B = [4,6,3]\)
其中4是第一个，所以写下。
其中6是A中的第四个元素，它大于前面的2，所以写下。
其中3是A中的最后一个3，它等于前面第5位上的3，所以写下。
现在的情况是，给出序列B，然后构造出一个序列A，使得A变换之后为B。 输出任意一个即可。
假设B的长度为n，则要求构造出的A序列长度m不得超过n的两倍。
\(1 <= n <= 2e5 , 1 <= a_i <= 1e9\)
题解
对于\(b_i >= b_{i-1}\)可以直接抄写在A中。
而如果\(b_i < b_{i-1}\)可以在第i个位置前面加一个等于\(b_i\)的数字。
例如对于\(B = [4 , 6 , 3]\) 构造出的\(A = [4 , 6 , 3 , 3]\)
#include<iostream>
using namespace std;
const int N = 2e5+10;
int B[N] , A[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T , n , m;
cin >> T;
while(T--)
{
cin >> n; m = 1;
for(int i = 1 ; i <= n ; ++i) cin >> B[i];
A[1] = B[1];
for(int i = 2 ; i <= n ; ++i)
{
if(B[i] >= B[i-1])
A[++m] = B[i];
else
A[++m] = B[i] , A[++m] = B[i];
}
cout << m << '\n';
for(int i = 1 ; i <= m ; ++i)
cout << A[i] << ' '; cout << '\n';
}
return 0;
}
C.Flower City Fence
有n个木块，从左到右依次排列，其中第i个木块的高度为\(a_i\).现在要讲这些木块翻转过来，问翻转过后的图形和之前是否一样。
所谓翻转就是从左到右，将木块放倒（旋转90度），左端对齐，依次垒高。
像这个图就是翻转前是\([5 , 4 , 3 , 2 , 1]\) ，翻转后最下方的是原来最左侧的，最上方的是原来最右侧的。
这个就是翻转前后图形一致的。
这个例子翻转前是\([4 , 2 , 1]\)，翻转之后就是\([3 , 2 , 1 , 1]\)所以是不一致的。
另外这些木块的高度是不增的，所以不用担心反转之后出现下面一层比上面一层短的情况。
\(1 <= n <= 2e5 , 1 <= a_i <= 1e9\)
题解
仔细观察一下，翻转之后坐标为i的高度应该是原序列中有多少大于等于i本身的数字个数。
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 2e5+10;
int A[N] , B[N] , t[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T , n , tmp , F;
cin >> T;
while(T--)
{
cin >> n; F = 1;
for(int i = 1 ; i <= n ; ++i)
cin >> A[i];
for(int i = 1 ; i <= n ; ++i)
B[i] = A[i];
sort(B + 1 , B + 1 + n);
for(int i = 1 ; i <= n ; ++i)
{
tmp = lower_bound(B + 1 , B + 1 + n , i) - B;
if(A[i] != n - tmp + 1)
{
F = 0;
break;
}
}
cout << (F ? "YES" : "NO") << '\n';
}
return 0;
}
D.Ice Cream Balls
制作一个双筒冰激凌要用到两个冰球。冰球的种类可以分为1，2，3，4。。。也就是无限多种。现在问需要准备最少多少个冰球使得能够做出的双筒冰激凌的种类数恰好为n。 两个冰球可以选择相同的。
\(\{1 , 2\}\) 与 \(\{1 , 3\}\) 认为是两种方案。
\(\{1 , 2\}\) 与 \(\{2 , 1\}\) 认为是一种方案。
\(1 <= n <= 1e18\)
题解
首先要注意两个关键，一是问的是多少个冰球而非多少种。而是可拼凑的种类数要恰好为n。
能够拼凑数量最多的做法就是选择的冰球两两不同类，如果选择了k个，那么也就是有k种冰球。
凑出来的双筒冰激凌数量就是\(k * (k - 1) / 2\) 种。
但是这样很有可能无法恰好有n种，这时考虑多选一个第i种，那么方案中就会多出\(\{i , i\}\) 这样1个。
而且如果i再多也不会增加方案数了。
最终的方法就是先选不同的，直到再选的话\(k * (k - 1) / 2\)就会大于n。
然后再用之前已经选过的凑足n，需要\(n - k * (k - 1) / 2\)个。
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T;
long long n , m;
cin >> T;
while(T--)
{
cin >> n; m = sqrt(n * 2.0);
while((m + 1) * m / 2 <= n && (m + 1) * m > 0) m++;
cout << m + n - m * (m - 1) / 2 << '\n';
}
return 0;
}
E.Kolya and Moive Theatre
有n场电影即将上映，一天上映一场。而每场电影都有一个欢乐值\(a_i \ \ (-1e9 <= a_i <= 1e9)\),若观看电影就会获得相应的欢乐值。
同时还有一个规则，如果之前看过电影，那么下一个观看的电影的欢乐值就会减少\(d * cnt\)其中d是一个给定的值（正数），cnt是两场电影之间的天数。
最多可以看m场电影。
而在这n场电影的前一天，看过了一场电影。相当于是在第0天看过了一场电影。（这一场不计入m中，但要计算\(d * cnt\) ）
\(1 <= n <= 2e5\)
题解
可以发现，所有\(d * cnt\)的和取决于最晚的一场电影。如果最晚的电影实在第T天，那么总的\(d * cnt = d *T\)所以可以枚举最后一场电影的时间，然后从前面的电影中选出最大的m个（或者少于m个）。
具体一点的话，可以用一个小根堆来维护。小根堆中的元素表示已经选择的元素，新来一个元素时，如果小根堆未满m-1，则直接加入。
如果满了，就先弹出原本的最小的，然后加入当前元素。
这里也可以先加入当前元素，再弹出最小的。 关于是否要强制选择当前元素的细节部分可以稍稍琢磨一下。
#include<iostream>
#include<queue>
using namespace std;
const int N = 2e5+10;
int A[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T , n , m , d;
long long Answer , Sum;
priority_queue<int , vector<int> , greater<int> > Q;
cin >> T;
while(T--)
{
cin >> n >> m >> d; Answer = 0ll; Sum = 0ll;
for(int i = 1 ; i <= n ; ++i)
cin >> A[i];
for(int i = 1 ; i <= n ; ++i)
{
if(A[i] < 0) continue;
if(Q.size() < m)
Q.push(A[i]) , Sum += A[i];
else
if(Q.top() < A[i])
Sum -= Q.top() , Q.pop() ,
Sum += A[i] , Q.push(A[i]);
Answer = max(Answer , Sum - 1ll * d * i);
}
cout << Answer << '\n';
while(Q.size()) Q.pop();
}
return 0;
}
F.Magic Will Save the World
有n个怪兽，每个怪兽都有相应的体力值\(a_i\),当体力值为0时，怪兽死亡。
每秒钟可以获得w个单位的水系能量和f个单位的火系能量（初始都为0）.
对于一个怪物，可以使用水系能量或者火系能量将其打死，消耗等于怪兽体力值的能量。
只能是水系或者火系，不能两者混合。
问最少需要多长时间才能消灭所有的怪兽。
\(1 <= n <= 100 , \ \ \ 1 <= a_i <= 1e4 , \ \ 1 <= w , f <= 1e9\)
题解
二分答案。
将一部分分给水系能量，然后看另一部分的和是否小于等于火系能量的和。
然后反着再来一遍。
可以先用dp预处理出来这些怪物的体力值可以组合成哪些和。
具体见代码，代码更简洁。
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 105;
int Sum;
int s[N] , dp[1000005];
bool Check(int n , int w , int f , int k)
{
int flag = 1;
long long W = 1ll * w * k;
long long F = 1ll * f * k;
if(W >= Sum || F >= Sum) return true;
if(W + F < Sum) return false;
// 可以被W 水系能力处理，并且剩下的部分可以交给火系能量
for(int i = W ; i >= 0 && Sum - i <= F ; --i)
if(dp[i]) return true;
// 同理
for(int i = F ; i >= 0 && Sum - i <= W ; --i)
if(dp[i]) return true;
return false;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T , n , w , f , l , r , mid;
cin >> T;
while(T--)
{
cin >> w >> f >> n; Sum = 0;
for(int i = 1 ; i <= n ; ++i) cin >> s[i] , Sum += s[i];
// 做的时候没有预处理，但是这题的数据小，所以也算是正确的复杂度。
// 写题解的时候才发现QAQ，不亏是div3。
// 没有预处理 1731ms ， 由于处理 156ms。
for(int i = 1 ; i <= Sum ; ++i) dp[i] = 0;
dp[0] = 1;
for(int i = 1 ; i <= n ; ++i)
{
for(int j = Sum ; j >= s[i] ; --j)
dp[j] |= dp[j - s[i]];
}
l = 1; r = Sum;
while(l < r)
{
mid = (l + r) >> 1;
if(Check(n , w , f , mid)) r = mid; else l = mid + 1;
}
cout << l << '\n';
}
return 0;
}
G.The Great Equalizer
给出一个序列。循环执行如下操作。
- 如果序列中只有一个数字，结束并返回这个数字。
- 将序列从小到大排序并去重，设去去重之后有n个元素。
- 则让第一个元素（最小的）加上n，第二个加上n-1，……，最后一个（最大的）加上1.
然后，现在会有一些操作，如将i个元素修改成val。要求对于每个操作之后输出序列变换的结果。
\(1 <= n <= 2e5 , 1 <= a_i <= 1e9\)
输入样例
3
2 4 8
3
1 6
2 10
3 1
输出样例
10 12 15
题解
每次操作（由序列计算最终值的时候）之后相邻元素的差值都会减少一。
所以操作次数就等于排完序之后相邻元素的差值的最大值。
然后还有一点就是最大值一直是最大值。
因为最大值和次大值最少差1，而每次两者之间的差距只会缩小一，直至相等。所以最大值是不变的。
而最终的答案就是最大值加上操作数。
所以要维护排序之后的相邻元素的最大值。
这里使用了两个multiset来维护，一个是S，用来维护原序列，方便找到相邻元素的差值。
另一个是R，用来维护相邻元素的差值。
当有元素发生“有无”的变化时，根据其在S中的状况，相应删减R中的元素。
#pragma GCC optimize(2)
#include<algorithm>
#include<iostream>
#include<set>
using namespace std;
const int N = 2e5+10;
int A[N] , B[N];
multiset<int>::iterator F;
inline void Del(multiset<int> &R , int val)
{
F = R.lower_bound(val);
if(F != R.end())
R.erase(F);
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T , n , Q , x , y , m;
multiset<int> S , R;
multiset<int>::iterator itl , itr;
cin >> T;
while(T--)
{
/*
S维护原序列，方便找到相邻元素的差值。
R维护相邻元素的差值。
*/
cin >> n;
for(int i = 1 ; i <= n ; ++i) cin >> A[i];
for(int i = 1 ; i <= n ; ++i)
S.insert(A[i]);
for(int i = 1 ; i <= n ; ++i) B[i] = A[i];
sort(B + 1 , B + 1 + n);
m = unique(B + 1 , B + 1 + n) - B - 1;
for(int i = 1 ; i < m ; ++i)
R.insert(B[i+1] - B[i]);
cin >> Q;
for(int i = 1 ; i <= Q ; ++i)
{
cin >> x >> y;
itl = S.lower_bound(A[x]);
itr = S.upper_bound(A[x]);
// 这个判断等价于 A[x] 这个元素在S中只有一个
if((++itl) == itr)
{
--itl;
if(itl != S.begin() && itr != S.end())
{
--itl;
Del(R , A[x] - *itl);
Del(R , *itr - A[x]);
R.insert(*itr - *itl);
// 删完之后会产生一个新的
// 如1 2 3 删除2之后会产生 1 3这样差值
}
else
if(itl != S.begin() && itr == S.end())
{
--itl;
Del(R , A[x] - *itl);
}
else
if(itl == S.begin() && itr != S.end())
{
Del(R , *itr - A[x]);
}
}
S.erase(S.lower_bound(A[x]));
// 这里是判断y在S中没有出现
itl = S.lower_bound(y);
if((itl == S.end()) || (*itl != y)) // count() 复杂度
{
itl = S.lower_bound(y);
itr = S.upper_bound(y);
if(itl != S.begin() && itr != S.end())
{
--itl;
R.insert(y - *itl);
R.insert(*itr - y);
Del(R , *itr - *itl);
}
else
if(itl != S.begin() && itr == S.end())
{
--itl;
R.insert(y - *itl);
}
else
if(itl == S.begin() && itr != S.end())
{
R.insert(*itr - y);
}
}
S.insert(y); A[x] = y;
cout << *(--S.end()) + (R.empty() ? 0 : *(--R.end())) << ' ';
}
cout << '\n'; S.clear(); R.clear();
}
return 0;
}
// cout << "RQ-A" << '\n';
// for(int j = 1 ; j <= n ; ++j)
// cout << A[j] << ' ';
// cout << '\n';
// cout << "RQ-S" << '\n';
// for(auto tmp:S)
// cout << tmp << ' ';
// cout << '\n';
// cout << "RQ-T" << '\n';
// for(auto tmp:R)
// cout << tmp << ' ';
// cout << '\n';
// cout << '\n';
// cout << "RQ\n";
// for(auto val:S)
// cout << val << ' ';
// cout << '\n';