CWOI 2019 NOIP 暑假测试二

Problem A 选值

题面

给定$n$个数,从中选出三个数,使得最大的那个减最小的那个的值小于等于$d$,问有多少种选法。

题解

排序一下。当确定最大值为$a_j$时, 用lower_bound找找前面大于等于$a_j-d$的第一个数$a_i$,因此我们可以在$[i,j-1]$中任选两个数作为一个组合,对答案的贡献为$C_{j-i}^{2}$。

代码

#include <iostream>
#include <cstring>
using namespace std;
const int MAXN=100005;
int main(){
#ifndef OFF_LINE
    freopen("select.in","r",stdin);
    freopen("select.out","w",stdout);
#endif
    ios::sync_with_stdio(false);
    int a[MAXN];
    long long ans=0,l,r,n,d;
    cin>>n>>d;
    memset(a,127,sizeof(a));
    for(unsigned int i=1;i<=n;i++){
        cin>>a[i];
    }
    //Select 1st.
    l=1;
    r=n;
    while(l<r-1){
        int mid;
        mid=(l+r)>>1;
        if(a[mid]-a[1]>d){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    while(a[r]-a[1]>d){
        r--;
    }
    l=1;
    ans+=((r-l)*(r-l-1))>>1;
    while(l<n){
        l++;
        r=min(r+1,n);
        while(a[r]-a[l]<=d&&r<=n){
            r++;
        }
        while(a[r]-a[l]>d){
            r--;
        }
        ans+=((r-l)*(r-l-1))>>1;
    }
    cout<<ans<<endl;
    return 0;
}

Problem B 遛狗

题面

wkr养了一条狗,有一天把它带出来遛,路过一片玉米地,他的狗用一种很萌的眼神告诉他饿了(狗要吃玉米?!暂且不讨论这个问题……)。wkr没办法,只好带他进去偷,不过为了不被发现,他们只能往下、左、右三个方向走(有联系吗?),走过的点上如果有玉米,他们就会全部偷走,然后那里的玉米就木有了。这是一个高端的农场,某些点会设有机器人,当你走到这些机器人的时候会掉落一定的玉米(然后就消失了),然后这个机器人就不再起作用了。wkr想到反正都来了,不如多偷一点,所以他想知道从第一行任意一个位置开始,一直到最后一行任意一个位置结束,最终他最多能得到多少的玉米。

题解

这一题我们抽象一下,就是在每一行找一个区间,相邻两行之间所找的区间必须要有重叠的部分,然后求出一个最有方案值。对于每一个选取的区间$[L,R]$,设他是从M处走下去的,那么就肯定满足$M \in [L,R]$。我们倒着来想,我们枚举每一行的入点,找出所有的方案(类似八皇后的全排列)然后再此基础上来确定每一行的最优区间,既然要满足$M \in [L,R]$,那么只要 $L \lt M$即,我们就要让$L=M$,R 同理。好了,这是找到满足当前方案的合法区间,但是不一定是一个最优的(可能 $L$ 再向左
或者$R$再向右能使整个区间值更大),所以我们只需要让$L$和$R$分别向左和向右来确定最大区间的$L$和$R$的位置,然后就能够得到最优值了。至于怎么确定$L$和$R$的位置把区间$[L,R]$分成$[L,M] + [M,R] - {M}$ ($M$为当前行到下一行的入点位置),那么我们维护$L$和$R$指针,在维护一个$L_{max}$和$R_{max}$,先让$L$从前面确定好的位置向左,每次求出$[L,M]$的和取$L_{max}$取最大值,$R$同理,最后区间的最优值就为$L_{max}+R_{max}-M$。再看看复杂度,$O(N^N)$,显然是不能承受的,不过很明显可以感觉到,特别是越到下面,他们重复计算的次数就越多,所以想到记忆化。复杂度就不分析了,大概是$O(N^4)$或者$O(N^3)$的样子。

代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int main() {
    ios::sync_with_stdio( false );
    int n, flag, tot, ans, sum[55][55], Map[55][55], dp[55][55][55];
    cin >> n;
    for ( int i = 1; i <= n; ++i )
        for ( int j = 1; j <= n; ++j ) {
            cin >> Map[i][j];
            tot += Map[i][j];
            if ( Map[i][j] < 0 )
                flag = 1;
            sum[i][j] = sum[i][j - 1] + Map[i][j];
        }
    if ( !flag ) {
        cout << tot << endl;
        return 0;
    }
    for ( int i = 1; i <= n; ++i )
        for ( int j = 1; j <= n; ++j )
            for ( int k = j; k <= n; ++k ) {
                for ( int l = 1; l <= k; ++l )
                    for ( int m = j; m <= n; ++m )
                        dp[i][j][k] = max( dp[i][j][k], dp[i - 1][l][m] );
                dp[i][j][k] += sum[i][k] - sum[i][j - 1];
            }
    for ( int i = 1; i <= n; ++i )
        for ( int j = i; j <= n; ++j )
            ans = max( ans, dp[n][i][j] );
    cout << ans << endl;
    return 0;
}

Problem C

题面

有一棵$n$个点的有根树,他有$m$个叶子结点(叶子结点是那些没有孩子的结点)。边由父亲指向孩子。数字$1$到$m$被分配到每一个叶子中。每一个叶子有一个数字,并且每一个数字恰好被分配到一个叶子中。

刚开始的时候根部有一个棋子。两个玩家轮流移动棋子,每一步都会将这个棋子向他的某一个孩子移动;如果玩家不能再移动棋子了,那么游戏结束。游戏的结果就是棋子所在叶子上面的数字。游戏的先手想要这个数字最大化,而后手想要这个数字最小化。

山巴布里想要给这些叶子分配数字使得最终结果最大,而马族塔想要给这些叶子分配数字使得最终结果最小。那么当山巴布里来分配数字的时候游戏结果会是多少?马族塔分配的时候又是多少呢?山马布里和马族塔并不参加游戏,而是另外两个非常聪明的人来参加游戏。

题解

一号管理员想让最后的数尽量大,这正好符合一号选手的思路,而与二号选手相违背,而且这一次该一号选手选还是该二号选手选只与深度有关。因此设$f_i$表示当一号选手选时,$f_i$表示在$i$的子树内,最少有几个数比最终结果大,$f[u]= min(f[v])$,这样,当他进入$v$这个子树中时,管理员可以把$u$子树内的前$v$大都放在$v$子树中,一号选手的最终答案就是$u$子树的前$v$大;当二号选手选时,$f_i$表示在$i$的子树中,最多有几个数比最终结果小,$f_u=\sum f_v$,这样,二号选手在知道$u$ 子树中的数字分布情况下尽量往小走。转移方程:($v$为$u$的孩子)

  • 该一号选手选时: $f_u = min(f_u,f_v)$
  • 该二号选手选时: $f_u = \sum f_v$

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; 
const int N=200010, INF=1000000000;
int n, mi, all;
int head[N], f[N], g[N], chu[N];
struct Edge{
    int to,next;
}e[N<<1];
inline void add(int u,int v){
    e[++mi] = (Edge){v,head[u]};
    head[u] = mi;
}
void dfs1(int u,int fa,int dep){
    for(int p=head[u]; p; p=e[p].next) if(e[p].to!=fa) dfs1(e[p].to, u, dep+1);
    if(!chu[u]) all++, f[u]=g[u]=1;
    else{
        if(dep&1){
            f[u] = INF;
            for(int p=head[u]; p; p=e[p].next) if(e[p].to!=fa){
                f[u] = min(f[u], f[e[p].to]);
                g[u] += g[e[p].to];
            }
        }else{
            g[u] = INF;
            for(int p=head[u]; p; p=e[p].next) if(e[p].to!=fa){
                f[u] += f[e[p].to];
                g[u] = min(g[u], g[e[p].to]);
            }
        }
    }
    
}
 
int main(){
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    scanf("%d",&n);
    for(int i=1, u, v; i<n; ++i){
        scanf("%d%d",&u,&v);
        add(u,v); add(v,u);
        chu[u]++;
    }
    dfs1(1,0,1);
    printf("%d %d\n",all-f[1]+1, g[1]);
}
Last modification:July 18th, 2019 at 05:04 pm
如果您觉得我的文章有用,请赏一颗糖糖。

Leave a Comment