A 阿宁的柠檬
题目
思路
签到
代码：
#include <bits/stdc++.h> using namespace std; int main() { long long a, b, c; cin >> a >> b >> c; cout << c << " " << (a + b) * c << endl; return 0; }
B 阿宁与猫咪
题目
思路
签到
代码
#include <bits/stdc++.h> using namespace std; int main() { int m; cin >> m; cout << m << endl; for (int i = 0; i < m; i++) cout << 1 << " "; return 0; }
C 阿宁吃粽子
题目
思路
以10分组，每组从后往前，所占权重递减，那么就从后往前，从大往小的放。
但是最后可能有多余的 n % 10 个位置，权重还需要和（每组已经放到剩 n % 10 个位置）去参与比较，从大往小放。
实际上的实现：直接拿每个位置（x%10）进行排序即可。那么这里可以用优先队列实现，第一维（i % 10：“权”），第二维（i：实际位置）。
代码
#include <bits/stdc++.h> using namespace std; const int N = 200010; priority_queue<pair<int, int>> q; int a[N], res[N]; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; q.push({i % 10, i}); } sort(a + 1, a + 1 + n); int s = n; while (q.size()) { auto x = q.top(); q.pop(); res[x.second] = a[s--]; } for (int i = 1; i <= n; i++) cout << res[i] << ' '; cout << endl; return 0; }
D 阿宁的质数
题目
思路
质数的话，首先预处理一下2e5个质数，也就是 N 的大小 3e6，能跑出2e5多一点的质数。
然后处理前缀最小未出现的质数
实际上就是开个map映射当前出现过的数字，然后一个指针指向prime数组，向后移动即能保证每次输出的是最小的质数。
代码
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 3e6; int a[N >> 3]; int primes[N], st[N], cnt; int res[N]; void get_primes(int n) // 线性筛质数 { for (int i = 2; i <= n; i ++ ) { if (!st[i]) primes[cnt ++ ] = i; for (int j = 0; primes[j] <= n / i; j ++ ) { st[primes[j] * i] = true; if (i % primes[j] == 0) break; } } } map<int, int> mp; signed main() { get_primes(N - 1); int n, q; cin >> n >> q; for (int i = 1; i <= n; i++) cin >> a[i]; int l = 0; for (int i = 1; i <= n; i++) { mp[a[i]] = 1; while (mp[primes[l]]) l++; res[i] = l; } for (int i = 1; i <= q; i++) { int x; cin >> x; cout << primes[res[x]] << endl; } return 0; }
E 阿宁睡大觉
题目
思路
int n, k; string s; map<int, int> mp; vi v; void solve() { cin >> n >> k; cin >> s; for (int i = 0; i < s.sz; i++) { if (s[i] == 'Z') { int j = i + 1; while (j < s.sz && s[j] == 'z') j++; if (j < s.sz && j - i - 1 > 0) { v.pb(j - i - 1); } i = j - 1; } } int res = 0; for (int i = 0; i < s.sz - 1; i++) if (s[i] == 'Z' && s[i + 1] == 'Z') res += 4; sort(all(v)); for (auto x: v) { if (k >= x) k -= x, res += 4; } cout << res << endl; }
F 阿宁去游玩
题目
思路
实际上边权就两种 min(x,y+z) or min(y,x+z)。
因为施展魔法，只会影响当前选中的这条边。选最优的走法就行。
然后就是建边跑dijkstra的板子…
代码
#include<bits/stdc++.h> // #include <bits/extc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define fi first #define sz size() #define se second #define endl ('\n') #define pb push_back #define ll long long #define int long long #define vi vector<int> #define eb emplace_back #define lowbit(x) (x & -x) #define PII pair<int, int> #define pqu priority_queue<int> #define vii vector<vector<int>> #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define pql priority_queue<int,vi,greater<int>> #define rep(i,a,n) for(ll i = (a); i < (n); ++i) #define Rep(i,a,n) for(ll i = (a); i <= (n); ++i) #define lb(v,x) (lower_bound(all(v),x)-(v).begin()) #define ub(v,x) (upper_bound(all(v),x)-(v).begin()) #define Dbug(x) (cout << #x << " <=> " << x << endl) #define IOS cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(false); #define print(x,s,e) { Rep(i,s,e) cout << x[i] << ' '; cout << endl; } const int N = 250010, M = N << 1; const int mod = 1000000007; // 998244353; using namespace std; using namespace __gnu_pbds; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; /*---------------------------------------------------------------------------------------------------------------------------*/ ll gcd(ll a, ll b){ if(b == 0){return a;} return gcd(b, a%b);} ll lcm(ll a, ll b){ return (a * (b / gcd(a, b)));} ll qmi(ll a, ll b){ if(!b) return 1ll; if(b&1) return a*qmi(a*a%mod, b>>1)%mod; return qmi(a*a%mod, b>>1)%mod;} /*---------------------------------------------------------------------------------------------------------------------------*/ int n, m; int x, y, z; // x // y // x + z < y // z + x int h[N], e[M], ne[M], w[M], idx; int A[N]; int dis[N]; bool st[N]; void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; } void dijkstra() { priority_queue<PII, vector<PII>, greater<PII>> q; memset(dis, 0x7f, sizeof dis); q.push({0, 1}); dis[1] = 0; while (q.size()) { auto t = q.top(); q.pop(); int d = t.fi, u = t.se; if (st[u]) continue; st[u] = 1; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (dis[j] > d + w[i]) { dis[j] = d + w[i]; q.push({dis[j], j}); } } } } void solve() { cin >> n >> m; cin >> x >> y >> z; memset(h, -1, sizeof h); x = min(x, z + y), y = min(y, z + x); for (int i = 1; i <= n; i++) cin >> A[i]; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; if (A[u] == A[v]) { add(u, v, x), add(v, u, x); } else { add(u, v, y), add(v, u, y); } } dijkstra(); cout << dis[n] << endl; } signed main() { IOS int _ = 1; // cin >> _; while(_--) { solve(); } return 0; }
