目前咕掉的题目有:

E67,E100 - 佩尔方程

E98 - 暂时没想到比较优的做法


Problem 101

最优多项式

如果我们知道了一个数列的前k项,我们仍无法确定地给出下一项的值,因为有无穷个多项式生成函数都有可能是这个数列的模型。

例如,让我们考虑立方数的序列,它可以用如下函数生成,
un = n3: 1, 8, 27, 64, 125, 216, …

如果我们只知道数列的前两项,秉承“简单至上”的原则,我们应当假定这个数列遵循线性关系,并且预测下一项为15(公差为7)。即使我们知道了数列的前三项,根据同样的原则,我们也应当首先假定数列遵循二次函数关系。

给定数列的前k项,定义OP(k, n)是由最优多项式生成函数给出的第n项的值。显然OP(k, n)可以精确地给出n ≤ k的那些项,而可能的第一个不正确项(First Incorrect Term,简记为FIT)将会是OP(k, k+1);如果事实的确如此,我们称这个多项式为坏最优多项式(Bad OP,简记为BOP)。

在最基本的情况下,如果我们只得到了数列的第一项,我们应当假定数列为常数,也就是说,对于n ≥ 2,OP(1, n) = u1。

由此,我们得到了立方数列的最优多项式如下:

| | |
| - | - |
| OP(1, n) = 1 | 1,1, 1, 1, … |
| OP(2, n) = 7n−6 | 1, 8,15, … |
| OP(3, n) = 6n2−11n+6 | 1, 8, 27,58, … |
| OP(4, n) = n3 | 1, 8, 27, 64, 125, … |

显然,当k ≥ 4时不存在坏最优多项式。

所有坏最优多项式的第一个不正确项(用红色标示的数)之和为1 + 15 + 58 = 74。

考虑下面这个十阶多项式生成函数:

$u_n = 1 − n + n^2 − n^3 + n^4 − n^5 + n^6 − n^7 + n^8 − n^9 + n^{10}$求其所有坏最优多项式的第一个不正确项之和。


毒瘤多项式终于来了。

第一个认识的多项式知识点:拉格朗日插值法。

问题:假如我们已知$n$个点$(x_i,y_i)$,我们希望构造出一个$n+1$次多项式经过这$n$个点,并且要求出一个$k$所对应的函数值。

最朴素的想法是利用待定系数法,列出方程$O(n^3)$高斯消元求解,但是太慢了,并且容易丢精,所以考虑更珂学的方法。

考虑对于这$n$个点分别构造$n$个函数$f_i(x)$,它们满足$f_i(x_i)=y_i,f_i(x_j)=0,\forall j≠i$。

这样的函数显然是很好构造的,就是$f_i(x)=y_i*\prod_{j≠i}\frac{x-x_j}{x_i-x_j}$,这样当$x=x_i$时,后面这一坨的值才为1,整个的值为$y_i$,否则值就是0,整个的值是0。

那么构造出这些函数之后,其他函数值就很好表示了,就是$f(x)=\sum_{i=1}^{n}y_i*\prod_{j≠i}\frac{x-x_j}{x_i-x_j}$。

显然这一坨可以$O(n^2)$求出,并且比写高斯消元要舒服。

于是这道题目就解决了。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int qpow(int a,int b){
    int x=1;
    while(b--)x*=a;
    return x;
}
int calc(int n){
    int res=0;
    for(int i=0;i<=10;i++)
        res+=qpow(-1,i+2)*qpow(n,i);
    return res;
}
// int calc(int n){
//     return n*n*n;
// }
int a[110];
int n=10;
int ans=0;
int lagrange(int k){
    int res=0;
    for(int i=0;i<k;i++){
        int fz=a[i],fm=1;
        for(int j=0;j<k;j++){
            if(i==j)continue;
            fz*=(k-j);
            fm*=(i-j);
        }
        // printf("%d %d\n",fz,fm);
        res+=fz/fm;
    }
    ans+=res;
    return res;
}
signed main(){
    for(int i=1;i<=n;i++)
        a[i-1]=calc(i),printf("%lld\n",calc(i));
    puts("");
    for(int i=1;i<=n;i++)
        printf("%lld\n",lagrange(i));
    printf("ans:%lld\n",ans);
    return 0;
}


Problem 102

包含原点的三角形

从笛卡尔平面中随机选择三个不同的点,其坐标均满足-1000 ≤ x, y ≤ 1000,这三个点构成一个三角形。

考虑下面两个三角形:

A(-340,495), B(-153,-910), C(835,-947)

X(-175,41), Y(-421,-714), Z(574,-645)

可以验证三角形ABC包含原点,而三角形XYZ不包含原点。

在27K的文本文件triangles.txt(右击并选择“目标另存为……”)中包含了一千个“随机”三角形的坐标,找出其中包含原点在其内部的三角形的数量。

注意:文件中的前两个三角形就是上述样例。


考虑一个非常简单的想法。

如果原点在这个三角形内,那么这个三角形会被拆成原点和另外任意两个顶点组成的三个三角形,或者说这样组成的三个三角形的面积和等于原来的三角形。

于是我们就暴力地拆开计算求和,再和原来的面积比较一下即可,eps选大一点,因为这个偏差可能会比较大。

然后就过了。

什么?你说不知道怎么计算面积?暴力计算三边长再带入海伦-秦九韶公式就可以了。

code

#include<bits/stdc++.h>
#define E(x) ((x)*(x))
using namespace std;
const double eps=0.1;
double calc(double x1,double y1,double x2,double y2,double x3,double y3){
    double a=sqrt(E(x1-x2)+E(y1-y2));
    double b=sqrt(E(x1-x3)+E(y1-y3));
    double c=sqrt(E(x2-x3)+E(y2-y3));
    double k=(a+b+c)*0.5;
    return sqrt(k*(k-a)*(k-b)*(k-c));
}
int main(){
    freopen("E102.txt","r",stdin);
    int ans=0; 
    double x1,y1,x2,y2,x3,y3;
    while(cin>>x1>>y1>>x2>>y2>>x3>>y3){
        double a=calc(x1,y1,x2,y2,x3,y3);
        double b=calc(0,0,x1,y1,x2,y2)+calc(0,0,x2,y2,x3,y3)+calc(0,0,x1,y1,x3,y3);
        if(fabs(a-b)<eps)ans++;
    }
    cout<<ans<<endl;
    return 0;
}


Problem 103

特殊的子集和:最优解

记S(A)是大小为n的集合A中所有元素的和。若任取A的任意两个非空且不相交的子集B和C都满足下列条件,我们称A是一个特殊的和集:

  1. S(B)≠S(C);也就是说,任意子集的和不相同。
  2. 如果B中的元素比C多,则S(B)>S(C)。

对于给定的n,我们称使得S(A)最小的集合A为最优特殊和集。前5个最优特殊和集如下所示。

n=1:{1}n=2:{1,2}n=3:{2,3,4}n=4:{3,5,6,7}n=5:{6,9,11,12,13}

似乎对于一个给定的最优特殊和集A={a1,a2,…,an},下一个最优特殊和集将是B={b,a1+b,a2+b,…,an+b}的形式,其中b是集合A“正中间”的元素。

应用这条“规则”,我们猜测对于n=6的最优特殊和集将是A={11,17,20,22,23,24},相应的S(A)=117。然而,事实并非如此,我们的方法仅仅只能找出近似最优特殊和集。对于n=6,最优特殊和集是A={11,18,19,20,22,25},相应的S(A)=115,对应的集合数字串是:111819202225。

若集合A是n=7时的最优特殊和集,求其对应的集合数字串。

注意:此题和第105题第106题有关。


考虑爆搜,从近似最优特殊和集{19,30,37,38,39,41,44}开始,进行微调并check,搜到底之后输出即可。

最后的最优S为255。

code

#include<bits/stdc++.h>
using namespace std;
int a[]={19,30,37,38,39,41,44};
// int a[]={11,17,20,22,23,24};
int n=7;
int lim=128;
int S(){
    int res=0;
    for(int i=0;i<n;i++)
        res+=a[i];
    return res;
}
bool check2(){
    for(int i=0;i<lim;i++){
        for(int j=0;j<lim;j++){
            if(i&j)continue;
            int s1=0,s2=0;
            int t1=i,t2=j;
            for(int k=0;k<n;k++){
                if(t1&1)s1+=a[k];
                if(t2&1)s2+=a[k];
                t1>>=1,t2>>=1;
            }
            if((i||j)&&s1==s2)return 0;
        }
    }
    return 1;
}
bool check(){

    if(a[0]+a[1]<=a[6])return 0;
    if(a[0]+a[1]+a[2]<=a[5]+a[6])return 0;
    if(a[0]+a[1]+a[2]+a[3]<=a[4]+a[5]+a[6])return 0;
    return 1&&check2();
}
int ans=1000000;
void dfs(int dep){
    if(dep==n){
        if(check()){
            int s=S();
            if(s<ans){
                ans=s;
                for(int i=0;i<n;i++)
                    cout<<a[i]<<" ";
                puts("");
                cout<<s<<endl;
            }
        }
        return;
    }
    dfs(dep+1);
    for(int del=1;del<=3;del++){
        a[dep]+=del;
        if(a[dep]>a[dep-1])dfs(dep+1);
        a[dep]-=del;
        a[dep]-=del;
        if(a[dep]>a[dep-1])dfs(dep+1);
        a[dep]+=del;
    }
}
int main(){
    dfs(0);
    return 0;
}


Problem 104

看到这题便有一个朴素的想法:高精度暴力艹过去。

但是发现高精度太慢了,铁定会T。

于是考虑近似地估计答案,不计算一整个数列。

那么就保留数字前16位(估计),后16位(精确)的值,前后一致只是为了方便,后面其实只需要保留9位即可。

然后就暴力地去加,由于前面的数字有效位只有9位,所以微小的误差是不可能影响答案的。

另外由于我的垃圾策略,所以用高精程序跑出了最开始的包含32位数字的菲波拉契数F151和F152即可。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e16;
const int Mod=1e9;
const int MOD=1e7;
int p[12]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
const int ANS=1111111110;
int cnt=0;
struct node{
    int fst,lst;
    node(){clear();}
    void clear(){fst=0,lst=0;}
    node operator + (const node &x){
        node c;
        c.lst=(lst+x.lst)%mod;
        c.fst=fst+x.fst;
        while(c.fst>mod)c.fst/=10,cnt++;
        return c;
    }
    bool check(){
        int t1=fst,t2=lst;
        t2%=Mod;
        t1/=MOD;
        // cout<<t1<<" "<<t2<<endl;
        int ck1=0,ck2=0;
        //ck1:first 9 digits 
        //ck2:last 9 digits
        for(int i=1;i<=9;i++){
            ck1+=p[t1%10];
            t1/=10;
        }
        for(int i=1;i<=9;i++){
            ck2+=p[t2%10];
            t2/=10;
        }
        // printf("%d %d\n",ck1,ck2);
        return ck1==ANS&&ck2==ANS;
    }
    node operator = (const node &x){
        fst=x.fst,lst=x.lst;
    }
};
void get(node &x){
    while(cnt--){
        x.fst/=10;
    }
}
signed main(){
    node a,b;
    a.fst=1613053142490458;
    a.lst=1415797907386349;
    //F151
    b.fst=2609974810209388;
    b.lst=4802012313146549;
    //F152
    for(int i=153;;i++){
        node c;
        cnt=0;
        c=a+b;
        // printf("%lld %lld\n",c.fst,c.lst);
        // if(i==156)break;
        if(i&1)a=c,get(b);
        else b=c,get(a);
        if(c.check()){
            cout<<i<<endl;
            return 0;
        }
    }
}
/*
151:16130531424904581415797907386349
152:26099748102093884802012313146549
*/


Problem 105

考虑暴力枚举子集,然后就没了。

code

#include<bits/stdc++.h>
using namespace std;
int n,lim;
int a[110];
bool check2(){
    for(int i=0;i<lim;i++){
        for(int j=0;j<lim;j++){
            if(i&j)continue;
            int s1=0,s2=0;
            int t1=i,t2=j;
            for(int k=0;k<n;k++){
                if(t1&1)s1+=a[k];
                if(t2&1)s2+=a[k];
                t1>>=1,t2>>=1;
            }
            if((i||j)&&s1==s2)return 0;
        }
    }
    return 1;
}
bool check(){
    int q=a[0],p=0;
    for(int i=1,j=n-1;i-1<j+1;i++,j--){
        if(q<=p)return 0;
        q+=a[i],p+=a[j];
    }
    return 1&&check2();
}
int S(){
    int res=0;
    for(int i=0;i<n;i++)
        res+=a[i];
    return res;
}
int main(){
    freopen("E105.in","r",stdin);
    int ans=0;
    while(cin>>n){
        for(int i=0;i<n;i++)
            cin>>a[i];
        sort(a,a+n);
        lim=(int)round(pow(2,n));
        if(check())ans+=S();
    }

    cout<<ans<<endl;
    return 0;
}


Problem 106

先来理解一波题目。

意思是,现在有长度为n的严格递增的数列,并且保证满足对于非空且互不相交的子集B,C,如果|B|>|C|,那么S(B)>S(C) (S(A)代表A内的元素和),现在问里面有多少非空且互不相交的子集元素和可能相等。

为什么是可能呢,因为题目没有给具体的数列,也就是比如有单调递增的$a,b,c,d,e,f$,$a+b+c$一定不等于$d+e+f$,$\{a,c,e\}$和$\{b,d,f\}$同理。但有些子集如果没有具体数值是无法判断是否相等的, 比如$\{a,b,f\}$和$\{c,d,e\}$。

那么考虑转化一下问题。

第一步,需要检验的一定是元素个数相同的子集。否则如果不同,肯定能通过元素个数来判断和值大小。

第二步,我们可以枚举集合的大小,这个大小是从2开始的,对应的还需要找另一个大小相等且不相交的子集,所以这一步我们可以找出$C_{n}^{2x}÷2$个集合对。x的取值只需要保证$2\leq 2x\leq n$就可以了。

第三步,我们要排除这些大小相同的子集中和值一定不等,也就是能直接判断出大小关系的集合对。考虑换一个思路,我们把一组能直接比较出大小关系的,例如$\{a,c\},\{b,e\}$,表示为左右括号。那么什么情况是不合法的呢,那就是这个括号序列合法时。

比如x=3时,我们有括号序列$((()))$,它代表集合对$\{a,b,c\},\{d,e,f\}$,$(())()$代表集合对$\{a,b,e\},\{c,d,f\}$,那么为什么这样的就是不合法的呢?一个合法的括号序列,代表着$\forall i ,i∈A$,在集合$B$中都有一个唯一对应的$p_i$满足$B_{p_i}>A_i$,那么和值是一定能判断出来的。

所以问题就转化为了求$n$对括号的合法方案数,这个显然是个卡特兰数,但是我不会,所以去学了一下。

再把问题抽象一下,变为有$n$个元素,$2n$次操作,分别是入栈和出栈,在平面直角坐标系中,每入栈一次,我们就向上走一步,每出栈一次,我们就向下走一步,很显然最终会走到$(n,n)$,并且不考虑是否合法,方案数是$C^{n}_{2n}$。并且如果合法,这条路径一定不会经过直线$y=x$。

那么我们把过了直线$y=x$以后的部分关于$y=x+1$对称一下,那么最后会到达点$(n-1,n+1)$,这样的方案数是$C^{n+1}_{2n}$,所以最后的方案数就是$C_{2n}^{n}-C_{2n}^{n+1}$。

$$ \begin{split} Catalan_n&=C_{2n}^n-C_{2n}^{n+1}\\ &=\frac{(2n)!}{n!*n!}-\frac{(2n)!}{(n+1)!*(n-1)!}\\ &=\frac{1}{n+1}(\frac{(2n)!*(n+1)}{n!*n!}-\frac{(2n)!}{n!*(n-1)!})\\ &=\frac{1}{n+1}(\frac{(2n)!*(n+1)}{n!*n!}-\frac{(2n)!*n}{n!*n!})\\ &=\frac{1}{n+1}*\frac{(2n)!*(n+1)-(2n)!*n}{n!*n!}\\ &=\frac{1}{n+1}*\frac{(2n)!}{n!*n!}\\ &=\frac{1}{n+1}C_{2n}^n\\ \end{split} $$

那么套入本题,我们可以计算出每个集合大小对应的系数,然后再乘上这个集合大小在原数列中能出现多少组,这个用组合数就可以轻松解决。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int fac[13]={1};
inline int C(int n,int m){
    return fac[n]/fac[m]/fac[n-m];
}
inline int f(int n){
    int res=C(n,n/2)/2-C(n,n/2)/(n/2+1);
    return res;
}
signed main(){
    int ans=0;
    int n=12;
    for(int i=1;i<=n;i++)
        fac[i]=fac[i-1]*i;
    for(int x=4;x<=n;x+=2){
        ans+=f(x)*C(n,x);
    }
    cout<<ans<<endl;
    return 0;
}


Problem 107

裸的MST,没啥好说的。

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;
}
const int N=1010;
struct node{
    int u,v,w;
    bool operator < (const node &x) const {
        return w<x.w;
    }
}d[N];
int fa[N],sz[N];
int get(int x){
    return fa[x]==x?x:fa[x]=get(fa[x]);
}
bool merge(int x,int y){
    int r1=get(x),r2=get(y);
    if(r1==r2)return 0;
    if(sz[r1]>sz[r2])fa[r2]=r1,sz[r1]+=sz[r2];
    else fa[r1]=r2,sz[r2]+=sz[r1];
    return 1;
}
int main(){
    freopen("E107.txt","r",stdin);
    int n,m=0;
    cin>>n;
    int res=0;
    for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int k=read();
            if(i<j&&k){
                d[++m]=(node){i,j,k};
                res+=k;
            }
        }
    }
    int cnt=0,ans=0;
    sort(d+1,d+1+m);
    for(int i=1;i<=m;i++){
        if(merge(d[i].u,d[i].v)){
            cnt++,ans+=d[i].w;
            if(cnt==n)break;
        }
    }
    cout<<res-ans<<endl;
    return 0;
}


Problem 108

证明方程$\frac{1}{x}+\frac{1}{y}=\frac{1}{n}$的整数解的组数为$\frac{d(n^2)+1}{2}$,其中$d(n)$表示$n$的约数个数。

移项,得$\frac{1}{y}=\frac{1}{n}-\frac{1}{x}=\frac{x-n}{xn}$,那么$y=\frac{xn}{x-n}$。

考虑构造合法的$x$使得一定能找到合法的$y$,因为$x-n$太丑了,所以我们考虑构造一个$x'=d+n$。

那么就有$y=\frac{n(d+n)}{d}=\frac{n^2+dn}{n}=d+\frac{n^2}{d}$,显然,$y$是整数当且仅当$d|n^2$,那么这样的数对有$d(n^2)$对,但显然会出现半数重复的情况($d'=\frac{n^2}{d}$),那么答案就是$\frac{d(n^2)+1}{2}$。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int st[N],pr[N],cnt;
int f[N],g[N];
void prime(int n=N-10){
    for(int i=2;i<=n;i++){
        if(!st[i])st[i]=2,pr[++cnt]=i,g[i]=2,f[i]=3;
        for(int j=1;j<=cnt&&pr[j]*i<=n;j++){
            st[pr[j]*i]=1;
            g[pr[j]*i]=2;
            f[i*pr[j]]=f[i]*3;
            if(i%pr[j]==0){
                g[i*pr[j]]=g[i]+2;
                f[i*pr[j]]=f[i]/(g[i]+1)*(g[i*pr[j]]+1);
                break;
            }
        }
    }
}
int main(){
    prime();
    int lim=1000;
    for(int i=2;;i++){
        if(f[i]+1>>1>lim){
            printf("%d\n",i);
            break;
        }
    }
    return 0;
}


Problem 109

分三层背包即可。

code

#include<bits/stdc++.h>
using namespace std;
int f[4][1000010];
int v[100010],n,m=99;
int main(){
    f[1][50]++;
    v[++n]=25,v[++n]=50;
    for(int i=1;i<=20;i++)
        f[1][i*2]++,v[++n]=i,v[++n]=i*2,v[++n]=i*3;
    for(int i=1;i<=n;i++)
        for(int j=v[i];j<=m;j++)
            for(int k=2;k<=3;k++)
                f[k][j]+=f[k-1][j-v[i]];
    int res=0;
    for(int i=1;i<=m;i++)
        res+=f[1][i]+f[2][i]+f[3][i];
    cout<<res<<endl;
    return 0;
}


Problem 110

反正是108的加强版,于是根据公式进行爆搜即可。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int pr[]={0,2,3,5,7,11,13,17,19,23,29,31,37,41};
int ans=1e17;
void dfs(int dep,long long now,int res,int pre){
      if(dep==14)return;
      if(now>=ans)return;
      if((res+1)/2>4000000){ans=now;return;}
      for(int i=1;i<=pre;i++){
        now*=pr[dep];
        if(now<0)return;
        dfs(dep+1,now,res*(i*2+1),i);
      }
}
signed main(){
    dfs(1,1,1,10);
    cout<<ans<<endl;
      return 0;
}

最后修改:2020 年 12 月 03 日 05 : 03 PM