首页 > 其他分享 >11.3 模拟赛小记

11.3 模拟赛小记

时间：2023-11-03 21:34:01浏览次数：24  
标签：std int ll d% long 11.3 ans 模拟 小记

今天题目质量逆天，题也不是那个他讲的。应该是生气了。所以我也不打算写赛时记录了。

T1 分讨负数个数，T2 二分答案；T3 我写了哈希，想半天想不到性质；T4 小范围暴力大范围输出区间最大值 + 暴力之类的。

本场的感觉很不好。模拟赛期间最绝望的是闲下来：指已经不能进一步思考、没有什么需要调了、没有暴力要打了、没什么事干，就很难受。真不知道正式考场上遇到这种情况该怎么办。

妈的，最后 15min 想出来一个 T3 的部分分，没调完，我急了。赛时摆烂导致的！

A.flip

给一个有正负数的序列。可以无限次将相邻两数都乘 1。求能得到最大的序列和。

分类讨论一下序列中个数：奇数个负数，则一定可以都变成正数；否则最后序列中一定有一个负数，让绝对值最小的数做负数就好了。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int n;
int tot;
ll ans;
int a[N];
int main(){
//	freopen("flip.in","r",stdin);
//	freopen("flip","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i]<0) tot++;
		a[i]=abs(a[i]);
	}
	sort(a+1,a+n+1);
	if(tot&1) ans=-a[1];
	else ans=a[1];
	for(int i=2;i<=n;i++) ans+=a[i];
	printf("%lld",ans);
	
}

B.cut

不介绍题目了。二分答案板子。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int n,ans=-1;
int l,r;
int a[N];
ll m;
bool check(int x){
	ll tot=0;
	for(int i=1;i<=n;i++){
		if(a[i]>x) tot+=a[i]-x;
	}
	return tot>=m;
}
int main(){
//	freopen("cut.in","r",stdin);
//	freopen("cut.out","w",stdout);
	scanf("%d%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		r=max(r,a[i]);
	}
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)){
			l=mid+1;
			ans=mid;
		}
		else r=mid-1;
	}
	printf("%d",ans);
}

C.模糊匹配(match)

正解是线段树维护字符串的哈希值。

赛时写了 \(O(n^2l)\) 的暴力。最后想出了一个 \(O(l^2 n\text{ }logn)\) 的对于第三部分分的暴力但没写完。这 30pts 也不该失啊。

这是 70pts 的码。没想到这么好写。

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
using namespace std;
const int N=3e4+10;
int n,len;
string s;
ull f;
map<ull,int> cnt[210];
ll ans;
int main(){
	scanf("%d%d",&n,&len);
	for(int i=1;i<=n;i++){
		cin>>s;
		for(int j=0;j<len;j++){
			f=0;
			for(int k=0;k<len;k++){
				if(j==k) continue;
				f=f*131+(s[k]-'a'+1);
			}
			ans+=cnt[j][f];
			cnt[j][f]++;
		}
	}
	printf("%lld",ans);
}

然后发现那个 \(O(L)\) 计算删掉一位的哈希值的过程可以优化成 \(O(1)\)，即先处理出整个串的哈希值。

在这里的字符串哈希指转为一个 P 进制数，所以减去那一位的哈希值就能写成 f-(s[j]-'a'+1)*p[len-j-1]，其中 p 数组是我们预处理出用来进行算的 P 的幂。通常取 131 或 13331，此时冲突的可能性极低。同时，取模其实是个很慢的过程，所以这里用 unsigned long long 的类型的自然溢出代替。

\(O(Ln\text{ }log n)\) 理论上能过，但是容易卡。加了很多奇奇怪怪的卡常优化，在 oj 上成功卡到了 90pts。虽然最后交上了完美的 std。

这是我的去掉火车头的 Code：（其实用 vector 优化常数就能过了。但是我太懒了不想写。）

#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N=3e4+10;
int n,len;
char s[N];
ull f,p[210];
map<ull,int> cnt[210];
ll ans;
int main(){
	scanf("%d%d",&n,&len);
	p[0]=1;
	for(int i=1;i<=len;i++) p[i]=p[i-1]*131;
	for(int i=1;i<=n;i++){
		scanf("%s",s);
		f=0;
		for(int j=0;j<len;j++)
			f=f*131+(s[j]-'a'+1);
		for(int j=0;j<len;j++){
			ull t=f-(s[j]-'a'+1)*p[len-j-1];
			ans+=cnt[j][t];
			cnt[j][t]++;
		}
	}
	printf("%lld",ans);
	return 0;
}

这是伟大的 std。

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int n,l,s;
ll ha[30005],t[30005],Hina[205];
char c[300005][205];
const int p = 2333;

int main()
{
#ifndef ONLINE_JUDGE
    freopen("match.in", "r", stdin);
    freopen("match.out", "w", stdout);
#endif
	scanf("%d%d%d",&n,&l,&s);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= l; j++)
		{
			cin >> c[i][j];
			ha[i] = ha[i] * p + c[i][j];
		}
	}
	Hina[0] = 1;
	for (int i = 1; i <= l; i++)
	{
		Hina[i] = Hina[i - 1] * p;
	}
	int ans = 0;
	for (int i = 1; i <= l; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			t[j] = ha[j] - c[j][i] * Hina[l - i];
		}
		sort(t + 1,t + n + 1);
		int tmp = 1;
		for (int j = 1; j < n; j++)
		{
			if (t[j] != t[j + 1]) tmp = 1;
			else 
			{
				ans += tmp;
				tmp++;
			}
		}
	}
	printf("%d\n",ans);
	//system("pause");
	return 0;
}

赛时纯纯的脑瘫了属于是。不太会哈希导致的。

D.养花(flower)

这是赛时的码。

#include<bits/stdc++.h>
#define push_up(x) (ans[x]=max(ans[x<<1],ans[x<<1|1]))
using namespace std;
const int N=2e5+10;
const int M=6e5+10;
int n,m;
int a[N];
int flag=1;
int ans[M],tag[M];
void build(int p,int l,int r){
	int mid=(l+r)>>1;
	if(l==r){
		ans[p]=a[l];
		return;
	}
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	push_up(p);
}
int query(int p,int l,int r,int nl,int nr){
	if(l>=nl&&r<=nr) return ans[p];
	int mid=(l+r)>>1;
	int ans=0;
	if(nl<=mid) ans=query(p<<1,l,mid,nl,nr);
	if(nr>mid) ans=max(ans,query(p<<1|1,mid+1,r,nl,nr));
	return ans;
}
void solve(){
	build(1,1,n);
	while(m--){
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		int ans=query(1,1,n,l,r);
		if(ans<k){
			printf("%d\n",ans);
			continue;
		}
		ans=0;
		for(int i=l;i<=r;i++){
			ans=max(ans,a[i]%k);
			if(ans==k-1) break;
		}
		printf("%d\n",ans);
	}
}
int main(){
//	freopen("flower.in","r",stdin);
//	freopen("flower","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i]>300) flag=0;
	}
	if((n>10000&&flag)||n>50000){solve();return 0;}
	while(m--){
		int l,r,k;
		int ans=0;
		scanf("%d%d%d",&l,&r,&k);
		for(int i=l;i<=r;i++){
			ans=max(ans,a[i]%k);
			if(ans==k-1) break;
		}
		printf("%d\n",ans);
	}
}

（这里的线段树其实就是个求区间最值的幌子。我其实不会写线段树啊。

贺了一份代码 qwq。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,m;
int a[N];
int len,cnt;
int mx[N],bel[N];
struct node{int l,r;int mx[N];}bl[2005];
int query(int l,int r,int mod){
	int res=0;
	if(bel[l]==bel[r]){
		for(int i=l;i<=r;i++) res=max(res,a[i]%mod);
	}
	else{
		for(int i=l;bel[i]==bel[l];i++) res=max(res,a[i]%mod);
		for(int i=bel[l]+1;i<bel[r];i++) res=max(res,bl[i].mx[mod]);
		for(int i=r;bel[i]==bel[r];i--) res=max(res,a[i]%mod);
	}
	return res;
}
int main(){
	scanf("%d%d",&n,&m);
	len=sqrt(n*log2(n));
	for(int i=1;i<=n;i++){
		bel[i]=(i-1)/len+1;
		scanf("%d",&a[i]);
		if(bel[i]!=bel[i-1]){
			bl[bel[i]].l=i;
			cnt++;
		}
		bl[bel[i]].r=i;
	}
	for(int i=1;i<=cnt;i++){
		memset(mx,0,sizeof mx);
		for(int j=bl[i].l;j<=bl[i].r;j++) mx[a[j]]=a[j];
		for(int j=1;j<=1e5;j++) mx[j]=max(mx[j-1],mx[j]);
		for(int k=1;k<=1e5;k++)
			for(int num=0;num<=1e5;num+=k)
				bl[i].mx[k]=max(bl[i].mx[k],mx[min(100000,num+k-1)]-num);
	}
	for(int i=1;i<=m;i++){
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		printf("%d\n",query(l,r,k));
	}
	return 0;
}

标签：std,int,ll,d%,long,11.3,ans,模拟,小记
From： https://www.cnblogs.com/Moyyer-suiy/p/17808539.html

相关文章

  • 金油胜手：11.3黄金、原油行情走势分析及操作建议
     现货黄金--  周五（11月3日）亚市盘中，黄金价格交投于1984美元/盎司附近，在美联储周四连续第二次会议维持利率不变后，美国国债延续了3月份以来的最大涨幅。这一决定强化了人们的猜测，即美联储已经结束了自上世纪80年代初以来最激进的货币紧缩政策。但随着美联储主席鲍威尔为进一步......
  • NOIP2023模拟9联测30
    这篇博客是第二天赛时写的。（恼）T1数学题。肯定是想把\(k\)质因数分解，然后找一找规律，发现对于一个最小的\(n\)一定不包括除了\(k\)有的质因子以外的其他质因子，因为其他质因子对是不是\(k\)的倍数没有用。\(n^2\)相当于把\(n\)的所有质因子的指数乘了个\(2\)，那么只......
  • 代码模拟死锁
    publicclassDeadLockDemo{privatestaticObjectresource1=newObject();//资源1privatestaticObjectresource2=newObject();//资源2publicstaticvoidmain(String[]args){newThread(()->{synchronized(resource1......
  • 飞行模拟机—使用WED建设一个新机场
    为了有一个独立的数据验证空间，我们需要自己来建一个机场，今天用到的工具是WorldEditor2.5（简称WED）。WED软件功能非常丰富，可用来绘制机场的多种场景，当下我们只取其中关于跑道和灯光的内容来使用，机坪、滑行道等细节内容时间关系暂时就不考虑了。打开软件后，在初始界面中，首先......
  • 2023.11.3 做题记录
    CF349B*1700\(Igor\)深深爱上了\(Tanya\).现在,\(Igor\)想表达他的爱意,他便在\(Tanya\)家对面的墙上写下一串数字.\(Igor\)认为,数字写得越大,\(Tanya\)越喜欢他.不幸的是,他只有\(v\)升油漆,每个数字都会花掉一定的油漆\(a_i\).\(Igor\)不喜欢\(0\)所以数中不会出......
  • 使用Qemu在Windows上模拟ARM平台
    我们平常使用的PC一般都是x86架构的IntelCPU，如果由于某些原因，需要使用arm架构的操作系统，我们无法使用一些虚拟机软件（如vmwareworkstation、virtualbox等）进行安装，因为这种类型的虚拟机软件只能安装和宿主机的CPU相同架构的系统。此时，我们可以使用qemu软件。Qemu是一款开源的模拟......
  • 模拟退火（浅谈）
    写在前面放眼历史，喧嚣过后终归无声，热寂才是最终归宿。算法思想世界上的万事万物总是比较容易稳定在低能量的状态，当物体温度较高时，内能较大，固体内部粒子处于快速无规则运动，在固体温度慢慢降低的过程中，固体内能减小，粒子慢慢趋于有序。举个现实生活的小栗子：在冶金工业中，通常会把......
  • NOIP2023模拟9联测30 T4 金牌
    NOIP2023模拟9联测30T4金牌LCA还能\(O(1)\)……思路思路非常简单，可考试就是想歪成统计指数了……将一条穿过\((x,y)\)的路径\((u,v)\)分为\(u\tox\toy\tov\)，所以说对答案的贡献为：\[2^{dis(u,x)+dis(x,y)+dis(y,v)}=2^{dis(u,x)}\times2^{dis(x,y)}\times2^{......
  • NOIP2023模拟9联测30 T3 高爸
    NOIP2023模拟9联测30T3高爸三分啊，三分……思路设现在的平均力量值为\(x\)，大于\(x\)力量值的龙有\(n\)条，小于等于的龙有\(m\)条，花费为：\[a(n\timesx-\sum_{i=1}^{n+m}p_i(p_i>x))+b(\sum_{i=1}^{n+m}p_i(p_i\leqx)-m\timesx)\]对于\(a(n\timesx-\sum_{......
  • 11.2 模拟赛小记
    赛时记录：5min：瞄了一眼题，感觉今天的部分分还是很多。写了一点目标分数和做题计划，就开始看T1。很明显的dij，但想怎么转点权。15min：点权转边权多源最短路，考虑建反边+超级源点就能完美解决。开写。代码实现用了5min但答案不对。哦，输出魅力值最高的城市。写成魅力值最高了。......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99