[游记]高一提高组过渡1-2022/5/31

昨天刚吵吵着要退奥被劝回来了

今天就来了场阴间考试（

离谱

A. 装饰

B. 中国象棋

C. 奇妙的 Fibonacci

赛时得分：130/300（第二题智障错误100->0笑了

赛时排行：Rank4

 先开T1，看着像是一道模拟

A. 装饰

自然不可能去推数学式子，看看是不是大模拟

然后发现肯定不是，原因显然：

1000^3 如果不想去航空班就别模拟了吧……

开始思考

首先对于三个都是0，显然答案是0

然后对于有一个特别多的情况我们每次选两个这个颜色和一个另外某种颜色。

不妨设 a > b > c ，显然的我们有答案就是 b + c

然后是其他的情况，可以考虑先三种颜色都选，然后剩下比较多的两种

两种中 3 个 3 个选，这样每选两组两种颜色各减去3个

对于剩下的较多的气球，考虑将先前的一张桌子三种颜色都选改为两种较少的单独出来，一个配两个较多的，这样就可以拆出来两个桌子

答案就是 ( a + b + c ) / 3 向下取整

题解也显然是这样的

【问题分析】

显然，(a+b+c)/3 是答案的一个上界，a+b+c-max(a,b,c)也是答案的一个上 界，

下面大致证明 min((a+b+c)/3,a+b+c-max(a,b,c))即为答案：

1、当(a+b+c)/3 <= a+b+c-max(a,b,c)时，没有哪一种颜色的气球数量特别 地多，气球数量的差距可以将三色气球装饰的桌子更换一个气球来弥补，这样就 可以装饰(a+b+c)/3 张桌子。

2、否则，不妨假设红色气球数量 a 很大，那么这时候显然可以装饰出 b+c= a+b+c-max(a,b,c)张桌子（两个红色气球与一个非红色气球）。

综上所述，答案即为 min((a+b+c)/3,a+b+c-max(a,b,c))。

#include
#include
#include<string>
#define WR WinterRain
#define int long long
#define Decorate signed
using namespace std;
const int WR=510;
int t,a,b,c;
int ans=0;
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<3)+(s<<1)+ch-48;
        ch=getchar();
    }
    return s*w;
}
void swp(int &x,int &y){
    int t=x;
    x=y;
    y=t;
}
void check(){
    if(a>b) swp(a,b);
    if(a>c) swp(a,c);
    if(b>c) swp(b,c);
}
Decorate main(){
    freopen("decorate.in","r",stdin);
    freopen("decorate.out","w",stdout);
    t=read();
    while(t--){
        a=read(),b=read(),c=read();
        check();
        if(a==0&&b==0){
            printf("0\n");
            continue;
        }
        if(c>=(a+b)*2){
            printf("%lld\n",a+b);
            continue;
        }
        printf("%lld\n",(a+b+c)/3);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

考试的时候想这是啥啊，这什么式子啊

然后交了虽然觉得不对但不交显得很蠢……然后就莫名其妙的A了

然后看T2，显然的动规

T3，显然的数学题

然后徘徊徘徊，直到我看到了T3的阴间时间空间限制：2000ms

果断开了T2

B. 中国象棋

 好像看到过这道题目

但是肯定早忘了

（ update：是洛谷原题 ）

于是滚去三楼推柿子

先写了个状压过50%的数据，然后一看这非同寻常的空间：

64MB

然后把状压扔了看看按行列DP

在三楼徘徊徘徊突然发现思路错了，不能按照行列做DP

不然良心出题人给一个100*100的数据范围太好了点

发现了有趣的性质，一行一列最多放两个炮

然后换思路看看能不能按照炮的个数DP

于是推了一大组方程，觉得比较稳

但是发现时间复杂度是 O ( n ^ 3 ) 的，于是开始卡常

先滚掉一维数组，

然后原来写的 memset 换成 for 循环清空，

这一清空啊，欸

就清空得分了，100->0

开心

一共五个状转方程恶心透了

//这64MB内存好像预示了什么
//状压显然不可用
//------------------------
//是否可以发现可以看单独的一列？ 
//有趣的性质：炮数每行每列最多2个
#include
#include
#include<string>
#define WR WinterRain
#define int long long
#define Chess signed
using namespace std;
const int WR=1010,mod=9999973;
int n,m;
int dp[WR][WR],tmp[WR][WR];
int ans;
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<3)+(s<<1)+ch-48;
        ch=getchar();
    }
    return s*w;
}
Chess main(){
    freopen("chess.in","r",stdin);
    freopen("chess.out","w",stdout);
    n=read(),m=read();
    dp[0][0]=1;
    for(int i=1;i<=n;++i){
        //设dp[i][j]表示转移到第i行第j列
        //这显然是错误的看看数据范围都知道肯定有毛病
        //------------------------------------------------
        //那试试当前第i行，有j个炮数为1的列，有k个炮数为2的列
        //这道题我好像见过。。。。。。就是没写
        //应该是洛谷上一道题目。。。
        for(int j=0;j<=m;++j){
            for(int k=0;k<=m-j;++k){//最多就是m-j列放两个炮了不可能更多了
                if(dp[j][k]){
                    if(j) tmp[j-1][k+1]=(tmp[j-1][k+1]+dp[j][k]*j%mod)%mod;
                    //有一个炮数为1的列，我在这里放上一个炮让它变成炮数为2
                    //这样j--，k++
                    //因为有j种可能所以乘个j
                    if(m-j-k) tmp[j+1][k]=(tmp[j+1][k]+dp[j][k]*(m-j-k)%mod)%mod;
                    //有一个空列，我放一个炮
                    //j++，k不变
                    //有m-j-k种可能
                    if(j>1) tmp[j-2][k+2]=(tmp[j-2][k+2]+dp[j][k]*j*(j-1)/2%mod)%mod;
                    //一次性放两个
                    //两次全都放在先前有炮的地方
                    //有C(2,j)种可能
                    if(m-j-k>1) tmp[j+2][k]=(tmp[j+2][k]+dp[j][k]*(m-j-k)*(m-j-k-1)/2%mod)%mod;
                    //一次放两个
                    //两次全都放在先前没有炮的地方
                    //有C(2,(m-j-k))种可能
                    if(m-j-k) tmp[j][k+1]=(tmp[j][k+1]+dp[j][k]*(m-j-k)*j%mod)%mod;
                    //一次放两个，两个在同一列
                    tmp[j][k]=(tmp[j][k]+dp[j][k])%mod;
                    //还要加上上面转移来的 
                }
            }
        }
        memcpy(dp,tmp,sizeof(tmp));
        memset(tmp,0,sizeof(tmp));
        //这里！！！一定要用memset！！！
        //我开了for循环，100->0 
    }
    for(int i=0;i<=m;i++){
        for(int j=0;j<=m-i;j++){
            ans=(ans+dp[i][j])%mod;
        }
    }
    printf("%lld",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

交了感觉比较稳

然后去看T3

C. 奇妙的 Fibonacci

 这时间是如此的玄学

以及

 这离谱的数据范围高精都得炸

所以果断推性质

 然后发现假如 fib[i] | fib[j]

则肯定有 i | j

那就没事了，硬暴力筛……

吗？

得到了30分的好成绩

赛后去问楚涵dalao得到结论

对于所有 f[x+2]=af[x+1]+bf[x] ( gcd(a,b)=1 )

都有 gcd( f[i] , f[j] ) = f [ gcd( i , j ) ]

好像是这样的明天再看看（

所以只能看题解了

A[i]为 i 的约数个数，B[i]为 i 的约数平方和，C[i]为 i 最小质因子的幂是多少，D[i]为 i 除 去所有最小质因子后的剩下的数。

显然 A[i],B[i]满足互质积性。

设 q 为最小质因子。

A[q]=2 B[q]=1+q^2 C[q]=1 D[q]=1 当 gcd(p,q)=1 ,A[pq]=A[p]A[q] ,B[pq]=B[p]B[q] ,C[pq]=1 ,D[pq]=p。

当 q|p 时，A[pq]=A[p]/(C[p]+1)*(C[p]+2)。 B[pq]=B[p]+B[D[p]]*(p/D[p])^2。 C[pq]=C[p]+1; D[pq]=D[p]。

所以线性筛就可以完成了。

于是本题基本做完了。 但还是有特殊，比如 f2=1,是所有 fi 的约数，所以要特判。

于是有了如下的AC代码

#include
#include
#include<string>
#define WR WinterRain
#define int long long
#define Fibonacci signed
using namespace std;
const int WR=10010000,mod=1e9+7;
int Q,a,b,c;
int n;
int prime[WR],cnt=0;
int sumad[WR],sumtm[WR];
int anssm,anstm;
int res[WR],minpow[WR];
bool vis[WR];
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<3)+(s<<1)+ch-48;
        ch=getchar();
    }
    return s*w;
}
void Euler(){
    sumad[1]=1; sumtm[1]=1;
    for(int i=2;i){
        if(!vis[i]){
            prime[++cnt]=i;
            sumad[i]=2;
            sumtm[i]=(i*i+1)%mod;
            minpow[i]=1;
            res[i]=1;
        }
        for(int j=1;j<=cnt&&i*prime[j]){
            int tmp=i*prime[j];
            vis[tmp]=true;
            if(i%prime[j]==0){
                minpow[tmp]=minpow[i]+1;
                res[tmp]=res[i];
                sumad[tmp]=sumad[i]/(minpow[i]+1)*(minpow[tmp]+1);
                sumtm[tmp]=(sumtm[i]*(prime[j]*prime[j]%mod)%mod+sumtm[res[i]])%mod;
                break;
            }
            sumad[tmp]=sumad[i]*sumad[prime[j]];
            sumtm[tmp]=sumtm[i]*sumtm[prime[j]]%mod;
            minpow[tmp]=1;
            res[tmp]=i;
        }
    }
}
Fibonacci main(){
    freopen("fibo.in","r",stdin);
    freopen("fibo.out","w",stdout);
    Euler();
    Q=read();
    n=read(),a=read(),b=read(),c=read();
    while(Q--){
        anssm=(sumad[n]+(n&1)+anssm)%mod;
        anstm=(sumtm[n]+4*(n&1)+anstm)%mod;
        n=(n*a+b)%c+1;
    }
    printf("%lld\n%lld",anssm,anstm);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

这次严重发挥失常……T2炸0是没想到的

加油吧ovo