7-1 String
给定一个只含有小写字母的文本串，给定n个模式串，求每个模式串在文本串中的出现次数。
我的做法是比较两个string：str和strr。 str是文本串，而strr是模式串 。以strr的第一个字符作为标志，在str中找到strr的第一个字符，再分别比较str和strr的每一个字母，匹配上即sum++。
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
| #include <iostream>
#include <cstring>
using namespace std;
int main(){
int N,flag;
string str,sstr;
cin >> N;
cin >> str;
for(int T=1;T<=N;T++){
cin >> sstr;
int num=0;
if(sstr.size()>str.size()){
cout << 0 << endl;continue;
}
for(int i=0;i<=str.size()-sstr.size();i++){
if(str[i]==sstr[0]){
flag=1;
int ip=i;
for(int p=0;p<sstr.size()&&ip<str.size();p++,ip++) if(str[ip]!=sstr[p]) flag=0;
if(flag==1) {
num++;
}
}
}
cout << num << endl;
}
return 0;
}
|
7-2 区间
有一个长为n的序列，一个区间的权值定义为这个区间内不同数字的个数，请在这个序列中找出两段不相交的区间使它们的权值的和最大
- 可以注意到区间越长，权值只增不减，所以应该考虑最长的区间，即两个区间的长度就是原区间的长度。
本题我本来用插板，这应该是正确的思路，但是在找前后区间权值时我用了暴力搜索导致时间耗费太长，所以应该考虑细微一点。插板移动时，有一个数分配给了前面的区间，同时后面的区间少了一个数。每一次移动应该只考虑增减而不是全盘考虑。
我的代码中，tap即插板。插板的位置为正数第tap个数的后面，这样的话，每次变化的数就是a[tap]。
- 同时我利用两个计数器memofront和memoback。
- memofront为前段区间的计数器，实际上应该是判断器，这个memofront的值只有0或1，是因为这个是代表这个数有没有存在过。
- memoback为后段区间的计数器，由于后段区间的特殊性，memoback的意义是这个数出现的次数。只有当memoback[nu]==1时，即减去的这个数为后半区间出现的唯一的数，才能把后面的权值减去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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include <iostream>
using namespace std;
int main(){
int N;
cin >> N;
int memofront[100005],memoback[100005];
int a[N];
for(int i=0;i<N;i++) cin >> a[i];
int tap=1,maxweight=0;
if(N==2) {cout << 2 << endl; return 0;}
for(int i=0;i<100005;i++) {memofront[i]=0;memoback[i]=0;}
int frontweight=0,backweight=0;
for(int i=0;i<tap;i++){
if(memofront[a[i]]==1) continue;
else {
memofront[a[i]]=1;
frontweight++;
}
}
for(int i=tap;i<N;i++){
if(memoback[a[i]]>0) {memoback[a[i]]++;continue;}
else {
memoback[a[i]]=1;
backweight++;
}
}
int weight=frontweight+backweight;
for(tap=1;tap<N-1;tap++){
if(memofront[a[tap]]==0) {frontweight++;memofront[a[tap]]++;}
if(backweight>0){
if(memoback[a[tap]]>1) memoback[a[tap]]--;
else if (memoback[a[tap]]==1) {
memoback[a[tap]]=0;backweight--;
}
}
int weight=frontweight+backweight;
if(weight>maxweight) maxweight=weight;
}
cout << maxweight << endl;
return 0;
}
|
7-3 小步点
众所周知，校园跑使用小步点软件时需要依次经过5个点位，一天Phenix发明了一个范围增强器，当Phenix距离点位R米的时就算经过了该点位，现在Phenix公里数已经达到了2公里，但是还剩两个点位需要经过，现在将校园抽象为一个二维坐标系，假设Phenix在（0,0）点，剩下的第一个点位在（d,n）,第二个在(2d,0)，由于Phenix超过了两公里的部分是一点也不想多跑，所以你需要计算在拥有范围增强器的基础上依次经过这两个点位的最短距离
本人由于数学不好，暴力求解了。。。
由于精度不高，能暴力求解。
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 <cmath>
using namespace std;
double distant(double x,double y,double a,double b){
return sqrt((x-a)*(x-a)+(y-b)*(y-b));
}
int main(){
double R,d,n,S,min=9999;
int flag=0;
cin >> R >> d >> n;
double l1,l2;
for(double i=d-R;i<d+R;i=i+0.01){
for(double j=n-R;j<n+R;j=j+0.01){
if(distant(i,j,d,n)<=R){
S=distant(i,j,0,0)+distant(i,j,2*d,0)-R;
if(flag==0) {
min=S;
flag=1;
}
}
if(S<min) min=S;
}
}
printf("%.2lf",min);
return 0;
}
|
7-4 分糖果
现在有n个糖果和一群小朋友，第一个小朋友拥有这n个糖果，他现在有两种选择①分给第二个小朋友x个，x必须是n的约数，且x<n②全部自己留着，第二个小朋友同样也是要么分自己拥有糖果数的约数个给下一个小朋友，要么全留着，以此类推。现在给出第一个小朋友的糖果数n，询问有多少种分法。
这里我用的是递归，定义一个函数表示n个的分发，因为分发都是一样的解法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include <iostream>
using namespace std;
int func(int n){
int sum=0;
if(n==1) return 1;
else{
sum=0;
for(int i=1;i<n;i++){
if(n%i==0) sum=sum+func(i);
}
}
return sum;
}
int main(){
int N;
cin >> N;
cout << func(N)*2 << endl;
return 0;
}
|
7-5 找眼镜
一天Phenix的眼镜被俱乐部某个成员拿了，然后所有的俱乐部成员围成了一个圈，每个人都有个编号，按逆时针递增，而且每个人都有朝向（面向圈内或者圈外），Phenix需要询问编号为1的同学是谁拿的眼镜，但是俱乐部成员很团结不会出卖队友，只会告诉他，例如“眼镜藏在我左数第3个人的右数第1个人的左数第2个人那里”这种形式。现在给出每个人的朝向和名字，和1号同学给出的提示，你需要帮他找出是谁拿的眼镜。
我用一个结构体fri来表示一个人的编号和名字，实际上顺着题目走就可以了。
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
| #include <iostream>
using namespace std;
struct fri{
int to;
string name;
};
int main(){
int n,m,toward,num,point,pointend;
cin >> n >> m;
struct fri frien[n];
for(int T=0;T<n;T++){
cin >> frien[T].to >> frien[T].name;
}
point = 0;
for(int t=1;t<=m;t++){
toward=0;num=0;
cin >> toward >> num;
if(toward==1&&frien[point].to==1) point=point-num;
else if(toward==0&&frien[point].to==0) point=point-num;
else if(toward==1&&frien[point].to==0) point=point+num;
else if(toward==0&&frien[point].to==1) point=point+num;
while(point<0) point=point+n;
while(point>=n) point=point-n;
}
cout << frien[point].name;
return 0;
}
|
7-6 恰早饭
Phenix今天又有早八，由于他喜欢卡点到，所以只给自己留了T分钟的时间吃饭。鹏远餐厅有n道菜，每道菜有一个快乐值v和用餐时间t，意为Phenix可以花t分钟吃掉这道菜，然后获得v的快乐值。但是如果吃早饭的时间太长了，导致他迟到了他也会感到不开心，具体的，如果t > T,他获得的快乐值就是v-(t-T)。现在请你计算Phenix吃掉某一道菜能获得的最大快乐值
这道题一开始我以为是背包问题把我吓傻了，后来发现不是背包，而且特简单。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include <iostream>
using namespace std;
int main(){
int n,T;
cin >> n >> T;
int time[n],happy[n];
for(int i=0;i<n;i++) cin >> happy[i] >> time[i];
bool flag=false;
int happymax,happymagic;
for(int i=0;i<n;i++){
if(time[i]<=T) happymagic=happy[i];
else happymagic=happy[i]-(time[i]-T);
if(flag==false) {happymax=happymagic;flag=true;}
else if(happymagic>happymax) happymax=happymagic;
}
cout << happymax << endl;
return 0;
}
|