2015暑假集训

8.2

早上第一个到学校...

学校把我们的宿舍安排到了西校区..十分钟路程...感人肺腑

下午在SGU看了几道题然后就回宿舍收拾行李了...

晚上颓废然后滚回宿舍了

8.3

早上做了一场比赛, T1写了个贪心结果就70分...T2写完发现理解错题意了...然后就弃疗了, T3没什么思路...

中午被学校告知要搬宿舍...呵呵

下午玩了道提答题..然而我不会玩..玩了好久才玩出几分..然而SA玩出了60+, kpm玩到了满分..跪

晚上STSR #5, CF赛制, 挺好玩的. 2.5h 7道题

T1水题...然而坑点很多. 3min就有人过了pretest..然后我过了pretest锁定后就造了一组数据hunt了10个人..哈哈, 虽说最后还是被人hunt掉了...

T2题意 : 给一个长度n<=20的数字，其中肯定会包括数字1.2.3.4.求调换数字顺序使得原数对7取模为0。(不允许前导0)

这道题我一开始没思路然后就写其他题了, 后来也没时间看..我们先把1.2.3.4提取出来, 把剩下的随意排序(不要前导0), 此时对7取模只有7种情况, 我们只需将1.2.3.4组合接在最后面就行了

T3题意:给 $K$ 组数，每组数有10个数 $a_{1}..a_{10}$ ，求一个最小的 $N$ $(0leqslant a_{10}< N)$ ，使得每组数都满足 $sum_{i=1}^{9}a_{i}equiv a_{10}(mod; N)$ $1leqslant Kleqslant 5$ . $0leqslant a_{i} <2^{28}$
把a_10移到左边就可以发现N是∑a_i - a_10(1<=i<=9)的约数, 这样只要求个gcd就行了.坑点在long long和impossible的输出

T4题意:一个长度N的序列, 最少要删掉多少数满足相邻两个数的绝对值差不为1. 1<=N<=1e5, 0<=a_i<=1e6

O(N²)很好想, 然而是CF赛制, 没有部分分...dp(x, 0~2)表示当前长度为x的序列, 最后一个数的三种情况. 我们发现一个数最多否定相邻数只有2种, 所以我们存三种就没问题了.

8.4

早上STSR#6

T1裸可并堆, 但是我不会QAQ..想写个平衡树+启发式合并..后来就用set水了一下, 然而挂掉了...

T2 离线 + 线段树, T3莫队..都只写了暴力...

下午和SA开始准备晚上的STSR#7(SA回家赛), 一个下午准备6题, 然而都是水题, 这是信心赛. 我出了A, B, E

A题线性筛欧拉函数...

B题水水的01背包, 有点不同稍微处理一下就可以了

C题递推或者dfs+记忆化就可以拿50了...然后加个矩阵快速幂就可以拿满分了

D题线段树...

E题状压dp

F题二分+MST, 二分给LLL御用大道加上的权值, 这样就可以恰好取need条边了

话说我比赛发了邀请邮件, 然后ZSYZ的NOI金牌LJT想让我改比赛时间...让他的学弟都做做...然而只是水题而已

8.5

在准备STSR#8(SA回归赛)...

晚上给他们讲了STSR#7的题目... SA回家了, 就只剩我一个人讲全部题了...

8.6

早上NOIP(PJ组)模拟赛

T1题意:一棵树, 要去掉一些边, 使得k个被标记的点不联通, 且去掉的边权最小.

这道可以直接贪心, 对边进行排序, 从大到小加边, 当前边不会使被标记的点联通就可以加.用并查集维护联通信息.然而我用并查集时写残了..最后发现时已经没有时间改了...然后就只有20了..改了一下就A掉了T T

T2:字符串, 加密什么的...一开始写了暴力, 然后再写了kmp, 然而我不会造数据...结果就没对拍..不过还是A掉了. 后来我发现暴力程序就可以过的...这个数据太弱了吧！正解是字符串hash.

T3题意:把2*n的栅格分成k个连通区域，每个区域至少有一个栅格.1<=n<=1000 ,1<=k<=2*n

感觉是dp, 然而状态表示不出来...最后乱搞一下骗了30分..正解dp(x, h, t)表示考虑了前x列, 分成h个连通块, 第x列的状态为t, t = 0表示第x列上下两块处于不同的连通块, t = 1表示第x列上下两块处于不同连通块.然后就各种讨论来转移..其实还是挺好写的..复杂度O(nk).转移懒得写, 扔代码

----------------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

const int maxk = 2009;

const int MOD = 100000007;

int dp[2][maxk][2], c = 0, p = 1, n, k;

void init() {

scanf("%d%d", &n, &k);

memset(dp[c], 0, sizeof dp[c]);

dp[c][1][1] = 1;

dp[c][2][0] = 1;

}

void work() {

while(--n) {

swap(c, p);

memset(dp[c], 0, sizeof dp[c]);

for(int i = 1; i <= k; i++) {

int &a = dp[c][i][0], &b = dp[c][i][1];

a = ((dp[p][i - 1][0] + dp[p][i - 1][1]) * 2 + dp[p][i][0]) % MOD;

b = (dp[p][i][0] * 2 + dp[p][i][1] + dp[p][i - 1][1] + dp[p][i - 1][0]) % MOD;

if(i > 1)

a = (a + dp[p][i - 2][0] + dp[p][i - 2][1]) % MOD;

}

printf("%d ", (dp[c][k][0] + dp[c][k][1]) % MOD);

}

int main() {

freopen("test.in", "r", stdin);

freopen("test.out", "w", stdout);

init();

work();

return 0;

}

----------------------------------------------------------------------

8.7

早上NOIP模拟赛..

8.8

之前后缀数组弄出模版后没怎么做题, 今天写了两道..

晚上是STSR#8, 我和SA出的比赛...

8.9

回家...