CCF计算机职业资格认证考试迫在眉睫,我的实力却依然没有长进,首先复习一下以前的代码吧,这些在oi时期还是经常用的。现在感觉入大学以来没有好好学算法貌似不太正确,不知道现在还来不来得及,感觉这次要水水的打酱油了(但是要跑到新校区好烦恼)。
熬过这次一定认真学习算法,看书练习55开。
本来还想纠结一下用java还是c++/c 的 现在发现考试的时候已经决定了,那就没这个事了。

poj 1011: 搜索剪枝

这是当初还是写pascal的时代遇到过搜索剪枝最教科书的一题了吧,翻出当年做了200道poj的帐号,这题wa了至少10次,不知道这个通过了的代码是不是抄袭的。这题的思想还是可以学习学习的。题目大意有人疯了,把若干等长的棒子切成了更多个不等长棒子,问处女座的你把他们拼成等长的话,这个长度最小值是多少。

var
state:boolean;
j,i,all,res,lenth,sum,maxln:longint;
w:array[0..200]of boolean;
a:array[0..200]of longint;

procedure dfs(no,now,stick,inx:longint); // no:目前所考虑的棒子编号, now:目前要拼的棒子的当前长度, stick:剩下可以拿来拼接的棒子总长, inx:上次取走的棒子编号+1
var
i,ws:longint;
begin
  ws:=0;
  if state then exit;
  if stick=0 then begin state:=true; exit; end;
  if now=lenth then dfs(no+1,0,stick,1);
  for i:=inx to all do // 剪枝4: 从最后取走的棒子之后的棒子开始考虑
  begin
     if w[i] then continue; //棒子已经取走
     if now+a[i]>lenth then continue; //棒子过长
     if a[i]=ws then continue; // 剪枝5: 棒子与最后失败的棒子长度一样
     w[i]:=true;
     dfs(no,now+a[i],stick-1,i+1);
     w[i]:=false;
     ws:=a[i];
     if inx=1 then break;
  end;
end;

begin
repeat
  readln(all); //棒子数量
  if all=0 then break;
  sum:=0;
  for i:=1 to all do
  begin
    read(a[i]);
    sum:=sum+a[i]; // 计算棒子总长
  end;
  state:=false;
  
  for i:=1 to all-1 do //剪枝1:棒子排序,拼接时先考虑较长的棒子
    for j:=i+1 to all do
      if a[i]<a[j] then
      begin
        a[i]:=a[i]+a[j];
        a[j]:=a[i]-a[j];
        a[i]:=a[i]-a[j];
      end;

  for res:=all downto 1 do // 枚举最后得出的棒子数量
  begin
    if sum mod res<>0 then continue;  //剪枝2: 排除棒子长度不是整数
    if sum div res<a[1] then continue; //剪枝3: 最长的棒子超过了所求平均长度
    fillchar(w,sizeof(w),false); 
    lenth:=sum div res;
    dfs(1,0,all,1);
    if state then break;
  end;

  writeln(sum div res); //总长 除以 最多棒子数量 等于 最小棒子长度
until false;
end.

我最常使用的最短路算法:SPFA

记得还是大一的时候,不管学什么语言,都用它写一遍spfa,这里是数组模拟指针版本的。

#include <iostream>
#include <deque> //其实stl及其不熟,考试前应该把常用的看看

using namespace std;
const int MAXDOT = 100;
const int MAXEGE = 1000;
const int INF = 0x7FFFFFFF;
int m, n, mm;
int fir[MAXDOT], dis[MAXDOT];
int ege_u[MAXEGE * 2], ege_v[MAXEGE * 2], ege_p[MAXEGE * 2], ege_next[MAXEGE * 2];

void build(int u, int v, int p){
	mm++;
	ege_u[mm] = u;
	ege_v[mm] = v;
	ege_p[mm] = p;
	ege_next[mm] = fir[u];
	fir[u] = mm;
}
void spfa(int source, int teriminal){
	deque<int> dq; // 存储待更新点的队列
	bool in_queue[MAXDOT];
	int in_sum[MAXDOT];

	for (int i = 1; i <= n; i++){
		dis[i] = INF;
		in_queue[i] = false;
		in_sum[i] = 0;
	}

	dq.push_back(source);
	in_sum[source]++;
	dis[source] = 0;
	in_queue[source] = true;
	//initialize

	while (!dq.empty()){
		int u = dq.front();
		dq.pop_front();
		in_queue[u] = false;

		int mm = fir[u];
		while (mm != 0){
			int v = ege_v[mm];
			int p = ege_p[mm];
			if (dis[v] > dis[u] + p){
				dis[v] = dis[u] + p;
				if (!in_queue[v]){
					in_sum[v]++;
					in_queue[v] = true;
					dq.push_back(v);
				}
			}
			mm = ege_next[mm];
		}
	}
}
int main() {

	cin >> n >> m;
	mm = 0;
	for (int i = 0; i < m; i++){
		int u, v, p;
		cin >> u >> v >> p;
		build(u, v, p);
		build(v, u, p);
	}
	spfa(1, n);
	cout << dis[n];
	return 0;
}

唯一还记得的数据结构:线段树

这个数据结构是个伤痛。记得当初比赛时候太紧张,一个小数组的区间求和写线段树写wa了导致没有了一等奖。

#include <cstdio>

using namespace std;

const int MAX_NODE = 70000;
const int MAX_STAR = 20000;

struct nodetype{
    int value;
    int left,right;
} tree_nodes[MAX_NODE];


int number_of_stars, left_limit, right_limit; // [1,15000] x,y = [0,32000]
int number_of_same_level_star[MAX_STAR];

void build_tree(int i, int left, int right);
void insert_node(int now, int dest_x);
int query_sum(int now, int left, int right); //区间求和

int main(){
    
    build_tree(1,1,32001);
    
    scanf("%d",&number_of_stars);
    for (int i = 0; i < number_of_stars; i++){
        int _x,_y;
        scanf("%d %d",&_x,&_y);
        _x++;
        
        number_of_same_level_star[query_sum(1,1,_x)] ++ ;
        
        //update
        insert_node(1,_x);
        
        
//        if (i == 0){
//            left_limit = _x;
//            right_limit = _x;
//        } else{
//            left_limit = (_x < left_limit) ? _x : left_limit;
//            right_limit = (_x > right_limit) ? _x : right_limit;
//        }
    }
    
    for (int i = 0; i < number_of_stars; i ++){
        printf("%d\n",number_of_same_level_star[i]);
    }
    
    
    return 0;
}

void build_tree(int i, int left, int right){
    tree_nodes[i].left = left;
    tree_nodes[i].right = right;
    tree_nodes[i].value = 0;
    if (left == right){
        return;
    }
    build_tree(i << 1, left, (right + left)/ 2);
    build_tree((i << 1) +1, (right+left)/ 2 + 1, right);
}
void insert_node(int now, int dest_x){
    tree_nodes[now].value ++;
    if (tree_nodes[now].left == tree_nodes[now].right) {
        return;
    } else{
        if (dest_x <= (tree_nodes[now].left + tree_nodes[now].right) / 2){
            insert_node(now << 1, dest_x);
        } else{
            insert_node((now << 1) + 1, dest_x);
        }
    }
}
int query_sum(int now, int left, int right){
    int sum = 0;
    if (left <= tree_nodes[now].left && tree_nodes[now].right <= right) {
        return tree_nodes[now].value;
    }
    int mid = (tree_nodes[now].left+tree_nodes[now].right)/2;
    if (right <= mid) {
        return query_sum(now << 1,left,right);
    }
    if (left > mid){
        return query_sum((now << 1) + 1, left, right);
    }
    sum = query_sum(now << 1, left, mid) + query_sum((now << 1) + 1, mid + 1, right);
    return sum;
}

「Unity Shaders」Surface Shaders and Texture Mapping

 本文内容参考《Unity 5.x Shaders and Effects Cookbook》 表面着色器和材质贴图 总的来说,一个表面着色器有两个关键的步骤。第一,必须确定材质的物理...

阅读全文

「Unity Shaders」Creating First Shader

创建第一个着色器 最近学习了一段时间Unity Shader相关知识,在进一步自顶向下学习计算机图形学之前,先将之前看《Unity 5.x Shaders and Effects Cookbook...

阅读全文

《Effective c++》、《Inside C++ Model》 小结(一)

最近瞻仰了一下Scott Meyers久负盛名的《effective c++》,特来总结一下,以加深一下印象与防止自己今后记忆力衰退。这本书里很多都是工程上很有意思的tips...

阅读全文

4 条评论

欢迎留言