前言:时间紧张,只写了两个题的题解,后续会补全(6.1号肯定完结)

对比赛的评价:

题目较难,数据较水,是一场值得用来练习的比赛(常州市的题目果然名不虚传)

同时,比赛也完美诠释了"十年OI一场空,不开long long见祖宗"的深刻道理.

进入正题

A题 矩形纸片(rectangle) 题目链接

送分题,不应该错,正确做法有两种:

·总覆盖面积=纸片1覆盖的面积+纸片2覆盖的面积-重叠部分,时间复杂度O(1),但不推荐,难算,耗时间且易算错.(能不优化坚决不优化)

·穷举,用数组记录每一个被覆盖的点,均设为1,最后计数,时间复杂度O(ab+cd),推荐,易懂.

第二种做法:

#include<iostream>
using namespace std;
int a,b,c,d,x,y,i,j,f[5005][5005];
long long S;
int main(){
    cin>>a>>b>>c>>d>>x>>y;
    for(i=1;i<=a;i++)
        for(j=1;j<=b;j++)
            f[i][j]=1,S++;
    for(i=x;i<c+x;i++)
        for(j=y;j<d+y;j++)
                S=(!f[i][j])?S+1:S;
    cout<<S;
    return 0;
}

B题 ABC 字符串(string) 题目链接

一步一步来,先看操作ABC->BCA,可以视为把后面的BC和前面的A位置交换.

BC不断往前进,A不断往后退,只要BC前面有A,操作数+1.

所以可以得出代码:

#include<bits/stdc++.h>
using namespace std;
string s;
int i,L,ans;
void work(){
    ans++,L++;
    swap(s[i],s[i+1]);
    swap(s[i+1],s[i+2]);
    return;    
}
int main(){
    cin>>s;
    for(i=0;i<s.length();i++)
        if(s[i]=='A'&&s[i+1]=='B'&&s[i+2]=='C'){
            L=0;
            work();
            while(s[--i]=='A'&&i>=0)
                work();
            i+=L;
        }
    cout<<ans;
    return 0;
}

But,超时了.

怎样解决?——来时记录连续A的个数(即最多操作数),遇到BC时累加起来(跳过BC,但记录连续A的个数的变量不要清空,后面再有BC可能会连接上去).

改进代码,时间复杂度为O(n)

#include<bits/stdc++.h>
using namespace std;
string s;
int i,L,ans;
int main(){
    cin>>s;
    for(i=0;i<s.length();i++){
        if(s[i]=='B'&&s[i+1]=='C')
            ans+=L,i++;
        else{
            if(s[i]=='A')
                L++;
            else
                L=0;
        }
    }
    cout<<ans;
    return 0;
}

但最后一个数据点WA了,怎么回事？

回收开头:"十年OI一场空,不开long long见祖宗",彦祖,数据这么大,开long long啊

#include<bits/stdc++.h>
using namespace std;
string s;
long long i,L,ans;
int main(){
    cin>>s;
    for(i=0;i<s.length();i++){
        if(s[i]=='B'&&s[i+1]=='C')
            ans+=L,i++;
        else{
            if(s[i]=='A')
                L++;
            else
                L=0;
        }
    }
    cout<<ans;
    return 0;
}

OK,搞定

C题 数学作业 (fib) 题目链接

这题很简单,不要看那数据范围那么大,其实搜索不会超时的

只要你搜索方向是对的

正常搜索都是从小往大了搜,但如果这样,50分带走

有效剪枝,从大往小搜,当后面数的和加上当前的和＜n时就停止.

还有,注意long long.

另外,dfs别忘了参数也设为long long(不然80分错得莫名其妙)

#include<iostream>
using namespace std;
long long a[100],f[100],L,n,ans;
void dfs(long long x,int p){    
    if(x>n)
        return;
    if(x==n){
        ans++;
        return;
    }
    for(int i=p;i>0;i--)
        if(!f[i]&&n-x-a[i]<a[i]*2)
            f[i]=1,dfs(x+a[i],i-1),f[i]=0;
}
int main(){
    cin>>n;
    a[1]=1,a[2]=2;L=3;
    while(a[L-1]<=n)
        a[L]=a[L-1]+a[L-2],L++;
    dfs(0,L-1);
    cout<<ans;
    return 0;
}

片尾
博主提醒您:规则千万条,诚信第一条;学术不规范,封号两行泪.
别再抄袭了,没有意义的！
黑名单:Joker(即眭鑫)