水
#includeusing namespace std;typedef long long ll;const int N = 1e5 + 5;const int INF = 0x3f3f3f3f;int main(void) { int s[5] = {50, 100, 150, 200, 250}; int m[5], w[5], hs, hu; for (int i=0; i<5; ++i) { scanf ("%d", &m[i]); } for (int i=0; i<5; ++i) { scanf ("%d", &w[i]); } scanf ("%d%d", &hs, &hu); int ans = 0; for (int i=0; i<5; ++i) { ans += max (3 * s[i], (250 - m[i]) * s[i] * 10 / 250 - 50 * w[i]); } ans += hs * 100 - hu * 50; printf ("%d\n", ans); return 0;}
(二分)+贪心
题意:n个物品最多放在k个盒子里,每个盒子最多放两个,问盒子的体积最小是多少.
分析:可以二分枚举体积大小,那么判断是否满足条件时需要贪心,如题解所说,如果k > n,那么体积就是单个中最大的.否则一定有n-k个盒子一定要放两个物品(解方程),那么优先选择组合体积小的,也就是前2 * (n - k)个物品前后组合,然后选取最大值和后面2*k-n个再取最大值就是答案.所以发现二分其实不需要用...
#includeusing namespace std;const int N = 1e5 + 5;int a[N];int main(void) { int n, k; scanf ("%d%d", &n, &k); for (int i=1; i<=n; ++i) scanf ("%d", &a[i]); int ans = a[n];; for (int i=1; i<=n-k; ++i) { ans = max (ans, a[i] + a[2*(n-k)-i+1]); } printf ("%d\n", ans); return 0;}
二分版
#includeusing namespace std;typedef long long ll;const int N = 1e5 + 5;const int INF = 0x3f3f3f3f;int a[N];bool vis[N];int n, k;int check(int s) { memset (vis, false, sizeof (vis)); int j = 1, ret = 0; for (int i=n; i>=1; --i) { if (j < i) { if (a[j] + a[i] <= s) { vis[j] = vis[i] = true; j++; } else vis[i] = true; ret++; } else if (j == i) { if (!vis[i]) ret++; break; } } return ret;}int main(void) { scanf ("%d%d", &n, &k); for (int i=1; i<=n; ++i) { scanf ("%d", &a[i]); } if (n == 1) { printf ("%d\n", a[1]); return 0; } int l = a[n], r = a[n-1] + a[n]; while (l + 1 <= r) { int mid = (l + r) >> 1; if (check (mid) <= k) r = mid; else l = mid + 1; } int ans = r; printf ("%d\n", ans); return 0;}
DP || 数学/构造
题意:有01串,可以选取任意长度的字串进行一次翻转(0->1, 1->0), 问形如01010110或1010101的最大长度.
分析:中间断开的可能是00或11型 或者只有一个1或0型.比如10110101 -> 10101010即蓝色部分为翻转后的,可见长度+1.还有一种:1011110101 -> 1010110101长度+2,所以ans = min (n, ret + 2);
下午想了很久的网上的DP做法,dp[i][j][k]表示第i位数字为j状态为k时的最大长度.主要想说我对第三维理解,k = 0表示没有改变,k=1表示改变,那么根据题意有一段是改变的,那么从1到2就是从变到不变
构造:
#includeusing namespace std;const int N = 1e5 + 5;char str[N];int main(){ int n; scanf ("%d%s", &n, str); int ans = 1; for (int i=1; i
DP:
#includeusing namespace std;const int N = 1e5 + 5;char str[N];int dp[N][2][3];int n;void _max(int &a, int b) { if (a < b) a = b;}int run(void) { memset (dp, -1, sizeof (dp)); dp[0][0][0] = dp[0][1][0] = 0; for (int i=0; i
置换群
题意：问所有的方案%MOD使得：f(k*x%p) == k * f(x) % p
分析：考虑特殊的情况，k=0， f(0) = 0, 其他随便，所以是p^(p-1); k=1，f (x) == f (x), 所以是p^p。然后考虑假设f (x1) % p = k * f (x2) % p, f (x2) % p = k * f (x3）% p.....最后有f (x1) = k ^ m * f (x1)，显然有k ^ m = 1才能成立。循环节长度为m，个数有(p - 1) / m(?)，x1的选则有p种，所以答案是 p ^ ((p-1) / m)
#includeusing namespace std;const int MOD = 1e9 + 7;int pow_mod(int x, int n) { int ret = 1; while (n) { if (n & 1) { ret = 1ll * ret * x % MOD; } x = 1ll * x * x % MOD; n >>= 1; } return ret;}int main(void) { int p, k; scanf ("%d%d", &p, &k); if (k == 0) { printf ("%d\n", pow_mod (p, p-1)); } else if (k == 1) { printf ("%d\n", pow_mod (p, p)); } else { int cur = k, ord = 1; while (cur != 1) { cur = 1ll * cur * k % p; ord++; } printf ("%d\n", pow_mod (p, (p-1)/ord)); } return 0;}