A.日期统计
写了一个很长的暴搜,第一题就做了四五十分钟,浪费了很多时间,导致后面没什么时间做了....关键这题最后一对答案还特么错了,艹
B.01串的熵
只需要带入公式计算熵,从小到大枚举\(0\)的数量,直至找到为题目给的熵的 \(0\)的个数.注意精度即可
C.冶炼金属
假设某种金属 A 用了 \(p\) 个炼出了 \(q\) 个新的金属,那么转化率 \(x\) 一定不能大于 \(p\div q\) (转化率都是整数).
那么转化率最大不能超过 \(min\{p_i/q_i\}\).
剩下只需要二分转化率的最小值即可.
(赛时脑子抽了加了个 \(p_i\%q_i==0\)的条件,痛失满分,估计只能拿到一点点分了)
点击查看代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
typedef long long LL;
using namespace std;
#define int long long
const int N = 1e6+10;
int a[N],b[N];
int n;
int check(int x)
{
for(int i=0;i<n;i++)
{
if(a[i]/x>b[i])return 0;
}
return 1;
}
signed main()
{
scanf("%lld",&n);
int rr;
int l = 1,r = 2147483647;
for(int i=0;i<n;i++)
{
scanf("%lld%lld",&a[i],&b[i]);
r = min(r,a[i]/b[i]);
}
rr = r;
while(l<r)
{
int mid = (l+r)>>1;
if(check(mid))
{
r = mid;
}
else
{
l = mid+1;
}
}
printf("%lld %lld",l,rr);
return 0;
}
D.飞机降落
比赛时毫无头绪,交了一发\(n<=2\)的情况骗分就润了.
赛后听群友讲了一下发现只是简单的全排列.....挨个枚举一下飞机的顺序就可以了.痛失10分
点击查看代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
typedef long long LL;
using namespace std;
const int N = 1e6+10;
int t[N],d[N],l[N];
int p[100];
int vis[100];
int solve(int n,int step)
{
if(step==n)
{
int start = 0;
for(int i=0;i<n;i++)
{
int now = p[i];
if(start>t[now]+d[now])
{
return 0;
}
else
{
start = max(start,t[now]);
start+=l[now];
}
}
return 1;
}
for(int i=0;i<n;i++)
{
if(!vis[i])
{
vis[i] = 1;
p[step] = i;
if(solve(n,step+1))
return 1;
vis[i] = 0;
}
}
return 0;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d%d%d",&t[i],&d[i],&l[i]);
memset(vis,0,sizeof vis);
if(solve(n,0))
{
printf("YES\n");
}
else printf("NO\n");
}
return 0;
}
E.接龙数列
比赛前只看了一点背包DP,线性DP根本没看,本来以为要寄,还好幸运女神眷顾了一下我,凭借残存的记忆想到了之前做过的最长上升子序列的方法,两层循环肯定是会超时的,类比于最长上升子序列的优化方法,记录一下每种字母的末尾最长长度的下标即可.这样就不需要回溯遍历之前每个单词了.
这题我算是有一定把握的,然后写了个对拍测了十几分钟发现没什么问题就交了.(一个寒假没怎么做题,对拍不会写了浪费了不少时间)
还好赛后在某网站提交自测了一发过了.不然估计要省四了,全程一共没对几道题.
点击查看代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
typedef long long LL;
using namespace std;
const int N = 1e6 + 10;
int a[N];
int dp[N];
int maxlen[10];
int maxid[10];
int getfirst(int x)
{
int t = x;
while (x)
{
t = x % 10;
x /= 10;
}
return t;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
for (int i = 0; i < n; i++)
{
dp[i] = 1;
int t = getfirst(a[i]);
int last = a[i] % 10;
dp[i] = max(dp[i], maxlen[t] + 1);
if (dp[i] >= maxlen[last])
{
maxlen[last] = dp[i];
maxid[last] = i;
}
}
int m = dp[n];
for (int i = 0; i < n; i++)
{
m = max(m, dp[i]);
}
printf("%d", n - m);
return 0;
}
F.岛屿个数
总结
回顾下来全场一共就一道填空和一道编程拿了满分(一共20分).
刚出考场本来还信心满满的,结果跟群友一讨论发现了诸多错误.后面时间仓促,大题都没有写暴力骗分.最后估摸也就二十多分,心灰意冷,寻思拿到省二就知足了,没想到最后出成绩是省一还是有点出乎我的意料的,运气太好了,感觉这次打的这么烂根本配不上省一....