首页 > 其他分享 >[HZOJ普及模拟2]

[HZOJ普及模拟2]

时间：2023-08-19 21:45:37浏览次数：51  
标签：std 普及 const number other int256 result 模拟 HZOJ

\(\Huge\color{7ff77f}{打了一场模拟赛，又垫底了。qwq}\)

\(\Huge\color{12f4ff}{快}\) \(\Huge\color{f9f98f}{V}\) \(\Huge\color{ff1256}{本}\) \(\Huge\color{ff4514}{蒟}\) \(\Huge\color{7ffff7}{蒻}\) \(\Huge\color{3f3f3f}{5}\) \(\Huge\color{f54321}{0}\)

\(\huge\color{418418}{好的我们步入正题}\)\(\huge\color{a9780c}{(逃)}\)

HZOJ普及模拟2

T1 地址

\(20pts\)

  • 本来挺水的一道题，结果硬生生丢了 \(80\) 分。。。 在判断是否为数字时，如果是数字，则 \(continue\) ，于是当最后一次循环时，如果还是数字，就 \(continue\) 了，于是快乐的 \(WA\) 了 \(qwq\)。
//码风怪异
#include<iostream>
#include<cstring>
#include<string.h>
using std::string;
string a,b;
int num[10];
signed main(void)
{
    //freopen("ip.in","r",stdin);
    //freopen("ip.out","w",stdout);
	int i,j,n,sum=0,flag=0;
    std::cin>>a;
    n=a.size();
    int cnt=0;
    for(i=0;i<n;++i)
    {
        if(a[i]>='0'&&a[i]<='9')
        {
            b[++cnt]=a[i];if(i!=n-1)continue;
        }
        else if(!flag)printf("NO\n"),flag=1;
        if(cnt>3)
        {
            if(!flag)printf("NO\n"),flag=1;
            ++sum;
            num[sum]=255;
            cnt=0;
        }
        if(cnt<=3&&cnt!=0)
        {
            ++sum;
            for(j=1;j<=cnt;++j)
                num[sum]=num[sum]*10+(b[j]-48);
            if(num[sum]>255&&!flag)
                printf("NO\n"),flag=1;
            cnt=0;
        }
        
    }
    if(!flag)
    {printf("YES\n");return 0;}
    for(i=1;i<=4;++i)
    {
        if(num[i]<=255)printf("%d",num[i]);
        else printf("255");
        if(i<4)printf(".");
    }
}

T2 内积

\(60pts\)

  • 本来也可以 \(A\) 掉的，但是一开始没有用 \(freopen\) 于是只得了 \(60\) 得 \(60\) 的原因是用了一个 \(int256\) 然后 \(T\) 了4个点，如果用 \(long long\) 就 \(AC\) 了

\(60pts\) 代码 \((int256)\)
\(\large{(如果您想要使用int256中的除法，请重构除法函数。~~因为这个真的很慢~~)}\)

//1145141919810......
#include <iostream>
#include <string>
#include <algorithm>
#include <stdexcept>

class int256 {
public:
    std::string number;
    bool negative;

    int256() : number("0"), negative(false) {}

    int256(const std::string& value) : number(value), negative(false) {
        if (!value.empty() && value[0] == '-') {
            negative = true;
            number = number.substr(1);
        }
    }

    friend std::ostream& operator<<(std::ostream& os, const int256& num) {
        if (num.number == "0") {
            os << "0";
        } else {
            if (num.negative) {
                os << "-";
            }
            os << num.number;
        }
        return os;
    }

    friend std::istream& operator>>(std::istream& is, int256& obj) {
        std::string input;
        is >> input;
        obj = int256(input);
        return is;
    }
    int256 operator-() const {
        return int256(number);
    }
    bool operator==(const int256& other) const {
        return (number == other.number && negative == other.negative);
    }

    bool operator<(const int256& other) const {
        if (negative && !other.negative) {
            return true;
        } else if (!negative && other.negative) {
            return false;
        } else if (!negative && !other.negative) {
            if (number.length() < other.number.length()) {
                return true;
            } else if (number.length() > other.number.length()) {
                return false;
            } else {
                return number < other.number;
            }
        } else {
            return (-other) < (-*this);
        }
    }
	bool operator<=(const int256& other) const 
    {
    	return (other.number < number||other.number == number);
	}
    bool operator>(const int256& other) const 
    {
    	return !(other.number <= number);
	}
	bool operator>=(const int256& other) const 
    {
    	return (other.number > number||other.number == number);
	}
	bool operator!=(const int256& other) const 
    {
    	return !(other.number == number);
	}

    int256 operator+(const int256& other) const {
        int256 result;
        if (negative == other.negative) {
            result.number = add(number, other.number);
            result.negative = negative;
        } else {
            if (abs_compare(number, other.number) >= 0) {
                result.number = subtract(number, other.number);
                result.negative = negative;
            } else {
                result.number = subtract(other.number, number);
                result.negative = other.negative;
            }
        }
        return result;
    }
    int256 operator++() const {
    	return number+'1';
	}
    int256 operator-(const int256& other) const {
        int256 result;
        if (negative != other.negative) {
            result.number = add(number, other.number);
            result.negative = negative;
        } else {
            if (abs_compare(number, other.number) >= 0) {
                result.number = subtract(number, other.number);
                result.negative = negative;
            } else {
                result.number = subtract(other.number, number);
                result.negative = !negative;
            }
        }
        return result;
    }
	int256 operator*(const int256& other) const {
        int256 result;
        result.number = multiply(number, other.number);
        result.negative = negative != other.negative;
        return result;
    }

    int256 operator/(const int256& other) const {
        if (other.number == "0") {
            throw std::runtime_error("Division by zero");
        }

        int256 result;
        result.number = divide(number, other.number);
        result.negative = negative != other.negative;
        return result;
    }

    int256 operator%(const int256& other) const {
        if (other.number == "0") {
            throw std::runtime_error("Division by zero");
        }

        int256 result;
        result.number = modulo(number, other.number);
        result.negative = negative;
        return result;
    }
    int256& operator+=(const int256& other) {
	    *this = *this + other;
	    return *this;
	}
	
	int256& operator-=(const int256& other) {
	    *this = *this - other;
	    return *this;
	}
	
	int256& operator*=(const int256& other) {
	    *this = *this * other;
	    return *this;
	}
	
	int256& operator/=(const int256& other) {
	    *this = *this / other;
	    return *this;
	}
	
	int256& operator%=(const int256& other) {
	    *this = *this % other;
	    return *this;
	}
private:
    std::string add(const std::string& a, const std::string& b) const {
        std::string result;
        int carry = 0;
        int i = a.length() - 1;
        int j = b.length() - 1;

        while (i >= 0 || j >= 0 || carry != 0) {
            int digit1 = (i >= 0) ? (a[i] - '0') : 0;
            int digit2 = (j >= 0) ? (b[j] - '0') : 0;
            int sum = digit1 + digit2 + carry;
            carry = sum / 10;
            sum = sum % 10;
            result = std::to_string(sum) + result;
            --i;
            --j;
        }

        return result;
    }

    std::string subtract(const std::string& a, const std::string& b) const {
        std::string result;
        int borrow = 0;
        int i = a.length() - 1;
        int j = b.length() - 1;

        while (i >= 0 || j >= 0) {
            int digit1 = (i >= 0) ? (a[i] - '0') : 0;
            int digit2 = (j >= 0) ? (b[j] - '0') : 0;
            int diff = digit1 - digit2 - borrow;

            if (diff < 0) {
                diff += 10;
                borrow = 1;
            } else {
                borrow = 0;
            }

            result = std::to_string(diff) + result;
            --i;
            --j;
        }

        std::size_t pos = result.find_first_not_of('0');
        if (pos != std::string::npos) {
            result = result.substr(pos);
        } else {
            result = "0";
        }

        return result;
    }

    std::string multiply(const std::string& a, const std::string& b) const {
        int len1 = a.length();
        int len2 = b.length();
        std::string result(len1 + len2, '0');

        for (int i = len1 - 1; i >= 0; --i) {
            int carry = 0;
            int n1 = a[i] - '0';

            for (int j = len2 - 1; j >= 0; --j) {
                int n2 = b[j] - '0';
                int sum = n1 * n2 + carry + (result[i + j + 1] - '0');
                carry = sum / 10;
                result[i + j + 1] = sum % 10 + '0';
            }

            result[i] += carry;
        }

        std::size_t pos = result.find_first_not_of('0');
        if (pos != std::string::npos) {
            result = result.substr(pos);
        } else {
            result = "0";
        }

        return result;
    }
    std::string divide(const std::string& dividend, const std::string& divisor)const {
	    if (divisor == "0") {
	        throw std::runtime_error("Division by zero");
	    }
	    
	    std::string quotient;
	    std::string remainder = dividend;
	    
	    while (remainder != "0" && remainder.size() >= divisor.size()) {
	        int carry = 0;
	        std::string partial_quotient;
	        
	        size_t pos = 0;
	        
	        while (pos < remainder.size()) {
	            int current = carry * 10 + (remainder[pos] - '0');
	            
	            if (current < (divisor[0] - '0')) {
	                if (!partial_quotient.empty()) {
	                    partial_quotient.push_back('0');
	                }
	            } else {
	                partial_quotient.push_back(current / (divisor[0] - '0') + '0');
	                carry = current % (divisor[0] - '0');
	            }
	            
	            pos++;
	        }
	        
	        size_t first_nonzero = partial_quotient.find_first_not_of('0');
	        partial_quotient = partial_quotient.substr(first_nonzero);
	        quotient += partial_quotient.empty() ? "0" : partial_quotient;
	        
	        remainder = std::to_string(carry);
	    }
	    
	    return quotient;
	}
	
	std::string modulo(const std::string& dividend, const std::string& divisor)const {
	    if (divisor == "0") {
	        throw std::runtime_error("Division by zero");
	    }
	    
	    std::string remainder = dividend;
	    
	    while (remainder != "0" && remainder.size() >= divisor.size()) {
	        int carry = 0;
	        
	        size_t pos = 0;
	        
	        while (pos < remainder.size()) {
	            int current = carry * 10 + (remainder[pos] - '0');
	            carry = current % (divisor[0] - '0');
	            pos++;
	        }
	        
	        remainder = std::to_string(carry);
	    }
	    
	    return remainder;
	}
    int abs_compare(const std::string& a, const std::string& b) const {
        if (a.length() < b.length()) {
            return -1;
        } else if (a.length() > b.length()) {
            return 1;
        } else {
            return a.compare(b);
        }
    }
};
int256 a[1000100],b[1000100],sum;
bool cmp(int x,int y)
{
	return x<y;
}
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //freopen("nj.in","r",stdin);
    //freopen("nj.out","w",stdout);
	int i,j,m,n;
	cin>>n;
	for(i=1;i<=n;i++)cin>>a[i];
	for(i=1;i<=n;i++)cin>>b[i];
	stable_sort(a+1,a+n+1);
	stable_sort(b+1,b+n+1);
	for(i=1;i<=n;i++)sum+=a[i]*b[i];
	cout<<sum;
}

不水int256了。

\(AC\) 代码。(虽然很简陋)

//凑合看吧
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,sum=0,flag=0;
int a[1100001],b[1100001];
signed main(void)
{
    //freopen("nj.in","r",stdin);
    //freopen("nj.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	int i,j,k,m;
	cin>>n;
	for(i=1;i<=n;i++)
		cin>>a[i];
	for(i=1;i<=n;i++)
		cin>>b[i];
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
    for(i=1;i<=n;i++)sum+=a[i]*b[i];
    cout<<sum;
}

T3 翻转

\(0pts\) 搜索题，没打。

也许可以去看看其他大佬的文章？

T4 阶乘

\(0pts\) 当时打表，结果 \(CE\) 了。

  • 首先，阶乘的增长速度极快
1!: 1
2!: 2
3!: 6
4!: 24
5!: 120
6!: 720
7!: 5040
8!: 40320
9!: 362880
10!: 3628800
11!: 39916800
12!: 479001600
13!: 6227020800
14!: 87178291200
15!: 1307674368000
16!: 20922789888000
17!: 355687428096000
18!: 6402373705728000
19!: 121645100408832000
20!: 2432902008176640000

从 \(1\) 到 \(1000\) 的阶乘

也可以打开这个?

仅仅是 \(20!\) 就已经达到了 \(2432902008176640000\) ，而 \(21!\) 已经超过了 \(long long\) 的存储范围。

  • 因此我们可以在一个较小的区间内枚举(而且范围是连续的，很方便枚举)，区间大约在 \(\Large{\sqrt[i]{n}}\) 左右， \(\large{(i为阶乘长度,大约枚举到20左右即可)}\) 。
  • 可以使用优先队列来存储每次得到的结果，(本来我用的结构体，但是莫名其妙的 \(TLE\) ，就算只有一个数据也要用几百毫秒，改成优先队列只需要 \(89ms\) )，这样得到的结果就是有序的，但是要注意优先队列默认从大到小排序，因此可以存负值或者写小根堆。
  • 当然，\(\Large{\dfrac{n!}{(n-1)!}}\) 的值是等于 \(n\) 的，因此可以不枚举 \(i=1\) 的情况。并且当 \(n=1\) 时，有无数解 \((\Large{\dfrac{n!}{n!}=1})\) 所以可以特判。
  • 由于 \(long long\) 最大可以存到 \(20!\) ，因此可以预处理 \(1\) 到 \(20\) 的阶乘 (以便卡常)。

\(\large{AC}\) \(\large{Code}\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
int fac[30][30];
inline int read(){
    int x=0,f=1;
    char s=getchar();
    for(;s<'0'||s>'9';s=getchar()) if(s=='-') f=-1;
    for(;'0'<=s&&s<='9';s=getchar()) x=(x<<1)+(x<<3)+(s^48);
    return x*f;
}
void write(int x){
    if(x<0) x=-x,putchar('-');
    if(x>9) write(x/10);
    putchar(x%10+48);
}
priority_queue<pair<int,int> >res;
signed main(void)
{
    //freopen("jc.in","r",stdin);
    //freopen("jc.out","w",stdout);
	int i,j,k,m,t,n;
    int cnt=1;
    for(i=1;i<=20;i++)
    {
        fac[i][i]=i;
        for(j=i+1;j<=20;++j)
            fac[i][j]=fac[i][j-1]*j;
    }
    t=read();
    while(t--)
    {
        cnt=1;
        n=read();
        if(n==1){printf("-1\n");continue;}
        res.push(make_pair(-n,-n+1));
        for(i=2;i<=20;++i)
        {
            int x=pow(n*1.0,1.0/i);
            while(k<n)
            {
                int y=x-i+1;
                int k=1;
                if(y-1>0)
                {
                    if(x<=20)
                    {
                        k=fac[y][x];
                        if(k>n)break;
                        if(k==n){++cnt;res.push(make_pair(-x,-y+1));break;}
                    }
                    else
                    {
                        for(j=y;j<=x;++j)k*=j;
                        if(k>n)break;
                        if(k==n){++cnt;res.push(make_pair(-x,-y+1));break;}
                    }
                }
                x++;
            }
        }
        write(cnt);printf("\n");
        for(i=cnt;i>=1;--i)
            write(-res.top().first),printf(" "),write(-res.top().second),printf("\n"),res.pop();
    }
}

\(\Huge{写完了？}...\)

\(\LARGE\color{fe3faf}{但是打了一场模拟赛，又垫底了。}\)

标签：std,普及,const,number,other,int256,result,模拟,HZOJ
From： https://www.cnblogs.com/minecraft666/p/17643175.html

相关文章

  • CSP模拟25
    炒币、凑数、同构、最近公共祖先A.炒币举个栗子，对于序列\[1,4,5\]在\(1\)处买进，在\(5\)处卖出是最优的选择。为什么不选择在\(4\)处买，因为\(4\)处成本更高，所以我们可以把一段递增或递减的序列缩成几个互不相同的点。例如\[1,3,5,3,2,7\]变成\[5,2,7\]只有这......
  • 普及模拟2 +【LGR-155-Div.3】洛谷基础赛 #3 &「NnOI」Round 2
    普及模拟2\(T1\)地址\(0pts\)简化题意：判断一个\(IP\)地址是否合法（数据保证字符串中存在且仅存在4个被字符分开的整数）#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#definesortstable_sort#defineendl'\n'chars[100];intmain(){ freope......
  • python模拟用户pa取
    使用Selenium模拟用户爬取页面内容，并输出成文件。关于Selenium是什么，欢迎看这篇文章：seleniumPython教程。在这里，我只讲我主要的实现。首先作为一款工具脚本，我们应该不喜欢窗口界面吧，除非你需要动态的观察程序的操作。所以，我开启了无头浏览器模式#无头浏览器chrome_options=webd......
  • python生成模拟数据
    python faker的使用Faker是一个Python包，开源的GITHUB项目，主要用来创建伪数据，使用Faker包，无需再手动生成或者手写随机数来生成数据，只需要调用Faker提供的方法，即可完成数据的生成安装pipinstallFaker使用fromfakerimportFakerfaker=Faker(locale='zh_CN')fromfakerimportF......
  • 8.19 模拟赛小结
    前言结束了也许这几天很苦但也是最有意义的几天这篇写简单一点吧T1颠倒黑白很强的构造题根据打表找出思路因为最左下角的是一定要点的就考虑它如果是先手左下角有黑色就把它点了后手只能帮我们把其它黑色点了最后还是我们先点完若是后手左下角是白色与先手同......
  • 【考后总结】8 月 CSP-S 模拟赛 7
    8.19CSP模拟25给我一首歌的时间-周杰伦雨淋湿了天空毁得很讲究你说你不懂为何在这时牵手我晒干了沉默悔得很冲动就算这是做错也只是怕错过在一起叫梦分开了叫痛是不是说没有做完的梦最痛迷路的后果我能承受这最后的出口在爱过了才有能不能给我一首歌的时......
  • 模拟应用网关下游系统的一些场景测试接口
    场景：构造一个返回请求参数(表单入参)，请求header，设置响应header的测试demo接口框架：springboot@ResponseBody@RequestMapping("/test/api/v1")publicMapserverPostTestv1(HttpServletRequesthttpRequest,HttpServletResponsehttpResponse,@RequestHeaderMultiValueMap<Str......
  • FBM山体模拟生成
    FBM山体模拟生成引言当我们沐浴在自然山脉的美景中，岩石峰峦和蜿蜒山谷的形态总能唤起人们的惊叹。然而，要在计算机图形中精确地还原这些复杂的地形却是一项挑战。在计算机图形学和游戏开发领域，分数布朗运动（FBM）被用来模拟自然地貌，为生成逼真的山地景观提供了一种强大方法。FBM利用分......
  • 2023年 8月15日普及组南外集训题解
    A陷阱我们可以从\(l\)枚举到\(d\)，再计算是否满足要求，满足要求加入到数组中，输出第一个和最后一个#include<iostream>usingnamespacestd;constintN=1e5+5;intk;intnums[N];intmain(){intl,d,x;cin>>l>>d>>x;for(inti=l;i<=d......
  • vector类的模拟实现
    一、vector的介绍vector的文档介绍1、vector是表示可变大小数组的序列容器。2、就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。3、本......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99