POJ2253 Frogger

发表于 2017-09-21 | 分类于 algorithm

题目大意

图中的一个点到另一个点, 每条路径都有一个最大的跳跃长度, 求所有路径的最大跳跃长度当中最小值.

涉及知识点

其实是考察最短路算法(Dijkstra, Floyd等)的变形, Dijkstra 和 Floyd 算法通常用来求最短路, 但其实只要改变边的松弛条件, 存储边的数组的含义便会发生改变, 比如PAT10031(使用Dijkstra可以求带点权图的最短路).

使用Dijkstra

思路

根据题目要求, dis数组的含义变为从一个点出发, 到其他点的最长路径中的最小值, 因此, dis的松弛条件变为 dis[v] = min(dis[v], max(dis[u], edge[u][v])), 所以说用Dijkstra的变形的时候一定要考虑不同的松弛条件, dis数组的含义是不同的

代码

#include <iostream>
#include <cmath>
#include <iomanip>
#include <cstring>
#include <cmath>
using namespace std;
double max(double a, double b){
  return a > b ? a : b;
}
double mina(double a, double b){
  return a < b ? a : b;
}
const int maxn = 210;
struct Point{
  int x, y;
}arr[maxn];
double getDis(Point a, Point b){
  return sqrt((a.x - b.x) * (a.x  - b.x) + (a.y - b.y) * (a.y - b.y));
}
double edge[maxn][maxn];
double dijkstra(int nC){
  double dis[maxn];
  for(int i = 0; i < nC; ++i){
    dis[i] = edge[0][i];
  }
  bool isVis[maxn];
  for(int i = 0; i < nC; ++i)
    isVis[i] = false;
  isVis[0] = true;
  for(int i = 0; i < nC; ++i){
    int u;
    double min = 99999;
    for(int j = 0; j < nC; j++){
      if(isVis[j])
        continue;
      if(dis[j] < min){
        min = dis[j];
        u = j;
      }
    }
    isVis[u] = true;
    for(int v = 0; v < nC; ++v){
      dis[v] = mina(dis[v], max(dis[u], edge[u][v]));
    }
  }
  return dis[1];
}
int main(){
  int t = 0;
  int nCase;
  while(cin >> nCase && nCase != 0){
    t++;
    for(int i = 0; i < nCase; i++){
      cin >> arr[i].x >> arr[i].y;
    }
    for(int i = 0; i < maxn; i++){
      for(int j = 0; j < maxn; j++)
        edge[i][j] = 0;
    }
    for(int i = 0; i < nCase; i++){
      for(int j = i + 1; j < nCase; j++){
        edge[i][j] = edge[j][i] = getDis(arr[i], arr[j]);
      }
    }
    //
    // for(int i = 0; i < nCase; i++){
    //   for(int j = 0; j < nCase; j++)
    //     cout << edge[i][j] << " ";
    //   cout << endl;
    // }
    //
    cout << "Scenario #" << t << "\nFrog Distance = " << fixed << setprecision(3) << dijkstra(nCase) << endl << endl;
  }
  return 0;
}

使用Floyd

思路

同理, 根据题目要求, Floyed中的edge数组, 代表不同两点之间最长路径的最小值. 因此, 松弛条件为 edge[i][j] = min(edge[i][j], max(edge[i][k], edge[k][j]));

代码

#include<iostream>
#include <cmath>
#include <cstdio>
#include <iomanip>
using namespace std;
struct Point{
  int x, y;
};
Point arr[210];
double getDis(Point a, Point b){
  return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double edge[210][210];
int main(){
  int nCase = -1;
  int t = 0;
  while(cin >> nCase && nCase != 0){
    t++;
    for(int i = 0; i < nCase; i++){
        cin >> arr[i].x >> arr[i].y;
    }
    for(int i = 0; i < nCase; i++){
      for(int j = i + 1; j < nCase; j++){
        edge[i][j] = edge[j][i] = getDis(arr[i], arr[j]);
      }
    }
    for(int k = 0; k < nCase; k++){
      for(int i = 0; i < nCase; i++){
        for(int j = 0; j < nCase; j++){
          edge[i][j] = min(edge[i][j], max(edge[i][k], edge[k][j]));
        }
      }
    }
    cout << "Scenario #" << t << "\nFrog Distance = ";
    cout << fixed << setprecision(3) <<edge[0][1] << endl << endl;
  }
  return 0;
}

总结

在进行最短路变形问题求解的时候, 一定要搞明白松弛条件和数组的含义, 松弛条件不同, 数组的含义也不同.

POJ1426 Find The Multiple

发表于 2017-09-14 | 分类于 Algorithm

题目大意

给定一个数字 n, 求 n 的一个倍数 m. m 的要求是一个只由 0 和 1 构成的十进制数字.

题目思路

对于一个 m 第一位肯定为 1, 剩下的每一位有 0 和 1 两种情况, 如果进行穷举, 数会变得很大. 因此, 需要运用同余模定理, 减少中间数字规模.

知识点

1 2	（ab）%n = （a%n b%n）%n （a+b）%n = （a%n +b%n）%n

代码

#include <iostream>
#include <cstring>
using namespace std;
const int maxV = 999999;
int m[maxV];
int rec[maxV];
int main() {
	int val;
	while (cin >> val && val) {
		memset(m, 0, sizeof(m));
		m[1] = 1;
		int i;
		for (i = 2; m[i - 1] != 0; i++) {
			m[i] = (m[i / 2] * 10 + i % 2) % val;
		}
		int len = 0;
		i--;
		while (i) {
			rec[len++] = i % 2;
			i /= 2;
		}
        while(len)
            cout << rec[--len];
		cout << endl;
	}
	return 0;
}

参考链接

POJ1426-Find The Multiple
poj 1426 Find The Multiple搜索BFS的思想+ 同余模定理+二叉树+01哈夫曼编码

POJ3279 Fliptile

发表于 2017-09-14 | 分类于 Algorithm

题目大意

给定一个矩阵，其中有 0 和 1. 每次旋转可以将 0 变为 1, 将 1 变为 0. 但每次旋转一个方块时, 所有邻接的方块都会被旋转, 求字典序最小的旋转方式.

思路

若给定第一行的旋转排列, 便可以得到整个矩阵的旋转方式. 矩阵最大为15 × 15 的标准, 因此可以使用状态压缩第一行, 求出剩下行数的旋转次数与方式, 并进行保存.

代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAX = 20;
int nRow, nCol;
int tile[MAX][MAX];
int flip[MAX][MAX];
int opt[MAX][MAX];
int d[][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {0, 0}};
int getColor(int x, int y) {
	int cnt = tile[x][y];
	for (int i = 0; i < 5; i++) {
		int x1 = x + d[i][0];
		int y1 = y + d[i][1];
		if(x1 >= 0 && x1 < nRow && y1 >= 0 && y1 < nCol)
			cnt += flip[x1][y1];
	}
	return cnt % 2;
}
int cntF() {
	for (int i = 0; i < nRow - 1; i++) {
		for (int j = 0; j < nCol; j++) {
			if (getColor(i, j) == 1) {
				flip[i + 1][j] = 1;
			}
		}
	}
	for (int j = 0; j < nCol; j++) {
		if (getColor(nRow - 1, j) == 1)
			return -1;
	}
	int cnt = 0;
	for (int i = 0; i < nRow; i++) {
		for (int j = 0; j < nCol; j++) {
			cnt += flip[i][j];
		}
	}
	return cnt;
}
int solve() {
	int res = -1;
	for (int i = 0; i < (1 << nCol); ++i) {
		memset(flip, 0, sizeof(flip));
		for (int j = 0; j < nCol; ++j) {
			flip[0][nCol - 1 - j] = (i >> j) & 1;
		}
		int temp = cntF();
		if ((temp >= 0) && (res == -1 || res > temp)) {
			res = temp;
			memcpy(opt, flip, sizeof(flip));
		}
	}
	return res;
}
int main() {
	cin >> nRow >> nCol;
	for (int i = 0; i < nRow; i++)
		for (int j = 0; j < nCol; j++)
			cin >> tile[i][j];
	if (solve() == -1) {
		cout << "IMPOSSIBLE";
	}
	else {
		for (int i = 0; i < nRow; ++i)
			for (int j = 0; j < nCol; ++j)
				printf("%d%c", opt[i][j], j == nCol - 1 ? '\n' : ' '); 
	}
//	system("pause");
	return 0;
}

I AM BACK

发表于 2017-09-14

Pop Sequence

发表于 2017-07-21 | 分类于 algorithm

题目大意

给定栈的大小m，序列长度n，和测试数据的个数k
每一组序列的入栈顺序都为 1 - n, 求每组出栈顺序能否成立。

思路

对于每一组序列， 入栈次序都为 1 - n，而出栈次序已经给出，我们只需要一次入栈，当栈顶元素为序列中的一个元素时即出栈，模拟看是否能够实现。
设置cur变量指向序列中元素， 循环进行1 - n的压栈操作，当遇到cur指向的元素与栈顶元素相等即出栈，直至不相等。

代码

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main()
{
    int sizeOfStack, lenSeq, nSeq;
    cin >> sizeOfStack >> lenSeq >> nSeq;
    for(int k = 0; k < nSeq; k++)
    {
        vector<int> seq(lenSeq + 1);
        stack<int> st;
        bool flag = false;
        for(int i = 1; i <= lenSeq; i++)
            cin >> seq[i];
        int cur = 1;
        for(int i = 1; i <= lenSeq; i++)
        {
            st.push(i);
            if(st.size() > sizeOfStack)
                break;
            while(st.empty() == false && seq[cur] == st.top() )
            {
                //cout << st.top();
                st.pop();
                cur++;
            }
        }
        if(cur == lenSeq + 1)
            flag = true;
        if(flag) cout << "YES" << endl;
        else    cout << "NO" << endl;
    }
    return 0;
}

infixToSuffixExpresion

发表于 2017-07-21 | 分类于 algorithm

中缀表达式转后缀表达式

思路

将中缀表达式读入字符串, 不断读入字符。
若字符为数字, 则直接打印。
若字符为运算符, 若栈顶元素运算的优先级高于读入的运算符的优先级，则弹出栈顶元素，压栈读入的运算符。
需要特殊说明的是括号的优先级, 左括号在压栈之前的优先级最高(括号的读取不能使任何之前的运算符进行出栈操作, 即所有操作都要等待括号的运算完成)， 在栈中优先级最低（在括号中, 括号的存在不能影响任何括号内的运算）。

代码实现

import java.util.HashMap;
import java.util.Scanner;
import java.util.Stack;
public class infixToSuffixExpresion {
	public static void main(String[] args)
	{
		// (的优先级在栈中最低， 但没必要另建一个表
		HashMap<Character, Integer> priorty = new HashMap<Character, Integer>();
		priorty.put('(', 0);
		priorty.put('+', 1); 
		priorty.put('-', 1); 
		priorty.put('*', 2); 
		priorty.put('/', 2); 
		Scanner in = new Scanner(System.in);
		String infix = in.next();
		StringBuilder ans = new StringBuilder();
		Stack<Character> oper = new Stack<Character>();
		for(int i = 0; i < infix.length(); ++i)
		{
			Character c = infix.charAt(i);
			if(c >= '0' && c <= '9')
			{
				ans.append(c);
				continue;
			}
			if(true == oper.isEmpty())
			{
				oper.push(c);
				continue;
			}
			
			if(c == '(')
			{
				oper.push(c);
			}
			else if(')' == c)
			{
				while(oper.peek() != '(')
				{
					ans.append(oper.peek());
					oper.pop();
				}
				oper.pop();
			}
			else if(priorty.get(oper.peek()) >= priorty.get(c))
			{
				ans.append(oper.peek());
				oper.pop();
				oper.push(c);
			}
			else if(priorty.get(oper.peek()) < priorty.get(c))
			{
				oper.push(c);
			}
		}
		while(oper.empty() == false)
		{
			ans.append(oper.peek());
			oper.pop();
		}
		System.out.println(ans);
		//System.out.println(oper.toString());
		in.close();
	}
}

秦九韶算法

发表于 2017-07-21 | 分类于 algorithm

简介

当处理一个多项式在 x = x0 处的值的时候, 不断地对求 x^n 是低效的。尤其是当n很大的时候, pow(x, n)在多项式系数的循环当中将整个算法的复杂度变为O(n^2).

公式

程序实现

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> arr(n + 1);
    for(int i = 0; i <= n; ++i)
    {
        cin >> arr[i];
    }
    int x;
    cin >> x;
    int ans = arr[n];
    for(int i = n - 1; i >= 0; --i)
    {
        ans = ans * x + arr[i];
    }
    cout << ans << endl;
    return 0;
}

import java.util.ArrayList;
import java.util.Scanner;
public class QinJiuZhaoAlgorithm {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		ArrayList<Integer> arr = new ArrayList<Integer>();
		int nNum = in.nextInt();
		for(int i = 0; i <= nNum; i++)
		{
			arr.add(in.nextInt());
		}
		int x = in.nextInt();
		int ans = arr.get(arr.size() - 1);
		for(int i = arr.size() - 2; i >= 0; --i)
		{
			ans = arr.get(i) + x * ans;
		}
		System.out.println(ans);
	}
}

HDU1584

发表于 2017-05-08 | 分类于 algorithm

题目大意

给定值为1到10的纸牌的顺序，每张牌只能放在大一的纸牌上，每次移动的代价为两张牌的差值的绝对值，求最小代价。

题目思路

在不改变数组排列顺序的前提下生成全排列的题，当然还要带上剪枝和关于回溯的判断，真的是考察dfs的好题。

代码

#include <iostream>
#include <cmath>
using namespace std;
int loc[11];
int isUsed[11];
int ans;
void dfs(int step, int temp)
{
    //剪枝. 无论何时, 只要当前步数大于已知的ans(最大值), 就进行回溯
    if(ans < temp)
        return;
    //由于值为10的牌的特殊性, 不需要进行移动, 所以步数为9步即可得出结论
    if(step == 9)
    {
        if(ans >= temp)
            ans = temp;
        return;
    }
    //选择进行九张牌的移动, 移动九次
    //在第几层递归, 此循环就选择i当作, 该层的一个子树的根节点
    for(int i = 1; i < 10; i++)
    {
        if(isUsed[i])
            continue;
        //选择移动到第几张牌的下面
        for(int j = i + 1; j <= 10; j++)
        {
            //比如要移1了，如果2,3,4,5都已经被移动过了 那么这几张牌必定叠放在6的下面，所以要移到6的位置
            if(isUsed[j])
                continue;
            isUsed[i] = true;
            dfs(step + 1, temp + abs(loc[i] - loc[j]));
            isUsed[i] = false;
            //注意不要再这个地方回溯 如果回溯了 就像是又一个全排列 而且牌得移动不合理，比如2移到6了，结果回溯就直接跳过3~6到了7的下面(比如: temp的值比ans更大, 但说不定2 -> 6的移动是合法的, 但之后存在不合法的移动)
            break;
        }
    }
}
int main()
{
    int nTest;
    cin >> nTest;
    while(nTest--)
    {
        for(int i = 1; i <= 10; i++)
        {
            int val;
            cin >> val;
            //怎么存储数据也是有讲究的
            loc[val] = i;
            isUsed[i] = false;
        }
        ans = 9999999;
        dfs(0, 0);
        cout << ans << endl;
    }
    return 0;
}

参考链接

hdu1584 蜘蛛牌（经典dfs）
hdu 1584 蜘蛛牌

HDU1097

发表于 2017-05-03 | 分类于 algorithm

题目大意

给定a, b求 a ^ b的个位数字.
(0<a,b<=2^30)

思路

这道题肯定是使用快速幂取模解题。
但是如果直接quickMod(a, b, c)肯定会爆掉，因为a最大值2 ^ 30在进入函数平方后，会超出int数据类型，所以应该quickMod(a % c, b, c)

代码

#include <stdio.h>
int quickMod(int a, int b, int c)
{
    int ans = 1;
    while(b)
    {
        if(b % 2)
            ans = (ans * a) % c;
        a = (a * a) % c;
        b /= 2;
    }
    return ans;
}
int main()
{
    int a, b;
    while(~scanf("%d%d", &a, &b))
    {
        printf("%d\n", quickMod(a % 10, b, 10));
    }
    return 0;
}

题目链接

HDU1097

快速幂取模

发表于 2017-05-03 | 分类于 algorithm

快速幂

基本公式

过程

以 b 为偶数举例
a^b%c = ((a^2)^b/2)%c

若 b / 2仍为偶数，那么
((a^2)^b/2)%c = (((a^2)^2)^(b/2)/2)%c

举例

3 ^ 16
= (3     * 3    ) ^ 8
= (3 ^ 2 * 3 ^ 2) ^ 4 //3^2 由上一步3 * 3得
= (3 ^ 4 * 3 ^ 4) ^ 2 //3^4 由上一步3 ^ 2 * 3 ^ 2得
= (3 ^ 8 * 3 ^ 8) ^ 1 //3^8 由上一步3 ^ 4 * 3 ^ 4得

代码

int myQuickPow1(int a, int b)
{
    int ans = 1;
    while(b != 0)
    {
        if(b % 2 == 1)
            ans = ans * a;
        a = a * a;
        b = b / 2;
    }
    return ans;
}

也可以取模

int myQuickMod1(int a, int b, int c)
{
    int ans = 1;
    while(b != 0)
    {
        if(b % 2 == 1)
            ans = (ans * a) % c;
        a = (a * a) % c;
        b = b / 2;
    }
    return ans;
}

参考链接

快速幂取余算法总结详解