/ ALGORITHM

PKU Campus 2017 (重现)

Contest Information

source: It’s from the Vjudge

Problem F

计算出 $ (7+4\sqrt{3})^N $ 的整数部分

数据范围:$ 1 ≤ N ≤ 10^{9}$

Solution

如果使用 double 来计算,精度肯定是不够的。我们发现 $ (7+4\sqrt{3})^N $ 展开之后是 $ a_N+b_N \sqrt{3} $ 的形式,而 $ (7-4\sqrt{3})^N $ 展开之后是 $ a_N-b_N \sqrt{3} $ 。因此 $ (7+4\sqrt{3})^N + (7-4\sqrt{3})^N = 2a_N $ 是个整数(因为 $ 0 < (7-4\sqrt{3})^N < 1 $ ),所以 $ (7+4\sqrt{3})^N $ 的整数部分等于 $ 2 a_N - 1$。

所以问题转换成求解出 $a_N$,因为
$ ( a_{N+1}+b_{N+1} \sqrt{3}) = (7+4\sqrt{3})^{N+1} = (7+4\sqrt{3}) (7+4\sqrt{3})^N = (7+4\sqrt{3}) ( a_N+b_N \sqrt{3}) $,所以我们可以得到递推关系:
$ a_{N+1} = 7 \times a_N + 12 \times b_N $
$ b_{N+1} = 4 \times a_N + 7 \times b_N $
$ a_0 = 1, b_0 = 0 $

AC code

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> T;
    while(T--)
    {
        cin >> N;
        if(N==0)
        {
            puts("1");
            continue;
        }
        Mat ans;
        ans.mat[0][0] = 7;
        ans.mat[0][1] = 4;
        ans.mat[1][0] = 12;
        ans.mat[1][1] = 7;
        ans = ans^N;
        int fn = (2*ans.mat[0][0]+mod-1)%mod;
        cout << (fn%mod+mod)%mod << endl;
    }
}

Problem H

给出一个序列 $ s_1, s_2, s_3, s_4, …, s_N $ ,给出 $Q$ 个查询, 每次询问原序列中有多少个区间满足第 $K$ 大的值为 $X$

数据范围:$ 1 ≤ N,S_i ≤ 2\times 10^{3}, 1 ≤ Q ≤ 2 \times 10^{6} $

Solution

使用 FFT 预处理出每一个数作为第 $K_i$ 大时有多少个区间。对于每个数,我们先统计出从它到它左边的序列里(等于它也算作大于它),它作为第 $K_i$ 大的区间有多少个,列成多项式: $ (a_0\times x^0 + a_1\times x^1 + … + a_n\times x^n $,每一项的指数代表第几大,系数代表第几大时的区间数量。同样,我们再统计出它到它右边的序列里(等于它不算作大于它), 它作为第 $K_i$ 大的区间有多少个,列成多项式: $ (b_0\times x^0 + b_1\times x^1 + … + b_n\times x^n $。那么这两个多项式相乘,就能统计出这个数作为第 $K_i$ 大的数的区间数量。

AC code

int T,N,Q,val[MaxN/2];
int a[MaxN/2],b[MaxN/2];
int ans[MaxN/2][MaxN/2];
void solve()
{
    for(int i=1;i<=N;i++)
    {
        CLR(a),CLR(b);
        a[0] = b[0] = 1;

        int loc = 0;
        for(int j=i-1;j>=1;j--)
        {   
            if(val[j]<val[i]) a[loc]++;
            else 
            {
                loc++;
                a[loc] = 1;
            }
        }
        //for(int i=0;i<=loc;i++) debug(a[i])
        len1 = loc+1;

        loc = 0;
        for(int j=i+1;j<=N;j++)
        {   
            if(val[j]<=val[i]) b[loc]++;
            else 
            {
                loc++;
                b[loc] = 1;
            }
        }
        //for(int i=0;i<=loc;i++) debug(b[i])
        len2 = loc+1;
        Prepare();
        Convolution(A,B);
        Adjustment(res);
        for(int j=0;j<len;j++)
        {
            ans[val[i]][j+1] += res[j];
        }
    }
}
void init()
{
    CLR(ans);
}
int main()
{
    //std::ios::sync_with_stdio(false);
    scanf("%d", &T);
    while(T--)
    {
        init();
        scanf("%d%d", &N, &Q);
        for(int i=1;i<=N;i++) scanf("%d", &val[i]);
        solve();
        int k,x;
        while(Q--)
        {
            scanf("%d%d", &k, &x);
            printf("%d\n", ans[x][k]);
        }
    }
    //system("pause");
    //printf("%lld\n", (x%mod+mod)%mod );
}

Problem I

给出 $7$ 种不同的俄罗斯方块,要求你用尽可能多种类的方块搭出一个高度为 $N$ 的阶梯

数据范围:$ 1 ≤ N ≤ 3\times 10^{3}$

Solution

只有当 $ N\%8==7 \ or\ N\%8==0 $ 时才有可能搭建成功,其中 $N=7$ 可以凑出 $6$ 种,$N=8$ 可以凑出 $7$ 种。再往后我们可以直接用样例里的输出拼凑成阶梯

Problem J

计算满足 $ q \times x^2 + p \times y = M $ 的整数对 $ (x, y)$ 的数量

数据范围:$ 1 ≤ M ≤ 8\times 10^{5} $

Solution

首先预处理出 $ 800000 $ 以下每个数包含的平方数因子,然后枚举 $y$ 和 $p$,统计 $M-y\times p $ 的平方因子。

AC code

int T,M;
vector<int> factor[MaxN];

void init()
{
    for(int x=1;x*x<=800000;x++)
    {
        for(int p=1;p*x*x<=800000;p++)
        {
            factor[x*x*p].push_back(x);
        }
    }
}
int vis[MaxN];
void solve()
{
    int ans = 0;
    for(int y=1;y<=M;y++)
    {
        for(int q=1;q*y<=M;q++)
        {
            int cnt = M-y*q;
            for(int i=0;i<factor[cnt].size();i++)
            {
                if(vis[factor[cnt][i]]!=y) ans++,vis[factor[cnt][i]] = y;
            }
        }
    }
    printf("%d\n", ans);
}
int main()
{
    //std::ios::sync_with_stdio(false);
    init();
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &M);
        solve();
    }
}

Problem K

有$ N $ 个人,其中有好人(不会说谎),也有坏人(可能说谎)。现在从第二个人开始询问,询问第 $i$个人时,他有可能会说: 第 $x$ 个人是好(坏)人;也可能会说: 如果第 $x$ 个人是(好)(坏)人, 那么第 $y$ 个人是 (好)(坏)人。其中 $x,y \in [max(i-K,1),i-1] $,要求你判断这儿最多有多少个好人

数据范围:$ 1 ≤ N ≤ 5\times 10^{3}, 1 ≤ K ≤ 10$

Solution

我们定义 $ DP[i][s] $ 为在第 $i$ 个人时,前 $K$ 个人的好坏状态为 $s$ 时的最大好人数量。每次假设第 $i$个人为好人,如果他说的话也符合当前枚举的状态那么他就真的是好人。

AC code

int T,N,K;
int DP[MaxN][(1<<10)+10];
char op[8],type1[8],type2[8];
inline void init(){
    MST(DP,-1);
    DP[1][0] = 0;
    DP[1][1] = 1;
}
bool check(int ss, int loc){
    return ss & (1<<loc);
}
int main()
{
    //std::ios::sync_with_stdio(false);
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &N, &K);
        //debug(N) debug(K)
        init();
        int STAT = (1<<K)-1;
        for(int id=2;id<=N;id++)
        {
            int woshishui;
            scanf(" Person %d: %s", &woshishui, op);
            //debug(op);
            if(op[0]=='P')
            {
                int x;
                scanf(" %d is a %s guy.", &x, type1);
                x = id-x-1;
                bool good = type1[0]=='g';
                for(int stat=0;stat<=STAT;stat++)
                {
                    if(DP[id-1][stat]==-1) continue;
                    auto &tmp = DP[id][((stat<<1)&STAT)|1];
                    //假设好人
                    bool judge = check(stat, x);
                    if( good == judge)
                    {
                        tmp = max(tmp, DP[id-1][stat]+1);
                    }
                    //假设坏人
                    auto &pmt = DP[id][(stat<<1)&STAT];
                    pmt = max(pmt, DP[id-1][stat]);
                }
            }
            else{
                int x,y;
                scanf(" person %d is a %s guy, person %d is a %s guy.", &x,type1,&y,type2);
                bool goodx = type1[0] == 'g', goody = type2[0]=='g';
                x = id-x-1, y = id-y-1;
                for(int stat=0;stat<=STAT;stat++)
                {
                    if( DP[id-1][stat]==-1 ) continue;
                    auto &tmp = DP[id][((stat<<1)&STAT)|1];
                    //假设好人
                    bool judgex = check(stat, x),
                         judgey = check(stat, y);
                    if( goodx == judgex)
                    {
                        if(goody == judgey) tmp = max(tmp, DP[id-1][stat]+1);
                    }
                    else tmp = max(tmp, DP[id-1][stat]+1);
                    //假设坏人
                    auto &pmt = DP[id][(stat<<1)&STAT];
                    pmt = max(pmt, DP[id-1][stat]);
                }
            }
        }
        int ans = 0;
        for(int i=0;i<=STAT;i++) ans = max2(ans, DP[N][i]);
        printf("%d\n", ans);
    }
    //system("pause");
    //printf("%lld\n", (x%mod+mod)%mod );
}