Problem A. 日麻计算器
- 当$x > 4$的时候,直接输出对应答案
- 当$x \leq 4$时,按照题目公式去计算,和$12\,000$取
max
。注意$z$向上保留到整百的一个比较快的写法是$z' = (z / 100 + !!(z\ \%\ 100)) \times 100$。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T;
scanf("%d", &T);
int a,b;
while (T--)
{
scanf("%d%d", &a, &b);
if (a >= 13) printf("48000\n");
else if (a >= 11) printf("36000\n");
else if (a >= 8) printf("24000\n");
else if (a >= 6) printf("18000\n");
else if (a == 5) printf("12000\n");
else
{
int t = (1 << (2 + a)) * 6 * b;
t = (t / 100 + !!(t % 100)) * 100;
printf("%d\n",min(t,12000));
}
}
return 0;
}
Problem B. 麻将桌绘制
由于$w \times h$最大为$40\,000$,我们可以暴力的判断每一个点是否符合以下两个条件之一。
- 对于圆形,直接带入圆的公式$(x - x_C)^2 + (y-y_C)^2 \leq r^2$即符合条件。
- 对于矩形,我们先通过题目中的两个点判断出$x$和$y$的合法上下界,对于每个点直接判断。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int w,h,xc,yc,r,x1,x2,y1,y2,xmin,xmax,ymin,ymax;
cin >> w >> h >> xc >> yc >> r >> x1 >> y1 >> x2 >> y2;
if (y1 < y2)
{
xmin = x1; xmax = x1 + y2 - y1;
ymin = y1; ymax = y2;
}
if (y1 > y2)
{
xmin = x2 - y1 + y2; xmax = x2;
ymin = y2; ymax = y1;
}
if (x1 < x2)
{
xmin = x1; xmax = x2;
ymin = y2 - x2 + x1; ymax = y1;
}
if (x1 > x2)
{
xmin = x2; xmax = x1;
ymin = y1; ymax = y1 + x1 - x2;
}
assert(xmax - xmin == ymax - ymin && xmax > xmin && ymax > ymin);
for (int i = 0; i < w; i++)
{
for (int j = 0; j < h; j++)
{
bool flag = false;
flag = flag || ((i - xc) * (i - xc) + (j - yc) * (j - yc) <= r * r);
flag = flag || ((xmin <= i && i <= xmax) && (ymin <= j && j <= ymax));
if (flag) printf("/"); else printf("\\");
}
printf("\n");
}
return 0;
}
Problem C. 雀士分麻将
Solution A: 贪心
本题可以直接贪心的来做,正着按照题目要求扫一遍,然后反着用上一次的数据扫一遍取max
即可。注意最后答案可能会超出int
的范围。
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll
const int INF = 0x3f3f3f3f;
const int MAXN = 100000+10;
int n;
int a[MAXN];
int b[MAXN];
void solve()
{
a[0] = a[n+1] = INF;
for(int i = 1; i <= n; i++ ){
b[i] = 1;
}
for(int i = 1; i <= n; i++ ){
if( a[i] > a[i-1] ) b[i] = max( b[i], b[i-1]+1 );
}
for(int i = n; i >= 1; i-- ){
if( a[i] > a[i+1] ) b[i] = max( b[i], b[i+1]+1 );
}
ll ans = 0;
for(int i = 1; i <= n; i++ ){
// printf("%d\n", b[i]);
ans += 1ll*b[i];
}
printf("%lld\n", ans);
}
int main(int argc, char * argv[])
{
scanf("%d", &n);
for(int i = 1; i <= n; i++ ){
scanf("%d", &a[i]);
}
solve();
return 0;
}
Solution B: 图论
我们可以根据相邻两个数的大小关系建立单向边,构成有向图。将所有入度为$0$的点设置为$1$个糖果,然后bfs
向上递增。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct edge{
int to,next;
}e[100010];
int head[100010],cnt;
int I[100010];
inline void ins(int u,int v)
{
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
I[v]++;
}
int n,a[100010],tot[100010];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)scanf("%d",a+i);
for (int i=1;i<n;i++)
{
if (a[i]>a[i+1])ins(i+1,i);
if (a[i]<a[i+1])ins(i,i+1);
}
ll ans=0;
queue<int>q;while (!q.empty())q.pop();
for (int i=1;i<=n;i++)if (!I[i])q.push(i),ans+=(tot[i]=1);
while(!q.empty())
{
int now=q.front(),d=tot[now]+1;q.pop();
for (int i=head[now];i;i=e[i].next)
{
tot[e[i].to]=max(tot[e[i].to],d);
I[e[i].to]--;
if (!I[e[i].to])q.push(e[i].to),ans+=tot[e[i].to];
}
}
printf("%lld\n",ans);
return 0;
}
Problem D. 牌河N对子
求给定的字符串有多少非空子序列,满足其是一个串加其本身。
由于$N \leq 200$,因此我们只需要$O(N^3)$的时间复杂度即可。
符合条件的子序列的第二部分可以从整个字符串的$s_1, s_2, \cdots, s_{|s| - 1}$开始,我们枚举这个起点$i$。
这样我们把字符串分割为两个部分$s[0:i]$和$s[i + 1: |s| - 1]$。
我们只需要求出其公共子序列的方案数即可,同时再减去$s[0:i]$和$s[i + 2: |s| - 1]$的公共子序列的方案数,就是该点的贡献。
求公共子序列的方案数可以在$O(n^2)$的时间复杂度内解决完毕,加上枚举分割点,整体时间复杂度为$O(n^3)$。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 210;
const int mod = 1000000007;
int ans[maxn][maxn];
int res, n;
char ss[maxn];
int work(int l) {
memset(ans, 0, sizeof(ans));
int n1 = l, n2 = n - l - 1;
for(int i=1; i<=n1; ++i)
ans[i][0] = ans[i-1][0] + (ss[i-1] == ss[l] ? 1 : 0);
for(int i=1; i<=n1; ++i)
for(int j=1; j<=n2; ++j) {
ans[i][j] = (ans[i][j-1] + ans[i-1][j])%mod;
if(ss[i-1] != ss[l+j])
ans[i][j] = (ans[i][j] - ans[i-1][j-1] + mod)%mod;
}
return ans[n1][n2];
}
void solve() {
res = 0;
n = strlen(ss);
for(int i=1; i<n; ++i)
res = (res + work(i))%mod;
printf("%d\n", res);
}
int main() {
int t;
scanf("%d", &t);
while(t--) {
scanf("%s", ss);
solve();
}
}
Problem E. 牌墙的深坑
将矩阵周边的格子都放到堆里,这些格子上面是无法盛水的。
每次在堆里挑出一个高度最小的格子 cell,把周围的格子加入到堆里。
这些格子被加入堆的时候,计算他们上面的盛水量。
盛水量 = cell.height - 这个格子的高度
当然如果这个值是负数,盛水量就等于 0。
堆我们可以使用优先队列进行实现。
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 1010;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
int h[MAXN][MAXN];
int vis[MAXN][MAXN];
int n, m;
struct node{
int x, y;
int height;
node(){}
node( int x, int y, int height): x(x), y(y), height(height) {}
};
struct cmp{
bool operator()( node a, node b ){
return a.height > b.height;
}
};
priority_queue<node, vector<node>, cmp> q;
void solve()
{
for(int i = 1; i <= n; i++ ){
vis[i][1] = vis[i][m] = 1;
q.push( node( i, 1, h[i][1]) );
q.push( node( i, m, h[i][m]) );
}
for(int j = 2; j < m; j++ ){
vis[1][j] = vis[n][j] = 1;
q.push( node( 1, j, h[1][j]) );
q.push( node( n, j, h[n][j]) );
}
ll ans = 0;
while( !q.empty() ){
node now = q.top();
q.pop();
int hh = now.height;
for(int i = 0; i < 4; i++ ){
int x = now.x+dx[i];
int y = now.y+dy[i];
if( x < 1 || x > n || y < 1 || y > m ) continue;
if( vis[x][y] ) continue;
vis[x][y] = 1;
if( hh > h[x][y] ){
ans += 1ll*(hh-h[x][y]);
h[x][y] = hh;
}
q.push( node( x, y, h[x][y]) );
}
}
printf("%lld\n", ans);
}
int main(int argc, char * argv[])
{
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++ ){
for(int j = 1; j <= m; j++ ){
scanf("%d", &h[i][j]);
}
}
solve();
return 0;
}
Problem F. 麻将大乱斗
如果$k$含有$2,3,5,7$之外的质因数,答案一定为$0$。
否则问题变成数位之积中恰好有若干个$2,3,5,7$质因子。
直接需要数位dp需要五维状态,如果处理不当,可能会MLE
。
考虑到可能出现的乘积不会很多,使用map
或unordered_map
维护即可。
注意最后输出总积分数时不用取模!
bonus:如果这题改为$n \leq 10\,000$,应该怎么做?
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
int dp[105][66666];
ll k;
char A[105], B[105];
int a[105];
inline int get(ll x)
{
static unordered_map<ll, int> dic;
static int sz = 0;
if (dic.count(x)) return dic[x];
return dic[x] = sz++;
}
int dfs(int pos, ll mul, int lead, int flag)
{
if (mul == 0) return 0;
if (pos == -1) return mul == 1;
int h = get(mul);
if (!flag && !lead && ~dp[pos][h]) return dp[pos][h];
int sum = 0;
int up = flag ? a[pos] : 9;
for (int i = 0; i <= up; i++)
{
if (i == 0 && !lead) continue;
if (i == 0)
sum += dfs(pos - 1, mul, lead && i == 0, flag && i == a[pos]);
else if (mul % i == 0)
sum += dfs(pos - 1, mul / i, lead && i == 0, flag && i == a[pos]);
if (sum >= MOD) sum -= MOD;
}
if (!flag && !lead) dp[pos][h] = sum;
return sum;
}
int solve(char* c)
{
int len = strlen(c);
int pos = 0;
for (int i = 0; i < len; i++)
a[pos++] = c[len - 1 - i] - '0';
return dfs(pos - 1, k, 1, 1);
}
void _minus(char* c)
{
int len = strlen(c);
reverse(c, c + len);
// cout << c << endl;
int flag = 1, len1 = 1;
for (int i = 0; i < len; i++)
{
if (flag)
if (c[i] == '0')
c[i] = '9';
else
c[i]--, flag = 0;
if (c[i] != '0') len1 = i + 1;
}
// cout << "LEN: "<<len1 << endl;
reverse(c, c + len1);
c[len1] = '\0';
}
int fac[] = {2, 3, 5, 7};
int main()
{
memset(dp, -1, sizeof(dp));
int T;
scanf("%d", &T);
long long TT = 0;
while (T--)
{
scanf("%s%s%lld", A, B, &k);
ll K = k;
for (int i = 0; i < 4; i++)
while (K % fac[i] == 0) K /= fac[i];
if (K != 1)
{
printf("0\n");
continue;
}
_minus(A);
int ans = solve(B) - solve(A);
if (ans < 0) ans += MOD;
printf("%d\n", ans);
TT += ans;
}
cout << TT << endl;
}