集训Day 1

王浩泽 / 2023-07-25 / 原文

A题：

B题：

刚开始看了眼T1觉得简单，就敲了一个暴力（get65）过了所有样例后就直奔T2，T2是拓扑排序的板子，但由于数据就只写了n^2算法(get100) 又过了所有样例，信心暴涨（当时想着能AK）但T1由于没写筛法，卒。giao~

t1其实很简单就是一个筛法模板（但我居然没看出来！）埃氏筛、欧拉筛均可（当然由于实力问题我……）最后总分165pt

t1程序：

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
long long n,m,z[N];
int p(long long t)
{
    while(t)
    {
        if(z[t]==1) return 0;
        t/=10;
    }
    return 1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>m>>n;
    z[1]=1;
    for(long long i=2;i<=n;i++)
    {
        if(z[i]==1) continue;
        else for(long long j=i*i;j<=n;j+=i) z[j]=1;
    }
    for(long long i=m;i<=n;i++) if(p(i)==1) printf("%lld\n",i);
    return 0;
}

t2程序：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
long long n,m,w,a[N],b[N],d[N],ans=0;
vector<int > mp[N];
int main()
{
     freopen( "study.in", "r", stdin );
     freopen( "study.out", "w", stdout );
    ios::sync_with_stdio(false);
    cin>>n>>m>>w;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        d[v]++;
        mp[u].push_back(v);
    }
    while(1)
    {
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            if(d[i]==0&&a[i]<=w)
            {
                cnt++;
                w+=b[i];
                ans++;
                d[i]=-1;
                for(int j=0;j<mp[i].size();j++) d[mp[i][j]]--;
            }
        }
        if(cnt==0) break;
    }
    cout<<ans;
    return 0;
}