1152 Google Recruitment
思路：判断素数
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1100;
int a[maxn];
int n,k;
long long getNum(int pos){
long long x = 0;
for(int i=pos;i<=pos+k-1;i++){
x = x*10 + a[i];
}
return x;
}
bool prime(long long x){
if(x < 2) return false;
if(x == 2) return true;
int endss = sqrt(x);
for(int i=2;i<=endss;i++){
if(x%i == 0) return false;
}
return true;
}
void print(long long x){
int len = 0;
long long temp = x;
while(temp){
temp/=10;
len++;
}
if(len == k) {
printf("%lld",x);
return;
}
int t = k - len;
while(t--)printf("0");
printf("%lld",x);
}
int main(){
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%1d",&a[i]);
bool flag = false;
for(int i=1;i+k-1<=n;i++){
long long x = getNum(i);
if(prime(x)){
flag = true;
print(x);
break;
}
}
if(flag == false) puts("404");
return 0;
}
1153 Decode Registration Card of PAT
思路：结构体排序，map计数，string.c_str()把字符串转成字符数组后可以使用print输出
注意：使用太多cin、cout太慢了会超时
#include<bits/stdc++.h>
//#include<unordered_map>
using namespace std;
/*
Cin和Cout不能用太多啦
除了string 和 char类型的输入 最好把Cin替换成scanf
Cout全部换成printf 对于string类型的printf 需要将string转换成字符数组
string.c_str();
*/
const int maxn = 1e4+10;
int n,m;
struct node{
char type;
int site;
string date;
int num;
int score;
string all;
};
struct node stu[maxn];
vector<node> ans;
bool cmp1(node s1,node s2){
if(s1.score == s2.score) {
s1.all < s2.all;
}
return s1.score > s2.score;
}
bool cmp2(node s1,node s2){
if(s1.score > s2.score) return true;
else if(s1.score < s2.score) return false;
return s1.all < s2.all;
}
int mm[1001];
struct nod{
int site;
int num;
nod(int sss,int nnn){
site = sss;
num = nnn;
}
};
vector<nod> ans3;
bool cmp3(nod s1,nod s2){
if(s1.num == s2.num) return s1.site < s2.site;
return s1.num > s2.num;
}
int main(){
// cin>>n>>m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
string str;
int score;
// cin>>str>>score;
cin>>str;
// scanf("%s",&str);
scanf("%d",&score);
stu[i].all = str;
stu[i].score = score;
stu[i].type = str[0];
stu[i].site = (str[1] - '0') * 100 + (str[2] - '0') * 10 + (str[3] - '0');
stu[i].date = str.substr(4,6);
stu[i].num = (str[10] - '0') * 100 + (str[11] - '0') * 10 + (str[12] - '0');
}
for(int Case=1;Case<=m;Case++){
int Type;
// cin>>Type;
scanf("%d",&Type);
int cnt = 0;
ans.clear();
ans3.clear();
if(Type == 1){
char type;
cin>>type;
printf("Case %d: 1 %c
",Case,type);
for(int i=1;i<=n;i++){
if(stu[i].type == type){
ans.push_back(stu[i]);
}
}
cnt = ans.size();
if(cnt == 0){
puts("NA");
}else{
sort(ans.begin(),ans.end(),cmp2);
for(int i=0;i<=cnt-1;i++){
// cout<<ans[i].all<<" "<<ans[i].score<<endl;
printf("%s ",ans[i].all.c_str());
printf("%d
",ans[i].score);
}
}
}else if(Type == 2){
int site;
// cin>>site;
scanf("%d",&site);
printf("Case %d: 2 %d
",Case,site);
int tot = 0;
for(int i=1;i<=n;i++){
if(stu[i].site == site){
tot += stu[i].score;
cnt++;
}
}
if(cnt == 0){
puts("NA");
}else{
printf("%d %d
",cnt,tot);
}
}else if(Type == 3){
string date;
cin>>date;
printf("Case %d: 3 ",Case);
// cout<<date<<endl;
printf("%s
",date.c_str());
for(int i=100;i<=999;i++) mm[i] = 0;
for(int i=1;i<=n;i++){
if(stu[i].date == date){
mm[stu[i].site]++;
}
}
for(int i=100;i<=999;i++){
if(mm[i] != 0){
ans3.push_back(nod(i,mm[i]));
}
}
// map<int, int> mp;
// for(int i=1;i<=n;i++){
// if(stu[i].date == date) mp[stu[i].site]++;
// }
// map<int, int>::iterator it = mp.begin();
// while(it!=mp.end()){
// ans3.push_back(nod(it->first,it->second));
// it++;
// cnt++;
// }
cnt = ans3.size();
if(cnt == 0){
puts("NA");
}else{
sort(ans3.begin(),ans3.end(),cmp3);
for(int i=0;i<=cnt-1;i++){
// cout<<ans3[i].site<<" "<<ans3[i].num<<endl;
printf("%d %d
",ans3[i].site,ans3[i].num);
}
}
}
}
return 0;
}
1154 Vertex Coloring
思路：图论，dfs遍历检查相邻结点的颜色
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;
int n,m,k;
vector<int> g[maxn];
int col[maxn];
int vis[maxn];
set<int> se;
bool flag = false;
void dfs(int x){
if(flag == false) return;
vis[x] = 1;
for(int i=0;i<g[x].size();i++){
int v = g[x][i];
if(col[x] == col[v]) flag = false;
if(!vis[v]) dfs(v);
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
cin>>k;
while(k--){
se.clear();
for(int i=0;i<n;i++){
cin>>col[i];
se.insert(col[i]);
vis[i] = 0;
}
flag = true;
for(int i=0;i<n;i++){
if(flag == false) break;
if(vis[i]) continue;
dfs(i);
}
if(flag) cout<<se.size()<<"-coloring"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
1155 Heap Paths
思路：给定序列，判断是否大根堆、小根堆(特殊二叉树)
#include<bits/stdc++.h>
using namespace std;
const int maxn = 50010;
int n;
int g[maxn];
vector<int> v;
bool flagMin = false;
bool flagMax = false;
bool flag = true;
void dfs(int x){
v.push_back(g[x]);
if(x * 2 + 1 <= n){
dfs(x * 2 + 1);
}
if(x * 2 <= n){
dfs(x * 2);
}
if(x * 2 + 1 > n && x * 2 > n){
int temp = v[0];
if(flag){
int cnt = 0;
for(int i=0;i<v.size();i++){
if(i > 0 && v[i] >= v[i-1]) cnt++;
}
if(cnt == v.size() - 1) flagMax = true;
else if(cnt == 0) flagMin = true;
else flag = false;
}
for(int i=0;i<v.size();i++){
if(i == 0) cout<<v[i];
else cout<<" "<<v[i];
}
if(v.size() != 0) cout<<endl;
}
v.erase(v.end()-1);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>g[i];
dfs(1);
if(flag == false){
cout<<"Not Heap"<<endl;
}else if(flagMin == true && flagMax == false){
cout<<"Max Heap"<<endl;
}else if(flagMin == false && flagMax == true){
cout<<"Min Heap"<<endl;
}else{
cout<<"Not Heap"<<endl;
}
return 0;
}