2008年5月28日
#include<iostream>
#include<queue>
#include<cmath>
using namespace std;
struct NODE
{
int p_x,p_y,step,c_x,c_y,d;
};
queue<NODE> que;
const int MAXN = 100;
bool p[MAXN][MAXN][4],c[MAXN][MAXN];
int map[MAXN][MAXN];
int mv[4][2]={-1,0,0,1,1,0,0,-1},p_sm,p_sn,c_sm,c_sn,m,n;
void init ( )
{
memset(p,false,sizeof(p));
for ( int i=0 ; i<m ; i++ )
for ( int j=0 ; j<n ; j++ )
{
scanf("%d",&map[i][j]);
if ( map[i][j]==4 )
p_sm=i,p_sn=j;
else
if ( map[i][j]==2 )
c_sm=i,c_sn=j;
}
}
int bfs ( )
{
NODE temp,go;
int i;
temp.p_x = p_sm;
temp.p_y = p_sn;
temp.c_x = c_sm;
temp.c_y = c_sn;
temp.step = 0;
temp.d=0;
for ( i=0 ; i<4 ; i++ )
{
p[p_sm][p_sn][i]=true;
temp.d=i;
que.push(temp);
}
c[c_sm][c_sn]=true;
while ( !que.empty () )
{
NODE head=que.front();
que.pop() ;
for ( i=0 ; i<4 ; i++ )
{
int tm=head.p_x+mv[i][0] , tn=head.p_y+mv[i][1] ;
if ( tm>=0 && tm<m && tn>=0 && tn<n && !p[tm][tn][i] && i!=(head.d+2)%4 && map[tm][tn]!=1 )
{
double t=sqrt( (double)( (tm-head.c_x)*(tm-head.c_x) ) +(double)( (tn-head.c_y)*(tn-head.c_y) ));
if ( t <= sqrt(2.0) && t>0 )
{
go=head;
go.p_x = tm;
go.p_y = tn;
go.step ++ ;
go.d=i;
p[tm][tn][i]=true;
que.push(go);
}
else
{
int tmm=tm+mv[i][0] , tnn=tn+mv[i][1];
if ( t==0 && tmm>=0 && tmm<m && tnn>=0 && tnn<n && map[tmm][tnn]!=1 && !c[tmm][tnn] )
{
go.c_x = tmm ;
go.c_y = tnn ;
go.p_x = tm;
go.d=i;
go.p_y = tn;
go.step = head.step+1;
if ( map[tmm][tnn]==3 )
return go.step ;
c[tmm][tnn]=true;
p[tm][tn][i]=true;
que.push(go);
}
}
}
}
}
return -1;
}
int main ( )
{
while ( scanf("%d%d",&n,&m)!=EOF )
{
init();
printf("%d\n",bfs());
// que.
}
}
2008年5月7日
#include<iostream>
#include<string>
using namespace std;
class FIELDDiagrams
{
public:
void dfs ( int k, int max, int n , long long& sum , int a )
{
int i;
if ( max==n )
{
sum++;
return;
}
if (( k-1)*a+1<max-n )
return ;
for ( i=a ; i>=1 ; i-- )
dfs(k-1,max,n+i ,sum , i );
}
long long countDiagrams ( int t )
{
long long map[40][40],sum=0,i;
memset(map,0,sizeof(map));
for ( i=1 ; i<=t*(t-1)/2 ; i++ )
dfs( t, i,0,sum, i );
return sum;
}
};
int main ( )
{
FIELDDiagrams a;
int n;
while (cin>>n)
cout<<a.countDiagrams (n)<<endl;
}
2008年4月16日
2008年4月3日
2008年4月2日
#include<iostream>
#include<sstream>
#include<map>
#include<string>
#include<vector>
#include<iomanip>
#include<fstream>
#include<algorithm>
using namespace std;
typedef map< string , vector<int> > WORD;
void init ( WORD & m )
{
ifstream fin;
fin.open("keywords.txt");
string keyword;
while ( fin>>keyword )
m[keyword];
fin.close();
}
void count ( WORD & m )
{
int line=0;
ifstream fin;
fin.open("text.txt");
string str;
while ( getline(fin,str) )
{
line++;
for ( WORD::iterator iter = m.begin () ; iter!=m.end( ); iter++ )
if ( str.find ( iter->first )!=string::npos )
m[iter->first].push_back(line);
}
fin.close();
}
void only( WORD &m )
{
for ( WORD::iterator i=m.begin() ; i!=m.end(); i++ )
{
vector<int>::iterator new_end=unique(i->second.begin(),i->second.end());
i->second.erase(new_end,i->second.end());
}
}
void sort_list ( WORD m , map<int,string> &mm )
{
for ( WORD::iterator iter_m = m.begin() ; iter_m != m.end() ; iter_m++ )
mm[iter_m->second .size ()]=iter_m->first;
}
void output ( WORD m , map<int,string> mm )
{
string keyword;
for ( map<int,string>::reverse_iterator iter=mm.rbegin() ; iter!=mm.rend() ; iter++ )
{
cout<<setw(10)<<iter->second<<":"
<<"(";
for ( vector<int>::iterator iter_vector=m[iter->second].begin() ; iter_vector!=m[iter->second].end(); iter_vector++ )
{
if ( iter_vector!=m[iter->second].begin() )
cout<<",";
cout<<*iter_vector;
}
cout<<")"<<endl;
}
}
int main ()
{
WORD m;
map<int , string> mm;
init(m);
count(m);
sort_list(m,mm);
only(m);
output(m,mm);
}
2008年3月31日
我就是不理解這個投票規(guī)則，對這題整整困惑了12個小時，從下午5點到凌晨5點。。。。。。。
Long March Voting
Description
Instant run-off voting is a system for selecting the most preferred candidate in an election. At the beginning of the process, each voter ranks the candidates from most preferred to least preferred. A series of automated voting rounds are then held to determine the overall winner.
In each round, each voter casts a single vote for his most preferred remaining candidate. If a candidate receives strictly more than 50% of the votes cast in that round, that candidate is declared the winner of the election. Otherwise, the candidate with the fewest votes in that round is eliminated, and another round is held. If multiple candidates are tied for the least number of votes, they are all eliminated. If all the candidates are eliminated, the election ends without a winner.
You are given the preferences of the voters in an election, and you must determine the outcome. There are M candidates numbered 0 to M-1, inclusive. The preferences are given in N lines, where each element describes the preferences of a single voter. This is a permutation of the digits 0 to M-1 in decreasing order of preference. In other words, the first digit is the voter's most preferred candidate, the second digit is his second most preferred candidate, and so on.
Input
There are several test cases,each test case begins with a integer N(1<=N<=50),means there are N voters.The next N lines,each contains a string with the same lenth M(1<=M<=10).Each element of a voter will be a permutation of the digits between 0 and M-1. There is a blank line between each test case.
Output
For each test case,output the number of the candidate who wins the election, or -1 if the election ends without a winner.
Sample Input
5
120
102
210
021
012
8
3120
3012
1032
3120
2031
2103
1230
1230
Sample Output
1
-1
Hint:
Case 1:
Nobody gets an absolute majority in the first round and candidate 2 is eliminated. Candidate 1 then receives 3 votes in the next round, giving an absolute majority.
Case 2:
Candidate 0 is eliminated in the first round of voting. Candidate 2 is eliminated in the second round. In the third round, candidates 1 and 3 get 4 votes each. Neither candidate receives an absolute majority, and they are both eliminated for having the least number of votes, so the election ends without a winner.
這題的投票，每輪都是從第一個數(shù)開始找的，找到第一個沒有被淘汰的人。
我一開始以為之前幾輪選的人，在后面不能被選了。。。。
2008年3月27日
#include<iostream>
#include<string>
#include<iomanip>
#include<vector>
#include<algorithm>
const int MAXN=100;
using namespace std;
int cmp ( const void* p1 , const void *p2 )
{
return *( double* )p1>*(double*)p2?1:-1;
}
typedef struct COLOR
{
string col;
double mean,median,sum,value[MAXN];
int num,p;
}COL;
int find ( vector<COL> &str , COL s )
{
for ( vector<COL>::size_type i = 0; i != str.size(); i++ )
if ( str[i].col==s.col )
{
str[i].sum+=s.sum;
str[i].num++;
str[i].value[str[i].p++]=s.sum;
return 1;
}
return 0;
}
void add ( vector<COL>& str , COL s )
{
if ( !find ( str , s ) )
{
s.p=1;
s.num=1;
s.value[0]=s.sum;
str.push_back(s);
}
}
void output ( vector<COL> str )
{
double s=0,v[MAXN],median;
int n=0,q,j=0;
for (vector<COL>::size_type i = 0; i != str.size(); ++i )
{
for (q=0 ; q<str[i].p ; q++)
v[j++]=str[i].value[q];
s+=str[i].sum;
n+=str[i].p;
qsort(str[i].value,str[i].num,sizeof(str[i].value[0]),cmp);
if (str[i].num%2)
str[i].median=str[i].value[(str[i].num-1)/2];
else
str[i].median=(str[i].value[str[i].num/2]+str[i].value[str[i].num/2-1])/2;
cout<<str[i].col<<"\t"<<": "<<"sum="<<"\t"
<<setw(10)<<str[i].sum<<"\t"<<"mean="<<"\t"
<<setw(10)<<str[i].sum/str[i].num<<"\t"<<"median="<<"\t"
<<setw(10)<<str[i].median<<endl;
/*
for ( int j=0 ; j<str[i].p ; j++ )
cout<<str[i].value[j]<<endl;
*/
}
qsort(v,j,sizeof(v[0]),cmp);
if (n%2!=0)
median=v[(n-1)/2];
else
median=(v[n/2]+v[n/2-1])/2;
cout<<"============================================================================"<<endl;
cout<<"ALL"<<"\t"<<": "<<"sum="<<"\t"
<<setw(10)<<s<<"\t"<<"mean="<<"\t"
<<setw(10)<<s/n<<"\t"<<"median="<<"\t"
<<setw(10)<<median<<endl;
/*
for ( j=0 ; j<n ;j++ )
cout<<v[j]<<endl;
*/
}
int main ( )
{
vector<COL> str;
COL s;
while ( cin>>s.col>>s.sum )
{
add(str,s);
}
output( str );
}
摘要: 0 前言: STL，為什么你必須掌握
對于程序員來說，數(shù)據(jù)結構是必修的一門課。從查找到排序，從鏈表到二叉樹，幾乎所有的算法和原理都需要理解，理解不了也要死記硬背下來。幸運的是這些理論都已經(jīng)比較成熟，算法也基本固定下來，不需要你再去花費心思去考慮其算法原理，也不用再去驗證其準確性。不過，等你開始應用計算機語言來工作的時候，你會發(fā)現(xiàn)，面對不同的需求你需要一次又一次去用代碼重復實現(xiàn)這些已經(jīng)成熟的... 閱讀全文
助教給我的郵件中這樣說：
Jerry Huang 致 我
顯示詳細信息 3月21日 (6天前)
Hi,
我編譯了你們的代碼，進行了測試，好像和希望的結果差距比較大，請你們再檢查確認一下。
如果是提交錯了，請重新提交。
Thanks
huang
結果我只打了70分。。。。。
1#include<iostream>
2using namespace std;
3/* 判斷字符串是否在引號里面 */
4int qutation ( char c , bool &f ,bool f1 )
5{
6 char temp;
7 if ( c=='"' && f1==false)
8 {
9 f=true;
10 cout<<c;
11 while ( f==true )
12 {
13 cin.get(temp);
14 if ( temp=='"')
15 f=false;
16 cout<<temp;
17 }
18 return 1; //發(fā)現(xiàn)引號
19 }
20 return 0; //沒有發(fā)現(xiàn)引號
21}
22void cut_add ( )
23{
24 char c,temp;
25 bool f1,f2,f3;
26 f1=f2=f3=false; // f1標記block注釋,f2標記引號,f3標記line注釋
27 while ( cin.get(c) )
28 {
29 if ( !qutation(c,f2,f1) ) // 沒有出現(xiàn)引號
30 {
31 /*判斷注釋開頭*/
32 if ( c=='/' )
33 {
34 cin.get(temp);
35 if ( temp=='*' )
36 f1=true;//找到了block注釋的開頭
37 else
38 if ( temp=='/' )
39 f3=true;//找到了line注釋的開頭
40 /*當沒有找到注釋的開頭時，執(zhí)行else部分*/
41 else
42 {
43 cout<<c;
44 cin.putback(temp);
45 }
46 }
47 else
48 if ( f1==false && f3==false )
49 cout<<c;
50 /*判斷注釋結尾*/
51 if ( c=='*' )
52 {
53 cin.get(temp);
54 if ( temp=='/' )
55 f1=false; //關閉block注釋
56 else
57 {
58 cout<<c;
59 cin.putback(temp);
60 }
61 }
62 else
63 if ( c=='\n' )
64 {
65 f3=false; //關閉line注釋
66 cout<<c;
67 }
68 }
69 }
70}
71int main ( )
72{
73 cut_add();
74}
我不知道什么原因，手動輸入可以的，但是用文件輸入輸出的話，輸出就停不了了。。。。
題目：
就是給你個.cpp文件，這是加注釋的，然后讓你生成一個.txt文件，除去代碼的注釋。
用命令行輸入：
erasecomment < DataIn.cpp > result.txt