今日codeforces刷题（1）

一、前言

新栏目，每隔几天就保质保量地刷个10道codeforces题左右的样子

筛选1200-1500难度的题，然后按通过题目的人数降序排列的前10题

二、题目总览

三、具体题目

3.1 25A. IQ test

我的代码

看奇数出现的次数为1还是偶数出现的次数为1，然后输出与其他数奇偶性不同的数的下标

// Problem: A. IQ test
// Contest: Codeforces - Codeforces Beta Round 25 (Div. 2 Only)
// URL: https://codeforces.com/problemset/problem/25/A
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;void solve(){int n;std::cin >> n;std::vector<int> v;int cnt0 = 0,cnt1 = 0;for(int i = 0;i<n;++i){int num;std::cin >> num;v.emplace_back(num);if(num&1) ++cnt1;else ++cnt0;}if(cnt1==1){for(int i = 0;i<n;++i){if(v[i]&1){std::cout << i+1 << '\n';break;}}}if(cnt0==1){for(int i = 0;i<n;++i){if((v[i]&1)==0){std::cout << i+1 << '\n';break;}}}
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// std::cin >> t;for(int ti = 0;ti<t;++ti) {solve();}return 0;
}

3.2 4C. Registration system

我的代码

注意不能无脑用std::unordered_set<std::string>来做，会超时；没有出现过的字符串，给cnt数组初始化为0，出现过的字符串根据它出现过的次数来设置cnt

// Problem: C. Registration system
// Contest: Codeforces - Codeforces Beta Round 4 (Div. 2 Only)
// URL: https://codeforces.com/problemset/problem/4/C
// Memory Limit: 64 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;void solve(){int n;std::cin >> n;std::set<std::string> set;std::unordered_map<std::string,int> map;int idx = 1;std::vector<int> cnt(N,0);for(int i = 0;i<n;++i){std::string s;std::cin >> s;if(set.find(s)==set.end()){set.insert(s);map[s] = idx++;cnt[map[s]];std::cout << "OK\n";}else{int cur = cnt[map[s]];std::string tmp = s+std::to_string(++cnt[map[s]]);std::cout << tmp << '\n';}}
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// std::cin >> t;for(int ti = 0;ti<t;++ti) {solve();}return 0;
}

3.3 230B. T-primes

我的代码

预处理出所有满足条件的数放进数组ans中，对于每组数据，如果可以使用二分查找到ans中相同的值，那么就输出YES否则输出NO。判断T-prime的方法：先使用欧拉筛 筛出所有1~1e6的所有素数，那么这些素数的平方都是T-prime。因为我们发现只有素数的平方才会是一个T-prime，因为xi最大为1e12，因此我们需要筛出1e6的所有素数。欧拉筛当然用了jiangly鸽鸽的模板。不用二分极有可能超时，不过我没试过

// Problem: B. T-primes
// Contest: Codeforces - Codeforces Round 142 (Div. 2)
// URL: https://codeforces.com/problemset/problem/230/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;std::vector<int> minp, primes;void sieve(int n) {minp.assign(n + 1, 0);primes.clear();for (int i = 2; i <= n; i++) {if (minp[i] == 0) {minp[i] = i;primes.push_back(i);}for (auto p : primes) {if (i * p > n) {break;}minp[i * p] = p;if (p == minp[i]) {break;}}}
}bool isprime(int n) {return minp[n] == n;
}std::vector<i64> ans;
void pre(){for(i64 i = 1;i<=1000000;++i){if(isprime(i)){ans.emplace_back(i*i);}}
}void solve(){int n;i64 num;std::cin >> n;for(int i = 0;i<n;++i){std::cin >> num;if(*std::lower_bound(ans.begin(),ans.end(),num)==num){std::cout << "YES" << '\n';}else{std::cout << "NO" << '\n';}}
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);sieve(1000010);pre();int t = 1;// std::cin >> t;for(int ti = 0;ti<t;++ti) {solve();}return 0;
}

3.4 492B. Vanya and Lanterns

我的代码

先对a数组排序，然后我们发现只需要找到a[0]-0、(a[1]-a[0])/2、(a[2]-a[1])/2、...、(a[n-1]-a[n-2])/2、l-a[n-1]中的最大值即可，注意中间除以2的时候记得强转成double

// Problem: B. Vanya and Lanterns
// Contest: Codeforces - Codeforces Round 280 (Div. 2)
// URL: https://codeforces.com/problemset/problem/492/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;
int n,l;
void solve(){std::cin >> n >> l;std::vector<int> v;for(int i = 0;i<n;++i){int num;std::cin >> num;v.emplace_back(num);}std::sort(v.begin(),v.end());double max_diff = 0;int max_idx = -1;if(1.0*v[0]>max_diff){max_diff = v[0];max_idx = 0;}for(int i = 0;i<n-1;++i){if(1.0*(v[i+1]-v[i])/2>max_diff){max_diff = 1.0*(v[i+1]-v[i])/2;max_idx = i+1;}}if(1.0*(l-v[n-1])>max_diff){max_diff = 1.0*(l-v[n-1]);max_idx = n;}std::cout << std::fixed << std::setprecision(12) << max_diff << '\n';
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// std::cin >> t;for(int ti = 0;ti<t;++ti) {solve();}return 0;
}

3.5 189A. Cut Ribbon

我的代码1

暴力枚举剪了i个a和j个b的情况，最后剪了多少个c可以用O(1)的时间复杂度间接算出来，那么最终的时间复杂度是O(n^2)，不会超时

// Problem: A. Cut Ribbon
// Contest: Codeforces - Codeforces Round 119 (Div. 2)
// URL: https://codeforces.com/problemset/problem/189/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;void solve(){i64 n,a,b,c;std::cin >> n >> a >> b >> c;i64 ans = 0;for(i64 i = 0;i<=4000;++i){//剪出i个aif(i*a>n) break;for(i64 j = 0;j<=4000;++j){//剪出j个b那么剩余(n-i*a-j*b)/c个cif(i*a+j*b>n) break;i64 rest = n-i*a-j*b;if(rest%c==0){ans = std::max(ans,i+j+(rest/c));} }}std::cout << ans << '\n';
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// std::cin >> t;for(int ti = 0;ti<t;++ti) {solve();}return 0;
}

我的代码2

完全背包实现，我写这题的时候，第一想法居然还是暴力枚举

// Problem: A. Cut Ribbon
// Contest: Codeforces - Codeforces Round 119 (Div. 2)
// URL: https://codeforces.com/problemset/problem/189/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;void solve(){i64 n;std::array<i64,5> a;std::cin >> n >> a[1] >> a[2] >> a[3];std::vector<i64> dp(4e3+5,-INF);dp[0] = 0;for(int i = 1;i<=3;++i){for(int j = a[i];j<=n;++j){dp[j] = std::max(dp[j],dp[j-a[i]]+1);}}std::cout << dp[n] << '\n';
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// std::cin >> t;for(int ti = 0;ti<t;++ti) {solve();}return 0;
}

3.6 466A. Cheap Travel

我的代码

没啥好说的，模拟题，我直接暴力枚举了

// Problem: A. Cheap Travel
// Contest: Codeforces - Codeforces Round 266 (Div. 2)
// URL: https://codeforces.com/problemset/problem/466/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;void solve(){i64 n,m,a,b;std::cin >> n >> m >> a >> b;i64 ans = INF;// ans = std::min(ans,a*n);for(int i = 0;i<=n;++i){ans = std::min(ans,i*b+(n-std::min(n,m*i))*a);}std::cout << ans << '\n';
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// std::cin >> t;for(int ti = 0;ti<t;++ti) {solve();}return 0;
}

3.7 455A. Boredom

我的代码

应该是这10道题里最难的题了

线性dp,dp[i]存的是考虑了前i个数字，可以获得的最高分数。dp[i]可以从dp[i-1]和dp[i-2]转移，具体要看选不选i-1这个数字（注意不是下标），如果不选，则dp[i] = dp[i-2]+i*cnt(i)；如果选，那么dp[i] = dp[i-1]。注意数据范围，需要开long long

// Problem: A. Boredom
// Contest: Codeforces - Codeforces Round 260 (Div. 1)
// URL: https://codeforces.com/problemset/problem/455/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;void solve(){int n;std::cin >> n;std::map<i64,i64> mp;std::vector<i64> a(N,0);i64 max = 0;for(i64 i = 1;i<=n;++i){std::cin >> a[i];++mp[a[i]];max = std::max(max,a[i]);}std::vector<i64> dp(max+5,0);dp[1]=mp[1];for(i64 i = 2;i<=max;++i){dp[i] = std::max(dp[i-1],dp[i-2]+mp[i]*i);}std::cout << dp[max] << '\n';
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// std::cin >> t;for(int ti = 0;ti<t;++ti) {solve();}return 0;
}

3.8 1352C. K-th Not Divisible by n

我的代码

简单的思维题，见代码

// Problem: C. K-th Not Divisible by n
// Contest: Codeforces - Codeforces Round 640 (Div. 4)
// URL: https://codeforces.com/problemset/problem/1352/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;void solve(){i64 n,k;std::cin >> n >> k;if(k%(n-1)!=0){i64 cnt = k/(n-1);i64 ans = cnt*n+(k-cnt*(n-1));std::cout << ans << '\n';}else{i64 ans = k/(n-1)*n-1;std::cout << ans << '\n';}}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;std::cin >> t;for(int ti = 0;ti<t;++ti) {solve();}return 0;
}

3.9 279B. Books

我的代码

双指针的题，我用双端队列实现的（普通队列就可以了），是同样的道理，因为是连续的，所以，能看几本书就先看几本书，如果第一次出现t时间内看不完某一本书，那么也先把它加进队尾，然后一直弹出队头，直到当前所用的时间小于等于t，然后比较队列大小

// Problem: B. Books
// Contest: Codeforces - Codeforces Round 171 (Div. 2)
// URL: https://codeforces.com/problemset/problem/279/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;void solve(){i64 n,t;std::cin >> n >> t;std::vector<i64> a(n+5,0);for(int i = 1;i<=n;++i) std::cin >> a[i];std::deque<i64> deq;i64 sum=0,ans=0;for(int i = 1;i<=n;++i){sum+=a[i];deq.emplace_back(a[i]);while(sum>t&&!deq.empty()){sum-=deq.front();deq.pop_front();}ans = std::max(ans,i64(deq.size()));}std::cout << ans << '\n';
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// std::cin >> t;for(int ti = 0;ti<t;++ti) {solve();}return 0;
}

3.10 514A. Chewbaсca and Number

我的代码1

dfs暴搜，每一位都有换和不换两种状态。注意特殊情况，一个要求答案为正数（0不是正数），一个答案要跟原数位数一致（WA好多次后去看了后台测试点才发现的）。至于时间复杂度，dfs递归的时间复杂度是O(2^len(n))即最坏是2^18的数量级，dfs每次结束前还需要O(len(n))的时间复杂度处理字符串，因此最终的时间复杂度为O(len(n)*2^len(n))约等于18*(2^18)约等于5e7的数量级，不会超时

// Problem: A. Chewbaсca and Number
// Contest: Codeforces - Codeforces Round 291 (Div. 2)
// URL: https://codeforces.com/problemset/problem/514/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;
i64 ans = 1e18+7;
i64 len;
std::string num;
std::vector<int> a(25,0);
void dfs(int u){if(u==len+1){std::string s;for(int i = 0;i<len;++i){if(a[i+1]){s+=char('9'-num[i]+'0');}else{s+=num[i];}}if(s[0]=='0') return;if(std::stoll(s)==0LL) return;ans = std::min(ans,std::stoll(s));return;}a[u] = 0;dfs(u+1);a[u] = 1;dfs(u+1);
}void solve(){std::cin >> num;len = num.size();ans = std::stoll(num);dfs(1);std::cout << ans << '\n';
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// std::cin >> t;for(int ti = 0;ti<t;++ti) {solve();}return 0;
}

我的代码2

贪心模拟，如果第一位反转后是'0'，那么就不反转，对于后面的数字，如果反转变得更小那么就反转，否则不反转。再特判这个数反转后是0的情况，直接输出9，因为只有9反转后是0,且0不是正数

// Problem: A. Chewbaсca and Number
// Contest: Codeforces - Codeforces Round 291 (Div. 2)
// URL: https://codeforces.com/problemset/problem/514/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;void solve(){std::string s;std::cin >> s;for(int i = 0;i<s.size();++i){if(i==0&&s[i]=='9') continue;if(s[i]>='5'){s[i] = '0'+('9'-s[i]);}}i64 ans = std::stoll(s);if(ans==0LL){char c = s[s.size()-1];c = '9';std::cout << c << '\n';}else{std::cout << std::stoll(s) << '\n';}
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// std::cin >> t;for(int ti = 0;ti<t;++ti) {solve();}return 0;
}