首页 > 其他分享 >[赛记] 暑假集训CSP提高模拟 #N/A 总结

[赛记] 暑假集训CSP提高模拟 #N/A 总结

时间:2024-08-01 15:18:13浏览次数:10  
标签:1.00 赛记 int long 集训 fa continue include CSP

没写的有些多,所以一块写

EVA

原题:忘了;

贪心;

赛时将每条鱼放在了右端点,导致分的情况太多,最后没打完;

贪心的想一下,将每条鱼放在网的左或右端点肯定不会更劣;

将每条鱼作为网的左端点,然后利用相对运动的知识统计出剩下 $ n - 1 $ 条鱼的进入和出去网的范围的时间(可以将出去的时间稍微调慢一些,方便统计在同一时刻出去和进来的鱼),取最大贡献即可;

我写的代码挺长的,主要是分类讨论了一下;

点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, a;
int q[5005], d[5005], h[5005];
struct sas{
	long double f;
	int s, id;
	bool operator <(const sas &A) const {
		return f < A.f;
	}
}t[5005];
int qcnt, dcnt, hcnt;
struct sss{
	long long w, x, v;
	bool operator <(const sss &A) const {
		return x < A.x;
	}
}e[5005];
long long ans;
int main() {
	cin >> n >> a;
	for (int i = 1; i <= n; i++) {
		cin >> e[i].w >> e[i].x >> e[i].v;
	}
	sort(e + 1, e + 1 + n);
	for (int i = 1; i <= n; i++) {
		long long sum = 0;
		memset(t, 0, sizeof(t));
		for (int j = 1; j <= n; j++) {
			int v = e[j].v - e[i].v;
			t[j].s = 1;
			t[j + n].s = 2;
			t[j].id = j;
			t[j + n].id = j;
			if (v < 0) {
				if (e[j].x < e[i].x) {
					t[j].f = -1.00;
					t[j + n].f = -1.00;
					continue;
				}
				if (e[j].x == e[i].x) {
					t[j].f = 0.00;
					t[j + n].f = 0.00000001;
					continue;
				}
				if (e[j].x > e[i].x) {
					if (e[j].x - e[i].x <= a) {
						t[j].f = 0.00;
					} else {
						t[j].f = 1.00 * (e[j].x - e[i].x - a) / (1.00 * (-v));
					}
					t[j + n].f = 1.00 * (e[j].x - e[i].x) / (1.00 * (-v)) + 0.00000001;
				}
			}
			if (v == 0) {
				t[j].f = -1.00;
				t[j].s = 1;
				t[j + n].f = -1.00;
				t[j + n].s = 2;
				if (e[j].x >= e[i].x && e[j].x - e[i].x <= a) sum += e[j].w;
			}
			if (v > 0) {
				if (e[j].x > e[i].x) {
					if (e[j].x - e[i].x > a) {
						t[j].f = -1.00;
						t[j + n].f = -1.00;
						continue;
					}
					if (e[j].x - e[i].x == a) {
						t[j].f = 0.00;
						t[j + n].f = 0.00000001;
						continue;
					}
					if (e[j].x - e[i].x < a) {
						t[j].f = 0.00;
						t[j + n].f = 1.00 * (a + e[i].x - e[j].x) / (1.00 * v) + 0.00000001;
					}
				}
				if (e[j].x == e[i].x) {
					t[j].f = 0.00;
					t[j + n].f = 1.00 * a / (1.00 * v) + 0.00000001;
					continue;
				}
				if (e[j].x < e[i].x) {
					t[j].f = 1.00 * (e[i].x - e[j].x) / (1.00 * v);
					t[j + n].f = 1.00 * (e[i].x - e[j].x + a) / (1.00 * v) + 0.00000001;
				}
			}
		}
		sort(t + 1, t + 1 + 2 * n);
		ans = max(ans, sum);
		int j = 1;
		while(j <= 2 * n) {
			if (t[j].f == -1) {
				j++;
				continue;
			}
			long double o = t[j].f;
			if (t[j].s == 1) sum += e[t[j].id].w;
			if (t[j].s == 2) sum -= e[t[j].id].w;
			j++;
			ans = max(ans, sum);
		}
	}
	cout << ans;
	return 0;
}

黑客

原题:没找;

发现最后的和很小,只有 $ 999 $,所以考虑枚举和为 $ 999 $ 的所有的两个数,则这两个数是由原数除以一个相同的数得来的;

所以去算一下到两个区间左右端点分别需要多少倍,最后用右端点的 $ \min $ 值减去左端点的 $ \max $ 值即可得出以这两个数形成的最简分数一共有多少个了,然后乘一下这两个数的和即可;

注意前提是这两个数互质,因为如果不互质的话就已经被前面互质的数算过了;

细节请看代码;

点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const long long mod = 1e9 + 7;
long long a, b, c, d;
long long ans;
long long w(long long aa, long long i) {
	if (aa % i == 0) return aa / i;
	else return aa / i + 1;
}
int main() {
	cin >> a >> b >> c >> d;
	for (long long i = 1; i <= 999; i++) {
		for (long long j = 1; j <= 999; j++) {
			if (i + j > 999) break;
			if (__gcd(i, j) != 1) continue;
			long long la = w(a, i);
			long long lc = w(c, j);
			long long rb = b / i;
			long long rd = d / j;
			if (rb == 0 || rd == 0) break;
			if (lc > rb) continue;
			if (rd < la) continue;
			long long ml = max(la, lc);
			long long mr = min(rb, rd);
			if (mr - ml < 0) continue;
			ans = (ans + (mr - ml + 1) * (i + j)) % mod;
		}
	}
	cout << ans;
	return 0;
}

密码技术

原题:yuan ti;

很显然,可以发现行列互不影响,所以我们分别算一下然后乘起来即可;

考虑可以互相转化的 $ n $ 组行(列同理),很显然有 $ A^{n}_{n} $ 种方法(全排列);

对于能互相转化,举个例子,考虑 $ 1 $ 和 $ 3 $ 可以互换,$ 1 $ 和 $ 2 $ 可以互换,则 $ 2 $ 和 $ 3 $ 就能互换(因为可以以 $ 1 $ 为中转点);

所以我们可以用并查集维护可以互换的每组行(或者列)的大小与连通性,最后将它们的阶乘乘起来即可;

点击查看代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define int long long
const int mod = 998244353;
int n, kk;
int a[55][55];
bool vis[55];
int fac[55];
int fa[55];
int b[505];
int find(int x) {
	if (fa[x] != x) fa[x] = find(fa[x]);
	return fa[x];
}
main() {
	cin >> n >> kk;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> a[i][j];
		}
	}
	fac[0] = 1;
	for (int i = 1; i <= n; i++) {
		fac[i] = fac[i - 1] * i % mod;
	}
	for (int i = 1; i <= n; i++) fa[i] = i;
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			bool vi = true;
			for (int k = 1; k <= n; k++) {
				if (a[i][k] + a[j][k] > kk) {
					vi = false;
					break;
				}
			}
			if (vi) {
				int ii = find(i);
				int jj = find(j);
				fa[ii] = jj;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		b[find(i)]++;
	}
	for (int i = 1; i <= n; i++) fa[i] = i;
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			bool vi = true;
			for (int k = 1; k <= n; k++) {
				if (a[k][i] + a[k][j] > kk) {
					vi = false;
					break;
				}
			}
			if (vi) {
				int ii = find(i);
				int jj = find(j);
				fa[ii] = jj;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		b[find(i) + n]++;
	}
	long long ans = 1;
	for (int i = 1; i <= 2 * n; i++) {
		if (b[i]) ans = ans * fac[b[i]] % mod;
	}
	cout << ans;
	return 0;
}

小孩召开法 1

原题:$ OT $;

赛时看到 $ n \leq 16 $,想到了状压,但没想到博弈论的一条性质:必败走到必胜,所以没做出来,打的暴搜还不对;

所以状压,考虑下一步如果是必胜,则这一步必败;

终态只有一个字符串,所以必胜;

又是没有签到的一场;

点击查看代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n;
char c[25][15];
int len[25];
struct sss{
	int t, ne;
}e[1005];
int h[1005], cnt;
void add(int u, int v) {
	e[++cnt].t = v;
	e[cnt].ne = h[u];
	h[u] = cnt;
}
int f[18][(1 << 17)];
bool dfs(int x, int now) {
	if (f[x][now]) return f[x][now] == 2 ? 0 : 1;
	for (int i = h[x]; i; i = e[i].ne) {
		int u = e[i].t;
		if ((1 << u) & now) continue;
		if (dfs(u, now | (1 << u))) {
			f[x][now] = 2;
			return 0;
		}
	}
	f[x][now] = 1;
	return 1;
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		scanf("%s", c[i] + 1);
		len[i] = strlen(c[i] + 1);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) continue;
			if (c[i][len[i]] == c[j][1]) {
				add(i, j);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (dfs(i, (1 << i))) {
			cout << "First";
			return 0;
		}
	}
	cout << "Second";
	return 0;
}

标签:1.00,赛记,int,long,集训,fa,continue,include,CSP
From: https://www.cnblogs.com/PeppaEvenPig/p/18336741

相关文章

  • CSP-J2019公交换乘
    马上CSP2024了,做题ing...(题目描述戳它思路1.用结构体双端队列存票,用双端队列的原因是后面要遍历2.结构体元素:price+time+used3.过期的票要及时pop4.不要一边遍历一边pop,用used标记代码#include<bits/stdc++.h>usingnamespacestd;structTicket{intprice......
  • 中山集训 day 1 day 3 模拟赛补题
    Round1A模拟即可。赛场上的写法我自认为写的挺好的。把所有的in替换成outans可以得到的所有串预处理出来,然后和其他原来的串判一下相等即可。Round1B很容易写错的题目。需要意识到\(dp_{\{\}}=x\),如果\(x\)的值更小的话,可以考虑将本来设为dp状态的四元组中的某......
  • 2024暑假集训测试16
    前言比赛链接。真是一次比一次唐了。被莫反害惨了属于是(其实完全是自己唐吧),T1狂推莫反不止,一直想着怎么处理\(999\)的限制,最后推出来了复杂度是\(999\sqrtn\)的,过不去,继续唐我的高级分块套分块做法,比赛快结束了才发现正因为那个限制所以我直接枚举就行了,丫的最后少了......
  • 暑假集训CSP提高模拟12
    T1这题千万不要认为是莫反题枚举质因子\(x,y\),\(x,y<=998\),对答案的贡献为\(min(\lfloor{\frac{B}{x}}\rfloor,\lfloor{\frac{D}{y}}\rfloor)\),再容斥一下即可MD最后答案要取模啊点击查看代码#include<bits/stdc++.h>#definespeed()ios::sync_with_stdio(false),cin.t......
  • 『模拟赛』暑假集训CSP提高模拟12
    Rank正常偏下发挥吧。A.黑客签到题。题目中的关键点是只有\(x\)和\(y\)的和在区间\(\left[0,999\right]\)内才合法,因此我们只枚举和在这个范围内的两个值,寻找约分前的值即可,复杂度为\(\mathcal{O(999^2)}\)。点击查看代码#include<bits/stdc++.h>#definefo(x,......
  • 暑假集训CSP提高模拟12
    暑假集训CSP提高模拟12\(T1\)P171.黑客\(40pts\)将式子进行二维差分。考虑枚举\(\frac{i+j}{\gcd(i,j)}=t\),并统计它能对答案产生的贡献。令\(\gcd(i,j)=1\),这样的话才会不重不漏。推式子,有\(\begin{aligned}&\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\fr......
  • 暑假集训CSP提高模拟 ∫[0,6] (x^2)/6 dx
    \[\text{暑假集训CSP提高模拟}\int^{6}_{0}\frac{x^{2}}{6}dx\]A.黑客显然这个题里只有\(999\)放在复杂度里是有可能对的,要么是\(999^{2}\)要么是\(999^{2}\log999\),显然应该是前者.考虑枚举全部的最简分数,然后乘上去,算的时候直接算当前分母/分子是最简分式的几倍(注意上......
  • 暑假集训csp提高模拟12
    赛时rank47,T1100,T20,T30,T420做题策略不好,没做T2,死在T4上了。感觉赛时就是唐。T1黑客考虑枚举结果,如果存在贡献,那么一定有\(i+j=k\&gcd(i,j)=1\),统计一下有多少组即可点此查看代码#include<bits/stdc++.h>#include<bits/extc++.h>//usingnamespace__gnu_pbds;......
  • CSP模拟10--总结
    今天是我第一次给模拟赛写正规总结--因为今天的题真的受不了了四道数学题,一点都不拖泥带水的纯血数学题!T1、黑暗型高松灯shit本来是一道放在T4防AK的题,结果学长为了恶心锻炼一下我们,直接将T1和T4swap了一下.一开始看了半个小时挺懵逼的,然后跳了,但心里一直觉得这题能做......
  • ssy中学暑假集训分数规划笔记
    分数规划出现在了我们今天的模拟赛中,看在这个名字深得我心而且我能看懂证明和内容的份上,给开个专题吧!\(1.定义\):分数规划就是求分数的极值。形象一点就是,给出\(a_i\)和\(b_i\),求一组\(w_i\in\{0,1\}\)最小化或者最大化下面的算式:\[\frac{\sum_{i=1}^{n}a_i*w_i}{\sum_{i=1}......