首页 > 其他分享 >初三赛季杂题泛做

初三赛季杂题泛做

时间：2023-07-12 17:26:14浏览次数：31  
标签：int 杂题 ll mx2 sqrt 赛季 ans 初三 mx

模拟赛1006 T3

可以发现交集点选的边一定是它的最小生成树上的，2^n爆算即可

模拟赛1006 T4

这种题做过好多遍了，一个广为人知的结论就是k选的区间一定是k+1选的区间的前缀，线段树上二分即可

模拟赛1007 T3

考虑每个不同的字符串前缀都会作为一个trie树上的节点，于是表示出每个前缀t至少出现一次的概率，加起来就是期望了。柿子用背包算。

设T中字符分别出现(T0,..Tn)次

P(T是S前缀)=

$\frac {A_{\sum Si}^{\sum ti}}{\prod A_{Si}^{Ti}}$

模拟赛1007 T4

自己看题解

计蒜客1007 T4

i=k时候，答案不超过n/k

线段树上二分即可

CF 1572D

建出二分图。

考虑每加入一条边，删去相邻边2n-1条，所以k-1次之后一定可以选第(2n-1)(k-1)+1大的边，这个数可以直接跑BM

模拟赛1011 T1

dp方程列出来，然后发现肯定是越往远处扩展越好。

考虑到[i,j]与[i+1,j]不同的地方只有多了[i]...j]

于是变长的那部分只能是与i往右的部分匹配了，否则[i+1，j]也会拓展到它。

双指针即可

模拟赛1011 T2

直接容斥会挂，考虑到把柿子写出来，相当于把Ci->Cj边权为-F[Ci][Cj],于是就是求从超级源到超级汇的路径乘积和了。

容斥不一定要2^n的啊啊啊

模拟赛1013 T1

把(a,b,c)钦定选a，于是变成选择y个(b-a)和z个(c-a)使得和最大。

微扰一下

设(b-a)=e,(c-a)=f

Ei+Fj>Ej>Fi

Ei-Fi>Ej-Fj

按Ei-Fi排序，记录前后缀和，枚举分界点取最大答案即可。

Ohhhhh傻逼题

Complete the MST

显然发现除了一条边填x之外其他都填0

肯定是想办法把0全部加入，x不加

当图比较稠密的时候，暴力枚举x填在哪条边，跑kruscal

O(nsqrt(n))

当图比较稀疏的时候，补图必定有环，环边上的0没有用，随便取一条换成x，最后再跑一遍kruscal。（相当于把0放下来到别的地方了。）

CF1031D Minium Path

模拟赛里做到了这种题。

总结一下套路:分层、BFS，贪心

求网格图中到某点路径字典序最小:

对于每层点，把右边和下面的点加入，这些是下一层可能用到的。

这些点里选最小的那些，所以每层点之间都是相等的

把这些点入队，一直做是N^2的

模拟赛1016 T1

给图分层，枚举前导0（即只通过0边BFS到的点），把最低的前导0加入，每层到下一层的贪心取最小的边（u,v），把v入队。

模拟赛1018 T2

记inv[i]为i前面比i大的个数，不难发现一个inv数组与一个排列一一对应，于是直接用某题做就行了。

模拟赛1020 T2

对每个k，求$ \max(A_i+B_j) (i|j=k)$

k<=2^18

yjj的算法很NB,就是一起一位一位填(i,j,k)，保证i|j==k并且i,j无交集。填满n位之后算a[i]+B[j] (此处B[j]表示B的超集中的k的子集的b的最大值)

在dfs的时传入三个指针(a,b,ans)每次+mid就是移动指针，结束时填到相应位置。当(a+mid,b,ans+mid)时可以加入包含b的数，用它们+mid的位置的b更新超集最大值。

回望过去，当年那场联合省选给我的启示意义太大了

无论如何要看清题面，模拟样例

无论如何要敢于尝试、相信自己的水平

无论如何要善于转化题面，相信一切都是可做的！

如果发现不是很可做，那一定有结论！

最重要的:无论如何，不能畏难！

遥想当年我Day1再次高估难度，降智得连T1都不会，一出考场发现大家都200+，很震惊，很难过。

于是Day2考场上就以为都是傻逼题（虽然这题真是傻逼题），没看清楚题面就开始写，白写了两个小时错题。

这题我想出了2^nnn*m 的做法，还过了大样例，但官方数据挂成了60分（md我2.5h写的和别人0.5h写的分数一样），并且至今不知道错在哪（也许是没开ll？还是边界问题？还是常数太大？）考场代码早就不知道放哪去了，反正至今都是一个大遗憾。

于是，今天，我决定复盘那场完全失败的联合省选！

鉴于D1T1、D1T3、D2T1之前已经复盘过了，而这道满载着遗憾的D2T2还没过，于是决定复盘。

显然打N！暴力的时候发现只要贪心$B_i=B_{i-1}+(A_i-A_{i-1})+(i-1<i)$ 最后$\sum Bi \le M$ 就OK了

于是差分一下

$\sum [(A_i-A_{i-1})+(i-1<i)]*(n-i+1) <= M$

于是这题就做完了，$O(2^N \times N \times N \times M)$

tmd要开ll

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=15,M=505;
int a[N]; 
// \sum max(a_i-1-a_i,0) * (n-i+1)
typedef long long ll;
ll f[1<<N][N][M];
int main(){
	int i,j,k,p,mx=0,mxf;
	cin>>n>>m;
	for(i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i]>mx){
			mx=a[i];
			mxf=i;
		}
	}
	for(i=1;i<=n;i++)
		if(n*(mx-a[i]+(mxf<i))<=m)f[1<<i-1][i][n*(mx-a[i]+(mxf<i))]=1;
	for(i=0;i<(1<<n);i++){
		int cnt=0,o=i;
		while(o)cnt++,o-=o&-o;
		if(cnt<=1)continue;
		for(j=1;j<=n;j++)
			if(i>>j-1&1)
				for(k=1;k<=n;k++)
					if((i^(1<<(j-1)))>>k-1&1){
						int del_cur=(n-cnt+1)*(max(a[k]-a[j]+(k<j),0));
						for(p=del_cur;p<=m;p++)
							f[i][j][p]+=f[i^(1<<(j-1))][k][p-del_cur];
					}
	}
	ll ans=0;
	for(i=1;i<=n;i++)
		for(j=0;j<=m;j++)
			ans+=f[(1<<n)-1][i][j];
	cout<<ans<<endl;
	return 0;
}

马上AFO了集齐九九八十一篇题解说不定能渡劫。。。

看到这题然后不会做，怎么办

合并操作啊

一个巧妙的建模是把操作转换成等腰直角三角形的覆盖。

一开始所有点都是底边为[i-a[i],i+a[i]]的等腰直角三角形。

很显然，当两区间有交的时候合并是优的，没交的时候合并是不优的

于是就做完了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2000005;
int n;
int L,R,top,sl[N],sr[N];
int main(){
	int i;
	cin>>n;
	for(i=1;i<=n;i++){
		int x,l,r;
		scanf("%d",&x);
		if(!x)continue;
		l=i-x,r=i+x;
		if(l>R){
			sl[++top]=L;
			sr[top]=R;
			L=l,R=r;
		}else{
			L=min(L,l),R=max(R,r);
			while(top&&L<=sr[top])
				L=min(L,sl[top--]);
		}
	}
	sl[++top]=L,sr[top]=R;
	int ans=0;
	for(i=1;i<=top;i++)ans+=(sr[i]-sl[i]+1)>>1;
	cout<<ans<<endl;
	return 0;
}

这可能是OI生涯最后的文章了

upd：渡劫失败，但复活了

MOMENT OF BLOSSOM

无向图，数据还那么大，还是异或，答案很显然是在随便一颗生成树上的。

感性理解一下，如果所有操作都集中在一条路径上，那抵销的肯定更多，所以结论是对的。

如果可以，直接暴力跳LCA即可。

否则，异或出来为1的那些路径所组成的连通块（是一片森林），每次选择一条路径删去，最少删几次？

这是个经典问题，ans=奇数点个数/2

code:

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=6e5+5;
int cnt,h[N],nxt[N],to[N],f[N],fa[N],a[N],X[N],Y[N],b[N],dep[N];
void add(int x,int y){
	nxt[++cnt]=h[x];
	h[x]=cnt;
	to[cnt]=y;
}
int gf(int x){
	return x==f[x]?x:f[x]=gf(f[x]);
}
void dfs(int u,int pa){
	int i;
	fa[u]=pa;dep[u]=dep[pa]+1;
	for(i=h[u];i;i=nxt[i]){
		int v=to[i];
		if(v!=pa)dfs(v,u);
	} 
}
int du[N],ans,dao[N],opt;
int cmp(int x,int y){
	return dep[x]<dep[y];
}
int main(){
	cin>>n>>m;
	int i;
	for(i=1;i<=n;i++)f[i]=i;
	for(i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		int fx=gf(x),fy=gf(y);
		if(fx^fy){
			f[fx]=fy;
			add(x,y),add(y,x);
		}
	}
	dfs(1,0);
	int q;cin>>q;
	for(int j=1;j<=q;j++){
		scanf("%d%d",&X[j],&Y[j]);
		for(i=X[j];i;i=fa[i])a[i]^=1;
		for(i=Y[j];i;i=fa[i])a[i]^=1;
	} 
	int tt=0;
	for(i=2;i<=n;i++)tt+=a[i];
	if(tt){
		puts("NO");
		for(i=1;i<=n;i++)du[i]^=a[i],du[fa[i]]^=a[i];
		for(i=1;i<=n;i++)ans+=du[i]&1; 
		cout<<ans/2<<endl;
	}else{
		puts("YES");
		for(int j=1;j<=q;j++){
			int x=X[j],y=Y[j];
			if(dep[x]>dep[y])swap(x,y);
			int p=1,opt=0;
			for(i=1;i<=n;i++)b[i]=0;
			for(i=x;i;i=fa[i])b[i]^=1;
			int LCA=0;
			for(i=y;i;i=fa[i]){
				b[i]^=1;
				if(b[i]==0&&!LCA)LCA=i;
			}
			for(i=x;i!=LCA;i=fa[i])p++;
			for(i=y;i!=LCA;i=fa[i])p++;
			printf("%d\n",p);
			for(i=X[j];i!=LCA;i=fa[i])
				printf("%d ",i);
			printf("%d ",LCA);
			for(i=Y[j];i!=LCA;i=fa[i])dao[++opt]=i;
			for(i=opt;i>=1;i--)
				printf("%d ",dao[i]);
			puts("");
		}
	}
	return 0;
}

SPANNING TREE QUERIES

肉眼可见，答案在很少几段区间内都是等差数列,为什么呢？

因为对于任意的两条边$(i,j)$,当且仅当$2x < A_i+A_j+1 $时，kruscal的时候会先尝试选$i$,否则先选$j$

这样答案就与小于x的边数线性相关，所以是等差数列。

所以称任意$(i,j)$的中点为关键点，只有$m2$个点，可以$m3$暴力算出这几个点的答案。而所有询问的答案一定是以这些答案为首项的等差数列的第几项。

所以对于每个q，它的答案容易通过lowerbound对应的关键点的答案算出来。

注意求的是所有答案的异或和，于是排个序再双指针算就可以做到线性了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005,M=1e7+5;
ll n,m;
struct node{
	ll x,y,z,zz;
}a[N],b[N];
ll cmp(node u,node v){
	if(u.z==v.z)return u.zz>v.zz;
	return u.z<v.z;
}
ll h,c[N],f[N];
ll gf(ll x){
	if(f[x]==x)return x;
	return f[x]=gf(f[x]);
}
ll s[N],ans,q[M],t[N],F[M];
int main(){
	cin>>n>>m;
	int i,j;
	c[++h]=0;
	for(i=1;i<=m;i++){
		scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].z),a[i].zz=a[i].z;
	c[++h]=a[i].z;
	}
	c[++h]=2e9;
	for(i=1;i<=m;i++)
	for(j=1;j<i;j++)
	c[++h]=(a[i].z+a[j].z+1)/2;
	sort(c+1,c+h+1);
	h=unique(c+1,c+h+1)-c-1;
	sort(a+1,a+m+1,cmp);
	for(i=1;i<=h;i++){
		for(j=1;j<=m;j++){
			b[j]=a[j];
			b[j].z=abs(c[i]-b[j].z);
		}
		sort(b+1,b+m+1,cmp);
		for(j=1;j<=n;j++)f[j]=j;
		int	tot=0;
		for(int j=1;j<=m;j++){
			int fx=gf(b[j].x),fy=gf(b[j].y);
			if(fx!=fy){
				f[fx]=fy;
				if(tot<n-1){
					tot++;
					if(b[j].zz<=c[i])s[i]-=b[j].zz,t[i]++;
					if(b[j].zz>c[i])s[i]+=b[j].zz,t[i]--;
				}
			}
		}
	}
	ll pos,k,A,B,C;
	cin>>pos>>k>>A>>B>>C;
	for(i=1;i<=pos;i++)scanf("%lld",&q[i]); 
	for(i=pos+1;i<=k;i++)q[i]=(q[i-1]*A+B)%C;
	sort(q+1,q+k+1);
	ll ans=0;int p=1;
	for(i=1;i<=k;i++){
		while(p<h&&c[p+1]<=q[i])p++;
		ans^=(s[p]+t[p]*q[i]);
	}

	cout<<ans<<endl;
	return 0;
}

CF1632E

mmd怎么现场比赛的2500+每次都不会做

加边肯定是加(1,x),如果二分一个答案A,那dep>A的一定要被影响到

那这些dep[u]=X+dis(u,x)，而dep[u]<=A,所以dis(u,x)<=A-X

总之，要在树上一堆点中找到一个x使得max(dis(u,x))最小。

这是个经典结论，x取直径中点就行了，所以要找到最小的A使得$A-\frac{D+1}{2} >=X$

显然，由于可二分性，不等式左随着A的增大而增大,右随X增大而增大

于是双指针搞定。至于维护直径这事，枚举LCA，显然一定是选最深和次深的链（最早且最长）。

code(Starline):

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 3e5 + 5;
vector <int> adj[N];
int T, n, ans, d[N], mx[N], mx2[N], f[N];
void dfs(int u, int fa) {
	mx[u] = mx2[u] = 0;
	for (auto v : adj[u]) if (v != fa) {
		d[v] = d[u] + 1, dfs(v, u);
		if (mx[v] + 1 > mx[u]) mx2[u] = mx[u], mx[u] = mx[v] + 1;
		else if (mx[v] + 1 > mx2[u]) mx2[u] = mx[v] + 1;
	}
	f[d[u] + mx2[u]] = max(f[d[u] + mx2[u]], mx2[u] + mx[u]);
}
 
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) adj[i].clear();
		fill(f, f + 1 + n, 0);
		for (int i = 1, x, y; i < n; i++)
			scanf("%d%d", &x, &y), adj[x].pb(y), adj[y].pb(x);
		dfs(1, 0);
		for (int i = mx[1] - 1; i >= 0; i--) f[i] = max(f[i + 1], f[i]);
		for (int i = 1, j = 0; i <= n; i++) {
			while (j < mx[1] && (f[j + 1] + 1) / 2 + i > j) j++;
			printf("%d ", j);
		}
		printf("\n");
	}
	return 0;
}

CF1634E&F 题解

E没什么好解的，注意欧拉回路只能搜一个连通块（因为这个我调了n年）看来以后还是要冷静冷静再冷静。

code:

#include<bits/stdc++.h>
using namespace std;
const int M=200005;
int T;
vector<int> g[M<<2];
int tot,cnt[M<<2],a[M<<2],tmp[M<<3],ans[M<<4],top,vis[M<<3];
map<pair<int,int>,int> mp;
vector<int> edge[M<<3],res[M<<3];
vector<int> lac[2][M<<3]; 
void Euler(int u){
	while(1){
		while(tmp[u]<edge[u].size()&&!mp[make_pair(u,edge[u][tmp[u]])])tmp[u]++;
		if(tmp[u]>=edge[u].size())break;
		int v=edge[u][tmp[u]];
		mp[make_pair(u,v)]--;
		mp[make_pair(v,u)]--;
		++tmp[u];
		Euler(v);
	}
	ans[++top]=u;
	vis[u]=1;
}
int main(){
	cin>>T;
	int i,j;
	for(i=1;i<=T;i++){
		int n;
		scanf("%d",&n);
		for(j=1;j<=n;j++){
			int x;
			scanf("%d",&x);
			g[i].push_back(x);
			a[++tot]=x;
		}
	}
	sort(a+1,a+tot+1);
	tot=unique(a+1,a+tot+1)-a-1;
	for(i=1;i<=T;i++){
		for(j=0;j<g[i].size();j++){
			int w=g[i][j];
			g[i][j]=lower_bound(a+1,a+tot+1,w)-a;
			cnt[g[i][j]]++;	
			edge[i].push_back(T+g[i][j]);
			edge[T+g[i][j]].push_back(i);
			mp[make_pair(i,T+g[i][j])]++,mp[make_pair(T+g[i][j],i)]++;
			lac[0][g[i][j]].push_back(i);
			lac[1][g[i][j]].push_back(j); 
		}
	}
	for(i=1;i<=tot;i++){
		if(cnt[i]&1){
			puts("NO");
			return 0;
		}
	}
	puts("YES");
	for(i=1;i<=T+tot;i++)
		sort(edge[i].begin(),edge[i].end());
	for(i=1;i<=T+tot;i++)
		if(!vis[i])Euler(i);
	for(i=top;i>=2;i--)
		if(ans[i]<=T&&ans[i-1]>T)
			res[ans[i-1]-T].push_back(ans[i]);
	for(i=1;i<=tot;i++){
		sort(res[i].begin(),res[i].end());
		int k=0;
		for(j=0;j<lac[0][i].size();j++){
			if(lac[0][i][j]==res[i][k]){
				g[lac[0][i][j]][lac[1][i][j]]=-1; 
				if(k<res[i].size()-1)k++;
				else{break;}
			}
		}
	}
	for(i=1;i<=T;i++){
		for(j=0;j<g[i].size();j++)
			putchar(g[i][j]==-1?'L':'R');
		putchar('\n');
	}
	return 0;
}

F

惊了，原来根本不用ds

设$C_i=A_i-B_i$

$D_i=C_i-C_{i-1}-C_{i-2}$

当且仅当D_i全为0时，答案为YES

考虑加一段对D_i的影响

Dl will increase by 1,

Dr+1 will decrease by Fr−l+2, and

Dr+2 will decrease by Fr−l+1.

Fibonacci addition on B can be handled in a similar way.

看来ds题还是要先想差分

P8118

其实不用左偏树，看一下三倍经验(P4331、P2893)的第一篇题解，发现DP过程可以通过大根堆来优化。这样不仅更好写，而且更加方便后续的min。

读入的时候把Ai -= k*i,就是原题了

然后每次要取个后缀最小值，这个直接做显然T飞（当然我不知道有没有什么高明做法）。于是反过来对每个ai，求取到哪个前缀的时候可以使ai开始小于bi,差分一下就行了。

线段树上二分，直接单log解决

[JRKSJ R4] risrqnis 题解

人在西安，刚下高铁qwq。

暴力算法（sub0）:

离散化，用并查集维护当前值域连续段，新增的一段值域暴力加入这个值对应的下标，树状数组上+1，询问内直接区间求和。

O(nmlogq)

根号分治：

  • 对于连续段数<= sqrt q 的, 离线二维数点，使用O(sqrt)修改，O(1)查询的分块
  • 对于连续段数> sqrt q 的，用暴力算法，将树状数组换成O（1）修改,O(sqrt)查询的分块。

O((n+q)(sqrt n+ sqrt q))

人在西安，刚下高铁qwq。

暴力算法（sub0）:

离散化，用并查集维护当前值域连续段，新增的一段值域暴力加入这个值对应的下标，树状数组上+1，询问内直接区间求和。

O(nmlogq)

根号分治：

  • 对于连续段数<= sqrt q 的, 离线二维数点，使用O(sqrt)修改，O(1)查询的分块
  • 对于连续段数> sqrt q 的，用暴力算法，将树状数组换成O（1）修改,O(sqrt)查询的分块。

O((n+q)(sqrt n+ sqrt q))

其实不用左偏树，看一下三倍经验(P4331、P2893)的第一篇题解，发现DP过程可以通过大根堆来优化。这样不仅更好写，而且更加方便后续的min。

读入的时候把Ai -= k*i,就是原题了

然后每次要取个后缀最小值，这个直接做显然T飞（当然我不知道有没有什么高明做法）。于是反过来对每个ai，求取到哪个前缀的时候可以使ai开始小于bi,差分一下就行了。

线段树上二分，直接单log解决

标签：int,杂题,ll,mx2,sqrt,赛季,ans,初三,mx
From： https://www.cnblogs.com/anticipator/p/17548249.html

相关文章

  • 初三赛季杂题泛做（9-10月）
    CF1580div1A:傻逼题，一开始没想出来，冷静了一会发现可以枚举两行，中间记录个前缀后缀最小值就行了B:考虑dp，设f[n][m][k]为答案，发现枚举最大数的位置可以做，于是就做了N^5tm能过C:想了一会，然后5ab说可以根号分治，我想了想好像真可以，于是就写了。x+y大于sqrtn的直接开大桶算贡献......
  • 7月杂题
    1.CF1835FGoodGraph判定YesorNo等同于判是否存在最大匹配。如果不存在，考虑找到一个不在匹配的左部点，在残量网络上bfs即可。如果存在，考虑tight集合是怎么构成的。如果\(S_i\)表示包含左部点\(i\)的最小tight集合，发现每个tight集合都是一些\(S_i\)的并。考......
  • 计数杂题
    搞一点计数题放在这，看到有意思的计数就更（虽然在组合数学那已经更了好多了）。[CTSC2017]吉夫特给定一个长度为\(n\)的序列\(a\)，保证\(a_i\)互不相同。求出有多少个长度大于等于二的序列满足\[\prod_{i=2}^{k}\binom{a_{b_{i-1}}}{a_{b_i}}\bmod2=\binom{a_{b_1}}{a_{......
  • 22年崇明区初三一模卷
    31.advisetodosth.固定搭配不会48.forgetful单词不会51.没有认真理解题目的意思，看到动词就直接写副词上去53.看到by就用how提问，bytheriver译为在河边，应用where提问54.被动语态不会55.too……to太……而不能句式不会56.直接引语该间接引语不会75.energy不会拼77enco......
  • 2023.7.5 杂题
    CF1174FEhabandtheBigFinale树链剖分。先s1求出\(x\)所在子树\(y\)。若\(y\)为\(1\)轻儿子，递归求解\(y\)。若\(y\)为重儿子，那么找到重链上与\(x\)深度相同的节点\(c\).调用dc，此时\(c\)向上跳\(x\)与\(c\)距离的一半便是\(lca\)，递归求解。相当......
  • 2022年长宁区初三英语一模错题
    18.没有注意过去式-120.需要自己理解后填词，因为没有听懂听力内容所以没有理解意思-221.没有注意元音开头-122.固定搭配：forthetimebeing不知道-125.系表结构不知道-151.没有仔细读题，没搞清楚语境-155.brokendown不知道什么意思-256.被动语态不会-257.不会改间接引语-2......
  • 【杂题乱写】6 月多校分治专题训练
    AGym-101471DMoneyfornothing就是求\((d_j-c_i)(q_j-p_i)\)的最大值。可以看作点对\((d_j,q_j)\)与\((c_i,p_i)\)在二维平面上构成矩形的最大值，且\(c_i\ged_j,p_i\geq_j\)。把卖家点对放在序列\(a\)，买家点对放在序列\(b\)，先删去一定不优的点，删完之后\(a,b\)都......
  • 【杂题乱写】6 月多校分治专题训练
    AGym-101471DMoneyfornothing就是求\((d_j-c_i)(q_j-p_i)\)的最大值。可以看作点对\((d_j,q_j)\)与\((c_i,p_i)\)在二维平面上构成矩形的最大值，且\(c_i\ged_j,p_i\geq_j\)。把卖家点对放在序列\(a\)，买家点对放在序列\(b\)，先删去一定不优的点，删完之后\(a,b\)都......
  • 【杂题乱写】6 月多校分治专题训练
    AGym-101471DMoneyfornothing就是求\((d_j-c_i)(q_j-p_i)\)的最大值。可以看作点对\((d_j,q_j)\)与\((c_i,p_i)\)在二维平面上构成矩形的最大值，且\(c_i\ged_j,p_i\geq_j\)。把卖家点对放在序列\(a\)，买家点对放在序列\(b\)，先删去一定不优的点，删完之后\(a,b\)都......
  • 7月CF杂题
    怎么七月了？六月的只写了一道题捏。EducationalCodeforcesRound151(RatedforDiv.2)俺寻思能行。D.RatingSystem为什么大家都切那么快捏。显然\(k\)一定是\(a\)数组的一个前缀和。假设\(k=\sum\limits_{i=1}^xa_i\)，剩下的等价于处理初值为0且\(k=0\)的子问......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99