专栏文章

8.21-东塘-401-下午-陈-训练

lliu_zheng
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio7htrn
此快照首次捕获于
2025/12/02 14:37
3 个月前
此快照最后确认于
2025/12/02 14:37
3 个月前
查看原文

U370610 回文串

这道题直接用常规实现回文操作 判断前后对称位置是否相同（回文定义）
CPP
#include<bits/stdc++.h>
using namespace std;
string s;
int n;
const int maxn=1e5+10;
char a[maxn];
char b[maxn];
//123456

//12345  5/2=2
bool huiwen(string s){
	int len=s.size()-1;
	for(int i=1;i<=len;i++){
		if(s[i]!=s[len-i+1]){
			return 0;
		}
	}
	return 1;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>s>>n;
	s='#'+s;
	while(n--){
		int x;
		char c;
		cin>>x>>c;
		s[x]=c;
//		cout<<s;
		if(huiwen(s)){
			cout<<"Yes"<<'\n';
		}else{
			cout<<"No"<<'\n';
		} 
	}
	return 0;
}
但是不能拿满分可以稍微优化一下 可以前后不判重复
CPP
bool huiwen(string s){
	int len=s.size()-1;
	for(int i=1;i<=len/2;i++){
		if(s[i]!=s[len-i+1]){
			return 0;
		}
	}
	return 1;
}

U372270 17的时间串

进制处理我首先打了暴力
进制处理有一点忘记了
但后面通过模拟我有思路了
但时间不够了 最后交卷没写完
后面用自己的思路写完就AC了
比较可惜 基础不牢固
（我过了也可能数据水了）
我直接在二进制上处理
我想的是乘法分配律
十进制乘17
相当与二进制每一位乘17
所以我就在乘完一个个进位
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long 
string s;
int x;
// 10011
int cnt=1;
const int maxn=1e6+10;
int a[maxn];
int b[maxn];
signed main(){
	cin>>s;
//	for(int i=s.size()-1;i>=0;i--){
//		x+=(s[i]-'0')*cnt;
//		cnt*=2;
//	}
//	x*=17;
//	int cnt=0;
	int tmp=0;
	for(int i=s.size()-1;i>=0;i--){
		tmp++;
		a[tmp]=(s[i]-'0')*17;
	}
	for(int i=1;i<=1e5;i++){
		if(a[i]>1){
			a[i+1]+=a[i]/2;
			a[i]%=2;
		}
//		cout<<a[i];
	}
	bool flag=0;
	int cnt=0;
	for(int i=tmp+1e5;i>=1;i--){
		if(a[i]==0&&flag==0){
			continue;
		}else {
			flag=1;
		}
		cnt++;
		b[cnt]=a[i];
	}
	for(int i=1;i<=cnt;i++){
		cout<<b[i];
	}
	return 0;
}

U550993 数对问题-基础版

这道题我也是先拿了暴力分
枚举i和j 然后判断题目条件
直接使用了自带__gcd（）
拿了30pts
正解考试没想出来
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
bool zhi(int x){//质数判断
	if(x<=1){
		return 0;
	}
	for(int i=2;i*i<=x;i++){
		if(x%i==0)return 0;
	}
	return 1;
}
signed main(){
	cin>>t;
	while(t--){
		int n,cnt=0;
		cin>>n;
		for(int i=2;i<=n;i++){
			for(int j=2;j<=n;j++){//暴力枚举
				if(zhi(i/__gcd(i,j))&&zhi(j/__gcd(i,j))){//判断题目条件
					cnt++;
				}
			}
		}
		cout<<cnt<<'\n';
	}
	return 0;
}

正解

有两种情况
第一种 i和j自己本身就是质数
第二种 i和j都是某个指数的k倍 k=__gcd(i,j);
从第二种可以得知可以运用埃氏筛

正解

CPP
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
bool vis[maxn];
int N=1e6;
int cnt=0;
int primes[maxn];
void aishishai(){
	vis[0]=vis[1]=1;
	for(int i=2;i<=N;i++){
		if(vis[i]==0){
			primes[cnt++]=i;
			for(int j=i+i;j<=N;j+=i){
				vis[j]=1;
			}
		}
	}
	return ;
}
struct ANS{
	int n,val;
	int id;
	bool operator<(const ANS &rhs)const {
		return n<rhs.n;
	}
}ans[maxn];
long long outp[maxn];
int main(){
	aishishai();
	cnt--;
	int t;
	cin>>t;
	for(int i=1;i<=t;i++){
		cin>>ans[i].n ;
		ans[i].id=i;
	}
	sort(ans+1,ans+t+1);
	int pos=0;
	for(int i=1;i<=t;i++){
		while(pos+1<=cnt&&primes[pos+1]<=ans[i].n){
			pos++;
		}
		long long sum=0;
		for(int j=0;j<=pos;j++){
			long long xx=ans[i].n/primes[j];
			sum+=xx*j;
		}
		sum*=2;
		outp[ans[i].id ]=sum;
	}
	for(int i=1;i<=t;i++){
		cout<<outp[i]<<'\n';
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...