【11.7】【NOIp 热身赛】解题报告及总结

· · 个人记录

今天的比赛感觉很不错啊，真正的贴近NOIp难度，真正的NOIp预热赛

总结一下顺便复习一下知识点

A. 区间方差

——线段树

其实这是一道题的弱化版

P1471 方差

本题只涉及单点修改和区间查询

不用懒标记，直接修改单点

重要的是方差的计算

s^2=\frac{(a_1-\overline{a})^2+(a_2-\overline{a})^2+(a_3-\overline{a})^2…+(a_n-\overline{a})^2}{n} =\frac{n\overline{a}^2-2\overline{a}(a_1+a_2+a_3+…a_n)+a_1^2+a_2^2+a_3^2+…+a_n^2}{n} \because \frac{a_1+a_2+a_3+…+a_n}{n}=\overline{a} \therefore s^2=\frac{a_1^2+a_2^2+a_3^2+…+a_n^2}{n}-\overline{n}^2

因此我们只需维护区间和以及区间平方和就能顺利计算出方差

#include<bits/stdc++.h>
#define lson p<<1
#define rson p<<1|1
using namespace std;
const int N=100010;
const int mod=1e9+7;
typedef long long ll;
struct node{
    int l,r;ll sum,sqsum;
}t[N<<2];
int n,m,a[N];
void exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b) x=1,y=0;
    else exgcd(b,a%b,y,x),y-=a/b*x;
}
ll inv(ll a)
{
    ll x,y;
    exgcd(a,mod,x,y);
    return (x+mod)%mod;
}
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r;
    if(l==r) 
    {
        t[p].sum=a[l];
        t[p].sqsum=1ll*a[l]*a[l]%mod;
        return;
    }
    int mid=l+r>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    t[p].sum=(t[lson].sum+t[rson].sum)%mod;
    t[p].sqsum=(t[lson].sqsum+t[rson].sqsum)%mod;
}
void change(int p,int l,int val)
{
    if(l==t[p].l&&t[p].r==l)
    {
        t[p].sum=val;
        t[p].sqsum=(1ll*val*val%mod);
        return;
    }
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid) change(lson,l,val);
    else change(rson,l,val);
    t[p].sum=(t[lson].sum+t[rson].sum)%mod;
    t[p].sqsum=(t[lson].sqsum+t[rson].sqsum)%mod;
}
ll q_sum(int p,int l,int r)
{
    if(l<=t[p].l&&t[p].r<=r) return t[p].sum;
    int mid=t[p].l+t[p].r>>1;
    ll ret=0;
    if(l<=mid) (ret+=q_sum(lson,l,r))%=mod;
    if(r>mid)  (ret+=q_sum(rson,l,r))%=mod;
    return ret;
}
ll q_sqsum(int p,int l,int r)
{
    if(l<=t[p].l&&t[p].r<=r) return t[p].sqsum;
    int mid=t[p].l+t[p].r>>1;
    ll ret=0;
    if(l<=mid) (ret+=q_sqsum(lson,l,r))%=mod;
    if(r>mid)  (ret+=q_sqsum(rson,l,r))%=mod;
    return ret;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,1,n);
    while(m--)
    {
        int opt,x,y;
        scanf("%d%d%d",&opt,&x,&y);
        if(opt==1) change(1,x,y);
        else
        {
            ll len=inv(y-x+1);
            ll avg=q_sum(1,x,y)*len%mod;
            ll sqsum=q_sqsum(1,x,y);
            ll ans=sqsum*len%mod-avg*avg%mod;
            while(ans<0) ans+=mod;
            printf("%lld\n",ans%mod);
        }
    }
    return 0;
}

B. 攀爬者

——模拟

很水啊，只需按高度排个序计算距离就好了啊

#include<bits/stdc++.h>
using namespace std;
struct node{
    double x,y,z;
}p[50010];
double ans;
bool cmp(node a,node b) {
    return a.z<b.z;
}
double cal(int i,int j){
    return (p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y)+(p[i].z-p[j].z)*(p[i].z-p[j].z);
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z); 
    sort(p+1,p+n+1,cmp);
    for(int i=2;i<=n;i++)
        ans+=sqrt(cal(i-1,i));
    printf("%.3lf",ans);
    return 0;
}

C. 蜈蚣

——dp

刚开始没看出来是dp啊……

之后 \text{sjt\ dalao} A了之后才发现真的是dp啊（为此还遭到了\text{lwz\ dalao} 的嘲讽

那么我们考虑状态

f[i][k]表示考虑到第 i 个位置，已经分了 k+1 段时的最大异或值

注意此处的k+1段时因为k枚举的是能放几个" ^ "符号，因此最开始 m 先要减 1

另外有一个神奇的小技巧，异或和可以像前缀和一样预处理，同一段值进行两次异或又变回原值，因此异或和的操作就是s[i]=s[i-1]\ \ xor\ \ a[i] [l,r]的异或和就是s[r]\ \ xor\ \ s[l-1]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,a[1010],s[1010],f[1010][110];
int main()
{
    scanf("%lld%lld",&n,&m);m--;
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]),
        s[i]=(s[i-1]^a[i]),
        f[i][0]=s[i];
    for(ll i=1;i<=n;i++)
        for(int k=1;k<=min(i-1,m);k++)
            for(int j=k;j<=i;j++)
                f[i][k]=max(f[i][k],f[j-1][k-1]+(s[i]^s[j-1]));
    printf("%lld\n",f[n][m]);
    return 0;
}

D. 漂浮的鸭子

——拓扑排序

题意很明确：求图中的最大环

今天新学到的一种方法——拓扑排序求环

由于拓扑排序每次都是从入度为0的点开始，而环上的点的入度都不会为0，所以环上的点就不会参加排序，也就是说，经过拓扑排序后剩下的边和点构成的都是环。

这样我们就可以直接把每个环扫一遍记录最大环就结束了。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=100010;
int n;
ll ans;
int tot,head[N],deg[N],ver[N],edge[N],nxt[N];
queue <int> q;
void add(int x,int y,int z)
{
    ver[++tot]=y;
    edge[tot]=z;
    nxt[tot]=head[x];
    head[x]=tot;
}
void topu_sort()
{
    while(q.size())
    {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=nxt[i])
        {
            int y=ver[i];
            if(--deg[y]==0) q.push(y);
        }
    }
}
void get_ring()//计算环的大小
{
    ll sum=0;
    while(q.size())
    {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=nxt[i])
        {
            int y=ver[i],z=edge[i];
            if(deg[y]==0) continue;
            sum+=z;
            deg[y]--;
            q.push(y);
        }
    }
    ans=max(ans,sum);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(i,x,y),
        deg[x]++;
    }
    for(int i=1;i<=n;i++) if(!deg[i]) q.push(i);
    topu_sort();
    for(int i=1;i<=n;i++)
        if(deg[i])
        {
            q.push(i);
            get_ring();
        }
    printf("%lld\n",ans);
    return 0;
}

E. 最大差值

又是一道水题，30秒切掉

只需要扫一遍就好了呀

不多说了

#include<bits/stdc++.h>
using namespace std;
int n,a[1000010],ans,minn=2e9;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        minn=min(minn,a[i]);
        ans=max(ans,a[i]-minn);
    }
    printf("%d",ans);
    return 0;
}

F. 随机数生成器

——数学

int work(int x)
{
    if(x==1)return 0;
    else return work(rand(1,x))+1;
}

问\text{work()}返回值的期望是多少

这道题其实并不会做啊但是硬生生地用尽各种手段A掉了……（IOI赛制就是不一样）

sjt大佬还是强啊

这是考场上的代码

////////*此处省略编译优化*/////////
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
double s=1,t=1;
int main()
{
    scanf("%d",&n);
    if(n<=200000000)
    {
        if(n==1) {printf("0.00000");return 0;}
        for(register int i=2;i<=n;i++)
            t=(s*1.0/(i-1))+1,s+=t;
        printf("%.5lf",t);
    }
    else printf("23.06478");
    return 0;
}

正解用到了欧拉常数\gamma=0.5772156649015328…（不会算啊只能百度一下了）

有一个这样的公式1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{n}=\ln n+\gamma

可能跟这个有点关系吧……

#include <cstdio>
#include <cmath>
using namespace std;
double a=1,s=1;
const double ola=0.5772156649015328;
int n,i;
int main()
{
    scanf("%d",&n);
    if(n==1){printf("%.5f\n",0);return 0;}
    if (n<=1000000)
    for(i=2;i<=n;i++)
    {
        a=(double)s/(i-1)+1;
        s+=a;
    }
    else
    a=log(n-1)+1+ola;
    printf("%.5f\n",a);
    return 0;
}

G. 大循环

——秦九韶算法，组合数

一道看起来懵逼实则比较水的题

计算形如a_0x^n+a_1x^{n-1}+a_2x^{n-2}+…+a_n的式子显然可以用秦九韶算法

就是a_0x^n+a_1x^{n-1}+a_2x^{n-2}+…+a_n

=(…((a_0x+a_1)x+a_2)x+…+a_{n-1})x+a_n

然后就是这个循环

for(a[1]=1;a[1]<=n;a[1]++)
    for(a[2]=1;a[2]<=a[1];a[2]++)
        for(a[3]=1;a[3]<=a[2];a[3]++)
        …
        for(a[k]=1;a[k]<=a[k-1];a[k]++)

刚开始看有些懵，之后发现原来很简单

因此循环的次数就相当于从$n$个数中选$k$个数的方案总数，即 $C(n,k) 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=500010;
ll n,m,q,k,fac[N],a[N],val;
int ksm(int a,int b)
{
    int ret=1;
    for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) ret=1ll*ret*a%mod;
    return ret;
}
ll inv(ll x) {return ksm(x,mod-2);}
ll C(ll n,ll m) {return fac[n]*inv(fac[m])%mod*inv(fac[n-m])%mod;}
ll QJS(ll x,int t)
{
    ll ret=0;
    for(int i=t;i>=0;i--) ret=(ret*x%mod+a[i])%mod;
    return ret;
}
void pre()
{
    fac[0]=fac[1]=1;
    for(int i=2;i<N;i++) fac[i]=1ll*fac[i-1]*i%mod;
}
int main()
{
    pre();
    scanf("%lld%lld%lld%lld",&n,&m,&k,&q);
    for(int i=0;i<=m;i++) scanf("%lld",&a[i]);
    val=QJS(q%mod,m);
    printf("%lld\n",1ll*C(n,k)*val%mod);
    return 0;
}

H. 会议座位

——分治

一对老师感到不满当且仅当他们的顺序和原顺序不同，如果原来是正序则现在是逆序，也就是说，原题意变为：求逆序对的个数

一遍sort就解决了呗

要注意的是字符串的处理，用map转一下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<string,int> ss;
string s;
ll ans;
int a[100010],c[100010];
void msort(int l,int r)
{
    if(l==r) return;
    int mid=l+r>>1;
    msort(l,mid);
    msort(mid+1,r);
    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r)
    {
        if(a[i]<=a[j]) c[k++]=a[i++];
        else c[k++]=a[j++],ans+=(ll)mid-i+1;
    }
    while(i<=mid) c[k++]=a[i++];
    while(j<=r)   c[k++]=a[j++];
    for(int i=l;i<=r;i++) a[i]=c[i];
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>s,ss[s]=i;
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        a[i]=ss[s];
    }
    msort(1,n);
    printf("%lld",ans);
    return 0;
}

I. 生日礼物

——质数相关

一道理解质数性质的好题

两个数的\text{lcm}，就是把这两个数分解质因数后每个因子的数目的最大值，即

a={p_1}^{k_1}+{p_2}^{k_2}+{p_3}^{k_3}+…+{p_n}^{k_n} b={p_1}^{s_1}+{p_2}^{s_2}+{p_3}^{s_3}+…+{p_n}^{s_n} lcm(a,b)={p_1}^{max(k_1,s_1)}+{p_2}^{max(k_2,s_2)}+{p_3}^{max(k_3,s_3)}+…+{p_n}^{max(k_n,s_n)}

其中p_x是质数

因此对于一个质因子p_x，我们必须使得两个数的其中一个或两个的质因子p_x的数量等于他们的lcm的p_x的数量。

所以我们对给定的最小公倍数进行质因数分解，对于因数{p_x}^{k_x}对答案的贡献就是2\times k_x-1（即(0,k_x),(k_x,0),(1,k_x),(k_x,1),…,(k_x-1,k_x),(k_x,k_x-1),(k_x,k_x)共2\times k_x-1种可能）

根据乘法原理，最终答案就是\prod_{p_i\in prime} (2k_i-1)

要注意分解质因数我的时候最后可能会剩下一个比\sqrt{n}大的质数，注意要把他也考虑在内

（\text{sjt\ dalao\ tql!!}）

#include<bits/stdc++.h>
using namespace std;
const int N=10000010;
typedef long long ll;
ll n,ans=1;
int tot;
bool flag[N];
int prim[N];
void prime()
{
    for(int i=2;i<=N;i++)
    {
        if(!flag[i]) prim[++tot]=i;
        for(int j=1;j<=tot;j++)
        {
            if(i*prim[j]>N-1) break;
            flag[i*prim[j]]=1;
            if(i%prim[j]==0) break;
        }
    }
}
ll part(ll x)
{
    for(int i=1;i<=tot;i++) 
    {
        int t=1;
        if(prim[i]*prim[i]>n) break;
        while(x%prim[i]==0) x/=prim[i],t++;
        if(t>1) ans*=(2*t-1);
    }
    if(x>1) ans*=(2*(1+1)-1);
    return ans;
}
int main()
{
    prime();
    scanf("%lld",&n);
    printf("%lld",part(n));
    return 0;
}

J. HKE与他的小朋友们

——求环

这个题和P2661信息传递有些类似，这个题同样是要求环

对于每个点，我们按照指定的路线走，如果能到达起点，那么说明路径构成了一个环，环的大小就是一个周期，也就是说只要走环的大小的整倍数，就等价于没走。

根据这一点，我们可以把所有的环都求出，然后用 换座次数 k 对环的大小取模，这样就可以求得每个小朋友换座后的位置。复杂度O(nk)

``` #include<bits/stdc++.h> const int N=1000010; using namespace std; int n,k,to[N],vis[N],ring[N],f[N],ans[N]; void getring(int st) { int p=st,size=0; do{ p=to[p]; vis[p]=1; ring[++size]=p; } while(p!=st); int t=k%size; for(int j=1;j<=size;j++) f[ring[j]]=ring[(j+t-1)%size+1]; } int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&to[i]); for(int i=1;i<=n;i++) if(!vis[i]) getring(i); for(int i=1;i<=n;i++) ans[f[i]]=i; for(int i=1;i<=n;i++) printf("%d ",ans[i]); return 0; } ``` # K. 宝藏 这个题我也不会额……直接上标程把，二维矩阵好像是一个二维树状数组 ``` #include<cstdio> const int maxn=2501; typedef int bit[maxn][maxn]; int n,m,x1,y1,x2,y2,k,ch,a,b,tmp,ans,t; bit pre,ipre,jpre,ijpre; char ins[3]; void read(int&x) { x=0,ch=getchar(); while(ch>'9'||ch<'0')ch=getchar(); while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); } void modify(bit&s,int x,int y,int val) { for(register int i=x;i<=n;i+=i&-i) for(register int j=y;j<=n;j+=j&-j) s[i][j]^=val; } int query(bit&s,int x,int y) { int ans=0; for(register int i=x;i;i-=i&-i)for(register int j=y;j;j-=j&-j)ans^=s[i][j]; return ans; } int Ask(int x2,int y2) { int t=0; if(x2*y2&1)t^=query(pre,x2,y2); if(x2&1)t^=query(jpre,x2,y2); if(y2&1)t^=query(ipre,x2,y2); return t^query(ijpre,x2,y2); } void Change(int i,int j,int val) { modify(pre,i,j,val); if((j-1)&1)modify(jpre,i,j,val); if((i-1)&1)modify(ipre,i,j,val); if((j-1)*(i-1)&1)modify(ijpre,i,j,val); } int Query(int x1,int y1,int x2,int y2){return Ask(x2,y2)^Ask(x1-1,y2)^Ask(x2,y1-1)^Ask(x1-1,y1-1);} void Modify(int x1,int y1,int x2,int y2,int val){Change(x1,y1,val),Change(x2+1,y1,val),Change(x1,y2+1,val),Change(x2+1,y2+1,val);} int main() { read(n),read(m); while(m--) { scanf("%s",ins);read(x1),read(y1),read(x2),read(y2); if(ins[0]=='Q') { ans=Query(x1,y1,x2,y2); for(register int i=0;i<30;++i)putchar(ans&(1<<i)?'2':'1'); puts(""); } else { read(k);t=0; while(k--)read(a),read(b),t^=((b&1)<<(a-1)); if(t)Modify(x1,y1,x2,y2,t); } } return 0; } ``` # L. 简单的函数 ——？？？ 考试的时候一直一直在找f(n)的规律，感觉应该是按照2,4,2,3,2,3,2,3,2,3,2,3的规律出现的，但是到后面出现了不一样的数……然后继续排错把破坏规律的位置排除掉后发现一些位置又有其他的不同破坏规律……总之最后只骗到50pt…… 正解不太懂啊…… ``` #include<cstdio> typedef long long ll; ll pre[55],m,cnt; const ll mod=1e9+7; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} ll qpow(ll a,ll n) { ll res=1; for(;n;(a*=a)%=mod,n>>=1)if(n&1)(res*=a)%=mod; return res; } int main() { pre[1]=1; for(register int i=2;i<=50;++i)pre[i]=lcm(pre[i-1],i); scanf("%lld",&m); for(register int i=3;i<=50;i+=2)cnt+=m/pre[i-1]-m/pre[i]; printf("%lld\n",qpow(2,(m-1)>>1)*qpow(3,cnt-1)%mod*qpow(4,(m>>1)-cnt)%mod); return 0; } ``` # M. 数列游戏 ——区间dp 我们要选择两个不互质的数进行消除，当且仅当两个数中间的所有的数都被消除 $f[i][j]$表示[i,j]区间的数被拿走数后能得到的最大值，因此我们最重要得到的答案是$f[1][n]

最后注意开\text{long long} !（不开爆零开后\text{AC}）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=810;
int n;
ll a[N],s[N],b[N],sum;
ll f[N][N];
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&b[i]),s[i]=s[i-1]+b[i];
        if(i>1&&gcd(a[i-1],a[i])!=1) f[i-1][i]=b[i-1]+b[i];
    }
    for(int len=3;len<=n;len++)//区间长度
        for(int i=1;i<=n-len+1;i++)//左端点
        {
            int j=i+len-1;//右端点
            for(int k=i;k<j;k++) f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);//更新区间最大值
            if(f[i+1][j-1]==s[j-1]-s[i])//说明[i+1,j-1]已经全部被取走，这样j,i才能碰到
                f[i][j]=max(f[i][j],f[i+1][j-1]+(gcd(a[i],a[j])==1?0:(b[i]+b[j])));
            else f[i][j]=max(f[i][j],f[i+1][j-1]);//否则直接转移子区间的值
        }
    printf("%lld",f[1][n]);
    return 0;
}

展示一种更优解法（跑的比标程还快）:（from：\text{lwz dalao}）

先预处理所有区间判断取走是否合法，再在按照线性dp转移

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=810;
int n;
ll a[N],b[N],s[N];
ll f[N][2];//f[i][0/1]表示前i个数中i位置的数不删/删得到的最大值
bool vis[N][N];//vis[i][j]=1表示[i,j]可以全部被取走
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) 
    {
        scanf("%lld",&a[i]);
        if(i>1&&gcd(a[i-1],a[i])!=1) vis[i-1][i]=1;
    }
    for(int i=1;i<=n;i++) scanf("%lld",&b[i]),s[i]=s[i-1]+b[i];
    for(int len=4;len<=n;len+=2)
        for(int i=1;i<=n-len+1;i++)
        {
            int j=i+len-1;
            if(vis[i+1][j-1]&&gcd(a[i],a[j])!=1) {vis[i][j]=1;continue;}
            for(int k=i+1;k<j-1;k++)
                if(vis[i+1][k]&&vis[k+1][j-1]&&gcd(a[i],a[j])!=1)
                    {vis[i][j]=1;break;}
        }
    for(int i=2;i<=n;i++)
        for(int j=1;j<i;j++)
        {
            f[i][0]=max(f[i][0],max(f[j][0],f[j][1]));
            if(vis[j][i]) f[i][1]=max(f[i][1],f[j][0]+b[j]+b[i]+s[i-1]-s[j]);
        }
    printf("%lld",max(f[n][0],f[n][1]));
    return 0;
}

后记：这个是NOIp2018前最后一次大型ACM模拟赛了，感觉自己有些能想出来的部分还是有些欠缺，最后一天再巩固一下基础算法，争取在NOIp2018复赛取得佳绩！

成败之机，在斯一举！