据5.3号截止,已经达到1180题.(还剩2天)

因为难以选择,所以,我决定,以竞赛的形式,决出归属权.

竞选名单:Joker,Will.Pam,阿兹卡班的小天狼星,徐佳元,铜龟

竞选规则:谁先在5.7之前做出 #12806.比赛 这题,谁得到小号.(如都没做出,那算了不给)

温馨提示,如果我在5.5晚上24:00之前还未达到1200题,题目改成做#3308.「NOI2011」道路修建,是降了难度的,不信洛谷去看

@zuotingting

啥时候举办模拟赛,5.13号就正式比赛了

挑战一下,不成功随机评论区挑选一名幸运儿送账号

Test 1,2,3,4,7,8,10全是“NO SOLUTION”

建议将0<K<=80改到0<K<=500

且如果存在不大于50000的解,则输出这个N,并输出相应的K个因子;否则输出NO SOLUTION.

首先声明,wuziyue第1,我第2,昊然第3.

先看wuziyue加的,现2087,原2001,加了86,没有错.

我只加了2,不信看前后对比(报名显示2024,实际2077),而且rating还是按原来2024加的.

再看昊然,原比我多了69rating,他第三,却比我第2加的还多,应该是14.

我不太注重rating，只请给个解释就可以了,另外:

我如果有时间能不能写月赛题解(第三题写了2小时,让本不善图论的我雪上加霜,暴力得出的结论不搞题解岂不是白搭)(算了算了,有人发过了)？

rating要不保了呀,今天才加的一点,

何时才能回到2198的巅峰！

#3681.「SDOI2010」猪国杀 大模拟

共计代码约100多行

有兴趣的自己去做.

另外提一嘴:猪都会玩三国杀了吗,NOIP竟然出现了"喵了个喵"(羊了个羊)

望老师批准

#123276 #12850. 互质 xushuoxin 100 344ms 10108kb C++ 855b 2023-04-05 17:48:26打卡

鏖战三天三夜,一个人的提交记录就有四页,用了无数解法……

今天,终于拿下了.

欢迎挑战！[抱拳] [抱拳]

A题 最接近 题目链接

很简单,送分题,只需注意两点:

1.开longlong(十年OI一场空,不开longlong见祖宗)

2.当这个2的幂次方大于n时,最后输出要除2.(见程序)

#include<iostream>
using namespace std;
long long s=1,n;
int main(){
    cin>>n;
    while(s<=n)
        s*=2;
    cout<<s/2;
    return 0;
}

B题 序列 题目链接

有点难度,要用高精度,不过思路一定要对:

先扪心自问:自己是不是一个数一个数加的？

如果是,哈哈,20分你拿走,超时.

如果你想得高分(除了最后三个数据有点大),

下面的思路你听好:

首先,算出这个不重复序列(也就是他一开始给你的那个)里的数的总和(记作成变量S).

我们知道这个总和是由N个数组成的,可以看成一个整体.

最多有多少个S加起来不超过题目给出的X呢?

X/S(C++对于整数的除法向下取整).

数的个数就是N*(X/S).

那么剩余部分就是X%S.(X%S记作变量P,一个数一个数加吧,循环不会超过N-1次).

还有一点:(Atk是总和大于P的数的个数)

$Atk$

$∑Ai=P$时

$i=1$

要再加上一个数(Atk++),一定要超过X,否则会少10分.

最后输出N*(X/S)+Atk.

如果你用了如上思路,70分.(程序与思路略有不同)

#include<iostream>
using namespace std;
unsigned long long a[100000],s,sum,x,n,k,l,t;
int main(){
    cin>>n;
    for(int i=0;i<n;s+=a[i],i++)
        cin>>a[i];
    cin>>x;
    k+=n*(x/s);
    t=x%s;
    while(sum<=t){
        sum+=a[l%n];
        l++,k++;
    }
    cout<<k;
    return 0;
}

想满分,很简单,有四种选择:

1.当个大冤种写高精度.

2.选择更好的思路(这也许不是最优解).

3.用科技(__int128,慎用).

4.用python(无视高精度,但在正式比赛中勿用,谨记慎用).

所以我选择了python(比赛时用的高精度,但思路错了).

有三条原因:

1.防止抄袭.

2.证明下我也是会python的.

3.因为懒.

n=int(input())
a=input().split()
x=int(input())
s=0
k=0
ans=0
for i in range(0,n):
    s+=(int)(a[i]);
k=(int)(n*(int)(x/s))
p=x%s
l=0
while(ans<=p):
    ans+=(int)(a[l%n])
    k+=1
    l+=1;
print(k)

这是给你们看看的,别抄啊,老老实实用高精度去吧.

嘿嘿嘿才怪,我怎么会给出python的满分程序呢?

AC程序如下:

#include<iostream>
using namespace std;
__int128 a[100000],s,sum,x,n,k,l,t;
__int128 in(){
    string str;__int128 ans=0,mul=1;
    cin>>str;
    for(int i=str.length()-1;i>=0;i--)
        ans+=(int)(str[i]-'0')*mul,mul*=10;
    return ans;
}
void out(__int128 p){
    if(p==0)
        return;
    out(p/10);
    cout<<(char)(p%10+48);
}
int main(){
    n=in();
    for(int i=0;i<n;s+=a[i],i++)
        a[i]=in();
    x=in();
    k+=n*(x/s);
    t=x%s;
    while(sum<=t){
        sum+=a[l%n];
        l++,k++;
    }
    out(k);
    return 0;
}

C题 互质 题目链接

前话:本来不想写的,毕竟三天的努力成果……

题意很简单,这里直接略过.

先展示一篇30分程序(基本都是你们写的那种)

#include<bits/stdc++.h>
using namespace std;
int n,m,s,ans,flag,p[100005],a[100005],f[100005];
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++){
        flag=0;
        for(int j=0;j<n;j++)
            if(__gcd(i,a[j])!=1){
                flag=1;
                break;    
            }    
        if(!flag)
            p[ans++]=i;
    }
    cout<<ans<<endl;
    for(int i=0;i<ans;i++)
        printf("%d\n",p[i]);
    return 0;
}

分析:时间复杂度为O(nm),超时.

优化一下:发现可以分质数,合数两种情况考虑.

能与质数互质的,只有1或这个质数的倍数(程序中没有特判1,请自行加上).

只要合数的质因数都与数列中所有数互质,那么这个合数也和数列中的所有数互质.

普通的判断素数会超时,这里推荐埃氏筛.

剩下的部分就没什么好说的了,有问题来问我.

#include<bits/stdc++.h>
using namespace std;
int n,m,s,mx,q,mi=INT_MAX,ans,flag,t[1000005],f[1000005],p[1000005],a[1000005],l[1000005];
void ass(){
    memset(f,1,sizeof(f));
    for(int i=2;i<=m;i++)
        if(f[i])
            for(int j=2*i;j<=m;j+=i)
                f[j]=0;
    return;
}
bool check(int x){
    for(int i=0;i<q;i++)
        if(x%l[i]==0)
            return false;
    return true;
}
int main(){
    cin>>n>>m;
    ass();
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        t[a[i]]=1,mx=max(a[i],mx),mi=min(mi,a[i]);
    }
    for(int i=1;i<=m;i++){
        flag=0;
        if(i==1){
            p[ans++]=1;
            continue;
        }    
        if(!f[i]){
            if(!check(i))
                flag=1;
        }
        else
            for(int j=mi/i;j<=mx/i;j++)
                if(t[i*j]==1)
                    flag=1,j=mx;
        if(!flag)
            p[ans++]=i;
        else if(f[i])
            l[q++]=i;
    }
    cout<<ans<<endl;
    for(int i=0;i<ans;i++)
        printf("%d\n",p[i]);
    return 0;
}

题外话:

请老师严抓抄袭,程序仅供参考,请选手们杜绝复制题解的行为,讲究下学术诚信.

尤其提醒@Joker等人:(特别是在我讲了以后还是抄袭)

#123842 #12850. 互质 Joker 100 331ms 10108kb C++ 1.1kb 2023-04-08 11:34:34

(没有冤枉,老师给我看过他的提交了,是抄袭的,之前应该也有此行为,但是没有证据).

虽然我没有能力像老师那样发程序图片,但请大家自觉一点.

如果再有此行为,以后题解一概不附代码

再次提醒:珍惜别人的劳动成果！！！杜绝抄袭！！！