Day 1
小菜鸡的第一天
一、当日总结
今天的题单是牛客网的练习赛75和竞赛域的提高篇和基础篇,一个上午敲着这能通过一星半点测试点的代码、看着不一定能看懂的题解,感到非常的力不从心。
二、题目回顾
2.1 广义斐波
这题的关键在于对同余性质的了解
m^(p-1)与p互质 m与p互质
有了这个条件,对指数的更新也就非常的便捷
#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e5+5;
const int MOD=1e9+7;
int main()
{
long long a,b,m,n;
long long f[N]={
0,1,1};
cin>>a>>b>>m>>n;
for(int i=3;i<=n;i++)
f[i]=(f[i-1]*a%(MOD-1)+f[i-2]*b%(MOD-1))%(MOD-1);
long long ans=1;
long long k=m;
while(f[n]){
if(f[n]%2) ans=(ans*k)%MOD;
f[n]>>=1;
k=(k*k)%MOD;
}
cout<<ans;
return 0;
}
2.2 魔法石
这里思考的点在于较小情况的考虑:
1)只有一棵树:直接求解
2)两棵树可以交换偶数次:相当于没有交换,直接求解
3)两棵树可以交换奇数次:取最优结构<最低减抗和最大魔力>
4)大于两棵树:最优情况
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
int n, m, k;
int a[N], b[N];
LL f[N];
int main()
{
cin >> n >> m >> k;
int maxed = 0, mined = 1e3;
for (int i = 1; i <= n; i ++)
{
cin >> a[i];
mined = min(mined, a[i]);
}
for (int i = 1; i <= n; i ++)
{
cin >> b[i];
maxed = max(maxed, b[i]);
}
if (n == 1 || (k && n > 2)) cout << (LL)m / mined * maxed;
else
{
if (k & 1) swap(b[1], b[2]);
for (int i = 1; i <= n; i ++)
for (int j = a[i]; j <= m; j ++)
f[j] = max(f[j], f[j - a[i]] + b[i]);
cout << f[m] << endl;
}
return 0;
}
2.3 减数
这题的关键在于使用优先队列的时候不能改变(由于取模导致)数之间的合并顺序,所以通过优先队列保证的单调性,用朴素队列实现整个算法过程
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int Mod = 1e9 + 7;
priority_queue<ll,vector<ll>,greater<ll> >q;//大顶堆
queue<ll> qq;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
ll n, k;
cin >> n >> k;
ll mx = 0;
for (int i = 1; i <= n; i++) {
ll tmp;
cin >> tmp;
q.push(tmp);
mx = max(mx, tmp);
}
if (n == 1) {
cout << q.top() << endl;
return 0;
}
while (q.size() > 1) {
ll u = q.top();
q.pop();
ll v = q.top();
q.pop();
ll tmp = u * v + k;
if (tmp >= mx) {
qq.push(u);
qq.push(v);
break;
}
q.push(tmp);
}
while (!q.empty()) {
qq.push(q.top());
q.pop();
}
while (qq.size() > 1) {
ll u = qq.front();
qq.pop();
ll v = qq.front();
qq.pop();
qq.push((u * v + k) % Mod);
}
cout << qq.front() << endl;
}
2.4 计数问题
原题很简单:
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
int n, x;
cin >> n >> x;
int ans = 0;
for (int i = 0; i <= n; i++){
int xx = i;
while (xx > 0){
if (xx % 10 == x)ans++;
xx /= 10;
}
}
cout << ans;
return 0;
}
拓展:
数据量大时的思路:
对不同的数量级计算增加
排列组合思想插入所需数
……
VaQX·青
2021.01.23