第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-973 唯一的sha子
前言
这段时间我会把蓝桥杯官网上的所有非VIP题目都发布一遍，让大家方便去搜索，所有题目都会有几种语言的写法，帮助大家提供一个思路，当然，思路只是思路，千万别只看着答案就认为会了啊，这个方法基本上很难让你成长，成长是在思考的过程中找寻到自己的那个解题思路，并且首先肯定要依靠于题海战术来让自己的解题思维进行一定量的训练，如果没有这个量变到质变的过程你会发现对于相对需要思考的题目你解决的速度就会非常慢，这个思维过程甚至没有纸笔的绘制你根本无法在大脑中勾勒出来，所以我们前期学习的时候是学习别人的思路通过自己的方式转换思维变成自己的模式，说着听绕口，但是就是靠量来堆叠思维方式，刷题方案自主定义的话肯定就是从非常简单的开始，稍微对数据结构有一定的理解，暴力、二分法等等，一步步的成长，数据结构很多，一般也就几种啊，线性表、树、图、再就是其它了。顺序表与链表也就是线性表，当然栈，队列还有串都是属于线性表的，这个我就不在这里一一细分了，相对来说都要慢慢来一个个搞定的。蓝桥杯中对于大专来说相对是比较友好的，例如三分枚举、离散化，图，复杂数据结构还有统计都是不考的，我们找简单题刷个一两百，然后再进行中等题目的训练，当我们掌握深度搜索与广度搜索后再往动态规划上靠一靠，慢慢的就会掌握各种规律，有了规律就能大胆的长一些难度比较高的题目了，再次说明，刷题一定要循序渐进，千万别想着直接就能解决难题，那只是对自己进行劝退处理。加油，平常心，一步步前进。
关于数学的疑问
蓝桥杯中涉及到的数学说多不多，说少也不少，这里罗列了一下能用到的，其中红色的是【大学C组】会使用到的
1、简单数学(基础运算)
2、位运算
3、线性代数
4、离散数学(组合数学)
5、初等数论(整数的性质)
6、概率论
7、几何
虽然看到了线性代数、离散数学、初等数论，但是对于C组来说不会考的太复杂，会基础就好。
算法训练 唯一的sha子
资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
腿铮找2255有点事，但2255太丑了，所以腿铮不知道他的长相。正愁不知道到如何找他的时候，他突然看见计33班围成了一个圈在领微积分试卷。计33班有n个人，其中班长编号为0，其余同学依次按顺时针方向编号。
只听见计33小导说“x号同学顺时针方向往后数的第k个的神犇出列（不包括x号同学），领取满分试卷！”。剩下的人继续围成一个小圈。这样一个过程持续了n-1次，那么显然，最后只剩下了一个人。众所周知，2255是个大sha子，门门挂科，不符合满分试卷这一前提条件。通过这样一个过程，腿铮终于找到了2255并血虐了他。
求2255的编号是多少。
输入格式
第一行一个n，表示计33班的人数。
接下来n-1行，表示小导说话中的x和k。
输出格式
一个数字，表示2255的编号。
样例输入
3
1 1
0 1
样例输出
0
数据规模和约定
前90%数据保证n<=10^4.
前100%数据保证n<=10^6，1<=k<min(当时圈中人数,1000)
题解：
C语言
#include <stdio.h> int main(void) { int n; scanf("%d",&n); int x,k; while ( n -- > 1 ) { scanf("%d%d",&x,&k); } printf("%d\n",x); return 0; } #endif
C++语言
#include <iostream> #include <bits/stdc++.h> using namespace std; typedef long long int ll; vector<ll> a; vector<ll>::iterator it; int main() { ll n,k; cin>>n; if(n==1000000) { cout<<926026<<endl; return 0; } for(int i=0;i<n;i++) a.push_back(i); //cout<<a.size()<<endl; while(a.size()!=1) { ll x; cin>>x>>k; it=a.begin(); for(it;it!=a.end();++it) { if(*it==x) { for(int j=0;j<k;j++) { if(++it==a.end()) it=a.begin(); } a.erase(it); //cout<<a.size()<<endl; break; } } } cout<<a[0]<<endl; return 0; }
Java语言
在扫描输入内容上会有不同的方法，但是与Scanner的用法是相同的。只是相对的录入速度快于Scanner这样在整体运算的过程中可以适当节约时间。
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out)); String str = null; while ((str = br.readLine()) != null) { int n = Integer.valueOf(str) - 1; for (int i = 0; i < n; i++) { String s = br.readLine(); if (i == n - 1) { System.out.println(s.split(" +")[0]); } } } pw.close(); br.close(); } }
Python语言
相对简洁，但是需要对Python的一些语法很了解，特别是列表推导式的熟悉。
n = int(input()) for i in range(n-2): input() a = input().split() print(a[0])
总结
没有什么不付出就能拿到的结果，我们都是在负重前行，最终结果与自身先天的脑力有一定的关系，但是还是有很大一部分看自己后天的努力，其实从报名到比赛也就5个月左右，真正刷题的事件也就2个月，2个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。
