目录
签到题
题目大意：
科学家发现远古用牛来运算（还是牛自己会运算，反正就是会运算），而挖掘的泥板中记载了运算的数和结果。想请你根据输入的数、运算法则和结果来检验是否正确。
解题思路：
只是一个四进制运算，把输入的四进制数转换为二进制，然后根据运算结果在转换为四进制，在与输入的结果比较就可以了。
代码：
#include <cstdio>
using namespace std;
//一个开关，检测输入的数是结果还是运算的数字
int kg=0;
//设置二进制数
void SetBit(unsigned short &s,int i,int v){
if(v){
s |= (1<<i);
}
else{
s &= ~(1<<i);
}
}
//换算
void hs(unsigned short &s,char c[]){
int i=4,j=0;
if(kg==1) i=7;
for(;i>=0;i--,j+=2){
switch(c[i]){
case 'V':
SetBit(s,j,0);
SetBit(s,j+1,0);
break;
case 'U':
SetBit(s,j,1);
SetBit(s,j+1,0);
break;
case 'C':
SetBit(s,j,0);
SetBit(s,j+1,1);
break;
case 'D':
SetBit(s,j,1);
SetBit(s,j+1,1);
break;
}
}
}
int main(void)
{
int n,p1=0,p2=0,p3=0;
unsigned short nm[20]={0},result[10]={0},emp[10]={0};
char zf[30],hc[9];
scanf("%d",&n);
//输入数据并且换算成二进制
for(int i=0;i<n*6;i++){
scanf("%s",hc);
if(i%6<2){
kg=0;
hs(nm[p1],hc);
p1++;
}
else if((i+1)%6==0&&i!=0){
kg=1;
hs(result[p3],hc);
p3++;
}
else{
zf[p2]=hc[0];
p2++;
}
}
//printf("%u %u\n",nm[2],nm[3]);
p1=0,p2=0;
for(int i=0;i<n*3;i+=3){
for(int j=i;j<i+3;++j){
switch(zf[j]){
case 'A':
nm[p2+1]=nm[p2]+nm[p2+1];
break;
case 'R':
nm[p2+1]=nm[p2+1]>>2;
break;
case 'L':
nm[p2+1]=nm[p2+1]<<2;
break;
case 'N':
break;
}
}
emp[p1++]=nm[p2+1];
p2+=2;
}
p1=0,p2=0;
puts("COWCULATIONS OUTPUT");
for(int i=0;i<n;i++){
//printf("%u %u\n",result[i],emp[i]);
if(result[i]==emp[i])
puts("YES");
else
puts("NO");
}
puts("END OF OUTPUT");
return 0;
}
dp签到题
题目大意：
有一个序列，从中找出最大连续序列，并且要输出他的起点和终点。
解题思路：
求解最优解往往可以用到动态规划，这里面我们可以定义
d
p
[
i
]
:
=
dp[i]:=
dp[i]:=以
i
i
i为终点的最大连续序列，而
s
t
a
r
t
[
i
]
:
=
start[i]:=
start[i]:=为以
i
i
i结尾的最大连续序列的起点。那么
d
p
[
i
]
=
(
d
p
[
i
−
1
]
+
a
[
i
]
≥
a
[
i
]
?
d
p
[
i
−
1
]
+
a
[
i
]
:
a
[
i
]
)
，
p
o
i
n
t
dp[i]=(dp[i-1]+a[i]≥a[i]?dp[i-1]+a[i]:a[i])，point
dp[i]=(dp[i−1]+a[i]≥a[i]?dp[i−1]+a[i]:a[i])，point是保存首序号的临时量，注意
p
o
i
n
t
point
point初值是1。
代码：
#include<iostream>
using namespace std;
const int N = 1e5+5;
int a[N];
int dp[N];
int start[N];
int n,t;
int main(){
cin>>t;
for(int k=1;k<=t;++k){
int point=1;
cout<<"Case "<<k<<":"<<endl;
cin>>n;
dp[0]=0;
for(int i=1;i<=n;++i) cin>>a[i];
for(int i=1;i<=n;++i){
if(dp[i-1]+a[i]>=a[i]){
dp[i]=dp[i-1]+a[i];
start[i]=point;
}else{
dp[i]=a[i];
start[i]=point=i;
}
}
int maxn=dp[1],ins=1;
for(int i=2;i<=n;i++){
if(dp[i]>maxn){
maxn=dp[i];ins=i;
}
}
cout<<maxn<<' '<<start[ins]<<' '<<ins<<endl;
if(k!=t) cout<<endl;
}
return 0;
}
这已经不是我能力范围内的题了
题目大意：
一堆石头，分成两堆，用程序检测是否能完美平分。
解题思路：
多重背包解题，我们看能否拿出石头装满总价值一半的石头，如果能就输出yes否则输出no。但是每种石头最多有20000个，所以会超时，但是可以用二进制优化，将多重背包问题转换为01背包问题。但其实这道题可以用dfs解决
代码：
#include <iostream>
using namespace std;
int stone[7],sum;
bool dfs(int cap,int value){
int i,temp;
if(value==sum) return 1;
//枚举拿石头
for(i=cap;i>=1;i--)
if(stone[i]){
temp=value+i;
//如果还有空间就下一层
if(temp<=sum){
stone[i]--;
if(dfs(i,temp)) return true;
}
}
return false;
}
int main(){
int flag,i,t;
for(t=1;;t++){
for(flag=sum=0,i=1;i<=6;i++){
cin>>stone[i];
sum+=i*stone[i];
if(!flag && stone[i]) flag=1;
}
if(!flag) break;
cout<<"Collection #"<<t<<":\n";
if(sum&1){
cout<<"Can't be divided.\n\n";
continue;
}
sum=sum>>1;
if(dfs(6,0))
cout<<"Can be divided.\n\n";
else
cout<<"Can't be divided.\n\n";
}
return 0;
}
遇到过的题
题目大意：
已知一张纸的长宽，求划分的矩形的周长小于k的方式有多少种
解题思路：
在长为
n
n
n，宽为
m
m
m的矩形上，长为
i
i
i，宽为
j
j
j的矩阵个数为
(
n
−
i
+
1
)
∗
(
m
−
j
+
1
)
(n-i+1) * (m-j+1)
(n−i+1)∗(m−j+1)，记
j
=
k
/
2
−
i
(
j
>
0
)
,
k
j = k / 2 - i(j>0),k
j=k/2−i(j>0),k为周长,
i
i
i为长,
j
j
j为宽, 在
j
≤
m
j \le m
j≤m时, j可以取
1
,
2
,
3...
j
1,2,3...j
1,2,3...j 所以答案为
a
n
s
=
(
n
−
i
+
1
)
∗
(
m
−
1
+
1
)
+
(
n
−
i
+
1
)
∗
(
m
−
2
+
1
)
+
…
+
(
n
−
i
+
1
)
∗
(
m
−
j
+
1
)
,
ans = (n - i + 1)*(m - 1 + 1) + (n - i + 1)*(m - 2 + 1) + … + (n - i + 1)*(m - j + 1),
ans=(n−i+1)∗(m−1+1)+(n−i+1)∗(m−2+1)+…+(n−i+1)∗(m−j+1),提取
(
n
−
i
+
1
)
,
(n - i + 1),
(n−i+1), 就是一个等差数列, 所以
a
n
s
+
=
(
n
−
i
+
1
)
∗
(
2
∗
m
−
j
+
1
)
∗
j
/
2
ans += (n - i + 1)*(2 * m - j + 1)*j / 2
ans+=(n−i+1)∗(2∗m−j+1)∗j/2
代码：
#include<iostream>
using namespace std;
typedef long long ll;
int main()
{
ll m, n, k;
while (cin>>m>>n>>k)
{
k /= 2;
ll ans = 0;
for (ll i = 1; i <= n; i++)
{
if (i>k - 1) break;
ll x = k - i;
x = min(x, m);
ans += (n - i + 1)*(m*x - (1 + x)*x / 2 + x);
}
cout<<ans<<endl;
}
return 0;
}
只是凑个数，很难的
题目大意：
胖子跳跳舞机，但是很累。每首歌有一个箭头序列，他必须按照这个序列依次用某一只脚跳，但是每次跳必须保证不能两只脚踏在同一个踏板上，但可以同时待在中心。每次只能动一只脚，另一只脚保持在原地。跳舞的方式可以可以用
l
1
l
2
l
3
.
.
.
l
n
l_1l_2l_3...l_n
l1l2l3...ln来表示，
l
i
=
0
l_i=0
li=0，表示为用左脚踩第
i
i
i个箭头，反之亦然。跳完后他要计算所消耗的体力。从中心移到任何一个箭头为2单位体力，任何一个箭头移到相邻的箭头消耗为3单位体力，移到对称则消耗4单位体力，留在原地消耗1单位体力。怎样才能最少体力跳完给定舞曲呢？
解题思路：
怀特先生需要作出一系列决策：对于每个舞步
i
i
i，选择他移动的脚
f
o
o
t
[
i
]
foot[i]
foot[i]，并把它移动到目标
A
i
A_i
Ai（这是已知的）。一个决策序列对于一个可行解，而他需要从中选出体力消耗最少的。
这里提到无后效性，也就是动态规划中，当前决策并不是由以前的决策决定，而是有当前某种状态决定。
根据这个性质，又可以用递归的思路解题：枚举第
i
i
i次所作的决策，计算出到达状态s，递归从状态s出发进行动态决策。如果跳到第
k
k
k个舞步时左脚在位置
x
x
x，右脚在位置
y
y
y时所需要耗费的最小体力记为
d
[
x
,
y
,
k
]
d[x,y,k]
d[x,y,k]，那么合法的决策有：
- 决策一： 把一只脚从中心移到目标位置；
- 决策二： 一只脚移到相邻位置；
- 决策三： 一只脚移到到相对位置；
- 决策四： 一只脚原地再踩一下；
代码：
'''
代码就不写了
'''