\[\text{NOIP模拟赛-2023.11.4} \]
T1 难题
设 \(f(i)\) 表示最小的非 \(i\) 因数的正整数，求 \(\sum\limits_{i=1}^nf(i)\)
\(T\leq 10^4\)，\(1\leq n\leq 10^{16}\)
考虑计算数 \(x\) 对 \(f(1\sim n)\) 的贡献
通过分析可以发现，\(1\sim x\) 能筛掉的数的个数为 \(n-\dfrac{n}{\operatorname{lcm}(1\dots x)}\)，因为如果你不能被筛掉就肯定同时是 \(1\sim x\) 的倍数，这样的数有 \(\dfrac{n}{\operatorname{lcm}(1\dots x)}\) 个。根据容斥可得：\(x\) 的贡献为 \(\dfrac{n}{\operatorname{lcm}(1,\dots x-1)}-\dfrac{n}{\operatorname{lcm}(1\dots x)}\)
code
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL MOD=1e9+7;
LL n,ans;
LL lcm(LL x,LL y)
{
return x/__gcd(x,y)*y;
}
void mian()
{
scanf("%lld",&n);
// if(n==1)
LL last=1,ans=0,i=2;
while(1)
{
LL cur=lcm(last,i);
(ans+=i*(n/last-n/cur)%MOD)%=MOD;
if((last=cur)>n)
break;
i++;
}
printf("%lld\n",ans);
}
int main()
{
freopen("math.in","r",stdin);
freopen("math.out","w",stdout);
int T;
scanf("%d",&T);
while(T--)
mian();
return 0;
}
T2 矩阵游戏
考场直接贪心取最大的行或列获得 \(58\) 分
对于这种操作题，有一部分的操作顺序都是无影响的，比如这题，因为每个点最后的贡献取决于被选中的次数，所以顺序其实不重要
再考虑贪心，如果我们直接贪心显然是错误的，行和列相互交叉会影响贪心的正确性。但我们发现行和行之间是互不影响的，所以我们可以对行和列分别进行贪心，然后枚举操作行的次数进行答案统计
（由于考场写了线段树，于是直接魔改）
code
#include<bits/stdc++.h>
#define pli pair<LL,int>
#define LL long long
using namespace std;
const int N=1e3+10,K=1e6+10;
int n,m,k,d;
LL a[N][N],sum[N<<1],ansr[K],ansc[K];
#define lc(p) p<<1
#define rc(p) p<<1|1
struct SegmentTree
{
LL ad; pli mx;
#define mx(x) tree[x].mx
#define ad(x) tree[x].ad
void add(LL v)
{
ad+=v; mx.first+=v;
}
}tree[N<<3];
pli pmax(pli x,pli y)
{
if(x.first<y.first)
return y;
return x;
}
void pushup(int p)
{
mx(p)=pmax(mx(lc(p)),mx(rc(p)));
}
void build(int p,int l,int r)
{
if(l==r)
{
mx(p)={sum[l],l};
return;
}
int mid=(l+r)>>1;
build(lc(p),l,mid);
build(rc(p),mid+1,r);
pushup(p);
}
void change(int p,int l,int r,int pos,LL v)
{
if(l==r)
return tree[p].add(v),void();
int mid=(l+r)>>1;
if(pos<=mid)
change(lc(p),l,mid,pos,v);
else
change(rc(p),mid+1,r,pos,v);
pushup(p);
}
pli ask(int p,int l,int r,int ql,int qr)
{
if(ql<=l && qr>=r)
return mx(p);
int mid=(l+r)>>1; pli res={-1e18,0};
if(ql<=mid)
res=pmax(res,ask(lc(p),l,mid,ql,qr));
if(qr>mid)
res=pmax(res,ask(rc(p),mid+1,r,ql,qr));
return res;
}
int main()
{
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&k,&d);
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
scanf("%lld",&a[i][j]),sum[i]+=a[i][j];
for(int i=1; i<=m; i++)
for(int j=1; j<=n; j++)
sum[i+n]+=a[j][i];
build(1,1,n+m);
for(int i=1; i<=k; i++)
{
pli res=ask(1,1,n+m,1,n);
ansr[i]=ansr[i-1]+res.first;
change(1,1,n+m,res.second,-1LL*m*d);
}
for(int i=1; i<=k; i++)
{
pli res=ask(1,1,n+m,n+1,n+m);
ansc[i]=ansc[i-1]+res.first;
change(1,1,n+m,res.second,-1LL*n*d);
}
LL ans=-1e18;
for(int i=0; i<=k; i++)
{
ans=max(ans,ansr[i]+ansc[k-i]-1LL*i*(k-i)*d);
if(n==900)
printf("%lld %lld\n",ansr[i],ansc[k-i]);
}
printf("%lld\n",ans);
return 0;
}
T3 括号序列
dp 再不训没救了
很经典的 \(1,-1\) 给 \(\texttt{(},\texttt{)}\) 赋值，设 \(val_i\) 表示每个字符串的权值
我们发现，如果一个串存在某段前缀使得权值小于 \(0\)，则它后面不管接什么都无法产生新的贡献。设存在一个前缀值均大于等于 \(0\) 的串 \(S\)，考虑在它后面接上一个新串 \(T\)
设 \(pre_i\) 表示字符串最小的前缀值
-
若 \(val_S+pre_T<0\)，则接上 \(T\) 后无法再接其它的串产生新的贡献。\(T\) 产生的贡献为第一个等于 \(pre_T\) 的位置之前值为 \(-val_S\) 的个数
-
否则，\(T\) 贡献为 所有值为 \(-val_S\) 的个数
第二种情况可以用桶记录，第一种情况本质上就是在 \(-val_S-1\) 出现之前 \(-val_S\) 的个数，也可以记录
下面考虑转移，设 \(f_s\) 表示选择的字符串集合为 \(s\) 的匹配数。但由于我们之前的讨论都基于串 \(S\) 的前缀值均不小于 \(0\)，所以我们令 \(f_s\) 中的 \(s\) 必须存在一种顺序拼起来是合法的。记 \(flag_s\) 表示 \(s\) 是否合法，不合法则不转移。合法的话枚举 \(i\notin s\)，若是第一种情况我们不更新 \(f\)，直接更新 \(ans\)。若是第二种情况，我们更新 \(f_{s'}\)，并令 \(flag_{s'}=1\)
code
#pragma GCC optimzie(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
const int N=25,M=4e5+10,SS=(1<<20)+10;
int n,pre[N],val[N],sumV[SS],f[SS],ans;
string s[N];
int t[N][M<<1],tt[N][M<<1];
bool legal[SS];
int main()
{
freopen("seq.in","r",stdin);
freopen("seq.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>s[i];
int len=s[i].size(),sum=0;
pre[i]=len+1;
for(int j=0; j<len; j++)
{
sum+=(s[i][j]=='('? 1:-1);
pre[i]=min(pre[i],sum);
t[i][sum+M]++;
if(t[i][sum+M]==1)
tt[i][sum+M+1]=t[i][sum+M+1];
}
val[i]=sum;
}
int S=(1<<n)-1;
for(int s=0; s<=S; s++)
{
for(int i=1; i<=n; i++)
{
if(s&(1<<i-1))
{
sumV[s]=sumV[s^(1<<i-1)]+val[i];
break;
}
}
}
legal[0]=1;
for(int s=0; s<=S; s++)
{
if(!legal[s])
continue;
for(int i=1; i<=n; i++)
{
if(s&(1<<i-1))
continue;
int ss=s^(1<<i-1);
if(sumV[s]+pre[i]<0)
ans=max(ans,f[s]+tt[i][-sumV[s]+M]);
else
f[ss]=max(f[ss],f[s]+t[i][-sumV[s]+M]),legal[ss]=1;
}
}
ans=max(ans,f[S]);
cout<<ans;
return 0;
}
T4 道路
给定 \(n(\leq 32500)\)，构造一个起点是 \(1\)，终点是 \(114\) 的 DAG，满足从起点到终点恰有 \(n-1\) 条路径，且路径权值和取遍 \([0,n]]\) 的整数，点数 \(\leq 18\)，边数 \(\leq 45\)
好题，学到了
取遍 \([0,n]\) 很容易让人想到二进制优美的性质，于是从二进制的角度出发。以 \(n=13\) 为例，将 \(13\) 拆成 \(0+[0,2^2+2^1+2^0],8+[0,2^1+2^0],12+[0,2^0]\) 即可
（不知道为什么我的代码只有 \(90\) 分）
#include<bits/stdc++.h>
using namespace std;
const int N=20,M=50;
int n,s,t,cnt;
struct Graph{int x,y,z;}e[M]; int tot=0;
int main()
{
// freopen("road.in","r",stdin);
// freopen("road.out","w",stdout);
scanf("%d",&n);
if(n==1)
{
printf("2 2\n1 114 0\n1 114 1");
return 0;
}
cnt=__lg(n);
int pw=1,sum=0; //cout<<cnt<<endl;
for(int i=1; i<=cnt; i++)
{
if(i==1)
e[++tot]={2,114,0},e[++tot]={2,114,1};
else
e[++tot]={i+1,i,0},e[++tot]={i+1,i,pw};
sum+=pw; pw<<=1;
}
int tmp=0;
for(int i=cnt; i>=0; i--)
{
// cout<<i<<" "<<tmp<<" "<<sum<<endl;
if(tmp+sum<=n)
{
if(i>=1)
e[++tot]={1,i+1,tmp};
else
e[++tot]={1,114,tmp};
tmp+=sum+1;
}
pw>>=1; sum-=pw;
}
printf("%d %d\n",cnt+2,tot);
for(int i=1; i<=tot; i++)
printf("%d %d %d\n",e[i].x,e[i].y,e[i].z);
return 0;
}