2020提高组十连测day1

首先答案小于等于8给出了....

证明其实就考虑 $3n^2-3n+1$

就是 $6\binom{n}{2} + 1$ 这样的数

然后我们减0~5至少能出一个6的倍数,然后用 $\binom{n}{2}$ 可以至多三个数凑齐

所以答案至多是8(必要性显然当是13的时候一定8个数)

然后显然 $3n^2-3n+1%6==1$

所以ans=n%6

所以就是要看是1还是7是2还是8

1显然可以哈希表

2显然可以枚举一个然后另一个双指针

code:


#include<bits/stdc++.h>
#define ll long long

#define min(x,y) (x<y?x:y)
using namespace std;
const int MAXB = 320000;
int T, ans, res;
ll a[MAXB + 7], b[MAXB + 7];
int dp[MAXB + 7];
// unordered_map<ll, int> mp;

const int P = 19260817;
int home[P], nxt[P], ccnt;
ll to[P];
inline void ct(int x, ll y) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
}

inline int query(ll x) {
	int u = x % P;
	if(!home[u])return 0;
	for(int i = home[u]; i; i = nxt[i]) {
		ll v = to[i];
		if(v == x)return 1;
	}
	return 0;
}
inline void add(ll x) {
	int u = x % P;
	if(!home[u]) {
		ct(u, x);
		return ;
	}
	// puts("YES!");
	for(int i = home[u]; i; i = nxt[i]) {
		ll v = to[i];
		if(v == x)
			return ;
	}
	ct(u, x);
}


inline void init() {
	for(ll i = 1; i <= MAXB; ++i) {
		a[i] = a[i - 1] + i;
	}
	add(0);
	for(ll i = 1; i <= MAXB; ++i) {
		b[i] = 3 * i * i - 3 * i + 1;
		add(b[i]);
	}
	// printf("%lld?\n", a[MAXB]);
	// memset(dp, 0x3f3f3f3f, sizeof(dp));
	// dp[0] = 0;
	// for(int i = 1; i <= MAXB; ++i) {
	// 	for(int j = 1; a[j] <= i; ++j) {
	// 		// if(i == MAXB)printf("%d %d %d\n", i, i - a[j], dp[i - a[j]] + 1);
	// 		dp[i] = min(dp[i - a[j]] + 1, dp[i]);
	// 	}
	// 	// if(i == MAXB)printf("%d?\n", dp[i]);
	// }
	return ;
}

inline void solve1(ll y) {
	if(query(y))
		ans = min(1, ans);
}

inline void solve2(ll y) {
	int R = lower_bound(a + 1, a + MAXB + 1, y) - a;
	int L = 0;
	for(int i = R; i >= 0; --i) {
		// printf("????%d?%d\n", a[i], i);
		if(i < L)break;
		while(a[L + 1] <= y - a[i] && L < R)
			++L;
		// printf("%d %d %d\n", L, R, i);
		if(y == a[L] + a[i]) {
			// printf("%d %d %d\n", y, a[L], a[i]);
			ans = min(2, ans);
			break;
		}
	}
	ans = min(8, ans);
	return ;
}

//艹,乱搞
inline void solve(ll x) {
	if(x == 0)return (void)puts("0");
	ans = 1000;
	solve1(x);
	if(x % 6 == 1)ans = min(ans, 7);
	if(x % 6 == 2)solve2((x - 2) / 6);
	if((x % 6 != 2)  && (x % 6 != 1))
		ans = min(ans, ((x % 6) == 0 ? (6) : (x % 6)));
	printf("%d\n", ans);
	return;
}

int main() {
	// freopen("test.in", "r", stdin);
	// freopen("test.out", "w", stdout);

	scanf("%d", &T);
	init();
	for(ll i = 1, x; i <= T; ++i) {
		scanf("%lld", &x);
		solve(x);
	}
	return 0;
}

推推式子就变成二维数点了

然后主席树只能nlogn

离线+树状数组即可

code:


#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define mkp(x,y) (make_pair(x,y))
#define ll long long
const int MAXN = 4e6 + 7;
char s[MAXN];
int n, ans, tot;
int p[MAXN];
int tr[MAXN];
struct rec {
	int x, y, z;
	rec(int x = 0, int y = 0, int z = 0): x(x), y(y), z(z) {};
	bool operator<(const rec &P)const {
		return x == P.x ? z < P.z : x < P.x;
	}
} que[MAXN];

inline void read() {
	s[0] = '$';
	s[1] = '|';
	n = 1;
	char c = 0;
	for(; !isalpha(c); c = getchar());
	for(; isalpha(c); c = getchar()) {
		s[++n] = c;
		s[++n] = '|';
	}
	return ;
}

inline void add(int x, int y) {
	for(; x <= n; x += lowbit(x))tr[x] += y;
}

inline int query(int x) {
	int ret = 0;
	for(; x; x -= lowbit(x))ret += tr[x];
	return ret;
}

int main() {
	// freopen("test.in", "r", stdin);
	// freopen("test.out", "w", stdout);
	read();
	for(int i = 1, r = 0, mid = 0; i <= n; i++) {
		if(i <= r)
			p[i] = min(p[(mid << 1) - i], r - i + 1);
		while(s[p[i] + i] == s[i - p[i]])p[i]++; //p[i]biaoshichangdu!
		if(p[i] + i > r)r = p[i] + i - 1, mid = i;
	}
	for(int i = 1; i <= n; ++i) {
		// printf("pos is :%d R is :%d %d %c\n", i, p[i], i - p[i] + 1, s[i]);
		if(s[i] == '|') {
			que[++tot] = rec(i - p[i] + 1, i, -1);
		}
	}
	ll ans = 0;
	for(int i = 1; i < n; ++i) {
		if(s[i] == '|') {
			// printf("%d %d %d\n", i, i + p[i] - 1, n);
			que[++tot] = rec(i, i, min(i + p[i] - 1, n));
			// ans = ans + 1ll * query(root[i], root[min(i + p[i] - 1, n)], 1, n, 1, i);
			// printf("%lld?\n", ans);
		}
	}
	sort(que + 1, que + tot + 1);
	for(int i = 1; i <= tot; ++i) {
		// printf("%d %d %d\n", que[i].x, que[i].y, que[i].z);
		if(que[i].z == -1) {
			add(que[i].y, 1);
		} else {
			// printf("%d %d??\n", que[i].z, que[i].y);
			ans = ans + query(que[i].z) - query(que[i].y);
			// printf("%lld\n", ans);

		}
	}
	printf("%lld\n", ans);
	return 0;
}

对于一个随机的树我们树高是根号的

然后我们考虑nh算法

可以首先dp出一条链中一个数的贡献

会发现一个数有贡献次数当且仅当他要在前面某个数删除

而且会发现这个和一个序列上前面某个数要比他小(删除的早)是一样的

然后这个东西就能dp了

$dp_{i}$ 表示位置一对于 $a_i$ 的贡献次数

转移时枚举之前某个位置,然后发现不知道怎么算中间转移系数

再想想都是统计一个开头为1的上升子序列数量的问题

先考虑里面数的取值,然后再考虑里面数的位置,位置和取值都有就有顺序了,再考虑其他数的排序

code:


#include<bits/stdc++.h>
#define ll long long
const int MAXM = 3e5 + 7;
const int MAXH = 1000;
const int MAXN = 2e5 + 7;
using namespace std;
const int P = 1e9 + 7;
int n, ccnt, home[MAXN], nxt[MAXM], to[MAXM];
ll a[MAXN], ans, val[MAXN], f[MAXN], fac[MAXN], ifac[MAXN];
int c[MAXH + 7][MAXH + 7], fa[MAXN];

inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
	return ;
}

inline ll ksm(ll x, ll y) {
	ll ans = 1;
	while(y) {
		if(y & 1)
			ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}

inline void init() {
	c[0][0] = 1;
	for(int i = 1; i < MAXH; ++i) {
		for(int j = 1; j <= i; ++j) {
			c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % P;
		}
	}
	// printf("????%d %d\n", c[2][2], c[5][3]);
	fac[0] = 1;
	for(int i = 1; i < MAXN; ++i) {
		fac[i] = fac[i - 1] * i % P;
	}
	ifac[MAXN - 1] = ksm(fac[MAXN - 1], P - 2);
	for(int i = MAXN - 2; i; --i) {
		ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
	}
	ifac[1] = 1;
	ifac[0] = 1;
	// printf("%lld %lld\n", fac[3], 1ll * fac[3]*ifac[3] % P);
	return ;
}

inline void dfs(int u, int F, int dep) {
	fa[u] = F;
	// printf("%d %d %d %d\n", u, F, dep, fa[u]);
	for(int y = u, t = 1; y; y = fa[y], ++t) {
		// printf("%d %d %lld\n", y, t, f[t]);
		(ans += f[t] * a[y]) %= P;
	}
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		// printf("%d %d\n", v, u);
		dfs(v, u, dep + 1);

	}
}

int main() {
	scanf("%d", &n);
	for(int i = 1, x, y; i < n; ++i) {
		scanf("%d%d", &x, &y);
		ct(x, y);
		ct(y, x);
	}
	init();
	val[1] = 2;
	for(int i = 2; i < MAXH; ++i) {
		for(int j = 1; j <= i; ++j) {
			val[i] += 1ll * c[i][j] * c[i - 1][j - 1] % P * fac[i - j] % P;
			val[i] %= P;
		}
	}
	f[1] = 2;
	for(int i = 3; i <= MAXH; ++i) {
		// printf("%d %lld %lld??\n", i, val[i], ifac[i]);
		f[i - 1] = 1ll * val[i] * ifac[i - 1] % P;
		// assert(f[i - 1] != 3);
		// printf("%lld %lld\n", i, f[i]);
	}
	for(int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
		a[i] %= P;
	}
	// puts("qwq");
	dfs(1, 0, 1);
	(ans += P) %= P;
	// printf("%lld?\n", ans);
	printf("%lld\n", 1ll * ans * fac[n] % P);
	return 0;
}

夏晓光(loveJY)的博客

P3694 邦邦的大合唱站队