目录
A – chmin
题意
思路
正解代码
B – Pepper Addiction
题意
思路
正解代码
C – Except and Min
题意
思路
正解代码
D – Integer-duplicated Path
题意
思路
正解代码
E – Simple Division
题意
思路
正解代码
B – Pepper Addiction
C – Except and Min
D – Integer-duplicated Path
E – Simple Division
A – chmin
题意
题目的意思大致是：给我们一个长度为 n 的数列和一个数 x ，对其从头到尾进行遍历，在遍历到 A[i] 时，我们会依据如下条件进行输出：
1.如果 A[i] < x ，将 x 更新成 A[i] 并输出 1。
2.除此之外，输出 0。
思路
进行 O(n) 的遍历，对于每一个 A[i] 进行判断并完成对应输出。
正解代码
#include<bits/stdc++.h>
using namespace std;
const int N= 105;
int T;
inline void solve()
{
int n,x;
int a[N];
cin>>n>>x;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
if(a[i] < x) {
x = a[i];
cout<<1<<'\\n';
}
else cout<<0<<'\\n';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
T = 1;
while(T–) solve();
return 0;
}
B – Pepper Addiction
题意
这道题目的意思大致是：我们有 m 种辣椒，对于品种 j 的辣椒，我们有 Cj 克。现在给出 n 个点餐信息，对于菜品 i ，我们只能放品种为 A[i] 的辣椒，并且最多放 B[i] 克。问，我们最多能用掉多少辣椒。
思路
很明显，如果我们要尽可能地多放辣椒，就要在每一个菜品中都尽可能地多放对应品种的辣椒。
于是，我们进行 O(n) 的遍历，对于每一个菜品，如果对应的辣椒还有剩余，就尽可能放完。
正解代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1005;
int n,m;
int c[N];
int a[N], b[N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>c[i];
for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
int ans = 0;
for(int i=1;i<=n;i++)
{
ans += min(b[i],c[a[i]]);
c[a[i]] = max(0ll,c[a[i]] – b[i]);
}
cout<<ans;
return 0;
}
C – Except and Min
题意
题目的大致意思是：我们有 n 个球，球 i 上写着数字 a[i] ，我们需要进行 q 次操作，每次操作给出 k 和 k 个数字，我们需要删除数字对应的球，然后输出最小的目前球上写的数字，再将它们都放回去。
思路
在看完这个题目之后，我们很快就可以想到需要使用 map ，用 map 来记录每一个球上的数字对应的球的个数，每次删除都数量减一，如果为 0 ，则移除 map 中的这一键值对，最后输出 map 最前面的键。
整个算法复杂度为 O(nlogn) ，可以完美通过本题。
正解代码
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+5;
int n,q;
int a[N];
int k;
map<int,int>mp;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i], mp[a[i]] ++;
while(q–)
{
cin>>k;
vector<int>B;
for(int i = 1;i<=k;i++) {
int x;
cin>>x;
B.push_back(x);
}
for(int i:B)
{
mp[a[i]] –;
if(mp[a[i]] == 0){
auto it = mp.find(a[i]);
mp.erase(it);
}
}
auto it = mp.begin();
cout<<it -> first<<'\\n';
for(int i:B) mp[a[i]] ++;
}
return 0;
}
D – Integer-duplicated Path
题意
题目的意思大致是：我们有一棵节点数为 n 的树，给出它的边信息和点权数组 a 。对于点 k (1~n)，要求我们判断从 1 到 k 的简单路径上存不存在两个点权相等的点。
思路
很显然，由于我们求的路径都是从 1 到 某个点 ，所以我们以 1 为根节点进行建树。
我们从 1 开始深搜，然后，维护一个 map 变量来记录目前存在在路径上的点权，对于每一个新加入的点进行判断并将已存在重复的信息传递下去就可以顺利完成这道题目了。
整个算法的复杂度是 O(nlogn) ，可以顺利通过本题。
正解代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n;
int a[N];
bool ans[N];
map<int,int>mp;
vector<int>e[N];
inline void dfs(int x, int fa, bool now)
{
if(mp[a[x]] || now){
ans[x] = true;
}
else ans[x] = false;
mp[a[x]] ++;
for(int i:e[x])
{
if(i == fa) continue;
dfs(i,x,ans[x]);
}
mp[a[x]] –;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1,0,false);
for(int i=1;i<=n;i++) cout<<(ans[i]?"Yes":"No")<<'\\n';
return 0;
}
E – Simple Division
题意
题目的大致意思是：我们有一个被除数 N 和一个除数 M ，我们最终需要输出 (N / M ) 向下取整再 mod 10007 的值。我们的 N 一开始是 0 ，我们要进行 k 次操作，每次操作给出一个 c 和 一个 l，我们需要将 l 个 c 加入到 N 的尾部。
思路
由于 c 和 l 都是极大的值，所以我们想要使用迭代来求出 N 的值是不现实的事情，这时候我们想到了快速幂。
对于每一次操作，我们先把 N 乘以 10 的 l 次 ，然后加上 l 个 c，后者也是比较好求的，我们模仿快速幂的操作写一个函数就可以了，也是 logl 的复杂度。
但是，我们最终的结果是 N/M 向下取整再对 mod = 10007 取模，所以我们快速幂取模时不可以直接选择 mod。那么我们该选择什么模数呢？
答案是 mod * M 。为什么呢？
等价于
这样，我们在快速幂的过程中取模就不会影响到最终结果了。
整个算法的复杂度是 O(klog l) ，能够完美通过本题。
除此之外，我们还可以用矩阵快速幂处理中间的过程，不过结果是一样的。
正解代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M = 1e4+5, K = 1e5+5, L = 1e9+5;
int mod = 10007;
int m,k;
int c[K],l[K];
inline int qpower1(int x, int y)
{
int res = 1;
for(;y;y>>=1, x=x*x%mod) if(y&1) res=res*x%mod;
return res;
}
inline int qpower2(int x,int y)
{
int res = 0;
int base = 10;
int now = x;
for(;y;y>>=1, now = (now*base%mod + now) % mod , base = base*base%mod) if(y&1) res = (res*base%mod + now)%mod;
return res;
}
signed main()
{
cin>>k>>m;
mod *= m;
for(int i=1;i<=k;i++) cin>>c[i]>>l[i];
int ans = 0;
for(int i=1;i<=k;i++) ans = (ans*qpower1(10,l[i])%mod + qpower2(c[i],l[i])%mod)%mod;
mod /= m;
ans = ans/m%mod;
cout<<ans;
return 0;
}
以上就是这篇文章的全部内容了。
