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 小鼠标 阅读(138) |
评论 (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 小鼠标 阅读(160) |
评论 (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 小鼠标 阅读(134) |
评论 (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 小鼠标 阅读(212) |
评论 (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 小鼠标 阅读(134) |
评论 (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 小鼠标 阅读(131) |
评论 (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 小鼠标 阅读(191) |
评论 (0) |
编辑 收藏
摘要: 简单说一下回溯法，回溯跟深度优先遍历是分不开的，我们倾向于把回溯看做深度优先遍历的延伸。我们知道，图的深度优先遍历每个节点只会被访问一次，因为我们一旦走过一个点，我们就会做相应的标记，避免重复经过同一个点。而回溯的做法是，当走过某一个点时，标记走过，并把该点压栈；当该节点出栈时，我们再把它标记为没有走过，这样就能保证另外一条路也能经过该点了
阅读全文
posted @
2012-08-20 16:09 小鼠标 阅读(419) |
评论 (0) |
编辑 收藏
摘要: 图的常见遍历方式有两种：深度优先遍历和广度优先遍历，他们的作用是将图中的每个点都访问一遍，只不过是顺序不同。
如果把图中的每条边长都相等（比如都是1）的话，深度优先遍历的过程是：
1.任意选定一个点p0作为遍历的起点
2.从未访问节点中任选一个距离p0最近的点进行访问，并标记该点被访问过
3.重复第2步，直到该连通分支中的所有节点都被访问过
阅读全文
posted @
2012-08-20 12:23 小鼠标 阅读(1582) |
评论 (0) |
编辑 收藏感谢杭电的水题，A水题，涨自信！
题意描述：
给出M组两个人之间的师徒关系，问是否存在悖论，即某个人的徒弟又是自己的师傅。
解题思路：
用拓扑排序判断图中是否存在环路即可。
拓扑排序参阅：
http://www.cppblog.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 小鼠标 阅读(593) |
评论 (0) |
编辑 收藏