题目大意:给定一张图,和每个点的油价,知道每条路的耗油量,给定一些询问,求从起点到终点用指定油箱容量的车所得到的最小耗费。
解题思路:BFS+优先队列
优先队列介绍:采用stl中的priority_queue实现。priority_queue默认的是最大优先队列,声明时只要priority_queue<int> q就行了。如果是最小堆,麻烦一些

priority_queue<int,vector<int>,cmp> q。其中cmp函数如下:
struct cmp
{
    bool operator()(const int &am[......]

继续阅读

本题主要是STL库里的next_permutation的用法!

在标准库算法中,next_permutation应用在数列操作上比较广泛.这个函数可以计算一组数据的全排列.但是怎么用,原理如何。
首先查看stl中相关信息.
函数原型:

template<class BidirectionalIterator>
   bool next_permutation(
      BidirectionalIterator _First,
   &nbsp[……]

继续阅读

1、USACO

命名比较有规则。

比如 2006年November题目和测试数据的网址是http://ace.delos.com/NOV06

2007年open赛题目和测试数据的网址是 http://ace.delos.com/OPEN07

2、日本ACM比赛

网址是 http://www.acm-japan.org/ ,进去后有题目和测试数据

http://icpc2010.honiden.nii.ac.jp/en/past-contests

3、官方网站

命名也有规则。

02年网址是 http://icpc.ba[……]

继续阅读

http://jsj.sdibt.edu.cn/judge/contest/viewProblem.action?pid=144

八数码转换问题……
经典bfs……
关键问题:
1.状态的保存(见longwuxu该题解题报告中的全排列Hash表示)
2.bfs中标记数组的处理:
    bfs中有两个标记数组,一个是标记队列中节点的标记数组isadd[],另一个是标记已访问节
    点标记数组isvis[]。前者在入队列的时候进行标记,而后者则要在出队列的时候[……]

继续阅读

题意:贪吃蛇问题。给定地图坐标,贪吃蛇的长度和位置,还有一些障碍物坐标,求蛇头移动到指定点的最小步数。
在这里我们将蛇的状态描述为如下三元组(x,y,state),其中 (x,y)是蛇头的坐标,state 记录的是身体的状态,由于身体最长为七段,每一段相对于前一段只有上下左右四种状态,仅需要两位表示,则身体所有块的状态最多需要 7×2=14 位二进制数表示,则我们可以构建矩阵 pMatrix[21][21][16384] 来保存访问过的状态,以避免重复访问相同的状态,后面的工作就是传统的广搜过程了;
用个结构提记录贪吃蛇的状态
struct Node
{
[……]

继续阅读

spj的文件可以是c或cpp编写的程序,编译为spj文件,并设执行权限。

spj.c 或 spj.cc,需编译为spj,执行spj时传3个文件名参数:输入,参考输出,用户输出。

spj的退出值决定判断结果,成功退出(0)表示AC,其余表示WA.

http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=1449

#include <stdio.h>

char fname[100];
FILE *dat, *diff;

int main(int argc, char **argv){
	int n;
	lo[......]

继续阅读

#include

int n;

int time[60];

int now[60];

int first[60];

int begin;

int last;

int min;

int temp;

bool isOK(int first, int inv) {
for (int i = first; i < 60; i += inv) {
if (time[i] – now[i] <= 0)
return false;
}
return true;
}

void mark(int first, int inv, int one_of_p_or_n) {
for (int i = first; i < 60; i += inv) {
now[i] += one_of_p_or_n;
}
}

void find(int x) {
if (x == 60) {

if (temp min) {

return;
}
if (time[x] – now[x] <= 0) {

int i;
for (i = x + 1; i 0) {
break;
}
}
find(i);
return;
}
for (int i = begin;i 0) {
if (isOK(x, x – i)) {

first[i]–;
mark(x, x – i, 1);
find(x);
mark(x, x – i, -1);
first[i]++;
}
}
}

if (x < last) { //找某条bus route上的第一班车,存在first里面
first[x]++;
now[x]++;
temp++;
find(x);
first[x]–;
now[x]–;
temp–;
}
}
int main() {
scanf("%d", &n);
if (!n) {
printf("0");
return 0;
}
scanf("%d", &temp);
time[temp]++;
begin = temp;
for (int i = 1; i < n; i++) {
scanf("%d", &temp);
time[temp]++;
}
last = temp;
min = n / 2;
temp = 0;
find(begin);
printf("%d\n", min);
return 0;
}
[……]

继续阅读

#include
#include
#include
using namespace std;
int fac[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };//…
int order(const char *s, int n)
{
int i, j, temp, num;
num = 0;
for (i = 0; i < n-1; i++)
{
temp = 0;
for (j = i + 1; j < n; j++) {
if (s[j] < s[i])
temp++;
}
num += fac[s[i] -1] * temp;
}
return num;
}
bool is_equal(const char *b1, const char *b2)
{ for(int i=0; i<9; i++)
if(b1[i] != b2[i])
return false;
return true;
}
struct node{
char board[9];
char space;//空格所在位置
};
const int TABLE_SIZE = 362880;
int hash(const char *cur)
{ return order(cur, 9);
}
char visited[TABLE_SIZE];
int parent[TABLE_SIZE];
char move[TABLE_SIZE];
int step[4][2] = {{-1, 0},{1, 0}, {0, -1}, {0, 1}};//u, d, l, r
void BFS(const node & start){
int x, y, k, a, b;
int u, v;
node cflag;
u = hash(start.board);
//start.vvvalue=u;
parent[u] = -1;
visited[u] = 1;
queue que;
que.push(start);
node tmp, cur;
while(!que.empty()){
cflag= que.front();
que.pop();
//get_node(u, cur);
// u=cflag.vvvalue;
u=hash(cflag.board );
k = cflag.space;
x = k / 3;
y = k % 3;
for(int i=0; i<4; ++i){
a = x + step[i][0];
b = y + step[i][1];
if(0<=a && a<=2 && 0<=b && b=0; –i){
if(path[i] == 0)
printf(“u”);
else if(path[i] == 1)
printf(“d”);
else if(path[i] == 2)
printf(“l”);
else
printf(“r”);
}
printf(“\n”);
}
int main(){
node start;
char c;
int k;
for(int i=0; i>c;
if(c == ‘x’){
start.board[i] = 9;
start.space = i;
}
else
start.board[i] = c – ‘0’;
}
for(k=0; k<TABLE_SIZE; ++k)
visited[k] = 0;
BFS(start);
if(visited[0] == 1)
print_path();
else
printf("unsolvable\n");
return 0;
}[……]

继续阅读

昨天写了使用NtQuerySystemInformation函数获取CPU占用率的方法,这个函数可以获得CPU占用率在内的许多系统信息。不过今天介绍的是GetSystemTimes这个函数,它同样可以获得CPU占用率。

为什么要介绍GetSystemTimes这个函数呢,因为MSDN上说NTquerySystemInformation这个函数只能在NT核心的系统上使用(经测试在Win7下也可使用),而GetSystemTimes这个函数MSDN上说在Vista和XP SP1以上系统可用。为了我们的程序在未来的新系统上不至于失效,所以介绍一下GetSystemTimes这个函数的用法。[……]

继续阅读

今天组长让我对动态调整帧率的代码进行核查,然后发现之前写的代码完全不能起到统计CPU占用率的作用,因为GetThreadTIme这个函数居然有15ms的误差(多核CPU的情况下,单核有10ms的误差)。之前的想法是通过获得线程的运行时间除以总共经过的时间来求线程占用CPU的比率,但是有个问题给忽略了,用这种方法会得到相反的结果。因为CPU空闲时线程运行的时间会增加,而CPU忙时反而会减小。所以之前的代码首先就有逻辑错误,而且这个函数本身就有很大的误差。所以祭起google大神,搜索了一把,发现原来微软隐藏了一个内核函数,这个函数可以获得进程的全部信息包括CPU占用率以及内存占用情况。好吧,其实[……]

继续阅读

一般在调试程序时都会设置断点,并且单步跟踪,但是当遇到数据比较多或者无法单步跟踪的情况(如图形程序)。遇到这种情况怎么办?

一般的解决办法是输出到文件,但是输出到文件还是无法单步跟踪的。以前我也遇到过这样的问题,没有办法,只好在人为有问题的地方打fprintf不停的输出到文件。不过通过这几天的工作我学到一种新的方法,这个可以开启编译器(VS2005之类)的输出功能。在编译器的输出框中输出你想要看到的变量。

下面是示例。比如我现在有一个变量是int i,我要在程序运行中看它的值改变的情况。

int i;

char pBuf[MAX_PATH];

StringCbPr[……]

继续阅读

http://www.awflasher.com/blog/archives/200

(2009年的更新:本文来自2005年的白云黄鹤BBS,未经排版,四年来,文末一直保留有英文原文出处并注明链接)

这个版上太多的问题,不能让我以很愉快的心情来解答,于是,我放弃了强忍着指责别人的心情找到了这篇《提问的艺术》(两年前我在HomePage版 张贴过),真诚的希望那些又困难又期望得到帮助的新手朋友们抽时间看看,问“好的问题”,收获“好的答案”,这对改善答题人的心情和形成版面氛围都有好 处。

提问之前

在通过电邮、新闻组或者聊天室提出技术问题前,检查你有没有做到:

1. 通读手册,试着自己找答案。
2. 在FAQ里找答案(一份维护得好的FAQ可以包罗万象:)。
3. 在网上搜索(个人推荐google~~~)。
4. 向你身边精于此道的朋友打听。

[……]

继续阅读

http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=1404

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 17  Solved: 3
[Submit][STATUS][DISCUSS]

Description

给出一组图形(矩形或圆)和一组点的数据,判断点的位置。

Input

输 入一组图形的数据,其中每行以“c”开头的表示圆,以“r”开头的表示矩形,其中矩形是依次给出左下角和右上角的坐标,圆是给出圆心坐标及半径,图形数据 以输入另起一行的 *结束,接下来是给出点的坐标(x,y[……]

继续阅读

http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=1462

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 10  Solved: 8
[Submit][STATUS][DISCUSS]

Description

gameboy 是一个CS高手,他最喜欢的就是扮演警察,手持M4爆土匪的头。也许这里有人没玩过CS,有必要介绍一下“爆头”这个术语:所谓爆头,就是子弹直接命中对 方的头部,以秒杀敌人。 现在用一个三维的直角坐标系来描述游戏中的三维空间(水平面为xoy平面,z轴正方向[……]

继续阅读

Problem分类:

初 学者(1000-1012,1552,1563) C语言(1500-1551) 二级C(1933-1949) 简单题(1800-1931) 《ACM程序设计》(1134-1192) 《挑战编程》(1013-1125) 算法(1288-1391) USACO Training(2300-2393)

算法分类:

第一章(1288-1292) 第二章(1293-1306) 第三章(1307-1325) 第四章(1326-1347) 第五章(1348-1373) 第六章(1374-1397)