Written by @Yue_chen
=================================================================================================================
镇楼
Update 12.3 11:13
A：再见603（贪心）
题意：
给n个字符串，可以任意两两拼接无限次，最多能拼多少个“603”
思路：
由样例可知，603串必须仅包含603串，如6031、9603等都是不合法的；
因此，记录603的所有子串“603”，“60”，“03”，“6”，“0”，“3”；
然后进行贪心，优先选择用最长的串:
ans += cnt("603");
ans += min(cnt("60"), cnt("3"));
ans += min(cnt("6"), cnt("03"));
ans += min({cnt("6"), cnt("0"), cnt("03")});
计算的时候记得将已经统计的串去除，cnt为该串出现的次数，可以使用map，哈希等方式保存。
时间复杂度O(nlog2****n)
AC代码：
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
map<string, int> mp;
int n; cin>>n;
for(int i=1; i<=n; ++i) {
string s; cin>>s;
mp[s]++;
}
i64 ans = 0;
ans += mp["603"];
int mn = min(mp["60"], mp["3"]);
ans += mn;
mp["60"] -= mn;
mp["3"] -= mn;
mn = min(mp["6"], mp["03"]);
ans += mn;
mp["6"] -= mn;
mp["03"] -= mn;
mn = min({mp["6"], mp["0"], mp["3"]});
ans += mn;
cout<<ans<<"\n";
}
signed main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr);
int t=1;// cin>>t;
while (t--) solve();
return 0;
}
B：欢迎加入实验室（构造+贪心）
题意：
给定一个长度 n 和一个 k ；
我们必须构造一个长度为 n 的序列 a（序列的定义为 1~n 当且仅当出现一次），并且，该序列 |a[i] - i| >= k。
并且使字典序尽可能小。
思路：
答案唯一，一眼贪心。
当 k > n/2 时：
显然数组中间的数无论如何也没法满足|a[i] - i| >= k，直接输出-1。
当 k < n/2 时：
我们根据贪心发现，当 n >= 4*k时，（n, k）可以转移为(n - k*2, k)；
例如：
9 2 5 2
3 4 1 2 7 8 9 5 6 -> 7 8 9 5 6
由于前2*k位满足贪心的最小字典序，k很小时，不论 n 多大时，前缀数组一定为 3 4 1 2。因此我们可以直接推出前缀固定的排列方式。
在上一步的化简之后，n 总会 < 4*k：
我们根据贪心方法手玩一下四个样例：
8 3
4 5 6 7 8 1 2 3
9 3
4 5 6 7 8 9 1 2 3
10 3
4 5 6 1 8 9 10 2 3 7
11 3
4 5 6 1 2 9 10 11 3 7 8
我们发现 当 n <= 3*k时：
将 [1 2 3 ... n-1 n] 循环左移k次，就是最终答案
当 3*k < n < 4*k 时：
出现了一种特殊的构造方式，我们尝试模拟一下这种构造方式；
实际上是先把最后k个数前移k次，再把前k个数后移k次，如果位置撞了，就顺延到后面的位置上，直到找到空位为止。
剩下的数依次从小到大找到一个空的位置。
时间复杂度O(n)
AC代码：
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
int n, k; cin>>n>>k;
vector<int> p(n+1);//答案数组
int m = n/(2 * k);
//初步判断
if(m == 0) {
cout<<"-1\n";
return ;
}
//化简转移
int j = 1;
while(m > 1) {
for(int i=j; i<j+k; ++i) {
p[i] = i + k;
}
for(int i=j+k; i<j+2*k; ++i) {
p[i] = i - k;
}
m--;
j += 2*k;
}
//分讨构造
int len = n-j+1;
if(len > k*3) {
//先放后k个
for(int i=n-k,x=0; i>n-k-k; --i,x++) {
p[i] = n-x;
}
//再放前k个
for(int i=j+k,x=0; x<k and i<=n; i++) {
if(!p[i]) {
p[i] = j+x; x++;
}
}
//最后总小到大依次放
for(int i=j,x=j+k; i<=n; ++i) {
if(!p[i]) {
p[i] = x++;
}
}
}else {
//直接循环左移k次放
for(int i=j; i<=n-k; ++i) {
p[i] = i + k;
}
for(int i=n-k+1; i<=n; ++i) {
p[i] = j + i - (n-k+1);
}
}
for(int i=1; i<=n; ++i) {
cout<<p[i]<<" \n"[i==n];
}
}
signed main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr);
int t=1; //cin>>t;
while (t--) solve();
return 0;
}
C：奶龙日历（数学）
题意：
由题意化简得出式子：
(x-y)*(d-1) % w == 0；d, w已经给出，x，y的上界也分别给出。
求满足上式的二元组(x, y)的数量。
思路：
式子化简由题意给出的两个式子相减得到，不再赘述。
由于y > x，设T = y-x，T的范围为[1, min(m, d)-1]，得到：
T * (d - 1) % w == 0
设 g = gcd(d-1, w)，将w/g，此时d-1 与 (w/g)互质，直接消掉，得到：
T % (w/g) == 0
我们发现T的数量就是(w/g)的所有倍数。
由于我们有了T的范围，所以可以直接用 T/ (w/g) 得到T的数量cnt[T]。
对于每一个T，他的贡献为 min(m, d) - T;
可以发现，随着T的增大，cnt的值是一个等差数列。
因此直接使用等差数列求和公式解决该问题。
最终答案ans = min(m,d) * cnt[T] - (cnt[T] * (cnt[T] -1) / 2 * T);
时间复杂度O(1)
AC代码：
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr i64 M = 1e9;
void solve() {
i64 m, d, w; cin>>m>>d>>w;
i64 k = w / gcd(d-1, w);
i64 q = min(m, d) / k;
cout<<(min(m, d) * q - (q + 1) * q / 2 * k)<<"\n";
}
signed main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr);
int t=1; cin>>t;
while (t--) solve();
return 0;
}
D：计计......计算几何???（签到）
题意：
输出三数相乘。
思路：
注意输入有小数，并且输出保留两位
时间复杂度O(1)
AC代码：
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
long double x, y, z; cin>>x>>y>>z;
cout<<fixed<<setprecision(2)<<(x*y*z)<<"\n";
}
signed main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr);
int t=1;// cin>>t;
while (t--) solve();
return 0;
}
E：零域（思维+二分）
题意：
给定一个 n 和 m，求[1 - n]中 有多少个数的阶乘末尾有m个0。
思路：
注意 n 和 m 很大，思维题 or 数位dp or 矩阵，很显然出题组不会考后面两个( )
直接开玩，枚举发现，每当遇到一个5的倍数，就会多一个0。
ok写完了直接交题。
ok喜提 wa
哦，不小心给0也算进去了，给0删了再交一发。
ok喜提 wa
肯定是我枚举的方法不对，重构一遍代码再交一发。
ok喜提 wa
如果你也红温了评论区请扣111
后来我们发现，25的时候会多出两个0，很简单的道理，两个5，在前面激情wa的可能是小丑吧（）
回归正题。
所以我们需要预处理5的所有幂数，然后使用二分去查找第一次出现m个0的数，锁定之后，向后查找5个数（为什么是5个数，因为更多的数一定会遇到新的5）。
把这5个数都check一遍，合法的都加进答案里面。
还有一个坑点，奶奶的这题卡常，给我十连评测都卡出来了，ok喜提tle，在我细节优化之后，也是成功通过了。
时间复杂度O(log5(1e18) * log2n * T)
AC代码：
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr i64 N = 1e18;
int cnt;
i64 p5[1001];
void solve() {
i64 n, m; cin>>n>>m;
auto check = [&](i64 x) {
i64 ans = 0;
for(int i=1; i<cnt; ++i) {
i64 y = x/p5[i];
if(y == 0) break;
ans += y;
}
return ans;
};
i64 l = 0, r = n;
while(r-l > 1) {
i64 mid = l+r >> 1;
if(check(mid) >= m) r = mid;
else l = mid;
}
vector<i64> v;
for(i64 i=r; i<=min(n, r+5); ++i) {
if(check(i) == m) {
v.push_back(i);
}else {
break;
}
}
if(v.size() == 0) {
cout<<"-1\n";
}else {
cout<<v.size()<<"\n";
for(auto x: v) {
cout<<x<<" ";
} cout<<"\n";
}
}
signed main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr);
for(i64 i=1; N/i>=5; i*=5) {
p5[cnt++] = i;
}
int t=1; cin>>t;
while (t--) solve();
return 0;
}
F：神秘三人组（枚举+前缀和）
题意：
给定一个长度为 n 的数组，和一个 p。
找长度为3。公比为p的子序列的个数。
思路：
直接枚举肯定超时。
枚举第一个数或最后一个数不能保证另外两个数的顺序，因此枚举中间的数，保证统计的子序列不重复，并且有序。
所以我们需要时刻保存前缀和后缀。
枚举时，在后缀中查找a[i] * p的数量，在前缀中查找 a[i]/p的数量，如果a[i]%p != 0 直接跳过。
合法时直接 ans += 前缀合法数量 * 1 * 后缀合法数量。
时间复杂度O(nlog2n)
AC代码：
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
int n, p; cin>>n>>p;
map<i64, i64> mp1, mp2;//mp1为前缀，mp2为后缀
vector<int> a(n+1);
for(int i=1; i<=n; ++i) {
cin>>a[i];
mp2[a[i]]++;
}
i64 ans = 0;
for(int i=1; i<=n; ++i) {//枚举中间的数
mp2[a[i]]--;
if(a[i]%p == 0) {
i64 pre = 1ll * a[i] / p;
i64 suf = 1ll * a[i] * p;
if(mp1.count(pre) and mp2.count(suf)) {
ans += mp1[pre] * mp2[suf];
}
}
mp1[a[i]]++;
}
cout<<ans<<"\n";
}
signed main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr);
int t=1; //cin>>t;
while (t--) solve();
return 0;
}
G：ICPC上海悲剧时刻（贪心）
题意：
给定一个长度为 n 的数组。
你可以选择任意 k 个数（每个数只能用一次）相乘后放回原数组。
求原数组最大值。
思路：
排序后。
如果最大的 k 个数中有 0 直接数组目前数组最大的数。
否则，输出最大的 k 个数之积。
时间复杂度O(nlog2n)
AC代码：
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int M=998244353;
void solve() {
int n, k; cin>>n>>k;
vector<i64> a(n+1);
for(int i=1; i<=n; ++i){
cin>>a[i];
}
sort(a.begin()+1, a.end());
i64 ans = 1;
for(int i=n; i>n-k; --i) {
if(a[i] == 0) {
cout<<a[n]%M<<"\n";
return ;
}
ans = ans * a[i]%M;
}
cout<<ans<<"\n";
}
signed main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr);
int t=1; //cin>>t;
while (t--) solve();
return 0;
}
===
H：等等...这是dp对吧（贪心+枚举）
题意：
给定一个长度为 n 的仅包含 'd' 和 'p' 字符串 s。
对于这个字符串的任意子串s[l, r]，你可以180°翻转它（相当于先reverse 然后 'p'会变成‘d’, 'd'会变成'p')，得到F(s[l, r])
然后你可以选择任意一个子串，用他的F(s[l, r]) 替换 s[l, r]，求最小字典序的串。
当然也可以不操作。
思路：
看见最小字典序直接贪心。
从前到后找第一个不是 d 的位置，然后将该位置固定为左端点 l ，枚举右端点 r ，
依次尝试把F(s[l,r])替换进来，对答案取min。
时间复杂度O(n2)
AC代码：
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
int n; cin>>n;
string s; cin>>s;
string ans = s;
string a1 = s;
for(int i=0; i<n; ++i) {
if(a1[i] == 'p') {
for(int j=i; j<n; ++j) {
for(int k=i; k<=j; ++k) {
a1[k] = (s[j+i-k]=='p'?'d':'p');
}
ans = min(ans, a1);
}
break;
}
}
cout<<ans<<"\n";
}
signed main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr);
int t=1; //cin>>t;
while (t--) solve();
return 0;
}
I：坐得下吗（思维）
题意：
给定 n 组人，要么是 1个， 要么是两个。
给定一排长度为 L 的座位 (所有人数之和必然等于L)
n组人依次来占座位，在最坏情况下是否能保证每一组人都能连坐在一起。
思路：
思考发现，只有当后面的人是2个的时候可能会做不到一起。
直接把前面的每组都想象的比较邪恶，每组都隔一个位置再坐，这样可以让后面2个人一起的队伍没法插空。
相当于把前面每一组占用的座位都+1
当最后没法隔着坐，并且挤不下时，判断还有没有2人一组的队伍还没坐，如果有就是“No”
否则是"Yes"
需要注意一下，如果最后剩了两个座位，并且刚好是两人一组过来，他们是可以做得下的，只不过他们占用的座位就没办法+1了。
时间复杂度O(n)
AC代码：
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
int n, L; cin>>n>>L;
for(int i=1; i<=n; ++i) {
int x; cin>>x;
if(L >= x+1) L -= x+1;//隔着坐能否坐下
else if(L >= x) L -= x;//最后挤一挤能否坐下
else {//只能挤着坐了，且空隙全为1，出现2人一起的就寄
if(x == 2) {
cout<<"No\n";
return ;
}
}
}
cout<<"Yes\n";
}
signed main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr);
int t=1; //cin>>t;
while (t--) solve();
return 0;
}
J：好长的序列（数学+枚举）
题意：
给定一个长度为 n 的数组和一个 x。
数组会循环延长，数组前缀的第几位能超越x
思路：
开一个ans直接循环加数组会tle。
优化一下枚举方法：
求出一个循环数组的总和 sum，x/sum 得到会完整经过 cnt 次循环数组 。
now = cnt * sum，t = n * cnt
用处理好的次数再去再枚举加上一遍数组的每一位，直到大于x时结束。
时间复杂度O(n)
AC代码：
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
int n; cin>>n;
i64 sum = 0;
vector<int> a(n+1);
for(int i=1; i<=n; ++i) {
cin>>a[i];
sum += a[i];
}
i64 x; cin>>x;
i64 cnt = x / sum;
i64 t = cnt * n;
i64 now = cnt * sum;
while(now <= x) {
now += a[t%n+1];
t++;
}
cout<<t<<"\n";
}
signed main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr);
int t=1;// cin>>t;
while (t--) solve();
return 0;
}
K：城市链接（并查集）
题意：
给 n 个点， m个操作，
操作一 联通 a b 点（联通是会传递的）
操作二 询问 a b 是否联通
思路：
并查集板子
时间复杂度O(n+m)
AC代码：
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int f[10001];
int Find(int x) {
if(x == f[x]) return x;
return f[x] = Find(f[x]);
}
void Union(int x, int y) {
int fx = Find(x), fy = Find(y);
if(fx == fy) return ;
f[fx] = fy;
}
void solve() {
int n, m; cin>>n>>m;
for(int i=1; i<=n; ++i) f[i] = i;
for(int i=1; i<=m; ++i) {
int op, a, b; cin>>op>>a>>b;
if(op == 1) {
T.Union(a, b);
}else {
if(T.Find(a) == T.Find(b)) {
cout<<"Y\n";
}else {
cout<<"N\n";
}
}
}
}
signed main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr);
int t=1; //cin>>t;
while (t--) solve();
return 0;
}
L题黑题(tag3000)，不可做题。
完结散花
0 条评论
