1140 Look-and-say Sequence
思路：模拟
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int d,n;
const int maxn = 10010;
int cnt[11];
vector<int> a;
vector<int> b;
int main(){
scanf("%d%d",&d,&n);
a.push_back(d);
if(n == 1) {
printf("%lld",d);
return 0;
}
for(int i=2;i<=n;i++){
int j = 0;
b.clear();
int len = a.size();
while(j < len){
int curv = a[j];
int cnt = 0;
while(j<len && a[j] == curv){
cnt++;
j++;
}
b.push_back(curv);
b.push_back(cnt);
}
a.clear();
for(int j=0;j<b.size();j++) a.push_back(b[j]);
}
for(int i=0;i<a.size();i++){
printf("%d",a[i]);
}
return 0;
}
1141 PAT Ranking of Institutions
思路：结构体排序，map统计查询
#include<bits/stdc++.h>
#include<algorithm>
#include<string>
using namespace std;
int n;
const int maxn = 1e5+10;
struct node{
string id;
double score;
string cap;
};
struct node stu[maxn];
map<string,int> mp;
map<string,double> scores;
struct capNode{
string cap;
int score;
int nums;
capNode(string ss,double cc,int num){
cap = ss;
score = cc;
nums = num;
}
};
vector<capNode> vec;
bool cmp(capNode x,capNode y){
if(x.score == y.score) {
if(x.nums == y.nums) return x.cap < y.cap;
return x.nums < y.nums;
}
return x.score > y.score;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
string curCap;
cin>>stu[i].id>>stu[i].score>>curCap;
transform(curCap.begin(),curCap.end(),curCap.begin(),::tolower);
stu[i].cap = curCap;
mp[stu[i].cap]++;
if(stu[i].id[0] == 'T'){
scores[stu[i].cap] += stu[i].score*1.5;
}else if(stu[i].id[0] == 'A'){
scores[stu[i].cap] += stu[i].score;
}else{
scores[stu[i].cap] += stu[i].score*1.0/1.5;
}
}
map<string,int>::iterator it = mp.begin();
while(it!=mp.end()){
string name = it->first;
int num = it->second;
int sc = (int)scores[name];
vec.push_back(capNode(name,sc,num));
it++;
}
sort(vec.begin(),vec.end(),cmp);
int len = vec.size();
printf("%d
",len);
if(len > 0){
int lastScore = vec[0].score;
int rank = 1;
for(int i=0;i<len;i++){
if(vec[i].score == lastScore){
cout<<rank<<" "<<vec[i].cap<<" "<<vec[i].score<<" "<<vec[i].nums<<endl;
}else{
rank = i+1;
lastScore = vec[i].score;
cout<<rank<<" "<<vec[i].cap<<" "<<vec[i].score<<" "<<vec[i].nums<<endl;
}
}
}
return 0;
}
1142 Maximal Clique
思路：图论，判断是否同一“集合”，按题目要求判断是否有边
#include<bits/stdc++.h>
using namespace std;
const int maxn = 210;
int n,ne;
int m;
int g[maxn][maxn];
int a[maxn];
int vis[maxn];
int k;
bool isClique(){
for(int i=1;i<=k;i++){
for(int j=1;j<=k;j++){
if(i!=j && g[a[i]][a[j]] == 0) return false;
}
}
return true;
}
bool isMaxClique(){
for(int i=1;i<=n;i++) vis[i] = 0;
for(int i=1;i<=k;i++) vis[a[i]] = 1;
for(int i=1;i<=n;i++){
if(!vis[i]){
for(int p=1;p<=k;p++){
for(int q=1;q<=k;q++){
if(p != q || (k==1)){ //这里特判k==1的情况 如样例图中查询1 8:8号结点应该输出Not Maximal
if(g[i][a[p]]==1 && g[i][a[q]] == 1){
return false;
}
}
}
}
}
}
return true;
}
int main(){
scanf("%d%d",&n,&ne);
for(int i=1;i<=ne;i++){
int u,v;
scanf("%d%d",&u,&v);
g[u][v] = g[v][u] = 1;
}
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d",&k);
for(int j=1;j<=k;j++) scanf("%d",&a[j]);
bool flag1 = isClique();
bool flag2 = isMaxClique();
if(flag1 == false){
puts("Not a Clique");
}else{
if(flag2 == false){
puts("Not Maximal");
}else{
puts("Yes");
}
}
}
return 0;
}
1143 Lowest Common Ancestor 29/30
思路：给先序序列建树，找最近公共祖先
一个点段错误，有时间再补。。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;
int m,n;
struct node{
int v;
node *l;
node *r;
};
int a[maxn];
set<int> se;
int deep[maxn];
int fa[maxn];
void getDeep(node *root,int depth,int father){
if(root == NULL) return;
deep[root->v] = depth;
fa[root->v] = father;
if(root->l != NULL) getDeep(root->l,depth+1,root->v);
if(root->r != NULL) getDeep(root->r,depth+1,root->v);
}
void build(int pos,node *root){
if(root == NULL) return;
node* fa = root;
int v = a[pos];
if(v < fa->v){
if(fa->l == NULL){
node *cur = new node();
cur->v = v;
cur->l = NULL;
cur->r = NULL;
fa->l = cur;
return;
}
build(pos,fa->l);
}else{
if(fa->r == NULL){
node *cur = new node();
cur->v = v;
cur->l = NULL;
cur->r = NULL;
fa->r = cur;
return;
}
build(pos,fa->r);
}
return;
}
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
se.insert(a[i]);
}
node *Root = new node();
Root->l = NULL;
Root->r = NULL;
if(n>=1) Root->v = a[1];
else Root->v = 0;
if(n>=2) for(int i=2;i<=n;i++) build(i,Root);
getDeep(Root,1,0);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
bool visu = true;
bool visv = true;
if(se.find(u) == se.end()) visu = false;
if(se.find(v) == se.end()) visv = false;
if(visu == false || visv == false){
if(visu==false && visv==false) printf("ERROR: %d and %d are not found.
",u,v);
else if(visu == false) printf("ERROR: %d is not found.
",u);
else printf("ERROR: %d is not found.
",v);
}else{
if(deep[u] < deep[v]){
int p = u;
int q = v;
while(deep[q] > deep[p]) q = fa[q];
if(q == p) printf("%d is an ancestor of %d.
",u,v);
else{
while(p != q){
p = fa[p];
q = fa[q];
}
printf("LCA of %d and %d is %d.
",u,v,p);
}
}else{
int p = u;
int q = v;
while(deep[p] > deep[q]) p = fa[p];
if(p == q) printf("%d is an ancestor of %d.
",v,u);
else{
while(p != q){
p = fa[p];
q = fa[q];
}
printf("LCA of %d and %d is %d.
",u,v,p);
}
}
}
}
return 0;
}