首页 > 其他分享 >初三赛季杂题泛做（9-10月）

初三赛季杂题泛做（9-10月）

时间：2023-07-12 17:22:25浏览次数：55  
标签：10 cnt const cur int tot st 赛季 杂题

CF1580 div1

A:

傻逼题，一开始没想出来，冷静了一会发现可以枚举两行，中间记录个前缀后缀最小值就行了

B:

考虑dp，设f[n][m][k]为答案，发现枚举最大数的位置可以做，于是就做了

N^5tm能过

C:

想了一会，然后5ab说可以根号分治，我想了想好像真可以，于是就写了。

x+y大于sqrtn的直接开大桶算贡献，反正不会T

x+y小于sqrtn的，因为只有sqrt种x+y，直接对于每种开一个余数的小桶记录，修改的时候暴力修改，反正不会T

D:

只要会dicker树的人一般都会，可惜我不会

建出dicker树，考虑把答案转成这样:

$ \sum_{i=1}{n}\sum_{j=1} a_i+a_j-2\times a_{lca(i,j)}$

这东西很像距离，于是w(i,j)=ai-aj,这东西就是距离了

于是变成要求树上选m个点，两两距离和最大

这东西转成贡献，上树形dp就行了

f[i][j]表示考虑了i子树内选出j个点，边的贡献和最大是多少

$f[u][j]=\max(f[v][k]+f[u][j-k]+Wv×j×(M-j))$

O(N^2)

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=4005;
int a[N],ls[N],rs[N],sz[N];
int st[N],tot;
typedef long long ll;
ll lw[N],rw[N],f[N][N];
void dfs(int u){
	int i,j;sz[u]=1;
	if(ls[u]){
		dfs(ls[u]);
		for(i=min(sz[u],m);i>=0;i--)
			for(j=min(sz[ls[u]],m);j>=0;j--)
				f[u][i+j]=max(f[u][i+j],f[ls[u]][j]+lw[u]*j*(m-j));
		sz[u]+=sz[ls[u]];
	}
	if(rs[u]){
		dfs(rs[u]);
		for(i=min(sz[u],m);i>=0;i--)
			for(j=min(sz[rs[u]],m);j>=0;j--)
				f[u][i+j]=max(f[u][i+j],f[u][i]+f[rs[u]][j]+rw[u]*j*(m-j));
		sz[u]+=sz[rs[u]];
	}
}
int main(){
	int i;
	cin>>n>>m;
	for(i=1;i<=n;i++){
		scanf("%d",&a[i]);
		while(tot>0&&a[st[tot]]>a[i])ls[i]=st[tot],lw[i]=a[st[tot]]-a[i],tot--;
		if(tot)rs[st[tot]]=i,rw[st[tot]]=a[i]-a[st[tot]];
		st[++tot]=i;
	}
	dfs(st[1]);
	cout<<f[st[1]][m];
	return 0;
}

接下来是更重要的反思:

这场比赛前4题都是力所能及的，zky90分钟就全过了

然而由于状态原因（累、太不激动），脑子不是很活跃。

排列的问题大多可以通过枚举最大值解决，但我忘了。

根号分治没想到可以把<sqrtn的直接暴力开桶

。。。

以后一定要早睡，给第二天一个好状态！

不要思维定势！！！

UOJ Round #22

估计是AFO前第一场也是最后一场UOJ了

A是个傻逼题，卡2log，煞笔煞笔煞笔

B、C完全不会

反思:过了大样例也要思考如何卡常！！！

LG 10月月赛I

C 构造题，一如既往地不会！！！

D 根本没来得及仔细想，也没透彻理解算本质不同子序列的性质！！！

反思:多刷构造题，数学构造都是解方程！

每道题都是可做的！要迎难而上！

LG 10月月赛II

C是个傻逼，但可惜我没发现单调性，于是只会90

D是个傻逼，经过CXY提醒后过了

反思:像C这种细节巨大的ds题，考场上直接交暴力！

CF 1592div2

ABC没看，是5ab写的

D也没想到dfs序的做法，搞了个子树大小，但既然数据水就算了。。。

E嘛，反正我只会每一位拆开算，懒得写。具体说就是枚举到一个位，区间长度是偶数并且与起来全是1，然后前面几位只能全是0（如果都是1那长度就是奇数了不符）所以，与起来为0且有偶数个1（前缀异或值相同）

F1，一直以为是DP，没想到贪心做法这么巧妙，给出题人点赞！Orz 9999！%%%

F2，巧妙的建二分图，Orz 9999！%%%

反思:树上二分考虑dfs序，这是好的

时间来不及了就不要写ds题！(和9999一样)

其实不需要啥事都往dp想，百、千级别的数据范围还可以是二分图！

实在不会做了或者太难写了就跳题罢！

NC 赛前训练营 4 T3

从小到大考虑选取第j个可以被贿赂的人，F[i][j]表示已经考虑了前i个人并且树上从根到i的路径上被取人的状态是j的方案数。组合数转移！

考虑n很小，爆搜出可能的序列，也很少，于是直接暴力带入序列进行DP就行了！！！

多做做鼠穴DP题

从小到大考虑dp，可以方便很多

CF EDU div2 115

E是个傻逼题，我不到10分钟就想到了，但因为没有选择比较好的实现方式，考试结束都没调完。

F也是个傻逼题，n很小，可以考虑状压dp，把括号序列转成1,-1的序列，再记录每个串的和，和前缀最小值的位置。直接在vector里面二分即可。

最近怎么看到DP就不会啊，还是要多做做DP

最近喜欢做一些似是而非的神必ds题

首先观察到答案就是按Bi排序的逆序对数

答案可以这么计算：

$\sum_{i=1}^k \sum_{j=i+1}^k f(S[b[i]],S[b[j]])$

$ 其中 S[i] 表示权值为i的位置集合，f(A,B)代表B中每个数在A中贡献逆序对数之和（类似归并）$

因为交换的是相邻的b[i],所以对答案的影响就是$2f(S[b[i]],S[b[i+1]])-c[b[i]]\times c[b[i+1]]$

考虑n是1e5级别的，同时这柿子也没啥性质，于是考虑根号分治。

考虑询问(b[x],b[x+1])时,分成两种情况：

  • $\max(cnt[b[x]],cnt[b[x+1]]) \le \sqrt n$
    :此时直接暴力双指针O(sqrt N)算贡献
  • $\max(cnt[b[x]],cnt[b[x+1]]) > \sqrt n$ 这样的b[x]不超过$\sqrt n $个（称为关键点），所以离线在每个关键点上O(n)处理每个包含此关键点的询问的答案
#include<bits/stdc++.h>
using namespace std;
int n,k,m;
const int N=100005,M=1000005;
int a[M],b[M];
#define lim 100  
int Q[M][2];
vector<int> g[M];
#define P pair<int,int>
#define fi first
#define se second
vector<P > q[M];
typedef long long ll;
ll c[M],s[M],w[M],u[M];
#define lowbit(x) x&-x
void add(int x){
	while(x<=k){
		u[x]++;
		x+=lowbit(x);
	}
}
ll sum(int x){
	ll res=0;
	while(x){
		res+=1ll*u[x];
		x-=lowbit(x);
	}
	return res;
}
inline ll solve(int x,int y){
	register int i;int p=1;
	ll ans=0;
	for(i=1;i<=g[x].size();++i){
		while(p<=c[y]&&g[y][p-1]<g[x][i-1])p++; 
		ans+=1ll*(p-1);
	}
	return ans;
}
inline void sol(int x){
	int tot=0;register int i;
	memset(w,0,sizeof(w));
	for(i=n;i>=1;--i){
		if(a[i]==x)tot++;
		else w[a[i]]+=1ll*tot;
	}
	for(i=0;i<q[x].size();++i){
		int to=q[x][i].fi,id=q[x][i].se;
		s[id]=w[to];
	}
}
inline int read(){
	char c=getchar();int O=0;
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')O=(O<<1)+(O<<3)+(c^48),c=getchar();
	return O;
}
int main(){
	register int i;
	n=read(),k=read(),m=read();
	for(i=1;i<=n;++i)a[i]=read(),g[a[i]].push_back(i),c[a[i]]++;
	for(i=n;i>=1;--i)s[0]+=sum(a[i]-1),add(a[i]);
	for(i=1;i<=k;++i)b[i]=i;
	for(i=1;i<=m;++i){
		int p=read();swap(b[p],b[p+1]);
		if(max(c[b[p]],c[b[p+1]])<=lim)s[i]=solve(b[p+1],b[p]);					
		else{
			if(c[b[p+1]]>c[b[p]])q[b[p+1]].push_back(make_pair(b[p],i));
			else q[b[p]].push_back(make_pair(b[p+1],i));
		}
		Q[i][0]=b[p+1],Q[i][1]=b[p];
	}
	for(i=1;i<=k;++i)if(c[i]>lim)sol(i);
	for(i=1;i<=m;++i){//求XI[x,y] when c[x],c[y]>sqrt(n) 
		int x=Q[i][0],y=Q[i][1];
		if(max(c[x],c[y])<=lim)s[i]=s[i-1]-s[i]*2+c[x]*c[y];
		else{
			if(c[x]<=c[y])s[i]=s[i-1]+s[i]*2-c[x]*c[y];
			else s[i]=s[i-1]-s[i]*2+c[x]*c[y];
		}
		printf("%lld\n",s[i]);
	}
	return 0;
}

[CCO2021]SWAP SWAP SORT

一开始写的是错解却过了

看到最小化极差想到双指针，毕竟已经被ZJOI搞过一次了。

每次枚举选进的点，看只选这些点和最短路上的边，能不能从1走到n，BFS就行了。

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m;
typedef long long ll;
int cnt,h[N],nxt[N],to[N];
ll val[N],a[N];
void add(int x,int y,ll z){
	nxt[++cnt]=h[x];
	h[x]=cnt;
	to[cnt]=y,val[cnt]=z;
}
queue<int> q;
struct node{
	int id;ll v;
	bool operator < (const node &w)const{
		return v>w.v;
	}
};
priority_queue<node> Q;
int vis[N];
ll dis[N];
int ok[N],bl[N];
int cmp(int x,int y){
	return a[x]<a[y];
}
void dij(){
	for(int i=2;i<=n;i++)dis[i]=1e18;
	Q.push((node){1,0});
	while(!Q.empty()){
		node u=Q.top();Q.pop();
		for(int i=h[u.id];i;i=nxt[i]){
			int v=to[i];ll w=val[i];
			if(dis[v]>dis[u.id]+w){
				dis[v]=dis[u.id]+w;
				Q.push((node){v,dis[v]}); 
			}
		}
	}
}
int bfs(){
	while(!q.empty())q.pop();
	memset(vis,0,sizeof(vis));
	if(!ok[1]||!ok[n]){return 0;}
	q.push(1),vis[1]=1;
	while(!q.empty()){
		int x=q.front();q.pop();
		if(n==x){return 1;}
		for(int i=h[x];i;i=nxt[i]){
			int v=to[i];ll w=val[i];
			if(ok[v]&&dis[v]==dis[x]+w&&!vis[v]){
				vis[v]=1;
				q.push(v);
			}
		} 
	}
	return 0;
}
int main(){
	int i;
	cin>>n>>m;
	for(i=1;i<=n;i++)scanf("%lld",&a[i]),bl[i]=i;
	sort(bl+1,bl+n+1,cmp);
	for(i=1;i<=m;i++){
		int x,y;ll z;
		scanf("%d%d%lld",&x,&y,&z);
		add(x,y,z),add(y,x,z);
	}
	dij();
	cout<<dis[n]<<endl;
	int r=0;
	ll ans=2e18;
	for(i=1;i<=n;i++){
		r=max(r,i-1);
		int flag=0;
		while(r<=n){
			if(bfs()){
				flag=1;
				break;
			}
			ok[bl[++r]]=1;
		}
		if(flag)ans=min(ans,a[bl[r]]-a[bl[i]]);
		ok[bl[i]]=0;
	}
	cout<<ans<<endl;
	return 0;
}

题目叫不想爬坡

rnm，终于过了，不开O2荣登最劣解

建立因数trie

显然每次贪心往自己最小的因数走，不超过log步

用set维护一下子树的不同质因子个数(每个数最多8个)和儿子的倍数就行了

O(8nlogn^2),还用了一堆set,比cxy劣了128倍

#include<bits/stdc++.h>
using namespace std;
#define ri register int
const int N=1e5+5;
int n;
struct st{int x,id;}p[N];
int cmp(const st &a,const st &b){return a.x < b.x;}
int ok=1,fa[N];
namespace GTR {
const int bufl=1<<15;char buf[bufl],*s=buf,*t=buf;
inline int fetch(){if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}return *s++;}
inline int read(){int a=0,b=1,c=fetch();while(!isdigit(c))b^=c=='-',c=fetch();while(isdigit(c))a=(a<<1)+(a<<3)+(c^48),c=fetch();return b?a:-a;}
inline void write(int x){if(x>9)write(x/10);putchar(x%10+48);}}
using GTR::read;using GTR::write;
multiset<int> g[N],G[N]; 
const int M=1000000; 
int tot,pr[M+5],vis[M+5],mn[M+5],f[N];
int cnt,h[M],nxt[M*3],to[M*3];
inline void add(int x,int y){
	nxt[++cnt]=h[x];
	h[x]=cnt;
	to[cnt]=y;
}
void xs(int mx){
	ri i,j; 
	for(i=2;i<=mx;++i){
		if(!vis[i]){
			pr[++tot]=i;
			mn[i]=i;
		}
		for(j=1;pr[j]<=mx/i&&j<=tot;++j){
			mn[i*pr[j]]=min(mn[i],pr[j]);
			vis[i*pr[j]]=1;
			if(i%pr[j]==0)break;
		}
	}
}
void pan(int cur,int ban,int x){
	for(ri j=h[x];j;j=nxt[j])
		if(g[cur].count(to[j])>G[ban].count(to[j])){
			ok=0;
			return ;
		}
}
int mx;
#define P pair<int,int>
set<P > s[N];
void upd(int cur,int tar){
	while(ok){
		int fl=0;P w=make_pair(p[tar].x,0),x;
		if(p[cur].x==p[tar].x){
			fa[p[tar].id]=p[cur].id;
			return ;
		}
		if(s[cur].lower_bound(w)!=s[cur].end()){
			x=*s[cur].lower_bound(w);
			if(x.first==p[tar].x)pan(cur,x.second,p[tar].x/p[cur].x),fl=1,cur=x.second;
		}
		if (!fl){
			pan(cur,0,p[tar].x/p[cur].x);
			fa[p[tar].id]=p[cur].id; 
			f[tar]=cur;
			for(ri i=p[tar].x;i<=mx;i+=p[tar].x)s[cur].insert(make_pair(i,tar));
			int pos=tar;
			while(pos){
				for(ri i=h[p[tar].x/p[pos].x];i;i=nxt[i])g[pos].insert(to[i]);
				if(f[pos])for(ri i=h[p[tar].x/p[f[pos]].x];i;i=nxt[i])G[pos].insert(to[i]); 
				pos=f[pos];
			}
			return;
		}
	}
}
int main(){
	ri i,j;
	n=read();
	for(i=1;i<=n;++i)p[i]=(st){read(),i},mx=max(mx,p[i].x);
	sort(p+1,p+n+1,cmp);
	xs(mx);
	for(i=2;i<=mx;++i){
		int w=i,ls=0;
		while(w>1){
			if(mn[w]!=ls){
				add(i,mn[w]);
				ls=mn[w];
			}
			w/=mn[w];
		} 
	}
	for(i=2;i<=n&&ok;++i){
		if(p[i].x%p[1].x){puts("-1");return 0;}
		upd(1,i);
	}
	if(ok==0)puts("-1");
	else for(i=1;i<=n;++i)write(fa[i]),putchar(' ');
	return 0;
}

这题叫GCD TREE

NC周赛TG28题解

T1 傻逼期望题，不用想复杂，考虑相邻边对自己的贡献即可

T2 好题：

考虑把指数拆开，$A^p= (Ap-A)+(A{p-1}-A)+...+(A-1)+(1-0)$ 因为柿子中每一项都比后一项大，所以如果把每项的价值定为1，重量定位自己的话，肯定是从小往大取到某一项，等价于在所有次幂中选择一个，价值是幂。

因为wi很大，所以我们考虑用答案去拼出wi，因为要求最大，所以相当于处理刚好x个能拼出的最小数（容易发现x是$\sqrt n$ 级别的），所以考虑取前x个最小的就行了。于是就从小到大枚举$d$,看d能被加入几次，不断减掉就行了。

T3 cxy的神题

我想了一年都不会啊。

首先找到 [l1, r1] 中的最大值，设其为 x，然后在 [l2, r2] 中找有没有合法的配对，如果有，直接
return，否则说明 [l2, r2] 中没有值在 [x/2, x − 1] 中的数。
然后去找到 [l2, r2] 中小于x/2的最大值，设其为 y，然后在 [l1, r1] 里找有没有合法的配对，如果
有，return，否则说明 [l1, r1] 中没有值在 [y + 1, 2 × y − 1] 内的数。
然后再在 [l1, r1] 中找到小于 y + 1 的最大数，如此这样循环往复，仍然是 log v 次枚举后排除所有
值域。
在 [l, r] 中找值域在 [L, R] 的数中的最大值可以用主席树求解。

标签：10,cnt,const,cur,int,tot,st,赛季,杂题
From： https://www.cnblogs.com/anticipator/p/17548274.html

相关文章

  • P1002 [NOIP2002 普及组] 过河卒 入门级别的dp
     思路：1.标记马点z[i][[j]=02.正常z[i][j]=z[i-1][j]+z[i][j-1]#include<iostream>usingnamespacestd;intn,m,a,b;longlongma[30][30],bck[30][30];intdx[8]={-2,-1,1,2,2,1,-1,-2},dy[8]={1,2,2,1,-1,-2,-2,-1};voidcan_not_reach(intx,inty){ma[......
  • HJ102 字符统计
    1.题目读题HJ102 字符统计  考查点 这道题的考查点可能是以下几个方面：字符串的处理和操作，如遍历、分割、拼接等。数据结构的选择和使用，如数组、字典、列表等。排序算法的理解和实现，如冒泡排序、选择排序、快速排序等。编程语言的基本语法和规范，如变量、函数、循......
  • RedHat5.5安装Oracle10205
    1.安装前准备1.1.修改hostsvi/etc/hosts192.168.1.100test01#这一句不是命令，是追加到hosts文件中1.2.关闭防火墙等#关闭防火墙serviceiptablesstopchkconfigiptablesoff#关闭NetworkManagerserviceNetworkManagerstopchkconfigNetworkManageroff#关......
  • 10.AbstractQueuedSynchronizer（AQS）
    AbstractQueuedSynchronizer（AQS）AQS入门理论知识概念​ 抽象队列同步器，是用来实现锁或者其它同步器组件的公共基础部分的抽象实现，是重量级基础框架及整个JUC体系的基石，主要用于解决锁分配给"谁"的问题​ 整体就是一个抽象的FIFO队列来完成资源获取线程的排队工作，并通过一个int......
  • HJ100 等差数列
    1.题目读题HJ100 等差数列  考查点 2.解法思路 等差数列是指从第二项起，每一项与它的前一项的差等于同一个常数的一种数列。这个常数叫做等差数列的公差，公差常用字母d表示。等差数列的通项公式是：an=a1+(n-1)d，其中a1是首项，an是第n项，n是正整数。等差数列的前n项......
  • 【雕爷学编程】Arduino动手做（117）---P10V706LED屏模组4
    37款传感器与执行器的提法，在网络上广泛流传，其实Arduino能够兼容的传感器模块肯定是不止这37种的。鉴于本人手头积累了一些传感器和执行器模块，依照实践出真知（一定要动手做）的理念，以学习和交流为目的，这里准备逐一动手尝试系列实验，不管成功（程序走通）与否，都会记录下来—小小的进步或是搞......
  • 【雕爷学编程】Arduino动手做（117）---P10V706LED屏模组3
    37款传感器与执行器的提法，在网络上广泛流传，其实Arduino能够兼容的传感器模块肯定是不止这37种的。鉴于本人手头积累了一些传感器和执行器模块，依照实践出真知（一定要动手做）的理念，以学习和交流为目的，这里准备逐一动手尝试系列实验，不管成功（程序走通）与否，都会记录下来—小小的进步或是搞......
  • 题：10. 正则表达式匹配
    leetcode题：（https://leetcode.cn/problems/regular-expression-matching/）给你一个字符串s和一个字符规律p，请你来实现一个支持'.'和'*'的正则表达式匹配。'.'匹配任意单个字符'*'匹配零个或多个前面的那一个元素所谓匹配，是要涵盖整个字符串s的，而不是部分字符串。示......
  • 【雕爷学编程】Arduino动手做（117）---P10V706LED屏模组2
    37款传感器与执行器的提法，在网络上广泛流传，其实Arduino能够兼容的传感器模块肯定是不止这37种的。鉴于本人手头积累了一些传感器和执行器模块，依照实践出真知（一定要动手做）的理念，以学习和交流为目的，这里准备逐一动手尝试系列实验，不管成功（程序走通）与否，都会记录下来—小小的进步或是搞......
  • 7DGroup性能&测试开发文章持续更新（2019/10/15）
    性能闲谈系列：浅谈window桌面GUI技术及图像渲染性能测试实践杂谈：性能测试的范围到底有多大？戏说CPU使用率-驳《CPU使用率度量指标是扯淡！》译文标题对性能测试评估分析优化市场的反思泛谈系统级跟踪和应用级跟踪性能测试分析优化该有的范围期待996ICU的条款尽早加入到开源协议中！性能基......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99