摘要: //server.c
1#include <stdlib.h> 2#include <stdio.h> 3#include <errno.h> 4#include <string.h> 5#include <unistd.h> ...
阅读全文
把自然数N分解成若干个互不相同的正整数，使乘积最大；
由于这种分解的数目是有限的，所以最大积存在；
假设最大积的分解为
n=a1+a2+a3+...+a[t-2]+a[t-1]+a[t]
(a1<a2<a3<...<a[t-2]<a[t-1]<a[t])
Now, from the five rules above, we could make the mutiple maximum.
to an N, find the integer k, fits
A=2+3+4+...+(k-1)+k <= N < A+(k+1)=B
Suppose N = A + p, (0 <= p < k+1)
1) p=0, then answer is Set A
2) 1<=p<=k-1 then answer is Set B - { k+1-p }
3) p=k, then answer is Set A - {2} + {k+2}
功 能: 把一整数转换为字符串
用 法: char *itoa(int value, char *string, int radix);
详细解释:itoa是英文integer to string a(将整形数转化为一个字符串,并将值保存在a中)
的缩写.其中value为要转化的整数, radix是基数的意思,即先将value转化为几进制的数,之后在保存在a 中.
作用:实现数制之间的转化
比较:ltoa,其中l是long integer(长整形数)
备注:该函数的头文件是"stdlib.h"
程序例:
#include <stdlib.h>
#include <stdio.h>
int main(){
int number = 123456;
char string[25];
itoa(number, string, 10);
printf("integer = %d string = %s\n", number, string);
return 0;
}
#include<iostream>
using namespace std;
int pre[110],rank[110],n;
int find(int x)
{
int r=x;
while(pre[r]!=-1)
r=pre[r];
while(x!=r){
int q=pre[x];
pre[x]=r;
x=q;
}
return r;
}
void unionone(int a,int b){
int t1=find(a);
int t2=find(b);
if(rank[t1]>rank[t2])
pre[t2]=t1;
else
pre[t1]=t2;
if(rank[t1]==rank[t2])
rank[t2]++;
n--;
}
int main(){
int m,i,begin,end;
while(1){
scanf("%d""%d",&n,&m);
if(n==0&&m==0)
break;
for(i=0;i<=n;i++){
rank[i]=0;
pre[i]=-1;
}
for(i=0;i<m;i++){
scanf("%d""%d",&begin,&end);
if(find(begin)!=find(end))
unionone(begin,end);
}
printf("%d\n",n-1);
}
return 0;
}
#include <stdio.h>
#define MAXN 500000
int height[MAXN+1],temp[MAXN+1];
__int64 sum;
void merge(int *a,int l,int mid,int r) {
int i,j,k;
i=0,j=l,k=mid;
while(j<mid &&k <r) {
if(a[j]>a[k]) {
sum += mid-j;
temp[i++] = a[k++];
}
else temp[i++] = a[j++];
}
while(j<mid)
temp[i++] = a[j++];
while(k<r)
temp[i++] = a[k++];
for(i=0; i<r-l; i++) a[l+i] = temp[i];
}
void divide(int *a,int l,int r) {
if(l+1<r) {
int mid = (l+r)>>1;
divide(a,l,mid);
divide(a,mid,r);
merge(a,l,mid,r);
}
}
int main() {
int n,i;
while(scanf("%d",&n)&&n) {
for(i=sum=0; i<n; i++) scanf("%d",&height[i]);
divide(height,0,n);
printf("%I64d\n",sum);
}
}
Longest Common Subsequence
Problem
Given a sequence A = < a1, a2, ..., am >, let sequence B = < b1, b2, ..., bk > be a subsequence of A if there exists a strictly increasing sequence ( i1<i2<i3 ..., ik ) of indices of A such that for all j = 1,2,...,k, aij = bj. For example, B = < a, b, c, d > is a subsequence of A= < a, b, c, f, d, c > with index sequence < 1, 2, 3 ,5 >.
Given two sequences X and Y, you need to find the length of the longest common subsequence of X and Y.
Input
The input may contain several test cases.
The first line of each test case contains two integers N (the length of X) and M(the length of Y), The second line contains the sequence X, the third line contains the sequence Y, X and Y will be composed only from lowercase letters. (1<=N, M<=100)
Input is terminated by EOF.
Output
Output the length of the longest common subsequence of X and Y on a single line for each test case.
Sample input
6 4
abcfdc
abcd
2 2
ab
cd
Sample output
4
0
#include <stdio.h>
char x[105],y[105];
int c[109][109],i,j,leny,lenx;
int main(){
while(scanf("%d %d",&lenx,&leny)!=EOF){
scanf("%s",&x);
scanf("%s",&y);
for(i=0;i<=leny;i++)
c[0][i]=0;
for(i=1;i<=lenx;i++)
c[i][0]=0;
for(i=1;i<=lenx;i++){
for(j=1;j<=leny;j++){
if(x[i-1]==y[j-1])
c[i][j]=c[i-1][j-1]+1;
else{
if(c[i-1][j]>=c[i][j-1])
c[i][j]=c[i-1][j];
else c[i][j]=c[i][j-1];
}
}
}
printf("%d\n",c[lenx][leny]);
}
return 0;
}
Problem
Give you a modular equation ax=b (mod n). Count how many different x (0<=x<n) satisfying the equation.
Input
The input may contain several test cases.
Each test contains a line with three integers a, b and n, each integer is positive and no more than 10^9.
Input is terminated by EOF.
Output
For each test case, output a line containing the number of solutions.
Sample input
4 2 6
Sample output
2
#include <stdio.h>
long a,b,n;
int gcd(long a,long b){
if(a==0){
return b;
}
else
{
return gcd(b%a,a);
}
}
int main(){
while(scanf("%d %d %d",&a,&b,&n)!=EOF){
long d=gcd(a,n);
if(b%d==0)
printf("%d\n",d);
else printf("0\n",d);
}
return 0;
}