Description
给一个N位的正整数，该数不包含前导0，先让你调整其中每个数字的位置，得到另一个n位的数，并且使得这个数越小越好，而且这个数不能包含前导0。比如543210可以变成102345，而12345保持不变才是最优结果。
Input
第一行一个整数T（T<=100)，表示有T组数据。
每组数据先输入一行一个整数N(1<=N<=100)，表示位数，接下来一行输入一个N位的不包含前导0的正整数。
Output
每组数据对应一行输出，即调整数字位置后能得到的最小的不包含前导0的数。
Sample Input
Sample Output
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 using namespace std; 5 char m[110],n[110]; 6 int main(){ 7 int T,N; 8 scanf("%d",&T); 9 while(T--){ 10 int num=0; 11 scanf("%d",&N); 12 scanf("%s",m); 13 if(strcmp(m,"0")==0)printf("0 "); 14 else { 15 for(int i=0;i<N;i++){ 16 if(m[i]=='0')num++; 17 } 18 sort(m,m+N); 19 int top=0; 20 while(m[top]=='0')top++; 21 if(m[top])printf("%c",m[top]); 22 while(num--)printf("0"); 23 for(int i=top+1;i<N;i++){ 24 printf("%c",m[i]); 25 } 26 puts(""); 27 } 28 } 29 return 0; 30 }
Description
Edward, a poor copy typist, is a user of the Dvorak Layout. But now he has only a QWERTY Keyboard with a broken Caps Lock key, so Edward never presses the broken Caps Lock key. Luckily, all the other keys on the QWERTY keyboard work well. Every day, he has a lot of documents to type. Thus he needs a converter to translate QWERTY into Dvorak. Can you help him?
The QWERTY Layout and the Dvorak Layout are in the following:
| The QWERTY Layout |
|---|
| The Dvorak Layout |
|---|
Input
A QWERTY document Edward typed. The document has no more than 100 kibibytes. And there are no invalid characters in the document.
Output
The Dvorak document.
Sample Input
Jgw Gqm Andpw a H.soav Patsfk f;doe
Nfk Gq.d slpt a X,dokt vdtnsaohe
Kjd yspps,glu pgld; aod yso kd;kgluZ
1234567890
`~!@#$%^&*()}"']_+-=ZQqWEwe{[|
ANIHDYf.,bt/
ABCDEFuvwxyz
Sample Output
Hi, I'm Abel, a Dvorak Layout user.
But I've only a Qwerty keyboard.
The following lines are for testing:
1234567890
`~!@#$%^&*()+_-={}[]:"'<>,.?/|
ABCDEFuvwxyz
AXJE>Ugk,qf;
题解：这道逗比题让我错了18次==一下午；改了n种方法，最终事实教会我我的数组开小了100 kibibytes我竟然不知道kibibytes什么意思把数组开到了100.。。最终还是没过，关键错误原因竟然是没见过的Segmentation Fault错误。。。什么分段错误。。。发现还是要读清题。。。
代码：
1 #include<stdio.h> 2 #include<string.h> 3 #include<map> 4 using namespace std; 5 char s[1000010]; 6 map<char,char>m; 7 int main(){ 8 char a,b; 9 m.clear(); 10 m['-']='[';a=34;b=39; 11 m['_']='{';m['=']=']';m['+']='}';m['q']=b;m['Q']=a; 12 m['w']=',';m['W']='<';m['e']='.';m['E']='>';m['r']='p';m['R']='P'; 13 m['t']='y';m['T']='Y';m['y']='f';m['Y']='F';m['u']='g';m['U']='G';m['i']='c'; 14 m['I']='C';m['o']='r';m['O']='R';m['p']='l';m['P']='L';m['[']='/';m['{']='?'; 15 m[']']='=';m['}']='+';m['s']='o';m['S']='O';m['d']='e';m['D']='E';m['f']='u';m['F']='U'; 16 m['g']='i';m['G']='I';m['h']='d';m['H']='D';m['j']='h';m['J']='H';m['k']='t';m['K']='T';m['l']='n'; 17 m['L']='N';m[';']='s';m[':']='S';m[39]='-';m[34]='_';m['z']=';';m['Z']=':';m['x']='q';m['X']='Q'; 18 m['c']='j';m['C']='J';m['v']='k';m['V']='K';m['b']='x';m['B']='X';m['n']='b';m['N']='B';m[',']='w';m['<']='W'; 19 m['.']='v';m['>']='V';m['/']='z';m['?']='Z'; 20 while(gets(s)){ 21 int len=strlen(s); 22 for(int i=0;i<len;i++){ 23 if(m.count(s[i]))printf("%c",m[s[i]]); 24 else printf("%c",s[i]); 25 } 26 printf(" "); 27 } 28 return 0; 29 }
| UVA 10397 | EPR悖论 |
Many new buildings are under construction on the campus of the University of Waterloo. The university has hired bricklayers, electricians, plumbers, and a computer programmer. A computer programmer? Yes, you have been hired to ensure that each building is connected to every other building (directly or indirectly) through the campus network of communication cables. We will treat each building as a point specified by an x-coordinate and a y-coordinate. Each communication cable connects exactly two buildings, following a straight line between the buildings. Information travels along a cable in both directions. Cables can freely cross each other, but they are only connected together at their endpoints (at buildings). You have been given a campus map which shows the locations of all buildings and existing communication cables. You must not alter the existing cables. Determine where to install new communication cables so that all buildings are connected. Of course, the university wants you to minimize the amount of new cable that you use. Fig: University of Waterloo Campus Input The input file describes several test cases. The description of each test case is given below: The first line of each test case contains the number of buildings N (1 ≤ N ≤ 750). The buildings are labeled from 1 to N. The next N lines give the x and y coordinates of the buildings. These coordinates are integers with absolute values at most 10000. No two buildings occupy the same point. After that there is a line containing the number of existing cables M (0 ≤ M ≤ 1000) followed by M lines describing the existing cables. Each cable is represented by two integers: the building numbers which are directly connected by the cable. There is at most one cable directly connecting each pair of buildings. Output For each set of input, output in a single line the total length of the new cables that you plan to use rounded to two decimal places.
Sample Input 4 103 104 104 100 104 103 100 100 1 4 2 4 103 104 104 100 104 103 100 100 1 4 2
Sample Output 4.41 4.41
题解；克鲁斯卡尔超时，超内存，prime水过；
代码：
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #include<math.h> 5 using namespace std; 6 const int INF=0x3f3f3f3f; 7 const int MAXN=760; 8 int dx[MAXN],dy[MAXN]; 9 double map[MAXN][MAXN],low[MAXN]; 10 int vis[MAXN]; 11 double fd(int sx,int sy,int ex,int ey){ 12 int s=ex-sx,e=ey-sy; 13 return sqrt(s*s+e*e); 14 } 15 int N,M; 16 double ans; 17 void prime(){ 18 for(int i=1;i<=N;i++)low[i]=map[1][i]; 19 for(int i=1;i<=N;i++){ 20 double temp=INF; 21 int k; 22 for(int j=1;j<=N;j++){ 23 if(!vis[j]&&temp>low[j])temp=low[k=j]; 24 } 25 if(temp==INF)break; 26 ans+=temp; 27 vis[k]=1; 28 for(int j=1;j<=N;j++) 29 if(!vis[j]&&low[j]>map[k][j]) 30 low[j]=map[k][j]; 31 } 32 } 33 int main(){ 34 int a,b; 35 while(~scanf("%d",&N)){ 36 ans=0; 37 for(int i=1;i<=N;i++){ 38 scanf("%d%d",&dx[i],&dy[i]); 39 }int top=0; 40 for(int i=1;i<=N;i++) 41 for(int j=1;j<=N;j++){ 42 if(j>i){ 43 map[i][j]=map[j][i]=fd(dx[i],dy[i],dx[j],dy[j]); 44 } 45 } 46 scanf("%d",&M); 47 while(M--){ 48 scanf("%d%d",&a,&b); 49 map[a][b]=map[b][a]=0; 50 } 51 memset(low,INF,sizeof(low)); 52 memset(vis,0,sizeof(vis)); 53 prime(); 54 printf("%.2lf ",ans); 55 } 56 return 0; 57 }
克鲁斯卡尔的也贴上吧：
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #include<math.h> 5 using namespace std; 6 const int MAXN=760; 7 int dx[MAXN],dy[MAXN]; 8 9 double fd(int sx,int sy,int ex,int ey){ 10 int s=ex-sx,e=ey-sy; 11 return sqrt(s*s+e*e); 12 } 13 struct Node{ 14 int s,e; 15 double dis; 16 }; 17 Node dt[MAXN*MAXN]; 18 int cmp(Node a,Node b){ 19 if(a.dis<b.dis)return 1; 20 else return 0; 21 } 22 int N,M; 23 int pre[MAXN]; 24 int find(int x){ 25 // return pre[x]= x==pre[x]?x:find(pre[x]);//这一句话超了半天内存。。。。 26 int r=x; 27 while(r!=pre[r])r=pre[r]; 28 int i=x,j; 29 while(i!=r){ 30 j=pre[i];pre[i]=r;i=j; 31 } 32 return r;//换成这就超时了。。。。 33 } 34 double ans; 35 void merge(Node a){ 36 int f1,f2,x,y; 37 x=a.s;y=a.e; 38 f1=find(x);f2=find(y); 39 if(f1!=f2){ 40 pre[f1]=f2; 41 ans+=a.dis; 42 } 43 } 44 int main(){ 45 int a,b; 46 while(~scanf("%d",&N)){ 47 ans=0; 48 for(int i=1;i<=N;i++){ 49 scanf("%d%d",&dx[i],&dy[i]); 50 pre[i]=i; 51 }int top=0; 52 for(int i=1;i<=N;i++) 53 for(int j=1;j<=N;j++){ 54 if(j>i){ 55 dt[top].s=i;dt[top].e=j; 56 dt[top++].dis=fd(dx[i],dy[i],dx[j],dy[j]); 57 } 58 } 59 scanf("%d",&M); 60 while(M--){ 61 scanf("%d%d",&a,&b); 62 pre[b]=a; 63 } 64 sort(dt,dt+N,cmp); 65 for(int i=0;i<top;i++){ 66 merge(dt[i]); 67 } 68 printf("%.2lf ",ans); 69 } 70 return 0; 71 }
Description
F(x) = 6 * x^7+8*x^6+7*x^3+5*x^2-y*x (0 <= x <=100)
Can you find the minimum value when x is between 0 and 100.
Input
Output
Sample Input
Sample Output
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 using namespace std; 5 int y; 6 double qd(double x){ 7 return 42*x*x*x*x*x*x+48*x*x*x*x*x+21*x*x+10*x-y; 8 } 9 double abc(double x){ 10 return x>0?x:-x; 11 } 12 double cao(double x){ 13 double temp=6*x*x*x*x*x*x*x+8*x*x*x*x*x*x+7*x*x*x+5*x*x-y*x; 14 return temp; 15 } 16 int main(){ 17 int T; 18 scanf("%d",&T); 19 while(T--){ 20 scanf("%d",&y); 21 double l=0,r=100,mid; 22 if(qd(l)>0)printf("%.4lf ",cao(l)); 23 else if(qd(r)<0)printf("%.4lf ",cao(r)); 24 else { 25 while(abc(r-l)>1e-10){ 26 mid=(l+r)/2; 27 if(qd(mid)>0)r=mid; 28 else l=mid; 29 } 30 printf("%.4lf ",cao(mid)); 31 } 32 } 33 return 0; 34 }