一、高一高二联合NOIP模拟赛11

T1:运输 (transport)

方差最小代表什么？设 \(\sum_{i=1}^{n} a_i = sum\). 最理想的情况是所有结点最终的 \(a_i\) 都变成 \(s = \lfloor {sum \over n} \rfloor\).但是有可能 \(n\) 不能整除 \(sum\)。设 \(las = sum \mod n\)。那么问题转化成有 \(las\) 个 \(a_i\) 变为 \(s\), \(n-las\)个 变成 \(s+1\).

树上背包问题。

设 \(dp_{i,j}\) 表示，以 \(i\) 为根节点的子树中，有 \(j\) 个结点为 \(s+1\)，其它结点都为 \(s\) 的代价。（如果子树内初始的松果的总数量恰好等于最终状态的松果的总数量，也就是自己能内部调整，肯定不会找外面借，或者送到外面。不能自己调整，那么就只能从外面把松果运输进来，或者运输出去，都会经过根节点 \(i\)。所以 \(dp\) 表示把多的（差的）松果放到该子树的根节点 \(i\) 时的代价）

转移方程就很好写了。具体看代码。

这里的时间复杂度似乎是 \(O(n^3)\) 但是可以A。貌似能证明时间复杂度为 \(O(n^2)\)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int,int>
const int MAXN=5005;
vector<pii> G[MAXN],lxx;
int n;
ll a[MAXN];
int read(){
    int x=0;char c=getchar();bool f=0;
    while(c>'9'||c<'0'){f|=(c=='-');c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return f?-x:x;
}
ll siz[MAXN],sum[MAXN];
ll s,las;//las有多少个s+1
//如果一棵子树内少了或者多了，一定会经过根节点进行传输
ll dp[MAXN][MAXN];//以u为根节点的子树中，有x个s+1，若有多余，都移动到u结点上的最小代价
ll f[MAXN];
const ll MAX=1e18;
void dfs(int u,int fa){
    siz[u]=1,sum[u]=a[u];
    dp[u][0]=dp[u][1]=0;//多的都在u上，不用再移动
    for(int i=2;i<=las;i++) dp[u][i]=MAX;
    for(pii t:G[u]){
        int v=t.first;
        if(v==fa)   continue;
        dfs(v,u);
        siz[u]+=siz[v];
        sum[u]+=sum[v];
        for(int i=0;i<=las;i++) f[i]=MAX;
        for(int i=0;i<=min(las,siz[v]);i++){
			ll c=llabs(sum[v]-siz[v]*s-i)*t.second;//有多少个点会经过t这条边
		    //如果有多的，都移动到根节点u，只有这样才能送出去
		    //v子树内多的都在v上，所以只会移动一次
            for(int j=i;j<=min(las,siz[u]);j++){
                f[j]=min(f[j],dp[u][j-i]+dp[v][i]+c);
            }
        }
        for(int i=0;i<=las;i++) dp[u][i]=f[i];
    }
}
void Init(){
    for(int i=1;i<=n;i++)   G[i]=lxx;
    s=0;
}
int main(){
	freopen("transport.in","r",stdin);
	freopen("transport.out","w",stdout);
    int T=read();
    while(T--){
        n=read();
        Init();
        for(int i=1;i<=n;i++){
            a[i]=read();
            s+=a[i];
        }
        las=s%n;
        s/=n;
        for(int i=1;i<n;i++){
            int u=read(),v=read(),w=read();
            G[u].push_back({v,w});
            G[v].push_back({u,w});
        }
        dfs(1,0);
        printf("%lld\n",dp[1][las]);
    }
    return 0;
}

T2：或 (or)

先考虑两种特殊情况：

1. \(R=2^k-1\) 显然能得到的答案区间为 \([L,R]\)
2. \(L=0\).设 \(R\) 的最高的位为第 \(k\) 位。能得到的答案区间为 \([0,2^{k+1}-1]\)

上面两种情况很好证明，不再赘述。

发现两种情况都与 二的整数次幂有关。那么找到最大的，在\([l,r]\) 中的 \(2^k\)。

分成两个区间来看。\([l,2^k-1]\) 和 \([2^k,r]\).

第一个区间能得到答案为 \([l,2^k-1]\)，原因显然。第二个区间能得到的答案为 \([2^k,2^k+2^{p+1}-1]\)（\(p\) 为 \(k\) 之后，\(R\) 中的第一个 \(1\)）因为 \(k\) 位置上的 \(1\) 固定不变了，可以忽略，那么就和特例2是一样的。这样两个答案合并起来就是\([l,2^k+2^{p+1}-1]\)

但是对于\([l,2^k-1]\) 和 \([2^k,r]\)，还两边都取来进行 or操作。在第一个区间的答案 \([l,2^k-1]\) 中取一个数 \(x\),另一个区间的答案 \([2^k,2^k+2^{p+1}-1]\) 中取一个数 \(y\). \(x^y\) 的所有不同的解就是新产生的答案。计算一下可以得到这个区间为 \([L+2^k,2^{k+1}-1]\)。简单解释一下 \(L+2^k=L | 2^k\)，\(2^{k+1}-1=(2^k-1) | 2^k\)。中间的那些数显然也可以取到，不再赘述。

所以最终的答案就是 \([L+2^k,2^{k+1}-1]\) 交 \([l,2^k+2^{p+1}-1]\) 的长度。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	freopen("or.in","r",stdin); 
	freopen("or.out","w",stdout); 
    ll l,r;
    scanf("%lld %lld",&l,&r);
    if(l==r){
        printf("1");
        return 0;
    }
    int k=62,p=62;
    for(k=62;k>=0;k--){
        if(l&(1ll<<k))    continue;
        if(r&(1ll<<k))    break;
    }
    for(p=k-1;p>=0;p--){
        if(r&(1ll<<p))    break;
    }
    ll t=(1ll<<k)+(1ll<<(p+1))-1ll;
    ll ans=t-l+1;
    ll tot=(1ll<<(k+1))-1ll;
    ll L=(l+(1ll<<k));
    if(L<=t)	ans+=tot-t;
    else{
		ans+=tot-L+1ll;
	}
    printf("%lld",ans);
    return 0;
}

二、高一高二联合NOIP模拟赛12

T1:返乡（home）\

一组数，表示同一个人的三个成绩。

首先有一个结论：无论是不是最优解，在一种解下，每组数的和是相等的。设和为 \(x\). 和为 \(x\) 的每一组数都是合法的。自行证明。

所以只用找到这个 能使答案最大的 \(x\).用 \(dp\) 什么的可以搞出来。然后输出和为 \(x\) 的每一组就可以了。

简单的写法

在考场上思路：

已知若两维的数从 \([l,r]\)，那么没有二维偏序的组数为 \(r-l+1\).不再赘述。对于三维的第一维，确定之后，构造一个合法的 \([l,r]\)就可以。设 \(mid= \lceil {n \over 2}\rceil\).第一维为 \(1\) 时，取的区间为 \([mid,n]\),第一维为 \(2\) 时，取的区间为 \([mid-1,n]\),.....,第一维为 \(mid\) 时，取的区间为 \([1,n]\)。第一维为 \(mid+1\) 时，取的区间为 \([1,n-1]\),第一维为 \(mid+2\) 时，取的区间为 \([1,n-2]\)...第一维为 \(n\) 时，取的区间为 \([1,n-mid+1]\)

上面是 \(n\mod 2=1\) 的情况，\(n\mod 2=0\) 的情况略有不同。赛后发现其实就是每一组数的和都为 \(\lceil {3\over 2n} \rceil\).不会证。

\(Code\):

#include<bits/stdc++.h>
using namespace std;
int n;
void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int a[605];
int main(){
   freopen("home.in","r",stdin);
   freopen("home.out","w",stdout);
    scanf("%d",&n);
    n++;
    int x=(n+1)/2;
    int sum=0;
    int t=x;
    for(int i=1;i<=x;i++){
        t--;
        a[i]=n-t;
    }
    t=n-1;
    for(int i=x+1;i<=n;i++){
        a[i]=t;
        t--;
    }
    for(int i=1;i<=n;i++){
    	sum+=a[i];
//    	printf("%d\n",a[i]);
	}
	// printf("%d\n",n-1);
	printf("%d\n",sum);
	t=x;
	for(int i=1;i<=x;i++){
		int s=n-a[i]+1;t=n;
		while(s<=n&&t>=1){
			write(i-1),putchar(' '),write(s-1),putchar(' '),write(t-1),putchar('\n');
//			printf("%d %d %d\n",i-1,s-1,t-1);
			s++,t--;
		}
	}
	for(int i=1;i<=n-x;i++){
		int s=1;t=n-i;
		while(s<=n&&t>=1){
			write(x+i-1),putchar(' '),write(s-1),putchar(' '),write(t-1),putchar('\n');
//			printf("%d %d %d\n",x+i-1,s-1,t-1);
			s++,t--;
		}
	}
    return 0;
}

T2:连接（connect）

开口的：指截断了某一段钢材的选法

封闭的：没有截断任意一段钢材的选法

我们首先考虑，最优的区间，一定不是两侧都可以随便选得。（否则我可以看左侧密度大还是右侧密度大来调整）。同时如果我们开始选某一段，但是没选完，当且仅当我们是在凑质量 \(L\) 或者 \(R\)，不然我为啥不选完.

这样就可以说明只有 \(O(n)\) 段一端开口的。这个枚举左端点/右端点直接做。

剩下的都是两端封闭的情况。设左端点为 \(l\)，右端点为 \(r\)。选取的钢材总密度就是 \({sum_r - sum_{l-1}}\over{u_r-u_{l-1}}\). \(sum\) 是前缀重量，\(u\) 是前缀长度。之前求这一坨的最大值不好求，考虑分数规划。（srds我也不知道是什么大概就是二分答案再移项）设二分值为 \(mid\),要找到一个 \({{sum_r - sum_{l-1}}\over{u_r-u_{l-1}}} >= mid\)。所以 \(mid \times u_l -sum_l>=mid \times u_r -sum_r\).枚举每一个 \(l\) 可以求出这个 \(l\) 对应的右端点合法的区间 \([a,b]\) ( 根据 \(L\),\(R\) 的限制 )。现在要找到 \([a,b]\) 中最小的\(mid \times u_r -sum_r\). 可以用 \(ST\) 表等等，但是要多一个 \(log\)。另一种方法：当 \(l\) 增加时，\(a\),\(b\) 都是单调递增的，所以相当于滑动窗口问题，用一个单调队列来维护即可。

三、高一高二联合NOIP模拟赛13

T1.特种训练\

整个序列只由两种字符构成，考虑把序列分为若干段 “L”，和若干段“R”。

分析可得：

若 a[i] 为 R，他就会一直往右跳，直到遇到一个L，就往回走，走到开始的位置。并且，原序列中，右边的第一个L会被改为 R，这个L 左边的所有 R 不变。

左边也差不多，向左遇到的第一个 R 会被改为 L，这个 R 右边的 L 不变。

当左边没有 R 或者右边没有 L 时，就会结束锻炼。

直到了怎么跳，答案就很好求了，答案跟 min(左边的 R 数量，右边的 L 数量) 有关。

但是细节有点多，要去判断一下先往哪边跳之类的。

T2.

T3.

T4.车站爆破（bomb）

考虑分块。对于每一个块，需要维护的是：1.这个块会删除之前的块中的多少个元素 cnt 2.这个块如果不考虑右面的块对它的影响（可能会删除最后的一些元素），的前缀和。

每一次修改操作，只会更改一个块。

每一次询问，只需要遍历每一个块。对于一个块，设它 不考虑右面的块对它的影响 时，会有 s 个元素保留到下一个块。那么一个块相当于：先删除栈中的 cnt 个元素，然后加入 s 个元素。维护每一个块保留在栈中的元素个数（显然保留下来的只会是sum内靠前的元素），遍历完之后利用 sum 计算。

四、高一联合NOIP模拟赛14

T1.集合\

对子集进行分析：发现子集的个数很多 ( \(2^n-1\) )，但是子集的范围很小 ( \([0,{{n \times (n+1) } \over 2}]\) )。

所以以每一个 子集 为 单位，统计 子集和 为 \(s\) 的子集个数 \(cnt[s]\)。那么最后答案就是 \(\prod _{s=1}^{{n \times (n+1) } \over 2} s^{cnt[s]}\)

T2.出租

引用原题解：

考虑什么时候是无解的。当出现任意一段区间 \([l,r]\) 的租户满足它们人数的和比 \(k*(r-l+1+d)\) 还多的时候，说明无论如何也无法给 \([l,r]\) 中的所有人都安排房间。我们对这个式子进行作差，得到 \(\sum _{l}^{r} (val-k) > k \times d\), \(val\) 就是当前位置的人数。可以这样理解： \([l,r]\) 这些人可以被分配到 \([l,r+d]\) 这些位置，每个位置 \(k\) 个人，那么总共就能够装下 \(k \times (r-l+1+d)\) 个人。将这个式子拆分成 \(k \times (r-l+1) + k \times d\)，其中左边 \(k \times (r-l+1)\) 是变量（因为我们不确定 \(l,r\) 的值，对本题来说，每一个 \(l,r\) 都需要满足要求），左边的值和 \([l,r]\) 的已有租户人数作差，看看差值是否超过 \(k \times d\)，如果超过，则说明无法满足。综上：用线段树维护最大子段和，然后和 \(k \times d\) 比大小即可。

T3.

T4.跳棋

分成两个子问题：

1. 怎么填 ?
2. 对一个确定的序列，怎么算答案。

下文的状态即指填好 ? 后的序列。

因为 \(n\) 的范围显然不支持我们把每一种 状态 枚举出来然后算答案。所以，应该每一种状态之间有关联，或者说，一些状态的答案是相同的。

先分析性质：

到底是怎么跳的？怎么转化？011100 -> 010110，或者011100 -> 110100，发现相邻的两个 1，其中一个跳 的过程，可以视为两个 1 一起平移。任意两个 0 之间， 1 的个数的奇偶性不变。

把两个相邻的 1 叫为 “双1”，那么，如果一种状态确定了，“双1” 和 0 可以随意交换位置，但是单个的 1 不变。设 “双1” 个数为 \(a\), 0 个数为 \(b\)。这个状态会产生的答案为 \(C_{a+b}^{a}\)

所以说，\(a\) 和 \(b\) 都相同的状态，它们的答案是一样的，所以我们需要求出，对于每一对不同的 \(a,b\)，“双1” 个数为 \(a\),0 个数为 \(b\) 的状态数。

用dp实现。设 dp[i][j][k][0/1] 为 前 \(i\) 个数，有 \(j\) 个“双1”，\(k\) 个 0 ，第 \(i\) 个数是否能与 \(i+1\) 一起成为 “双1” 的状态数。

转移见代码。