A. Game Shopping
签.
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define N 1010 5 int n, m, c[N]; 6 queue <int> q; 7 8 int main() 9 { 10 while (scanf("%d%d", &n, &m) != EOF) 11 { 12 while (!q.empty()) q.pop(); 13 for (int i = 1; i <= n; ++i) scanf("%d", c + i); 14 for (int i = 1, x; i <= m; ++i) 15 { 16 scanf("%d", &x); 17 q.push(x); 18 } 19 int res = 0; 20 for (int i = 1; i <= n && !q.empty(); ++i) 21 { 22 if (q.front() >= c[i]) 23 { 24 q.pop(); 25 ++res; 26 } 27 } 28 printf("%d ", res); 29 } 30 return 0; 31 }
B. Minimum Ternary String
签.
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define N 100010 5 char s[N]; 6 int n, cnt; 7 8 int main() 9 { 10 while (scanf("%s", s + 1) != EOF) 11 { 12 n = strlen(s + 1); 13 cnt = 0; 14 for (int i = 1; i <= n; ++i) if (s[i] == '1') 15 ++cnt; 16 bool flag = false; 17 for (int i = 1; i <= n; ++i) 18 { 19 if (flag && s[i] != '1') 20 putchar(s[i]); 21 else if (!flag) 22 { 23 if (s[i] == '0') 24 putchar(s[i]); 25 else if (s[i] == '2') 26 { 27 flag = true; 28 while (cnt--) putchar('1'); 29 putchar(s[i]); 30 } 31 } 32 } 33 if (cnt > 0) while (cnt--) putchar('1'); 34 puts(""); 35 } 36 return 0; 37 }
C. Annoying Present
签.
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define db long double 5 #define ll long long 6 #define N 100010 7 int n, m, x[N], d[N]; 8 9 ll f(int x) 10 { 11 return 1ll * n * (n + 1) / 2 + (1ll * x * x - 1ll * n * x - x); 12 } 13 14 int main() 15 { 16 while (scanf("%d%d", &n, &m) != EOF) 17 { 18 ll Max = (ll)-1e18, Min = (ll)1e18; 19 for (int i = 1; i <= n; ++i) 20 { 21 ll tmp = f(i); 22 Max = max(Max, tmp); 23 Min = min(Min, tmp); 24 } 25 for (int i = 1; i <= m; ++i) 26 scanf("%d%d", x + i, d + i); 27 db res = 0; 28 for (int i = 1; i <= m; ++i) 29 { 30 res += 1ll * n * x[i]; 31 if (d[i] < 0) 32 res += 1ll * d[i] * Min; 33 else 34 res += 1ll * d[i] * Max; 35 } 36 printf("%.10Lf ", res * 1.0 / n); 37 } 38 return 0; 39 }
D. Relatively Prime Graph
签。
$考虑质数的密度很大 并且phi(p) = p - 1 所以暴力找边即可$
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define ll long long 5 #define N 100010 6 #define pii pair <int, int> 7 int n, m; 8 vector <pii> res; 9 int phi[N], prime[N]; 10 bool check[N]; 11 int tot; 12 13 void init() 14 { 15 memset(check, false, sizeof check); 16 phi[1] = 1; 17 tot = 0; 18 for (int i = 2; i < N; ++i) 19 { 20 if (!check[i]) 21 { 22 prime[++tot] = i; 23 phi[i] = i - 1; 24 } 25 for (int j = 1; j <= tot; ++j) 26 { 27 if (i * prime[j] >= N) break; 28 check[i * prime[j]] = true; 29 if (i % prime[j] == 0) 30 { 31 phi[i * prime[j]] = phi[i] * prime[j]; 32 break; 33 } 34 else 35 phi[i * prime[j]] = phi[i] * (prime[j] - 1); 36 } 37 } 38 } 39 40 int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } 41 42 int main() 43 { 44 init(); 45 while (scanf("%d%d", &n, &m) != EOF) 46 { 47 ll sum = 0; 48 for (int i = 2; i <= n; ++i) sum += phi[i]; 49 if (m < n - 1 || m > sum) 50 { 51 puts("Impossible"); 52 continue; 53 } 54 puts("Possible"); 55 for (int i = 2; i <= n; ++i) printf("%d %d ", 1, i); 56 m -= n - 1; 57 vector <int> vec; 58 for (int i = 3; i <= n; ++i) vec.push_back(i); 59 sort(vec.begin(), vec.end(), [](int a, int b) { return phi[a] > phi[b]; }); 60 for (auto it : vec) 61 { 62 for (int i = 2; i < it && m > 0; ++i) if (gcd(it, i) == 1) 63 { 64 printf("%d %d ", it, i); 65 --m; 66 } 67 if (m <= 0) break; 68 } 69 } 70 return 0; 71 }
E. Intercity Travelling
签。
统计$a_i$被计算多少次
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define ll long long 5 #define N 1000010 6 const ll p = (ll)998244353; 7 int n; 8 ll a[N], Bit[N]; 9 10 int main() 11 { 12 while (scanf("%d", &n) != EOF) 13 { 14 for (int i = 1; i <= n; ++i) scanf("%lld", a + i); 15 Bit[0] = 1; 16 for (int i = 1; i <= n; ++i) Bit[i] = (Bit[i - 1] * 2) % p; 17 if (n == 1) 18 { 19 printf("%lld ", a[1]); 20 continue; 21 } 22 ll res = 0; 23 for (int i = 1; i <= n; ++i) 24 { 25 res = (res + Bit[n - i] * a[i] % p) % p; 26 if (n - i - 1 >= 0) 27 res = (res + 1ll * (n - i) * Bit[n - i - 1] % p * a[i] % p) % p; 28 } 29 printf("%lld ", res); 30 } 31 return 0; 32 }