首页 > 其他分享 >AtCoder Beginner Contest 374

AtCoder Beginner Contest 374

时间：2024-10-07 15:34:59浏览次数：8  
标签：AtCoder Beginner 10 int iut ans include 374 getchar

ABC374 A - Takahashi san 2

题目传送门

代码（签到题）

#include <cstdio>
#include <cctype>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
int iut(){
	int ans=0,f=1; char c=getchar();
	while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans*f;
}
void print(int ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
}
int main(){
	char s[111]; int len;
	scanf("%s",s+1),len=strlen(s+1);
	if (s[len-2]=='s'&&s[len-1]=='a'&&s[len]=='n'){
		printf("Yes");
	}else printf("No");
	return 0;
}

ABC374 B - Unvarnished Report

题目传送门

代码（签到题）

#include <cstdio>
#include <cctype>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
char s[111],t[111]; int n,m;
int iut(){
	int ans=0,f=1; char c=getchar();
	while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans*f;
}
void print(int ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
}
int main(){
	scanf("%s",s+1),n=strlen(s+1);
	scanf("%s",t+1),m=strlen(t+1);
	for (int i=1;i<=n||i<=m;++i)
	if (s[i]!=t[i]){
		return !printf("%d",i);
	} 
	return !printf("0");
}

ABC374 C - Separated Lunch

题目传送门

代码（签到题）

#include <cstdio>
#include <cctype>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,a[111],ans,sum;
int iut(){
	int ans=0,f=1; char c=getchar();
	while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans*f;
}
void print(int ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
}
int main(){
	n=iut();
	for (int i=0;i<n;++i) a[i]=iut(),sum+=a[i];
	ans=sum;
	for (int i=2;i<(1<<n);i+=2){
		int now=0;
		for (int j=0;j<n;++j)
		    if ((i>>j)&1) now+=a[j];
		ans=min(ans,max(now,sum-now));
	}
	return !printf("%d",ans);
}

ABC374 D - Laser Marking

题目传送门

代码（签到题）

#include <cstdio>
#include <cctype>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
const int N=111; double ans=1e18;
int n,v1,v2,x[N][2],y[N][2],rk[N];
int iut(){
	int ans=0,f=1; char c=getchar();
	while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans*f;
}
void print(int ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
}
double o(int lx,int ly,int rx,int ry){return sqrt((rx-lx)*(rx-lx)+(ry-ly)*(ry-ly));}
int main(){
	n=iut(),v1=iut(),v2=iut();
	for (int i=1;i<=n;++i){
		x[i][0]=iut(),y[i][0]=iut();
		x[i][1]=iut(),y[i][1]=iut();
		rk[i]=i;
	}
	do{
		for (int i=0;i<(1<<n);++i){
			int lstx=0,lsty=0; double now=0;
			for (int j=1;j<=n;++j){
				int z=(i>>(j-1))&1;
				now+=o(lstx,lsty,x[rk[j]][z],y[rk[j]][z])/v1;
				lstx=x[rk[j]][z^1],lsty=y[rk[j]][z^1];
				now+=o(lstx,lsty,x[rk[j]][z],y[rk[j]][z])/v2;
			}
			ans=min(ans,now);
		}
	}while (next_permutation(rk+1,rk+1+n));
    printf("%.12lf",ans);
}

ABC374 E - Sensor Optimization Dilemma 2

题目传送门

分析

二分答案，这样就变成每种机器有最低产量限制，且让总费用最小，而单个最小值的枚举机器个数是在 \(\max\{a_i,b_i\}\) 范围内的，考场写了假的三分故意扩大 eps 然后过了

代码

#include <cstdio>
#include <cctype>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
const int N=111;
typedef long long lll;
int w[N][2],c[N][2],n,X;
int iut(){
	int ans=0,f=1; char c=getchar();
	while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans*f;
}
void print(int ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
}
lll calc(lll j,int i,int mid){
	if (mid>j*c[i][0]) return j*w[i][0]+(mid-j*c[i][0]+c[i][1]-1)/c[i][1]*w[i][1];
	    else return j*w[i][0];
}
bool check(int mid){
	lll sum=0;
	for (int i=1;i<=n;++i){
		lll now=1e18,lim=(mid+c[i][0]-1)/c[i][0];
		for (int j=0;j<=c[i][1];++j) now=min(now,calc(j,i,mid));
		for (int j=lim;j>=lim-c[i][0]&&j>=0;--j) now=min(now,calc(j,i,mid));
		sum+=now;
		if (sum>X) return 0;
	}
	return 1;
}
int main(){
	n=iut(),X=iut();
	for (int i=1;i<=n;++i){
		c[i][0]=iut(),w[i][0]=iut();
		c[i][1]=iut(),w[i][1]=iut();
		if (c[i][0]<c[i][1]) swap(c[i][0],c[i][1]),swap(w[i][0],w[i][1]);
	}
	int l=0,r=0x3f3f3f3f;
	while (l<r){
		int mid=(l+r+1)>>1;
		if (check(mid)) l=mid;
		    else r=mid-1;
	}
	return !printf("%d",l);
}

ABC374 F - Shipping

题目传送门

分析

本题动态规划一定要利用时刻，而有效的时刻就是 \(T_i+kX\) 共 \(O(n^2)\) 个。

设 \(dp[i][j]\) 表示时刻 \(i\) 或以前已经让前 \(j\) 艘船通过的最小值，直接 \(O(n^3k)\) 即可

代码

#include <cstdio>
#include <cctype>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
const int N=111;
typedef long long lll;
lll n,m,k,X,a[N],dp[N*N][N],b[N*N];
lll iut(){
	lll ans=0,f=1; char c=getchar();
	while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans*f;
}
int main(){
	n=iut(),k=iut(),X=iut();
	for (int i=1;i<=n;++i){
		a[i]=iut();
		for (int j=0;j<n;++j) b[++m]=a[i]+j*X;
	}
	sort(b+1,b+1+m),m=unique(b+1,b+1+m)-b-1;
	for (int i=0;i<=m;++i)
	for (int j=0;j<=n;++j) dp[i][j]=1e18;
	dp[0][0]=0,b[0]=-X;
	for (int i=1,I=0;i<=m;++i){
		while (I<=m&&b[I]+X<=b[i]) ++I; --I;
		for (int j=0;j<=n;++j){
			if (b[i]<a[j]) break;
			dp[i][j]=dp[i-1][j];
			lll sum=0;
			for (int o=0;o<=k&&o<=j;++o)
			    dp[i][j]=min(dp[i][j],dp[I][j-o]+sum),sum+=b[i]-a[j-o];
		}
	}
	return !printf("%lld",dp[m][n]);
}

ABC374 G - Only One Product Name

题目传送门

分析

最多有 \(26^2\) 个点的有向图，求最小可相交路径覆盖，由于可相交，不妨先将该有向图缩点成 DAG，

在新图传递闭包，答案为新图点数减去最大匹配数

代码

#include <iostream>
#include <string>
#include <stack>
#include <bitset>
using namespace std;
const int N=911; bitset<N>a[N]; string str[N];
struct node{int y,next;}e[N*N]; stack<int>st;
int dfn[N],low[N],v[N],col[N],tot,cnt,n,upd,link[N],et=1,ans,as[N];
void tarjan(int x){
	dfn[x]=low[x]=++tot,v[x]=1,st.push(x);
	for (int i=as[x];i;i=e[i].next)
	if (!dfn[e[i].y]){
		tarjan(e[i].y);
		low[x]=min(low[x],low[e[i].y]);
	}else if (v[e[i].y]) low[x]=min(low[x],dfn[e[i].y]);
	if (dfn[x]==low[x]){
		int y; ++cnt;
		do{
			y=st.top(); st.pop();
			col[y]=cnt,v[y]=0;
		}while (y!=x);
	}
}
bool match(int x){
	for (int y=1;y<=cnt;++y)
	if (a[x][y]&&v[y]!=upd){
		v[y]=upd;
		int q=link[y];
		link[y]=x;
		if (!q||match(q)) return 1;
		link[y]=q;
	}
	return 0;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for (int i=1;i<=n;++i) cin>>str[i];
	for (int i=1;i<=n;++i)
	for (int j=1;j<=n;++j)
	if (str[j][0]==str[i][1]){
		e[++et]=(node){j,as[i]},as[i]=et;
	}
	for (int i=1;i<=n;++i) if (!dfn[i]) tarjan(i);
	for (int i=1;i<=n;++i)
	for (int j=as[i];j;j=e[j].next)
	    if (col[i]!=col[e[j].y]) a[col[i]][col[e[j].y]]=1;
	for (int k=1;k<=cnt;++k)
	for (int i=1;i<=cnt;++i)
	    if (a[i][k]) a[i]|=a[k];
	for (int i=1;i<=cnt;++i){
		++upd;
		if (match(i)) ++ans;
	}
	cout<<cnt-ans;
	return 0;
}

标签：AtCoder,Beginner,10,int,iut,ans,include,374,getchar
From： https://www.cnblogs.com/Spare-No-Effort/p/18450149

相关文章

  • 题解：AT_abc374_c [ABC374C] Separated Lunch
    无耻的广告更好的阅读体验~最近在搞个人博客博客园的差点忘了更了。已经沦落到在写这种水题题解了。题目翻译有\(n\)队人，每个队人数不同，把他们分成2组（同一队的不能拆开），使两组人数差距尽量小。形式化题意：有\(n\)个数，把它们分成两组，使两组和的差尽量小。说句闲话：感觉这......
  • ABC374 E 题解
    ABC374E题解E-SensorOptimizationDilemma2题目链接：AT|洛谷容易发现答案可以二分。于是我们把问题转化为了判定性问题：给定目标\(x\)，能否在花费不超过预算的情况下，使得每个过程的产量都不低于\(x\)？进一步，由于各个过程的生产互不相关，所以我们要尽可能让每个过程的费......
  • [题解]ABC374 A~E
    A-Takahashisan2直接判断字符串是否以san结尾即可。点击查看代码#include<bits/stdc++.h>usingnamespacestd;intmain(){ strings; cin>>s; intn=s.size(); if(s[n-1]=='n'&&s[n-2]=='a'&&s[n-3]=='s')cout<<&......
  • ABC374E 题解
    好题。爱做。标签：二分。求最大的最小值，考虑二分答案。然后问题就转化成了（求\(n\)次）：有两种物品，每种物品有一个代价和价值，求获得不少于给定价值所需的最小代价。下文记物品的代价为\(w\)，价值为\(v\)，所拿的数量为\(cnt\)。假设有两种物品\(S\)与\(T\)，\(S\)物品的性价比......
  • 题解：AT_abc374_d [ABC374D] Laser Marking
    看到\(n\le6\)，就知道这道题又是一道搜索了。题面有点长，信息也给的有点多，但稍微分析就可以得到只需要搜索印刷线段的顺序即可。具体的，我们在深搜函数里面传\(4\)个参数，分别代表已选线段的数量，当前位置的横纵坐标，以及当前时间。为了方便，我们表示的是已经印刷完当前线段后的时间......
  • AtCoder Beginner Contest 374
    省流版A.判断末三位即可B.逐位判断即可C.枚举所有分组情况即可D.枚举线段顺序、端点顺序即可E.二分答案，发现贵的机器数量不超过\(100\)，枚举求最小花费看是否可行即可F.朴素DP，复杂度分析得到有效时刻不超过\(O(n^2)\)而非\(O(s_i)\)，直接\(DP\)即可A-Takahashi......
  • 2023-12-15 博士挑战--落幕 123744
    目录总纲现状反思未来总纲宇宙万物、世间一切自有因果。自助者天助，然若不自助，神明亦爱莫能助。人的好坏定义并非从言行举止来衡量，而是有无执着。现状老师不再执着于己见--要求他的所有学生都成为有声望的学者。我目前一切都好，正在做想做的理论方向且成就感满满，工资上涨，......
  • AtCoder Beginner Contest 373
    省流版A.暴力即可B.求出字母位置，绝对值相加即可C.显然答案为两个数组的最大值的和D.注意直接BFS的点权范围不超过题目范围，直接BFS即可E.发现单调性，二分票数，用前缀和\(O(1)\)判断可行性即可F.朴素背包DP，相同重量的物品一起考虑，用优先队列求解\(l\)个相同重量物品最大......
  • Solution - Atcoder ARC157E XXYX Binary Tree
    考虑这个不存在\(\texttt{YY}\)的限制，与\(\texttt{XX}\)个数为变量的限制相比较，看起来\(\texttt{Y}\)就更特殊，于是考虑从\(\texttt{Y}\)的视角来分析问题。同时考虑到因为有\(A+B+C=n-1\)，所以\(\texttt{XX}\)其实也不是很重要，因为只需要让\(\texttt{XY}\)和......
  • Solution - Atcoder ARC157D YY Garden
    考虑到因为有横轴数轴两部分的限制，不妨先固定下来一部分的限制再处理另一部分。对于这题来说横轴竖轴本质是相同的，于是不妨考虑固定横轴。如果知道了横轴的分割，那么对于竖轴上就可以根据分割情况知道合法的分割了。即考虑记\(f_i\)为考虑了竖轴的前\(i\)列，第\(i\)列为最......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99