标签：le int sum 石子 2024 Shintaro 寒假 100 集训

2024初三年前集训测试3

ps：也不知道我为什么没写测试1，2的题解

T1 夕景昨日 $100pts$

题目描述

$Shintaro$ 制作了 $n$ 个开关，每个开关的状态可被设置为 $+$ 或 $-$。

现在你有一个数列 $ A=(a_1,a_2, \dots,a_n ) $ ，和一个初始值为 $0$ 的变量 $v$ 。你可以自由地操纵开关，当第 $i$ 个开关被设置为 $+$ 状态时，会加上 $a_i$ ，被设置为 $-$ 状态时，会减去 $a_i$。

请你判断是否有两种及以上不同的方式操纵开关，使得最后得到的 $v$值相等。

输入格式

第一行一个数 $n$ ，表示开关的个数

第二行 $n$ 个数，第 $i$ 个数表示 $a_i$

输出格式

如果有请输出 $Yes$，否则输出 $No$ 。

$ 20 $ $\%$ $: n \le 10 $

$ 100 $ $\%$ $: 1 \le n \le 100000,0 \le a_i \le 500000 $

赛时思路

一看到题目，先懵了一会，看了数据范围，人都快傻了，想过难但没想到 $T1$都不会。然后想起了 $2023 CSP-S$，我 $T1$做了2h，然后A了。上午两个小时又在推 $T1$，还没想到可行解，做得挺难受的。最后打的暴搜+特判+面向数据点分治。

若 $ A $中含有 $0$ ，则有解。
若 $ A $中含有相等的数，则有解。
当 $ n \le 30 $，暴搜。
否则，直接输出 $Yes$。

结果A了？挺难崩

正解

首先，当 $ n \ge 20 $ 时，一定有解

证明

我们假设数列 $vis$ 内的元素无解，我们将一元素加入原数列时，若数列仍无解，当且权当 $vis$内每一个元素与 $v$之和，仍不重复，并将所有加和放入原数列，循环操作 $k$ ，每次元素个数变为原来的 $2$倍。

观察数据范围，$ \sum_{i=1}^na_i \le 5e10 $，所以 $ 2^k \le 5e10 $。 $k$ 不妨取 $20$。

当 $ n \le 20 $，打暴力；否则，直接输出 $Yes$。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e7;
int n,a[N];
bool b[N<<2],flag;
void dfs(int x,int y)
{
    if(flag)return ;
    if(x==n){
        if(b[y+a[x]+N]){
            flag=1;
        }
        if(b[y-a[x]+N]){
            flag=1;
        }
        b[y+a[x]+N]=1;
        b[y-a[x]+N]=1;
        return;
    }
    dfs(x+1,y+a[x]);
    dfs(x+1,y-a[x]);
}
signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=n;i++){
        if(a[i]==0){
            printf("Yes");
            return 0;
        }
        if(b[a[i]]){
            printf("Yes");
            return 0;
        }
        b[a[i]+N]=1;
        b[-a[i]+N]=1;
    }
    if(n<=20){
        memset(b,0,sizeof(b));
        dfs(1,0);
        if(flag)printf("Yes");
        else printf("No");
    }
    else{
        printf("Yes");
    }
}

总结

应该注意值域范围，好像数据很大，但其中有效的很少。（感觉像数论Longge的问题）

数据有点水，只输出 $Yes$得 $90 pts$。

透明答案 $30pts$

题目描述

$Ayano$ 和 $Bob$ 在玩简单的取石子游戏。最初有 $n$堆石子，每堆有 $2$ 块。

$ Ayano $ 和 $ Bob $ 轮流取石子（从 $ Ayano $ 开始）。每一次取石子时当前玩家可以任选一堆，如果还剩下 $k$ 块石子，则可以从这堆中取出 $1$ 到 $k$ 之间的任意数量的石子。

此外，每 $3$ 回合他们会添加一堆石子（含 $2$ 块石子）。换句话说，在第 $t$ 次操作（两个人操作的总次数）之后，如果 $t$ 可以被 $3$ 整除，则添加一堆 $2$ 块石子的石子堆。

（即使在第 $t$ 次操作中取完了所有石子，如果 $t$ 可被 $3$ 整除，也会添加新石子堆并继续游戏。）

双方都采取最优策略，无法操作的玩家输掉游戏。请你判断哪个玩家获胜。

数据范围

$ 30 $ $\%$ $: n\le 10 $

$ 100 $ $\%$ $ n \le 1000 $

赛时思路

一眼博弈论，然后......读完题觉得不可做，就先跳了，$T4$做完再回来看看，结果只有两种情况，那我随意输出一个一定有分。那......输出什么呢？许多游戏都有先手必胜的性质，但并不保证多得分，写 $rand$ 也比较悬。从地上捡了个小塑料片，随机吧，正面A，反面B。最后输出 $Bob$ （期末考试一道历史题不会做就抛橡皮，正面B，反面D，结果它立起来了？~~那题答案是C~~

正解

博弈论，推了半个下午还是不会，学校题解给的很抽象：

爆搜找规律，发现 $ n \equiv 2 \ (\mod \ 3) $ 时， $ Bob $赢，否则 $ Ayano $ 赢。由于是普及题，所以放 $dfs$ 过。

还是不会，先放下了。

Code

#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
    cin>>n;
    if(n%3==2){
        printf("Bob");
    }
    else {
        printf("Ayano");
    }
}

界外科学 $100pts$

题目描述

$ENE$ 是一位电脑少女，这天她在帮 $Shintaro$ 网上购物。网店一共有 $n$ 件物品，第 $i$ 件物品有 $a_i$ 的价格，并且购买这件物品会给 $Shintaro$ 带来 $b_i$ 的满足度，不同的物品获得的满足度会累加。

$Shintaro$ 最多只能支付 $m$ 元。由于他资金有限， $ENE$ 黑入了网店的支付系统。在她操作之后，总价格的计算方式是将所有物品的价格给 $xor$ （异或运算）起来。

如 $Shintaro$ 现在买了价格为 $1$ 、$2$ 、$4$ 、$7$ 的四件物品，总价格为 $ 1 \bigoplus 2 \bigoplus 4 \bigoplus 7=0 $ 。

$Shintaro$ 现在想知道在足够支付所买的物品的前提下，他最多能获得多少满足度。

数据范围

$ 30 $ $\%$ $ :n \le 5 $

$ 50 $ $\%$ $ :n \le 20 $

另外 $ 20 $ $\%$ $ :1 \le m,a_i \le 100 $

$ 100 $ $\%$ $ :1 \le n \le 36 , 1 \le m,a_i, \left| b_i \right| \le 10^9 $

赛时思路

$ n \le 36 $ ，为暴搜准备的嘛。但复杂度 $ O(2^n) $ ，最坏情况下会 $TLE$ ，所以写了一个剪枝：

用sum[i] 记录以i为起点，数组b的后缀和，当当前价值加后续所有价值仍小于现有的 ans ，那就不需要再搜下去了。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=50;
struct node{
    int a,b;
}s[N];
int n,m,ans,sum[N];
inline int Max(int x,int y)
{
    if(x>=y)return x;
    else return y;
}
void dfs(int x,int y,int z)
{
    if(x==n){
        if((y^s[x].a)<=m){
            ans=Max(ans,z+s[x].b);
        }
        if(y<=m){
            ans=Max(ans,z);
        }
        return ;
    }
    if(z+sum[x]<=ans)return;
    dfs(x+1,(y^s[x].a),z+s[x].b);
    dfs(x+1,y,z);
}
bool cmp(node x,node y)
{
    return x.b>y.b;
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&s[i].a);
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",&s[i].b);
    }
    sort(s+1,s+n+1,cmp);
    for(int i=n;i>=1;i--){
        if(s[i].b>=0)
        sum[i]=sum[i+1]+s[i].b;
        else sum[i]=sum[i+1];
    }
    dfs(1,0,0);
    printf("%lld",ans);
}

闲话：数据过水，虽然赛时AC，但后来被 Vsinger_LuoTianYi $ hack $了，机房每份代码都被 $ hack $了一遍。另外把价值都加起来好像就可以AC。

原代码的剪枝不能处理价值为负数的情况，调整一下sum的定义，只使其记录正数。

注意一个点，位运算一定要加括号。

整个集训最难崩的一道题

正解

折半搜索，可将复杂度降到 $O(2^{\frac{n+4}{2}}+2^n)$ ，挺神奇的，可以学一下，但这题我没打出来，因为异或运算不像普通的加减法，有一些特殊的性质，处理出异或值和权值，再用 $01trie$ 求最大值。

回忆补时 $30pts$

题目描述

$Shintaro$ 有 $n$ 条直线，第 $i$ 条直线 $l_i$ 可以被描述为 $k_ix+b_i$。

这天 $Ayano$ 和 $Shintaro$ 在一起玩游戏。每局游戏 $Ayano$ 会给出一个整数 $x$ ，然后让 $Shintaro$ 选两条不同的直线 $l_i,l_j$ ，得到 $ y=k_j \times(k_i \times x +b_i)+b_j $ 作为他的得分。

作为游戏中级高手， $Shintaro$ 觉得得分肯定是越大越好，然而他不知道自己的得分是否达到了最大。所以对于每局游戏里 $Ayano$ 给出的整数 $x$ ，请你告诉 $Shintaro$ 可能得分的最大值。

数据范围

$ 30 $ $\%$ $ :n,q \le 100 $

$ 60 $ $\%$ $ :n,q \le 3000 $

$ 100 $ $\%$ $ :2 \le n,q \le 100000, \left| x_i \right|,\left| k_i \right| \le 10^6, \left|b_i \right| \le 10^{12} $

赛时思路

能感觉到题目很难，但是得分比较容易，从前做过两道与直线解析式的题目，做得还算轻松。

先考虑 $ n \le 100 $ ，很容易想到 $ O(n^2q) $ 的做法，每次查询枚举直线 $i$ ，再枚举直线 $j$ ，求最大值即可。可得 $30pts$ 。

$ O(n\ logn\ q) $的做法，我们可以知道直线是具有单调性的：

当 $ k \ge 0 $ 时， $y$ 随 $x$ 增大而增大，我们只需要知道最大值

当 $ k<0 $ 时， $y$ 随 $x$ 增大而减小，我们只需要知道最小值

注意特判 $i=j$ 即所选同一条直线的情况（你猜为什么 $ n \ge 2 $ ）

预估 $60pts$ ，但赛时结果大小计算有误，开了 $ __int 128 $ ，由于速度比 $long long$ 慢，挂了 $30pts$ 。据 $ The_Shadow_Dragon $ 说，可以优化一下， $ O(n) $ 求出最大值，次大值,最小值，次小值。总复杂度 $ O(nq) $ 。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+100;
int n,q,x,k[N],b[N],z[N],ans;
struct node{
    int y,id;
}num[N];
inline int read()
{
    int f=1,w=0;
    char c=getchar();
    while(c>'9'||c<'0'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        w=w*10+(c-'0');
        c=getchar();
    }
    return w*f;
}
void write(int x)
{
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
void qwrite(int x)
{
    write(x);
    puts("");
}
bool cmp(node a,node b)
{
    return a.y<b.y;
}
inline int Max(int a,int b)
{
    if(a>b)return a;
    else return b;
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++){
        k[i]=read();
        b[i]=read();
    }
    q=read();
    while(q--){
        x=read();
        ans=-1e13;
        for(int i=1;i<=n;i++){
            num[i].y=k[i]*x+b[i];
            num[i].id=i;
        }
        sort(num+1,num+n+1,cmp);
        for(int i=1;i<=n;i++){
            if(k[i]>0){
                if(num[n].id==i)z[i]=num[n-1].y*k[i]+b[i];
                else z[i]=num[n].y*k[i]+b[i];
            }
            else {
                if(num[1].id==i)z[i]=num[2].y*k[i]+b[i];
                else z[i]=num[1].y*k[i]+b[i];
            }
            ans=Max(ans,z[i]);
        }
        qwrite(ans);
    }
}

感觉寒假年前集训过得很快，这就要结束了，做的题目不是很多，主要是一些较基础的字符串，数论 $exgcd 和欧拉函数$ 写了写，有的题目是有难度的，还有题目没A，打算过年几天写。剩下的时间在打模拟赛，调题，前两场打得稀烂，挂分不少，但给人一些启发，也触碰到一些盲点。现在比较关心过年不会要补文化课吧。

标签：le,int,sum,石子,2024,Shintaro,寒假,100,集训
From： https://www.cnblogs.com/abnormal123/p/18008872

2024初三寒假年前集训测试3

2024初三年前集训测试3

T1 夕景昨日 \(100pts\)

题目描述

输入格式

输出格式

赛时思路

正解

证明

Code

总结

透明答案 \(30pts\)

题目描述

数据范围

赛时思路

正解

Code

界外科学 \(100pts\)

题目描述

数据范围

赛时思路

Code

正解

回忆补时 \(30pts\)

题目描述

数据范围

赛时思路

Code

相关文章

赞助商

阅读排行