头像

Overnoise

ZTOI


访客:20333

离线:3小时前



看到题目第一眼就可以联想到二进制
代码如下

#include<bits/stdc++.h>
using namespace std;
long long ans[10000];
long long tot,m;
int main() {
    cin>>m;
    for(long long i=1;; i*=2) {
        if(tot+i<m) {
            tot+=i;
            ans[++ans[0]]=i;
        } else {
            ans[++ans[0]]=m-tot;

            //特判
            for(int i=2; i<ans[0]; i++)
                if(ans[i]==ans[ans[0]]) {
                    ans[2]--;
                    ans[ans[0]]++;
                    break;
                }

            break;
        }
    }
    sort(ans+1,ans+ans[0]+1);
    cout<<ans[0]<<"\n";
    for(int i=1; i<=ans[0]; i++)
        cout<<ans[i]<<" ";
    return 0;
}



python3

自带高精和字符处理

print(eval(input()))

c++

毒瘤题,我打了好久!!!

主要包括的高精有
高精加高精
高精乘高精
高精&高精
高精|高精

注意运算顺序(优先级)和字符串处理

运用递归处理括号

/*
by 安排
技术不够,难免会有BUG之处,见谅 
*/
#include<bits/stdc++.h>
#define pass puts("pass")
#define LL long long
using namespace std;
string T;//字符串
int now;//目前搜索到的位置
int len;//字符串长度
struct oppo {
    bool f;//高精正负
    short a[100005];//高精(a[1]是个位)
    int len;//高精位数
    oppo operator*(const oppo x) { //高精*高精
        oppo y;
        memset(y.a,0,sizeof(y.a));
        y.len=len+x.len;
        y.f=f^x.f;//判断符号
        for(int i=1; i<=len; ++i)
            for(int j=1; j<=x.len; ++j) {
                //存入下标 i+j-1
                y.a[i+j-1]+=a[i]*x.a[j];
                if(y.a[i+j-1]>9) {
                    y.a[i+j]+=y.a[i+j-1]/10;
                    y.a[i+j-1]%=10;
                }
            }
        while(!y.a[y.len])
            --y.len;
        return y;
    }
    bool bjabs(oppo a,oppo b) { //比较绝对值
        if(a.len!=b.len) return a.len>b.len;
        for(int i=a.len; i; --i)
            if(a.a[i]!=b.a[i])
                return a.a[i]>b.a[i];
        return 1;//两个相等返回1
    }
    oppo gjj(oppo a,oppo b) {//高精-高精
        oppo y;
        memset(y.a,0,sizeof(y.a));
        int l=max(a.len,b.len);
        y.len=l;
        for(int i=1; i<=l; ++i) {
            while(a.a[i]<b.a[i]) {
                a.a[i]+=10;
                --a.a[i+1];
            }
            y.a[i]=a.a[i]-b.a[i];
        }
        while(!y.a[y.len])
            --y.len;
        return y;
    }
    oppo operator+(const oppo x) {//高精+高精
        if(f^x.f) { //两个符号不一样,当成高精减处理
            if(f) {//分类讨论
                if(bjabs(x,*this)) {
                    oppo y=gjj(x,*this);
                    y.f=0;
                    return y;
                } else {
                    oppo y=gjj(*this,x);
                    y.f=1;
                    return y;
                }
            } else {
                if(bjabs(*this,x)) {
                    oppo y=gjj(*this,x);
                    y.f=0;
                    return y;
                } else {
                    oppo y=gjj(x,*this);
                    y.f=1;
                    return y;
                }
            }
        }
        oppo y;
        memset(y.a,0,sizeof(y.a));
        int l=max(len,x.len);
        y.len=l;
        for(int i=1; i<=l; ++i) { //先计算绝对值
            y.a[i]+=a[i]+x.a[i];
            if(y.a[i]>9) {
                y.a[i]-=10;
                y.a[i+1]+=1;
            }
        }
        if(y.a[y.len+1])
            ++y.len;
        y.f=f;//符号
        return y;
    }
    oppo Divide(oppo x) { //高精除2
        for(int i=x.len; i; --i) {
            x.a[i-1]+=10*(x.a[i]%2);
            x.a[i]/=2;
        }
        if(!x.a[x.len]&&x.len!=0)
            --x.len;
        return x;
    }
    oppo multiply(oppo x) { //高精乘2
        oppo y;
        y.f=0;
        y.len=x.len;
        memset(y.a,0,sizeof(y.a));
        for(int i=1; i<=x.len; i++) {
            y.a[i]+=x.a[i]*2;
            y.a[i+1]+=y.a[i]/10;
            y.a[i]%=10;
        }
        while(y.a[y.len+1])
            ++y.len;
        return y;
    }
    oppo add(oppo x) { //高精加1
        ++x.a[1];
        for(int i=1; i<=x.len&&x.a[i]>9; ++i) {
            x.a[i]-=10;
            ++x.a[i+1];
        }
        if(x.a[x.len+1])
            ++x.len;
        return x;
    }
    oppo operator&(oppo x) { //数据保证为正数
        oppo y;
        memset(y.a,0,sizeof(y.a));
        y.f=0;
        y.len=min(len,x.len);
        stack< short > v;
        while(len&&x.len) {
            v.push((a[1]&1)&&(x.a[1]&1));
            *this=Divide(*this);
            x=Divide(x);
        }
        while(v.size()) {
            y=multiply(y);
            if(v.top())
                y=add(y);
            v.pop();
        }
        y.len=max(y.len,1);
        while(!y.a[y.len]&&y.len!=1)
            --y.len;
        return y;
    }
    oppo operator|(oppo x) { //数据保证为正数
        oppo y;
        memset(y.a,0,sizeof(y.a));
        y.f=0;
        y.len=max(len,x.len);
        stack< short > v;
        while(len||x.len) {
            v.push((a[1]&1)||(x.a[1]&1));
            *this=Divide(*this);
            x=Divide(x);
        }
        while(v.size()) {
            y=multiply(y);
            if(v.top())
                y=add(y);
            v.pop();
        }
        y.len=max(y.len,1);
        return y;
    }
};
void sc(oppo a) { //输出高精
    if(a.f) cout<<"-";
    for(int i=a.len; i; --i)
        cout<<a.a[i];
    puts("");
}
oppo work();
oppo Get() { //获取一个数字
    if(T[now+1]=='(') { //把括号当成数字,直接处理
        ++now;
        oppo x=work();
        return x;
    }
    bool flag=0;
    oppo x;
    memset(x.a,0,sizeof(x.a));
    if(T[now+1]=='-') { //判断负数
        flag=1;
        ++now;
    }
    int v[100005];
    v[0]=0;
    while(T[now+1]>='0'&&T[now+1]<='9') { //循环读入
        v[++v[0]]=T[now+1]-'0';
        now++;
    }
    for(int i=v[0]; i; --i) //存入高精
        x.a[v[0]-i+1]=v[i];
    x.f=flag;//存入符号
    x.len=v[0];//存入位数
    return x;
}
oppo work() {
    vector< oppo > v;
    vector< short > fh;//存第i个前的符号  符号对应(优先级  + > & >| )  1:+  2:&  3:|
    int shu=1;
    v.resize(1);
    fh.resize(1);
    v.push_back(Get());//加入第一个数
    fh.push_back(0);//为了和 v 同步
    while(now+1<=len) { //分类讨论
        if(T[now+1]=='+') {
            ++now;
            oppo x=Get();
            fh.push_back(1);
            v.push_back(x);
        } else if(T[now+1]=='-') {
            ++now;
            oppo x=Get();
            x.f^=1;//改变符号
            fh.push_back(1);//因为改变了符号,所以是加
            v.push_back(x);
        } else if(T[now+1]=='*') {
            ++now;
            oppo x=v.back();
            v.pop_back();
            v.push_back(x*Get());   //*已经被处理,不需要加入fh
        } else if(T[now+1]=='&') {
            ++now;
            v.push_back(Get());
            fh.push_back(2);
        } else if(T[now+1]=='|') {
            ++now;
            v.push_back(Get());
            fh.push_back(3);
        } else if(T[now+1]==')') {
            ++now;
            break;
        }
    }
    vector< oppo > v2;//注意!!!   优先级:+ > & > |
    vector< short > fh2;
    v2.resize(1);
    fh2.resize(1);
    v2.push_back(v[1]);
    fh2.push_back(0);
    for(int i=2; i<=v.size()-1; ++i) {//计算 +
        if(fh[i]==1) { //+
            oppo x=v2.back();
            v2.pop_back();
            v2.push_back(x+v[i]);
        } else if(fh[i]==2) { //&
            v2.push_back(v[i]);
            fh2.push_back(2);
        } else if(fh[i]==3) { //|
            v2.push_back(v[i]);
            fh2.push_back(3);
        }
    }
    v.resize(1);
    v.push_back(v2[1]);
    for(int i=2; i<=v2.size()-1; ++i) { //计算 &
        if(fh2[i]==2) {
            oppo x=v.back();
            v.pop_back();
            v.push_back(x&v2[i]);
        } else if(fh2[i]==3) {
            v.push_back(v2[i]);
        }
    }
    for(int i=2; i<=v.size()-1; ++i) //计算 |
        v[1]=v[1]|v[i];
    return v[1];
}
int main() {
    cin>>T;
    len=T.length();
    T=" "+T;
    sc(work());
    return 0;
}



包含下面库(python3)
文件夹创建 os库
html分析 beautfulsoup库
时间控制 time库
多线程 threading库
正则表达式 re库
网页抓取 requests库

import re
import requests
import time
import os
import threading
from bs4 import BeautifulSoup

url1='http://www.ezdmw.com/Home/Index/contribution/up_atlas.html?type=&order=new&page='
url2='http://www.ezdmw.com'
headers = {'Referer':'www.baidu.com',
           'User-Agent':'Mozilla/5.0 (Windows NT 6.1) AppleWebKit/537.11 (KHTML, like Gecko) Chrome/23.0.1271.64 Safari/537.11'}
root=os.getcwd()+'\Ezhan'

def xgname(name):
    xname=''
    for i in name:
        if i in ['\\','/',':','*','?','<','>','|','"',' ','.']:
            xname+='#'
        else:
            xname+=i
    return xname

def hq(dz,url):
    try:
        #print('正在进行:',url)
        #print('存入',dz)
        img=requests.get(url,headers=headers).content
        f=open(dz,'wb')
        f.write(img)
        f.close
    except:
        print(url,dz,'获取错误')
    else:
        print(url,dz,'获取成功')

def jm2(name,url):
    tot=1
    name=xgname(name)
    dz=root+'\\'+name
    if not os.path.exists(dz):
        os.makedirs(dz)
    wz=requests.get(url,headers=headers).text
    dome=BeautifulSoup(wz,'html.parser')
    k=dome.find_all('img')
    dxc=[]
    for i in k:
        if(i.parent.parent.name=='pre'):
            #print('--------')
            #print(i.attrs.get('style'))
            #print(i.attrs.get('src'))
            tt=threading.Thread(target=hq , args=(dz+'\\'+str(tot)+'.jpg',i.attrs['src']))
            tt.setDaemon(True)
            dxc.append(tt)
            tot+=1
    print('加入任务中')
    for i in dxc:
        i.start()
    for i in dxc:
        i.join()
    print('完成任务')


def jm1(url):
    wz=requests.get(url,headers=headers).text
    #print(wz)
    dome=BeautifulSoup(wz,'html.parser')
    for i in dome.find_all('a',style="color:#000;",target="_blank"):
        if i.string!=None:
            print(i.string)
            print(url2+i.attrs['href'])
            jm2(i.string,url2+i.attrs['href'])


if __name__ == "__main__":
    if not os.path.exists(root):
        os.makedirs(root)
    for i in range(int(input('输入开始页数:')),11000):
        url=url1+str(i)+'0'
        jm1(url)
        print('第',i,'页执行完毕')



新鲜事 原文

Overnoise
1个月前
调爬虫好麻烦。。。


新鲜事 原文

Overnoise
1个月前
把这个爬虫(https://www.acwing.com/blog/content/2293/)搞成了exe文件 没有python的小伙伴也可以运行了 下载地址(腾讯微云):https://share.weiyun.com/EjT3qEXz



Overnoise
1个月前

注意除数为0抛出异常

#include<bits/stdc++.h>
using namespace std;
int n;
string t;
int main()
{
    cin>>n;
    while(n--){
        try{
            cin>>t;
            int a=0,b=0,c=0;
            for(int i=0;i<=t.length()/2-1;i++)
                a=a*10+t[i]-'0',c=c*10+t[i]-'0';
            for(int i=t.length()/2;i<t.length();i++)
                b=b*10+t[i]-'0',c=c*10+t[i]-'0';
            if(a*b==0) throw "divide 0";
            else if(c%(a*b)==0) puts("Yes");
            else puts("No");
        }
        catch(const char* msg){
            puts("No");
        }
    }
    return 0;
}


新鲜事 原文

Overnoise
1个月前
捞一捞自己的分享 最近大家都在找好康的桌面吧? (成为找壁纸的工具人。。。) 是时候让爬虫代替我们了!!! 我的分享: (我的第一个爬虫的图片不太适合做壁纸) https://www.acwing.com/blog/content/2335/
图片



Overnoise
1个月前

使用python3的切片操作和强制类型转换
注意除数为0特判

n=input()
for i in range(int(n)):
    a=input()
    b=a[:len(a)//2]
    c=a[-len(a)//2:]
    try:
        if (int(a)%(int(b)*int(c))==0):
            print('Yes')
        else:
            print('No')
    except:
        print('No')



Overnoise
2个月前

题目链接
【题目描述】
一个软件开发公司同时要开发两个软件,并且要同时交付给用户,现在公司为了尽快完成这一任务,将每个软件划分成m个模块,由公司里的技术人员分工完成,每个技术人员完成同一软件的不同模块的所用的天数是相同的,并且是已知的,但完成不同软件的一个模块的时间是不同的,每个技术人员在同一时刻只能做一个模块,一个模块只能由一个人独立完成而不能由多人协同完成。一个技术人员在整个开发期内完成一个模块以后可以接着做任一软件的任一模块。写一个程序,求出公司最早能在什么时候交付软件。

【输入】
输入文件第一行包含两个由空格隔开的整数n和m。

接下来的n行每行包含两个用空格隔开的整数d1和d2,d1表示该技术人员完成第一个软件中的一个模块所需的天数,d2表示该技术人员完成第二个软件中的一个模块所需的天数。

【输出】
输出文件仅有一行包含一个整数d,表示公司最早能于d天后交付软件。

【输入样例】
3 20
1 1
2 4
1 6
【输出样例】
18
【数据规模】

对于100%的数据,1≤n≤100,1≤m≤100,1≤d1,d2≤100。

【样例说明】

最快的方案是第一个技术人员完成第二个软件的18个模块,用时18天,第三个技术人员完成第一个软件的18个模块,用时18天,其余的模块由第二个技术人员完成,用时12天,做完所有的模块需要18天。如果第一个技术人员完成第二个软件的17个模块,第三个技术人员完成第一个软件的17个模块,其余的模块由第二个技术人员完成,需要用时18天,做完所有模块仍然需要18天,所以少于18天不可能做完所有模块。

思路

2分答案,然后用dp判断(dp过程见代码,类似背包DP)

参考代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define pass puts("pass")
#define LL long long
#define N 105
#define M 105
using namespace std;

int n,m,ans;
int a[N],b[N];
bool dp[M+M][M+M];

bool work(int p) {
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(int i=1; i<=n; i++)
        for(int x=m; x>=0; x--)
            for(int y=m; y>=0; y--)
                if(dp[x][y])
                    for(int k=0; k*a[i]<=p; k++) {
                        int z=(p-k*a[i])/b[i];
                        dp[min(x+k,m)][min(m,y+z)]=1;
                        if(dp[m][m])
                            return 1;
                    }
    return 0;
}

int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        scanf("%d%d",&a[i],&b[i]);
    int l=0,r=M;
    while(l<=r) {
        int mid=(l+r)/2;
        if(work(mid)) {
            ans=mid;
            r=mid-1;
        } else {
            l=mid+1;
        }
    }
    cout<<ans<<endl;
    return 0;
}



Overnoise
2个月前

题目链接
1676:手机游戏

时间限制: 1000 ms 内存限制: 131072 KB

【题目描述】
明明的手机上有这样一个游戏,一排n个怪物,每个怪物的血量是mi。现在明明可以射出k个伤害均为p的火球,当某个火球射到第i个怪物,除了这个怪物会掉血p以外,它左边的第j个怪物(j≤i),也会遭到max(0,p−(i−j)2)的溅射伤害。当某个怪物的血量为负的时候,它就死了,但它的尸体依然存在,即其他怪物不会因为它死而改变位置。

明明想用这k个火球消灭掉所有的怪物,但他同时希望每个火球的伤害p能尽可能的小,这样他才能完美过关。

所有数均为整数。

【输入】
第一行两个数n,k。

第二行n个数m1,m2,…,mn表示每个怪物的生命值。

【输出】
一行一个整数表示最小的符合要求的p值。

【输入样例】
3 1
1 4 5
【输出样例】
6
【提示】
【数据规模】

对于30%的数据,n≤500。

对于100%的数据,1≤n≤50000,1≤k≤100000,1≤mi≤10^9。

思路

考虑2分答案
因为只对左边有溅射伤害,所以从右边开始遍历
特别注意:当某个怪物的血量为负的时候,它就死了(血量为0时怪物还活着)

参考代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define pass puts("pass")
#define LL long long
#define N 50004
#define M INT_MAX
using namespace std;

int n,k,ans;
int a[N],b[N];

bool work(int p) {
    int all=k;
    for(int i=1; i<=n; i++) b[i]=a[i];
    for(int i=n; i>=1&&all!=-1; i--)
        while(b[i]>=0&&all!=-1) {
            for(int j=i; j>=1&&(i-j)*(i-j)<p; j--)
                b[j]-=p-(i-j)*(i-j);
            all--;
        }

    //cout<<p<<" "<<all<<"\n";
    if(all==-1) return 0;
    return 1;
}

int main() {
    cin>>n>>k;
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    int l=1,r=M;
    while(l<=r) {
        int mid=(l+r)/2;
        if(work(mid)) {
            ans=mid;
            r=mid-1;
        } else
            l=mid+1;
    }
    cout<<ans<<endl;
    return 0;
}