C题应该是最好的一道题
| A | 阿宁的柠檬 |
分析：
酸度是[1,a] 甜度是[0,b]总共有n个柠檬，问最小快乐值和最大快乐值
最小就是 n 最大就是 n * (a + b)
void solve()
{
cin>>a>>b>>n;
cout<<1ll * 1 * n + 1ll * 0 * n<<' '<<a * n + b * n<<endl;
}
| B | 阿宁与猫咪 |
最近阿宁的房子附近有猫咪喵喵叫，阿宁很烦躁。
阿宁对自己施展隔音膜法。该膜法需要构造一个长度为 n 的正整数数组 a，需要满足 a 数组的所有数总和等于 m。假设 a 数组的奇数位的数的乘积为 u，偶数位的数的乘积为 v，阿宁烦躁值为 u+v。
奇数位的数指第1,3,5 ....个数，偶数位的数指第2,4,6 ....个数。如果不存在奇数位的数，u 视为 0，如果偶数位的数不存在，则 v 视为 0。
阿宁想施展膜法使得她的烦躁值最小，问构造的数组是什么？
分析
输入只有一个 n 。。。。
所以只要输出 n 个 1 就可以找到最小的 烦躁值。。
void solve()
{
// cin>>n>>m;
cin>>m;
cout<<m<<endl;
fo(i,1,m) {
cout<<1<<' ';
}
}
| C | 阿宁吃粽子 |
链接：https://ac.nowcoder.com/acm/contest/39100/C
来源：牛客网
阿宁的公司给阿宁发了各种口味的粽子。
一共有 n 条粽子，每条粽子有个美味值 ai。
阿宁想立即吃下全部。吃下第 k 条粽子时，该粽子的美味值是 x，阿宁获得 2^{k mod10 } x的愉悦值。（k 从 1 开始）
阿宁想安排一下吃粽子的顺序，使她获得的愉悦值最大。
链接：https://ac.nowcoder.com/acm/contest/39100/C
来源：牛客网
输入描述:
第一行输入一个正整数 nnn。第二行输入 nnn 个正整数 aia_iai，aia_iai 表示第 iii 条粽子的美味值。 1≤n,ai≤2×1051\leq n, a_i \leq 2 \times 10^51≤n,ai≤2×105
输出描述:
一行输出 n个正整数，第 j个数表示吃下的第 j条粽子的美味值。
如果有多解，请把美味值较大的粽子，安排到后面。（好吃的留到后面）
分析：
愉悦值越大的粽子越靠近第 9 位，小的数字放到小的位置，最小的数字放在第十位，并且如果它们的愉悦值一样，就把越早出现的粽子放到前面，就可以了。
出现了类似字典序的东西，所以，我们将所有粽子以愉悦值位第一关键字从大到小，以出现时刻 i 为第二关键字，从小到大排序
然后将它们按照由大到小的顺序挨个放到可以放的地方。
如何确定 0~9 每个数字能放的个数？
遍历一遍所有数，for(int i = 1;i<=n;i++) p[i%10].pb(i)；即可确定每一个位置需要放多少数，并且每个数是在那个位置
如何保证由大到小，并且按照字典序放？
从9开始遍历到0。
of(i,9,0)
fo(j,0,p[i].size()-1)
ans[p[i][j]] = a[++cnt].x;
//#define int ll
const int N = 1e5+10;
int n,m;
V<int> p[10];
struct node {
int num,id;
}a[200010];
int ans[200010]
bool cmp(node a,node b) {
if(a.num != b.num) return a.num > b.num;
return a.id < b.id;
}
void solve()
{
// cin>>n>>m;
cin>>n;
fo(i,1,n) {
int x;cin>>x;
a[i] = {x,i};
}
of(i,n,1) p[i%10].pb(i);
sort(&a[1],&a[n+1],cmp);
int cnt = 0;
of(i,9,0) {
m = p[i].size();
fo(j,0,m-1) {
ans[p[i][j]] = a[++cnt].num;
}
}
fo(i,1,n) cout<<ans[i]<<' ';cout<<endl;
}
| D | 阿宁的质数 |
链接：https://ac.nowcoder.com/acm/contest/39100/D
来源：牛客网
题目描述
阿宁有一个长度为 nnn 的正整数数组 aaa，她有很多次询问，每次询问：在数组 aaa 的前 xxx 个数中，未出现的最小质数是多少？分析：
就是找还没出现的数的最小质数
用set维护还没出现的质数，每次加入质数，就将set中的质数删除，并输出set中的第一个质数就可以了
const int N = 4e6+10;
int n,m,q;
int a[N];int ans[N];int primes[N],st[N];
int cnt;
set<int> k;
void solve()
{
cin>>n>>q;
fo(i,1,n) {
cin>>a[i];
if(k.count(a[i])) {
k.erase(a[i]);
}
ans[i] = *k.begin();
}
while(q -- ) {
int x;cin>>x;
cout<<ans[x]<<endl;
}
}
void main_init() {
for(int i = 2;i<N;i++) {
if(!st[i]){
primes[cnt ++ ] = i;
k.insert(i);
}
for(int j = 0;primes[j] * i < N;j++) {
st[primes[j] * i] = primes[j];
if(i % primes[j] == 0) break;
}
}
}
| E | 阿宁睡大觉 |
链接：https://ac.nowcoder.com/acm/contest/39100/E
来源：牛客网
题目描述
分析：
只有连续的大写Z可以起作用
维护一个最大值，先将所有相邻的Z 所能产生的睡觉质量累加起来，同时用向量存储每两个大写的之间的距离
将向量按从小到大的顺序排序，每消除一次这个距离，睡眠质量就 + 4
const int N = 1e5+10;
int n,m,k;
string s;
void solve()
{
cin>>m>>k;
string s;
cin>>s;
ll res = 0;
int id = 0;
V<int> v;
while(s[id] == 'z' && id < m) id ++ ;
for(int i = id;i< m - 1 ;) {
if(s[i+1] == 'Z') {
res += 4;
i ++ ;
} else {
int j = i+1;
while(j < m && s[j] == 'z') j ++ ;
if(j < m) v.pb(j-i-1);
i = j;
}
}
sort(all(v));
for(auto x:v) {
if(k >= x) res += 4;
k -= x;
}
cout<<res<<endl;
}
| F | 阿宁去游玩 |
分析：
一开始以为倒转膜法只会改变一个城市的属性，然后才知道是所有城市，那直接从一号点跑一边最短路到 n 号点，距离就是 x + z 或者 x 或者 y ，取满足条件的最小值就好了。。。
const int N = 4e5+10;
int n,m,x,y,z;
int h[N],ne[N],idx,e[N];void add(int a,int b) {e[idx] = b,ne[idx] = h[a],h[a] = idx ++ ;}
ll a[N],dist[N];
bool vis[N];
void dijkstra() {
ms(dist,0x3f);
dist[1] = 0;
priority_queue<pii,V<pii>,greater<pii>> q;
q.push({0,1});
while(q.size()) {
auto t = q.top();q.pop();
if(vis[t.y]) continue;
vis[t.y] = 1;
fe(i,t.y) {
int j = e[i];
int k = inf;
if(a[t.y] == a[j]) {
k = min(x,y + z);
} else {
k = min(y,x + z);
}
if(dist[j] > dist[t.y] + k) {
dist[j] = dist[t.y] + k;
q.push({dist[j],j});
}
}
}
}
void solve()
{
ms(h,-1);
cin>>n>>m>>x>>y>>z;
fo(i,1,n) cin>>a[i];
while(m -- ) {
int a,b;cin>>a>>b;add(a,b);add(b,a);
}
dijkstra();
cout<<dist[n]<<endl;
}
标签：dist,粽子,int,void,56,cin,牛客,小白月赛,阿宁 From： https://www.cnblogs.com/er007/p/16634582.html