当前位置： 首页 > article >正文

今日codeforces刷题（1）

article 2024/11/30 10:06:04

一、前言

新栏目，每隔几天就保质保量地刷个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个a
		if(i*a>n) break;
		for(i64 j = 0;j<=4000;++j){//剪出j个b那么剩余(n-i*a-j*b)/c个c
			if(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;
}

http://www.kler.cn/a/415464.html

相关文章：

  • 《Java 对象池技术：性能优化的利器》
  • JSP+Servlet实现列表分页功能
  • 011变长子网掩码
  • Java的常识
  • 智慧防汛平台在城市生命线安全建设中的应用
  • 第33章 - Go语言 云原生开发
  • 【Canvas与雷达】简约绿色扫描雷达图标
  • 【Linux】Linux常用命令
  • .net6.0 mvc 传递 model 实体参数（无法对 null 引用执行运行时绑定）
  • Python 3 教程第36篇（XML 解析）
  • 小程序 - 婚礼邀请函
  • 微信小程序Webview与H5通信
  • Vision Transformer（vit）的主干
  • CSS学习记录02
  • AI开发：逻辑回归 - 实战演练- 垃圾邮件的识别（一）
  • SpringMVC跨域问题解决方案
  • BUUCTF—Reverse—GXYCTF2019-luck_guy（9）
  • 003 MATLAB基础计算
  • Cesium 当前位置矩阵的获取
  • 深入探索 Java 中的 Spring 框架
  • ORACLE之DBA常用数据库查询
  • openGauss你计算的表大小，有包含toast表么？
  • ArcGIS pro中的回归分析浅析（加更）关于广义线性回归工具的补充内容
  • 2.安装docker、docker compose
  • 使用Native AOT发布C# dll 提供给C++调用
  • c++趣味编程玩转物联网：树莓派Pico控制 LED点阵屏