A - Sum of 2050
首先n需要滿足被2050整除，然后就一定有解，
這是n可以被看成
2050 * x * 10^a + 2050 * y * 10^b + ... + 2050 * z * 10 ^c
這時候把n/2050就得到了很多個10的冪次相乘，然后我們只需要去看一下有多少個冪次就好了，盡量取大一點就好了
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#include<stack>
#include<vector>
#include<queue>
#include<unordered_map>
#include<stdio.h>
using namespace std;
const int MAXN = 3e5 + 7;
typedef long long ll;
#define INFll 9223372036854775807
#define INF 0x3f3f3f3f
#define dbg(x) cout << #x << " = " << x << endl;
#define lowbit(n) (n&-n)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const ll mod = 1e9 + 7;
ll t, n;
int main(int argc, char const *argv[])
{
IOS
cin >> t;
while(t--)
{
cin >> n;
if (n % 2050)//判斷是否滿足
{
cout << -1 << endl;
continue;
}
ll ans = 0;
n /= 2050;
while(n)
{
ll k = 1;
while(k * 10<= n)
k *= 10;
n -= k;
ans++;
}
cout << ans << endl;
}
return 0;
}
B - Morning Jogging(優先佇列模擬一下)
就是對于個節點上的邊，最小的邊都讓現在手上拿的邊長最小值最大的人先選即可，
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#include<stack>
#include<vector>
#include<queue>
#include<unordered_map>
#include<stdio.h>
using namespace std;
const int MAXN = 3e5 + 7;
typedef long long ll;
#define INFll 9223372036854775807
#define INF 0x3f3f3f3f
#define dbg(x) cout << #x << " = " << x << endl;
#define lowbit(n) (n&-n)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const ll mod = 1e9 + 7;
ll t, n, m;
vector<int>vec[105];
int mi[105];
struct node
{
int x;
friend operator <(node n1, node n2)
{
return mi[n1.x] < mi[n2.x];
}
};
int b[105];
int main(int argc, char const *argv[])
{
IOS
cin >> t;
while(t--)
{
cin >> n >> m;
priority_queue<node>Q;
memset(mi, INF, sizeof(mi));//存每個人手上拿所有路中的最小值
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
ll x;
cin >> x;
vec[i].push_back(x);//存邊排序
}
sort(vec[i].begin(), vec[i].end());
}
for (int i = 0; i < n; i++)
{
for (int i = 1; i <= m; i++)
Q.push(node{i});
for (int j = 0; j < m; j++)
{
int x = Q.top().x;//手上邊大的人優先選
Q.pop();//選過就踢掉
b[x] = vec[i][j];//更新答案
mi[x] = min(mi[x], vec[i][j]);//更新最小值
}
for (int j = 1; j <= m; j++)
cout << b[j] << " ";
cout << endl;
}
}
return 0;
}
C - Fillomino 2
題意：給定一個矩陣的主對角線的元素，問能否讓每個主對角線上位置延伸出對應該值長度的連續路徑，有就輸出這個表，沒有就-1
很明顯，只需要從主對角線開始一層一層往下遍歷就行了，對于每個斜線，很明顯，對于主對角線來說，如果最上面的值不是1， 那么它只能往下延伸一個位置，然后主對角線上第二個數如果不為1， 那么也只能往下延伸，如果為1，則無法再延伸，這時候主對角線下面的數都只能往左邊遍歷，然后每個數都延伸出了一位，這時候輪到2不能再延伸了，就這樣發現，其實結果以及固定了，只需要再模擬的程序中判斷一下有沒有沖突就可以了
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#include<stack>
#include<vector>
#include<queue>
#include<unordered_map>
#include<stdio.h>
using namespace std;
const int MAXN = 3e5 + 7;
typedef long long ll;
#define INFll 9223372036854775807
#define INF 0x3f3f3f3f
#define dbg(x) cout << #x << " = " << x << endl;
#define lowbit(n) (n&-n)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const ll mod = 1e9 + 7;
ll t, n, m;
int a[505][505];
int b[105];
int main(int argc, char const *argv[])
{
IOS
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i][i];
int num = 1;//延伸了幾層，初始一層
int judge = 1;//判斷有沒有沖突
for (int i = 2; i <= n && judge; i++)
{
int flag = 0;//1表示向左，0表示向下
for (int j = i; j <= n; j++)
{
if (a[j - 1][j - i + 1] - num == 0)//遇到被遍歷完的數了，那么改變方向
{
flag = 1;
}
if (a[j][j - i + 1])//沖突
judge = 0;
if (flag == 0)
{
a[j][j - i + 1] = a[j - 1][j - i + 1];
}
else{
a[j][j - i + 1] = a[j][j - i + 2];
}
}
num++;
}
if (judge == 0)
cout << -1 << endl;
else
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
cout << a[i][j] << " ";
}
cout << endl;
}
}
return 0;
}
D - Explorer Space（滾動陣列+dp）
不知道不用滾動會不會爆空間，我也沒試過，保險起見上了個滾動
題意：就是對于每個點，都和他上下左右四個方向的相鄰點之間有一條雙向邊，每條邊都有一個權值，每個點都可以訪問上下左右四個方向的相鄰點，并獲得這條邊的權值，問，正好走往k步后，獲得的最小權值總和是多少，
思路：用step來存下每個點往上下左右四個方向之間邊的權值，
然后， dp[2][k][i][j]表示該點走了k步獲得的最小權值和
很明顯，k為奇數的時候不可能
行走k步的狀態為，每個點的狀態轉移方程其實就相當于往四個方向走并且回來，并且加上四個方向k-2的狀態取最小，也就是說，假定往上走并回來，那么將會消耗2步，那么其他三個方向也是一樣的，因為k-2的狀態已經得到了，所以只需要求四個方向的最小值就好了，這樣子不斷轉移就可以了，
for (int i = 1; i <= n; i++)
{
for (int j = 1; j < m; j++)
{
cin >> step[i][j][4];//1 2 3 4上下左右
step[i][j + 1][3] = step[i][j][4];
}
}
for (int i = 1; i < n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> step[i][j][2];
step[i + 1][j][1] = step[i][j][2];
}
}
for (int len = 2; len <= k; len += 2)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
dp[num&1][len][i][j] = min(min(dp[(num + 1) & 1][len - 2][i + 1][j] + step[i][j][2] + step[i + 1][j][1], dp[(num + 1) & 1][len - 2][i - 1][j] + step[i][j][1] + step[i - 1][j][2]),min(dp[(num + 1) & 1][len - 2][i][j + 1] + step[i][j][4] + step[i][j + 1][3] , dp[(num + 1) & 1][len - 2][i][j - 1]+ step[i][j - 1][4] + step[i][j][3]));
}
}
num++;
}
代碼：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#include<stack>
#include<vector>
#include<queue>
#include<unordered_map>
#include<stdio.h>
using namespace std;
const int MAXN = 3e5 + 7;
typedef long long ll;
#define INFll 9223372036854775807
#define INF 0x3f3f3f3f
#define dbg(x) cout << #x << " = " << x << endl;
#define lowbit(n) (n&-n)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const ll mod = 1e9 + 7;
ll t, n, k;
int dp[2][25][505][505];
int step[505][505][5];
int main(int argc, char const *argv[])
{
IOS
int m;
cin >> n >> m >> k;
memset(step, INF, sizeof(step));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j < m; j++)//左右
{
cin >> step[i][j][4];//1 2 3 4上下左右
step[i][j + 1][3] = step[i][j][4];
}
}
for (int i = 1; i < n; i++)
{
for (int j = 1; j <= m; j++)//上下
{
cin >> step[i][j][2];
step[i + 1][j][1] = step[i][j][2];
}
}
if (k % 2)//為奇數
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cout << -1 << " ";
}
cout << endl;
}
return 0;
}
int num = 0;
for (int len = 2; len <= k; len += 2)//每次+2，因為要剛好回來
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
dp[num&1][len][i][j] = min(min(dp[(num + 1) & 1][len - 2][i + 1][j] + step[i][j][2] + step[i + 1][j][1], dp[(num + 1) & 1][len - 2][i - 1][j] + step[i][j][1] + step[i - 1][j][2]),min(dp[(num + 1) & 1][len - 2][i][j + 1] + step[i][j][4] + step[i][j + 1][3] , dp[(num + 1) & 1][len - 2][i][j - 1]+ step[i][j - 1][4] + step[i][j][3]));
}
}
num++;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
cout << dp[(num + 1)&1][k][i][j] << " ";
cout << endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/279892.html
標籤：其他
上一篇：C1任務01-資訊編碼
下一篇：Contest 2050 and Codeforces Round #718 (Div. 1 + Div. 2) A B C 題解