首页 > 其他分享 >2022 CCPC 女生赛 补题 ACEGHI

2022 CCPC 女生赛 补题 ACEGHI

时间:2023-10-18 21:35:23浏览次数:42  
标签:ll idx int tt d% CCPC 补题 id ACEGHI

2022 女生赛 补题 ACEGHI

https://codeforces.com/gym/104081
属于是考前抱佛脚了,希望能有个好成绩球球了
一些写过的题题解在此:如何评价2022CCPC女生赛? - 知乎用户的回答 - 知乎

A. 减肥计划

模拟直到最大的那个人到前面
(最开始用queue模拟的,样例居然过了)WA了之后直接改成变量记录队头和第二个人

#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 5;
int n, k, mx, mxid;

struct Node {
	int v, id, cnt;
}p[N];

int main () {
	scanf ("%d%d", &n, &k);
	deque<Node> q;
	for (int i = 1; i <= n; i++) {
		scanf ("%d", &p[i].v), p[i].id = i, p[i].cnt = 0;
		if (p[i].v > mx)	mx = p[i].v, mxid = i;
		q.push_front (p[i]);
	}
	//moni
	auto t = p[1], tt = p[2];
	int idx = 2;
	while (idx < mxid) {
		if (t.v >= tt.v) {
			t.cnt++;
			if (t.cnt >= k) {
				printf ("%d", t.id);
				return 0;
			}
		}
		else {
			tt.cnt++;
			if (t.cnt >= k) {
				printf ("%d", tt.id);
				return 0;
			}
			t = tt;
		}
		idx++, tt = p[idx];
	}
	printf ("%d", mxid);
}

C. 测量学

去年因为我WA了一发,至今仍印象深刻。

#include <bits/stdc++.h>
#define pi acos (-1)

using namespace std;
const int N = 1e5 + 5;
int n;
double R, theta, r[N];

int main () {
	cin >> n >> R >> theta;
	theta = min (theta, 2 * pi - theta);
	double ans = theta * R;
	for (int i = 1; i <= n; i++) {
		ans = min (ans, 2 * (R - r[i]) + theta * r[i]);
	}
	cout << fixed << setprecision(5) << ans;
}

E. 睡觉

注意无限长的情况

#include <bits/stdc++.h>
#define pi acos (-1)

using namespace std;
const int N = 1e5 + 5;
int n, x, t, k, d, a[N];

void solve () {
	scanf ("%d%d%d%d%d", &x, &t, &k, &n, &d);
	//cin >> x >> t >> k >> n >> d;
	int dx = 0;
	for (int i = 1; i <= n; i++) {
		scanf ("%d", &a[i]);
		if (a[i] <= d)	dx--;
		else	dx++;
	}
	if (dx < 0) {
		printf ("YES\n");
		return ;
	}
	//内部
	int wei = 0, xx = x;
	for (int i = 1; i <= n; i++) {
		if (a[i] <= d)	x--;
		else	x++;
		if (x <= k)	wei++;
		else	wei = 0;
		if (wei >= t) {
			printf ("YES\n");
			return ;
		}
	}
	//开头len
	int tou = 0;
	x = xx;
	for (int i = 1; i <= n; i++) {
		if (a[i] <= d)	x--;
		else	x++;
		if (x <= k)	tou++;
		else	break;
	}
	if (tou + wei >= n) {
		printf ("YES\n");
		return ;
	}
	if (tou + wei >= t)	printf ("YES\n");
	else	printf ("NO\n");
}

int main () {
	int t;
	scanf ("%d", &t);
	while (t--)	solve ();
}

G. 排队打卡

这小小的模拟题竟WA了两发,说明读题能力不行(X
坑点:

  • 给定的日志不一定按照时间顺序排列
  • 注意每秒的开始先进来人,这一秒结束之后再放人走,所以在出队的时候要注意带上一个 \(-1\)
    然后就是萌萌模拟了:
#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 5e5 + 5;
ll t, n, m, k, sum;

struct Node {
	ll a, b;
	bool operator<(const Node &t) const {
		return a < t.a;
	}
}p[N];

int main () {
	scanf ("%lld%lld%lld%lld", &t, &n, &m, &k);
	for (int i = 1; i <= m; i++)	scanf ("%lld%lld", &p[i].a, &p[i].b);
	p[++m] = {t, 0};
	sort (p + 1, p + m + 1);
	ll ans = 2e18, ansid = 0;
	for (int i = 1; i <= m; i++) {
		sum = max (0ll, sum - k * (p[i].a - p[i-1].a - 1)), sum += p[i].b;
		if (p[i].a == t) {
			if (sum != n) {
				printf ("Wrong Record\n");
				return 0;
			}
		}
		if (p[i].a > t) {
			ll tt = (sum + 1 + k - 1) / k;
			if (tt <= ans)	ans = tt, ansid = p[i].a;
		}
		sum = max (0ll, sum - k); //这一秒结束了出队
	}

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

H. 提瓦特之旅

dp!!!!!!!!!!
注意转移顺序,长度从小到大

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

using namespace std;
typedef pair<int, int> pii;
const int N = 505, M = 2e5 + 5;
int n, m, q, dis[N], dep[N];
int h[N], e[M], ne[M], idx;
ll w[M], f[N][N]; //f[i][j]: 1到i经过j条边的最小代价
bool vis[N];

void add (int a, int b, ll c) {
	e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

int main () {
	memset(h, -1, sizeof h);
	scanf("%d%d", &n, &m);
	while (m--) {
		int a, b;
		ll c;
		scanf ("%d%d%lld", &a, &b, &c);
		add (a, b, c), add (b, a, c);
	}
	memset(f, 0x3f, sizeof f);
	f[1][0] = 0;
	
	for (int k = 1; k < n; k++) {
		for (int t = 1; t <= n; t++) { //上一个点
			for (int i = h[t]; ~i; i = ne[i]) {
				int j = e[i]; //t -> j
				f[j][k] = min (f[j][k], f[t][k-1] + w[i]);
			}
		}
	}
	
	//dijkstra ();
//	for (int i = 2; i <= n; i++) {
//		for (int j = 1; j <= 10; j++) {
//			cout << f[i][j] << ' ';
//		}
//		cout << endl;
//	}
	
	scanf ("%d", &q);
	while (q--) {
		int t;
		ll sum = 0, x = 0, ans = 1e18;
		scanf ("%d", &t);
		for (int i = 1; i < n; i++) {
			scanf ("%lld", &x);
			sum += x;
			ans = min (ans, sum + f[t][i]);
		}	
		printf ("%lld\n", ans);
	}
}

/*
4 5
1 2 1
1 4 6
2 4 4
2 3 1
3 4 1
*/

I. 宠物对战

还是dp,结合了Trie树,注意是从前往后更新
(其实也非常典)

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

using namespace std;
const int N = 5e5 + 5, M = 5005, inf = 0x3f3f3f3f, P = 13331;
int n, m, f[2][M], son[2][N][30], idx[2], cnt[2][N];
string s, t;

void insert(string str, int id){
	int p = 0, tt = (int)str.size ();
	for (int i = 0; i < tt; i++){
		int u = str[i] - 'a';
		if (!son[id][p][u])    son[id][p][u] = ++idx[id];
		p = son[id][p][u];
	}
	cnt[id][p]++;
}

int main () {
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)	cin >> t, insert (t, 0);
	cin >> m;
	for (int i = 1; i <= m; i++)	cin >> t, insert (t, 1);
	cin >> s;
	int len = s.size();
	s = ' ' + s;
	
	memset(f, 0x3f, sizeof f);
	f[0][0] = f[1][0] = 0;
	for (int i = 1; i <= len; i++) {
		for (int k = 0; k < 2; k++) {
			int p = 0;
			for (int j = i; j <= len; j++) {
				int u = s[j] - 'a';
				p = son[k][p][u];
				if (!p)	break;  //往后也找不到了
				if (cnt[k][p])	f[k^1][j] = min (f[k^1][j], f[k][i - 1] + 1);
			}
		}
	}
	int ans = min (f[0][len], f[1][len]);
	if (ans == inf)	ans = -1;
	cout << ans;
}

//注意必须是交替

L题没咋看懂,问问队友ds qaq

标签:ll,idx,int,tt,d%,CCPC,补题,id,ACEGHI
From: https://www.cnblogs.com/CTing/p/17773346.html

相关文章

  • 【题解】「KDOI-06-S」补题
    「KDOI-06-S」A.「KDOI-06-S」消除序列赛时写了一个\(O(nq)\)的线性DP,喜提60分。注意到如果操作1被使用,则一定只会使用一次,而且在最优策略中一定是第一次使用操作1。则我们可以通过以下方式进行操作,使序列满足条件:首先执行\(a_i\)和\(\sum^{j\lei,i\inP}_{j=......
  • CCPC 秦皇岛 散记
    前言XCPC生涯中的第一次现场赛!原来QZone里已经有了我随便发的几句零星的随感。我个人很少写这些随感类文章,毕竟心里想的可能很多但是苦于言辞不精,很多感觉写出来就变味了。当然也不想随大流写流水账。但是想到生涯的首次出征,也是首次Au,可能还得尽力写得更正式一点。于是......
  • The 2021 CCPC Weihai Onsite
    Preface又被打爆了,看了下榜这场罚时比较炸喜提银首咯不过yysy这场题出的还是挺好的,medium题都挺有意思需要想一想但就是感觉考的组合计数这一块有点太多了,而且因为有人歪榜开局过了M,导致我前期一直在这道题上坐牢,最后还是徐神出马一套生成函数秒了此题A.Goodbye,Ziyin!签......
  • 2022 China Collegiate Programming Contest (CCPC) Guilin Site(持续更新)
    Preface由于还有两周就要滚去打区域赛了,这周开始周末每天都训一场吧这场总体来说打的还可以,虽然E题这个Easy从卡局卡到3h,但由于其它的题都是一遍过所以罚时还尚可跻进Au区后面一个小时看徐神和祁神苦战K大分类讨论,虽然场下感觉摸了一个B的做法出来,但感觉实现还是太麻烦了就没写......
  • 2021 China Collegiate Programming Contest (CCPC) Guilin Site
    A.AHeroNamedMagnus#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongusingpii=pair<int,int>;usingvi=vector<int>;voidsolve(){intx;cin>>x;cout<<2ll*x-1<<"......
  • CSP-S 2021 补题
    P7913[CSP-S2021]廊桥分配考虑对于国际航班和国内航班单独进行分配对于国际航班处理\(res1[i]\)数组作为给国际航班分配\(i\)个廊桥的最大飞机停靠数量\(res2[i]\)同理对于每一种类的航班我们维护一个\(in\)优先队列和一个\(left\)优先队列\(in\)队列中放所有......
  • 动态规划的状态设计 | bot 讲课の补题
    stojames1badcreeperorz.好厉害的题,但是怎么有人补了三天才补完呢?CF1810GTheMaximumPrefix线性dp,怎么有bot说题目难度在*2400~*2800之间结果开场就是*3200啊/youl尝试直接正着做,发现要记\(f_{i,j,k}\)表示前\(i\)个数,最大前缀和是\(j\),当前前缀和是\(k\)......
  • 开学过半 (cf补题和算法训练)
    Problem-A-Codeforces题意:给你一个n/2个元素的b数组,然后让你构造出一个n个元素的排列数组其中这些p数组里的数有以下要求注意这个p数组要求你搞字典序最小,也就是最好小的元素在前面如果b =[4,3,6],那么可以从中得到的词法最小排列是p =[1,4,2,3,5,6],因为:b1=max(p1,p......
  • 模拟赛补题
    农场道路修建与没有上司的舞会类似,关键在于添加道路。添加的道路一定是两点中一有一无或两无,则判断哪些点必须有,用总方案数减去不合法方案数即可。P7828[CCO2021]SwapSwapSort基本思路不难,没有想到根号分治(准确来说是不会,呃呃),以及在\(x\)确定的情况下不会\(O(n)\)处理......
  • 模拟赛补题
    感觉模拟赛质量比之前打的高一些。Day1A赛时过B需要保存每个点的状态,为了使状态数尽量少,让每个点代表右下方是否已经达到终止状态,故如果一个点状态为\(1\),右下方所有点的状态都为1,那么状态能用轮廓线来描述,数量为\(\binom{n+m}{n}\),直接高斯消元。C将每条路径对应到一条......