小弟我实在是没办法了，pku 2886 一直WA 请高手看一下代码
我实在是没办法了，pku 2886 一直WA 请高手看一下代码
#include <iostream>
#include <cmath>
#include <fstream>
using std::cout;
using std::endl;
using std::ifstream;
using std::cin;
//ifstream cin( "in.txt" );
const int MAXLENGTH = 11;
const int MAXNUM = 500001;
const int ITEMNUM = 37;
struct Internal{
int left;
int right;
};
struct Leaf{
char name[MAXLENGTH];
int turn;
};
union Content{
public:
Leaf l;
Internal i;
};
struct Node{
Content c;
bool isleaf;
};
Node* child;
int (*tableItem)[2];
int n;
int curN;
int nameStart;
int totalFloor;
int targetItemIdx;
void build( int node, int num ){
if( num == 1 ){
cin >> child[node].c.l.name;
cin >> child[node].c.l.turn;
child[node].isleaf = true;
return;
}
int m = num / 2;
child[node].c.i.left = m;
child[node].c.i.right = num - child[node].c.i.left;
child[node].isleaf = false;
build( node * 2, child[node].c.i.left );
build( node * 2 + 1, child[node].c.i.right );
return;
}
void pick( int turn , int localTurn, int node ){
if( child[node].isleaf ){
curN --;
if( n - curN == tableItem[targetItemIdx][0] )
cout << child[node].c.l.name << ' ' << tableItem[targetItemIdx][1] << endl;
else{
if( child[node].c.l.turn < 0 ){
int temp = (turn -2 - child[node].c.l.turn) % curN + 1 ;
pick( temp, temp, 1 );
}
else{
int temp = curN - (( curN - turn ) + child[node].c.l.turn ) % curN ;
pick( temp, temp, 1 );
}
}
}
else{
if( child[node].c.i.left >= localTurn ){
child[node].c.i.left--;
pick( turn, localTurn, node * 2 );
}
else{
child[node].c.i.right--;
pick( turn, localTurn - child[node].c.i.left, node * 2 + 1 );
}
}
}
int main(){
child = new Node[MAXNUM * 3];
//clock_t start = clock();
int theTableItem[ITEMNUM + 1][2] = { 1,1,2,2,4,3,6,4,12,6,24,8,36,9,48,10,60,12,
120,16,180,18,240,20,360,24,720,30,840,32,
1260,36,1680,40,2520,48,5040,60,7560,64,
10080,72,15120,80,20160,84,25200,90,27720,96,
45360,100,50400,108,55440,120,83160,128,
110880,144,166320,160,221760,168,277200,180,
332640,192,498960,200, 554400,216, 665280, 224 };
tableItem = theTableItem;
// cout << table[MAXNUM -1][0] << endl;
//cout << "time_used:" << clock() - start << endl;
int k;
while( !cin.eof()){
cin >> n >> k;
//cin.ignore();
curN = n;
int l = -1;
int r = ITEMNUM + 1;
while( l != r -1 ){
int m = ( l + r )/ 2;
if( n >= tableItem[m][0] )
l = m;
else r = m;
}
targetItemIdx = l;
build( 1, n );
pick( k, k, 1 );
}
delete []child;
delete []tableItem;
//system( "pause" );
return 0;
}
------解决方案--------------------
#include <iostream>
#include <cmath>
#include <fstream>
using std::cout;
using std::endl;
using std::ifstream;
using std::cin;
//ifstream cin( "in.txt" );
const int MAXLENGTH = 11;
const int MAXNUM = 500001;
const int ITEMNUM = 37;
struct Internal{
int left;
int right;
};
struct Leaf{
char name[MAXLENGTH];
int turn;
};
union Content{
public:
Leaf l;
Internal i;
};
struct Node{
Content c;
bool isleaf;
};
Node* child;
int (*tableItem)[2];
int n;
int curN;
int nameStart;
int totalFloor;
int targetItemIdx;
void build( int node, int num ){
if( num == 1 ){
cin >> child[node].c.l.name;
cin >> child[node].c.l.turn;
child[node].isleaf = true;
return;
}
int m = num / 2;
child[node].c.i.left = m;
child[node].c.i.right = num - child[node].c.i.left;
child[node].isleaf = false;
build( node * 2, child[node].c.i.left );
build( node * 2 + 1, child[node].c.i.right );
return;
}
void pick( int turn , int localTurn, int node ){
if( child[node].isleaf ){
curN --;
if( n - curN == tableItem[targetItemIdx][0] )
cout << child[node].c.l.name << ' ' << tableItem[targetItemIdx][1] << endl;
else{
if( child[node].c.l.turn < 0 ){
int temp = (turn -2 - child[node].c.l.turn) % curN + 1 ;
pick( temp, temp, 1 );
}
else{
int temp = curN - (( curN - turn ) + child[node].c.l.turn ) % curN ;
pick( temp, temp, 1 );
}
}
}
else{
if( child[node].c.i.left >= localTurn ){
child[node].c.i.left--;
pick( turn, localTurn, node * 2 );
}
else{
child[node].c.i.right--;
pick( turn, localTurn - child[node].c.i.left, node * 2 + 1 );
}
}
}
int main(){
child = new Node[MAXNUM * 3];
//clock_t start = clock();
int theTableItem[ITEMNUM + 1][2] = { 1,1,2,2,4,3,6,4,12,6,24,8,36,9,48,10,60,12,
120,16,180,18,240,20,360,24,720,30,840,32,
1260,36,1680,40,2520,48,5040,60,7560,64,
10080,72,15120,80,20160,84,25200,90,27720,96,
45360,100,50400,108,55440,120,83160,128,
110880,144,166320,160,221760,168,277200,180,
332640,192,498960,200, 554400,216, 665280, 224 };
tableItem = theTableItem;
// cout << table[MAXNUM -1][0] << endl;
//cout << "time_used:" << clock() - start << endl;
int k;
while( !cin.eof()){
cin >> n >> k;
//cin.ignore();
curN = n;
int l = -1;
int r = ITEMNUM + 1;
while( l != r -1 ){
int m = ( l + r )/ 2;
if( n >= tableItem[m][0] )
l = m;
else r = m;
}
targetItemIdx = l;
build( 1, n );
pick( k, k, 1 );
}
delete []child;
delete []tableItem;
//system( "pause" );
return 0;
}
------解决方案--------------------
- C/C++ code
//约瑟夫环,反素数
//用树状数组+二分枚举过的
#include <iostream>
#include <deque>
#include <vector>
#include <string>
using namespace std;
const int MAX = 500005;
char names[MAX][12];
int number[MAX];
int position[]={1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,
15120,20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,500100};
int value[]={1,2,3,4,6,8,9,10,12,16,18,20,24,30,32,36,40,48,60,64,72,80,84,90,96,100,108,120,128,144,
160,168,180,192,200,0};
int tree[MAX];
void inc(int x, int n, int value)
{
for (; x <= n; x += x & -x) tree[x] += value;
}
int sum(int x)
{
int ret = 0;
for (; x; x -= x & -x) ret += tree[x];
return ret;
}
int main(void)
{
int n, k;
while (scanf("%d%d", &n, &k) == 2)
{
for (int i = 1; i <= n; ++i) scanf("%s%d", names[i], &number[i]), tree[i] = i & -i;
int where;
for(where = 0; where < 36 && n >= position[where]; ++where);
int curr = k - 1, abs_pos = k, dest = position[--where];
for (int i = 0, t = n - 1; i < dest - 1; ++i, --t)
{
if (number[abs_pos] > 0)
curr = (curr - 1 + number[abs_pos]) % t;
else
curr = ((curr + t + number[abs_pos]) % t + t) % t;
inc(abs_pos, n, -1);
int l = 1, r = n;
for (; l <= r;)
{
int mid = (l+r)/2;
if (sum(mid) >= curr+1) r = mid - 1;
else l = mid + 1;
}
abs_pos = l;
}
printf("%s %d\n", names[abs_pos], value[where]);
}
return 0;
}
------解决方案--------------------
- C/C++ code
//用线段树过的
#include <iostream>
#include <deque>
#include <vector>
#include <string>
using namespace std;
const int MAX = 500005;
char names[MAX][12];
int number[MAX];
int tree[MAX*4];
int position[]={1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,
15120,20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,500100};
int value[]={1,2,3,4,6,8,9,10,12,16,18,20,24,30,32,36,40,48,60,64,72,80,84,90,96,100,108,120,128,144,
160,168,180,192,200,0};
void create(int root, int l, int r)
{
if (l == r) {tree[root] = 1;return;}
int mid = (l+r)/2;
int root2 = root << 1;
create(root2, l, mid);
create(root2+1, mid+1, r);
tree[root] = r - l + 1;
}
void update(int root, int l, int r, int pos)
{
for (;;)
{
--tree[root];
if (l == r) return;
int mid = (l+r)>>1;
if (pos <= mid) root = root << 1, r = mid;
else root = (root << 1) + 1, l = mid + 1;
}
}
int query(int root, int l, int r, int idx)
{
for (;;)
{
if (l==r){return l;}
int mid = (l+r)>>1, root2 = root << 1;
int l_sum = tree[root2];
if (idx <= l_sum){r = mid; root = root2;}
else {l = mid + 1, root = root2 + 1, idx -= l_sum;}
}
}
int main(void)
{
int n, k;
while (scanf("%d%d", &n, &k) == 2)
{
for (int i = 1; i <= n; ++i) scanf("%s%d", names[i], &number[i]);
int where;
for(where = 0; where < 36 && n >= position[where]; ++where);
int curr = k - 1, abs_pos = k, dest = position[--where];
create(1, 1, n);
for (int i = 0, t = n - 1; i < dest - 1; ++i, --t)
{
if (number[abs_pos] > 0)
curr = (curr - 1 + number[abs_pos]) % t;
else
curr = ((curr + t + number[abs_pos]) % t + t) % t;
update(1, 1, n, abs_pos);
abs_pos = query(1, 1, n, curr+1);
}
printf("%s %d\n", names[abs_pos], value[where]);
}
return 0;
}