首页 > 其他分享 >USACO Feb 2024 bronze

USACO Feb 2024 bronze

时间:2024-02-20 09:02:22浏览次数:27  
标签:pre Feb 牛奶 int work 2024 return bronze 赛时

挖个坑,今天晚上完成三篇手工翻译。awa

T1 Palindrome Game

赛时 100分

经典博弈论。手动枚举一下,很容易发现规律,当 S 为 10 的倍数时,先手输。
手动枚举需注意,不会证明你先别急,枚举要多,才能得出普遍规律(这个傻逼比赛刚开始一直打的是,当 S 为时 10 先手输)。

需要注意的是 S 的非常大。

T2 Milk Exchange

赛时 93.75分

简要题意,有一群奶牛,她们和相邻的牛交换牛奶,但是奶牛拿不了那么多牛奶。有些牛奶可能在交换的过程中浪费了。求交换 m 轮后剩余的牛奶。

如果把奶牛们传牛奶的过程抽象一张图的话,如下图(以样例以为例子)。我们很容易可以发现 1 .当这张图是一条链时,牛奶不会浪费。 2. 当两个点单独形成环的时候,牛奶不会浪费。 3. 当两个点形成环且环链接着链时,牛奶会发成浪费。

需要注意:牛奶不是无限多的,数据范围。

赛时代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6;
int n,m,a[N],k[N],s=0;
int pre[N];
char c[N];

int work(int x,int last){
	///if(pre[x]==last) return a[x];
	if(x==-1) return 0;
	return a[x]+work(pre[x],x);
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>c[i];
	for(int i=1;i<=n;i++) cin>>a[i],s+=a[i];
	memset(pre,-1,sizeof(pre));
	for(int i=1;i<=n;i++){
		if(c[i]=='L'){
			if(pre[i]!=i-1) pre[i-1]=i;
			k[i-1]++;
			k[i]--;
		}
		if(c[i]=='R'){
			if(pre[i]!=i+1) pre[i+1]=i;
			k[i+1]++;
			k[i]--;
		}
	} 
	if(pre[1]==0) pre[1]=n;
	if(pre[n]==0) pre[n]=1;  
	k[n]+=k[0];
	k[1]+=k[n+1];   			
	int ans=0;
	for(int i=1;i<=n;i++){
		if(k[i]>0){
			int maxx=work(i,0)-a[i];
			k[i]*=m;
			ans+=min(k[i],maxx);
		} 
	} 
	cout<<s-ans;
	return 0;
}

debug细节处理有误。

订正代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6;
int n,m,a[N],k[N],s=0;
int pre[N];
char c[N];

int work(int x,int last){
	if(x==-1) return 0;
	return a[x]+work(pre[x],x);
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>c[i];
	for(int i=1;i<=n;i++) cin>>a[i],s+=a[i];
	memset(pre,-1,sizeof(pre));
	for(int i=1;i<=n;i++){
		if(c[i]=='L'){
			if(pre[i]!=i-1) pre[i-1]=i;
			k[i-1]++;
			k[i]--;
		}
		if(c[i]=='R'){
			if(pre[i]!=i+1) pre[i+1]=i;
			k[i+1]++;
			k[i]--;
		}
	} 
	if(pre[0]==1) pre[n]=1;
	if(pre[n+1]==n) pre[1]=n;  
	k[n]+=k[0];
	k[1]+=k[n+1];   			
	int ans=0;
	for(int i=1;i<=n;i++){
		if(k[i]>0){
			int maxx=work(i,0)-a[i];
			k[i]*=m;
			ans+=min(k[i],maxx);
		} 
	} 
	cout<<s-ans;
	return 0;
}

T3 Maximizing Productivity

赛时分数 23.53分

题意感觉比较容易让人混淆,反正比赛的时候我是读了很多很多遍。
简要题意:已知 $c_i$,$t_i$ ,多次询问给你 s 和 v。问是否有至少 v 个 i 满足 s + $t_i$ < $c_i$ 。

暴力的做法,很简单。每次询问都遍历一边,统计符合条件的 i 即可。时间复杂度 O(nQ) 。 1≤Q≤2⋅105 ,1≤N≤2⋅105 。这个数据范围显然是难以通过的。

考虑怎么优化。首先 $t_i$,$c_i$ 都是常量,只有s是遍历。 求有多少个 v 个 i 满足 s < $c_i$ - $t_i$(s + $t_i$ < $c_i$→ s < $c_i$ - $t_i$)。
以此我们可以根据 $c_i$ - $t_i$ 对各个农场进行排序。最后二分查找第一个大于 $c_i$ - $t_i$ > s 的农场。即可求出满足条件的农场。

赛时代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int n,q,k[N];
int v,s,jsq;
struct code{
	int c,t,k;
}a[N];
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%d",&a[i].c);
	for(int i=1;i<=n;i++) scanf("%d",&a[i].t);
	
	for(int p=1;p<=q;p++){
		scanf("%d%d",&v,&s);
		jsq=0;
		for(int i=1;i<=n;i++){
			if(s+a[i].t>=a[i].c) continue;
			jsq++;
		}
		if(jsq>=v) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}


需要注意数据范围。

标签:pre,Feb,牛奶,int,work,2024,return,bronze,赛时
From: https://www.cnblogs.com/wh1sky/p/18022323

相关文章

  • 2024年,提升Windows开发和使用体验的一些实践 - 包管理器篇
    前言短暂的春节假期转瞬即逝,忙碌的一年又要开启了......
  • .NET周刊【2月第2期 2024-02-11】
    国内文章C#/.NET该如何自学入门?https://www.cnblogs.com/Can-daydayup/p/18006914随着DotNetGuide技术社区交流群的扩大,很多新成员希望知道如何自学C#/.NET。本文提出了自学建议:首先要了解语言特点与发展,然后制定详细学习计划,以微软官方文档为学习起点,并结合动手实践与其他资源......
  • 2024.2.19 在愿望的最后一个季节 记起我曾身藏利刃
    今天模拟赛,顺利过了T1然后发现T2是答辩题,T3写了送的。出分发现T2挂了,看起来是被T2卡哈希了,魔怔。下午讲的题都挺好的,晚上看了RMR,小蜜蜂乱杀,雪碧乱杀,就连C9都乱杀了,这才是我想象中的一线强队暴打二线队啊,不要学Faze和NAVI。子序列这个做法比较神秘。考虑试填,发......
  • 20240217
    创建拥有多的页面的单Activity应用,使用Jetpack的导航和其他组件1.介绍在这个记账本App中,我们不仅需要一个页面来记录支出和收入,还需要一个页面来显示支出和收入的统计信息。当然我们可以使用两个Activity来实现这个功能,但是Google更推荐的方式是使用单Activity多Fragment的架构......
  • 2024初三集训模拟测试2
    2024初三集训模拟测试2\(T0\)谜之阶乘\(100pts\)详见普及模拟2T4阶乘。\(T1\)小P的2048\(10pts\)大模拟,没什么好说的。注意可以同时合并多对数字,但不能连续合并。点击查看代码lla[10][10];queue<ll>q;intmain(){ lln,m,x1,y1,v1,x2,y2,v2,d,k,v,su......
  • 2024牛客寒假算法基础集训营4 K.方块掉落
    线段树维护的信息有当前行有多少方块,一共有多少方块拿线段树维护一个矩阵就行,转移更新就是矩阵乘类似题有这个 牛客多校第二场-H-zhujio两题都基本上就是转移矩阵求出来正常建线段树,pushup就是直接矩阵乘 #include<bits/stdc++.h>usingnamespacestd;#defineen......
  • 2024程序员能有什么新的出路?
    前言前两天和一个前端同学聊天,他说不准备再做前端了,准备去考公。不过难度也很大。从20152016年那会儿开始互联网行业爆发,到现在有7、8年了,当年20多岁的小伙子们,现在也都30+了大量的人面临这个问题:大龄程序员就业竞争力差,未来该如何安身立命?先说我个人的看法:除非你......
  • [20240219]建立完善sql_idx.sh脚本.txt
    [20240219]建立完善sql_idx.sh脚本.txt--//再次遇到sql_id的计算问题,该语句已经dba_hist相关视图无法查询.--//w3wp.exe程序里面的sql语句脚本带有^M符号(dos文本格式),执行时并不过滤.--//而我的计算sql_id脚本计算时过滤掉^M符号,导致计算错误.--//我修改完善如下:(注里面的^M......
  • 2024九省联考 数学 T19
    寒假有朋友打电话吐槽九省联考,看了眼数学卷子感觉非常刺激。刚开学没事干,试着做一下\(19\).(\(17\)分)离散对数在密码学中有重要的应用。设\(p\)是素数,集合\(X=\{1,2,\cdots,p-1\}\),若\(u,v\inX,m\in\mathbb{N}\),记\(u\otimesv\)为\(uv\)除以\(p\)的余数,\(u^{m,......
  • 2024牛客寒假算法基础集训营4 H&K
    H传送门  观察下图  1.只有在横着连续有三个*的时候才可能会出现三角形,并且随着横坐标的增加实际上增加的是(从左往右从上往下方向)斜对角线上点的数量。  2.当横着连续有3-4个的时候斜线的长度为2,当横着又连续5-6个的时候斜线的长度为3,以此类推,所以启发使用......