反素数

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool f(int x){
    if(x<=1){
        return 0;
    }
    for(int i=2;i<=x/i;i++){
        if(x%i==0){
            return 0;
        }
    }
    return 1;
}
signed main(){
    int n;
    cin >> n;
    int primes[n];
    int xb=-1;
    for(int i=2;i<=n;i++){
        if(f(i)){
            primes[xb+1]=i;
            xb++;
        }
    }
    for(int i=0;i<=xb;i++){
        int k=primes[i];
        int ans=0;
        while(k<=n){
            ans+=n/k;
            k*=primes[i];
        }
        cout << primes[i] << " " << ans << endl;
    }
}

using namespace std;
#define int long long
const int N=1e6+10;
int primes[N],cnt;
bool st[N];
bool is_p[N];
void init(int n){
    memset(st,0,sizeof st);
    cnt=0;
    for(int i=2;i<=n;i++){
        if(!st[i]){
            primes[cnt++]=i;
        }
        for(int j=0;j<cnt&&i*primes[j]<=n;j++){
            st[i*primes[j]]=1;
            if(i%primes[j]==0){
                break;
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    init(50000);
    int l,u;
    while(cin>>l>>u){
        memset(is_p,0,sizeof is_p);
        if(l==1) is_p[0]=1;
        for(int i=0;i<cnt;i++){
            int p=primes[i];
            int start=max(p*2,(l+p-1)/p*p);
            for(int j=start;j<=u;j+=p){
                is_p[j-l]=1;
            }
        }
        int last=-1;
        int min_d=1e18,max_d=-1;
        int c1=-1,c2=-1,d1=-1,d2=-1;
        for(int i=0;i<=u-l;i++){
            if(!is_p[i]){
                int p=i+l;
                if(last!=-1){
                    int d=p-last;
                    if(d<min_d){
                        min_d=d;
                        c1=last;
                        c2=p;
                    }
                    if(d>max_d){
                        max_d=d;
                        d1=last;
                        d2=p;
                    }
                }
                last=p;
            }
        }
        if(max_d==-1){
            cout<<"There are no adjacent primes.\n";
        }else{
            cout<<c1<<","<<c2<<" are closest, "<<d1<<","<<d2<<" are most distant.\n";
        }
    }
    return 0;
}

根据数论基础：如果一个数 X ≤ U X≤U 是合数，那么它必定有一个质因数 P ≤ U P≤ U ​ 。 因为 2 31 − 1 ≈ 46340 2 31 −1 ​ ≈46340，所以我们只需要： 第一步（预处理）：用线性筛求出 1 ∼ 50000 1∼50000 范围内的所有质数。 第二步（区间筛）：对于每组输入的 L L 和 U U，遍历我们预处理出的质数 P P。算出在 [ L , U ] [L,U] 区间内 P P 的倍数，把它们全部标记为合数。为了不爆内存，我们将下标平移，用 is_p[i - L] 来代表数字 i 是否为合数。 第三步（统计）：遍历平移后的标记数组，记录相邻两个质数的差值，不断更新最大值和最小值即可。

C++#include<bits/stdc++.h> using namespace std; #define int long long const int N=1e6+10; int primes[N],cnt; bool st[N]; bool is_p[N]; void init(int n){ memset(st,0,sizeof st); cnt=0; for(int i=2;i<=n;i++){ if(!st[i]){ primes[cnt++]=i; } for(int j=0;j<cnt&&iprimes[j]<=n;j++){ st[iprimes[j]]=1; if(i%primes[j]0){ break; } } } } signed main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); init(50000); int l,u; while(cin>>l>>u){ memset(is_p,0,sizeof is_p); if(l1) is_p[0]=1; for(int i=0;i<cnt;i++){ int p=primes[i]; int start=max(p2,(l+p-1)/pp); for(int j=start;j<=u;j+=p){ is_p[j-l]=1; } } int last=-1; int min_d=1e18,max_d=-1; int c1=-1,c2=-1,d1=-1,d2=-1; for(int i=0;i<=u-l;i++){ if(!is_p[i]){ int p=i+l; if(last!=-1){ int d=p-last; if(d<min_d){ min_d=d; c1=last; c2=p; } if(d>max_d){ max_d=d; d1=last; d2=p; } } last=p; } } if(max_d==-1){ cout<<"There are no adjacent primes.\n"; }else{ cout<<c1<<","<<c2<<" are closest, "<<d1<<","<<d2<<" are most distant.\n"; } } return 0; }

没有上司的舞会 注：不知为何在519周测中只有91分……（接广了

using namespace std;
bool g[6007][6007],r[6007],t[6007];
int dp[6007][2],n,l,k,h=0,z[6007];
int dfs(int q,bool f){
    if(dp[q][f]){
    	return dp[q][f];
	}
    int gg=0;
    if(f){
    	gg=z[q];
	}
    for(int i=1;i<=n;i++){
        if(g[q][i]){
            if(f){
            	gg+=dfs(i,0);
			}
            else{
            	gg+=max(dfs(i,0),dfs(i,1));
			}
        }
    }
    dp[q][f]=gg;
    return gg;
}
int main(){
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>z[i];
    }
    cin>>l>>k;
    while(l!=0||k!=0){
        g[k][l]=1;
        r[l]=1;
        t[k]=1;
        cin>>l>>k;
    }
    for(int i=1;i<=n;i++){
    	if(r[i]==0&&t[i]==1){
    		h=i;
		}
	}
    cout<<max(dfs(h,0),dfs(h,1));
    return 0;
}

没有上司的舞会

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=6003;
int val[N];
vector<int> ve[N];
int f[N][2],n,m;
// f[i][0] 以i为根的子树，并且第i个点没有参加舞会，子树的最大权值
// f[i][1] 以i为根的子树，并且第i个点参加舞会，子树的最大权值
void dfs(int x,int t){// x当前的点，t是x的父亲节点 
    if(f[x][1]!=0)return;
    f[x][1]=val[x];
    for(int y:ve[x]){//遍历x相邻的点 
        if(y==t)continue;//y是x的父节点，continue 
        dfs(y,x);//先算子节点y 
        f[x][0]+=max(f[y][0],f[y][1]);//x节点没有参加，子节点y可以参加也可以不参加，取最大值 
        f[x][1]+=f[y][0];// x节点参加，子节点y不参加 
    }
}
bool st[N];
signed main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> val[i];//输入每个点的权值 
    }
    int a,b,root; 
    while(1){
        cin >> a >> b;
        ve[b].push_back(a);//邻接表存图  单向图 
        st[a]=1;
        if(a==0 && b==0) break;
    }
    for(int i=1;i<=n;i++){
        if(!st[i]) root=i;
    }
     
    dfs(root,0);
    cout << max(f[root][1],f[root][0]);//1号点可参加与不参加，取最大 
}

多重背包二进制优化 https://www.gdgzoi.com/problem.php?cid=2830&pid=2

#include<bits/stdc++.h>
using namespace std;
const int N=25000;
int n,m;
typedef long long ll;
ll f[N];
int v[N],w[N];
int main(){
    cin>>n>>m;
    int cnt=1;
    for(int i=1;i<=n;i++){
        int vi,wi,si;
        cin>>si>>vi>>wi;
        int k=1;
        while(k<=si){
            si-=k;
            v[cnt]=k*vi;
            w[cnt]=k*wi;
            k*=2;
            cnt++;
        }
        if(si){
            v[cnt]=si*vi;
            w[cnt]=si*wi;
            cnt++;
        }
    }
    n=cnt;
    for(int i=1;i<n;i++){
        for(int j=m;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m];
    return 0;
}

多重背包 未经授权不得使用

#include<bits/stdc++.h>
using namespace std;
const int N=2005,V=505;
int n,v;
long long m[N],w[N],s[N];
long long dp[2][V];
vector<pair<int,int>>q;
int main(){
    cin>>n>>v;
    for(int i=1; i<=n; i++)cin>>m[i]>>w[i]>>s[i];
    for(int i=1; i<=n; i++){
        int k=1;
        while(k<=m[i]){
            q.push_back({k*w[i],k*s[i]});
            m[i]-=k;
            k*=2;
        }
        if(m[i]>0)q.push_back({m[i]*w[i],m[i]*s[i]});
    }
    for(auto it:q){
        for(int j=1; j<=v; j++){
            dp[1][j]=dp[0][j];
            if(j>=it.first)dp[1][j]=max(dp[1][j],dp[0][j-it.first]+it.second);
        }
        for(int j=1; j<=v; j++){
            dp[0][j]=dp[1][j];
        }
    }
    cout<<dp[1][v];
    return 0;
}

Problem C: 最长不下降子序列

#include<bits/stdc++.h>
using namespace std;
const int N=1e3;
int n,a[N+5],dp[N+5];
int main(){
    cin>>n;
    for(int i=1; i<=n; i++)cin>>a[i];
    a[0]=-1e9;
    for(int i=1; i<=n; i++){
        for(int j=0; j<n; j++){
            if(a[i]>a[j]){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
    int ans=-1e9;
    for(int i=1; i<=n; i++)ans=max(ans,dp[i]);
    cout<<ans;
    return 0;
}

没有上司的舞会

#include<bits/stdc++.h>
using namespace std;
const int N=6000;
bool g[N+5][N+5];
bool fpre[N+5];
bool fnxt[N+5];
int dp[N+5][2];
int p[N+5];
int n,l,k;
int dfs(int u,bool f){
	if(dp[u][f])return dp[u][f];
	int res=0;
	if(f)res=p[u];
	for(int i=1; i<=n; i++){
		if(g[u][i]){
			if(f)res+=dfs(i,0);
			else res+=max(dfs(i,0),dfs(i,1));
		}
	}
	dp[u][f]=res;
	return res;
}
int main(){
	cin>>n;
	for(int i=1; i<=n; i++){
		cin>>p[i];
	}
	cin>>l>>k;
	while(l!=0||k!=0){
		g[k][l]=1;
		fpre[l]=1;
		fnxt[k]=1;
		cin>>l>>k;
	}
	int head=0;
	for(int i=1; i<=n; i++)
		if(fpre[i]==0&&fnxt[i]==1)
			head=i;
	cout<<max(dfs(head,0),dfs(head,1));
	return 0;
}

树形·T1

#include<bits/stdc++.h>
using namespace std;
const int N=6e3+5;
int f[N][2],n;
vector<int>ve[N];
void dfs(int x,int fa){
	if(f[x][1])return ;
	f[x][1]=1;
	for(int y:ve[x]){
		if(y==fa)continue;
		dfs(y,x);
		f[x][0]+=max(f[y][1],f[y][0]);
		f[x][1]+=f[y][0];
	}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	for(int i=1;i<n;i++){
		int a,b;cin>>a>>b;
		ve[a].push_back(b);
		ve[b].push_back(a);
	}
	dfs(1,0);
	
	cout<<max(f[1][0],f[1][1]);
	return 0;
} 

https://www.gdgzoi.com/problem.php?cid=2832&pid=1

#include<bits/stdc++.h>
using namespace std;
const int N=6000;
bool g[N+5][N+5];
int dp[N+5][2];
int n,u,v;
int dfs(int u,int pre,bool f){
	if(dp[u][f])return dp[u][f];
	int res=f;
	for(int i=1; i<=n; i++){
		if(g[u][i]&&i!=pre){
			if(f)res+=dfs(i,u,0);
			else res+=max(dfs(i,u,0),dfs(i,u,1));
		}
	}
	dp[u][f]=res;
	return res;
}
int main(){
	cin>>n;
	for(int i=1; i<n; i++){
		cin>>u>>v;
		g[u][v]=1;
		g[v][u]=1;
	}
	cout<<max(dfs(1,0,0),dfs(1,0,1));
	return 0;
}

树形dp↑

T3

#include <bits/stdc++.h>
using namespace std;
int n,a[205];
long long dp[205][205];
       
long long cost(int i,int k,int j){
    return 1ll*a[i]*a[k+1]*a[j+1];
}
int main() 
{
    ios::sync_with_stdio(0);cin.tie(0);
       
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i];
    }
       
    for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=2*n;i++){
            int j=i+len-1;
            for(int k=i;k<j;k++){
                dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+cost(i,k,j));
            }
        }
    }
       
    long long ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,dp[i][i+n-1]);
    }
    cout<<ans;
    return 0;
}

T2

#include <bits/stdc++.h>
using namespace std;
int n,a[55];
long long cost(int i,int k,int j){
	return 1ll*a[i]*a[k]*a[j];
}
int main() 
{
    ios::sync_with_stdio(0);cin.tie(0);
	
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	long long dp[55][55];
	for(int i=1;i<=n;i++)dp[i][i]=0;
	for(int len=3;len<=n;len++){
		for(int i=1;i+len-1<=n;i++){
			int j=i+len-1;
			dp[i][j]=0x3f3f3f3f3f3f3f3f;
			for(int k=i+1;k<j;k++){
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+cost(i,k,j));
			}
		}
	}
	cout<<dp[1][n];
    return 0;
}

小视野区间dp T1

#include <bits/stdc++.h>
using namespace std;

int n, a[305];
int sum[305];
int dp[305][305];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    for (int i = 1; i <= n; i++) {
        dp[i][i] = 0;
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            dp[i][j] = 0x3f3f3f3f;
            for (int k = i; k < j; k++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1]);
            }
        }
    }

    cout << dp[1][n] << endl;
    return 0;
}

```cpp
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long a[73];
	long long x;
	cin >> x;
	for(int i = 0;i <= 63;i++) a[i] = pow(i,5);
	//for(int i = 1;i <= 63;i++) cout << a[i] << endl;
    long long b[3];
	bool y=0;
	for(int i = 0;i <=63;i++)
	{
		for(int j = 0;j <=63;j++)
		{
			b[1]=i,b[2]=j;
			if(a[i]+a[j]==x)
			{
				b[1]=i;b[2]=-j;
                y=1;
			}
			if(a[i]-a[j]==x)
			{
				b[1]=i;
                b[2]=j;
				y=1;
			}
			if(y==1)break;
		}
        if(y==1)break;
	}
	cout<<b[1]<<' '<<b[2];
	return 0;
}

C

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,ans=0;
int h[100005];
bool tp[100005];
int main(){
	cin>>n>>m;
	for(int i=1; i<=100004; i++)tp[i]=1;
	for(int i=1; i<=n; i++){
		cin>>h[i];
	}
	for(int i=1; i<=m; i++){
		cin>>a>>b;
		if(h[b]>=h[a])tp[a]=0;
		if(h[a]>=h[b])tp[b]=0;
	}
	for(int i=1; i<=n; i++)if(tp[i])ans++;
	cout<<ans;
	return 0;
}

```cpp
#include<bits/stdc++.h>
using namespace std;
bool b[105];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,k,d;cin>>n>>k;
    
    for(int j=1;j<=k;j++){
        cin>>d;
        for(int i=1;i<=d;i++){
            int x;cin>>x;
            if(b[x]==0)n--;
            b[x]=1;
        }
    }
    cout<<n;
    return 0;
}

赛时讨论区↑

吴奕希 (hzzxwuyixi) @ 12 分钟前
https://www.gdgzoi.com/problem.php?cid=2830&pid=2

提示：该代码仅能获得70分，3个点TLE

#include<bits/stdc++.h>


using namespace std;
const int N=2005,V=505;
int n,v;
int m[N],w[N],s[N];
int dp[2][V];
int main(){
    cin>>n>>v;
    for(int i=1; i<=n; i++)cin>>m[i]>>w[i]>>s[i];
    for(int i=1; i<=n; i++){
        for(int j=1; j<=v; j++){
            for(int k=1; k<=m[i]; k++){
                if(j>=w[i]*k){
                    dp[1][j]=max(dp[1][j],dp[0][j-w[i]*k]+s[i]*k);
                }
            }
        }
        for(int j=1; j<=v; j++){
            dp[0][j]=dp[1][j];
        }
    }
    cout<<dp[1][v];
    return 0;
}```

P448题解 43.138.245.169/d/hongchang/p/P448/solution

https://www.gdgzoi.com/problem.php?cid=2829&pid=5

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 105,mod = 1e6+7;
int n,be,en,dp[N][N*10],a[N];
signed main(){
    ios::sync_with_stdio(false),cin.tie(0);
    cin >> n >> be >> en;dp[0][be] = 1;
    for(int i = 1 ; i < n ; i++){
        cin >> a[i];
        for(int j = 0 ; j <= en ; j++){
            if(dp[i-1][j]){
                int l = j-a[i],r = j+a[i];
                if(l >= 0) dp[i][l] = 1;
                if(r <= en) dp[i][r] = 1; 
            }
        }
    }
     
    for(int i = en ; i >= 0 ; i--) if(dp[n-1][i]) {cout << i;return 0;}
    cout << "-1";return 0;
    return 0;
}

https://www.gdgzoi.com/problem.php?cid=2829&pid=4

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 105,mod = 1e6+7;
int n,m,dp[N][N],a[N];
signed main(){
    ios::sync_with_stdio(false),cin.tie(0);
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++) cin >> a[i];
    dp[0][0] = 1;
    for(int i = 1 ; i <= n ; i++){
        for(int j = 0 ; j <= m ; j++){
            if(dp[i-1][j] == 0 ) continue;
            for(int k = 0 ; k <= a[i]&&k+j<=m ; k++){
                (dp[i][j+k] += dp[i-1][j])%=mod;
            }
        }
    }
    cout << dp[n][m];
    return 0;
}

https://www.gdgzoi.com/problem.php?cid=2829&pid=3

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 105,inf = 0x3f3f3f3f;
int n,k,dp[N][N],a[N][N],put[N][N],maxx = -1;
signed main(){
    ios::sync_with_stdio(false),cin.tie(0);
    cin >> n >> k;
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= k ; j++){
            cin >> a[i][j];
        }
    }
    memset(dp,-0x3f,sizeof dp);
    dp[0][0] = 0;
    for(int i = 1 ; i <= n ; i++){
        for(int p = i ; p <= k-n+i ; p++){
            for(int j = i-1 ; j < p ; j++){
                int pos = dp[i-1][j]+a[i][p];
                if(pos > dp[i][p]){
                    put[i][p] = j;
                    dp[i][p] = pos;
                }
            }
        }
    }
    int last = 0;
    for(int i = n ; i <= k ; i++){
        if(maxx < dp[n][i]){
            last = i;
            maxx = dp[n][i];
        }
    }
    vector<int>pos(n+1);
    for(int i = n ; i >= 1 ; i--){
        pos[i] = last;
        last = put[i][last];
    }
    cout << maxx << "\n";
    for(int i = 1 ; i <= n ; i++) cout << pos[i] << " ";
    return 0;
}

erweidonggui

https://www.gdgzoi.com/problem.php?cid=2829&pid=2

#include <bits/stdc++.h>
using namespace std;
int f[2005][2005];
int main()
{
    string a,b;
    cin >>a>>b;
      
    int n=a.size();
    int m=b.size();
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            if (a[i-1]==b[j-1])
                f[i][j]=f[i-1][j-1]+1;
            else
                f[i][j]=max(f[i-1][j],f[i][j-1]);
        }
    }
    cout <<f[n][m];
}

https://www.gdgzoi.com/problem.php?cid=2829&pid=1

#include <bits/stdc++.h>
using namespace std;
  
int main() {
    int n;
    cin >> n;
      
    int t[105][105];
      
  
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> t[i][j];
        }
    }
      
  
    for (int i = n - 1; i >= 1; i--) {
        for (int j = 1; j <= i; j++) {
            t[i][j] += max(t[i + 1][j], t[i + 1][j + 1]);
        }
    }
    cout << t[1][1] << endl;
      
    return 0;
}
  

https://www.gdgzoi.com/problem.php?cid=2829&pid=0

#include <bits/stdc++.h>


using namespace std;
int f[5009][5009];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<=n;i++)
    {
        f[0][i]=1;
    }
    for(int i=0;i<=m;i++)
    {
        f[i][0]=1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            f[j][i]=(f[j-1][i]+f[j][i-1])%100000;
            //cout<<f[j][i]<<" ";
        }
        //cout<<endl;
    }
    cout<<f[m][n]%10000;
}```