提前打摆开始写总结。
A
记 \(\displaystle f(x)=\min_{i\in \mathbb{N^+}}\)，求 \(\displaystyle \sum_{i=1}^{n}f(i)\).
答案模 \(1\mathrm{e}9+7\)，多测。
\(n\le 10^{16}\)，\(T\le 10^4\).
从小到大考虑每个 \(f(i)\) 的出现次数。
若当前求 \(x\) 的出现次数，那么符合的是 \(\bmod x\not=0\) 且 \(\bmod y=0,y\in[2,x)\) 的数。
右边即 \(\bmod \operatorname{lcm}(2,\dots,x-1)=0\).
求 \(\bmod x\not=0\) 且 \(\bmod t=0\) 的数的个数，容易得到为 \(\displaystyle \lfloor\frac{n}{t}\rfloor-\lfloor\frac{n}{\operatorname{t,x}}\rfloor\).
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define P 1000000007
using namespace std;
ll read(){
ll x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
ll n;
void solve(){
n=read();
ll ans=0;
for(ll i=2,s=1,lcm;s<=n;s=lcm,i++){
lcm=s/__gcd(s,i)*i;
ans=(ans+(n/s-n/lcm)%P*i)%P;
}
printf("%lld\n",ans);
}
int main(){
int T=read();
while(T--)solve();
return 0;
}
B
*2000.
\(n\times m\) 的矩阵，进行 \(k\) 次操作，每次选出一行或一列，将其和计入贡献，并将每个格子上的值减去 \(p\).
试最大化贡献。
\(n,m,a_{i,j}\le 10^3\)，\(k\le 10^6\)，\(1\le p\le 100\).
显然操作顺序不影响答案最优性。考虑选了 \(i\) 行，\(k-i\) 列，最终需要减去 \(i\cdot (k-i)\cdot p\) 的贡献。
用两个优先队列记录选出若干行或列的最大贡献即可。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define N 1010
#define M 1000010
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
int n,m,k;ll p;
ll line[N],row[N];
priority_queue<ll>A,B;
ll f[M],g[M],ans=-1e18;
int main(){
n=read(),m=read(),k=read(),p=read();
for(int i=1,x;i<=n;i++)
for(int j=1;j<=m;j++)
x=read(),line[i]+=x,row[j]+=x;
for(int i=1;i<=n;i++)A.push(line[i]);
for(int j=1;j<=m;j++)B.push(row[j]);
for(int i=1;i<=k;i++){
ll cur=A.top();A.pop();
f[i]=f[i-1]+cur,A.push(cur-p*m);
}
for(int i=1;i<=k;i++){
ll cur=B.top();B.pop();
g[i]=g[i-1]+cur,B.push(cur-p*n);
}
for(int i=0;i<=k;i++){
ll cur=f[i]+g[k-i]-1ll*i*(k-i)*p;
ans=max(ans,cur);
}
printf("%lld\n",ans);
return 0;
}
C
*2400.
将 \(n\) 个括号串任意拼接，最大化前缀合法括号串个数。
\(n\le 20\)，\(\sum |s|\le 4\times 10^5\).
很好想。垃圾主席树 WA on Test 43，不想玩了。
标签：le,read,2023.11,ch,bmod,ll,define From： https://www.cnblogs.com/SError0819/p/17809126.html