WillPam账号被封并不是我搞的。

有人恶意机惨，改了用户名并发布了恶意帖子。

WillPam可以调出后台数据来看登录的IP地址，罪犯最好主动承认。

这里建议使用复活币，奖项认证解封。

h ttps://www.luogu.com.cn/contest/114059

h ttps://www.luogu.com.cn/contest/116264#description

恭喜，您上传的题解 P2199题解 已经通过审核，1小时内在题解界面显示。

全体起立！

所以题目的意思到底是缩内存还是缩长度

前言:时间紧张,只写了两个题的题解,后续会补全(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(即眭鑫)

弱弱地问一句:Mathler给出的数字为99991(质数),有合法六位表达式的值等于这个数吗

在线求Hack数据(别告诉我题目出错了哈)

#12754 Mathler

交互题没有模板,纯靠随心所欲地去模拟

代码量巨大

关键网站上无法评测,很难受.

有做出来的在评论区放代码,我会出数据测试,AC者奖励账号(这次不是小号了哦,但我觉得没人能做对)

先看下Test 5(别的数据也有此情况)

2 9296330

可题目中说的是N(2<=N<=10或N=16)进制数M(100位之内).

2进制的数里出现个9,不正常吧

很早的题目,应该没有官方数据,请老师再看看

还有,Impossible!的情况占了50%,请调整数据占比

http:(有外链不能保存,复制时记得把括号里的删掉)//119.27.163.117/

自己复制去逝逝吧