http://acm.hdu.edu.cn/showproblem.php?pid=3123純粹的數學題，當n>m時就沒必要再計算了，因為下面的數模m都等于0
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 200
int main()
{
//printf("len = %d\n", getLen(100));
int i, j;
int T;
int n, m;
char str[LEN];
long long rs;
long long multi;
scanf("%d", &T);
while(T--)
{
scanf("%s%d", str, &m);
int len1 = strlen(str);
if(len1 > 7)
n = m;
else
sscanf(str, "%d", &n);
if(n == 0)
{
printf("%d\n", 1 % m);
}
else
{
rs = 1;
multi = 1;
for(i = 1; i <= n; i++)
{
multi = (multi * i) % m;
rs = (rs + multi) % m;
}
printf("%lld\n", rs % m);
}
}
//system("pause");
return 0;
}
posted @
2012-09-04 19:34 小鼠標 閱讀(156) |
評論 (0) |
編輯 收藏
數字游戲，逐位推出數字即可，需要注意的是結束條件，當迭代達到一定數量時就認為沒有結果。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 3000
int main()
{
int i, j;
int T;
int n, k;
scanf("%d", &T);
int n0[LEN];
int n1[LEN];
while(T--)
{
scanf("%d%d", &n, &k);
int t = 0;
int t1;
n0[0] = k;
int len = LEN - 10;
int gard = 0;
for(i = 0; i < len; i++)
{
t1 = n0[i] * n + t;
n1[i] = t1 % 10;
t = t1 / 10;
n0[i + 1] = n1[i];
if(n1[i] == k && t == 0 && n1[i - 1] != 0)//結果數字不能有前導0，并且最高位不能有進位
{
gard = 1;
break;
}
}
if(n == 1)//n為1的時候只需要直接輸出k，而上面for()的結果會輸出兩個k
printf("%d\n", k);
else
{
if(gard == 1)
{
for(; i >= 0; i--)
printf("%d", n0[i]);
putchar(10);
}
else
printf("0\n");
}
}
//system("pause");
return 0;
}
posted @
2012-09-01 17:36 小鼠標 閱讀(176) |
評論 (0) |
編輯 收藏對模擬題不太感冒，這道題搞了好久，感謝小焦~~
網選在即，一周的加強訓練馬上就要過去了，著急啊，著急啊！！
#include<stdio.h>
#include<stdlib.h>
#define LEN
typedef struct
{
char c;
int a, b;
}Node;
int main()
{
int i, j;
int T, n;
Node nd[1000];
int min = 0xfffffff;
int max = -1;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(i = 0; i < n; i++)
{
getchar();
scanf("%c%d%d", &nd[i].c, &nd[i].a, &nd[i].b);
if(nd[i].a < min)
min = nd[i].a;
if(nd[i].b > max)
max = nd[i].b;
}
int count = 0;
for(i = min; i <= max; i++)
{
for(j = 0; j < n; j++)
{
if(nd[j].a == i)
count++;
if(nd[j].b == i)
count--;
}
if(count)
printf("%c", count + 'A' - 1);
}
printf("\n");
}
//system("pause");
}
posted @
2012-09-01 11:11 小鼠標 閱讀(144) |
評論 (0) |
編輯 收藏
摘要: http://www.bnuoj.com/bnuoj/problem_show.php?pid=3017很是奇怪，晚上交一直TLE，優化了很久都無效，今天把優化都刪了，直接交，奇跡般的A了。。
Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->#inc...
閱讀全文
posted @
2012-09-01 11:05 小鼠標 閱讀(227) |
評論 (0) |
編輯 收藏
最長上升子序列，算法不多講了，這里說一下代碼里的二分查找函數（bS()）
二分查找以前也寫過，是在有序表中找出元素key的位置，這里的bS()函數略有不同，它是在遞增序列中找出第一個大于key的元素的位置。為了方便處理邊界，我在有序序列的起點加入了一個最小值，在有序序列的終點加了一個最大值。
具體請看代碼：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 1010
#define MAX 1000000
int num[LEN];
int L[LEN];
int len;
int p;
int bS(int bg, int ed, int n)
{
int mid;
while(bg <= ed)
{
mid = (bg + ed) / 2;
if(n > L[mid] && n < L[mid + 1])
return mid + 1;
else if(n > L[mid])
bg = mid + 1;
else
ed = mid - 1;
}
}
int main()
{
int i, j;
int N;
scanf("%d", &N);
for(int ii = 0; ii < N; ii++)
{
scanf("%d", &p);
for(i = 0; i < p; i++)
scanf("%d", &num[i]);
L[0] = -MAX;
L[1] = num[0];
len = 2;
for(i = 1; i < p; i++)
{
L[len] = MAX;
int mid = bS(1, len - 1, num[i]);
if(mid >= len)
{
L[len++] = num[i];
}
else
L[mid] = num[i];
}
if(ii != 0)
printf("\n");
printf("%d\n", len - 1);
}
//system("pause");
}
posted @
2012-08-30 22:13 小鼠標 閱讀(157) |
評論 (0) |
編輯 收藏
最長上升子序列，算法時間復雜度O(NlgN)，理解不怎么深刻，就不多說了。
注意二分查找。
1#include<iostream>
2#include<string.h>
3#define LEN 40010
4using namespace std;
5int len;
6int L[LEN];
7int A[LEN];
8int binSearch(int bg, int ed, int n)
9{
10 int mid;
11 while(bg <= ed)
12 {
13 mid = (bg + ed) / 2;
14 if(n > L[mid] && n < L[mid + 1])
15 return mid + 1;
16 else if(n > L[mid])
17 bg = mid + 1;
18 else
19 ed = mid - 1;
20 }
21}
22int main()
23{
24 int i, j;
25 int n, p;
26 cin >> n;
27 while(n--)
28 {
29 cin >> p;
30 for(i = 0; i < p; i++)
31 cin >> A[i];
32 L[0] = 0;
33 L[1] = A[0];
34 len = 1;
35 for(i = 1; i < p; i++)
36 {
37 if(A[i] > L[len])
38 L[++len] = A[i];
39 else if(A[i] < L[1])
40 L[1] = A[i];
41 else
42 {
43 int mid = binSearch(1, len, A[i]);
44 L[mid] = A[i];
45 }
46 }
47 cout << len << endl;
48 }
49 //system("pause");
50 return 0;
51}
52posted @
2012-08-30 21:44 小鼠標 閱讀(154) |
評論 (0) |
編輯 收藏表達式求值，牽涉到大數。用Java寫的，收獲不少，膜拜光輝啊~~
import java.math.*;
import java.util.*;
public class Main
{
public static void main(String[] s)
{
int count = 1;
int i, j;
String[] str = new String[30];
int hsrs;
Scanner sc = new Scanner(System.in);
while(sc.hasNext())
{
hsrs = 1;
int N = sc.nextInt();
for(i = 0; i < N; i++)
str[i] = (String)sc.next();
for(i = 1; i < N; i += 2)
if(!str[i].equals("+") && !str[i].equals("*"))
hsrs = 0;
for(i = 0; i < N; i += 2)
if(str[i].equals("+") || str[i].equals("*"))
hsrs = 0;
if(N % 2 == 0)
hsrs = 0;
BigInteger left = BigInteger.ZERO;
BigInteger right = BigInteger.ZERO;
if(hsrs == 1)
{
right = new BigInteger(str[0]);
String op = "+";
for(i = 1; i < N; i += 2)
{
if(str[i].equals("+"))
{
left = left.add(right);
right = new BigInteger(str[i + 1]);
op = "+";
}
else
right = right.multiply(new BigInteger(str[i + 1]));
}
}
left = left.add(right);
System.out.print("Case " + count++ +": ");
if(hsrs == 1)
System.out.println(left);
else
System.out.println("Invalid Expression!");
}
}
}
posted @
2012-08-28 21:50 小鼠標 閱讀(208) |
評論 (0) |
編輯 收藏
摘要: 簡單說一下回溯法，回溯跟深度優先遍歷是分不開的，我們傾向于把回溯看做深度優先遍歷的延伸。我們知道，圖的深度優先遍歷每個節點只會被訪問一次，因為我們一旦走過一個點，我們就會做相應的標記，避免重復經過同一個點。而回溯的做法是，當走過某一個點時，標記走過，并把該點壓棧；當該節點出棧時，我們再把它標記為沒有走過，這樣就能保證另外一條路也能經過該點了
閱讀全文
posted @
2012-08-20 16:09 小鼠標 閱讀(449) |
評論 (0) |
編輯 收藏
摘要: 圖的常見遍歷方式有兩種：深度優先遍歷和廣度優先遍歷，他們的作用是將圖中的每個點都訪問一遍，只不過是順序不同。
如果把圖中的每條邊長都相等（比如都是1）的話，深度優先遍歷的過程是：
1.任意選定一個點p0作為遍歷的起點
2.從未訪問節點中任選一個距離p0最近的點進行訪問，并標記該點被訪問過
3.重復第2步，直到該連通分支中的所有節點都被訪問過
閱讀全文
posted @
2012-08-20 12:23 小鼠標 閱讀(1604) |
評論 (0) |
編輯 收藏感謝杭電的水題，A水題，漲自信！
題意描述：
給出M組兩個人之間的師徒關系，問是否存在悖論，即某個人的徒弟又是自己的師傅。
解題思路：
用拓撲排序判斷圖中是否存在環路即可。
拓撲排序參閱：
http://m.shnenglu.com/hoolee/archive/2012/08/16/187400.html以下是本題代碼：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 110
int mp[LEN][LEN];
int d[LEN];
int s[LEN];
int N, M;
int zr;
int findZero()
{
int i;
int a = -1;
for(i = 0; i < N; i++)
if(s[i] == 0 && d[i] == 0)
{
a = i;
break;
}
if(a == -1)
return 0;
zr = a;
return 1;
}
int TopSort()
{
int i, j;
for(i = 0; i < N; i++)
{
if(findZero())
{
s[zr] = 1;
for(j = 0; j < N; j++)
d[j] -= mp[zr][j];
}
else
return 0;//如果點還沒有選完，且已經找不到入度為0的點，說明圖中存在回路
}
return 1;
}
int main()
{
int i, j;
int x, y;
while(scanf("%d%d", &N, &M), N)
{
memset(mp, 0, sizeof(mp));
memset(s, 0, sizeof(s));
memset(d, 0, sizeof(d));
for(i = 0; i < M; i++)
{
scanf("%d%d", &x, &y);
if(mp[x][y] == 0)
{
mp[x][y] = 1;
d[y]++;
}
}
if(TopSort() == 1)
printf("YES\n");
else
printf("NO\n");
}
//system("pause");
}posted @
2012-08-18 17:39 小鼠標 閱讀(606) |
評論 (0) |
編輯 收藏