【酱油记】NOIP 2016

序言

又是一年NOIP
又是一次伤心离别时

3126387
每每看到这两张照片便感慨万分
时光荏苒,人终散尽

正文

D0

爸爸我要AK!

D1

先看了看T1,嗯还好,可以做
水完T1去水T2,卧槽∑( 口 || 怎么突然不会做了!
不会今年NOIP就这么挂了吧 QwQ
然后赶紧码了一个大暴力,然后去水T3
写完T3的程序后对拍,怎么一上来就wa (╯‵□′)╯︵┻━┻
到底是我暴力写挫了还是标准程序错了 (・∀・(・∀・(・∀・*)
好像数据不好手玩的样子,遂调试了一个小时……..
这时还剩30min结束,跑回去看T2
推了推式子,发现可做的样子!搞一个DFS序加函数式线段树就好
然而还剩20min了,最终没有写出来

D2

先看看T1,嗯可做的样子,于是就写了
又去看T2,又™不会做了……..
于是先写了一个堆放着,然后去看T3,发现T3一脸可做的样子
于是就做了T3。但一直到考试结束都没有想出T2

成绩

本来可以上500来着,结果D1T2的暴力掉了20分,D2T3被卡常了5分
于是遗憾485,全省18的样子
虽然不尽人意,但想起考前浪的日子,算是自食其果吧!

尾声

其实这次考试的成绩勉强还能看吧!
但不知道小伙伴们有没有退役的……
经过苦口婆心的劝说后,似乎有还是有同学摇摆不定
只要这次NOIP之后小伙伴们都还安好,那便是晴天!

【Codevs 4560】[NOIP2015] 子串

题目传送门:http://codevs.cn/problem/4560/

就是一个很简单的DP加一个滚动数组的优化
然而为什么纸张的我去年连这是个DP都看不出来 QAQ

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1000000007; 

int f[2][209][209][2],w,p,n,m,K;
char s1[1009],s2[1009];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main(){
	n = read(); m = read(); K = read();
	scanf("%s%s",s1+1,s2+1);
	w = 1; f[p][0][0][0] = 1;
	
	for (int t=1;t<=n;t++,w^=1,p^=1) {
		memset(f[w],0,sizeof(f[w]));
		for (int i=0;i<=m;i++) {
			for (int k=0;k<=K;k++) {
				if (f[p][i][k][0]) {
					(f[w][i][k][0] += f[p][i][k][0]) %= MOD;
					if (s1[t] == s2[i+1]) {
						(f[w][i+1][k+1][1] += f[p][i][k][0]) %= MOD;
					}
				}
				if (f[p][i][k][1]) {
					(f[w][i][k][0] += f[p][i][k][1]) %= MOD;
					if (s1[t] == s2[i+1]) {
						(f[w][i+1][k][1] += f[p][i][k][1]) %= MOD;
						(f[w][i+1][k+1][1] += f[p][i][k][1]) %= MOD;
					}
				}
			}
		}
	}
	printf("%d\n",(f[p][m][K][0]+f[p][m][K][1])%MOD);
	return 0;
}