今天是算我第一次正式参加CF的比赛吧，其实在那之前有一次打算认真做来着，结果时间问题，过了午夜，断网了，也没法开热点，就不了了之了，所以并不算参加了吧，今天因为官方把比赛时间提前了，所以很幸运的我不用半夜做比赛了，我对这场比赛期待还是蛮高的。（实现定了目标3题以上吧，因为是Div.2 所以前三题应当是一定要写出来的，然后我对有关图论的算法什么的还没学习，所以只能寄希望少点这种体型，就能争取4题了）
一上来果然A题挺简单的，数据也很小，只有100，我却很为难，到底是直接O（n^2）呢还是写个DP优化呢？拿不定主意，也好了一些时间，结果还是O（n^2）直接上了，经验就是以后遇到这种小数据题，最好写的，思路最清晰的写上去就好了，不需要害怕超时，而去优化了。
这题就不多说了代码如下：
A：
#include<iostream>
#define LL long long
using namespace std;
int a[100][100] = {0};
int main()
{
int i, j, n, max, s, e, count = 0;
int b[100] = {0};
cin >> n;
for (i = 0; i < n; ++i)
cin >> b[i];
for (i = 0; i < n; ++i)
for (j = i; j < n; ++j)
{
if (j == i)
a[i][j] = (b[j] == 1) ? -1 : 1;
else
a[i][j] = a[i][j - 1] + (b[j] == 1 ? -1 : 1);
}
max = a[0][0];
for (i = 0; i < n; ++i)
for (j = i; j < n; ++j)
{
if (max < a[i][j])
{
max = a[i][j];
s = i;
e = j;
}
}
for (i = 0; i < n; ++i)
if (b[i] == 1)
count++;
count += max;
cout << count << endl;
return 0;
}
B题想到简单，想不到可能花一定时间了，一开始我看到是一道构造题，有点阴影感觉高中数学竞赛的构造题都好难，自己很少做出来，看了一下样例给的小数据的构造，也没发现什么规律就有点犹豫不决到底要不要先做这题，毕竟C题分值更高啊，分掉的也快啊，于是我做出了一个很愚蠢的决定，去做C题，后来C题在最不应该的地方卡住了，看看时间还有半个小时不到，额，还是来看看B吧，到这是我才开始自己认真思考一下这题怎么构造。（原本想着能不能从样例里找规律）。
题意就是让构造一个递增序列，是排在前面的数不能被排在它后面的任意一个数整除，例如长度为3时，样例给出了：2 9 15
最开始的思路转向了分析因子，我想这样构造，让前面的数的因子中一定有一个素数因子的指数比后面所有数大，但是这种思路增长太快，很容易超出题目设定的10000000的上届，于是放弃，后来一想如果能让每个数两两互质不就可以了么？最简单的不就是素数序列么？可是前100000位素数序列还是不求算了，又想到（n， n+1） = 1，肯定互质，所以我想到了构造一串连续的数字，很快正确答案出来了：n， n+1， n+2， ，，，，，2*n - 1，这串数字连续，没有一个数是其他数的因子，（可以最大公约数不为1）
因为如果a = k*b,那么k >= 2, 但这里 最大的 2*n - 1 不到最小数n的两倍，所以满足条件。提交AC。
整个过程花了大概6分钟，看来以前的一些思维套路，确实对我做题有影响显得畏首畏尾，不敢大胆去做，其实这题并不难，自己认真思考以后6分钟解决。这是一种信心的增强吧，希望自己牢记，以后也要有这种精神。
B：
#include<iostream>
using namespace std;
int main()
{
int i, n;
cin >> n;
for (i = n; i < 2 * n - 1; ++i)
cout << i << ' ';
cout << 2 * n - 1 << endl;
return 0;
}
其实最想说的，写这篇文章的目的也就是C题，这是一道数论题！！！！！！！！！！！！！
对于一个子串，假设第 i 位上有0 或者5，那么前 i 之前的位上的数字有选与不选2种可能，所以答案为 2 ^ i, 遍历这个子串得到好多 i1， i2， i3，，，，ik，都取 2 的幂求和取模就是子串重复一遍的结果，对于k次重复，很显然，只要多2 ^ ((k - 1) * len)即可，len为子串长度，于是得到一个等比数列，利用求和公式求答案，再取模，好了，关键问题来了，（我想我再也不会忘记的!）等比数列求和公式的表达式是分式，要求 2 ^ len - 1 关于1000000007的逆，怎么求呢？一开始想到了拓展欧几里德，事实是数据大，这种方法会超过数据类型的极限，可是我还是不愿意走其他的路，而去期望数据不会那么变态，于是花了时间写拓展欧几里得的代码，结果当然是浪费时间，于是终于下定决心找其他出路，这样才想到了以前从没用过的来求逆的费马小定理，因为p
= 1000000007是个质数，所以a ^ (p - 1) = 1 (mod p), （其中a 不是p的倍数）， 那么 a * a ^ (p - 2) = 1(mod p)
所以a 的逆不就找到了么？ 这么简单！！！！！！！！！！（看来是太久没有用过了，我清晰记得这个是我在高中很常用的技巧啊！！！）
其他实现大概就是一个快速幂算法，代码如下：
C：
#include<iostream>
#include<cstring>
#define LL long long
using namespace std;
char a[100010] = {0};
LL power(LL a, LL i)
{
LL ans = 1, tem = a;
while (i)
{
if (i & 1)
{
ans *= tem;
ans %= 1000000007;
}
i >>= 1;
tem *= tem;
tem %= 1000000007;
}
return ans;
}
int main()
{
LL i, len, re = 0, k, tem1, tem2;
cin >> a >> k;
len = strlen(a);
for (i = 0; i < len; ++i)
if (a[i] == '0' || a[i] == '5')
re += power(2, i) % 1000000007;
re %= 1000000007;
tem1 = (power(2, len * k) - 1) % 1000000007;
tem2 = power(power(2, len) - 1, 1000000005) % 1000000007;
re *= tem1;
re %= 1000000007;
re *= tem2;
re %= 1000000007;
cout << re << endl;
return 0;
}
（第二天）再去做了一下D题发现也不难，一个DFS，但是很郁闷用cin，cout会超时，很还是用scanf，printf吧；
过程中用了队列保存要执行的操作。
代码如下：
D：
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#pragma warning (disable : 4996)
#define LL long long
using namespace std;
const int N = 502;
char a[N][N];
queue<char> c;
queue<int> x, y;
int st;
void dfs(int i, int j, int de)
{
if (a[i][j] == '#' || a[i][j] == 0)
return ;
else
{
a[i][j] = '#';
st++;
c.push('B');
x.push(i);
y.push(j);
de++;
dfs(i - 1, j, de), dfs(i, j - 1, de), dfs(i + 1, j, de), dfs(i, j + 1, de);
de--;
if (de)
{
st += 2;
c.push('D');
x.push(i);
y.push(j);
c.push('R');
x.push(i);
y.push(j);
}
return ;
}
}
int main()
{
memset(a, 0, sizeof(a));
int n, m, i, j, ch;
cin >> n >> m;
for (i = 1; i <= n; ++i)
scanf("%s", &a[i][1]);
for (i = 1; i <= n; ++i)
for (j = 1; j <= m; ++j)
dfs(i, j, 0);
cout << st << endl;
for (i = 0; i < st; ++i)
{
printf("%c %d %d\n", c.front(), x.front(), y.front());
x.pop(), y.pop(), c.pop();
}
return 0;
}
总结：我知道做比赛的经历太少，也感觉这次心理得到锻炼挺大的，确实会紧张，还有就是要自信，自己能解决！要勇于创新！就是这样了！努力！！！还有就是加快思考过程的速度，写代码的速度，不然两个小时做不完五道题，会做也无济于事！！！！！！
（Ps ： 看过这篇文章的人对于解这些题目有什么更好的技巧，希望都留言告诉我，我会十分感谢的， 其实以前发过一篇用拓展欧几里得求逆的算法代码，当时就觉得不是很快，希望其他人能提供更好的算法，要是有人能点播一下，就应该能马上想到用费马小定理了，大家都能共同进步嘛！谢谢）