Tag: 其他C++

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 84538    Accepted Submission(s): 20059

 
===========================================
按照PPT里面的说法，就是“对于这种题目，千万不能蛮干！实际上，有经验的同学看到本题目的数据规模，很快就能知道：这类题目有规律可循。”
由于是mod7的关系，函数f两个参数，都是0~6范围内的，所以共计7*7=49种可能性，这是其一，避免重复计算。
其二，http://www.cnblogs.com/Lyush/archive/2011/09/04/2165927.html里面所说一般，这种东西肯定是有循环的，循环节最大50，何时找到循环呢？两个参数一样的时候呗。这个问题困扰了我一晚上，今天早上实在忍不住搜博客搜到了…所以自己还是太年轻了吧
这两点搞定了，就没有任何问题了。

#include 
using namespace std;
int f(int A, int B, unsigned long n)
{
    if(n == 2 || n == 1)
        return 1;
    int mat[7][7];
    int looked[7][7];
    for(int i=0; i<7; i++)
    {
        for(int j=0; j<7; j++)
        {
            mat[i][j] = (A*i+B*j)%7;
            looked[i][j] = 0;
        }
    }
    int last_2 = 1;
    int last_1 = 1;
    looked[1][1] = 2;
    unsigned long next = n;
    for(unsigned long m=3; m<=next; m++)
    {
        int curr = mat[last_1][last_2];
        last_2 = last_1;
        last_1 = curr;
        if(looked[last_1][last_2] > 0)
        {
            //开始循环了！
            next = (n - looked[last_1][last_2])%(m - looked[last_1][last_2]) + m;
        }
        looked[last_1][last_2] = m;
    }
    return last_1;
}
int main()
{
    int A, B;
    unsigned long n;
    while(cin >> A >> B >> n && A+B+n != 0)
    {
        cout << f(A, B, n) << endl;
    }
    return 0;
}

原题：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1002
试水ZOJ的第一题，果然ACM的难度比PAT大一些，入门题目都那么长…
思路其实不难，弄个二维数组来搞，有点回溯的味道，刚巧最近看书看到了分而治之还要动态规划什么的
某一步的结果= max{当前位置放置1个+后面位置放置个数, 当前位置放置0个+后面位置放置个数}
然后就能做啦~
 

#include 
#include 
#include 
#include     // std::max
using namespace std;
enum state{
    READY, BLOCK, DISABLED, USED
};
/**
从i,j 开始找下一个可用的位置
**/
void findNextPossiblePos(int &i, int &j, int **inData, int N)
{
    for(int m=i; m=0; row--)
    {
        if(s1Data[row][j] == BLOCK)
            break;
        s1Data[row][j]= DISABLED;
    }
    //↓
    for(int row = i+1; row=0; col--)
    {
        if(s1Data[i][col] == BLOCK)
            break;
        s1Data[i][col] = DISABLED;
    }
    //→
    for(int col = j+1; cols2Result)? s1Result:s2Result;
    //mmax[i][j] = retVal;
    return retVal;
}
int main()
{
    int n;
    while(cin >> n)
    {
        if(n == 0)
            break;
        //create data
        int **data = new int*[n];
        for(int i=0; i> c;
                if(c == '.')
                    data[i][j] = READY;
                else if(c == 'X')
                    data[i][j] = BLOCK;
                else
                    data[i][j] = DISABLED;
            }
        }
        /////Start!
        int result = startJob(data, n, 0, 0);
        cout << result << endl;
    }
    return 0;
}

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 23989    Accepted Submission(s): 8466

==========================================
死搞肯定是要超时的….
其实一共9个数字，乘方都是有规律的..写的丑陋了点，不过能用就好^^

#include 
#include 
using namespace std;
const int BUFFER_LENGTH = 31;
const int pattern_size[] = {1, 1, 4, 4, 2, 1, 1, 4, 4, 2};
const int pattern_0[] = {0};
const int pattern_1[] = {1};
const int pattern_2[] = {2, 4, 8, 6};
const int pattern_3[] = {3, 9, 7, 1};
const int pattern_4[] = {4, 6};
const int pattern_5[] = {5};
const int pattern_6[] = {6};
const int pattern_7[] = {7, 9, 3, 1};
const int pattern_8[] = {8, 4, 2, 6};
const int pattern_9[] = {9, 1};
int main()
{
	char a[BUFFER_LENGTH];
	long long b;
	while(cin >> a >> b)
	{
		int len_a = strlen(a);
		int last_digit = a[len_a-1] - 0x30;
		int result;
		b--;
		switch(last_digit)
		{
		case 0:
			result = pattern_0[b%pattern_size[0]];
			break;
		case 1:
			result = pattern_1[b%pattern_size[1]];
			break;
		case 2:
			result = pattern_2[b%pattern_size[2]];
			break;
		case 3:
			result = pattern_3[b%pattern_size[3]];
			break;
		case 4:
			result = pattern_4[b%pattern_size[4]];
			break;
		case 5:
			result = pattern_5[b%pattern_size[5]];
			break;
		case 6:
			result = pattern_6[b%pattern_size[6]];
			break;
		case 7:
			result = pattern_7[b%pattern_size[7]];
			break;
		case 8:
			result = pattern_8[b%pattern_size[8]];
			break;
		case 9:
			result = pattern_9[b%pattern_size[9]];
			break;
		default:
			result = -1;
		}
		cout << result << endl;
	}
	return 0;
}