网站建设属于软件开发列举常见的网络营销工具
一、前言
新栏目,每隔几天就保质保量地刷个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;
}