外面下著瘋狂暴雨
應該是學生時代的最後一個暑假
- Jul 10 Sun 2016 17:46
7月10號
- Mar 14 Mon 2016 23:23
FIND MY WAY
- Sep 11 Fri 2015 11:49
UVa - 10008 What's Cryptanalysis?
#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);
// getchar();
// getchar();
getline(std::cin,str);
while(n--)
{
//printf("PIG!\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
- Sep 11 Fri 2015 11:47
UVa - 10959 The Party, Part I
#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; //printf("%d %d %d",j,answer[i],answer[j]); } } } } } for(int i=1; i<p; i++) { printf("%d\n",answer[i]); } if(test) { printf("\n"); } } }
#tree #BFS
- Sep 11 Fri 2015 11:43
UVa - 10954 Add All
#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
- Sep 11 Fri 2015 11:39
UVa - 10034 Freckles
#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)); //printf("%f\n",len); 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
- Sep 11 Fri 2015 11:36
UVa - 10327 Flip Sort
#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
- Sep 11 Fri 2015 11:31
UVa - 11988 Broken Keyboard (a.k.a. Beiju Text)
#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> 型態的應用