6.3 string
【例】A1140 Look-and-say Sequence (20 分)
Look-and-say 看图说话
ATTENTION
string的+=会比+快很多很多，空间也会省很多很多。 这道题用=会超时。- 获取一个字符串连续数字的个数：将
pre初始化为字符串的第一个字符，并且将 cnt初始化为0（因为第一个字符还会被比较一次，所以初始化为0）。遍历字符串，直到遇到一个不同的字符，此时前一个字符的数量就是cnt，保存。并且更新pre为当前字符，cnt为1，当前字符也要被计算。继续遍历即可。对于最后一串相同的字符，需要在循环结束后对齐保存。
char pre=str1[0];
int cnt=0;
for(int i=0;i<str1.size();i++)
{
if(str1[i]==pre)
cnt++;
else
{
pre=str1[i];
str2=str2+str1[i-1]+(char)(cnt+'0');
cnt=1;
}
}
str2=str2+str1[str1.size()-1]+(char)(cnt+'0');
- 记一下数字转
string的函数：to_string(x)。很实用。 - 这道题的题干难读.jpg
- 表示依旧不懂为什么题目里说了D不为1，样例里D就为1了orz…This definition works for D = 1 as well. …艹
#include <iostream>
#include <string>
using namespace std;
int n;
string str1,str2;
int main()
{
ios::sync_with_stdio(false);
cin>>str1>>n;
n--;
while(n--)
{
str2="";
int idx=0;
while(idx<str1.size())
{
int i;
for(i=idx+1;i<str1.size();i++)
{
if(str1[i]!=str1[idx])
break;
}
int cnt=i-idx;
str2+=str1[idx]+to_string(cnt);
idx+=cnt;
}
str1=str2;
}
cout<<str1<<endl;
return 0;
}
【例】A1060
【例】A1100 Mars Numbers (20 分)
ATTENTION
- 这道题麻烦就麻烦在13的整数倍和0的处理。
对于13的整数倍，并不是像十进制那样，输出10/20等等，而是只输出十位数！ - 所以，在自然数转火星文时，判断自然数num是否大于等于13。如果小于13，则一定是一位火星文。如果大于13，再判断num/13是否为0，如果是0，只输出十位，否则要输出十位和个位。
- 还有需要注意的是，在处理进制转换时，使用
while(num)一定要特别处理num=0的情况！！！ - 火星文转自然数时，根据火星文的长度判断是两位数还是一位数。注意
tret是三个字符啊啊啊！！！还要注意空格哇哇哇！！！ - 由于输入可能有空格，所以不能用
cin，用getline哈。然后用getline的话，记得用getchar吞到前面那个cin遗留下来的换行符。
cin>>str;
遇到空格、tab、回车等空白符即结束读入
getline(cin,str);
头文件：#include < string > ，可接受空白符并输出
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
const string ge[13]={"tret","jan","feb","mar","apr","may","jun","jly","aug","sep","oct","nov","dec"};
const string higher[13]={"","tam","hel","maa","huh","tou","kes","hei","elo","syy","lok","mer","jou"};
int n;
int main()
{
cin>>n;
getchar();
for(int i=0;i<n;i++)
{
string str;
getline(cin,str);
if(str[0]>='0'&&str[0]<='9')
{
int num=0;
for(int j=0;j<str.size();j++)
num=num*10+(str[j]-'0');
bool flag=false;
vector<string> ans;
if(num==13)
ans.push_back(higher[1]);
else
{
if(num==0)
ans.push_back(ge[0]);
while(num)
{
int cur=num%13;
num/=13;
if(!flag)
{
if(cur!=0)
ans.push_back(ge[cur]);
flag=true;
}
else
ans.push_back(higher[cur]);
}
}
for(int j=ans.size()-1;j>=0;j--)
{
if(j!=0)
cout<<ans[j]<<" ";
else
cout<<ans[j];
}
cout<<endl;
}
else
{
int res=0;
if(str.size()>4)
{
string s1=str.substr(0,3);
for(int j=0;j<13;j++)
{
if(higher[j]==s1)
res=j*13;
}
string s2=str.substr(4,str.size()-4);
for(int j=0;j<13;j++)
{
if(ge[j]==s2)
res+=j;
}
}
else
{
for(int j=0;j<13;j++)
{
if(higher[j]==str)
res=j*13;
}
for(int j=0;j<13;j++)
{
if(ge[j]==str)
res+=j;
}
}
cout<<res<<endl;
}
}
return 0;
}
【例】A1084 Broken Keyboard (20 分)
worn out 疲惫不堪的；耗尽的
original a.原来的，开始的
typed-out 输入
detect v.检测
captilize vt. 用大写字母写或印刷;
ATTENTION
- 大小写不敏感。
- 按检测到的顺序输出
- 其实不用存储在vector中，直接输出就行了。
- 柳神使用的
str.find()。对于s1中的每个字符，在s2和ans中进行查找，如果他在s2中找不到，并且他的大写形式在ans中找不到的话，说明第一次遇到这个worn out键，把他加入ans中。最后输出ans即可。
#include <iostream>
#include <string>
#include <vector>
#include <set>
using namespace std;
string s1,s2;
bool vis[100]={0};
vector<char> ans;
int main()
{
cin>>s1>>s2;
for(int i=0;i<s2.size();i++)
{
if(s2[i]>='a'&&s2[i]<='z')
s2[i]=s2[i]-'a'+'A';
if(s2[i]>='0'&&s2[i]<='9')
vis[s2[i]-'0']=1;
else if(s2[i]>='A'&&s2[i]<='Z')
vis[s2[i]-'A'+20]=1;
else
vis[50]=1;
}
for(int i=0;i<s1.size();i++)
{
int idx=0;
if(s1[i]>='a'&&s1[i]<='z')
s1[i]=s1[i]-'a'+'A';
if(s1[i]>='0'&&s1[i]<='9')
idx=s1[i]-'0';
else if(s1[i]>='A'&&s1[i]<='Z')
idx=s1[i]-'A'+20;
else
idx=50;
if(vis[idx]==0)
{
ans.push_back(s1[i]);
vis[idx]=1;
}
}
for(int i=0;i<ans.size();i++)
cout<<ans[i];
return 0;
}
【例】A1132 Cut Integer (20 分)
an even number 偶数
an odd number 奇数
ATTENTION
substr(起始位置，子串长度);int a = stoi(str);
#include <iostream>
#include <string>
using namespace std;
int n;
string str;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>str;
int len=str.size()/2;
int a=stoi(str.substr(0,len));
int b=stoi(str.substr(len,len));
int c=stoi(str);
if(a*b!=0&&c%(a*b)==0)
cout<<"Yes\n";
else
cout<<"No\n";
}
return 0;
}
6.9 algorithm头文件
【例】A1141 PAT Ranking of Institutions (25 分)
ATTENTION
- PAT真的好喜欢多关键词排序[○･｀Д′･ ○]
- 这道题的因素好多，没想到柳神把
tws和ns单独存储在了map里！！这样就不用去找school对应的idx了！妙妙子！！！ #include <unordered_map> 不需要map的排序功能时可以用它，快！（map默认升值排序）
#include <iostream>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
int n;
map<string,int> schoolToIdx;
map<int,string> idxToSchool;
struct institution{
int rank;
int nb,na,nt;
string school;
int tes;
int ns;
institution()
{
nb=na=nt=0;
ns=0;
tes=0;
}
}ins[100010];
int idx=1;
bool cmp(institution &a,institution &b)
{
if(a.tes==b.tes)
if(a.ns==b.ns) return a.school<b.school;
else return a.ns<b.ns;
else
return a.tes>b.tes;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
string id,sch;
int score;
cin>>id>>score>>sch;
for(int j=0;j<sch.size();j++)
if(sch[j]>='A'&&sch[j]<='Z')
sch[j]=sch[j]-'A'+'a';
if(schoolToIdx[sch]==0)
{
ins[idx].school=sch;
schoolToIdx[sch]=idx;
idxToSchool[idx++]=sch;
}
int schIdx=schoolToIdx[sch];
if(id[0]=='A')
ins[schIdx].na+=score;
else if(id[0]=='B')
ins[schIdx].nb+=score;
else
ins[schIdx].nt+=score;
ins[schIdx].ns++;
}
for(int i=1;i<idx;i++)
ins[i].tes=(int)(ins[i].na*1.0)+(ins[i].nb/1.5)+(ins[i].nt*1.5);
sort(ins+1,ins+idx,cmp);
cout<<idx-1<<"\n";
ins[1].rank=1;
cout<<ins[1].rank<<" "<<ins[1].school<<" "<<ins[1].tes<<" "<<ins[1].ns<<"\n";
for(int i=2;i<idx;i++)
{
if(ins[i].tes==ins[i-1].tes)
ins[i].rank=ins[i-1].rank;
else
ins[i].rank=i;
cout<<ins[i].rank<<" "<<ins[i].school<<" "<<ins[i].tes<<" "<<ins[i].ns<<"\n";
}
return 0;
}
【例】A1083 List Grades (25 分)
ATTENTION
sort函数的头文件：#include <algorithm>vector使用sort函数时，使用迭代器说明排序区间。
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
struct PER{
string name,id;
int grade;
PER(string n,string i,int g)
{
name=n;
id=i;
grade=g;
}
};
vector<PER> stu;
int n,g1,g2;
bool cmp(PER a,PER b)
{
return a.grade>b.grade;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
string s1,s2;int g;
cin>>s1>>s2>>g;
PER tmp(s1,s2,g);
stu.push_back(tmp);
}
cin>>g1>>g2;
bool flag=false;
sort(stu.begin(),stu.end(),cmp);
for(int i=0;i<stu.size();i++)
{
if(stu[i].grade<=g2&&stu[i].grade>=g1)
{
flag=true;
cout<<stu[i].name<<" "<<stu[i].id<<endl;
}
}
if(!flag)
cout<<"NONE";
return 0;
}
【例】A1080 Graduate Admission (30 分)
proceed v.开始
automate v.自动化
admission n.录用
national entrance exam 全国入学考试
quota n.定额; 限额; 配额
exceed v.超过
ATTENTION
- 可以直接用GE+GI作为排序的第一标尺。因为GE+GI不会超出int范围，还能避免出现小数。
sort函数的头文件：#include <algorithm>vector使用sort函数时，使用迭代器说明排序区间。- 排序函数
cmp使用&引用传参，可以节约时间，例如：bool cmp(peo& a, peo& b)。 - **输出时的换行，最后一行也要有换行。**看来PAT里的题目，按行输出结果时，每一行都要换行。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,k;
int tot[110];
int curRank[110]={0};
vector<int> ans[110];
struct Stu{
int ge,gi,ave,rank;
int idx;
vector<int> choice;
Stu()
{
rank=0;
}
}stu[40010];
bool cmp(Stu a,Stu b)
{
if(a.ave==b.ave)
return a.ge>b.ge;
return a.ave>b.ave;
}
int main()
{
scanf("%d %d %d",&n,&m,&k);
for(int i=0;i<m;i++)
scanf("%d",&tot[i]);
for(int i=0;i<n;i++)
{
scanf("%d %d",&stu[i].ge,&stu[i].gi);
stu[i].ave=(stu[i].ge+stu[i].gi)/2;
stu[i].idx=i;
for(int j=0;j<k;j++)
{
int tmp;
scanf("%d",&tmp);
stu[i].choice.push_back(tmp);
}
}
sort(stu,stu+n,cmp);
for(int i=0;i<n;i++)
{
stu[i].rank=i+1;
if(i>0&&stu[i].ave==stu[i-1].ave&&stu[i].ge==stu[i-1].ge)
{
stu[i].rank=stu[i-1].rank;
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<stu[i].choice.size();j++)
{
if(ans[stu[i].choice[j]].size()<tot[stu[i].choice[j]])
{
ans[stu[i].choice[j]].push_back(stu[i].idx);
curRank[stu[i].choice[j]]=stu[i].rank;
break;
}
else if(ans[stu[i].choice[j]].size()>=tot[stu[i].choice[j]])
{
if(stu[i].rank==curRank[stu[i].choice[j]])
{
ans[stu[i].choice[j]].push_back(stu[i].idx);
curRank[stu[i].choice[j]]=stu[i].rank;
break;
}
}
}
}
for(int i=0;i<m;i++)
{
sort(ans[i].begin(),ans[i].end());
}
for(int i=0;i<m;i++)
{
for(int j=0;j<ans[i].size();j++)
{
if(j!=ans[i].size()-1)
printf("%d ",ans[i][j]);
else
printf("%d",ans[i][j]);
}
printf("\n");
}
return 0;
}
【例】A1153 Decode Registration Card of PAT (25 分)
registration n. 登记；注册；挂号
site n. 地点；位置；场所
specify vt. 指定；详细说明；列举；把…列入说明书
query n. [计] 查询
tie n.平局
ATTENTION
- 看错考场范围了呜呜呜TAT
- 白瞎了好多时间啊啊啊啊啊啊！！！
#include <cstdio>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
struct Per{
string id;
int score;
}per[10010];
struct Site{
string s;
int cnt;
Site(){
s="000";
cnt=0;
}
}site[1010];
int n,m,type;
string term;
bool cmp1(Per &a,Per &b)
{
if(a.score==b.score)
return a.id<b.id;
return a.score>b.score;
}
bool cmp2(Site &a,Site &b)
{
if(a.cnt==b.cnt)
return a.s<b.s;
return a.cnt>b.cnt;
}
void caseOne()
{
sort(per,per+n,cmp1);
bool flag=false;
for(int i=0;i<n;i++)
{
if(per[i].id[0]==term[0])
{
flag=true;
printf("%s %d\n",per[i].id.c_str(),per[i].score);
}
}
if(!flag) printf("NA\n");
}
void caseTwo()
{
int nt=0,ns=0;
for(int i=0;i<n;i++)
{
if(per[i].id.substr(1,3)==term)
{
nt++;
ns+=per[i].score;
}
}
if(nt==0) printf("NA\n");
else printf("%d %d\n",nt,ns);
}
void caseThree()
{
for(int i=0;i<1010;i++)
site[i].cnt=0;
bool flag=false;
for(int i=0;i<n;i++)
{
if(per[i].id.substr(4,6)==term)
{
flag=true;
int idx=(int)(per[i].id[1]-'0')*100+(int)(per[i].id[2]-'0')*10+(int)(per[i].id[3]-'0');
site[idx].cnt++;
site[idx].s=per[i].id.substr(1,3);
}
}
sort(site,site+1010,cmp2);
if(!flag) printf("NA\n");
else
{
for(int i=0;i<1010;i++)
{
if(site[i].cnt!=0)
printf("%s %d\n",site[i].s.c_str(),site[i].cnt);
}
}
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
{
cin>>per[i].id>>per[i].score;
}
for(int i=0;i<m;i++)
{
cin>>type>>term;
printf("Case %d: %d %s\n",i+1,type,term.c_str());
if(type==1)
{
caseOne();
}
else if(type==2)
{
caseTwo();
}
else if(type==3)
{
caseThree();
}
else
printf("NA\n");
}
return 0;
}
|