2024百度之星程序设计大赛初赛第一场

补给

可以O(n^2)做，枚举豁免量

#include<bits/stdc++.h> 
#define int long long
using namespace std;
const int N=1010;
struct Node{int p,s;
}node[N];
bool cmp(Node tx,Node ty){return tx.p+tx.s<ty.p+ty.s;
}int n,m;
signed main( )
{std::ios::sync_with_stdio(false);cin>>n>>m;for(int i=1;i<=n;i++){cin>>node[i].p>>node[i].s;}sort(node+1,node+n+1,cmp);int ans=0;for(int i=1;i<=n;i++){int tem=node[i].p/2+node[i].s;int cnt=1;if(tem>m)continue;for(int j=1;j<=n;j++){if(j==i)continue;if(tem+node[j].p+node[j].s<=m){tem+=node[j].p+node[j].s;cnt++;}}ans=max(ans,cnt);}cout<<ans;return 0;
}

跑步

这oj1e7还是可以线性
这个思路23年也考过，每个i，所有j<i会被追上，相遇lcm/i-lcm/j次
每个i的贡献即为1<=j<=i-1 sum(lcm/i-lcm/j)=lcm(n-2i+1)/i

求lcm，计算每个质因子最多出现次数乘起来 ->质因子欧拉筛
线性求逆元

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
const ll p=998244353;
const ll N=1e7+10;
ll n;
ll inv[N];ll ksm(ll a,ll b){
ll res=1;
a=a%mod;
while(b){if(b&1)res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;
}
return res;
}void get_inv(){inv[1]=1;
for(ll i = 2; i <=n; i++){inv[i] = 1ll*(p - p / i) * inv[p % i] % p;// if(i<=50) cout<<inv[i]<<" "<<ksm(i,p-2)<<endl;逆元是对的
}
}
bool vis[N];ll prime[N];ll tot_prime=0;
void sieve(){for(ll i=2;i<=n;i++){if(!vis[i])prime[++tot_prime]=i;for(ll j=1;i*prime[j]<=n;j++){vis[i*prime[j]]=true;if(i%prime[j]==0)break;}
}
}signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;get_inv();sieve();ll lcm=1;for(ll i=1;i<=tot_prime;i++){ll tem=prime[i];int ci=0;while(tem<=1ll*n){tem*=prime[i];ci++;}lcm=lcm*ksm(prime[i],ci)%mod;//必须记录次数之后快速幂}ll ans=0;for(ll i=1;i<=n;i++){ans=(ans+1ll*((n-2*i+1)%mod)%mod*inv[i]%mod)%mod;//cout<<ans<<'\n';}ans=ans*lcm%mod;cout<<(ans%mod+mod)%mod;}