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

AtCoder Beginner Contest 373

时间：2024-10-07 21:26:44浏览次数：9  
标签：AtCoder Beginner int namespace ans using 373 include ABC373

ABC373 A - September

题目传送门

代码（签到题）

#include <cstdio>
#include <cstring>
using namespace std;
char s[1111];
int ans;
int main(){
    for (int i=1;i<=12;++i){
        scanf("%s",s+1);
        if (strlen(s+1)==i) ++ans;
    }
    printf("%d",ans);
    return 0;
}

ABC373 B - 1D Keyboard

题目传送门

代码（签到题）

#include <cstdio>
#include <cstring>
using namespace std;
char s[1111];
int ans,lst,pos[11111];
int Abs(int x){return x<0?-x:x;}
int main(){
    scanf("%s",s+1);
    for (int i=1;i<=26;++i){
        pos[s[i]-64]=i;
    }
    for (int i=2;i<=26;++i){
        ans+=Abs(pos[i]-pos[i-1]);
    }
    printf("%d",ans);
    return 0;
}

ABC373 C - Max Ai+Bj

题目传送门

代码（签到题）

#include <iostream>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,mx1=-2e9,mx2=-2e9;
    cin>>n;
    for (int i=1,x;i<=n;++i) cin>>x,mx1=max(mx1,x);
    for (int i=1,x;i<=n;++i) cin>>x,mx2=max(mx2,x);
    cout<<mx1+mx2;
    return 0;
}

ABC373 D - Hidden Weights

题目传送门

分析

对于所有弱连通分支，任取一种生成树令根节点点权为 \(0\)，

按照边的要求扩展，最后每条边都判断是否满足有向的要求

代码

#include <iostream>
using namespace std;
const int N=200011;
struct node{int y,w,next;}e[N<<1];
int v[N],as[N],n,m,et=1; long long dis[N];
void dfs(int x){
    v[x]=1;
    for (int i=as[x];i;i=e[i].next)
    if (!v[e[i].y]){
        if (i&1) dis[e[i].y]=dis[x]-e[i].w;
            else dis[e[i].y]=dis[x]+e[i].w;
        dfs(e[i].y);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=m;++i){
        int x,y,w; cin>>x>>y>>w;
        e[++et]=(node){y,w,as[x]},as[x]=et;
        e[++et]=(node){x,w,as[y]},as[y]=et;
    }
    for (int i=1;i<=n;++i) if (!v[i]) dfs(i);
    for (int i=1;i<=n;++i) cout<<dis[i]<<' ';
    return 0;
}

ABC373 E - How to Win the Election

题目传送门

分析

二分答案，不然很难弄，二分答案之后就能定下某个人的得票数，如果原本这个人就是前 \(m\) 名，就要保证前 \(m+1\) 名其他人即使用了其它票都无法都比它高；

如果不是就是保证前 \(m\) 名，找出本来就比新票数还要高的人，剩下的人尝试都凑到得票数加一。

代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N=200011;
typedef long long lll;
lll a[N],k,s[N],b[N]; int n,m,rk[N],Rk[N];
bool cmp(int x,int y){return a[x]>a[y];}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    for (int i=1;i<=n;++i) cin>>a[i],rk[i]=i,k-=a[i];
    if (n==m){
        for (int i=1;i<=n;++i) cout<<"0 ";
        return 0;
    }
    sort(rk+1,rk+1+n,cmp);
    for (int i=1;i<=n;++i) s[i]=s[i-1]+a[rk[i]],b[i]=a[rk[n-i+1]],Rk[rk[i]]=i;
    for (int i=1;i<=n;++i){
        lll l=0,r=k+1;
        while (l<r){
            lll mid=(l+r)>>1;
            int pos=upper_bound(b+1,b+1+n,a[i]+mid)-b;
            if (pos<=n-m+1) l=mid+1;
            else{
                pos=n-pos+1;
                if (Rk[i]<=m){
                    if (k-mid<(a[i]+mid+1)*(m-pos)-(s[m+1]-s[pos]-a[i])) r=mid;
                        else l=mid+1;
                }else{
                    if (k-mid<(a[i]+mid+1)*(m-pos)-(s[m]-s[pos])) r=mid;
                        else l=mid+1;
                }
            }
        }
        if (l==k+1) cout<<-1<<' ';
            else cout<<l<<' ';
    }
    return 0;
}

ABC373 F - Knapsack with Diminishing Values

题目传送门

分析

非常好的背包，让我的大脑旋转，对于同体积的物品，由于价值与选择个数有关，不妨使用堆维护 \(\Delta k_iv_i-k_i^2\)，每次选择最大的。

那么对于一个体积能够提供它与它倍数的新物品，一共有 \(W\log W\) 个，用这些新物品做完全背包即可，要注意出自原体积的物品继承的dp数组要来自上一体积而不是上一物品。

代码

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int N=3011;
typedef long long lll;
struct rec{
    lll delta,w,cnt;
    bool operator <(const rec &t)const{
        return delta>t.delta;
    }
};
lll n,m,f[N],g[N],dp[N]; multiset<rec>K[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;++i){
        lll w,v; cin>>w>>v;
        K[w].insert((rec){v-1,v,1});
    }
    for (int i=1;i<=m;++i)
    if (!K[i].empty()){
        for (int j=0;j<=m;++j) f[j]=dp[j];
        for (int j=i;j<=m;j+=i){
            rec t=*K[i].begin();
            if (t.delta<0) break;
            K[i].erase(K[i].begin());
            g[j]=g[j-i]+t.delta;
            t.delta=t.w-1-2*(t.cnt++);
            K[i].insert(t);
            for (int k=m;k>=j;--k)
                dp[k]=max(dp[k],f[k-j]+g[j]);
        }
    }
    cout<<dp[m];
    return 0;
}

ABC373 G - No Cross Matching

题目传送门

分析

KM 或者费用流，原题来自 UVA1411 Ants

代码

#include <cstdio>
#include <cctype>
#include <cmath>
#include <queue>
using namespace std;
const int N=311; bool vx[N],vy[N];
typedef double db; queue<int>q;
db slack[N],lx[N],ly[N],G[N][N];
int px[N],py[N],link[N],n,x[N],y[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);
}
db min(db a,db b){return a<b?a:b;}
db max(db a,db b){return a>b?a:b;}
void adjust(int y){
	for (int _y;y;y=_y){
		_y=px[link[y]];
		px[link[y]]=y;
		py[y]=link[y]; 
	}
}
void bfs(int st){
	for (int i=1;i<=n;++i) slack[i]=1e12,vx[i]=vy[i]=0;
	while (!q.empty()) q.pop();
	q.push(st);
	while (1){
		while (!q.empty()){
			int x=q.front();
			vx[x]=1,q.pop();
			for (int y=1;y<=n;++y)
			if (!vy[y]&&slack[y]>lx[x]+ly[y]-G[x][y]){
				slack[y]=lx[x]+ly[y]-G[x][y],link[y]=x;
				if (!slack[y]){
					vy[y]=1;
					if (!py[y]) {adjust(y); return;}
					    else q.push(py[y]);
				}
			}
		}
		db mn=1e12;
		for (int i=1;i<=n;++i)
		    if (!vy[i]) mn=min(mn,slack[i]);
		for (int i=1;i<=n;++i){
			if (vx[i]) lx[i]-=mn;
		    if (vy[i]) ly[i]+=mn;
		        else slack[i]-=mn;
		}
		for (int i=1;i<=n;++i)
		if (!vy[i]&&!slack[i]){
			vy[i]=1;
			if (!py[i]) {adjust(i); return;}
			    else q.push(py[i]);
		}
	}
}
void KM(){
	for (int i=1;i<=n;++i){
		link[i]=ly[i]=px[i]=py[i]=0,lx[i]=-1e12;
		for (int j=1;j<=n;++j)
		    lx[i]=max(lx[i],G[i][j]);
	}
	for (int i=1;i<=n;++i) bfs(i);
}
int o(int x){return x*x;}
int main(){
    n=iut();
	for (int i=1;i<=n;++i) x[i]=iut(),y[i]=iut();
	for (int j=1;j<=n;++j){
		int X=iut(),Y=iut();
		for (int i=1;i<=n;++i)
			G[i][j]=-sqrt(o(X-x[i])+o(Y-y[i]));
	}
	KM();
	for (int i=1;i<=n;++i)
		print(px[i]),putchar(32);
	return 0;
}

标签：AtCoder,Beginner,int,namespace,ans,using,373,include,ABC373
From： https://www.cnblogs.com/Spare-No-Effort/p/18450624

相关文章

  • Solution - Atcoder ARC116C Multiple Sequences
    一个\(\mathcal{O}(m^{\frac{3}{4}}\logm)\)做法。令\(a_0=1\)。对于倍数问题，考虑类似差分的思想，定义\(b_i=\frac{a_i}{a_{i-1}}(1\lei\len)\)，那么合法的\(a\)和\(b\)是双射的，就只需要考虑对\(b\)计数了。考虑到因为有\(\prod\limits_{i=1}^nb_i\lem\)......
  • abc373E How to Win the Election
    有N个候选人和总共K张选票，目前第i个候选人的票数为A[i]。在全部选票统计完成后，如果得票数多于自己的人数小于M，则当选，可以多个人同时当选。对于每个人，输出当选需要再获得的最少票数。1<=M<=N<=2E5,1<=K<=1E12,0<=A[i]<=1E12,sum(A[i])<=K分析：对每个候选人，二分答案，假设需要的票......
  • AtCoder Beginner Contest 374
    ABC374A-Takahashisan2题目传送门代码（签到题）#include<cstdio>#include<cctype>#include<cstring>#include<cmath>#include<queue>usingnamespacestd;intiut(){ intans=0,f=1;charc=getchar(); while(!isdigit(c))f=(c==&......
  • AtCoder Beginner Contest 374
    省流版A.判断末三位即可B.逐位判断即可C.枚举所有分组情况即可D.枚举线段顺序、端点顺序即可E.二分答案，发现贵的机器数量不超过\(100\)，枚举求最小花费看是否可行即可F.朴素DP，复杂度分析得到有效时刻不超过\(O(n^2)\)而非\(O(s_i)\)，直接\(DP\)即可A-Takahashi......
  • ABC373 E/F
    ABC373E/FE-HowtoWintheElection二分答案比较好想，可是细节有点多，复杂度$O(n\log^2n)$。一开始忘了一个特判，狂WA不止，然后调完再交，直接破防，WA一个点。接着尝试去卡，不知道怎么想的，粘错代码了。还剩半个小时，非常忙碌地调代码，但是不知道在忙什么。赛后找到正确代码，调过h......
  • AtCoder Beginner Contest 373
    省流版A.暴力即可B.求出字母位置，绝对值相加即可C.显然答案为两个数组的最大值的和D.注意直接BFS的点权范围不超过题目范围，直接BFS即可E.发现单调性，二分票数，用前缀和\(O(1)\)判断可行性即可F.朴素背包DP，相同重量的物品一起考虑，用优先队列求解\(l\)个相同重量物品最大......
  • 题解：AT_abc373_d [ABC373D] Hidden Weights
    可以发现一个性质：对于图的每个连通分量，一旦在其中任何顶点上的值固定，则所有写入的值都是确定的。我们可以逐个DFS每个连通分量，按照题目的要求给每个点赋值，初始搜索的点值设成\(0\)即可。代码：#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intn,m;......
  • 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\)列为最......
  • AT_abc373_e 的题解
    （一）二分套二分。（感觉是一个很麻烦的做法。）题目问的是让额外给的票最少，考虑二分答案。设二分的答案为\(x\)，该候选人原来的得票为\(v\)，想要超过他至少要\(x+v+1\)。同时用前缀和维护区间和。第一种情况为该候选人在前\(m\)个人中，如下图所示。绿色箭头为被讨论的人，蓝色箭......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99