A题:
由于太菜而一直没有AC。其实是一道01背包。。最后才AC的
01背包什么的自己去了解就行了吧
因为我(DP)太烂,所以不会(DP)的我也救不了了
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define MAXN 222
int f[MAXN][MAXN],d[MAXN],p[MAXN];
int main()
{
int n,m,s;
scanf("%d%d%d",&n,&m,&s);
for (int i=1;i<=n;i++)
{
scanf("%d%d",&d[i],&p[i]);
}
for (int i=1;i<=n;i++)
{
for (int j=m;j>=0;j--)
{
if (j>=d[i])
{
f[i][j]=max(f[i][j],max(f[i-1][j-d[i]]+p[i],f[i-1][j]+s));
}
else
{
f[i][j]=f[i-1][j]+s;
}
}
}
printf("%d",f[n][m]);
}
(B)题:
字符串膜你题。
用(char[])存储整个串,判断到四个目标串的首字母的时候直接枚举判断就行了。。
或者每次用(string)读入一整个单词,同上,枚举判断。(反正就是裸的字符串暴力膜你 咋写都行。。)
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
string s;
int f1=0,f2=0,f3=0,f4=0;
string s1="sing",s2="dance",s3="rap",s4="basketball";
void c1(int l)
{
int tot=0;
for (int i=l;i<=l+3;i++)
{
if (s[i]!=s1[tot++])
{
return;
}
}
f1++;
return;
}
void c2(int l)
{
int tot=0;
for (int i=l;i<=l+4;i++)
{
if (s[i]!=s2[tot++])
{
return;
}
}
f2++;
return;
}
void c3(int l)
{
int tot=0;
for (int i=l;i<=l+2;i++)
{
if (s[i]!=s3[tot++])
{
return;
}
}
f3++;
return;
}
void c4(int l)
{
int tot=0;
for (int i=l;i<=l+9;i++)
{
if (s[i]!=s4[tot++])
{
return;
}
}
f4++;
return;
}
int main()
{
bool flag=1;
while (flag==1)
{
cin>>s;
int len=s.size();
for (int i=0;i<len;i++)
{
if (s[i]=='s')
{
c1(i);
continue;
}
if (s[i]=='d')
{
c2(i);
continue;
}
if (s[i]=='r')
{
c3(i);
continue;
}
if (s[i]=='b')
{
c4(i);
continue;
}
}
if (s[len-1]=='@')
{
flag=0;
break;
}
}
printf("sing : %d
",f1);
printf("dance : %d
",f2);
printf("rap : %d
",f3);
printf("basketball : %d
",f4);
return 0;
}
(C)题:
是个什么鬼题目
(30)分做法:输出(1)
(70)分做法:输出(2)
以上纯属瞎说233,下面是真题解
结论题。应该很多人都发现了结果是(1)或者(2)(23333)
至于为什么除1之外,都满足偶数答案为(1),奇数答案为(2),
首先需要了解一下位运算。
异或运算(^):
同0异1。
比如说(10^2),
(10)的二进制:(1) (0) (1) (0)
(02)的二进制:(0) (0) (1) (0)
(00)计算结果:(1) (0) (0) (0)
所以(10^2=8)。
就是各个对应二进制位,如果两位相同即为0,不同即为1。
(最后一行的00是用来占位的不用理w)
与运算(&):
皆1为1否则为0。
(10&2=2)
或运算(&):
皆0为0否则为1。
(10&2=10)
(自行膜你)
正题。
对于(1):
(1) (xor) (1=0)。通过上面的解释我们知道 (n xor n=0)。
对于一个(非0)偶数(n):
(n) (and) (1=0)。
由于(n)是一个偶数,所以(n)的二进制末位为(0)。
(n) (and) (1)即:
(xxxxxxxxxxxxx0)
&
(0000000000001)
。
(and)运算必须满足对应的二进制位都为(1),对应的结果位才为(1)。由于(1)的二进制除了末位都为(0),所以(n)除了末尾以外的二进制位都被清零。
而(n)本身的末位就为(0),所以结果末位也为(0)。
所以若(n)为偶数,满足(n) (and) (1=0)。
即(ans=1)。
对于一个(非1)奇数(n):
由于(n)是一个奇数,所以(n)的二进制末位为(1)。
那么可以通过(n) (xor) (1)使得(n)变成一个偶数。
即:
(xxxxxxxxxxxxx1)
^
(0000000000001)
=
(xxxxxxxxxxxxx0)
那么我们通过花费(1)就使得一个奇数变成了一个偶数。接下来的操作就和偶数的处理方式一样了。
所以若(n)为一个(非1)奇数,(ans=2)。
所以这道题差不多就是个判断奇偶性233
但是看到数据范围:(10^{10000})
这个时候就可以用字符串存储,直接挑最后一位来判断就行了。。
记得判断(1)的时候别忘了判断字符串长度为(1)啊23333
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int n,m;
string s;
int main()
{
cin>>s;
int len=s.size();
int n=s[len-1]-'0';
if (len==1&&n==1)
{
printf("1");
return 0;
}
if (!(n&1))
{
printf("1");
return 0;
}
printf("2");
return 0;
}
(D)题:
签到题!
(AC)数还是令人满意的。。
等差数列和等比数列的基本性质大家应该都了解w。
正常的等差数列判断:(b-a==c-b)
正常的等比数列判断:(b/a==c/b)
这个时候的卡点:
在验题的时候发现一个问题,有人用一个(int)变量来存储(b/a)以及(c/b)
于是有了这么一个数据:
(12) (23) (45)
然后可想而知233
接着想卡一下(b/a==c/b)做法的,于是有了这么三个数据:
1.(0) (0) (0)
2.(0) (0) (1)
3.(0) (1) (2)
这个时候正确的写法是,判断(a*c==b*b)。
接着想到输入都在(int)范围内,于是又出了两个个数据来卡:
2000000000 1 2000000000 (卡单独(int)变量存)
15970 1006110 63384930 ((ans)超出(int)范围)
记住,输入在(int)范围内,并不代表计算过程和输出在int范围内233
别的数据点都正常啦w。。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int main()
{
// freopen("test4.in","r",stdin);
// freopen("test4.out","w",stdout);
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if (a==0&&b==0&&c==0)
{
printf("Arithmetic progression!
0
");
return 0;
}
if (b==0||c==0)
{
printf("N0!!!!!
");
return 0;
}
if (a==0)
{
if (b-a==c-b)
{
printf("Arithmetic progression!
%d
",c+c-b);
return 0;
}
}
if ((a*c==b*b)&&(b-a==c-b))
{
printf("YE5!
%d %lld
",c+c-b,(long long)c/b*c);
return 0;
}
if (a*c==b*b)
{
printf("Geometric progression!
%lld
",(long long)c/b*c);
return 0;
}
if (b-a==c-b)
{
printf("Arithmetic progression!
%d
",c+c-b);
return 0;
}
printf("N0!!!!!
");
return 0;
}
感谢 陈浩宇 在验题中发现了标程的错误
感谢 林倩瑜 在验题中给了出题人更加(duliu)的数据灵感
最终感谢(wjd),(xn),(zzx)学长们辛勤地为了初一OIer们的成长出题(
(我好咸啊233 不刷题在这里写题解)