20191221-题解2
大连理工大学程序设计竞赛2019届新生赛
Problem Designer : 出水当风 yzm007 Kinesis King_of_Dark coca NaCNer Dickwyz huxiaotaostasy
A 电玩城之战
因为能回本，所以根据\(a_i\)从小到大排序，当\(a_i\)相同时比较\(b_i\),\(b_i\)越大的越靠前，排完序后按顺序逐个打就好
#include<bits/stdc++.h>
using namespace std;
const int N=105,mxs=1e9,mxv=1e7;
int n,s,ans,num;
struct node
{
int a,b;
}e[N];
bool operator<(node a,node b)
{
return a.a<b.a||(a.a==b.a&&a.b>b.b);
}
int main()
{
//freopen("10.in","r",stdin);
//freopen("10.out","w",stdout);
scanf("%d",&n);
//assert(1<=n&&n<=100);
for(int i=0;i<n;++i)
{
scanf("%d%d",&e[i].a,&e[i].b);
}
scanf("%d",&s);
sort(e,e+n);
for(int i=0;i<n;++i)
{
if(e[i].a<=s)
{
ans++;
s+=e[i].b;
}
}
printf("%d\n",ans);
return 0;
}B 双子塔
\(dp[i][j]\)代表前
i个积木搭建起来的两个塔，第一个塔的高度减掉第二个塔的值为j，所能得到的双子塔的高度之和。
转移方程有三个情况
- \(dp[i][j]=dp[i-1][j]\) 不放积木
- \(dp[i][j]=\max(dp[i][j],dp[i-1][j-h[i]]+h[i])\) 将积木放第一个塔
- \(dp[i][j]=\max(dp[i][j],dp[i-1][j+h[i]]+h[i])\) 将积木放第二个塔
因为数据大且转移方程仅跟前一项有关所以使用滚动数组进行了优化
#include <bits/stdc++.h>
using namespace std;
int T;
const int maxn = 500000;
int dp[2][maxn * 2 + 5];
int n, h[maxn];
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
//clock_t start = clock();
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
int sum = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d", h + i);
sum += h[i];
}
for (int i = 0; i <= 2 * sum; i++)
{
dp[0][i] = dp[1][i] = -1;
}
dp[0][sum] = 0;
int now = 0;
for (int i = 1; i <= n; i++)
{
now = now ^ 1;
for (int j = 0; j <= sum * 2; j++)
{
dp[now][j] = dp[now ^ 1][j];
if (j - h[i] >= 0 && dp[now ^ 1][j - h[i]] != -1)
dp[now][j] = max(dp[now][j], dp[now ^ 1][j - h[i]] + h[i]);
if (j + h[i] <= sum * 2 && dp[now ^ 1][j + h[i]] != -1)
dp[now][j] = max(dp[now][j], dp[now ^ 1][j + h[i]] + h[i]);
}
}
if (dp[now][sum] <= 0)
printf("GG\n");
else
printf("%d\n", dp[now][sum] / 2);
}
//clock_t ends = clock();
//printf("running time:%Lf\n", (long double)(ends - start) / CLOCKS_PER_SEC);
return 0;
}C 植树造林
题意其实就是一株小草只能吸收周围横坐标纵坐标与它绝对值之差都小于等于2的格子，在循环遍历时，对于每一株小草，求出它附近满足条件的土地营养值之和就可以了，然后按照答案要求输出。
#include <iostream>
using namespace std;
const int maxn = 500;
int a[maxn][maxn], ans[maxn][maxn];
int n, m;
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
for (int k = i - 2; k <= i + 2; k++)
for (int w = j - 2; w <= j + 2; w++)
{
if (0 <= k && k < n && 0 <= w && w < m)
ans[i][j] += a[k][w];
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cout << ans[i][j] << " ";
}
cout << endl;
}
}D 日语课堂
这是一个签到模拟题。
你只需要将英文、日文的每个月份、每个时间的标签分别存在一个数组中即时查找即可（共四个数组）。
string weekEnglish[] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
string weekJapanese[] = {"getsuyoubi", "kayoubi", "suiyoubi", "mokuyoubi", "kinnyoubi", "toyoubi", "nichiyoubi"};
string hourJapanese[] = {"", "ichiji", "niji", "sannji", "yoji", "goji", "rokuji", "shichiji", "hachiji", "kuji", "jyuuji", "jyuuichiji", "jyuuniji"};
string minJapanese[] = {"", "jyuugofunn", "sannjyuppunn", "yonnjyuugofunn"};因为数据量比较小，因此只需要遍历查询并对比每个字符串就可以。
#include <iostream>
#include <cstring>
using namespace std;
string weekEnglish[] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
string weekJapanese[] = {"getsuyoubi", "kayoubi", "suiyoubi", "mokuyoubi", "kinnyoubi", "toyoubi", "nichiyoubi"};
string hourJapanese[] = {"", "ichiji", "niji", "sannji", "yoji", "goji", "rokuji", "shichiji", "hachiji", "kuji", "jyuuji", "jyuuichiji", "jyuuniji"};
string minJapanese[] = {"", "jyuugofunn", "sannjyuppunn", "yonnjyuugofunn"};
string week(string str)
{
for (int i = 0; i < 7; i++)
if (str == weekEnglish[i])
return weekJapanese[i];
return "";
}
string hour(string str)
{
int num = 0, siz = str.length();
for (int i = 0; i < siz; i++)
{
if (str[i] == ':')
return hourJapanese[num];
num = num * 10 + str[i] - '0';
}
return "";
}
string minu(string str)
{
int num = 0, siz = str.length();
bool over = false;
for (int i = 0; i < siz; i++)
{
if (str[i] == ':')
{
over = true;
continue;
}
if (!over)
continue;
num = num * 10 + str[i] - '0';
}
return minJapanese[num / 15];
}
int main()
{
int T;
cin >> T;
while (T--)
{
string w, m, t;
cin >> w >> m >> t;
cout << week(w) << " ";
cout << (m == "Morning" ? "gozen" : "gogo") << " ";
cout << hour(t) << " " << minu(t) << endl;
}
return 0;
}E 仙女矩阵
只要满足：
- 从起点到终点横奇偶性不发生变化
- 纵轴奇偶性不发生变化
就能到达
考虑数据范围，使用前缀和，O(n)预处理，O(1)回复询问，时间复杂度O(N+Q)。
#include<bits/stdc++.h>
using namespace std;
int n,q,a[100020],b[100020];
int aa[100020],bb[100020];
inline int read(){
int x=0;//f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
//if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x;
}
int main()
{
n=read(),q=read();
for(int i=1;i<=n;++i) a[i]=read(),aa[i]=(a[i]+a[i-1])%2?aa[i-1]+1:aa[i-1];
for(int i=1;i<=n;++i) b[i]=read(),bb[i]=(b[i]+b[i-1])%2?bb[i-1]+1:bb[i-1];
while(q--)
{
int x1=read(),y1=read(),x2=read(),y2=read();
if(aa[x1]!=aa[x2]||bb[y1]!=bb[y2]) puts("NO");
else puts("YES");
}
return 0;
}F 数数
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 2e5 + 500;
int T, a, b;
int main()
{
char c ;
do{
c = getchar();
if (c >= '0' and c <= '9')
{
while (c >= '0' and c <= '9')
putchar(c), c = getchar();
putchar('\n');
}
}while (c != EOF);
}G 简单数学题
\[ 3f(n)f(2n+1)=f(2n)(1+3f(n)),f(2n)<5f(n)\ \ \ ①\\ 3f(n)f(2n+1)-3f(n)f(2n)=f(2n)<5f(n)\\ 3(f(2n+1)-f(2n))<5\\ f(2n+1)-f(2n)=1\\ 代入①可得f(2n)=3f(n) \]
奇数项=偶数项+1
偶数项 \(f(x)=3 * f(x / 2)\)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 65537 + 100;
const int mod=1e9+7;
ll n;
ll calc(ll x)
{
if (x == 1)
return 1;
if (x & 1)
return (calc(x - 1) + 1)%mod;
else
return 3 * calc(x / 2)%mod;
}
int T;
int main()
{
freopen("G.in","r",stdin);
freopen("G.out","w",stdout);
scanf("%d", &T);
while (T--)
{
scanf("%lld", &n);
printf("%lld\n", calc(n));
}
}H 妍静的数据结构
图的直径默认为，两点间最短距离最长的那个
答案是图的直径+1
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) 42
#endif
using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;
template <typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
const int maxn = 205;
const int inf = maxn + 5;
char s[maxn];
int gr[maxn][maxn];
int d[maxn];
queue<int> q;
int n;
int answer = 0;
void go(int start)
{
for (int i = 0; i < n; i++)
d[i] = inf;
d[start] = 0;
q.push(start);
while (!q.empty())
{
int cur = q.front();
q.pop();
answer = max(answer, d[cur] + 1);
for (int i = 0; i < n; i++)
if (gr[cur][i] && d[i] > d[cur] + 1)
{
d[i] = d[cur] + 1;
q.push(i);
}
}
if (start == 0)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
if (gr[i][j] && d[i] == d[j])
{
cout << -1 << endl;
exit(0);
}
}
}
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%s", s);
for (int j = 0; j < n; j++)
gr[i][j] = s[j] - '0';
}
answer = 0;
for (int i = 0; i < n; i++)
go(i);
cout << answer << endl;
return 0;
}