专栏文章

8.26 test

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

文章操作

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

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

T1

签到题，枚举就行
CPP
#include<bits/stdc++.h>
using namespace std;
int main() {
	int t;
	cin>>t;
	while(t--) {
		int a;
		cin>>a;
		int ans=1;
		for(int i=2;i*i<=a;i++){
			if(a%i==0) {
				ans=a/i;
				break;
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}

T2

注意n的数据范围只有1e4，我们可以将结果预处理省时间
首先用埃式筛筛出指数，在埃式筛过程中枚举这个数之前有多少个质数，然后枚举1-n来算出这个区间答案，每个区间的答案是1-i之间的质数数量*（质数数量-1）（正反都算然后排列组合），最后加上就行
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e4+7;
#define mod 99824353
int cnt=0,idx;
bool vis[maxn];
int prime[maxn],ans[maxn];
void Ash() {
	vis[1]=vis[0]=1;
	for(int i=2;i<=10000;i++) {
		if(vis[i]==0) {
			prime[++idx]=i;
			for(int j=i+i;j<=10000;j+=i) {
				vis[j]=1;
			}
		}
		prime[i]=idx;
	}
	return;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Ash();
	int t;
	cin>>t;
	for(int n=1;n<=10000;n++) {
		for(int i=1;i<=n;i++) {
			int k=floor(1.0*n/i);
			ans[n]+=(prime[k]*(prime[k]-1))%mod;
			ans[n]%=mod;
		}
	}
	while(t--) {
		int n;
		cin>>n;
		cnt+=ans[n];
		cnt%=mod;
	}
	cout<<cnt;
	return 0;
}

T3

题目简化就是在字符串中寻找目标字符串使区间内可以拿到更多分
首先注意，ac和wa不能合并不然会100->95，例如wac这样的结构，考场上想到正解思路然后边界没改干净掉了70pts（）
按照dp的思想枚举每一个点最多可以拿到的分数，以这个点为终点，分别寻找前面的3个特殊字符串，找到了就将之前的答案+这个字符串的价值与上一个打擂台
状态转移方程：
CPP
if(s1=="acwa") {
			dp[i]=max(dp[i-3]+a,dp[i]);
}
if(s2=="acwaac") {
		dp[i]=max(dp[i],dp[i-5]+b);
}
if(s3=="acwaacwaac") {
	dp[i]=max(dp[i],dp[i-9]+c);
}
最后写出答案dp[n]
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 3e5+7;
int dp[maxn];
signed main() {
	int n,a,b,c;
	cin>>n>>a>>b>>c;
	string s;
	cin>>s;
	string s1="",s2="",s3="";
	for(int i=0;i<s.size();i++) {
		s1="",s2="",s3="";
		if(i>=3) 
			for(int j=i;j>=i-3;j--) 
				s1=s[j]+s1; 
		if(i>=5)
			for(int j=i;j>=i-5;j--) 
				s2=s[j]+s2;
		if(i>=9)	
			for(int j=i;j>=i-9;j--) 
				s3=s[j]+s3;
		dp[i]=dp[i-1];
		if(s1=="acwa") {
			dp[i]=max(dp[i-3]+a,dp[i]);
		}
		if(s2=="acwaac") {
			dp[i]=max(dp[i],dp[i-5]+b);
		}
		if(s3=="acwaacwaac") {
			dp[i]=max(dp[i],dp[i-9]+c);
		}
	}
	int len=n-1;
	cout<<dp[len];
	return 0;
}

T4

题意简化：从m条边中选出几条边使其可以覆盖所有的点
首先如果n>=m，说明点的数量比边多，如果没有重边就可以选择所有的边
对于30%的数据可以直接搜索
如果选用最大生成树，若图本身不连通，就会出现下面的情况1 而在一个连通块中x个点是一定会有至少x条边连接上，所以只需要考虑点的数量和边的数量，然后用最小生成树的贪心思路来写就行
CPP
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+7;
int fa[maxn];
int edges[maxn];
int node[maxn];
struct Node{
	int u,v,w;
}a[maxn];
int find(int x) {
	if(x==fa[x]) {
		return x;
	}
	return fa[x]=find(fa[x]);
}
bool cmp(Node A,Node B) {
	return A.w>B.w;
}
void solve() {
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) {
		fa[i]=i;
		edges[i]=0;
		node[i]=1; 
	}
	for(int i=1;i<=m;i++) {
		cin>>a[i].u>>a[i].v>>a[i].w;
	}
	sort(a+1,a+1+m,cmp);
	long long ans=0;
	for(int i=1;i<=m;i++) {
		int u=find(a[i].u);
		int v=find(a[i].v);
		if(u==v) {
			if(edges[u]<node[u]) {
				edges[u]++;
				ans+=a[i].w;
			}
		} else {
			if(edges[u]<node[u]||edges[v]<node[v]) {
				fa[u]=v;
				edges[v]+=edges[u];
				node[v]+=node[u];
				ans+=a[i].w;
				edges[v]++;
			}
		}
	}
	cout<<ans<<'\n';
	return ;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin>>T;
	while(T--) {
		solve();
	}
	return 0;
}

评论

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

正在加载评论...