标签归档：Codeforces

Codeforces 102346 problem K Keep Calm and Sell Balloons

发表评论

这道题重点要说矩阵快速幂，公式不会推。用了一个Berlekamp-Massey algorithm的模板。最主要想将一般情况下线性递推式怎么用矩阵快速幂优化。
本题目的递推公式是：F(n)=6*F(n-1)-8*F(n-2)-8*F(n-3)+16*F(n-4)。
故构造矩阵递推公式：
\begin{bmatrix}
F(n) \\
F(n-1) \\
F(n-2) \\
F(n-3)
\end{bmatrix} =
\begin{bmatrix}
6 & -8 & -8 & 16 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0
\end{bmatrix} *
\begin{bmatrix}
F(n-1) \\
F(n-2) \\
F(n-3) \\
F(n-4)
\end{bmatrix}
得
\begin{bmatrix}
F(n) \\
F(n-1) \\
F(n-2) \\
F(n-3)
\end{bmatrix} =
\begin{bmatrix}
6 & -8 & -8 & 16 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0
\end{bmatrix}^{n-4} *
\begin{bmatrix}
F(4) \\
F(3) \\
F(2) \\
F(1)
\end{bmatrix}
。
对于一般的线性递推公式F(n)=a_1*F(n-1)+a_2*F(n-2)+…+a_{k-1}*F(n-k+1)+a_k*F(n-k)，
可以构造一长宽都为k的矩阵，满足：
\begin{bmatrix}
F(n) \\
F(n-1) \\
… \\
F(n-k+2) \\
F(n-k+1)
\end{bmatrix} =
\begin{bmatrix}
a_1 & a_2 & … & a_{n-k+1} & a_{n-k} \\
1 & 0 & … & 0 & 0 \\
0 & 1 & … & 0 & 0 \\
… & … & … & … & … \\
0 & 0 & … & 1 & 0
\end{bmatrix} *
\begin{bmatrix}
F(n-1) \\
F(n-2) \\
… \\
F(n-k+1) \\
F(n-k)
\end{bmatrix}
因此只需对该矩阵做快速幂，即可以以O(k^3logn)的复杂度推出任意n情况下的数列的值。
本题代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
using namespace std;
const long long MOD = 1e9 + 7;
const int maxtrixN=4;
struct matrix {
    long long arr[maxtrixN][maxtrixN];
    matrix operator * (matrix m2) {
        matrix result;
        long long(&arr)[maxtrixN][maxtrixN] = result.arr;
        const long long(&arr1)[maxtrixN][maxtrixN] = this->arr;
        const long long(&arr2)[maxtrixN][maxtrixN] = m2.arr;
        for (int i = 0; i < maxtrixN; i++) {
            for (int j = 0; j < maxtrixN; j++) {
                arr[i][j] = 0;
                for (int k = 0; k < maxtrixN; k++) {
                    arr[i][j] += arr1[i][k] * arr2[k][j] % MOD;
                    arr[i][j] += MOD;
                    arr[i][j] %= MOD;
                }
            }
        }
        return result;
    }
};
const matrix c = { 6,-8,-8,16,1,0,0,0,0,1,0,0,0,0,1,0 };
matrix quickpow(long long n) {
    if (n == 1)return c;
    matrix half = quickpow(n / 2);
    matrix result = half * half;
    if (n & 1)result = result * c;
    return result;
}
long long getValue(long long n) {
    matrix result = quickpow(n);
    long long(&arr)[4][4] = result.arr;
    return (arr[0][0] * 1536 % MOD + arr[0][1] * 416 % MOD + arr[0][2] * 96 % MOD + arr[0][3] * 24 % MOD +MOD) % MOD;
}
int main() {
    int n;
    long long a1[] = { 0,2,24,96,416,1536 };
    cin >> n;
    if (n < 6)cout << a1[n];
    else cout << getValue(n-5);
}

Codeforces Round #494 (Div. 3) 1003 B题 Binary String Constructing 构建二进制字符串 题解

发表评论

简明题意：用a个0，b个1构建出长度为n=a+b的字符串s，且对于$0 < i < n$，有$s_i != s_{i-1}$的i的个数恰为x。
当时比赛的时候没做出来，估计就是要写搜索一类的就先跳过了。后来再来写这道题目。

所以今天改了三遍。没有看任何题解。第一版：递归，第二版：递推/迭代（动规），第三版：递推（动规）+滚动数组优化。真的不知道我是怎么想起来N长时间之前背包问题里的滚动数组优化了。感觉自己特别厉害好长时间都没写了这都能想的起来。第三版程序终于有了让人没有文字说明就完全看不懂想不明白的资本啦，哈哈^v^

第一版：递归，没有任何记忆化措施，所以TLE了，然后就想着把递归换成递推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<algorithm>
using namespace std;
int a, b, x;
char str[105];
bool recusive(int curpos, int cura, int curb, int curx) {
    if (curpos == a + b) {
        if (cura == a && curb == b && curx == x) {
            str[curpos] = '\0';
            return true;
        }
        else return false;
    }
    if ((cura == a || curb == b)&&curx==x) {
        if (cura == a) {
            for (int i = curpos; i < a + b; i++)str[i] = '1';
            str[a + b] = '\0';
            return true;
        }
        else {
            for (int i = curpos; i < a + b; i++)str[i] = '0';
            str[a + b] = '\0';
            return true;
        }
    }
    //Assume curpos==0
    str[curpos] = '0';
    bool flag = false;
    if (curpos == 0 || str[curpos - 1] == '0')flag = recusive(curpos + 1, cura + 1, curb, curx);
    else flag = recusive(curpos + 1, cura + 1, curb, curx + 1);
    if (flag)return true;
    str[curpos] = '1';
    if (curpos == 0 || str[curpos - 1] == '1')flag = recusive(curpos + 1, cura, curb + 1, curx);
    else flag = recusive(curpos + 1, cura, curb + 1, curx + 1);
    if (flag)return true;
    return false;
}
int main() {
    cin >> a >> b >> x;
    recusive(0, 0, 0, 0);
    cout << str;
}

第二版：递推。没有任何优化，时间够了，但是内存不够MLE了。四个维度分别是a,b,x,上个字符串的最后一个数字是0还是1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int a, b, x;
string arr[101][101][201][2]; //a,b,x,
int main() {
    cin >> a >> b >> x;
    for (int i = 1; i <= a; i++)arr[i][0][0][0] = arr[i - 1][0][0][0] + '0';
    for (int i = 1; i <= b; i++)arr[0][i][0][1] = arr[0][i - 1][0][1] + '1';
    for (int k = 1; k <= x; k++) { //curx
        for (int i = 1; i <= a; i++) { //cura
            for (int j = 1; j <= b; j++) { //curb
                //Assume to place a 0
                if (arr[i - 1][j][k - 1][1] != "")arr[i][j][k][0] = arr[i - 1][j][k - 1][1] + '0';
                else if (arr[i - 1][j][k][0] != "")arr[i][j][k][0] = arr[i - 1][j][k][0] + '0';
                //Assume to place a 1
                if (arr[i][j - 1][k - 1][0] != "")arr[i][j][k][1] = arr[i][j - 1][k - 1][0] + '1';
                else if (arr[i][j - 1][k][1] != "")arr[i][j][k][1] = arr[i][j - 1][k][1] + '1';
            }
        }
    }
    if (arr[a][b][x][0] != "")cout << arr[a][b][x][0];
    else cout << arr[a][b][x][1];
}

第三版：递推+滚动数组。把第三维由201优化到只剩2。因为动规的转移方程里面只需要上一个k和当前k的数组，所以滚动数组优化一下就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int a, b, x;
string arr[101][101][2][2];
inline int trans(int num) {
    if (num % 2 == 0)return 0;
    else return 1;
}
int main() {
    cin >> a >> b >> x;
    for (int i = 1; i <= a; i++)arr[i][0][0][0] = arr[i - 1][0][0][0] + '0';
    for (int i = 1; i <= b; i++)arr[0][i][0][1] = arr[0][i - 1][0][1] + '1';
    for (int k = 1; k <= x; k++) { //curx
        for(int i=0;i<=a;i++)for(int j=0;j<=b;j++)for(int m=0;m<=1;m++)arr[i][j][trans(k)][m]=""; //Clean the rolling array to prevent unexpected error
        for (int i = 1; i <= a; i++) { //cura
            for (int j = 1; j <= b; j++) { //curb
                //Assume to place a 0
                if (arr[i - 1][j][trans(k - 1)][1] != "")arr[i][j][trans(k)][0] = arr[i - 1][j][trans(k - 1)][1] + '0';
                else if (arr[i - 1][j][trans(k)][0] != "")arr[i][j][trans(k)][0] = arr[i - 1][j][trans(k)][0] + '0';
                else arr[i][j][trans(k)][0]="";
                //Assume to place a 1
                if (arr[i][j - 1][trans(k - 1)][0] != "")arr[i][j][trans(k)][1] = arr[i][j - 1][trans(k - 1)][0] + '1';
                else if (arr[i][j - 1][trans(k)][1] != "")arr[i][j][trans(k)][1] = arr[i][j - 1][trans(k)][1] + '1';
                else arr[i][j][trans(k)][1]="";
            }
        }
    }
    if (arr[a][b][trans(x)][0] != "")cout << arr[a][b][trans(x)][0];
    else cout << arr[a][b][trans(x)][1];
}

写了我三个小时，也是挺不容易的……继续努力！写的不清楚有问题可以在下面评论问。

Codeforces 官方规则介绍

发表评论

发几个链接，因为国内实在不好找，所以贴上来：
Codeforces Contest Rules https://codeforces.com/blog/entry/4088
Codeforces Contests https://codeforces.com/blog/entry/456
Frequently Asked Questions https://codeforces.com/blog/entry/1336

Codeforces Round #494 (Div. 3) 1003 A/C/D题解

发表评论

A题：非常简单，只要找重复数字的最大个数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<algorithm>
using namespace std;
int arr[105];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int tmp;
        cin>>tmp;
        arr[tmp]++;
    }
    int maxn=0;
    for(int i=1;i<=100;i++){
        maxn=max(maxn,arr[i]);
    }
    cout<<maxn;
}

C题：用个前缀和优化一下，剩下的暴力去吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
int n,k;
double arr[5005];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>arr[i];
    for(int i=2;i<=n;i++)arr[i]+=arr[i-1];
    double maxavg=0,curavg;
    for(int i=k;i<=n;i++){
        for(int j=i;j<=n;j++){
            curavg=(arr[j]-arr[j-i])/i;
            maxavg=max(maxavg,curavg);
        }
    }
    printf("%.15lf",maxavg);
}

D题：把所有二的次幂数全部搞到桶里，然后按照次幂由高到低往下减，看最后能不能减到0，如果能即可，不能就不能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
int n,q;
int bucket[32];
int powarr[32];
int checkpower(int num){
    if(num==1)return 0;
    int cnter=0;
    while(num!=1){
        num/=2;
        cnter++;
    }
    return cnter;
}
void program_init(){
    powarr[0]=1;
    for(int i=1;i<=30;i++){
        powarr[i]=powarr[i-1]*2;
    }
}
int main(){
    program_init();
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        int num;
        cin>>num;
        bucket[checkpower(num)]++;
    }
    for(int i=1;i<=q;i++){
        int num,cnter=0;
        cin>>num;
        for(int i=30;i>=0;i--){
            cnter+=min(num/powarr[i],bucket[i]);
            num-=min(num/powarr[i],bucket[i])*powarr[i];
        }
        if(num!=0)cout<<-1<<endl;
        else cout<<cnter<<endl;
    }
}

Codeforces 598A Tricky Sum 技巧求和

发表评论

题目地址：http://codeforces.com/problemset/problem/598/A
这道题目本来一开始是想要搞暴力的，但是第一个就超时。不得已换了个数学方法。
首先用小学生都会的数列求和：（首项+末项）*项数/2 把从1…n的和算出来，然后计算出不大于n的2的幂次共有多少个，用等比数列求和公式求出它们的和，减去两倍即可。
上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<algorithm>
using namespace std;
long long try2(long long n){ //函数try2就是计算从1到n之间所有不大于n的2的幂次之和，可结合等比数列求和公式推导后再领悟，不懂可以看下面或者评论我博客。
    long long m2=1;
    while(m2<=n)m2*=2;
    return m2-1;
}
void process(){
    long long n;
    cin>>n;
    cout<<((1+n)*n/2-2*try2(n))<<endl;
}
int main(){
    int t;
    cin>>t;
    while(t--)process();
}

其实做这道题是要数学功底的。。。我还是把具体的推导过程说一下好了。我们想要求出小于n的所有2的幂次方项之和，根据等比数列求和公式可知:2^0+2^1+2^2+…+2^n=2^{n+1}-1所以我们只要找到最大的小于n的2的幂次再乘2减1就可以了。具体代码可参见函数try2()。

Codeforces 597B Restaurant 餐厅

发表评论

题目地址：http://codeforces.com/contest/597/problem/B
和洛谷P1803一模一样，之前写过的题解：https://renjikai.com/luogu-p1803/
耻辱啊，还要看原来的题解……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
#include<algorithm>
using namespace std;
struct ss{
    int s,e;
    bool operator < (ss s2){
        if(e!=s2.e)return e<s2.e;
        else return s>s2.s;
    }
}sa[500005];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>sa[i].s>>sa[i].e;
    }
    sort(sa+1,sa+1+n);
    int cnter=0,t=0;
    for(int i=1;i<=n;i++){
        if(sa[i].s>t){
            cnter++;
            t=sa[i].e;
        }
    }
    cout<<cnter;
}

Codeforces 597A Divisibility 整除

发表评论

题目：http://codeforces.com/contest/597/problem/A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
using namespace std;
inline long long cal(long long a,long long b,long long k){
    return b/k-(a-1)/k;
}
int main(){
    long long k,a,b;
    cin>>k>>a>>b;
    if(a>0)cout<<cal(a,b,k);
    else if(b<0)cout<<cal(-b,-a,k);
    else if(a==0)cout<<b/k+1;
    else if(b==0)cout<<(-a)/k+1;
    else if(a<0&&b>0)cout<<cal(1,b,k)+cal(1,-a,k)+1;
}