Problem 68

考虑只有10个数字,而且10!非常小,于是我们枚举全排列就可以过了。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
   int x=0,f=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
   while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
   return x*f;
}
int a[11];
bool check(){//123 435 657 879 1092
    int tmp=a[1]+a[2]+a[3];
    if(tmp!=a[4]+a[3]+a[5])return 0;
    if(tmp!=a[6]+a[5]+a[7])return 0;
    if(tmp!=a[8]+a[7]+a[9])return 0;
    if(tmp!=a[9]+a[2]+a[10])return 0;
    if(a[1]!=10&&a[4]!=10&&a[6]!=10&&a[8]!=10&&a[10]!=10)return 0;
    return 1;
}
int pj(int p,int b,int c){
    return 100*a[p]+10*a[b]+a[c];
}
int mn(){
    int t=min(a[1],min(a[4],min(a[6],min(a[8],a[10]))));
    if(t==a[1])return 1;
    if(t==a[4])return 2;
    if(t==a[6])return 3;
    if(t==a[8])return 4;
    if(t==a[10])return 5;
}
void P(int &a,int b){
    a=a*pow(10,(int)log10(b)+1)+b;
}
int b[10];
signed main(){
    for(int i=1;i<=10;i++){
        a[i]=i;
    }
    int ans=0;
    do{
        if(!check())continue;
        b[1]=pj(1,2,3),b[2]=pj(4,3,5),b[3]=pj(6,5,7);
        b[4]=pj(8,7,9),b[5]=pj(10,9,2);
        int p=mn(),l=0;
        for(int i=1;i<=5;i++){
            int k=(p+i-1)%5;
            if(k==0)k=5;
            P(l,b[k]);
        }
        ans=max(ans,l); 

    }while(next_permutation(a+1,a+11));
    cout<<ans<<endl;
    return 0;
}

Problem 69

线性筛一波phi之后统计答案输出即可。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int st[N],pr[N],cnt,phi[N];
void prime(int n=N-10){
    for(int i=2;i<=n;i++){
        if(!st[i])st[i]=2,pr[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt&&pr[j]*i<=n;j++){
            st[pr[j]*i]=1;
            if(i%pr[j]==0){
                phi[pr[j]*i]=phi[i]*pr[j];
                break;
            }
            phi[pr[j]*i]=phi[i]*(pr[j]-1);
        }
    }
}
int main(){
    double mx=0,ans=-1;
    prime();
    for(int i=2;i<=N-10;i++){
        if(1.0*i/phi[i]>mx){
            mx=1.0*i/phi[i];
            ans=i;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Problem 70

欧拉总计函数与重排

在小于n的数中,与n互质的数的数目记为欧拉总计函数φ(n)(有时也称为φ函数)。例如,因为1、2、4、5、7和8均小于9且与9互质,故φ(9)=6。

1被认为和任意正整数互质,所以φ(1)=1。

有趣的是,φ(87109)=79180,而79180恰好是87109的一个重排。

在1 < n < 10^7中,有些n满足φ(n)是n的一个重排,求这些取值中使n/φ(n)最小的一个。


和上一题一样,线性筛phi之后统计答案即可。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+10;
int st[N],pr[N],cnt,phi[N];
void prime(int n=N-10){
    for(int i=2;i<=n;i++){
        if(!st[i])st[i]=2,pr[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt&&pr[j]*i<=n;j++){
            st[pr[j]*i]=1;
            if(i%pr[j]==0){
                phi[pr[j]*i]=phi[i]*pr[j];
                break;
            }
            phi[pr[j]*i]=phi[i]*(pr[j]-1);
        }
    }
}
int p[11];
int get(int a){
    int k=0;
    while(a){
        k+=p[a%10];
        a/=10;
    }
    return k;
}
bool check(int a,int b){
    return get(a)==get(b);
}
signed main(){
    p[0]=1;
    for(int i=1;i<=10;i++)
        p[i]=p[i-1]*10;
    double mn=1e5;
    int ans=-1;
    prime();
    for(int i=2;i<=N-10;i++){
        if(check(i,phi[i])){
            if(1.0*i/phi[i]<mn){
                mn=1.0*i/phi[i];
                ans=i;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}


Problem 71

有序分数

考虑形如n/d的分数,其中n和d均为正整数。如果n < d且其最大公约数为1,则该分数称为最简真分数。

如果我们将d ≤ 8的最简真分数构成的集合按大小升序列出,我们得到:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8可以看出2/5是3/7直接左邻的分数。

将所有d ≤ 1,000,000的最简真分数按大小升序排列,求此时3/7直接左邻的分数的分子。


考虑乱搞。

记得之前在OI-wiki上看到过一个这样的数据结构:Stern-Brocot树

然后感觉有点类似,但是又不太像。

题面中又给出了d=8时3/7左侧的第一个真分数,考虑从这个入手。

在Stern-Brocot树中,第一层是$\frac{0}{1}$和$\frac{1}{0}$(无视这个理论上无意义的分数),假设上一层有相邻的两个真分数$\frac{a}{b}$和$\frac{c}{d}$,下一层就会在它们中间出现一个新的分数$\frac{a+c}{b+d}$,并且这个分数的值也是在它们之间的。

略证:

$\frac{a}{b}<\frac{c}{d}$

$ad < bc$

$ad+ab < bc+ab$

$\frac{a}{b} <\frac{a+c}{b+d}$

另一边同理,+ab改成+cd即可。

这样,我们一层层递归下去就可以得到有序真分数序列。

那么就考虑能不能在2/5和3/7中间像这样插入新的分数来替代2/5的位置,直到新的分母超过了10^6。

试了一下,然后就过了。

然后这个过程可以用取模做到O(1),完了。

code

#include<bits/stdc++.h>
using namespace std;
int main(){
    int fz=2,fm=5;
    int n=1000000;
    int del=(n-fm)/7;
    fz+=3*del;
    cout<<fz;
    return 0;
}

Problem 72

分数计数

考虑形如n/d的分数,其中n和d均为正整数。如果n < d且其最大公约数为1,则该分数称为最简真分数。

如果我们将d ≤ 8的最简真分数构成的集合按大小升序列出,我们得到:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8可以看出该集合中共有21个元素。

d ≤ 1,000,000的最简真分数构成的集合中共有多少个元素?


以为是和上一道一样的套路,发现不是的。

我们统计以i为分母对答案的贡献,发现就是φ(i)。

所以答案就是$\sum^{10^6}_{i=2} \phi(i)$。

至于为什么不加phi1呢,如果你和鸽酱一样觉得1/1是真分数的话,那就加上吧:)

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int st[N],pr[N],cnt,phi[N];
void prime(int n=N-10){
    for(int i=2;i<=n;i++){
        if(!st[i])st[i]=2,pr[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt&&pr[j]*i<=n;j++){
            st[pr[j]*i]=1;
            if(i%pr[j]==0){
                phi[pr[j]*i]=phi[i]*pr[j];
                break;
            }
            phi[pr[j]*i]=phi[i]*(pr[j]-1);
        }
    }
}
int main(){
    long long ans=0;
    prime();
    for(int i=2;i<=N-10;i++){
        ans+=phi[i];
    }
    cout<<ans<<endl;
    return 0;
}


Problem 73

分数有范围计数

考虑形如n/d的分数,其中n和d均为正整数。如果n < d且其最大公约数为1,则该分数称为最简真分数。

如果我们将d ≤ 8的最简真分数构成的集合按大小升序列出,我们得到:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8可以看出在1/3和1/2之间有3个分数。

将d ≤ 12,000的最简真分数构成的集合排序后,在1/3和1/2之间有多少个分数?


Stern-Brocot树

利用它的建树在分母<=12000的范围内递归就完事了。

code

#include<bits/stdc++.h>
using namespace std;
int cnt=0,n=12000;
void build(int a=1,int b=2,int c=1,int d=3){
    int x=a+c,y=b+d;
    if(y>n)return;
    if(x>y)return;
    cnt++;
    build(a,b,x,y);
    build(x,y,c,d);
}
int main(){
    build();
    printf("%d\n",cnt);
    return 0;
}


Problem 74

数字阶乘链

145之所以广为人知,是因为它的各位数字的阶乘之和恰好等于本身:

1! + 4! + 5! = 1 + 24 + 120 = 145

而169则可能不太为人所知,尽管从169开始不断地取各位数字的阶乘之和构成了最长的循环回到169;事实上,只存在三个这样的循环:

169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872

不难证明,从任意数字出发最终都会陷入循环。例如,

69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)

从69开始可以得到一个拥有五个不重复项的链,但是从一个小于一百万的数出发能够得到的最长的无重复项链包含有60项。

从小于一百万的数出发,有多少条链恰好包含有60个不重复项?


我以为需要记忆化,然而直接爆搜就可以了。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int now;
int p[11];
int calc(int x){
    int ans=0;
    while(x){
        ans+=p[x%10];
        x/=10;
    }
    return ans;
}
int res[100000010];
int dfs(int x,int dep=0){
//    cout<<x<<endl;
    dep++;x=calc(x);
    if(res[x]==now)return dep;
    res[x]=now;
    return dfs(x,dep);
}
signed main(){
    p[0]=1;
    for(int i=1;i<=9;i++)
        p[i]=p[i-1]*i;
    int n=1000000,ans=0;
    for(now=1;now<=n;now++){
//        cout<<now<<endl;
        if(dfs(now)==60)ans++;
    }
    cout<<ans<<endl;
    return 0;
}


Problem 75

唯一的整数边直角三角形

只能唯一地弯折成整数边直角三角形的电线最短长度是12厘米;当然,还有很多长度的电线都只能唯一地弯折成整数边直角三角形,例如:

12厘米: (3,4,5)
24厘米: (6,8,10)
30厘米: (5,12,13)
36厘米: (9,12,15)
40厘米: (8,15,17)
48厘米: (12,16,20)

相反地,有些长度的电线,比如20厘米,不可能弯折成任何整数边直角三角形,而另一些长度则有多个解;例如,120厘米的电线可以弯折成三个不同的整数边直角三角形。

120厘米: (30,40,50), (20,48,52), (24,45,51)

记电线长度为L,对于L ≤ 1,500,000,有多少种取值只能唯一地弯折成整数边直角三角形?


首先考虑找到像(3,4,5),(5,12,13)这样的本原勾股数组,即不能被其他勾股数组乘上$d,d∈N^+$得到的勾股数组。

易得这样的勾股数组满足$gcd(a,b,c)=1$,否则一定能约掉这个公因数之后得到本原勾股数组。

然后观察一下得到本原勾股数组都是由2个奇数+1个偶数组成的,考虑如何证明。

首先肯定不是三个偶数组成的,否则有$gcd=2$。

然后考虑是否能两个偶数一个奇数,设$a=2x,b=2y,c=2z+1$,我们有$a^2=4x^2,b^2=4y^2,c^2=4z^2+4z+1$,显然前两项都是偶数,第三项是奇数,不能组成和差关系。

考虑三个奇数,设$a=2x+1,b=2y+1,c=2z+1$,那么和上面同样的可以得到三项奇数,不能组成和差关系。

只有当2个奇数和1个偶数的时候,我们才能有两个奇数的平方和等于剩余偶数的平方和。

假定$a,c$都是奇数,$b$是偶数。

变形$a^2+b^2=c^2$,得到$a^2=(c+b)(c-b)$,考虑证明$gcd((c+b),(c-b))=1$。

设$d=gcd((c+b),(c-b))$,那么我们有$d|(c+b),d|(c-b)$,那么$d|(c+b+c-b),d|(c+b-c+b)$,也就是$d|2c,d|2b$,另外我们还有$d^2|a^2$,也就是$d|a$。

然后我们有$b\mod 2=0,c\mod 2=1$,那么就有$(b+c)\mod 2=1$,所以$d$一定是奇数,否则不满足$d|(b+c)$。

那么就可以变为$d|b,d|c$,再加上$d|a,gcd(a,b,c)=1$,就可以得到d=1了。

于是得证。

然后考虑对$a^2$使用惟一分解定理,得到它的质因数的指数一定都是偶数,再考虑如何把$a^2$分成两个互质的数的积,那么这两个数里面一定各自包含了某些偶数次幂的质因子,也就是说这两个数也是完全平方数。那么这两个数是谁呢,没错,就是(c+b)和(c-b)。

于是我们设$s^2=c+b,t^2=c-b$。

首先我们有$a^2=s^2*t^2$,也就是$a=st$。

然后我们可以得到$c=\frac{s^2+t^2}{2},b=\frac{s^2-t^2}{2}$。

所以我们枚举互质奇数s和t,就可以计算出一对本原勾股数组(a,b,c)。

为什么互质?(c+b)和(c-b)是互质的。

为什么奇数?(c+b)是奇数,(c-b)也是奇数。

所以我们就可以考虑通过枚举这个得到所有的本原勾股数组,因为每一对勾股数组都可以通过上述的分解方式找到一对s,t。

然后这道欧拉题就通过暴力枚举s和t来找到就好了,小剪枝就看代码了。。

code

#include<bits/stdc++.h>
using namespace std;
int res[1500010];
int main(){
    int n=1500000;
    int e=sqrt(n);
    for(int t=1;t<=n&&t<=e;t+=2){
        for(int s=t+2;s<=e&&s*t<=n;s+=2){
            if(__gcd(s,t)!=1)continue;
            int a=s*t;
            int b=s*s-t*t;b>>=1;
            int c=s*s+t*t;c>>=1;
            int S=a+b+c;
            if(S>n)break;
            for(int i=1;S*i<=n;i++){
                res[S*i]++;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(res[i]==1)ans++;
    }
    cout<<ans<<endl;
    return 0;
}


Problem 76

加和计数

将5写成整数的和有6种不同的方式:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

将100写成整数的和有多少种不同的方式?


完全背包。不能只放一个100,所以答案-1即可。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int f[110];
signed main(){
    int n=100;
    f[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            f[j]+=f[j-i];
        }
    }
    cout<<f[n]-1<<endl;
    return 0;
}


Problem 77

素数加和

将10写成素数的和有5种不同的方式:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

写成素数的和有超过五千种不同的方式的数最小是多少?


考虑魔改欧拉筛,每筛出来一个质数就去更新答案,最后输出的时候发现答案小的离谱。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int st[N],pr[N],cnt,dp[N];
int ans=0x3f3f3f3f;
void prime(int n=N-10){
    for(int i=2;i<=n;i++){
        if(!st[i]){
            st[i]=2,pr[++cnt]=i;
            for(int j=i;j<=n;j++){
                dp[j]+=dp[j-i];
                if(dp[j]>5000){
                    ans=min(ans,j);
                }
            }
        }
        for(int j=1;j<=cnt&&pr[j]*i<=n;j++){
            st[pr[j]*i]=1;
            if(i%pr[j]==0)break;
        }
    }
}
int main(){
    dp[0]=1;
    prime();
    cout<<ans<<endl;
    cout<<dp[ans]<<endl;
    return 0;
}

Problem 78

硬币分拆

记p(n)是将n枚硬币分拆成堆的不同方式数。例如,五枚硬币有7种分拆成堆的不同方式,因此p(5)=7。

OOOOO
OOOO O
OOO OO
OOO O O
OO OO O
OO O O O
O O O O O

找出使p(n)能被一百万整除的最小n值。


发现只需要被100w整除,于是O(n^2)跑出来即可,过程值只保留6位。

#include<bits/stdc++.h>
#define reg register
#define int long long
using namespace std;
int f[1000010];
const int mod=1e10;
signed main(){
    int n=60000;
    f[0]=1;
    for(reg int i=1;i<=n;i++){
        for(reg int j=i;j<=n;j++){
            f[j]+=f[j-i];
            f[j]%=mod;
        }
    }
    for(reg int i=1;i<=n;i++){
        if(f[i]%1000000==0){
            printf("%d\n",i);
            return 0;
        }
    }
    return 0;
}

Problem 79

密码推断

网上银行常用的一种密保手段是向用户询问密码中的随机三位字符。例如,如果密码是531278,询问第2、3、5位字符,正确的回复应当是317。

在文本文件keylog.txt中包含了50次成功登陆的正确回复。

假设三个字符总是按顺序询问的,分析这个文本文件,给出这个未知长度的密码最短的一种可能。


观察答案,发现所有出现的数字都只出现了一次,所以拓扑排序一下就过了。

code

#include<bits/stdc++.h>
using namespace std;
vector<int> g[25];
int deg[15];
int c[15];
queue<int> q;
int main(){
    string a;
    freopen("E79.txt","r",stdin);
    while(cin>>a){
        g[a[0]^48].push_back(a[1]^48);
        g[a[0]^48].push_back(a[2]^48);
        g[a[1]^48].push_back(a[2]^48);
        c[a[0]^48]=c[a[1]^48]=c[a[2]^48]=1;
        deg[a[1]^48]++,deg[a[2]^48]+=2;
    }
    for(int i=0;i<=9;i++){
        if(!deg[i]&&c[i])q.push(i);
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        printf("%d",u);
        for(int i=0;i<g[u].size();i++){
            if(!(--deg[g[u][i]]))q.push(g[u][i]);

        }
    }
    return 0;
}


Problem 80

平方根数字展开

众所周知,如果一个自然数的平方根不是整数,那么就一定是无理数,也即无限不循环小数。

2的平方根为1.41421356237309504880…,它的前一百个数字(包括小数点前的1)的和是475。

考虑前一百个自然数的平方根,求其中所有无理数的前一百个数字的总和。


高精度开根,模拟就好了

code

#include<bits/stdc++.h>
using namespace std;
int lim=103;
struct node{
    int a[310],len;
    void csh(){len=1;memset(a,0,sizeof a);}
    int &operator [] (int x){return a[x];}
    int operator[] (int x)const{return a[x];}
    node operator * (const node &x){
        node s;s.csh();s.len=len*2-1;
        for(int i=1;i<=len;i++)
            for(int j=1;j<=x.len;j++)
                s[i+j-1]+=a[i]*x[j];
        for(int i=1;i<=s.len;i++)
            s[i+1]+=s[i]/10,s[i]%=10;
        int l=s.len;s.len=len;
        for(int i=1;i<=s.len;i++){
            s[i]=s[i+s.len];
        }
        for(int i=s.len+1;i<=l;i++)
            s[i]=0;
        return s; 
    }
    node operator = (const int &x){
        int i=0,tmp=x;len=0;
        while(tmp)a[++len]=tmp%10,tmp/=10;
    }
    node operator = (const node &x){
        memcpy(a,x.a,sizeof a);
        len=x.len;
    }
    void print(){
        for(int i=len;i>=1;i--)
            printf("%d",a[i]);
        puts("");
    }
    int sum(){
        int s=0;
        for(int i=lim-100+1;i<=lim;i++){
            s+=a[i];
        }
        return s;
    }
};
bool xy(node a,node b){
    for(int i=lim;i>=1;i--){
        if(a[i]!=b[i])return a[i]<b[i];
    }
    return 0;
} 
int len(int t){
    int c=0;
    while(t){
        c++;
        t/=10; 
    }
    return c-1;
}
int solve(int x,int op){
    node k,ans;
    ans.csh(),k.csh();
    int t=x;
    int l=lim-len(t)-op;
    while(t){
        ans[l++]=t%10;
        t/=10;
    }
    ans.len=lim;
    k[lim]=(int)sqrt(x);
    k.len=lim;
    for(int i=lim-1;i>=1;i--){
        while(1){
            k[i]++;
            node p=k*k;
            if(xy(ans,p)){
                k[i]--;
                break;
            }
            if(k[i]==10)return solve(x,1);
        }
    }
    return k.sum(); 
}
int main(){
    int ans=0;
    for(int i=1;i<=100;i++){
        int k=sqrt(i);
        if(k*k==i)continue;
        ans+=solve(i,0);
    }
    printf("%d\n",ans);
    return 0; 
}


Problem 81

路径和:两个方向

在如下的5乘5矩阵中,从左上方到右下方始终只向右或向下移动的最小路径和为2427,由标注红色的路径给出。

| | | | | |
| :-: | :-: | :-: | :-: | :-: |
| 131 | 673 | 234 | 103 | 18 |
| 201 | 96 | 342 | 965 | 150 |
| 630 | 803 | 746 | 422 | 111 |
| 537 | 699 | 497 | 121 | 956 |
| 805 | 732 | 524 | 37 | 331 |

在这个31K的文本文件matrix.txt(右击并选择“目标另存为……”)中包含了一个80乘80的矩阵,求出从该矩阵的左上方到右下方始终只向右和向下移动的最小路径和。


简单的dp。

code

#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int x=0,f=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
   while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
   return x*f;
}
int a[110][110];
int dp[110][110];
int main(){
    freopen("E81.txt","r",stdin);
    int n=80;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=read();
    memset(dp,0x3f,sizeof dp);
    dp[1][1]=a[1][1];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==1&&j==1)continue;
            dp[i][j]=min(dp[i-1][j],dp[i][j-1])+a[i][j];
        }
    }
    cout<<dp[n][n]<<endl;
    return 0;
}


Problem 82

路径和:三个方向

注意:这是第81题的一个更具挑战性的版本。

在如下的5乘5矩阵中,从最左栏任意一格出发,始终只向右、向上或向下移动,到最右栏任意一格结束的最小路径和为994,由标注红色的路径给出。

| | | | | |
| :-: | :-: | :-: | :-: | :-: |
| 131 | 673 | 234 | 103 | 18 |
| 201 | 96 | 342 | 965 | 150 |
| 630 | 803 | 746 | 422 | 111 |
| 537 | 699 | 497 | 121 | 956 |
| 805 | 732 | 524 | 37 | 331 |

在这个31K的文本文件matrix.txt(右击并选择“目标另存为……”)中包含了一个80乘80的矩阵,求出从最左栏到最右栏的最小路径和。


依然dp,但是O(n^3)。

code

#include<bits/stdc++.h>
#define reg register
#define max(a,b) (a>b?a:b)
using namespace std;
inline int read(){
    int x(0),f(1);char ch(getchar());
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch<='9'&&ch>='0')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*f;
}
int a[1005][1005],s[1005][1005];
int f[1005][1005];
signed main(){
    freopen("E81.txt","r",stdin);
    int n,m;
    n=80,m=80;
    for(reg int i(1);i<=n;++i)
        for(reg int j(1);j<=m;++j){
            a[j][i]=read();
        }
    n^=m^=n^=m;
    for(reg int i(1);i<=n;++i)
        for(reg int j(1);j<=m;++j)
            s[i][j]=s[i][j-1]+a[i][j];
    for(reg int i(0);i<=n+1;++i)
        for(reg int j(0);j<=n+1;++j)
            f[i][j]=1e9;
    for(reg int i(1);i<=m;++i)
        f[1][i]=a[1][i];
    for(reg int i(2);i<=n;++i)
        for(reg int j(1);j<=m;++j)
            for(reg int k(1);k<=m;++k)
                f[i][j]=min(f[i][j],f[i-1][k]+(k>j?s[i][k]-s[i][j-1]:s[i][j]-s[i][k-1]));
    int ans=0x3f3f3f3f;
    for(int i=1;i<=m;i++){
        ans=min(ans,f[n][i]);
    }
    printf("%lld\n",ans);
    return 0;
}


Problem 83

路径和:四个方向

注意:这是第81题的一个极具挑战性的版本。

在如下的5乘5矩阵中,从左上角到右下角任意地向上、向下、向左或向右移动的最小路径和为2297,由标注红色的路径给出。

| | | | | |
| :-: | :-: | :-: | :-: | :-: |
| 131 | 673 | 234 | 103 | 18 |
| 201 | 96 | 342 | 965 | 150 |
| 630 | 803 | 746 | 422 | 111 |
| 537 | 699 | 497 | 121 | 956 |
| 805 | 732 | 524 | 37 | 331 |

在这个31K的文本文件matrix.txt(右击并选择“目标另存为……”)中包含了一个80乘80的矩阵,求出从左上角到右下角任意地向上、向下、向左或向右移动的最小路径和。


发现四个方向都可以走,不太方便dp,于是考虑是在点权非负的图上跑最短路,于是spfa即可。

code

#include<bits/stdc++.h>
#define NN 80
#define id(x,y) ((x-1)*NN+y)
using namespace std;
const int N=1e5+10;
const int M=1e5+10;
int in[N],dis[N],vis[N];
int head[M],to[M],val[M],nxt[M],cnt;
void add(int u,int v,int w){
    to[++cnt]=v,val[cnt]=w,nxt[cnt]=head[u],head[u]=cnt;
}
int a[110][110];
void spfa(int s){
    deque<int> q;
    q.push_front(s);
    in[s]=1;vis[s]=1;dis[s]=a[1][1];
    while(!q.empty()){
        int u=q.front();
        in[u]=0;
        q.pop_front();
        for(int i=head[u];i;i=nxt[i]){
            int v=to[i],w=val[i];
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                if(!in[v]){
                    vis[v]++;
                    in[v]=1;
                    q.push_back(v);
                }
            }
        }
    }
}
int main(){
    freopen("E81.txt","r",stdin);
    memset(dis,0x3f,sizeof dis);
    int n=80,m,s;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
        }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i!=1)add(id(i,j),id(i-1,j),a[i-1][j]),add(id(i-1,j),id(i,j),a[i][j]);
            if(i!=n)add(id(i,j),id(i+1,j),a[i+1][j]),add(id(i+1,j),id(i,j),a[i][j]);
            if(j!=1)add(id(i,j),id(i,j-1),a[i][j-1]),add(id(i,j-1),id(i,j),a[i][j]);
            if(j!=n)add(id(i,j),id(i,j+1),a[i][j+1]),add(id(i,j+1),id(i,j),a[i][j]);
        }
    }
    n=n*n;
    spfa(1);
    cout<<dis[n]<<endl;
    return 0;
}


Problem 84

大富翁几率

大富翁游戏的标准棋盘大致如下图所示:

玩家从标记有“GO”的方格出发,掷两个六面的骰子并将点数和相加,作为本轮他们前进的步数。如果没有其它规则,那么落在每一格上的概率应该是2.5%。但是,由于“G2J”(入狱)、“CC”(宝箱卡)和“CH”(机会卡)的存在,这个分布会有所改变。

| | | | | | | | | | | |
| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |
| GO | A1 | CC1 | A2 | T1 | R1 | B1 | CH1 | B2 | B3 | JAIL |
| H2 | | | | | | | | | | C1 |
| T2 | | | | | | | | | | U1 |
| H1 | | | | | | | | | | C2 |
| CH3 | | | | | | | | | | C3 |
| R4 | | | | | | | | | | R2 |
| G3 | | | | | | | | | | D1 |
| CC3 | | | | | | | | | | CC2 |
| G2 | | | | | | | | | | D2 |
| G1 | | | | | | | | | | D3 |
| G2J | F3 | U2 | F2 | F1 | R3 | E3 | E2 | CH2 | E1 | FP |

除了落在“G2J”上,或者在“CC”或“CH”上抽到入狱卡之外,如果玩家连续三次都掷出两个相同的点数,则在第三次时将会直接入狱。

游戏开始时,“CC”和“CH”所需的卡片将被洗牌打乱。当一个玩家落在“CC”或“CH”上时,他们从宝箱卡和机会卡的牌堆最上方取一张卡并遵循指令行事,并将该卡再放回牌堆的最下方。宝箱卡和机会卡都各有16张,但我们只关心会影响到移动的卡片,其它的卡片我们都将无视它们的效果。

  • 宝箱卡 (2/16 张卡):

    • 回到起点“GO”
    • 进入监狱“JAIL”
  • 机会卡 (10/16 张卡):

    • 回到起点“GO”
    • 进入监狱“JAIL”
    • 移动到“C1”
    • 移动到“E3”
    • 移动到“H2”
    • 移动到“R1”
    • 移动到下一个“R”(铁路公司)
    • 移动到下一个“R”
    • 移动到下一个“U”(公共服务公司)
    • 后退三步

这道题主要考察掷出骰子后停在某个特定方格上的概率。显然,除了停在“G2J”上的可能性为0之外,停在“CH”格的可能性最小,因为有5/8的情况下玩家会移动到另一格。我们不区分是被送进监狱还是恰好落在监狱“JAIL”这一格,而且不考虑需要掷出两个相同的点数才能出狱的要求,而是假定进入监狱的第二轮就会自动出狱。

从起点“GO”出发,并将方格依次标记00到39,我们可以将这些两位数连接起来表示方格的序列。

统计学上来说,三个最有可能停下的方格分别是“JAIL”(6.24%)或方格10,E3(3.18%)或方格24以及“GO”(3.09%)或方格00。这三个方格可以用一个六位数字串表示:102400。

如果我们不用两个六面的骰子而是用两个四面的骰子,求出三个最有可能停下的方格构成的数字串。


模拟一下计算概率即可。

大模拟,注意细节即可。

code

#include<bits/stdc++.h>
using namespace std;
queue<int> cc,ch;
set<int> R,U,CC,CH;
int ts(int k){
    if(R.count(k))return 1;
    if(U.count(k))return 2;
    if(CH.count(k))return 3;
    if(CC.count(k))return 4;
    return 0;
}
int get_cc(int x){
    int k=cc.front();
    cc.pop();cc.push(k); 
    if(k==0)return 0;
    if(k==1)return 10;
    return x;
}
int get_ch(int x){
    int k=ch.front();
    ch.pop();ch.push(k);
    if(k>=10)return x;
    switch(k){
        case 0:return 0;//GO
        case 1:return 10;//JAIL
        case 2:return 11;//C1
        case 3:return 24;//E3
        case 4:return 38;//H2
        case 5:return 5;//R1
        case 6:{while(ts(x)!=1)(x+=41)%=40;return x;}
        case 7:{while(ts(x)!=1)(x+=41)%=40;return x;}
        case 8:{while(ts(x)!=2)(x+=41)%=40;return x;}
        case 9:return (x-3+40)%40;
    }
}
void init(){
    int a[20];
    for(int i=1;i<=16;i++)
        a[i]=i-1;
    random_shuffle(a+1,a+17);
    for(int i=1;i<=16;i++)
        cc.push(a[i]);
    random_shuffle(a+1,a+17);
    for(int i=1;i<=16;i++)
        ch.push(a[i]);
    R.insert(5),R.insert(15),R.insert(25),R.insert(35);
    U.insert(12),U.insert(28);
    CH.insert(6),CH.insert(22),CH.insert(36);
    CC.insert(2),CC.insert(17),CC.insert(33);
}
void get(int &x){
    if(x==30)x=10;
    if(ts(x)==3)x=get_ch(x);
    if(ts(x)==4)x=get_cc(x);
}
int cnt;
int dice(){
    int a=rand()%4 +1;
    int b=rand()%4 +1;
    if(a==b)cnt++;
    else cnt=0;
    return a+b;
}
const double MAX_T=1;
int g[50],tot;
struct node{
    int id;
    double num;
    bool operator < (const node &x)const{
        return num>x.num;
    }
}result[50];
int main(){
    srand(time(NULL));
    init();
    int now=0;
    while((double)clock()/CLOCKS_PER_SEC<MAX_T){
        now+=dice();
        (now+=40)%=40;
        if(cnt==3)cnt=0,now=10;
        get(now);tot++,g[now]++;
    }
    for(int i=0;i<40;i++){
        result[i]=(node){i,1.0*g[i]/tot};
    }
    sort(result,result+40);
    for(int i=0;i<40;i++){
        printf("%d %.4lf\n",result[i].id,result[i].num);
    } 
    return 0;
}


Problem 85

数长方形

如果数得足够仔细,能看出在一个3乘2的长方形网格中包含有18个不同大小的长方形,如下图所示:

尽管没有一个长方形网格中包含有恰好两百万个长方形,但有许多长方形网格中包含的长方形数目接近两百万,求其中最接近这一数目的长方形网格的面积。


答案很小,所以我们可以对于x*y的长方形网格暴力计算答案,即

$\sum^x_{a=1}\sum^y_{b=1}(x-a+1)(y-b+1)$

然后计算即可。

code

#include<bits/stdc++.h>
using namespace std;
int calc(int x,int y){
    int ans=0;
    for(int a=1;a<=x;a++){
        for(int b=1;b<=y;b++){
            ans+=(x-a+1)*(y-b+1); 
        }
    }
    return ans;
}
int main(){
    int lim=2000000;
    int res=0x3f3f3f3f,id=-1;
    for(int x=1;x<=100;x++){
        for(int y=x;y<=100;y++){
            int k=calc(x,y);
            if(abs(k-lim)<res){
                res=abs(k-lim),id=x*y;
                printf("%d %d %d\n",x,y,k);
            }

        }
    }
    cout<<id<<endl;
    return 0;
}

Problem 86

长方体路径

蜘蛛S位于一个6乘5乘3大小的长方体屋子的一角,而苍蝇F则恰好位于其对角。沿着屋子的表面,从S到F的最短“直线”距离是10,路径如下图所示:

然而,对于任意长方体,“最短”路径实际上一共有三种可能;而且,最短路径的长度也并不一定为整数。

当M=100时,若不考虑旋转,所有长、宽、高均不超过M且为整数的长方体中,对角的最短距离是整数的恰好有2060个;这是使得该数目超过两千的最小M值;当M=99时,该数目为1975。

找出使得该数目超过一百万的最小M值。


转化题意,这个数目就等同于找到三元组(a,b,c),a,b,c<=m,使得a<=c,b<=c且$(a+b)^2+c^2$是一个完全平方数的数量。

于是我们考虑枚举a+b,记为s,发现s的范围在[1,2m]中,然后去寻找对应的c,我们固定c为m,再枚举m即可。

这样能不重不漏的枚举a+b,也能不重不漏的枚举c,所以肯定是能找完的。

code

#include<bits/stdc++.h>
using namespace std;
int main(){
    int m=1,cnt=0;
    while(cnt<1000000&&(++m)){
        for(int s=2,b=s*s+m*m;s<=2*m;s++,b=s*s+m*m){
            int t=int(sqrt(b));
            if (t*t==b)cnt+=(s>=m)?(m-(s+1)/2)+1:s/2;
        }
    }
    cout<<m<<endl;
    return 0;
}


Problem 87

素数幂三元组

最小的可以表示为一个素数的平方,加上一个素数的立方,再加上一个素数的四次方的数是28。实际上,在小于50的数中,一共有4个数满足这一性质:

28 = 2^2 + 2^3 + 2^4
33 = 3^2 + 2^3 + 2^4
49 = 5^2 + 2^3 + 2^4
47 = 2^2 + 3^3 + 2^4

有多少个小于五千万的数,可以表示为一个素数的平方,加上一个素数的立方,再加上一个素数的四次方?


暴力枚举即可。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100010;
int st[N],pr[N],cnt;
void prime(int n=N-10){
    for(int i=2;i<=n;i++){
        if(!st[i])st[i]=2,pr[++cnt]=i;
        for(int j=1;j<=cnt&&pr[j]*i<=n;j++){
            st[pr[j]*i]=1;
            if(i%pr[j]==0)break;
        }
    }
}
bool res[50000010];
signed main(){
    prime();
    int n=50000000;
    int a,b,c;
    for(int i=1;i<=cnt;i++){if(pr[i]*pr[i]>n){a=i-1;break;}}
    for(int i=1;i<=cnt;i++){if(pr[i]*pr[i]*pr[i]>n){b=i-1;break;}}
    for(int i=1;i<=cnt;i++){if(pr[i]*pr[i]*pr[i]*pr[i]>n){c=i-1;break;}}
    int ans=0;
    for(int i=1;i<=a;i++){
        int now=pr[i]*pr[i];
        for(int j=1;j<=b;j++){
            int now2=now+(pr[j]*pr[j]*pr[j]);
            if(now2>n)break;
            for(int k=1;k<=c;k++){
                int now3=now2+(pr[k]*pr[k]*pr[k]*pr[k]);
                if(now3<=n){
                    if(!res[now3])res[now3]=1,ans++;
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}


Problem 88

积和数

若自然数N能够同时表示成一组至少两个自然数{a1, a2, … , ak}的积和和,也即N = a1 + a2 + … + ak = a1 × a2 × … × ak,则N被称为积和数。

例如,6是积和数,因为6 = 1 + 2 + 3 = 1 × 2 × 3。

给定集合的规模k,我们称满足上述性质的最小N值为最小积和数。当k = 2、3、4、5、6时,最小积和数如下所示:

k=2: 4 = 2 × 2 = 2 + 2
k=3: 6 = 1 × 2 × 3 = 1 + 2 + 3
k=4: 8 = 1 × 1 × 2 × 4 = 1 + 1 + 2 + 4
k=5: 8 = 1 × 1 × 2 × 2 × 2 = 1 + 1 + 2 + 2 + 2
k=6: 12 = 1 × 1 × 1 × 1 × 2 × 6 = 1 + 1 + 1 + 1 + 2 + 6

因此,对于2≤k≤6,所有的最小积和数的和为4+6+8+12 = 30;注意8只被计算了一次。

已知对于2≤k≤12,所有最小积和数构成的集合是{4, 6, 8, 12, 15, 16},这些数的和是61。

对于2≤k≤12000,所有最小积和数的和是多少?


发现数据小,爆搜即可。

code

#include<bits/stdc++.h>
#define reg register
using namespace std;
inline bool check(reg int x,reg int y,reg int d){
    if(y<d)return false;
    if(x==1)return y==d;
    if(d==1)return x==y;
    for(reg int i=1;i*i<=x;i++)
        if(x%i==0){
            if(i!=1&&check(x/i,y-i,d-1))return 1;
            if(check(i,y-x/i,d-1))return 1;
        }
    return 0;
}
inline int get(reg int n){
    for(reg int i=n+1;;i++)
        if(check(i,i,n))return i;
}
bool vis[100010];
signed main(){
    int n=12000,ans=0;
    for(reg int i=2;i<=n;i++){
        int k=get(i);
        if(vis[k])continue;
        vis[k]=1,ans+=k;
    }
    printf("%d\n",ans);
    return 0;
}


Problem 89

罗马数字

要正确地用罗马数字表达一个数,必须遵循一些基本规则。尽管符合规则的写法有时会多于一种,但对每个数来说总是存在一种“最好的”写法。

例如,数16就至少有六种写法:

IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI

然而,根据规则,只有XIIIIII和XVI是合理的写法,而后一种因为使用了最少的数字而被认为是最有效的写法。

在这个11K的文本文件roman.txt (右击并选择“目标另存为……”)中包含了一千个合理的罗马数字写法,但并不都是最有效的写法;有关罗马数字的明确规则,可以参考关于罗马数字

求出将这些数都写成最有效的写法所节省的字符数。

注意:你可以假定文件中的所有罗马数字写法都不包含连续超过四个相同字符。


根据提示,发现可以被替换的只有:

"DCCCC","LXXXX","VIIII","IIII","XXXX","CCCC"。

然后就可以了。

code

#include<bits/stdc++.h>
using namespace std;
string ss="AA";
string f[6]={"DCCCC","LXXXX","VIIII","IIII","XXXX","CCCC"};
int main(){
    freopen("E89.txt","r",stdin);
    string s;
    int ans=0;
    while(cin>>s){
        if(s=="P")break;
        int a=s.size();
        for(int i=0;i<6;i++){
            int p=s.find(f[i]);
            while(p!=-1){
                s.replace(p,f[i].size(),ss);
                p=s.find(f[i]);
            }
        }
        ans+=a-s.size();
    }
    cout<<ans<<endl;
    return 0;
}

Problem 90

立方体数字对

在一个立方体的六个面上分别标上不同的数字(从0到9),对另一个立方体也如法炮制。将这两个立方体按不同的方向并排摆放,我们可以得到各种各样的两位数。

例如,平方数64可以通过这样摆放获得:

事实上,通过仔细地选择两个立方体上的数字,我们可以摆放出所有小于100的平方数:01、04、09、16、25、36、49、64和81。

例如,其中一种方式就是在一个立方体上标上{0, 5, 6, 7, 8, 9},在另一个立方体上标上{1, 2, 3, 4, 8, 9}。

在这个问题中,我们允许将标有6或9的面颠倒过来互相表示,只有这样,如{0, 5, 6, 7, 8, 9}和{1, 2, 3, 4, 6, 7}这样本来无法表示09的标法,才能够摆放出全部九个平方数。

在考虑什么是不同的标法时,我们关注的是立方体上有哪些数字,而不关心它们的顺序。

{1, 2, 3, 4, 5, 6}等价于{3, 6, 4, 1, 2, 5}
{1, 2, 3, 4, 5, 6}不同于{1, 2, 3, 4, 5, 9}

但因为我们允许在摆放两位数时将6和9颠倒过来互相表示,这个例子中的两个不同的集合都可以代表拓展集{1, 2, 3, 4, 5, 6, 9}。

对这两个立方体有多少中不同的标法可以摆放出所有的平方数?


爆搜即可。

code

#include<bits/stdc++.h>
#include<windows.h>
using namespace std;
bool a[10],b[10];
int p[10][2]={0,0,0,1,0,4,0,9,1,6,2,5,3,6,4,9,6,4,8,1};
int ans;
void dfs(int dep,int pre,int op){
//    printf("%d %d %d\n",dep,pre,op);
    if(dep==7){
        if(op==0){
            dfs(1,0,1);
        }
        int f=1;
        for(int i=1;i<=9;i++){
            if((a[p[i][0]]&&b[p[i][1]])||(b[p[i][0]]&&a[p[i][1]]))continue;
            else f=0;
        }
        if(!f)return;
        ans++;
        return;
    }
    for(int i=pre;i<10;i++){
        if(op==0)a[i]=1;
        else b[i]=1;
        if(i==6){
            if(op==0)a[9]=1;
            else b[9]=1;
        }
        if(i==9){
            if(op==0)a[6]=1;
            else b[6]=1;
        }
        dfs(dep+1,i+1,op);
        if(op==0)a[i]=0;
        else b[i]=0;
        if(i==6){
            if(op==0)a[9]=0;
            else b[9]=0;
        }
        if(i==9){
            if(op==0)a[6]=0;
            else b[6]=0;
        }
    }
}
int main(){
    dfs(1,0,0);
    cout<<ans/2<<endl;
    return 0;
}


Problem 91

格点直角三角形

点P(x1, y1)和点Q(x2, y2)都是格点,并与原点O(0,0)构成ΔOPQ。

当点P和点Q的所有坐标都在0到2之间,也就是说0 ≤ x1, y1, x2, y2 ≤ 2时,恰好能构造出14个直角三角形。

如果0 ≤ x1, y1, x2, y2 ≤ 50,能构造出多少个直角三角形?


n^4暴力枚举即可。

code

#include<bits/stdc++.h>
using namespace std;
bool vis[51][51][51][51];
int main(){
    int n=50;
    int ans=0;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            for(int x=0;x<=n;x++)
                for(int y=0;y<=n;y++){
                    if(i==0&&j==0||x==0&&y==0||i==x&&j==y||x==0&&i==0||y==0&&j==0)continue;
                    if(vis[i][j][x][y]||vis[x][y][i][j])continue;
                    int a=i*i+j*j,b=x*x+y*y,c=(i-x)*(i-x)+(j-y)*(j-y);
                    if(a+b==c||a+c==b||b+c==a);
                    else continue;
                    ans++/*,printf("(%d,%d) (%d,%d) (%d,%d)\n",0,0,i,j,x,y)*/;
                    vis[i][j][x][y]=vis[x][y][i][j]=1;
                }
    cout<<ans<<endl;
    return 0;
}


Problem 92

平方数字链

将一个数的所有数字的平方相加得到一个新的数,不断重复直到新的数已经出现过为止,这构成了一条数字链。

例如,

44 → 32 → 13 → 10 → 11
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

可见,任何一个到达1或89的数字链都会陷入无尽的循环。更令人惊奇的是,从任意数开始,最终都会到达1或89。

有多少个小于一千万的数最终会到达89?


记忆化搜索即可。

code

#include<bits/stdc++.h>
using namespace std;
int res[10000010];
int p[11];
int get(int x){
    int s(0);
    while(x)s+=p[x%10],x/=10;
    return s;
}
bool check(int x){
    if(x==1)return 0;
    if(x==89)return 1;
    if(res[x])return res[x]==1;
    res[x]=check(get(x))?1:-1;
    return res[x]==1;
}
int main(){
    for(int i=1;i<=9;i++)
        p[i]=i*i;
    int ans=0;
    for(int i=2;i<=10000000;i++){
        if(check(i))ans++;
    }
    cout<<ans<<endl;
    return 0;
}

Problem 93

算术表达式

使用集合{1, 2, 3, 4}中每个数字恰好一次以及(+, −, *, /)四则运算和括号,可以得到不同的正整数。

例如,

8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) − 1
36 = 3 4 (2 + 1)

注意不允许直接把数字连起来,如12 + 34。

使用集合{1, 2, 3, 4},可以得到31个不同的数,其中最大值是36,以及1到28之间所有的数。

若使用包含有四个不同数字a < b < c < d的集合可以得到从1到n之间所有的数,求其中使得n最大的集合,并将你的答案写成字符串:abcd。


搜索题,考虑枚举选择0-9里的四个数字,再枚举这个全排列,对于每个排列枚举符号,因为有除法,所以我们记录分子分母,过程中约分。

这样跑出来的结果最开始出了问题,问题在于集合{1,2,5,8}不能组合出36。

手算一波发现36=(-1/2 +5)*8,问题就出在这个刚开始的负号上,于是我们就初始符号两个都传入即可。

code

#include<bits/stdc++.h>
using namespace std;
int s[110];
bool vis[1010];
void calc(int dep,int fz,int fm){
    int g=__gcd(fz,fm);
    fz/=g,fm/=g;
    if(dep==5){
        if(fm==1&&fz>0){
            if(!vis[fz])vis[fz]=1;
        }
        return;
    }
    calc(dep+1,fz+fm*s[dep],fm);
    calc(dep+1,fz-fm*s[dep],fm);
    calc(dep+1,fz*s[dep],fm);
    if(s[dep])calc(dep+1,fz,fm*s[dep]);
}
int res=0;
void dfs(int dep,int pre){
    if(dep==5){
        memset(vis,0,sizeof vis);
        do{
            calc(2,s[1],1);
            calc(2,-s[1],1);
        }while(next_permutation(s+1,s+5));
        int i=1;
        while(vis[i])i++;
        i--;
        if(i>res){
            printf("%d%d%d%d\n",s[1],s[2],s[3],s[4]);
            res=i;
            printf("%d\n",res);
        }
        return;
    }
    for(int i=pre;i<=9;i++){
        s[dep]=i;
        dfs(dep+1,i);
        s[dep]=0;
    }
} 
int main(){
    dfs(1,0);
    return 0;
}


Problem 94

几乎等边的三角形

可以证明,不存在边长为整数的等边三角形其面积也是整数。但是,存在几乎等边的三角形 5-5-6,其面积恰好为12。

我们定义几乎等边的三角形是有两条边一样长,且第三边与这两边最多相差1的三角形。

对于所有边长和面积均为整数且周长不超过十亿(1,000,000,000)的三角形,求其中几乎等边的三角形的周长之和。


考虑什么样的“几乎等边的三角形”才能使得面积整数。

我们发现,只有这个高h是整数的时候,我们才能说这是一个面积为整数的三角形, 因为底边a+1/a-1是整数。

所以问题就变成了使得高h是整数。

考虑勾股定理,给分割出来的直角三角形的斜边设为C,底边($\frac{a±1}{2}$)设为A,高h设为B,显然有$A^2+B^2=C^2$。

那么这就要求A是整数,所以a必定是奇数,到这一步就可以想到暴力枚举奇数,但是会爆longlong。

考虑如何优化,我们有$A*2==C+1$或者$A*2==C-1$,所以筛一筛本原勾股数组就可以了。(方法详见Problem75)

code

#include<bits/stdc++.h>
#define reg register
#define min(a,b) (a<b?a:b)
#define int long long
using namespace std;
signed main(){
    int n=333333333;
    int e=sqrt(n);
    int ans=0;
    for(int t=1;t<=e;t+=2){
        for(int s=t+2;s<=e&&s*t<=n;s+=2){
            if(__gcd(s,t)!=1)continue;
            reg int a=s*t;
            reg int b=s*s-t*t;b>>=1;
            reg int C=s*s+t*t;C>>=1;
            reg int A=min(a,b);
            if((A!=(C+1>>1))&&(A!=(C-1>>1)))continue;
            printf("%lld %lld %lld\n",C,C,A<<1);
            ans+=(A+C<<1);
        }
    }
    cout<<ans<<endl;
    return 0;
}

Problem 95

亲和数链

一个数除了本身之外的因数称为真因数。例如,28的真因数是1、2、4、7和14。这些真因数的和恰好为28,因此我们称28是完全数。

有趣的是,220的真因数之和是284,同时284的真因数之和是220,构成了一个长度为2的链,我们也称之为亲和数对。

有一些更长的序列并不太为人所知。例如,从12496出发,可以构成一个长度为5的链:

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → ...)由于这条链最后又回到了起点,我们称之为亲和数链。

找出所有元素都不超过一百万的亲和数链中最长的那条,并给出其中最小的那个数。


搜索即可。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int st[N],pr[N],cnt;
int d[N],g[N];
void prime(int n=N-10){
    g[1]=d[1]=1;
    for(int i=2;i<=n;i++){
        if(!st[i]){
            st[i]=2;
            pr[++cnt]=i;
            d[i]=i+1;
            g[i]=i+1; 
        }
        for(int j=1;j<=cnt&&pr[j]*i<=n;j++){
            st[pr[j]*i]=1;
            if(i%pr[j]==0){
                g[pr[j]*i]=g[i]*pr[j]+1;
                d[pr[j]*i]=d[i]/g[i]*g[i*pr[j]];
                break;
            }
            d[pr[j]*i]=d[i]*d[pr[j]];
            g[pr[j]*i]=pr[j]+1;
        }
    }
    for(int i=1;i<=n;i++)
        d[i]-=i;
}
int ans=0,res=0;
int vis[N],b;
void get(int x){
    int cnt=0;
    int mn=x;
    while(1){
        mn=min(mn,x);
        x=d[x];
        if(x==b)break;
        if(x>N-10)return;
        if(vis[x]==b)return;
        vis[x]=b,cnt++;
    }
    if(cnt>res)res=cnt,ans=mn;
}
int main(){
    prime();
    for(int i=1;i<=1000000;i++){
        b=i;
        get(i);
    }
    cout<<res<<endl;
    cout<<ans<<endl;
    return 0;
}

Problem 96

数独

数独(日语原意为数的位置)是一种热门的谜题。它的起源已不可考,但是与欧拉发明的一种类似而更加困难的谜题拉丁方阵之间有着千丝万缕的联系。数独的目标是替换掉9乘9网格中的空白位置(或0),使得每行、每列以及每个九宫格中恰好都包含数字1~9。如下是一个典型的数独谜题以及它的解答。

| | | | | | | |
| :-: | :-: | :-: | :-: | :-: | :-: | :-: |
| 0 0 3 | 0 2 0 | 6 0 0 | * | 4 8 3 | 9 6 7 | 2 5 1 |
| 9 0 0 | 3 0 5 | 0 0 1 | * | 9 2 1 | 3 4 5 | 8 7 6 |
| 0 0 1 | 8 0 6 | 4 0 0 | * | 6 5 7 | 8 2 1 | 4 9 3 |
| | | | | | | |
| 0 0 8 | 1 0 2 | 9 0 0 | * | 5 4 8 | 7 2 9 | 1 3 6 |
| 7 0 0 | 0 0 0 | 0 0 8 | * | 1 3 2 | 5 6 4 | 7 9 8 |
| 0 0 6 | 7 0 8 | 2 0 0 | * | 9 7 6 | 1 3 8 | 2 4 5 |
| | | | | | | |
| 0 0 2 | 6 0 9 | 5 0 0 | * | 3 7 2 | 8 1 4 | 6 9 5 |
| 8 0 0 | 2 0 3 | 0 0 9 | * | 6 8 9 | 2 5 3 | 4 1 7 |
| 0 0 5 | 0 1 0 | 3 0 0 | * | 5 1 4 | 7 6 9 | 3 8 2 |

一个构造精良的数独谜题应该包含有唯一解,且能够通过逻辑推断来解决,尽管有时可能必须通过“猜测并检验”来排除一些选项(这一要求目前还颇受争议)。寻找答案的复杂度决定了题目的难度;上面这个谜题被认为是简单的谜题,因为我们可以通过直截了当的演绎推理来解决它。

在这个6K的文本文件sudoku.txt(右击并选择“目标另存为……”)中包含有50个不同难度的数独谜题,但保证它们都只有唯一解(文件中的第一个谜题就是上述样例)。

解开这50个谜题,找出每个谜题解答左上角的三个数字并连接起来,给出这些数的和;举例来说,上述样例解答左上角的三个数字连接起来构成的数是483。


傻逼题,描述说唯一解,样例我就跑出来了个不同的解。

傻逼翻译搞错了。

case #1:
 4  8 [3] 9 [2] 1 [6] 5  7
[9] 6  7 [3] 4 [5] 8  2 [1]
 2  5 [1][8] 7 [6][4] 9  3
 5  4 [8][1] 3 [2][9] 7  6
[7] 2  9  5  6  4  1  3 [8]
 1  3 [6][7] 9 [8][2] 4  5
 3  7 [2][6] 8 [9][5] 1  4
[8] 1  4 [2] 5 [3] 7  6 [9]
 6  9 [5] 4 [1] 7 [3] 8  2

于是爆搜就可以了。

code

#include<bits/stdc++.h>
#define id(x,y) ((y-1)/3+1+(x-1)/3*3)
using namespace std;
char mp[20][20];
int m[20][20];
int v[20][20];//0待用 1已用 2禁用
int ans=0;
void dfs(){
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
            if(m[i][j])continue;
            for(int k=1;k<=9;k++){//欲在m[i][j]放k 
                if(v[id(i,j)][k])continue;
                int f=0;
                for(int I=1;I<=9;I++)
                    if(m[I][j]==k){
                        f=1;
                        break;
                    }
                for(int J=1;J<=9;J++)
                    if(m[i][J]==k){
                        f=1;
                        break;
                    }
                if(f)continue;
                m[i][j]=k;
                v[id(i,j)][k]=1;
                dfs();
                m[i][j]=0;
                v[id(i,j)][k]=0;
            }
            if(!m[i][j])return;
        }
    }
//    puts("");
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
            if(v[id(i,j)][m[i][j]]==1)printf(" %d ",m[i][j]);
            else printf("[%d]",m[i][j]);
        }
        puts("");
    }
    ans+=m[1][1]*100+m[1][2]*10+m[1][3];
//    exit(0);
} 
int main(){
    freopen("E96.txt","r",stdin);
    for(int cc=1;cc<=50;cc++){
        int fff=2;
        while(fff){
            char ch=getchar();
            if(ch<='9'&&ch>='0')fff--;
        }
        memset(v,0,sizeof v);
        memset(m,0,sizeof m); 
        memset(mp,0,sizeof mp);
        for(int i=1;i<=81;i++){
            char ch=getchar();
            while(ch>'9'||ch<'0')ch=getchar();
//            printf("%d -> (%d,%d) ",i,(i-1)/9+1,(i%9==0)?9:i%9);cout<<ch<<endl;
            mp[(i-1)/9+1][(i%9==0)?9:i%9]=ch;
        }
        printf("case #%d:\n",cc);
        for(int i=1;i<=9;i++)
            for(int j=1;j<=9;j++)
                v[i][j]=0,m[i][j]=max(0,mp[i][j]-'0');
        for(int i=1;i<=9;i++)
            for(int j=1;j<=9;j++)
                if(m[i][j])v[id(i,j)][m[i][j]]=2;
        dfs();
        cout<<ans<<endl;
    }
    printf("%d\n",ans);
    return 0;
}

Problem 97

非梅森大素数

1999年人们发现了第一个超过一百万位的素数,这是一个梅森素数,可以表示为2^6972593−1,包含有2,098,960位数字。在此之后,更多形如2p−1的梅森素数被发现,其位数也越来越多。

然而,在2004年,人们发现了一个巨大的非梅森素数,包含有2,357,207位数字:28433×2^7830457+1。

找出这个素数的最后十位数字。


好久没有遇到这种朴实无华的水题了。

code

#include<bits/stdc++.h>
using namespace std;
struct node{
    int a[1010];//len=10
    void csh(){memset(a,0,sizeof a);}
    int &operator [] (int x){return a[x];}
    int operator[] (int x)const{return a[x];}
    node operator * (const node &x){
        node s;s.csh();
        for(int i=1;i<=10;i++)
            for(int j=1;j<=10;j++)
                s[i+j-1]+=a[i]*x[j];
        for(int i=1;i<=10;i++)
            s[i+1]+=s[i]/10,s[i]%=10;
        return s; 
    }
    node operator = (const int &x){
        int i=0,tmp=x;
        while(tmp)a[++i]=tmp%10,tmp/=10;
    }
    node operator = (const node &x){
        memcpy(a,x.a,sizeof a);
    }
    void print(){
        for(int i=10;i>=1;i--)
            printf("%d",a[i]);
        puts("");
    }
}a;
node qpow(int b){
    node c;c=2;
    node k;k=1;
    while(b){
        if(b&1)k=k*c;
        c=c*c;
        b>>=1;
    }
    return k;
}
int main(){
    a=28433;
    node c=qpow(7830457);
    a=a*c;
    a[1]++;
    a.print();
    return 0;
}


E98

在鸽了在鸽了


Problem 99

最大的幂

比较两个如211和37这样写成幂的形式的数并不困难,任何计算器都能验证211 = 2048 < 37 = 2187。

然而,想要验证632382518061 > 519432525806就会变得非常困难,因为这两个数都包含有超过三百万位数字。

22K的文本文件base_exp.txt(右击并选择“目标另存为……”)有一千行,每一行有一对底数和指数,找出哪一行给出的幂的值最大。

注意:文件的前两行就是上述两个例子。


显然$a^b$不可计算,考虑如何转化。

于是想到我们有:

$x=a^{log_a(x)}$

$x^y=a^{log_a(x)*y}$

然后就随便以啥为底算就完了。

code

#include<bits/stdc++.h>
using namespace std;
int main(){
    freopen("E99.txt","r",stdin);
    double mx=0;
    int i=0,a,b;
    int ans=-1;
    while(~scanf("%d%d",&a,&b)){
        i++;
        double now=log2(a)*b;
        if(now>mx)mx=now,ans=i;
    }
    printf("%d\n",ans);
    return 0;
}


E100

咕了 佩尔方程 以后补

最后修改:2020 年 11 月 24 日 03 : 29 PM