Sweet Round 1题解

感谢各位参赛者，所有的题解如下：

T1 syx的奖励

这题明显是签到题了吧，随便猜猜结论就A掉了

先说怎么做吧，把所有的可走的数gcd起来，然后再与n求gcd

如果为1，则输出n，若不为1，则输出-1

证明如下：

∵gcd(所有可行的数，n）=1,

∴在可行的步数中必有一点y，使得gcd(x,y)<x（x!=1）

∴有x,y等价于又了gcd(x,y)

然后就数学归纳一下，就得出了结论了鸭

注意！！！

当n==1&&m==1时，就一步都不能走了

所以输出 -1

代码如下：

#include<bits/stdc++.h>

using namespace std;

#define int long long

inline int read() {

    int x(),neg();char ch(getchar());

    while(!isdigit(ch)) {

        if (ch=='-') neg=-;

        ch=getchar();

    }

    while(isdigit(ch)) {

        x=(x<<)+(x<<)+(ch^);

        ch=getchar();

    }

    return x*neg;

}

int n,k;

int mp[];

int baozi,T;

signed main() {

//    freopen("baozi.in","r",stdin);

//    freopen("baozi.out","w",stdout);

    T=read();

    for (int t=;t<=T;++t) {

        memset(mp,,sizeof(mp));

        n=read(),k=read();

        baozi=n;

        for (int i=;i<=k;++i) {

            int x;

            x=read();

            mp[x]=;

        }

        for (int i=;i<=n;++i) {

            if (!mp[i]) {

                baozi=__gcd(baozi,i);

            }

        }

        if (baozi!=||n==&&k==) {

            puts("-1");

            continue;

        }

        printf("%lld\n",n);

    }

    return ;

}

T2 Ethan and sets
思路：
挺明显的Two-pointers吧qwq

这题应该还是挺简单的，模拟即可（Two-pointers 难不到哪里去）

直接上代码（详细注释）

#include<bits/stdc++.h>

using namespace std;

#define int long long

inline int read() {

    int x(),neg();char ch(getchar());

    while(!isdigit(ch)) {

        if (ch=='-') neg=-;

        ch=getchar();

    }

    while(isdigit(ch)) {

        x=(x<<)+(x<<)+(ch^);

        ch=getchar();

    }

    return x*neg;

}

int n,m,g,s[],cnt[],c[][],num[],p[];

bool found=;

int ansb=,anss,ansl,ansr;

signed main() {

    n=read(),m=read(),g=read();

    for(int i=;i<=g;i++){

        int x(read());

        p[x]=;//标记为喜欢

    }

    for(int i=;i<=n;i++){

        scanf("%lld%lld",&s[i],&num[i]);

        for(int j=;j<=num[i];j++)

            scanf("%lld",&c[i][j]);

    }

    int l=,r=,sum=,sumb=;//当前区间为 [l,r) , sum = [l,r) 的魔力值之和 , sumb = [l,r) 中不喜欢的数的个数

    while(l<=n) {

        while(r<=n) {

            bool flag=,check=;//flag: 是否有不喜欢的数 (1=NO,0=YES) , check: 是否全部包含了所有 Ethan 喜欢的数

            for(int i=;i<=num[r];++i)

                if(!p[c[r][i]])

                    flag=;

            for(int i=;i<=m;i++)

                if(p[i]&&!cnt[i])//喜欢但不包含的数

                    check=;

            if(check&&!flag)break;//如果包含了所有喜欢的数 , 且 [l,r-1] 比 [l,r] " 不喜欢的数的个数 " 少 ( 集合 r 有不喜欢的数 ) , 那就选 [l,r-1] , 退出

            for(int i=;i<=num[r];++i){//右端点往右移 , 加上集合 r 的所有属性

                if(!p[c[r][i]]) ++sumb;

                ++cnt[c[r][i]];

            }

            sum+=s[r];

            ++r;//右端点 ++

        }

        bool check=;//这边还要再判断一下是否有全部喜欢的数 , 可能是 r>n 从上一个 whlie 循环退出来的

        for(int i=;i<=m;++i)

            if(p[i]&&!cnt[i])

                check=;

        if(check) {

            found=;//标记一下找到了

            if(ansb>sumb||sumb==ansb&&anss<sum)//如果满足更新条件

                ansb=sumb,anss=sum,ansl=l,ansr=r-;//更新

        }

        for(int i=;i<=num[l];++i){//左端点往右移 , 把集合 l 的所有属性减掉 ( 可以和上面的右端点往右移对比一下 )

            cnt[c[l][i]]--;

            if(!p[c[l][i]])sumb--;

        }

        sum-=s[l];

        ++l;//左端点 ++

    }

    if(!found) puts("-1");//没找到输出 -1

    else printf("%lld %lld\n",ansl,ansr);

    return ;

}

T3 syx与他的邪恶序列 (easy version)

这题就属于随便做的题目了吧。。。

但是如果你用T4的方法做可能还拿不到几分（看看时间和空间限制）

直接考虑贪心

在当前的点是要删除的数(=x)的时候，考虑它离最近的点需要多少步，离最近可以删的点为2^k且这个点为离它前面最近的点，而它前面删掉的点有cur个，所以每个数需要(当前位置减2^k-cur)次才能到达，所以得出程序：

#include<bits/stdc++.h>

using namespace std;

inline int read() {

    int x(),neg();char ch(getchar());

    while(!isdigit(ch)) {

        if (ch=='-') neg=-;

        ch=getchar();

    }

    while(isdigit(ch)) {

        x=(x<<)+(x<<)+(ch^);

        ch=getchar();

    }

    return x*neg;

}

int n,k,x,cnt,cur;

int main() {

    int ans=;

    n=read(),k=read();

    for (int i=;i<=n;++i) {

        x=read();

        if (x==k) {

            int t=i-(<<((int)log2(i)));

            if (t>cur) {

                ans+=t-cur;

                cur=t;

            }

            cnt++;

            cur++;

        }

    }

    printf("%d\n",ans+cnt);

    return ;

}

T4 syx与他的邪恶序列 (hard version)

前言:

其实这题出题的时候也是我和csy在操场上聊天，然后就突然有了灵感，去出这一题（所以非常水啊！！！）

题解：

其实这个n≤3∗10⁶我觉得提示已经很明显了，肯定要不是O(1),要不就是O(n)，要不是O(nlogn)，但是想想O(1)和O(n)，好像又很不可做的亚子，于是就奔着O(nlogn)的方向去了吧

首先，大家可以思考一下，如果有位置在2^k的数，那么一定会弹掉。但是弹哪个呢？？？

肯定是弹最后一个啊！因为弹前面的一定会影响后面的，会使后面的不再在2^k这个位置上，所以思路是很明显的，然后看怎么实现

对于实现，可能大家第一步想到的是O(n²)的算法，就是先找有没有目标要删除的数在2^k这个位置上，如果有，记录最后一个，然后把那个删掉（删掉操作可能就把数组忘前移吧），再++cnt，如果没有，就把第一个数删掉（因为当前的第一个数也是2^k，所以没有的话，第一个数肯定不是目标要删除的数），然后把所有的数往前移，知道把所有的目标要删的数都搞完为止

恭喜你，获得了35分的高分！！！

#include<bits/stdc++.h>

using namespace std;

#define int long long

inline int read() {

    int x(),neg();char ch(getchar());

    while(!isdigit(ch)) {

        if (ch=='-') neg=-;

        ch=getchar();

    }

    while(isdigit(ch)) {

        x=(x<<)+(x<<)+(ch^);

        ch=getchar();

    }

    return x*neg;

}

int pos[];

int cnt,now[],pw[],used[],ok[],a[],ans[],tot;

signed main() {

    int n1=read(),k=read();

    pw[]=;

    used[]=;

    for (int i=;i<;++i) {

        pw[i]=pw[i-]*;

        used[pw[i]]=;

    }

    for (register int i=;i<=n1;i++) {

        int t=read();

        if (t==k) {

            register int k=;

            pos[++cnt]=i;

            now[cnt]=i;

        }

    }

    int cntt=cnt;

    int start=;

    while(cntt) {

        int flag=;

        for (int i=cnt;i>=;--i) {

            if (used[pos[i]]&&!ok[now[i]]) {

                ans[++tot]=now[i];

                cntt--;

                flag=;

                ok[now[i]]=;

                for (int j=i+;j<=cnt;++j) --pos[j];

                break;

            }

        }

        if (flag) continue;

        while(true) {

            ++start;

            if (!ok[start]) {

                ok[start]=;

                break;

            }

        }

        for (int j=cnt;j>=;--j) {

            if (pos[j]<start) break;

            --pos[j];

        }

        ans[++tot]=start;

    }

    printf("%lld\n",tot);

    for (int i=;i<=tot;++i) {

        printf("%lld ",ans[i]);

    }

    return ;

}

/*

5 2

2 2 2 2 2

3 3

1 1 3

*/

然后再看看复杂度

于是就发现非常不行，就开始往数据结构上想，要维护最后一个可以删的数咋办啊？
然后就考虑用线段树记录每个数离它要删除的地方的位置，如果这个线段的区间最小值为0，那么就说明可以删，就先看它的右节点为不为0，如果为0，就直接往右节点跑，如果不为0，那么就说明应该往左节点跑，找到最右边

然后就发现你已经把这题想好了，然后就花个5min写代码吧

Code:

#include<bits/stdc++.h>

using namespace std;

inline int read() {

    int x(),neg();char ch(getchar());

    while(!isdigit(ch)) {

        if (ch=='-') neg=-;

        ch=getchar();

    }

    while(isdigit(ch)) {

        x=(x<<)+(x<<)+(ch^);

        ch=getchar();

    }

    return x*neg;

}

struct node{

    int left,right,minv,lazy;

}tree[];

int n1,k,a[],tot,noww,num[],ans2[],now[],ans;

inline void build(register int cnt,register int l,register int r) {

    tree[cnt].left=l;tree[cnt].right=r;

    if (l==r) {

        tree[cnt].minv=a[l];

    }

    else {

        build(cnt<<,l,l+r>>);

        build(cnt<<|,(l+r>>)+,r);

        tree[cnt].minv=min(tree[cnt*].minv,tree[cnt*+].minv);

    }

}

inline int find(register int p) {

    register int t;

    if ((tree[p].minv-tree[p].lazy)!=){

        register int total=tree[p].minv-tree[p].lazy;

        for (register int i=;i<=total;++i) {

            ++noww;

            while(num[noww]==k) {

                ++noww;

            }

            ans2[++tot]=noww;

        }

        ans+=tree[p].minv-tree[p].lazy;

        tree[p].lazy=tree[p].minv;

    }

    if (tree[p].left==tree[p].right){

        tree[p].minv=;

        return tree[p].left;

    }

    else{

        tree[p<<].lazy+=tree[p].lazy;

        tree[p<<|].lazy+=tree[p].lazy;

        tree[p].lazy=;

        if (tree[p<<|].minv-tree[p+p+].lazy==) t=find(p*+);

        else t=find(p*);

        tree[p].minv=min(tree[p+p].minv-tree[p+p].lazy,tree[p+p+].minv-tree[p+p+].lazy);

        return t;

    }

}

inline void add(register int p,register int l,register int r) {

    if (l>r) return ;

    if (l<=tree[p].left&&tree[p].right<=r){

        tree[p].lazy++;

    }

    else{

        tree[p*].lazy+=tree[p].lazy;

        tree[p*+].lazy+=tree[p].lazy;

        tree[p].lazy=;

        if (l<=(tree[p].left+tree[p].right)/) add(p*,l,r);

        if ((tree[p].left+tree[p].right)/+<=r) add(p*+,l,r);

        tree[p].minv=min(tree[p*].minv-tree[p*].lazy,tree[p*+].minv-tree[p*+].lazy);

    }

    return ;

}

int pw[];

signed main(){

//  freopen("link.in","r",stdin);

//  freopen("line.out","w",stdout);

    n1=read(),k=read();

    register int t,cnt=;

    pw[]=;

    for (int i=;i<;++i) {

        pw[i]=pw[i-]*;

    }

    for (register int i=;i<=n1;i++) {

        register int t;

        t=read();

        num[i]=t;

        if (t==k) {

            register int k=;

            for (register int j=;j<=;++j) {

                if (pw[j]>i) {

                    k=i-pw[j-];

                    break;

                }

            }

            a[++cnt]=k;

            now[cnt]=i;

        }

    }

    if (cnt==) {

        puts("");

        return ;

    }

    build(,,cnt);

    for (register int i=;i<=cnt;i++) {

        t=find();

        ++ans;

        ans2[++tot]=now[t];

        add(,t+,cnt);

    }

    printf("%lld\n",ans);

    for (register int i=;i<=tot;++i) {

        printf("%lld ",ans2[i]);

    }

    puts("");

    return ;

}

T5 Alex does homework

题解：

我也不知道这个部分分给的有什么用
Sol 1 : 5-15 pts
爆搜，期望得分 5-15% （要看你怎么搜）

Sol 2 : 75-100 pts

注意空间限制！！！

一看题就应该知道时间 O(nk)，空间 O(k)

如果没有 时间的限制，那么这道题目就是 完全背包

但有了时间怎么办 qwq?

不慌，将所有种类的作业按时间从大到小排序

每次一种作业去更新 dp 数组

再 对于每一个更新 求出最小（精力）花费

最后求出天数不就行了嘛 awa

最后，上代码：

#include<bits/stdc++.h>

using namespace std;

#define int long long

inline int read() {

    int x(),neg();char ch(getchar());

    while(!isdigit(ch)) {

        if (ch=='-') neg=-;

        ch=getchar();

    }

    while(isdigit(ch)) {

        x=(x<<)+(x<<)+(ch^);

        ch=getchar();

    }

    return x*neg;

}

const int N=;

const int INF=;

struct homew{

    int x,w,t,cos;

}k[N];

bool cmp(homew a,homew b){return a.t>b.t;}//将作业按时间大小排序

int x,w,n,dp[N<<];

void init() {

    x=read(),w=read(),n=read();

    for(int i=;i<=n;++i)

        k[i].x=read(),k[i].w=read(),k[i].t=read();//读入

    sort(k+,k+n+,cmp);//sort

    memset(dp,0x3f,sizeof(dp));//dp 赋初值

    dp[]=;

}

inline void DP() {

    for(int i=;i<=n;i++){

        if(k[i].w>=w)//特判一下 w[i]>=w 的情况

            dp[w]=min(dp[w],k[i].x);

        else

            for(int j=k[i].w;j<=w+k[i].w;j++)//完全背包

                dp[j]=min(dp[j],dp[j-k[i].w]+k[i].x);

        k[i].cos=INF;//赋初值

        for(int j=w;j<=(w<<);++j)

            k[i].cos=min(k[i].cos,dp[j]);//找出最小值

    }

}

inline void answer() {

    for(int i=n;i>=;--i) {//时间从小到大遍历

        int cos=k[i].cos*(k[i].t-k[i+].t);//总花费

        if(cos<=x) x-=cos;//有足够的精力

        else {

            printf("%lld %lld",k[i+].t+x/k[i].cos,x%k[i].cos);exit();//否则输出并退出

        }

    }

    printf("%lld %lld\n",k[].t,x);//特判天天能写完作业

}

signed main() {

//    freopen("homework.in","r",stdin);

//    freopen("homework.out","w",stdout);

    init();

    DP();

    answer();

    return ;

}

最后，再次感谢大家参加此次比赛！！！

巴特西

Sweet Round 1题解

最新文章

热门文章