\(\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
仅仅是 \(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();
}
}