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

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