首页 > 软件开发 > 软件开发

【Contest 2050 and Codeforces Round #718 (Div. 1 + Div. 2)】Codeforces-1517

admin 软件开发 2021-04-26 15:58:03 acm竞赛  
后台-系统设置-扩展变量-手机广告位-内容正文底部

A. Sum of 2050

第一眼以为dp,憨憨写了五分钟发现d不出来,我好傻qaq
这道题只讨论 n ∣ 2050 n\mid2050 n∣2050的情况。
假设 n 为 n为 n为m位十进制数,则有
n = k 1 ∗ 2050 ∗ 1 0 m − 4 + k 2 ∗ 2050 ∗ 1 0 m − 5 + k 3 ∗ 2050 ∗ 1 0 m − 6 + . . . + k m − 4 ∗ 2050 ∗ 1 0 0 n=k_1*2050*10^{m-4}+k_2*2050*10^{m-5}+k_3*2050*10^{m-6}+...+k_{m-4}*2050*10^{0} n=k1​∗2050∗10m−4+k2​∗2050∗10m−5+k3​∗2050∗10m−6+...+km−4​∗2050∗100
其中 k i k_i ki​可能有多种可能,要使得 ∑ i = 1 n k i \sum_{i=1}^n k_i ∑i=1n​ki​最小,则必有 ∀ k i ≤ 9 \forall k_i\leq9 ∀ki​≤9。即只要从最大的 2050 ∗ 1 0 k 2050*10^k 2050∗10k减下去就行。

void solves(){
	ll n;cin>>n;
	if(n<2050){
		cout<<-1<<endl; return ;
	}
	int cnt=0;
	while(n){
		ll i=2050;
		while(i<=n)i*=10;
		i/=10;
		n-=i;
		cnt++;
		if(n<2050&&n){
			cout<<-1<<endl;return ;
		}
	}
	cout<<cnt<<endl;
}

B. Morning Jogging

认真读一下题意,思维非常简单,没什么好分析的,但是代码不太好写,写了快1h才调出来wssb 。记列数为m,取最小的m个数字,要使得每一列都有一个这m个数字即可。如样例:
2 3 4
1 3 5
⇓ \Downarrow ⇓
2 3 4
5 3 1
我个人感觉我的写法复杂乱乱的且sb,不知道有没有更好的写法

void solves(){
	int n,m; cin>>n>>m;
	int tot=0;
	for(int i=0;i<n;++i){
		for(int j=0;j<m;++j){
			cin>>mp[i][j];
			a[tot++]=mp[i][j];
			vis[i][j]=0;
		}
	}
	sort(a,a+tot);
	int mid=a[m-1];
	int s=0;
	for(int i=0;i<tot;++i){
		if(a[i]<mid) s++;
	}
	s=m-s;
	memset(cnt,0,sizeof(cnt));
	for(int i=0;i<n;++i){
		for(int j=0;j<m;++j){
			if(mp[i][j]<mid){
				vis[i][j]=1;
				cnt[j]++;//统计原本每一列中有多少个最小的m个数字
			}
			if(mp[i][j]==mid&&s){
				vis[i][j]=1;
				cnt[j]++;//统计原本每一列中有多少个最小的m个数字
				s--;
			}
		}
	}
	for(int j=0;j<m;++j){//先逐个询问每一列
		if(!cnt[j]){ //如果这一列没有最小的数字
			for(int i=0;i<m;++i){ //就找一列有的并且个数>1的
				if(cnt[i]>1){
					for(int k=0;k<n;++k){ //再遍历可swap的这一列 然后找到那个可swap的数
						if(vis[k][i]){
							swap(mp[k][i],mp[k][j]);
							vis[k][i]=0;
							vis[k][j]=1;
							cnt[i]--;
							cnt[j]++;
							goto ok;
						}
					}
				}
			}
		}
		ok: ;
	}
	for(int i=0;i<n;++i){
		for(int j=0;j<m;++j) cout<<mp[i][j]<<" ";
		cout<<endl;
	}
}

C. Fillomino 2

一开始真的是思维受限,想着一条对角线一条对角线直接填充,写了半天还是wa了。其实想明白思路后代码其实很简单。
从最下面开始,每一个元素尽量向下填充慢慢往上铺即可。

const int N=5e2+7;
int mp[N][N],vis[N][N],cnt[N];
int n;
void dfs(int c,int num,int x,int y){
	if(c==0||x<1||y<1) return ;
	if(x==n||mp[x+1][y]){
		mp[x][y-1]=num;
		dfs(c-1,num,x,y-1);
	} else{
		mp[x+1][y]=num;
		dfs(c-1,num,x+1,y);
	}
	
}
void solves(){
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>mp[i][i];
		cnt[i]=mp[i][i]-1;
	}
	for(int i=n;i>=1;--i) dfs(cnt[i],mp[i][i],i,i);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=i;++j) cout<<mp[i][j]<<" ";cout<<endl;
	}
}

感觉这场思维还是比较简单的,就看想不想得到了。主要我还是太菜了qaq

文章来源:https://blog.csdn.net/JophieQu/article/details/116116320

后台-系统设置-扩展变量-手机广告位-内容正文底部
版权声明

本文仅代表作者观点,不代表本站立场。
本文系作者授权发表,未经许可,不得转载。
本文地址:https://jcdi.cn/ruanjiankaifa/ruanjiankaifa/729.html

留言与评论(共有 0 条评论)
   
验证码:
后台-系统设置-扩展变量-手机广告位-评论底部广告位

教程弟

https://www.jcdi.cn/

统计代码 | 京ICP1234567-2号

Powered By 教程弟 教程弟

使用手机软件扫描微信二维码