首页 > 其他分享 >23.0104 winter training 3

23.0104 winter training 3

时间：2023-01-04 12:23:06浏览次数：68  
标签：training const winter int ll 23.0104 include sum define

B - Editor

题意

给定长度为n的字符串，每个字符代表一个操作，'L','R'分别代表位置左移和右移，其余字符代表修改当前位置为s[i]
输出每次操作后打印出的字符串是否是合法的括号匹配，若是输出最大镶嵌括号层数

思路

我们将'('看作是1，')'看作是-1，其余的是0, 那么一个合法的字符串的括号层数 就是最大的前缀和
因为每次都要进行修改操作 字符串一直在变 容易想到用线段树去维护最大最小前缀和每次去单点修改即可
最后判断整段字符串的和是否为0，以及最小前缀是否为负数，两者满足之一就是不合法的
合法就输出根节点的最大前缀即可

#include <bits/stdc++.h>
#include <stdlib.h>
#include <cstring>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
#define int ll
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 5;
const int M = 5e5 + 5;
const ll mod = 998244353;

int n;
int a[N];

struct node{
	int l, r, sum, mxpre, mipre;
}tree[N<<2];//四倍大小

void push_up(int p)
{
	tree[p].sum = tree[p<<1].sum + tree[p<<1|1].sum;
	tree[p].mxpre = max(tree[p<<1].mxpre, tree[p<<1|1].mxpre + tree[p<<1].sum);
	tree[p].mipre = min(tree[p<<1].mipre, tree[p<<1|1].mipre + tree[p<<1].sum);
}

void build(int l, int r, int p)
{
	tree[p].l = l, tree[p].r = r;
	if(l == r)
	{
		tree[p].mipre = tree[p].mxpre = tree[p].sum = 0;
		return;
	}
	int mid = (l + r)>>1;
	build(l, mid, p << 1);
	build(mid + 1, r, p << 1|1);
	push_up(p);
}

void update(int pos, int val, int p)
{
	int  l = tree[p].l, r = tree[p].r;
	if(l == r)
	{
		tree[p].mipre = tree[p].mxpre = tree[p].sum = val;
		return;
	}
	int mid = (l + r)>>1;
	if(pos <= mid)
		update(pos, val, p<<1);
	else
		update(pos, val, p<<1|1);
	push_up(p);
}

void solve()
{
	cin >> n;
	build(1, n, 1);

	string s;
	cin >> s;
	s= " " + s;

	int pos = 1;
	for(int i = 1; i <= n; i++){
		if(s[i] == 'L') {
			if(pos > 1) pos--;
		}
		else if(s[i] == 'R') pos++;
		else {
			if(s[i] == '(')
				update(pos, 1, 1);
			else if(s[i] == ')')
				update(pos, -1, 1);
			else update(pos, 0, 1);
		}

		if(tree[1].sum != 0 || tree[1].mipre < 0) cout << -1 << " ";
		else cout << tree[1].mxpre << " ";
	}
	cout << "\n";
}


signed main()
{
	IOS;
	int t = 1;

	//cin >> t;
	while (t--)
	{
		solve();
	}
}

D - Packing Potatoes

题意

给定n种重量的土豆（土豆数量无限），每次从前往后拿，拿到最后一种就再回到第一种，如果当前拿的土豆总重量大于等于X就将它们装为一筐
有q次询问 每次一个k 问第k个筐中的土豆的个数

思路

首先考虑到x可能会很大 这样循环暴力的求肯定会超时
如果x超过n种土豆质量和sum时 那就会循环一轮再回到当前位置 所以我们先预处理将\(X%=sum\) 在最后询问的时候多加\(X / sum\)即可
但是这样之后再去模拟也会超时 应该考虑二分右边界
我们求出前缀 每次从当前位置先后找第一个不小于\(pre[now] + x\)的位置 就是这筐的右边界
如果找到最后一个位置也没找到 就说明循环到了前面 那就根据还需要的量按相同方式从一个开始找
然后每次记录一下该区段的左右边界 如果第二次访问到这个区段 就说明循环了 就不用继续求下去了
最后根据k的位置给出相应的答案即可

#include <bits/stdc++.h>
#include <stdlib.h>
#include <cstring>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
#define int ll
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 5;
const int M = 5e5 + 5;
const ll mod = 998244353;

int n, m, k;
int a[N], val[N], pre[N];

void solve()
{
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		pre[i] = pre[i - 1] + a[i];
	}

	int ext = (k / pre[n]) * n;
    k %= pre[n];
	map<pair<int, int>, int>vis;
	int l = 0, s = 0, tot = 0;
	while(1){
		int x = pre[l] + k;
		int st = l + 1;
		if(st > n) st = 1;
		int pos = lower_bound(pre + 1, pre + 1 + n, x) - pre;
		if(pos <= n){
			if(vis[{st, pos}]){
				s = vis[{st, pos}] - 1;
				break;
			}
			vis[{st, pos}] = ++tot;
			val[tot] = pos - l;
			l = pos;
		}
		else {
			int x = pre[n] - pre[l];
			x = k - x;
			pos = lower_bound(pre + 1, pre + 1 + n, x) - pre;
			if(vis[{st, pos}]){
				s = vis[{st, pos}] - 1;
				break;
			}
			vis[{st, pos}] = ++tot;
			val[tot] = pos + n - l;
			l = pos;
		}
	}

	// for(int i = 1; i <= tot; i++)
	//     cerr << val[i] << " \n"[i == tot];
	for(int i = 1, x; i <= m; i++){
		cin >> x;
		//cerr << tot << " " << s << "\n";
		if(x > s){
			x -= s;
			x = (x - 1) % (tot - s) + 1;
			cout << val[s + x] + ext << "\n";
		}
		else cout << val[x] + ext << "\n";
	}
	
}


signed main()
{
	IOS;
	int t = 1;

	//cin >> t;
	while (t--)
	{
		solve();
	}
}

E - List Generation

https://codeforces.com/problemset/problem/1747/E

题意

给定n, m 规定a数组头是0,尾是n,b数组头是0,尾是m, 两数组长度要一样
要求a和b都是非递减的
求所有不同方案的a, b的长度和

思路

我们可以把问题转化为下图：

我们可以枚举图中红色点 i个 \(\tbinom{n}{i} * \tbinom{m}{i}\)
这样我们可以得到一条路径 路径上的剩余点的个数是 \(s = n + m - 1 - i\)
然后我们枚举再选多少个点 j, 那么总贡献就是 \(\sum_{j = 0}^s{\tbinom{s}{j}} * (s + 2 + j)\)
而 \(\sum_{j = 0}^s{\tbinom{s}{j}} = 2^s\) 公式可以转换成 \(2^s * (s + 2) + \sum_{j = 0}^s{\tbinom{s}{j}} * j\)
又因为\(\sum_{j = 0}^s{\tbinom{s}{j}} * j = \sum_{j = 0}^s{\tbinom{s}{j}} * {s - j}\)
那么 \(\sum_{j = 0}^s{\tbinom{s}{j}} * j = (\sum_{j = 0}^s{\tbinom{s}{j}} * s) / 2 = s * 2^{s - 1}\)
结果就是\(\sum_{i = 0}^{\min(n,m)}\tbinom{n}{i} \tbinom{m}{i}(2^s * (s + 2) + s * 2^{s - 1})\)

借鉴于大佬博客：https://www.cnblogs.com/zltzlt-blog/p/16862436.html

#include <bits/stdc++.h>
#include <stdlib.h>
#include <cstring>
#include <deque>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
#define int ll
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 2e3 + 5;
const int M = 5e6 + 5;
const ll mod = 1e9 + 7;

int n, m, fac[M], inv[M], twop[M * 2];
int qpow(int base, int pow){
	int ans = 1;
	while(pow){
		if(pow & 1) ans = ans * base % mod;
		base = base * base % mod;
		pow >>= 1;
	}
	return ans;
}

int C(int x, int y){
	if(y > x) return 0;
	else if(x == y || y == 0) return 1;
	return fac[x] * inv[x - y] % mod * inv[y] % mod;
}

void solve()
{
	cin >> n >> m;
	int ans = 0;
	for(int i = 0; i <= min(n, m); i++){
		int s = n + m - i - 1;
		ans = (ans + C(n, i) * C(m, i) % mod * (s * twop[s - 1] % mod + (i + 2) * twop[s] % mod) % mod) % mod;
	}
	cout << ans << "\n";
}


signed main()
{
	IOS;
	int t = 1;
	fac[0] = inv[0] = 1;
	for(int i = 1; i < M; i++){
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = qpow(fac[i], mod - 2);
	}
	twop[0] = 1;
	for(int i = 1; i < M * 2; i++)
		twop[i] = twop[i - 1] * 2 % mod;

	cin >> t;
	while (t--)
	{
		solve();
	}
}

F - Equidistant Vertices

题意

给定一个n(n <= 100)个点的树，选择k个点满足两两之间的距离一样
求方案数

思路

如果要满足两两距离一样除了 k=2,其他情况肯定是所有k个点到某个点的距离一样且lca为那个点,
因为点数很小 我们可以考虑树形dp
枚举根节点 即那个到k个点距离一样的点 然后dfs一遍,记录每个点为根节点的子树的每个距离的点有几个
dis[i][j] i号节点往深处的与i的距离为j的个数
然后枚举那个相同距离len 对于当前root的每个儿子子树 这样的距离最多只能选一个，如果当前根节点的儿子个数小于k，那么这个根节点没有贡献
\(dp[len][j][k]\)代表相同长度为len 前j个儿子子树中已经选了k个点的方案数
转移方程就是
\(dp[len][j][k] = dp[len][j - 1][k] + dp[len][j - 1][k - 1] * dis[x][len - 1]\)
最后统计一下所有点为根节点的方案数即可

#include <bits/stdc++.h>
#include <stdlib.h>
#include <cstring>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
#define int ll
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 5;
const int M = 5e5 + 5;
const ll mod = 1e9 + 7;

int n, m;
int dis[105][105], ans;
int dp[105][105][105];
vector<int>g[N];

void dfs(int x, int fa){
	dis[x][0] = 1;
	
	for(auto to : g[x]){
		if(to == fa) continue;
		dfs(to, x);
		for(int i = 1; i <= n; i++){
			if(dis[to][i - 1]) 
				dis[x][i] = (dis[x][i] + dis[to][i - 1]) % mod;
		}

	}
}

void solve()
{
	cin >> n >> m;

	for(int i = 1; i <= n; i++) g[i].clear();
	for(int i = 1, u, v; i < n; i++){
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	if(m == 2){
		cout << n * (n - 1) / 2 % mod << "\n";
		return;
	}

	ans = 0;
	for(int i = 1; i <= n; i++){
		int cnt = g[i].size();
		//cerr << "i,cnt" << i << " " << cnt << "\n";
		if(cnt < m) continue;
		for(int k = 1; k <= n; k++)
			for(int j = 1; j <= n; j++)
				dis[k][j] = 0;

		dfs(i, -1);
		memset(dp, 0, sizeof dp);
		for(int len = 1; len <= n; len++) 
			for(int j = 0; j <= cnt; j++)
				dp[len][j][0] = 1;

		for(int len = 1; len <= n; len++){
			for(int j = 1; j <= cnt; j++){
				int x = g[i][j - 1];
				for(int k = 1; k <= min(j, m); k++)
					dp[len][j][k] = (dp[len][j - 1][k] + dp[len][j - 1][k - 1] * dis[x][len - 1] % mod) % mod;
			}
		}

		for(int len = 1; len <= n; len++)
			ans = (ans + dp[len][cnt][m]) % mod;
		
	}
	cout << ans << "\n";
}


signed main()
{
	IOS;
	int t = 1;

	cin >> t;
	while (t--)
	{
		solve();
	}
}

G - Sweets

题意

n 罐糖果。不同的糖果罐，糖果的种类不同，第i个糖果罐里有mi个糖果,求最少吃a个，最多吃b个的方案数

思路

令f(x)为吃x个糖果的方案数 那么答案就是f(b) - f(a - 1)
对于吃b个糖果 就相当于将b个糖果分成n分 代表从每罐糖果中选了几个 这个可以用隔板法计算
一个糖果罐可以吃 0个 而挡板法最少一份是1 所以我们可以总数多加n个糖果 当做每个糖果罐额外多选了一颗
但是可能第i个糖果罐选的糖果超过了mi,那就是不合法的
这部分不合法的要减去 可以用容斥处理

#include <bits/stdc++.h>
#include <stdlib.h>
#include <cstring>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
#define int ll
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 5;
const int M = 5e5 + 5;
const ll mod = 2004;

int n, a, b;
int val[N], modd, fac;

void init(){
	modd = 2004;
	fac = 1;
	for(int i = 1; i <= n; i++) 
		fac *= i;
	modd *= fac;
}

int C(int x, int y){
	if(y > x) return 0;
	if(x == y || y == 0) return 1;
	int ans = 1;
	for(int i = x; i > x - y; i--)
		ans = ans * i % modd;
	return ans / fac;
}

void solve()
{
	cin >> n >> a >> b;

	init();
	for(int i = 0; i < n; i++) 
		cin >> val[i];

	int ans = 0;
	for (int s = 0; s < (1 << n); s++) { // 枚举状态
		int sgn = 1, cnt = 0;
		for (int i = 0; i < n; i++) { 
			if (s >> i & 1) {
				sgn = -sgn;
				cnt += val[i] + 1;
			}
		}
		ans = (ans + sgn * (C(b - cnt + n, n) - C(a - 1 - cnt + n, n)) + mod) % mod;
	}
	cout << ans << "\n";
}


signed main()
{
	IOS;
	int t = 1;

	//cin >> t;
	while (t--)
	{
		solve();
	}
}

标签：training,const,winter,int,ll,23.0104,include,sum,define
From： https://www.cnblogs.com/yaqu-qxyq/p/17024473.html

相关文章

  • 迁移学习（DANN）《Domain-Adversarial Training of Neural Networks》
    论文信息论文标题：Domain-AdversarialTrainingofNeuralNetworks论文作者：YaroslavGanin,EvgeniyaUstinova,HanaAjakan,PascalGermain,HugoLarochelle....论文......
  • 1.2 SMU Winter 2023 蓝桥杯模拟赛 1
    [蓝桥杯2013省B]带分数题意：给n，使满足式子a+b/c=n，其中a，b，c共同恰好由1，2...9组成，求a，b，c的取值种数思路1：枚举出9个数的全排列（可使用next_permutation()），再用两重循环暴......
  • 23.0101 winter training.2
    A-BasicDiplomacy题意某人有n个朋友要出去m天，第i天可以选着\(a_i\)个朋友中的一个一起出去玩，每个朋友被选择的次数不能超过\(\lceilm\rceil\)问是否存在一种方案......
  • HZNU Winter Trainning 8 补题
    CodeForces-1353DConstructingtheArray题目传送门：https://vjudge.net/contest/536385#problem/D题意：给你一个全是0的数组，用1-n的数将这个数组填满，规则是从左至右筛......
  • UNIQUE VISION Programming Contest 2022 Winter(AtCoder Beginner Contest 283)
    A-PowerGivenintegersAandB,printthevalueA^B.基础不解答B-FirstQueryProblem基础不解答C-CashRegisterTakahashiisacashier.Thereis......
  • cs231n学习笔记——lecture6 Training Neural Networks
    该博客主要用于个人学习记录，部分内容参考自：[基础]斯坦福cs231n课程视频笔记(三)训练神经网络、【cs231n笔记】10.神经网络训练技巧(上)、CS231n学习笔记-训练神经网络、......
  • LF Professional及WINTERACTER产品简介
    LF专业版v7.9LFProfessionalv7.8将32/64位Rainier编译器与经典的Lahey/FujitsuLF95编译器相结合！Rainier完全符合Fortran95/90/77标准，并广泛支持Fortran2003......
  • 【JZWinter Camp 2017】欠题小结
    2017.1.12Day1【GDKOI2017模拟】T2[JZOJ4938]序列T3[JZOJ4939]平均数2017.1.13Day2【NOIP2017提高组模拟】T2[JZOJ3824][CFRCC2014warmupDiv.1D]渴2017.1......
  • HZNU Winter Trainning 7 补题 - Zeoy
    CodeForces-1660C题目传送门：https://vjudge.net/contest/535955#problem/C题意：询问一个字符串最少删去几个字符，能够把这个字符串变成aabbccdd这种两两相同的字符串题......
  • 2022 winter training.1
    A-SearchingLocalMinimumhttps://codeforces.com/problemset/problem/1480/C题意交互题有一个1~n的序列最多询问100次问i位置上的数是什么最后要找出一个局部最......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99