Codeforces Round 861 (Div. 2) A-E2

题目链接：Dashboard - Codeforces Round 861 (Div. 2) - Codeforces

A - Lucky Numbers

解题思路：大于100就直接输出最大值，小于的话就暴力一下。

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)|1
typedef long long ll;
using ull = unsigned long long;
const int mx = 1e5 + 10;
const int mod = 1e9 + 7;int main() {auto solve = [](int x) {int mi = 100, ma = -1;while (x) {int v = x % 10;ma = max(ma, v);mi = min(mi, v);x /= 10;}return ma - mi;};int t;scanf("%d", &t);while(t--) {int l, r;scanf("%d%d", &l, &r);if (r - l >= 100) {int v = l / 100 * 100 + 90;if (v < l)printf("%d\\n", v + 100);else printf("%d\\n", v);continue;}int ans = -1,p;while (l <= r) {int val = solve(l);if (ans < val) {ans = val;p = l;}l++;}printf("%d\\n", p);}return 0;
}

B - Playing in a Casino

解题思路：按列进行排序，然后算一下每个数的正负值贡献

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)|1
typedef long long ll;
using ull = unsigned long long;
const int mx = 3e5 + 10;
const int mod = 1e9 + 7;vector <int> vec[mx];int main() {auto solve = [](int x) {int mi = 100, ma = -1;while (x) {int v = x % 10;ma = max(ma, v);mi = min(mi, v);x /= 10;}return ma - mi;};int t;scanf("%d", &t);while(t--) {int n,m,v;scanf("%d%d", &n, &m);for (int i=1;i<=m;i++)vec[i].clear();for (int i=1;i<=n;i++) {for (int j=1;j<=m;j++) {scanf("%d", &v);vec[j].push_back(v);}}ll sum = 0;for (int i=1;i<=m;i++) {sort(vec[i].begin(), vec[i].end());for (int j=0; j<n; j++) {sum += 1ll * j * vec[i][j] - 1ll * (n - 1 - j) * vec[i][j];}}printf("%lld\\n", sum);}return 0;
}

C - Unlucky Numbers

解题思路：暴力枚举+剪枝。

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)|1
typedef long long ll;
using ull = unsigned long long;
const int mx = 3e5 + 10;
const int mod = 1e9 + 7;ll n,m;
ll tens[20];
ll val;bool check(ll v, int mi, int ma, int p, bool f1, bool f2)
{if (v > m || v + tens[p] - 1 < n)return false;if (p == 0) {val = v;return f1 && f2;}for (int i=mi; i<=ma; i++) {if (check(v + i * tens[p-1], mi, ma, p - 1, f1 | (i==mi), f2 | (i==ma)))return true;}return false;
}int main() {auto solve = [](int &ans, ll &ret, int i) {for (int j=0; j<ans; j++) {for (int mi_k=0; mi_k+j<10; mi_k++) {if (mi_k * tens[i] > m)break;for (int k=max(1,mi_k); k<=mi_k+j; k++) {if (k * tens[i] > m)break;//printf("%d %d\\n", k*tens[i], i);// 当前值，最小值，最大值，还有的位数，最小值满足，最大值满足 if (check(k*tens[i], mi_k, mi_k+j, i, k==mi_k, k==mi_k+j)) {ret = val;ans = j;return;}}}}	};tens[0] = 1;for (int i=1;i<=18;i++) {tens[i] = tens[i-1] * 10;}tens[19] = 2 * tens[18];int t;scanf("%d", &t);while(t--) {scanf("%lld%lld", &n, &m);int ans = 10;ll ret; for (int i=0;i<=18;i++) {if (tens[i] > m)break;if (tens[i+1] - 1 < n)continue;solve(ans, ret, i);}printf("%lld\\n", ret);}return 0;
}

D - Petya, Petya, Petr, and Palindromes

解题思路：算一下不需要修改的对数，然后用总共的对数减去不需要修改的对数就是答案了，不需要修改也就是两个位置数相同，因为k是奇数，所以我们分开讨论偶数的位置和奇数的位置相同数的贡献就行了。

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)|1
typedef long long ll;
using ull = unsigned long long;
const int mx = 2e5 + 10;
const int mod = 1e9 + 7;vector <int> vec[2][mx];int main() {auto solve = [](int &ans, ll &ret, int i) {	};int n, k, u;scanf("%d%d", &n, &k);ll sum = 1ll * k / 2 * (n - k + 1);for (int i=1;i<=n;i++) {scanf("%d", &u);vec[i&1][u].push_back(i);}for (int i=1; i<mx; i++) {for (int j=0; j<2; j++) {for (int v: vec[j][i]) {int r = 2 * n - (k - 1) - v;int l = 2 + (k - 1) - v;int d1 = upper_bound(vec[j][i].begin(), vec[j][i].end(), min(r, v + k)) - vec[j][i].begin() - 1;int d2 = lower_bound(vec[j][i].begin(), vec[j][i].end(), max(l, v + 1)) - vec[j][i].begin();//cout << i << " v: " << v << " l: " << l << " r: " << r << " d1: " << d1 << " d2: " << d2 << endl;if (d1 >= d2)sum -= (d1 - d2 + 1);}}}printf("%lld\\n", sum);return 0;
}

E1 - Minibuses on Venus (easy version)

解题思路：如果一组数最终和的模是k，那么要减去i之后模为i，那么2 * i = k (mod m)。可以分析出可能多个i只想同一个k。我们dp[i][j][k]表示获取i张牌之后这i张牌里面不包含2 * x = j(mod m)的数并且它的和对m求模等于k。那么我们最终只需要把总数减去dp[n][i][i](0~k)就行了，因为这些情况是不满足条件的，因为他没不包含2 * x = i(mod m)的数并且他们最终的模数还等于i。dp时间复杂度为O（n*k^3）

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)|1
typedef long long ll;
using ull = unsigned long long;
const int mx = 1e2 + 10;
const int mod = 1e9 + 7;ll dp[mx][35][35];
ll ret[mx][35];
ll res[35];int main() {auto solve = [](int &ans, ll &ret, int i) {	};int n, k, m;scanf("%d%d%d",&n,&k,&m);ret[0][0] = 1;for (int i=0;i<k;i++)dp[0][i][0] = 1;for (int i=1;i<=n;i++) {for (int j=0;j<k;j++) {for (int q=0;q<k;q++) {ret[i][(j+q)%k] += ret[i-1][j];ret[i][(j+q)%k] %= m;for (int p=0;p<k;p++) {if (2 * q % k == p)continue;dp[i][p][(j+q)%k] += dp[i-1][p][j];dp[i][p][(j+q)%k] %= m;}}}}ll sum = 0;for (int i=0;i<k;i++) {int mo = 2 * i % k; res[mo] = ret[n][mo] - dp[n][mo][mo];}for (int i=0;i<k;i++) {sum += res[i] + m;sum %= m;}printf("%lld\\n", sum);return 0;
}

E2 - Minibuses on Venus (medium version)

解题思路：我们可以把每次枚举一张牌看做是多项式卷积，枚举x，令2 * i = x (mod k)的数的项数为零，其他位置为1，那么就可以像E1那样求得n个数最终模数是x但是里面不包含2 * i = x （mod k）的情况了，最终用总数减去就行了。所以这里面需要用到快速幂来解决，因为每次卷积的式子是一样的，所以可以使用快速幂，并且卷积方式也满足快速幂乘法要求。最终时间复杂度为O（logn*k^3）

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)|1
typedef long long ll;
using ull = unsigned long long;
const int mx = 1e2 + 10;
const int mod = 1e9 + 7;int m;class MultiData {public:vector <ll> v;MultiData (int k, int val) {v = vector<ll> (k, val);}MultiData operator * (const MultiData &A) const {int k = v.size();MultiData temp(k, 0);for (int i=0;i<k;i++) {for (int j=0;j<k;j++) {temp.v[(i+j)%k] += v[i] * A.v[j] % m;temp.v[(i+j)%k] %= m;}}return temp;}
};ll qpow(ll x, ll y)
{ll ans = 1;while (y) {if (y&1) ans = ans * x % m;y>>=1;x = x * x % m;}return ans;
}MultiData qmulti(MultiData &base, ll n, int k)
{MultiData ans(k, 0);ans.v[0] = 1;while (n) {if (n&1) ans = ans * base;n >>= 1;base = base * base;}return ans;
}int main() {auto solve = [](int &ans, ll &ret, int i) {	};int k;ll n;scanf("%lld%d%d",&n,&k,&m);ll ans = qpow(k, n);for (int i=0;i<k;i++) {MultiData base(k, 1);for (int j=0;j<k;j++) {if (2 * j % k == i)base.v[j] = 0;}MultiData ret = qmulti(base, n, k);ans -= ret.v[i];ans = (ans + m) % m;}printf("%lld\\n", ans);return 0;
}