NEW RDSP MODE I
时间： 1ms 内存：128M
描述：
Little A has became fascinated with the game Dota recently, but he is not a good player. In all the modes, the rdsp Mode is popular on online, in this mode, little A always loses games if he gets strange heroes, because, the heroes are distributed randomly.
Little A wants to win the game, so he cracks the code of the rdsp mode with his talent on programming. The following description is about the rdsp mode:
There are N heroes in the game, and they all have a unique number between 1 and N. At the beginning of game, all heroes will be sorted by the number in ascending order. So, all heroes form a sequence One.
These heroes will be operated by the following stages M times:
1.Get out the heroes in odd position of sequence One to form a new sequence Two;
2.Let the remaining heroes in even position to form a new sequence Three;
3.Add the sequence Two to the back of sequence Three to form a new sequence One.
After M times' operation, the X heroes in the front of new sequence One will be chosen to be Little A's heroes. The problem for you is to tell little A the numbers of his heroes.
输入：
There are several test cases.
Each case contains three integers N (1<=N<1,000,000), M (1<=M<100,000,000), X(1<=X<=20).
Proceed to the end of file.
输出：
For each test case, output X integers indicate the number of heroes. There is a space between two numbers. The output of one test case occupied exactly one line.
示例输入：
5 1 2
5 2 2示例输出：
2 4
4 3提示：
参考答案（内存最优[800]）：
#include <stdio.h>
#include <math.h>
#define __int64 long long
long long done(int m, int n)
{
if(n == 0)
{
return 1;
}
if(n == 1)
{
return 2;
}
__int64 t = done(m, n/2);
t = t*t;
if(n%2 == 0)
{
return (long long)(((t%m)==0)?m:t%m);
}
else
{
return (long long)(((2*t%m)==0) ? m : t%m*2);
}
}
int main()
{
// freopen("in.in","r",stdin);
//freopen("test.out","w",stdout);
//printf("%I64d", ((__int64)(pow(2,59))%1223411) );
int m,n,x;
long long t;
int i;
while(scanf("%d %d %d",&m, &n, &x)!=EOF)
{
if(m % 2 == 0)
m +=1;
t = done(m, n);
t = t == 0?m:t;
//printf("%d\n",t);
for(i=1; i<=x; ++i)
{
if(i != 1)
{
printf(" ");
}
printf("%lld", t*i%m == 0?m: t*i%m);
}
printf("\n");
}
}
参考答案（时间最优[0]）：
#include<iostream>
using namespace std;
int r[] = {0, 0, 1, -1};
int c[] = {1, -1, 0, 0};
int maxi(int a, int b) {
if(a > b) return a;
return b;
}
int dfs(char graph[][100], int row, int col, int maxRow, int maxCol) {
if(row < 0 || row >= maxRow) return 0;
if(col < 0 || col >= maxCol) return 0;
if(graph[row][col] != '*') return 0;
graph[row][col] = '#';
int ret = 1;
for(int i=0; i<4; i++) ret += dfs(graph, row+r[i], col+c[i], maxRow, maxCol);
return ret;
}
int main(void) {
int row, col;
while(cin >> col >> row) {
int answer = 0;
char graph[1100][100];
for(int i=0; i<row; i++)
for(int j=0; j<col; j++) cin >> graph[i][j];
for(int i=0; i<row; i++) {
for(int j=0; j<col; j++) {
if(graph[i][j] == '*') {
answer = maxi(answer, dfs(graph, i, j, row, col));
}
}
}
cout << answer << endl;
}
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。