1、Count PAT’s (25)
题目：给一段由PAT三个字母组成的字符串，看里面能组成几个Pat。
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
int coun(string a)
{
int pnum=0;//pnum存的是p有几个
vector<int> anum,tnum;//anum存的是当前这个a前面有几个p，tnum存的是当前这个a后面有几个t
for(int i=0;i<a.size();i++)
{
if(a[i]=='P') pnum=(pnum+1)%1000000007;
else if(a[i]=='A')
if(pnum!=0)
{
anum.push_back(pnum);
tnum.push_back(0);
}
else if(a[i]=='T')
if(anum.empty()!=1)
for(int j=0;j<tnum.size();j++)
tnum[j]=(tnum[j]+1)%1000000007;
}
int ans=0;
for(int i=0;i<anum.size();i++)//针对每一个a，看他前后有几个p和t，就可以知道一共有几个pat
ans=(ans+(anum[i]*tnum[i])%1000000007)%1000000007;
return ans%1000000007;
}
int main()
{
//freopen("a.txt","r",stdin);
string a; cin>>a;
cout<<coun(a)<<endl;
return 0;
}看了别人的答案，巧妙的一个方法！
#include <iostream>//牛客网的答题记录上转载来的！写的太棒了！
#include <string>
#include <stdio.h>
using namespace std;
int main()
{
string str; cin >> str;
int p=0, pa=0, pat=0, len = str.length();
for(int i=0; i<len; i++) {
if(str[i] == 'P') {
p++;//当前出现了几个p
} else if(str[i] == 'A') {
pa += p; pa %= 1000000007;//每遇到一个a就加上前面p的个数，就是当前pa出现的次数
} else {
pat += pa; pat %= 1000000007;//每遇到一个t加上前面pa出现的次数，就是当前pat出现次数
}
}
printf("%d", pat);
return 0;
}2、To Buy or Not to Buy (20) 水题
给定两个字符串a,b。看a是否包含了b里的所有的字符。如果包含所有的字符，看多出来几个字符。如果没有包含所有的字符看少了几个。明显使用hash的方法。
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int j[75];
void pan(string a1,string a2)
{
for(int i=0;i<a2.size();i++)
j[a2[i]-'0']++;
for(int i=0;i<a1.size();i++)
j[a1[i]-'0']--;
int yu=0,mei=0;
for(int i=0;i<75;i++)
{
if(j[i]<0) mei+=j[i];
else yu+=j[i];
}
if(yu!=0) cout<<"No "<<yu<<endl;
else cout<<"Yes "<<mei*(-1)<<endl;
}
int main()
{
//freopen("a.txt","r",stdin);
memset(j,0,sizeof(int)*75);
string a1,a2; cin>>a1>>a2;
pan(a1,a2);
return 0;
}3、Insert or Merge (25)
给N，和长度为N的原字符串和排序中间状态的字符串。看是插入排序还是归并排序，并且给出下一个改变的状态（注意！一定是改变的！）插入排序是前j个是顺序的，后面的与原字符串的状态相同，归并排序是两种方法一种递归一种是2的倍数，这里是用的2的倍数的方法。
#include <iostream>
#include <stdio.h>
#include<algorithm>
using namespace std;
void Insert_sort_now(int* yuan,int* pai,int N,int d)
{
for(int i=d;i<N;i++)
{int j=0;
for(;j<i;j++) if(pai[j]>pai[i]) break;
int h=j;
for(;j<i;j++) pai[i-j+h]=pai[i-j+h-1];
pai[i-j+h]=yuan[i];
if(h!=i) break;//注意一定要有这个！因为很可能状态并没有改变！
}
for(int i=0;i<N-1;i++) cout<<pai[i]<<" ";
cout<<pai[N-1];
}
bool ifsorted(int* pai,int n,int N)
{ int h=0; int k=n;
for(;k<N;h=k,k+=n)
{ for(int hh=h;hh<k-1;hh++)
if(pai[hh]>pai[hh+1]) return false;
}
for(int hh=k-n;hh<N-1;hh++)//最后的一个bin可能不足n个所以要单独拿出来
if(pai[hh]>pai[hh+1])return false;
return true;
}
void Merge_sort(int* pai,int b,int e,int N,int d)
{
int n=2;
while(n<=d)
{
if(ifsorted(pai,n,N)!=true)//如果bin为n没有被排序那么下一个状态就是n被排序之后的样子
{
int h=0; int k=n;
for(;k<N;h=n,k+=n) sort(pai+h,pai+k);
sort(pai+k/2,pai+N);
return ;
}
n*=2;
}
int h=0;int k=n;
for(;k<N;h=n,k+=n) sort(pai+h,pai+k);
sort(pai+k-n,pai+N);
return ;
}
void pai(int* yuan,int* pai,int N)
{
int i=0;//插入排序前面都是顺序的一直到变小了，从这个小的数开始所有的数与原始的序列一样
for(;i<(N-1);i++) if(pai[i]>pai[i+1]) break;
i++; int jj=i;//jj是下一个需要被排序的位置，jj前面都是顺序的
for(;i<N;i++) if(yuan[i]!=pai[i]) break;
if(i==N)
{
cout<<"Insertion Sort"<<endl;
Insert_sort_now(yuan,pai,N,jj);//jj对于归并排序是最大的可能已经被排序的bin
}
else{
cout<<"Merge Sort"<<endl;
Merge_sort(pai,0,N-1,N,jj)
for(int pp=0;pp<N-1;pp++)
cout<<pai[pp]<<" ";
cout<<pai[N-1];
}
}
int main()
{
//freopen("a.txt","r",stdin);
int y,N; cin>>N; int g[N],p[N];
for(int i=0;i<N;i++) cin>>g[i];
for(int i=0;i<N;i++) cin>>p[i];
pai(g,p,N);
return 0;
}
4、Linked List Sorting (25)
给定一个链表，输入链表长度和头结点。之后给出每个结点的头结点，key值和下一个结点。之后将这个链表按照Key值重新排序，即下一个结点的值要改变了。输出排序后的结点个数（注意！链表里很可能存在某个点不在这个头结点开始的链表里）
注意Map本身是有排序的
#include <bits/stdc++.h>
using namespace std;
map<string,int> mapdtov;
map<string,string> mapdtod;
bool cmp(string a,string b)
{ return mapdtov[a]<mapdtov[b]; }
void pai(int N,string beginy)
{
vector<string> yuan;
if(beginy=="-1")//注意临界条件！
{
cout<<"0 -1"<<endl;
return;
}
while(beginy.compare("-1"))//string比较可以用str.compare("")==true就代表是""了
{
yuan.push_back(beginy);
beginy=mapdtod[beginy];
}
sort(yuan.begin(),yuan.end(),cmp);
int i=0; cout<<yuan.size()<<" "<<yuan[0]<<endl;
for(;i<yuan.size()-1;i++) cout<<yuan[i]<<" "<<mapdtov[yuan[i]]<<" "<<yuan[i+1]<<endl;
cout<<yuan[i]<<" "<<mapdtov[yuan[i]]<<" "<<"-1"<<endl;
}
int main()
{
// freopen("a.txt","r",stdin);
int N;string beginy; cin>>N>>beginy;
for(int i=0;i<N;i++)
{
string d,nd; int v; cin>>d>>v>>nd;
mapdtov[d]=v; mapdtod[d]=nd;
}
pai(N,beginy);
return 0;
}5、Path of Equal Weight (30)
给一个树结构，找这个树上等于给定weight的所有的路径,明显使用dfs
#include <s/stdc++.h>
using namespace std;
struct node
{
int biao;
int value;
vector<int> next;
node(int v) {value=v;}
};
map<int, node*> iton;
vector<vector<int> > DFS(int nodenow,int weight)
{
vector<vector<int> > ans;
if(iton[nodenow]->next.empty()==1)
{
if(weight==iton[nodenow]->value)
{
vector<int> ansnow;
ansnow.push_back(iton[nodenow]->value);
ans.push_back(ansnow);
}
return ans;
}
else
{
for(int i=0;i<iton[nodenow]->next.size();i++)
{
vector<vector<int> > jj=DFS(iton[nodenow]->next[i],weight-iton[nodenow]->value);
if(jj.size()!=0)
{
for(int j=0;j<jj.size();j++)
{
jj[j].insert(jj[j].begin(),iton[nodenow]->value);
ans.push_back(jj[j]);
}
}
}
return ans;
}
}
bool cmp(int a,int b)
{
return iton[a]->value>iton[b]->value;
}
int main()
{
//freopen("a.txt","r",stdin);
int num,nnum,weight; cin>>num>>nnum>>weight;
for(int i=0;i<num;i++)
{
int v;cin>>v;
node* now=new node(v);
iton[i]=now;
}
for(int i=0;i<nnum;i++)
{
int nn,ge; cin>>nn>>ge;
for(int j=0;j<ge;j++)
{
int k;cin>>k;
iton[nn]->next.push_back(k);
}
sort(iton[nn]->next.begin(),iton[nn]->next.end(),cmp);
}
vector<vector<int> > ans;
if(iton.empty()==1) cout<<"";
else ans=DFS(0,weight);
for(int i=0;i<ans.size();i++){
for(int j=0;j<ans[i].size();j++)
cout<<ans[i][j]<<" ";
cout<<endl;}
return 0;
}
但是在牛客网的答题记录上看到一个大佬的方法：其实
不用深搜也不用广搜
，在输入的时候直接标记所有的叶子节点，然后对每个节点设置一个父指针。最后对于所有的叶子节点，根据他的父指针从下向上累加，把所有符合条件的节点保存下来，然后排一下序输出！很好！（有时间要实现一下！）
6、The Dominant Color (20)
相当于求一个序列里出现次数最多的数字,最开始用的hash。
#include <bits/stdc++.h>
using namespace std;
map<int,int> k;
int main()
{// freopen("a.txt","r",stdin);
int M,N; cin>>M>>N;
for(int i=0;i<M*N;i++)
{int h; cin>>h; k[h]++；}
int a1=0,a2=0;//a1代表出现次数最多的那个数字的数字 a2代表a1出现的次数
for(map<int,int>::iterator it=k.begin();it!=k.end();it++)
{if(a2 < it->second)
{
a1=it->first;
a2=it->second;
}
}
cout<<a1; return 0;
}之后发现了一个很好的方法
#include <bits/stdc++.h>
using namespace std;
int main() //方法2，找到出现次数最多的那个数，用string存数。int cnt 存相对从出现次数。如果cnt等于0.ans=now。否则。如果ans==now cnt++, ans!=now cnt--。这样就可以得到相对出现
{
// freopen("a.txt","r",stdin);
int M,N; cin>>M>>N;
int cnt=0;string now;string ans;
for(int i = 0; i < N; ++i)
for(int j = 0; j < M; ++j){
cin>>now;
if(cnt==0){ans=now;cnt++;}
else if(ans.compare(now)){cnt--;}//如果相等则compare的结果是0.
else cnt++;
}
cout<<ans; return 0;
}
版权声明：本文为qq_33666011原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。