首页 > 其他分享 >十月初 AT/CF

十月初 AT/CF

时间：2024-10-10 14:48:01浏览次数：1  
标签：const int sum CF long son LL 十月初

ABC374 E

最大最小值，想到二分，问题是怎么 check。

其实就是对两个种有价值有重量的物品，求达到规定价值的最小重量。

只有两种物品，而且数据范围很小，考虑贪心。

假设 \(a\) 的性价比较高，\(b\) 的性价比较低，那么不可能选太多 \(b\)。

也就是如果能用 \(a\) 代替的就用 \(a\) 代替。所以选 \(b\) 的总价值不能超过 \(lcm(a,b)\)。否则能用 \(a\) 替换更优。

发现 \(a\) 最大只有 \(100\)，所以 \(b\) 最多选 \(100\) 个。暴力枚举。

code 
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 105;
int n; LL X;
int a[N],b[N],p[N],q[N];

bool check(int w)
{
	LL sum=0;
	for(int i=1;i<=n;i++)
	{
		LL tmp=1e18;
		for(int j=0;j<=100;j++)
		{
			int k=ceil((1.0*w-j*b[i])/a[i]); k=max(k,0);
			tmp=min(tmp,1ll*k*p[i]+1ll*j*q[i]);
			if(j*b[i]>w) break;
		}
		sum+=tmp;
	}
	return sum<=X;
}
int main()
{
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	scanf("%d%lld",&n,&X);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d%d",&a[i],&p[i],&b[i],&q[i]);
		if(a[i]*q[i]<b[i]*p[i]) swap(q[i],p[i]),swap(a[i],b[i]);
	}
	int l=0,r=1e9+7,ans=0;
	while(l<=r)
	{
		int mid=(1ll*r-l>>1)+l;
		if(check(mid)) ans=mid,l=mid+1;
		else r=mid-1;
	}
	printf("%d\n",ans);
	return 0;
}

CF997 C2

有点难调。

容易发现是否合法只与 \(a\) 的元素在 \(b\) 中第一次出现的位置有关。

对于 \(a\) 序列来说，在 \(b\) 中的第一次出现的位置应该是单调递增的。

所以直接用 set 维护位置，每次更新就行。（不需要特殊处理第一个位置）

code 
#include<bits/stdc++.h>
using namespace std;
#define LL long long
int T;
const int N = 2e5+5;
int n,m,q;
int a[N],b[N],ys[N];
set<int> p[N];
int main()
{
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d",&n,&m,&q);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]),p[a[i]].clear(),p[a[i]].insert(m+1),ys[a[i]]=i;
		for(int i=1;i<=m;i++)
		{
			scanf("%d",&b[i]);
		}
		for(int i=1;i<=m;i++)
		{
			p[b[i]].insert(i);
		}
		int res=0;
		for(int i=2;i<=n;i++) if(*p[a[i]].begin()<*p[a[i-1]].begin())
			res++;
		if(!res) printf("YA\n");
		else printf("TIDAK\n");
		while(q--)
		{
			int x,y; scanf("%d%d",&x,&y);
			if(ys[b[x]]-1>=1&&*p[b[x]].begin()<*p[a[ys[b[x]]-1]].begin())
				res--;
			if(ys[b[x]]+1<=n&&*p[a[ys[b[x]]+1]].begin()<*p[b[x]].begin())
				res--;
			p[b[x]].erase(x);
			if(ys[b[x]]-1>=1&&*p[b[x]].begin()<*p[a[ys[b[x]]-1]].begin())
				res++;
			if(ys[b[x]]+1<=n&&*p[a[ys[b[x]]+1]].begin()<*p[b[x]].begin())
				res++;
			if(ys[y]-1>=1&&*p[y].begin()<*p[a[ys[y]-1]].begin())
				res--;
			if(ys[y]+1<=n&&*p[a[ys[y]+1]].begin()<*p[y].begin())
				res--;
			p[y].insert(x);
			if(ys[y]-1>=1&&*p[y].begin()<*p[a[ys[y]-1]].begin())
				res++;
			if(ys[y]+1<=n&&*p[a[ys[y]+1]].begin()<*p[y].begin())
				res++;
			b[x]=y;
			if(res==0) printf("YA\n");
			else printf("TIDAK\n");				
		}
	}
}

CF997 E1

出题人贴心地给出了 \(n^3\) 的范围。直接考虑 floyd。

跑完最短路后暴力枚举选的点就好，仍然是 \(n^3\) 暴力。

code 
#include<bits/stdc++.h>
using namespace std;
#define LL long long
int T;
const int N = 405;
int n,m,q;
int f[N][N],a[N],now[N],ttt[N];
LL sum;
bool vs[N];
int main()
{
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	scanf("%d",&T);
	while(T--)
	{
		sum=0;
		scanf("%d%d%d",&n,&m,&q);
		memset(vs,0,sizeof(vs));
		memset(f,0x3f,sizeof(f));
		for(int i=1;i<=q;i++) scanf("%d",&a[i]);
		for(int i=1;i<=m;i++)
		{
			int x,y,z; scanf("%d%d%d",&x,&y,&z);
			f[x][y]=f[y][x]=z;
		}
		for(int i=1;i<=n;i++) f[i][i]=0;
		for(int k=1;k<=n;k++)
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					f[i][j]=min(f[i][j],max(f[i][k],f[k][j]));
		int fl=0;
		sum=1e18;
		for(int i=1;i<=n;i++)
		{
			LL tmp=0;
			for(int j=1;j<=q;j++) tmp+=f[i][a[j]];
			if(sum>tmp)
			{
				for(int j=1;j<=q;j++) now[j]=f[i][a[j]];
				sum=tmp; fl=i;
			}
		}
		vs[fl]=1;
		printf("%lld ",sum);
		for(int i=2;i<=n;i++)
		{
			if(i>=q) {printf("0 "); continue;}
			fl=0;
			for(int j=1;j<=q;j++) ttt[j]=now[j];
			for(int j=1;j<=n;j++) if(!vs[j])
			{
				LL tmp=0;
				for(int k=1;k<=q;k++) tmp+=min(f[j][a[k]],now[k]);
				if(tmp<sum)
				{
					for(int k=1;k<=q;k++) ttt[k]=min(f[j][a[k]],now[k]);
					sum=tmp; fl=j;
				}
			}
			for(int j=1;j<=q;j++) now[j]=ttt[j];
			vs[fl]=1; printf("%lld ",sum);
		}
		putchar('\n');
	}
}

CF997 E2

要求 \(n^2\) 的复杂度，发现问题是求路径上最大边权的最小值。考虑Kruskal 生成树。

其实这个生成的是一个堆，将边权转化为点权，保证父亲的权值不小于儿子。

因此我们将问题转化为了树上问题，设计状态 \(f_{u,i}\) 表示以 \(u\) 为根的子树内有 \(i\) 个 servers。

从下向上更新，由于越往上权值越大，说明需要连接的最大边越大，所以需要连接的点一定尽量连深的点。

如果是 \(f_{son,0}\)，说明儿子这棵子树内没有 servers，那么如果以 \(u\) 根这棵子树内有servers（\(f_{u,1/2/3\dots}\)）,那么一定连这个更优。

此时最大边就是 \(va_u\)（根节点的权值），用子树内需要连接的点的个数（\(cnt_{son}\)） 乘上最大边就行。

如果以儿子为根的子树内已经有了，那直接相加更新就好。（\(f_{u,i+j}=\sum_i\sum_j f_{son_1,i}+f_{son_2,j}\)）

然后你发现重构树会使点数翻倍，空间直接炸。

小 trick，发现最终答案只关心根 \(f_{1,i}\)，所以 dp 数组用 vector，每更新完一个就返还空间，shrink_to_fit。

code 
#include<bits/stdc++.h>
using namespace std;
int T;
#define LL long long
const int N = 1e4+5;
const LL inf = 1e15;
int n,m,q;
int num;
struct E {int u,v,w;} ed[N];
int fa[N],son[N][2],va[N],cnt[N];
inline int find(int x) {return x==fa[x]?(x):(fa[x]=find(fa[x]));}
vector<LL> f[N];
void dfs(int u)
{
	if(!son[u][0]&&!son[u][1]) return ;
	dfs(son[u][0]); dfs(son[u][1]);
	f[u].resize(cnt[u]+1,inf);
	for(int i=1;i<=cnt[son[u][1]];i++) f[u][i]=min(f[u][i],1ll*va[u]*cnt[son[u][0]]+f[son[u][1]][i]);
	for(int i=1;i<=cnt[son[u][0]];i++) f[u][i]=min(f[u][i],1ll*va[u]*cnt[son[u][1]]+f[son[u][0]][i]);
	for(int i=1;i<=cnt[son[u][0]];i++)
		for(int j=1;j<=cnt[son[u][1]];j++)
			f[u][i+j]=min(f[u][i+j],f[son[u][0]][i]+f[son[u][1]][j]);
	f[son[u][0]].clear(); f[son[u][0]].shrink_to_fit();
	f[son[u][1]].clear(); f[son[u][1]].shrink_to_fit();
}

int main()
{
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d",&n,&m,&q);
		for(int i=1;i<=n<<1;i++)
		{
			f[i].clear(); f[i].resize(1,inf);
			cnt[i]=0; fa[i]=i; son[i][0]=son[i][1]=0;
		}
		for(int i=1,x;i<=q;i++) scanf("%d",&x),cnt[x]=1,f[x].resize(2,inf),f[x][1]=0;
		for(int i=1;i<=m;i++)
			scanf("%d%d%d",&ed[i].u,&ed[i].v,&ed[i].w);
		num=n;
		sort(ed+1,ed+1+m,[&](E &x,E &y){return x.w<y.w;});
		for(int i=1;i<=m;i++)
		{
			int fx=find(ed[i].u),fy=find(ed[i].v);
			if(fx==fy) continue;
			fa[fx]=fa[fy]=++num; va[num]=ed[i].w; 
			son[num][0]=fx; son[num][1]=fy; cnt[num]=cnt[fx]+cnt[fy];
		}
		dfs(num);
		for(int i=1;i<=q-1;i++) printf("%lld ",f[num][i]);
		for(int i=q;i<=n;i++) printf("0 ");
		putchar('\n');

	}
	return 0;
}

ABC374F

思路来自 int_R

假设物品发出时间是 \(s_i\)，需求时间是 \(t_i\)，那么答案就是 \(\sum s - \sum t\)，发现后面是定值，可以直接处理。

我们要确定的就是所有物品发出时间的总和。

在能出发的时刻，要不然立即出发，要不然等下一个时刻出发，所以出发时间一定是 \(t_i+kx\)，也就是从某一个 \(t_i\) 开始后连续发送几次 \(x\)，然后等待。

设计状态 \(f_{i,j}\) 表示在 \(t_i\)，第 \(i\) 个物品的状态从即将出发到已经到达，此时还有 \(j\) 个物品没有出发（被跳过去了）。

转移即枚举这次运输会连续几个 \(x\)，注意细节。

马蜂抽象。

code 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 105,inf = 1e15;
int n,k,x,t[N],f[N][N],ans;

main()
{
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
	scanf("%lld%lld%lld",&n,&k,&x);
	memset(f,0x3f,sizeof(f)); f[0][0]=0;
	for(int i=1;i<=n;i++) scanf("%lld",&t[i]),ans-=t[i];
	for(int i=1;i<=n;i++)//第 i-1 个到了，第 i 个将要发出时，还有 j 个没发出
	{
		for(int j=0;j<i;j++) f[i][j]=min(f[i-1][j],f[i][j]);
		for(int j=i;j>=1;j--) f[i][j]=f[i][j-1]; f[i][0]=inf;//第 i 个没发出，要加上。
		for(int j=1;j<=i;j++)
		{
			int now=j,tm=t[i],sum=0,h=i+1;
			while(now)
			{
				int cur=min(now,k);
				sum+=cur*tm; now-=cur; tm+=x;//发第 i 个。
				for(;h<=n&&t[h]<tm;h++) now++;
				f[h][now]=min(f[h][now],f[i][j]+sum);//第 i 个发完，该第 h 个了。
			}
		}
	}
	printf("%lld\n",ans+f[n+1][0]);

	return 0;
}

标签：const,int,sum,CF,long,son,LL,十月初
From： https://www.cnblogs.com/ppllxx-9G/p/18450395

相关文章

  • Day3 备战CCF-CSP练习
    Day3题目描述目前在一个很大的平面房间里有\(n\)个无线路由器，每个无线路由器都固定在某个点上。任何两个无线路由器只要距离不超过\(r\)就能互相建立网络连接。除此以外，另有\(m\)个可以摆放无线路由器的位置。你可以在这些位置中选择至多\(k\)个增设新的路由器。你的......
  • 题解：CF1007D Ants
    题目传送门每只蚂蚁只走一对点肯定是不劣的，由此想到2-sat。限制条件是：若\((a,b)\)和\((c,d)\)两条链相交，则不能同时选。直接建图肯定是爆炸的。用树剖可以将\((a,b)\)这条链划分成\(O(\logn)\)个区间。因为同一条链的区间不交，限制条件变为若两个区间相交，则这两个点不......
  • 使用C#和WCF创建并托管简单服务的指南
    在C#中，实现WindowsCommunicationFoundation(WCF)功能通常涉及几个关键步骤，包括定义服务契约、实现服务、配置服务以及托管服务。下面是一个简单的示例，展示如何使用C#和WCF来创建一个简单的服务。步骤1:创建服务契约首先，我们需要定义一个服务契约，这通常是通过接口来......
  • cf2009 Codeforces Round 971 (Div. 4)
    A.Minimize!签到题。计算\((c-a)+(b-c)\)的最小值，其实值固定的，等于\(b-a\)。inta,b;voidsolve(){cin>>a>>b;cout<<b-a<<endl;}B.Osu!mania签到题。给定一个4k下落式的网格，求#下落顺序。直接数组记录就好了。intn;constintN=500;chars[......
  • GCC编译器CFLAGS、LDFLAGS详解
    目录CFLAGSLDFLAGS在编译C/C++程序时，可以使用CFLAGS和LDFLAGS环境变量来设置编译器和链接器的选项。下面对CFLAGS和LDFLAGS进行详解：CFLAGSCFLAGS是用于设置C/C++编译器选项的环境变量。它可以用来指定编译过程中的各种选项，如优化级别、警告级别、头文件包含路......
  • Day2 备战CCF-CSP练习
    Day2题目描述请你写一个命令行分析程序，用以分析给定的命令行里包含哪些选项。每个命令行由若干个字符串组成，它们之间恰好由一个空格分隔。这些字符串中的第一个为该命令行工具的名字，由小写字母组成，你的程序不用对它进行处理。在工具名字之后可能会包含若干选项，然后可能会包含......
  • CCF--GESP复习资料（1级）
    CCF--GESP复习资料第一部分：计算机基础与编程环境计算机硬件主要由五大部分组成：运算器、储存器、控制器、输入设备、输出设备。第二部分：计算机历史计算机的诞生（1950年至今）1950年以后出现的计算机都差不多基于冯·诺依曼模型，它们变得更快、更小、更便宜，但原理几乎是相同的。......
  • CF1406E Deleting Numbers
    题意简述交互题，给定集合\(S=\{1,2,\cdots,n\}\)和一个隐藏的数\(m\)，你需要使用不超过\(10^4\)次操作猜出\(m\)，操作类型如下：Ax，查询在\(S\)中是\(x\)的倍数的数的个数。Bx，查询在\(S\)中是\(x\)的倍数的数的个数，并把这些数删去，但是\(m\)不会被删去。Cx，表示你......
  • CF2021D Boss, Thirsty
    原题链接原来就是直接做啊。记\(s_{i,j}=\sum\limits_{k\leqj}a_{i,k}\)，设\(f_{i,x,y}\)表示第\(i\)行选区间\([x,y]\)的最大答案，有转移：\[f_{i,x,y}=s_{i,y}-s_{i,x-1}+\max(\max\limits_{x<l\leqy,r\geql}f_{i-1,l,r},\max\limits_{x\leqr<y,l\leqr}f_{i-1......
  • Day1 备战CCF-CSP练习
    Day1201403-1问题描述有$N$个非零且各不相同的整数。请你编一个程序求出它们中有多少对相反数($a$和$-a$为一对相反数)。输入格式第一行包含一个正整数$N$。$(1≤N≤500)$。第二行为$N$个用单个空格隔开的非零整数,每个数的绝对值不超过$1000$,保证这些整数各......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99