2019.11.08考试解题报告

2019.11.08考试解题报告

总结

期望得分：(100+ 40 + 0 = 140)
实际得分：(100 + 40 + 0 = 140)

没有挂分，但是是大众分。。。人均(140)

---

思路&&代码

T1

这题可以用二分答案来做

那么为什么可以用二分答案呢？

答案当然是满足了单调性。假设用(x)天能够杀死所有人，那么用大于$x $天必定也可以杀死所有人，所以满足了单调性，我们就可以二分答案

那么如何(check)呢？考虑一下贪心

贪心思路：在二分的(mid)天之前找到每个敌人暴露弱点的最后一天，只在这一天杀死此敌人，其它时间积攒体力，若在最后一天这个敌人暴露了弱点，而此时积攒的体力并不足以杀死这个敌人，则说明用(mid)天不能杀死所有敌人，否则就让计数器(cnt)的值加一，表示现在已经杀了(cnt)个人，最后检验一下(cnt)是否等于(m)，若不等于则说明还有敌人在(mid)天前没有出现，增大范围，否则缩小范围，让(ans)等于(mid)。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int A = 1e5 + 11;
const int B = 1e6 + 11;

inline int read() {
	char c = getchar(); int x = 0, f = 1;
	for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
	for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
	return x * f;
}

int n, m, all, cnt;
int d[A], w[A], a[A], la[A];

inline bool check(int x) {
	memset(la, 0, sizeof(la));
	for(int i = 1; i <= n; i++) a[i] = d[i];
	for(int i = 1; i <= x; i++) if(a[i]) a[la[a[i]]] = 0, la[a[i]] = i; 
	int tl = 0, cnt = 0;
	for(int i = 1; i <= x; i++) {
		if(a[i]) { tl -= w[a[i]]; if(tl < 0) return 0; else cnt++; }
		else tl++;
	}
	return cnt == m; 
}

int main() {
	freopen("generals.in", "r", stdin);
	freopen("generals.out", "w", stdout);
	n = read(), m = read();
	if(n < m) return puts("-1"), 0;
	for(int i = 1; i <= n; i++) d[i] = read();
	for(int i = 1; i <= m; i++) w[i] = read(), all += w[i];
	if(all > n) return puts("-1"), 0;
	int l = 0, r = n, ans = -1;
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(check(mid)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	return cout << ans << '
', 0;
}

*/

T2

(20)分：

暴搜，只能从左往右搜，所以记录一下上次用的是哪一个，这次枚举直接从上次用的下一个开始枚举，保证从左往右

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

const int A = 1e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;

inline int read() {
	char c = getchar();
	int x = 0, f = 1;
	for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
	for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
	return x * f;
}

int n, m, ans, vis[A], a[A];
char s[A];
int c[4000][4000];

void dfs(int cnt, int last) {
	if(cnt > n + 1) return;
	if((cnt - 1) % 2 == 0 && cnt - 1 != 0) {
		int now = cnt - 1;
		int zuo = 0, you = 0, cao = 0;
		for(int i = 1; i <= now / 2; i++) {
			if(a[i] == 2) {
				cao = 1;
				break;
			}
			if(a[i] == 1) zuo++;
		}
		for(int i = now / 2 + 1; i <= now; i++) {
			if(a[i] == 1) {
				cao = 1;
				break;
			}
			if(a[i] == 2) you++;
		}
		if(!cao && zuo == you && zuo + you == now) ans++;
	}
	for(int i = last + 1; i <= n; i++) {
		if(!vis[i]) {
			vis[i] = 1;
			a[cnt] = (s[i] == '(' ? 1: 2);
			dfs(cnt + 1, i);
			vis[i] = 0;
		}
	}
}

signed main() {
	freopen("beauty.in", "r", stdin);
	freopen("beauty.out", "w", stdout);
	scanf("%s", s + 1);
	n = strlen(s + 1);
	if(n <= 20) {
		dfs(1, 0);
		cout << ans % mod << '
';
		return 0;
	}
	return 0;
}

(50)分：

考虑每个左括号，不包括他的，左边有多少个左括号，右边有多少个右括号，就可以得出，对于每一个左括号的位置，都有：（(x)是指左边不包括这个左括号有多少个左括号，(y)是右边有多少个右括号）

[sum_{i = 0}^{x} C(x, i) * C(y, i + 1) ]

然后就有(50)了

(100)分：

考虑直接换一种想法，我们枚举包括这个位置的左括号的，左边有多少个左括号，右边有多少个右括号，这个位置必须选，那么就能得出

[sum_{i = 1}^{x} C(x, i) * C(y, i) ]

但是这样就会把不选这个位置的情况算上，所以还要减去

[sum_{i = 1}^{x} C(x - 1, i) * C(y, i) ]

就得出了

[sum_{i = 1}^{x} C(x, i) * C(y, i) - sum_{i = 1}^{x} C(x - 1, i) * C(y, i) ]

有一个辅助式子

[sum_{i = 0}^{x} C(x, i) * C(y, i) = C(x + y, x) ]

所以上面的式子就能写成

[(C(x + y, x) - 1 )- ( C(x + y - 1, x - 1) - 1) ]

就等于

[C(x + y, x) - C(x + y - 1, x - 1) ]

对于每个左括号的位置，我们都这样计算一遍，然后就做完了

时间复杂度(O(n))

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

const int A = 5e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;

inline int read() {
	char c = getchar(); int x = 0, f = 1;
	for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
	for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
	return x * f;
}

int n, m, a[A], b[A], fac[A], inv[A], ans; //a[i]左边的左括号个数，b[i]右边的右括号个数 
char s[A];

int power(int a, int b, int res = 1) {
	while(b) {
		if(b & 1) res = res * a % mod;
		a = a * a % mod; b >>= 1;
	} return res;
} 

void prepare(int n) {
	fac[0] = 1;
	for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
	inv[n] = power(fac[n], mod - 2);
	for(int i = n - 1; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % mod; 
	return;
}

int C(int n, int m) {
	if(n < m) return 0;
	return fac[n] % mod * inv[n - m] % mod * inv[m] % mod;
}

signed main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	prepare(n * 2);
	for(int i = n; i >= 1; i--)
		if(s[i] == ')') b[i] = b[i + 1] + 1;
		else b[i] = b[i + 1];
	for(int i = 1; i <= n; i++) {
		if(s[i] == '(') a[i] = a[i - 1] + 1;
		else a[i] = a[i - 1]; 
	}
	for(int i = 1; i <= n; i++) {
		if(s[i] == ')') continue;
		int x = a[i], y = b[i];
		ans += C(x + y, x) - C(x + y - 1, x - 1) , ans %= mod;
	}
	ans = (ans % mod + mod) % mod;
	cout << ans << '
';
	return 0;
}

T3

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
//var
int n,m;
//Trie
struct Tree {
	int ch[26];
	int fail;
} T[400010];
int tot;
int pos[400010];//index->node
void insert(char* st,int num) {
	int now=0,len=strlen(st);
	for(int i=0; i<len; i++) {
		if(!T[now].ch[st[i]-'a'])
			T[now].ch[st[i]-'a']=++tot;
		now=T[now].ch[st[i]-'a'];
	}
	pos[num]=now;
	return ;
}
//fail-tree
vector<int>son[400010];
//AC Automaton
queue<int>q;
void bfs() {
	for(int i=0; i<26; i++)
		if(T[0].ch[i]) {
			q.push(T[0].ch[i]);
			T[T[0].ch[i]].fail=0;
		}
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		son[T[u].fail].push_back(u);
		for(int i=0; i<26; i++)
			if(T[u].ch[i]) {
				T[T[u].ch[i]].fail=T[T[u].fail].ch[i];
				q.push(T[u].ch[i]);
			} else T[u].ch[i]=T[T[u].fail].ch[i];
	}
	return ;
}
//get dfn
int dfn[400010],to[400010],now;
//vector<char>Vec;
void dfs(int u) {
	dfn[u]=++now;
	for(int i=0; i<son[u].size(); i++)
		dfs(son[u][i]);
	to[u]=now;
	return ;
}
/*
//for debug
void _dfs(int u)
{
	printf("%d: str=",u);
	for(int i=0;i<Vec.size();i++)
		printf("%c",Vec[i]);
	printf("
");
	for(int i=0;i<26;i++)
		if(T[u].ch[i]){
			Vec.push_back(i+'a');
			_dfs(T[u].ch[i]);
			Vec.pop_back();
		}
	return ;
}*/
//Fenwick
int c[400010];
int lowbit(int x) {
	return x&(-x);
}
void add(int x,int y) {
	for(; x<=tot+1; x+=lowbit(x))
		c[x]+=y;
	return ;
}
int query(int x) {
	int ans=0;
	for(; x; x-=lowbit(x))
		ans+=c[x];
	return ans;
}
//Song-Tree
vector<pair<int,char> >S[400010];
//queries
vector<int>qnum[400010];
//answers
int ans[400010];
//REAL-DFS
void DFS(int u,int state) {
	add(dfn[state],1);
	for(int i=0; i<qnum[u].size(); i++) {
		int v=qnum[u][i];
		ans[v]=query(to[pos[v]])-query(dfn[pos[v]]-1);
	}
	for(int i=0; i<S[u].size(); i++) {
		int v=S[u][i].first;
		int C=S[u][i].second-'a';
		DFS(v,T[state].ch[C]);
	}
	add(dfn[state],-1);
	return ;
}
char str[400010];
int main() {
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	scanf("%d",&n);
	for(int i=1; i<=n; i++) {
		int op,fa;
		scanf("%d",&op);
		if(op==1)fa=0;
		else scanf("%d",&fa);
		scanf("%s",str);
		S[fa].push_back(make_pair(i,str[0]));
	}
	scanf("%d",&m);
	for(int i=1; i<=m; i++) {
		int u;
		scanf("%d",&u);
		scanf("%s",str);
		insert(str,i);
		qnum[u].push_back(i);
	}
//	_dfs(0);
	bfs();
	dfs(0);
	DFS(0,0);
//	for(int i=1;i<=tot;i++)
//		printf("fail[%d]=%d
",i,T[i].fail);
	for(int i=1; i<=m; i++)
		printf("%d
",ans[i]);
//	for(int i=1;i<=m;i++)
//		printf("%d ",pos[i]);
//	printf("
");
	return 0;
}