8.26 test

· · 个人记录

T1

签到题，枚举就行

#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）（正反都算然后排列组合），最后加上就行

#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个特殊字符串，找到了就将之前的答案+这个字符串的价值与上一个打擂台
状态转移方程：

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]

#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%的数据可以直接搜索
如果选用最大生成树，若图本身不连通，就会出现下面的情况 而在一个连通块中x个点是一定会有至少x条边连接上，所以只需要考虑点的数量和边的数量，然后用最小生成树的贪心思路来写就行

#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;
}