月度归档：2018年07月

洛谷 加分二叉树

发表评论

题号：P1040
很有意义，想了不短时间，和一位群里的同学讨论了一下：代码如下：

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
int n;
struct re{
    int i;
    string s;
    re(){
       
    }
    re(int i,string s){
        this->i=i;
        this->s=s;
    }
    re operator = (const re r){
        this->i=r.i;
        this->s=r.s;
        return *this;
    }
}f[32][32];
int scores[35];
string construction(int num){
    string s="";
    while(num!=0){
        s.insert(0,1,'0'+num%10);
        num/=10;
    }
    s+=' ';
    return s;
}
re dfs(int l,int r){
    if(l==r)return re(scores[l],construction(l));
    if(l>r)return re(1,"");
    if(f[l][r].i!=0)return f[l][r];
    int mm=0;
    string s;
    for(int i=l;i<=r;i++){
        re re1=dfs(l,i-1);
        re re2=dfs(i+1,r);
        if(mm<re1.i*re2.i+scores[i]){
            mm=re1.i*re2.i+scores[i];
            s=construction(i)+re1.s+re2.s;
        }
    }
    return f[l][r]=re(mm,s);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>scores[i];
    re re1=dfs(1,n);
    cout<<re1.i<<endl;
    cout<<re1.s;
}

洛谷 谁拿了最多奖学金

发表评论

这题本身没啥好说的，非常简单，要说的是C++的一个特性。
这个题写的比较复杂，其实不用这么多空间，也不要排序，直接线性处理就行了。但是我写题写习惯了，又接着搞排序，就出了这么个问题。

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
#include<bits/stdc++.h>
using namespace std;
int n;
struct stu{
    string name;
    int fs,cs;
    char sl,wp;
    int an;
    int money;
    stu(){
        money=0;
    }
    bool operator < (const stu& s2){
        return money>=s2.money;
    }
}stus[105];
int sum=0;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>stus[i].name>>stus[i].fs>>stus[i].cs>>stus[i].sl>>stus[i].wp>>stus[i].an;
    for(int i=1;i<=n;i++){
        if(stus[i].fs>80&&stus[i].an>=1)stus[i].money+=8000;
        if(stus[i].fs>85&&stus[i].cs>80)stus[i].money+=4000;
        if(stus[i].fs>90)stus[i].money+=2000;
        if(stus[i].fs>85&&stus[i].wp=='Y')stus[i].money+=1000;
        if(stus[i].cs>80&&stus[i].sl=='Y')stus[i].money+=850;
        sum+=stus[i].money;
    }
    sort(stus+1,stus+n+1);
    cout<<stus[1].name<<endl;
    cout<<stus[1].money<<endl;
    cout<<sum;
}

问题就出在比较的>=号上。查找了资料（地址http://blog.sina.com.cn/s/blog_532f6e8f01014c7y.html），我没细看，总结出来就是sort的cmp不能用带=号的。这个问题我最后就用stable_sort解决了。好用。代码如下：

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
#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct stu{
    string name;
    int fs,cs;
    char sl,wp;
    int an;
    int money;
    bool operator < (const stu& s2) const{
        return money>s2.money;
    }
}stus[205];
int sum1=0;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>stus[i].name>>stus[i].fs>>stus[i].cs>>stus[i].sl>>stus[i].wp>>stus[i].an;
    }
    for(int i=1;i<=n;i++){
        if(stus[i].fs>80&&stus[i].an>=1)stus[i].money+=8000;
        if(stus[i].fs>85&&stus[i].cs>80)stus[i].money+=4000;
        if(stus[i].fs>90)stus[i].money+=2000;
        if(stus[i].fs>85&&stus[i].wp=='Y')stus[i].money+=1000;
        if(stus[i].cs>80&&stus[i].sl=='Y')stus[i].money+=850;
        sum1+=stus[i].money;
    }
    stable_sort(stus+1,stus+n+1);
    cout<<stus[1].name<<endl;
    cout<<stus[1].money<<endl;
    cout<<sum1;
}

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;
}