2992. 卡片

第一反应就是考双端队列deque，模拟+离线计算即可

include

using namespace std;
int T,n;
int ans[210];
deque D;
void cal(int aa)
{
D.clear();
for(int i=1;i<=aa;i++) D.push_front(i);
while(D.size()>1)
{
D.pop_back();
int xx=D.back();
D.pop_back();
D.push_front(xx);
}
ans[aa]=D.front();
return;
}
void solve()
{
cin>>n;
cout<<ans[n]<>T;
for(int i=5;i<=200;i++) cal(i);
for(int step=0;step<T;step++)
{
printf(“case #%d:\n”,step);
solve();
}
return 0;
}

所谓离线计算，就是先全部算好，存在数组里面，询问的时候直接输出，具体见代码。

简单的数学规律，从5–>2开始，每增加一张牌，则留存的牌是上一个结果加2，如果发现留存结果加2大于目前最大牌的数字，则将留存数字改为2并重新原有规则计数。
、、、

include

int the_card_sum[210];

void init_the_card_sum(){
int flag = 0;
for(int i = 5;i < 250;i++){
flag = flag + 2;
if(i >= flag){
the_card_sum[i] = flag;
}
else if(i < flag){
flag = 2;
the_card_sum[i] = flag;
}
}
}

int main()
{
init_the_card_sum();
int T = 0;
int n = 0;
scanf(“%d”,&T);
getchar();
for(int k = 0;k < T;k++){
scanf(“%d”,&n);
getchar();

    printf("case #%d:\n",k);
    printf("%d\n",the_card_sum[n]);
}
return 0;

}
、、、

其实这道题有时间更优的算法，仔细找找规律就出来了，不知道以后会不会出大数版本

用链表做的

include

include

include

typedef struct card
{
int entry;
struct cardnext;
}Card;
void Delete(Card p1);
void get_down(Card p2);
Card head,last;
int main()
{
int t;
int w=0;
scanf(“%d”,&t);
while(t–>0)
{
int n,i;
scanf(“%d”,&n);
Card p;
head=malloc(sizeof(Card));
if(head!=NULL)
{
p=head;
head->entry=1;
}
else
printf(“Overflow!\n”);
for(i=2;i<=n;i++)
{
Card q;
q=malloc(sizeof(Card));
q->entry=i;
p->next=q;
p=q;
}
last=p;
while(n>1)
{
Cardold=head;
head=head->next;
free(old);
n–;
Card *in=head;
head=head->next;
last->next=in;
last=last->next;
}
printf(“case #%d:\n”,w++);
printf(“%d\n”,last->entry);
free(last);
}
return 0;
}

还是vector用得顺手
int main(int argc, const char * argv[]) {
int cas;
cin>>cas;
for(int i=0;i>n;
printf(“case #%d:\n”,i);
vector v;
for(int j=1;j<=n;j++)
v.push_back(j);
while(v.size()!=1){
v.erase(v.begin());
v.push_back(v.front());
v.erase(v.begin());
}
cout<<v.front()<<endl;
}
return 0;
}