牛客小白月赛90
比赛链接https://ac.nowcoder.com/acm/contest/78306
A.小A的文化节
直接暴力求解，找到相应的下标求和
#include <bits/stdc++.h>
#define ll long long
const ll N = 1e6 + 100;
ll dp1[N],dp2[N],dp3[N];
void solve(){
ll n,m;
std::cin >> n >> m;
std::vector<ll> op(n + 1);
for(ll i = 1; i <= n; i ++){
std::cin >> op[i];
}
ll res = 0;
for(ll i = 1; i <= m; i ++){
ll a;
std::cin >> a;
res += op[a];
}
std::cout << res << "\n";
return ;
}
int main(){
// init();
ll t = 1;
while(t --)
solve();
return 0;
}
B.小A的游戏
赢就有三分，输没有分，平就是1分。显然两个人平局次数应该是相等或者相差3的倍数，所以将两人的得分除余3，结果如果相等就代表正确，反之错误。
#include <bits/stdc++.h>
#define ll long long
const ll N = 1e6 + 100;
ll dp1[N],dp2[N],dp3[N];
void solve(){
ll n,m;
std::cin >> n >> m;
n %= 3;
m %= 3;
if(n != m){
std::cout << "No\n";
}
else{
std::cout << "Yes\n";
}
return ;
}
int main(){
// init();
ll t = 1;
std::cin >> t;
while(t --)
solve();
return 0;
}
C.小A的数字
题目意思是求最小的正整数，使得与n的每一位都不相同。这里用字符串进行存储每一位（方便补零），之后进行判断0的话就是1最小，不是0的话就是0最小。但是有一个弊端，就是有可能结果是0，不满足正整数要求，所以还要判断如果最终判断后的结果是0的话看第一个数位是1还是其他，是1的话就是2，反之就是1。
#include <bits/stdc++.h>
#define ll long long
const ll N = 1e6 + 100;
ll dp1[N],dp2[N],dp3[N];
void solve(){
ll n;
std::cin >> n;
std::vector<ll> op(100);
ll re = 0;
while(n){
op[++ re] = n % 10;
n /= 10;
}
std::string aa = "";
for(ll i = 1; i <= re; i ++){
if(op[i] > 0){
aa += '0';
}
else{
aa += '1';
}
}
reverse(aa.begin(),aa.end());
ll mm = aa.size();
bool ok = false;
for(ll i = 0; i < mm; i ++){
if(aa[i] == '0'){
if(ok == false) continue;
else std::cout << aa[i];
}
else{
ok = true;
std::cout << aa[i];
}
}
if(ok == false){
if(op[1] == 1) std::cout << '2';
else std::cout << '1';
}
std::cout << "\n";
return ;
}
int main(){
// init();
ll t = 1;
std::cin >> t;
while(t --)
solve();
return 0;
}
D.小A的线段（easy version）
由于这题m的范围较小，所以用dfs就可以通过。
dfs的思想就是遍历每一种情况，遍历到一种就只有选与不选的情况。这时候可以用字符串来记录具体情况比如字符串0110，这就可以代表选2和3的线段。统计完之后搜索有多少种满足情况的就行了。
#include <bits/stdc++.h>
#define ll long long
const ll N = 1e6 + 100;
const ll mod = 998244353;
ll n,m;
ll dp1[N],dp2[N],dp3[N];
std::map<std::string,ll> op;
ll dis[N];
struct ii{
ll a;
ll b;
}pp[N];
void dfs(ll i,std::string aa,ll uu){
if(i > m){
if(uu >= n){
op[aa] ++;
}
return ;
}
dfs(i + 1,aa + '0',uu);
ll kk = 0;
for(ll j = pp[i].a; j <= pp[i].b; j ++){
dis[j] ++;
}
for(ll j = 1; j <= n; j ++){
if(dis[j] >= 2) kk ++;
}
dfs(i + 1,aa + '1',kk);
for(ll j = pp[i].a; j <= pp[i].b; j ++){
dis[j] --;
}
}
void solve(){
std::cin >> n >> m;
for(ll i = 1; i <= m; i ++){
ll a,b;
std::cin >> a >> b;
pp[i] = {a,b};
}
dfs(1,"",0);
ll kk = op.size();
std::cout << kk % mod << "\n";
return ;
}
int main(){
// init();
ll t = 1;
// std::cin >> t;
while(t --)
solve();
return 0;
}
E.小A的任务
这题的意思是，选A的话，前面的A必须都得选，选B的话对应的A必须要选。所以A是必须从头到尾遍历的选，而B可以选择，这时候只需要选一个区域内最小的前x个就行，这时候就能想到用优先队列来选择B，这样遍历到大于要选的个数时可以把最大的删掉就行。
#include <bits/stdc++.h>
#define ll long long
const ll N = 1e6 + 100;
const ll mod = 998244353;
ll n,m,q;
ll dp1[N],dp2[N],dp3[N];
ll dis[N];
void solve(){
std::cin >> n >> q;
std::vector<ll> opA(n + 1),opB(n + 1);
for(ll i = 1; i <= n; i ++){
std::cin >> opA[i];
}
for(ll i = 1; i <= n; i ++){
std::cin >> opB[i];
}
std::priority_queue<ll> pkp;
for(ll i = 1; i <= n; i ++){
pkp.push(opA[i]);
}
while(q --){
ll aa;
std::cin >> aa;
std::priority_queue<ll> pk;
ll res = 0;
ll ans = 0;
ll sum = 1e17;
for(ll i = 1; i <= n; i ++){
if(i <= aa){
pk.push(opB[i]);
ans += opB[i];
res += opA[i];
if(i == aa){
sum = std::min(sum,ans + res);
}
}
else{
pk.push(opB[i]);
ans += opB[i];
auto jj = pk.top();
ans -= jj;
pk.pop();
res += opA[i];
sum = std::min(sum,ans + res);
}
}
std::cout << sum << "\n";
}
return ;
}
int main(){
// init();
ll t = 1;
// std::cin >> t;
while(t --)
solve();
return 0;
}
F.小A的线段（hard version）
看题解要用上离散化，人麻了，呜呜呜真不会了
