#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <iostream>
#include <stdlib.h>
struct T
{
char ch;
int Fre=0;
};
bool operator < (const T &lhs,const T &rhs)
{
return lhs.Fre > rhs.Fre;
}
int main()
{
T record[26];
int count=0;
int n;
std::string str;
scanf("%d",&n);
getline(std::cin,str);
while(n--)
{
getline(std::cin,str);
for(int i=0;i<str.length();i++)
{
if(isalpha(str[i]))
{
if(! record[toupper(str[i])-'A'].Fre)
{
record[toupper(str[i])-'A'].ch = toupper(str[i]);
}
record[toupper(str[i])-'A'].Fre++;
}
}
}
std::stable_sort(record,record+26);
for(int i=0;i<26;i++)
{
if(record[i].Fre)
printf("%c %d\n",record[i].ch,record[i].Fre);
}
return 0;
}
#英文字元處理#sort
Nate_Tang 發表在 痞客邦 留言(0) 人氣()
#include <queue>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
int visit[1001];
int adj[1001][1001];
int main()
{
queue<int>q;
int test=0;
char blank[10];
int p,d;
scanf("%d",&test);
getchar();
gets(blank);
while(test--)
{
scanf("%d%d",&p,&d);
for(int i=0; i<p; i++)
{
visit[i]=false;
}
for(int i=0; i<p; i++)
{
for(int j=0; j<p; j++)
{
adj[i][j]=false;
}
}
while(d--)
{
int temp1,temp2;
scanf("%d%d",&temp1,&temp2);
adj[temp1][temp2]=true;
adj[temp2][temp1]=true;
}
int answer[1001]={};
for(int k=0; k<p; k++)
{
if(!visit[k])
{
q.push(k);
visit[k]=true;
while(!q.empty())
{
int i= q.front();
q.pop();
for(int j=0; j<p; j++)
{
if(adj[i][j]&&!visit[j])
{
q.push(j);
visit[j]=true;
answer[j]=answer[i]+1;
}
}
}
}
}
for(int i=1; i<p; i++)
{
printf("%d\n",answer[i]);
}
if(test)
{
printf("\n");
}
}
}
#tree #BFS
Nate_Tang 發表在 痞客邦 留言(0) 人氣()
#include <cstdio>
#include <queue>
using namespace std;
int main()
{
long long int N, x;
while (scanf("%d", &N) && N)
{
priority_queue<int, vector<int>, greater<int>> PQ;
for (int i = 0; i < N; ++i)
{
scanf("%d", &x);
PQ.push(x);
}
long long int cost = 0;
while (PQ.size() != 1)
{
x = PQ.top();
PQ.pop();
x += PQ.top();
PQ.pop();
cost += x;
PQ.push(x);
}
printf("%lld\n", cost);
}
return 0;
}
#priority-queue
Nate_Tang 發表在 痞客邦 留言(0) 人氣()
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <queue>
#include <math.h>
#include <algorithm>
using namespace std;
struct edge
{
int a,b;
double dis;
bool operator < (const edge &s2) const
{
return dis > s2.dis;
}
};
struct point
{
double x,y;
};
point P[105];
int root[105];
int find(int x)
{
if(x== root[x])return x;
else return root[x]=find(root[x]);
}
int un (int a,int b)
{
int ra=find(a);
int rb=find(b);
if(ra != rb)
{
root[ra]=root[rb];
return 1;
}
return 0;
}
void init ()
{
for(int i=0; i<105; i++)
{
root[i]=i;
}
}
priority_queue<edge> pq;
int main()
{
int test=0;
scanf("%d",&test);
string str;
while(test--)
{
getchar();
getline(cin,str);
int num=0;
scanf("%d",&num);
init();
for(int i=0; i<num; i++)
{
scanf("%lf%lf", &P[i].x, &P[i].y);
}
int edge_count=0;
for(int i=0; i<num; i++)
{
for(int j=i+1; j<num; j++)
{
double len = sqrt(pow(P[i].x - P[j].x, 2) + pow(P[i].y - P[j].y, 2));
pq.push( {i,j,len} );
}
}
edge E;
int num2=0;
double cost=0;
while(num2+1<num && !pq.empty())
{
E=pq.top();
pq.pop();
if(un(E.a,E.b))
{
num2++;
cost+=E.dis;
}
}
printf("%.2f\n\n",cost);
}
}
#kruskal's 用到sort 和 dependent set
Nate_Tang 發表在 痞客邦 留言(0) 人氣()
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
int main()
{
int n=0;
while(scanf("%d",&n)!=EOF){
int input[n];
for(int i=0;i<n;i++)
{
input[i]=0;
scanf("%d",&input[i]);
}
int count=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n-1;j++)
{
if(input[j]>input[j+1])
{
std::swap(input[j],input[j+1]);
count+=1;
}
}
}
printf("Minimum exchange operations : %d\n",count);
}
return 0;
}
#buble_sort #swap
Nate_Tang 發表在 痞客邦 留言(0) 人氣()
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <list> #include <iostream>
using namespace std;
list<char> text;
list<char>::iterator it=text.begin();
int main()
{
char input[100001];
while(scanf("%s",input)!=EOF)
{
int length = strlen(input); text.clear();
it = text.begin();
for(int i=0; i<length; i++)
{
if(input[i]=='[')it=text.begin();
else if(input[i]==']')it=text.end();
else
{
text.insert(it,input[i]);
}
}
for(it=text.begin(); it!=text.end(); it++) printf("%c",*it);
printf("\n");
}
return 0;
}
#<list> 型態的應用
Nate_Tang 發表在 痞客邦 留言(0) 人氣()
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
struct DNA
{
char word[1000];
int sort;
};
bool operator < (const DNA &lhs,const DNA &rhs)
{
return lhs.sort < rhs.sort;
}
DNA str[110]= {0,0};
int main()
{
int i, j, k, t, n, m;
char blank[10];
scanf("%d",&t);
getchar();
while (t--)
{
gets(blank);
scanf("%d %d",&n,&m);
for (i=0 ; i<m ; i++)
{
str[i].sort=0;
scanf(" %s",str[i].word);
for (j=0 ; j<n ; j++)
{
for (k=j+1 ; k<n ; k++)
{
if (str[i].word[j]>str[i].word[k])
{
str[i].sort++;
}
}
}
}
stable_sort(str,str+m);
for (i=0 ; i<m ; i++) {
printf("%s\n",str[i].word);
}
if (t) printf("\n");
getchar();
}
}
Nate_Tang 發表在 痞客邦 留言(0) 人氣()
Nate_Tang 發表在 痞客邦 留言(0) 人氣()