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

AtCoder Beginner Contest 371

时间:2024-09-14 22:25:18浏览次数:10  
标签:AtCoder Beginner 10 int cin long maxn 371 define

https://atcoder.jp/contests/abc371

C:

暴力。思路是把1-8的点映射到全排列上面,然后把有的点去掉没的点加上取ans最小值。
这题复杂度是\(8!\times7\times4\),暴力求全排列即可(第一次写暴力全排列思索了一会复杂度

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mkp make_pair
#define lowbit(x) ((x&(-x)))
#define int long long
const int maxn=2e5+10;
bool edgg[10][10];
bool edgh[10][10],vis[10];
int mp[10],n;
int a[10][10],sum=1e17;
void jud(){
	int tmp=0;
	//for(int i=1;i<=n;i++)cout<<mp[i]<<' ';
	//cout<<endl;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(edgg[i][j]!=edgh[mp[i]][mp[j]]){
				int x=mp[i],y=mp[j];if(x>y)swap(x,y);
				tmp+=a[x][y];	
			}
		}
	}
	sum=min(tmp,sum);
}
void dfs(int nw){
	if(nw==n){
		jud();return;
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			vis[i]=1;mp[nw+1]=i;
			dfs(nw+1);
			vis[i]=0;
		}
	}
}
void solve(){
	cin>>n;
	int mg,mh,u,v;cin>>mg;
	for(int i=1;i<=mg;i++){
		cin>>u>>v;
		edgg[u][v]=1;
		edgg[v][u]=1;
	}
	cin>>mh;
	for(int i=1;i<=mh;i++){
		cin>>u>>v;
		edgh[u][v]=1;
		edgh[v][u]=1;
	}
	for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)cin>>a[i][j];
	for(int i=1;i<=n;i++){
		vis[i]=1;
		mp[1]=i;dfs(1);
		vis[i]=0;
	}
	
	cout<<sum<<endl;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int tt;tt=1;while(tt--){
		solve();
	}
} 

D:

最先想到的是权值线段树。。但是发现只要二分找区间就能前缀和做了

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mkp make_pair
#define lowbit(x) ((x&(-x)))
#define int long long
const int maxn=2e5+10;
int x[maxn],p[maxn],pre[maxn];
void solve(){
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i];
	}
	for(int i=1;i<=n;i++){
		cin>>p[i];pre[i]=pre[i-1]+p[i];
	}
	int q;cin>>q;
	while(q--){
		int ql,qr;cin>>ql>>qr;
		int l=0,r=n,mid=(l+r+1)/2;
		while(l<r){
			if(x[mid]<ql)l=mid;
			else r=mid-1;
			mid=(l+r+1)/2;
		}
		int ml=mid,mr;
		l=0,r=n,mid=(l+r+1)/2;
		while(l<r){
			if(x[mid]<=qr)l=mid;
			else r=mid-1;
			mid=(l+r+1)/2;
		}
		//cout<<pre[mid]<<' '<<pre[ml]<<"mk\n";
		cout<<pre[mid]-pre[ml]<<"\n";
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int tt;tt=1;while(tt--){
		solve();
	}
} 

标签:AtCoder,Beginner,10,int,cin,long,maxn,371,define
From: https://www.cnblogs.com/lyrrr/p/18414771

相关文章

  • 题解 [ABC371G] Lexicographically Smallest Permutation(中文/English)
    本题解提供英文版,位于示例代码之后。Englishversionofthiseditorialisprovidedafterthesamplecode.官方题解竟然用Python来算高精度lcm,我来提供一个可以避免一切大整数运算的方法。考察\(u\getsP_u\)这张图的每个置换环。为了使答案字典序最小,显然需要从前往后......
  • Taro(ABC 371)
    #include<bits/stdc++.h>#defineendl'\n'#defineintllusingll=longlong;typedefunsignedlonglongull;usingnamespacestd;voidGordenGhost();signedmain(){#ifdefGordenfreopen("in.txt","rt",stdi......
  • AtCoder Beginner Contest 370 补题记录
    A-RaiseBothHands题意:给出Snuke举的左右手情况,如果只举左手,输出Yes,如果只举右手,输出No,否则输出Invalid思路:举左手:(l==1&&r==0)举右手:(l==1&&r==0)其他情况都是Invalidvoidsolve(){intl=read(),r=read();if(l==1&&r==0){......
  • AtCoder Beginner Contest 274 A~E 题解
    吐槽:这比赛名字为啥没有英文版。。。A-BattingAverage题目大意给定整数\(A,B\),输出\(\fracBA\),保留三位小数。\(1\leA\le10\)\(0\leB\leA\)分析签到题,使用printf或cout格式化输出即可。代码#include<cstdio>usingnamespacestd;intmain(){ inta,b; sc......
  • TOYOTA MOTOR CORPORATION Programming Contest 2023#1 (AtCoder Beginner Contest 29
    好久没写题解了,这就来水一篇。A-JobInterview题目大意给定一个长为\(N\)的字符串\(S\),由o、-、x组成。判断\(S\)是否符合下列条件:\(S\)中至少有一个o。\(S\)中没有x。\(1\leN\le100\)分析签到题。直接按题意模拟即可。代码#include<cstdio>usingn......
  • AtCoder Beginner Contest 318 G - Typical Path Problem 题解
    G-TypicalPathProblem题目大意给定一张\(N\)个点、\(M\)条边的简单无向图\(G\)和三个整数\(A,B,C\)。是否存在一条从顶点\(A\)到\(C\),且经过\(B\)的简单路径?数据范围:\(3\leN\le2\times10^5\)\(N-1\leM\le\min(\frac{N(N-1)}2,2\times10^5)\)\(1\leA......
  • UNIQUE VISION Programming Contest 2023 Christmas (AtCoder Beginner Contest 334)
    A-ChristmasPresent题目大意给定两个正整数\(B,G\)(\(1\leB,G\le1000\)且\(B\neG\)),判断哪个更大。分析模拟即可。代码#include<cstdio>usingnamespacestd;intmain(){ intb,g; scanf("%d%d",&b,&g); puts(b>g?"Bat":&qu......
  • AtCoder Beginner Contest 254 A~E 题解
    A-LastTwoDigits题目大意给定正整数\(N\),求\(N\)的后两位。\(100\leN\le999\)输入格式\(N\)输出格式输出\(N\)的后两位,注意输出可能有前导0。样例\(N\)输出\(254\)54\(101\)01分析题目已经规定\(N\)是三位数,因此无需使用整数输入,直接将输入看成......
  • AtCoder Beginner Contest 258 A~Ex 题解
    D-Trophy题目大意有一个游戏,由\(N\)个关卡组成。第\(i\)个关卡由一个数对\((A_i,B_i)\)组成。要通过一个关卡,你必须先花\(A_i\)的时间看一次介绍。然后,用\(B_i\)的时间打通这个关卡。若想多次通过同一个关卡,则第一次需要看介绍,后面无需再看(即如果想打通第\(i\)关\(N\)次,则所......
  • AtCoder Beginner Contest 260 A~F 题解
    A-AUniqueLetter题目大意给定一个长度为\(3\)的字符串\(S\)。输出\(S\)中出现正好一次的字母(任意,如abc中,三个字母都可为答案)。如果没有,输出-1。数据保证\(S\)的长为\(3\),且由小写英文字母组成。输入格式\(S\)输出格式输出任意符合条件的答案。样例\(S\)输出......