也是时隔那么长时间,再一次写解题报告,相比以前,现在只是为了提高能力,还没有更多可见的比赛或者考试需要准备。所以从简单到难慢慢磨练自己吧。
另外,马上就考ccf了,于是做了一下网上的模拟题安慰一下自己,如果难度差不多就是这样,那还是可以接受,感觉连noip难的时候的水平都没有达到。1,2,3题纯送分,就不记录了。来看看有趣的数和I’m stuck!吧

有趣的数

问题描述
我们把一个数称为有趣的,当且仅当:
1. 它的数字只包含0, 1, 2, 3,且这四个数字都出现过至少一次。
2. 所有的0都出现在所有的1之前,而所有的2都出现在所有的3之前。
3. 最高位数字不为0。
因此,符合我们定义的最小的有趣的数是2013。除此以外,4位的有趣的数还有两个:2031和2301。
请计算恰好有n位的有趣的数的个数。由于答案可能非常大,只需要输出答案除以1000000007的余数。
输入格式
输入只有一行,包括恰好一个正整数n (4 ≤ n ≤ 1000)。
输出格式
输出只有一行,包括恰好n 位的整数中有趣的数的个数除以1000000007的余数。
样例输入
4
样例输出
3
这题自己做的时候觉得就是个数学题,于是开始找规律,发现一个简单的公式,对于前几项时显然成立,于是就用上了,不知道是不是因为计算过程中数据溢出了,答案一直不对

//
//  main.cpp
//  main1
//
//  Created by 缪哲文 on 15/9/12.
//  Copyright (c) 2015年 缪哲文. All rights reserved.
//

#include <iostream>
using namespace std;

const long long p = 1000000007;

long long pow(long long a,long long b)
{
    long long result = 1, base = a;
    while(b!=0)
    {
        if(b&1)
            result = (base * result) % p;
        base = (base * base) % p;
        b >>= 1;
    }
    return result;
}
int main(){
    long long n;
    cin >> n;
    long long answer = (n-1)*(n-3);
    
    for (int i = 3; i < n - 1; i++){
        answer =(answer + (pow(i, n-i)*(n-i)) % p) % p;
    }
    
    cout << answer << endl;
    return 0;
}

参考网上动态规划的思路。
我们对一个数的第n位规定:到这一位为止还有哪几个数字没有使用。
共有6种状态:
    0--用了2,剩0,1,3
1--用了0,2,剩1,3
2--用了2,3,剩0,1
3--用了0,1,2,剩3
4--用了0,2,3,剩1
5--全部用了
用动态规划思想从第一位向左开始计算。
例如对i位状态5的计算,考虑在i-1位时有三种状态可以到达状态5,第3种,此时只能在i位填3,所以*1;第4种,此时只能在i位填1,所以*1;第5种,此时能在i位填2或3(参考规则),所以*2;
  states[i][5] = (states[i-1][3] + states[i-1][4] + states[i-1][5] * 2) % mod;
其他同上。
最后完成计算只需输出n位的第5种状态中的个数。

//
//  main.cpp
//  t
//
//  Created by 缪哲文 on 15/9/13.
//  Copyright (c) 2015年 缪哲文. All rights reserved.
//

#include <iostream>

using namespace std;

const long long p = 1000000007;

long long apow(long long a, long long b)
{
	long long result = 1, base = a;
	while (b != 0)
	{
		if (b & 1)
			result = (base * result) % p;
		base = (base * base) % p;
		b >>= 1;
	}
	return result;
}
int main() {
	long long mod = 1000000007;
	long long n;
	cin >> n;
	long long **states = new long long*[n + 1];
	for (long long i = 0; i<n + 1; i++)
		states[i] = new long long[6];
	for (long long i = 0; i<6; i++)
		states[0][i] = 0;
	/*6种状态
	* 0--剩013
	* 1--剩13
	* 2--剩01
	* 3--剩3
	* 4--剩1
	* 5--无
	*/
	for (long long i = 1; i <= n; i++)
	{
		long long j = i - 1;
		states[i][0] = 1;
		states[i][1] = (states[j][0] + states[j][1] * 2) % mod;
		states[i][2] = (states[j][0] + states[j][2]) % mod;
		states[i][3] = (states[j][1] + states[j][3] * 2) % mod;
		states[i][4] = (states[j][1] + states[j][2] + states[j][4] * 2) % mod;
		states[i][5] = (states[j][3] + states[j][4] + states[j][5] * 2) % mod;
	}
	cout << states[n][5] << endl;

	return 0;
}

I'm stuck

问题描述
给定一个R行C列的地图,地图的每一个方格可能是’#’, ‘+’, ‘-‘, ‘|’, ‘.’, ‘S’, ‘T’七个字符中的一个,分别表示如下意思:
‘#’: 任何时候玩家都不能移动到此方格;
‘+’: 当玩家到达这一方格后,下一步可以向上下左右四个方向相邻的任意一个非’#’方格移动一格;
‘-‘: 当玩家到达这一方格后,下一步可以向左右两个方向相邻的一个非’#’方格移动一格;
‘|’: 当玩家到达这一方格后,下一步可以向上下两个方向相邻的一个非’#’方格移动一格;
‘.’: 当玩家到达这一方格后,下一步只能向下移动一格。如果下面相邻的方格为’#’,则玩家不能再移动;
‘S’: 玩家的初始位置,地图中只会有一个初始位置。玩家到达这一方格后,下一步可以向上下左右四个方向相邻的任意一个非’#’方格移动一格;
‘T’: 玩家的目标位置,地图中只会有一个目标位置。玩家到达这一方格后,可以选择完成任务,也可以选择不完成任务继续移动。如果继续移动下一步可以向上下左右四个方向相邻的任意一个非’#’方格移动一格。
此外,玩家不能移动出地图。
请找出满足下面两个性质的方格个数:
1. 玩家可以从初始位置移动到此方格;
2. 玩家不可以从此方格移动到目标位置。
输入格式
输入的第一行包括两个整数R 和C,分别表示地图的行和列数。(1 ≤ R, C ≤ 50)。
接下来的R行每行都包含C个字符。它们表示地图的格子。地图上恰好有一个’S’和一个’T’。
输出格式
如果玩家在初始位置就已经不能到达终点了,就输出“I’m stuck!”(不含双引号)。否则的话,输出满足性质的方格的个数。
样例输入
5 5
–+-+
..|#.
..|##
S-+-T
####.
样例输出
2
样例说明
如果把满足性质的方格在地图上用’X’标记出来的话,地图如下所示:
–+-+
..|#X
..|##
S-+-T
####X
其实并没有什么难度,只是做两遍“灌水”一样,就是从一点开始——让被标记的点向周围扩散的dfs或者bfs。第一次从开始点出发,标记可以到达的点,第二次以终点为目标,找可以到终点的所有点,所以两次dfs的判断方式有所不同。

//
//  main3.cpp
//  main1
//
//  Created by 缪哲文 on 15/9/12.
//  Copyright (c) 2015年 缪哲文. All rights reserved.
//

#include <iostream>

using namespace std;

int row, colomn,
    mapa[50][50],
    mapb[50][50],
    map[50][50],
    sx,sy,tx,ty;

void dfs(int m[50][50],int x,int y){
    int flag = map[x][y];
    if (m[x][y] == 1) return;
    if (flag == 0) return;
    m[x][y] = 1;
    if (flag == 1 || flag == 5 || flag == 6) {
        int targetx = x + 1, targety = y; // 向下
        if (targetx < row && targetx >= 0 && targety < colomn && targety >= 0) {
            dfs(m, targetx, targety);
        }
        targetx = x - 1; targety = y; // 向上
        if (targetx < row && targetx >= 0 && targety < colomn && targety >= 0) {
            dfs(m, targetx, targety);
        }
        targetx = x; targety = y + 1; // 向右
        if (targetx < row && targetx >= 0 && targety < colomn && targety >= 0) {
            dfs(m, targetx, targety);
        }
        targetx = x; targety = y - 1; // 向左
        if (targetx < row && targetx >= 0 && targety < colomn && targety >= 0) {
            dfs(m, targetx, targety);
        }
    } else if (flag == 2){
        int targetx = x; int targety = y + 1; // 向右
        if (targetx < row && targetx >= 0 && targety < colomn && targety >= 0) {
            dfs(m, targetx, targety);
        }
        targetx = x; targety = y - 1; // 向左
        if (targetx < row && targetx >= 0 && targety < colomn && targety >= 0) {
            dfs(m, targetx, targety);
        }
    } else if (flag == 3){
        int targetx = x + 1, targety = y; // 向下
        if (targetx < row && targetx >= 0 && targety < colomn && targety >= 0) {
            dfs(m, targetx, targety);
        }
        targetx = x - 1; targety = y; // 向上
        if (targetx < row && targetx >= 0 && targety < colomn && targety >= 0) {
            dfs(m, targetx, targety);
        }

    } else if (flag == 4){
        int targetx = x + 1, targety = y; // 向下
        if (targetx < row && targetx >= 0 && targety < colomn && targety >= 0) {
            dfs(m, targetx, targety);
        }
    }
}

void dfs2(int m[50][50], int x, int y){
    if (m[x][y] == 1) return;
    m[x][y] = 1;
    int sourcex = x - 1; int sourcey = y; // 从上
    if (sourcex < row && sourcex >= 0 && sourcey < colomn && sourcey >= 0) {
        if (map[sourcex][sourcey] != 0 && map[sourcex][sourcey] != 2) {
            dfs2(m, sourcex, sourcey);
        }
    }
    sourcex = x + 1; sourcey = y; // 从下
    if (sourcex < row && sourcex >= 0 && sourcey < colomn && sourcey >= 0) {
        if(map[sourcex][sourcey] != 0 && map[sourcex][sourcey] != 2 
&& map[sourcex][sourcey] != 4){
            dfs2(m, sourcex, sourcey);
        }
    }
    sourcex = x; sourcey = y - 1; // 从左
    if (sourcex < row && sourcex >= 0 && sourcey < colomn && sourcey >= 0) {
        if (map[sourcex][sourcey] != 0 && map[sourcex][sourcey] != 3 
&& map[sourcex][sourcey] != 4) {
            dfs2(m, sourcex, sourcey);
        }
        
    }
    sourcex = x; sourcey = y + 1; // 从右
    if (sourcex < row && sourcex >= 0 && sourcey < colomn && sourcey >= 0) {
        if (map[sourcex][sourcey] != 0 && map[sourcex][sourcey] != 3 
&& map[sourcex][sourcey] != 4) {
            dfs2(m, sourcex, sourcey);
        }
    }
}

int main(){
    cin >> row >> colomn;
    string line;
    getline(cin, line);
    
    for (int i = 0; i < row; i ++){
        getline(cin,line);
        for (int j =0; j < line.length(); j ++){
            switch (line[j]) {
                case '#':
                    map[i][j] = 0;
                    break;
                case '+':
                    map[i][j] = 1;
                    break;
                case '-':
                    map[i][j] = 2;
                    break;
                case '|':
                    map[i][j] = 3;
                    break;
                case '.':
                    map[i][j] = 4;
                    break;
                case 'S':
                    map[i][j] = 5;
                    sx=i;
                    sy=j;
                    break;
                case 'T':
                    map[i][j] = 6;
                    tx=i;
                    ty=j;
                    break;
                default:
                    break;
            }
        }
    }
    
    dfs(mapa,sx,sy);
    if (mapa[tx][ty] == 0){
        cout << "I'm stuck!" << endl;
        return 0;
    }
    dfs2(mapb,tx,ty);
    
    int sum = 0;
    for (int i = 0; i < row; i ++){
        for (int j = 0; j < colomn; j ++) {
            if (mapa[i][j] == 1 && mapb[i][j] == 0) {
                sum ++;
            }
        }
    }
    
    cout << sum << endl;
    
    return 0;
}

「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 条评论

欢迎留言