A Sum of 2050
題意：給定一個數字n，要求將n表示為一些2050*數字(不一定是不同的)的和，計算所需的最小2050個數，
思路：如果不能整除2050則輸出-1，否則輸出商的每個位上的數字之和，
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
long long res;
int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%lld", &res);
if (res % 2050 == 0) {
res /= 2050;
long long ans = 0;
while (res) {
ans += res % 10;
res /= 10;
}
printf("%lld", ans);
}
else
printf("-1");
printf("\n");
}
return 0;
}
B Morning Jogging
題意：給你n個長度為m的陣列，要求對其按行進行排列，使得每一列上的最小值之和最小，如果有多個答案，列印任何一個，
思路：讀懂題意之后就會發現，將所有n*m個數按升序排序，第i小的數（1<=i<=m）一定在第i列，而其余數隨機排列即可，注意每一個數的行是不變的，
到這一步之后，唯一糾結的地方就是這些資料應該怎樣存盤，怎樣處理，又怎樣進行輸出，
剛開始想著用小根堆的性質存盤會不會賊方便，（然而菜雞對于STL容器實在是太生疏了），于是用二維陣列存盤加上雙指標標記暴力AC，事實上我認為開bool陣列標記會更方便一些，當時有些著急了……
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int n, m;
int s[110][2];
long d[110][110];
long q[110][110];
int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%ld", &q[i][j]);
for (int i = 1; i <= n; i++) {
sort(q[i] + 1, q[i] + m + 1);
s[i][1] = m;
s[i][0] = 1;
}
for (int j = 1; j <= m; j++) {
int k = 1;
for (int i = 2; i <= n; i++)
if (q[i][s[i][0]] < q[k][s[k][0]])
k = i;
for (int i = 1; i < k; i++)
d[i][j] = q[i][s[i][1]--];
d[k][j] = q[k][s[k][0]++];
for (int i = k + 1; i <= n; i++)
d[i][j] = q[i][s[i][1]--];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
printf("%d ", d[i][j]);
printf("\n");
}
}
return 0;
}
C Fillomino 2
題意：給你一個n個數的全排列的其中一種排列方式
其中這n個數分別為n*n矩陣的對角線
求是否可以構造一個下三角矩陣
滿足這個矩陣對角線的每一個元素
都有
旁邊與它相等的數的個數（包括它本身）等于這個元素的值
如果存在這個矩陣，輸出這個下三角矩陣
如果不存在，輸出-1
思路：
看懂題目的條件下，很明顯這題答案一定存在
因為你舉不出反例去反對它
然后就是一個簡單的貪心的做法了
在不超過下三角矩陣范圍的情況下
每次優先把它左邊的數變成和它一樣的
如果超了左邊界
就把下面的數變成和它一樣的
且一定不會超過下邊界
一共變a[i][i] - 1 次
dfs或者bfs都可
dfs代碼如下
#include<bits/stdc++.h>
#define fer(i,a,b) for(re i = a ; i <= b ; ++ i)
#define re register int
#define x first
#define y second
typedef long long ll ;
using namespace std;
const int N = 1e6 + 10 , M = 1010 , inf = 0x3f3f3f3f , mod = 1e9 + 7 ;
int n ;
int a[N] ;
int s[M][M] ;
bool st[M][M] ;
int k ;
void dfs(int i , int j , int res)
{
if(k == res) return ;
if(i <= 0 || i > n || j <= 0 || j > n) return ;
if(st[i][j]) return ;
st[i][j] = true ;
s[i][j] = res ;
k ++ ;
dfs(i,j-1,res) ;
dfs(i+1,j,res) ;
}
int main()
{
cin >> n ;
fer(i,1,n)
{
cin >> a[i] ;
s[i][i] = a[i] ;
}
fer(i,1,n)
fer(j,1,n)
if(i == j)
{
k = 0 ;
dfs(i,j,s[i][j]) ;
}
fer(i,1,n)
{
fer(j,1,n)
if(s[i][j] != 0) cout << s[i][j] << " " ;
cout << endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/279893.html
標籤：其他
上一篇：Contest 2050 and Codeforces Round #718 (Div. 1 + Div. 2)