如何在蓝桥杯中优雅地骗分（雾）_蓝桥骗分cin

        众所周知，蓝桥杯又称为暴力杯(近几年难度持续加大，快变成dp杯了)。一方面这是因为蓝桥杯采用OI赛制，按照测试点给分，每通过一个测试点就能获得一定的分数，另一方面则是因为蓝桥杯大部分考察的内容很多是思维，dp和搜索。但是dp对新手来说可是一个大坑，无论是从记忆化搜索还是从动态转移方程入手都有一定的难度（可能是我太废了）。因此今天我们来展开说说在蓝桥杯中如何能够合理骗分。

模拟

        尽管模拟算不上什么技巧，但是在这里还是有必要说一下。模拟在蓝桥杯可以说是至关重要的，当一道题拿到手上的时候不清楚如何做的时候，最先想到的就是模拟暴力求解。以约瑟夫问题题为例：

洛谷P1996 约瑟夫问题​​​​​​

题目描述

 n 个人围成一圈，从第一个人开始报数,数到 m 的人出列，再由下一个人重新从 1 开始报数，数到 m 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

输入格式

输入两个整数 n,m。

输出格式

输出一行 n 个整数，按顺序输出每个出圈人的编号。

说明/提示

1≤n,m≤100

        这道题可以说是非常经典的模拟题（虽然也可以用数学方法）。这题我们首先就可以想到使用一个环状链表，一边遍历一边删除，或者使用数组来判断该人是否出圈。模拟的方法有很多，此处使用双端队列进行模拟。附上AC代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n,m,num=1;
	cin>>n>>m;
	deque<int> q; //创建一个双端队列，方便操作队列中的前部和尾部
	for(int i=1;i<=n;i++) q.push_back(i);//将每一个人顺序加入双端队列
	while(!q.empty())//如果圈内还有人，则开始报数
	{
		if(num!=m)
		{
			int tmp=q.front();
			q.pop_front();
			q.push_back(tmp);
			num++;
        //如果没有报数到m，则把第一个人放到最后的位置上。
		}
		else
		{
			cout<<q.front()<<" ";
			q.pop_front();
			num=1;
        //如果报数到m，则把队首的人弹出去，并重新初始化报数。
		}
	}
}

打表

        打表是一种在IOI中比较常见的办法，当常规算法对答案的计算已经会超出时间限制的时候，选择打表可以帮助思考或者避免一些大的数据使程序TLE。这时候可以在大数据上区间自己跑程序，对应输出答案也可以。如果是一堆小数据，也可以使用这种办法。由于打表不好找典型例题，所以以下面为例：

洛谷P1463 [POI2001] [HAOI2007] 反素数

题目描述

对于任何正整数 x，其约数的个数记作 g(x)。例如 g(1)=1，g(6)=4。

如果某个正整数 x 满足：∀0<i<x，都有 g(x)>g(i)，则称 x 为反质数。例如，整数 1,2,4,61,2,4,6 等都是反质数。

现在给定一个数 N，你能求出不超过 N 的最大的反质数么？

输入格式

一个数 N。

输出格式

不超过 N 的最大的反质数。

说明/提示

1≤N≤2×109

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
int main() 
{
	gp_hash_table<int,int> mp;
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int cnt=0;
		for(int j=1;j<=i;i++)
		{
			if(i%j==0) cnt++;
		}
		mp[i]=cnt;
	}
	for(auto& it:mp)
	{
		cout<<it.first<<","<<it.second<<"\n";
	}
		return 0;
}

将所得的结果存进两个数组，然后直接判断即可。

快读快写

        快读快写是一个玄学的东西，有时候使用模板反而会慢几个ms，也许在输入输出非常大的时候才会有区别吧。

template<typename type>
inline void read(type &x)
{
    x=0;bool flag(0);char ch=getchar();
    while(!isdigit(ch)) flag=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    flag?x=-x:0;
}
 
template<typename type>
inline void write(type x,bool mode=1)//0为空格，1为换行
{
    x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);
    do Stack[++top]=x%10,x/=10; while(x);
    while(top) putchar(Stack[top--]|48);
    mode?putchar('\n'):putchar(' ');
}

感谢亲爱的学长给我的模板（真的会有人记住这么长的模板只为了快读快写吗？）

ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);

还是C++关闭同步流更容易记住（关闭同步流后不能再使用scanf、printf）

随机化

       随机化首先想到是自动生成随机数去碰答案（能想到这样的办法可以看出做题者是多么绝望了）。

但随机化其实也是一类算法，如爬山算法和模拟退火。由于笔者还在研究，因此贴上OI wiki的解释爬山算法 - OI Wiki (oi-wiki.org)

模拟退火 - OI Wiki (oi-wiki.org)

总结

        对于蓝桥杯而言，其实最重要的是要细心，因为蓝桥杯中无论你交了多少次，系统只会取比赛结束的最后一次提交进行评测，因此每一次提交都需要认真思考。同时，使用暴力的同时还要思考应该怎么优化时间，很多算法即使通过暴力，但只要进行一定的优化，也是可以AC的，即使不能AC，也可以获得一定的分数。所以不要看到庞大的数据量就不敢使用暴力，暴力也是能出奇迹的！蓝桥杯比赛在即，希望大家能取得自己期望的成绩！！！