Codeforces Round #540 (Div. 3)

A链接
讨论一下 2 a 2a 2a跟 b b b的大小关系即可。

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <bitset>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define MAXN 1010100
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ll __int64
#define INF 0x7fffffff
#define cs(s) freopen(s,"r",stdin)
#define mem(x) memset(x,0,sizeof(x))
#define PI acos(-1)
#define eps 1e-10
using namespace std;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
//head
int main(){
	ios::sync_with_stdio(false);
	int t;
	for(cin>>t;t;t--){
		LL n,a,b;
		cin>>n>>a>>b;
		if(2*a<=b)cout<<1ll*n*a<<endl;
		else {
			cout<<(1ll*n/2*b+1ll*(n%2)*a)<<endl;
		}

	}
	return 0;
}

B链接
分奇偶性，预处理前缀和，然后遍历每个位置，判断一下即可。

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <bitset>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define MAXN 1010100
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ll __int64
#define INF 0x7fffffff
#define cs(s) freopen(s,"r",stdin)
#define mem(x) memset(x,0,sizeof(x))
#define PI acos(-1)
#define eps 1e-10
using namespace std;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
//head
LL sum[200001],sumA[200001][2],sumB[200001],a[200001];
int main(){
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],sum[i]=sum[i-1]+a[i];
	sum[1]=a[1];
	for(int i=1;i<=n;i++){
		if(i%2)sumA[i][1]=sumA[i-1][1]+a[i],sumA[i][0]=sumA[i-1][0];
		else sumA[i][0]=sumA[i-1][0]+a[i],sumA[i][1]=sumA[i-1][1];
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(sumA[i-1][0]+sumA[n][1]-sumA[i][1]==sumA[i-1][1]+sumA[n][0]-sumA[i][0])ans++;
	}
	cout<<ans<<endl;
	return 0;
}

C链接
模拟，题意是判断给的 n 2 n^2 n2个数能否组成一个回文矩阵。
分奇偶讨论：
n为偶数时，每个位置与之对称的位置有四个，即判断是否有一个数出现次数大于四，遍历 1 4 \frac{1}{4} 41​矩阵的每个位置即可。
n为奇数时，奇数与偶数不同的地方在于，必然有且仅有一个数出现了奇数次，这个数放正中间，然后遍历有四个对称位置的位置，放出现大于四次的即可，然后，中间行和中间列的每个元素与之对称的位置有两个，找出现大于两次的放即可。
若中间放的过程中，找不到满足的即输出-1。

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <bitset>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define MAXN 1010100
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ll __int64
#define INF 0x7fffffff
#define cs(s) freopen(s,"r",stdin)
#define mem(x) memset(x,0,sizeof(x))
#define PI acos(-1)
#define eps 1e-10
using namespace std;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
//head
int a[444],cnt[1111];
int ans[22][22];
int main(){
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	for(int i=1;i<=n*n;i++)cin>>a[i],cnt[a[i]]++;
	if(n==1){cout<<"YES\n"<<a[1];return 0;}
	if((n)%2){
		int bj=0;
		for(int k=1;k<=1000;k++){
			if(cnt[k]%2!=0){ans[(n+1)/2][(n+1)/2]=k,bj=1;cnt[k]--;break;}
		}
		if(!bj)return cout<<"NO\n",0;
	}
	for(int i=1;i<=1000;i++){
		if(cnt[i]%2)return cout<<"NO",0;
	}
	for(int i=1;i<=n/2;i++){
		for(int j=1;j<=n/2;j++){
			if(ans[i][j])continue;
			int bj=0;	
			for(int k=1;k<=1000;k++){
				if(cnt[k]>=4){
					ans[i][j]=k;
					ans[n-i+1][j]=k;
					ans[i][n-j+1]=k;
					ans[n-i+1][n-j+1]=k;
					cnt[k]-=4;
					bj=1;
					break;
				}
			}
			if(!bj){return cout<<"NO",0;}
		}
	}	
	if(n%2){
		for(int j=1;j<=n/2;j++){
			int bj=0;
			for(int i=1;i<=1000;i++){
				if(cnt[i]>=2){ans[j][(n+1)/2]=ans[n-j+1][(n+1)/2]=i,cnt[i]-=2;bj=1;break;}
			}
			if(!bj)return cout<<"NO",0;
		}
		for(int j=1;j<=n/2;j++){
			int bj=0;
			for(int i=1;i<=1000;i++){
				if(cnt[i]>=2){ans[(n+1)/2][j]=ans[(n+1)/2][n-j+1]=i,cnt[i]-=2;bj=1;break;}
			}
			if(!bj)return cout<<"NO",0;
		}
	}
	cout<<"YES\n";
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)cout<<ans[i][j]<<' ';
		cout<<endl;
	}
	return 0;
}

F1链接
题意是找到最多数量的边。
这种边满足：去掉这条边之后分成的两个部分，不同时存在红色和蓝色。
做法：两次dfs
第一次dfs:从1开始dfs这颗树，记录当前节点可以遍历到的红色，蓝色的数量。
第二次dfs:从1开始dfs这棵树，设当前节点为 u u u，下一个节点为 v v v，显然，从1到 v v v只能存在一个颜色，且另一个颜色只能存在于 v − &gt; n v-&gt;n v−>n,记录下答案即可。

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <bitset>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define MAXN 1010100
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ll __int64
#define INF 0x7fffffff
#define cs(s) freopen(s,"r",stdin)
#define mem(x) memset(x,0,sizeof(x))
#define PI acos(-1)
#define eps 1e-10
using namespace std;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
//head
const int N=3e5+11;
int n,a[N],ans;
vector<int>v[N];
int cnt[N][4];
void dfs1(int now,int pre){
	cnt[now][a[now]]++;
	for(auto k:v[now]){
		if(k==pre)continue;
		dfs1(k,now);
		for(int j=0;j<3;j++)cnt[now][j]+=cnt[k][j];
	}
}
void dfs2(int now,int pre){
	for(auto k:v[now]){
		if(k==pre)continue;
		dfs2(k,now);
		if(cnt[k][1]==0&&cnt[1][2]==cnt[k][2])ans++;
		if(cnt[k][2]==0&&cnt[1][1]==cnt[k][1])ans++;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++){
		int s,t;
		cin>>s>>t;
		v[s].pb(t);
		v[t].pb(s);
	}
	dfs1(1,0);
	dfs2(1,0);
	cout<<ans<<endl;
	return 0;
}

D链接
题意是，有n杯咖啡，m页作业，每杯咖啡只能喝一次。每天可以喝任意多杯咖啡。
假如有一天喝了k杯咖啡，那么这一天的总贡献为 ∑ 1 k m a x ( a k i − k + 1 , 0 ) \sum_1^{k}max(a_{ki}-k+1,0) ∑1k​max(aki​−k+1,0)。
问 ：最少要多少天能完成作业，或者完不成输出-1 。
做法：二分答案，上界n，下界1，ans初始为-1。
先将 n n n杯咖啡按权值排序（大的优先）
每次 c h e c k check check当前天数 m i d mid mid， n n n杯咖啡均摊给 m i d mid mid天，依次递减，求出总贡献与m比较即可。

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <bitset>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define MAXN 1010100
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ll __int64
#define INF 0x7fffffff
#define cs(s) freopen(s,"r",stdin)
#define mem(x) memset(x,0,sizeof(x))
#define PI acos(-1)
#define eps 1e-10
using namespace std;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
//head
LL n;
LL a[200001],ans=-1;
LL m;
int cmp(int A,int b){
	return A>b;
}
int ch(int k){
	int cnt=0;
	LL sum=0;
	int res=0;
	for(int i=1;i<=n;i++){
		sum+=max(a[i]-cnt,0ll);
		res++;
		if(res==k)cnt++,res=0;
	}
	return sum>=m;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	LL sum=0;
	for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];
	if(sum<m)return cout<<-1,0;
	else if(sum==m)return cout<<n,0;
		sort(a+1,a+1+n,cmp);
	LL l=1,r=n;
	ans=-1;
	while(l<=r){
		LL mid=(l+r)/2;
		if(ch(mid))r=mid-1,ans=mid;
		else l=mid+1;
	}
	cout<<ans<<endl;	
	return 0;
}

E链接
题意：n对，k种颜色。
要求构造n对，满足：
(设每对的颜色为 g i , b i g_i,b_i gi​,bi​)
1.每一对的 g i ≠ b i g_i \neq b_i gi​̸​=bi​。
2. k ≤ g i , b i ≤ k k \leq g_i,b_i \leq k k≤gi​,bi​≤k
3.不存在 i , j ( i ≠ j ) , b i = b j 且 g i = g j i,j(i \neq j),b_i=b_j且g_i=g_j i,j(i̸​=j),bi​=bj​且gi​=gj​。
4. 1.... n − 1 满 足 b i ≠ b i + 1 , g i ≠ g i + 1 1....n-1满足b_i \neq b_{i+1},g_i \neq g_{i+1} 1....n−1满足bi​̸​=bi+1​,gi​̸​=gi+1​。
显然k种颜色最多可以构造 k ∗ ( k − 1 ) k*(k-1) k∗(k−1)组不同的对。 n &gt; k ∗ ( k − 1 ) n&gt;k*(k-1) n>k∗(k−1)则不可能构造出来，即输出-1。

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <bitset>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define MAXN 1010100
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ll __int64
#define INF 0x7fffffff
#define cs(s) freopen(s,"r",stdin)
#define mem(x) memset(x,0,sizeof(x))
#define PI acos(-1)
#define eps 1e-10
using namespace std;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
//head
int a[200001];
int main(){
	ios::sync_with_stdio(false);
	int n,k;
	cin>>n>>k;
	if(n>1ll*k*(k-1))cout<<"NO\n";
	else{
		cout<<"YES\n";
		for(int i=1;i<=k;i++){
			a[i]=i+1;
			if(a[i]==k+1)a[i]=1;
		}
		for(int i=1,j=1;i<=n;i++){
			cout<<j<<' '<<a[j]<<endl;
			a[j]++;
			if(a[j]==k+1)a[j]=1;
			j++;
			if(j==k+1)j=1;
		}
	}
	return 0;
}
全部评论

相关推荐

11-28 09:24
影石Insta360_深度学习算法工程师(准入职员工)
影石内推影石面经
自我介绍（3min左右）看你最近的工作是和bootloader相关的，汽车后视镜相关的，从7.8到3.6s的改进是比较显著的，那你有没有比较以前的不同的机制主要耗时在哪几个地方我看你一直在写x86平台的操作系统，基本是从基础到操作系统的构建工作，这中间持续开发的过程中有没有不太好理解，或者阻塞的事情呢这个启动加载器，比如从bios启动那部分是怎么完成的，或者说bootloader部分你做了什么呢，平台是什么呢（最开始我是在bochs上完成的）你现在是在x86下完成的，有没有考虑过arm呢，因为armv8也是64位，有没有想过去做二者的比较呢（过程中提到了看过电源管理的源码），你看的电源管理是在...
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
11-29 12:19
点赞 评论 收藏
分享
11-18 10:36
内蒙古民族大学 Java
二本实习简历，初筛都过不去
狠狠的赚一笔😋
听说改名字就能收到offer哈：Radis写错了兄弟
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

正在热议
# 拼多多求职进展汇总 #
240442次浏览 2049人参与
# 实习，投递多份简历没人回复怎么办 #
2447110次浏览 34795人参与
# 阿里云管培生offer #
65272次浏览 1766人参与
# 25届秋招总结 #
424422次浏览 4289人参与
# 虾皮求职进展汇总 #
100231次浏览 808人参与
# 地方国企笔面经互助 #
7346次浏览 18人参与
# 北方华创开奖 #
67933次浏览 558人参与
# ai智能作图 #
35185次浏览 434人参与
# 中兴求职进展汇总 #
470913次浏览 2453人参与
# 我在牛爱网找对象 #
75220次浏览 556人参与
# 双非有机会进大厂吗 #
106054次浏览 1333人参与
# 实习想申请秋招offer，能不能argue薪资 #
37912次浏览 313人参与
# 机械求职避坑tips #
24187次浏览 252人参与
# 发工资后，你做的第一件事是什么 #
10490次浏览 52人参与
# 25届机械人为了秋招做了哪些准备？ #
26790次浏览 366人参与
# 投格力的你，拿到offer了吗？ #
47860次浏览 337人参与
# 我的实习求职记录 #
6143522次浏览 84081人参与
# 投递实习岗位前的准备 #
1193495次浏览 18510人参与
# 机械人怎么评价今年的华为 #
158417次浏览 1354人参与
# 在职场上，你最讨厌什么样的同事 #
6467次浏览 96人参与
# 实习与准备秋招该如何平衡 #
725858次浏览 8568人参与
# 华为工作体验 #
112419次浏览 870人参与
牛客网
牛客企业服务