A、招生
思路比较简单，排序+向上取整，注意坑点，分数不可以为负数。
如果wa的应该大部分都是没有考虑负数的情况。可以测下下面这组样例。
1 1 1000000000 100 100
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
const int N = 1e5 + 7;
ll n, m, k;
double a[N];
void solve() {
n = read(), m = read(), k = read();
for (int i = 1; i <= n; ++i) a[i] = read() * 0.85 + read() * 0.15;
sort(a + 1, a + 1 + n, greater<double>());
double x = a[m];
ll ans = ceil((x - k * 0.15) / 0.85);
print(max(ans,0ll));
}
int main() {
//int T = read(); while (T--)
solve();
return 0;
} B、遥远的记忆
查看序列中10串出现的次数，而且连续的1要合并成一个1，连续的0类似。
最终单独的也要计算一次次数。
因为输入不保证第一个是1，所以我就自己修改，把第一个数硬性的改成1，后面的全部改成对应的值即可。
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 5e5 + 7;
int n, m;
int a[N];
void solve() {
int ans = 0, x = 0;
n = read();
a[1] = read();
if (!a[1])
a[1] = 1, x = 1;
for (int i = 2; i <= n; ++i) a[i] = read() ^ x;
for (int i = 1; i <= n;) {
int j = i;
while (j <= n and a[j] == 1) ++j;
while (j <= n and a[j] == 0) ++j;
++ans;
i = j;
}
print(ans);
}
int main() {
//int T = read(); while (T--)
solve();
return 0;
}
C、生涯回忆录
首先题目涉及 mex 操作，那么是不是最极端的情况就是到 n + 1，一共 n 个数不可能出现一个进行 mex 运算得到一个 n + 2 的数。
所以我们可能的答案取值都在 1 到 n + 1之间。
那么我们从1枚举到n+1计算每个数的答案情况就行了。那么如何计算当前数的价值呢？
首先如果我们当前计算的价值是 i 说明 i 的值都不能选了，并且i之前的数一定要每个数都最少选一个。
那么比i小的数方案数是几呢？全部数随便选就是二次幂，但是要减掉一个空集。也就是一定要每个数都选一次最少。
那么比i大的数就可以随便选了，因为我们当前就没有选i。这样就可以不重不漏的选到全部的数。
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 20000311;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 7;
int n, m;
unordered_map<int, int> mp;
void solve() {
n = read();
for (int i = 1; i <= n; ++i) ++mp[read()];
ll ans = 0, l = 1, cnt = n;
for (int i = 1; i <= n + 1; ++i) {
cnt -= mp[i];
ans = (ans + l * qpow(2, cnt, MOD) % MOD * i % MOD) % MOD;
l = l * (qpow(2, mp[i], MOD) - 1) % MOD;
}
print(ans);
}
int main() {
//int T = read(); while (T--)
solve();
return 0;
}
京公网安备 11010502036488号