此帖是为纪念自己第一次AK周赛,hhhhh(虽然很简单,但是过程坎坷啊)
T1.判断数字
思路:算出给出数字中的4和7的个数,它们之和若为4或者7就输出YES
(貌似就是把题目说了一遍,hh)
需要注意给出数字的范围需要用long long来存储
AC代码:
#include<iostream>
using namespace std;
typedef long long ll;
int cal(ll x,int c){
int res=0;
while(x){
if(x%10==c){
res++;
}
x/=10;
}
return res;
}
int main(){
ll n;
cin>>n;
int ans=cal(n,4)+cal(n,7);
if(ans==4||ans==7){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
return 0;
}
T2.最长合法括号子序列
思路:当且仅当(
的数量大于)
数量时可选择(
或者)
,或者(
的数量等于)
数量时我们只能选择)
。最后选出的数量减去(
比)
多的数量就是答案。
AC代码:
#include<iostream>
using namespace std;
const int N=1e6+10;
int main(){
string str;
cin>>str;
int n=str.size();
int ans=0,cnt=0;
for(int i=0;i<n;i++){
if(cnt>0){
if(str[i]=='('){
cnt++;
}
else{
cnt--;
}
ans++;
}
else if(cnt==0&&str[i]=='('){
cnt++,ans++;
}
}
ans-=cnt;
cout<<ans<<endl;
return 0;
}
T3.电话号码
思路:
使用unordered_map套上vector,然后去重,最后去掉所有是其他号码后缀的号码就是答案。
坑点:find函数从左往右找第一个找到的元素,例如下面示例代码:
string s="33",a="3";
cout<<s.find(a)<<endl;
输出是0
而不是1
。(血的教训啊)
技巧:使用rfind函数,从后往前找的函数
下面这样写ck函数也可以
bool ck(string nm,string tel){
int sz=mp[nm].size();
int c=tel.size();
for(int i=0;i<sz;i++){
int pos=mp[nm][i].rfind(tel);
if(pos!=mp[nm][i].npos&&pos!=0&&pos==mp[nm][i].size()-c){
return false;
}
}
return true;
}
AC代码:
#include<iostream>
#include<unordered_map>
#include<vector>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
unordered_map<string,vector<string>> mp,ans;
int n,cnt;
bool ck(string nm,string tel){
int sz=mp[nm].size();
int c=tel.size();
for(int i=0;i<sz;i++){
string ss="";
if(mp[nm][i].size()>c){
ss=mp[nm][i].substr(mp[nm][i].size()-c);
if(ss==tel){
// cout<<ss<<endl;
return false;
}
}
}
return true;
}
int main(){
cin>>n;
string nm,tel;
for(int i=0;i<n;i++){
cin>>nm>>cnt;
for(int j=0;j<cnt;j++){
cin>>tel;
mp[nm].push_back(tel);
}
}
for(unordered_map<string,vector<string>>::iterator pos=mp.begin();pos!=mp.end();pos++){
sort((pos->second).begin(),(pos->second).end());
(pos->second).erase(unique((pos->second).begin(),(pos->second).end()),(pos->second).end());
int sz=(pos->second).size();
for(int i=0;i<sz;i++){
if(ck(pos->first,(pos->second)[i])){
ans[pos->first].push_back((pos->second)[i]);
}
}
}
cout<<ans.size()<<endl;
for(unordered_map<string,vector<string>>::iterator pos=ans.begin();pos!=ans.end();pos++){
int sz=(pos->second).size();
cout<<pos->first<<" "<<sz;
for(int i=0;i<sz;i++){
cout<<" "<<pos->second[i];
}
cout<<endl;
}
return 0;
}