前言
大唐胜屎
\(T1\) 镜的绮想
水签
CODE
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 5e3 + 100;
const int M = 4e6 + 100;
int n, m;
struct Poi {
int x, y;
} a[N], b[N];
int num[M];
signed main() {
auto Ret1 = freopen("mirror.in", "r", stdin);
auto Ret2 = freopen("mirror.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++ i) cin >> a[i].x >> a[i].y;
for (int i = 1; i <= m; ++ i) cin >> b[i].x >> b[i].y;
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) {
if (a[i].x == b[j].x) {
num[a[i].y + b[j].y + 2000000] ++;
}
}
}
int ans = 0;
for (int i = 0; i < M; ++ i) {
ans = max(ans, num[i]);
}
cout << ans << '\n';
}
\(T2\) 万物有灵
水签，但是我 \(vis\) 数组没有清空卡了四个小时，然后因为没特判快速幂负数死循环，然后因为写了一个唐氏特判被卡的比错解分还低。
其实贪心是显然的，模数非质，然后就考虑这个等差数列怎么求。
其实我有些小疑问吧，大家是不是以前都会用矩阵求这个，我赛时现推感觉还挺麻烦的。
考虑定义主矩阵和辅助矩阵，设 \(f(n) = \sum\limits_{i = 0}^{n - 1} k^i\)
他的线性递推是这样的： \(f(n) = kf(n - 1) +1\)
所以 \(f(n) - 1 = kf(n - 1)\)
那么这个矩阵乘法就是这样的：
\[\begin{vmatrix} f(n) \\ \\ f(n) - 1 \end{vmatrix} \times \begin{vmatrix} k + 1 & - 1 \\ \\ k & 0 \end{vmatrix}\]快速幂加速一下。时间复杂度为 \(\mathcal{O}(k + \log \frac{n}{k})\)
码有点长（流汗黄豆）
CODE
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 5e5 + 100;
ll n, K, mod;
ll a[N], sum[N];
inline ll Quick_Pow(ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) ans = (ans * a) % mod;
b >>= 1, a = (a * a) % mod;
}
return ans;
}
bool vis[N];
ll fir[N];
struct Node {
ll a[2][2];
Node operator * (Node b) {
Node c; c.clear();
for (int i = 0; i < 2; ++ i) {
for (int j = 0; j < 2; ++ j) {
for (int k = 0; k < 2; ++ k)
c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j] % mod + mod) % mod;
}
}
return c;
}
inline void clear() {
memset(a, 0, sizeof(a));
}
};
inline ll Quick(ll b, ll p) {
if (b < 0) return 1145141919810;
if (!b) return 1;
Node a, ans; a.a[0][0] = (p + 1) % mod, a.a[0][1] = mod - 1, a.a[1][0] = p, a.a[1][1] = 0;
ans.clear();
bool flag = 0;
while (b) {
if (b & 1) {
if (!flag) {
flag = 1;
for (int i = 0; i < 2; ++ i) {
for (int j = 0; j < 2; ++ j) ans.a[i][j] = a.a[i][j];
}
} else ans = ans * a;
}
b >>= 1, a = a * a;
}
return ans.a[0][0];
}
signed main() {
auto Ret1 = freopen("animism.in", "r", stdin);
auto Ret2 = freopen("animism.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> K >> mod;
for (int i = 0; i < K; ++ i) {
cin >> a[i];
if (!i) sum[i] = a[i];
else sum[i] = (sum[i - 1] * a[i]) % mod;
}
if (n & 1) {
ll round = 1, num = 1, m = ((n - 1) >> 1) + 1, ans = 0, q = (n - 1) / 2;
ll Around = (K & 1) ? (sum[K - 1] * sum[K - 1]) % mod : sum[K - 1];
for (int i = 0; !vis[i % K]; i += 2, ++ num) {
vis[i % K] = 1;
fir[i % K] = Quick_Pow(sum[K - 1], i / K) % mod * sum[i % K] % mod;
} -- num;
for (int i = 0; i < K; ++ i) vis[i] = 0;
round = m / num;
round --;
ll now = Quick(round, Around);
if (round >= 0) {
for (int i = 0; !vis[i]; (i += 2) %= K) {
vis[i] = 1;
(ans += now * fir[i] % mod) %= mod;
}
m %= num;
for (int i = 0; m; (i += 2) %= K, -- m) {
(ans += fir[i] * Quick_Pow(Around, round + 1) % mod) %= mod;
}
} else {
for (int i = 0; m; (i += 2) %= K, -- m) {
(ans += fir[i] * Quick_Pow(Around, round + 1) % mod) %= mod;
}
}
cout << ans << '\n';
} else {
ll round = 1, num = 1, m = n / 2, ans = 0, q = n / 2;
ll Around = (K & 1) ? (sum[K - 1] * sum[K - 1]) % mod : sum[K - 1];
for (int i = 1; !vis[i % K]; i += 2, ++ num) {
vis[i % K] = 1;
fir[i % K] = Quick_Pow(sum[K - 1], i / K) % mod * sum[i % K] % mod;
} -- num;
for (int i = 0; i < K; ++ i) vis[i] = 0;
round = m / num; round --;
ll now = Quick(round, Around);
if (round >= 0) {
for (int i = 1; !vis[i]; (i += 2) %= K) {
vis[i] = 1;
(ans += now * fir[i] % mod) %= mod;
}
m %= num;
for (int i = 1; m; (i += 2) %= K, -- m) {
(ans += fir[i] * Quick_Pow(Around, round + 1) % mod) %= mod;
}
} else {
for (int i = 1; m; (i += 2) %= K, -- m) {
(ans += fir[i] * Quick_Pow(Around, round + 1) % mod) %= mod;
}
}
cout << (ans + 1) % mod << '\n';
}
}
白石溪
考虑拆贡献，然后排序贪心做完了。
题解写的还挺对的。所以我是不是不用写了（宝宝巴士）
CODE
#include <bits/stdc++.h>
#define i128 (__int128)1
typedef long long ll;
// #pragma GCC optimize(2)
using namespace std;
const int N = 1e6 + 100;
#ifdef linux
#define getchar getchar_unlocked
#endif
inline ll read() {
ll x = 0; char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x;
}
template <typename T> void write(T x) {
if (x / 10) write(x / 10);
putchar(x % 10 + '0');
}
ll n, c, d;
ll a[N], b[N];
__int128 f[N], ans, num = 0, p;
signed main() {
auto Ret1 = freopen("creek.in", "r", stdin);
auto Ret2 = freopen("creek.out", "w", stdout);
n = read(), c = read(), d = read();
for (int i = 1; i <= n; ++ i) a[i] = read(), b[i] = read(), num += i128 * b[i] + i * c, p += a[i];
num -= i128 * n * (n + 1) / 2 * c; ans = num;
for (int i = 1; i <= n; ++ i) f[i] = i128 * a[i] + i * d - b[i] - i * c;
stable_sort(f + 1, f + n + 1, greater<__int128>());
for (int i = 1; i <= n; ++ i) num += f[i], num -= i128 * i * d, num += i128 * (n - i + 1) * c, ans = max(ans, num);
write(ans);
}
上山岗
题解写的真抽象，对我赛后改题没有任何帮助。上午我想。
题解写的真抽象，对我赛后改题没有任何帮助。中午我想。
题解写的真抽象，对我赛后改题没有任何帮助。下午我想。
题解写的真抽象，对我赛后改题没有任何帮助。晚午我想。
为了对称还是不改了。
但是还真没啥意义，于是口胡一个， byd 跑的还挺快的。
就是你考虑一下将人的能力排序， 小仙女总是喜欢_的 。
然后你先从小到大插，尽量往后放，因为你想让字典序最大嘛。
然后你在从大往小扫一遍，如果这个人没有小仙女，你就分配一个最早的空闲的，这个不合法，但还是得给，byd 给你个小仙女还不知足，还想要好的》
要是有，你就把这个山退回去，然后再找一个最早的。
这样显然贡献并未减少，而刚开始的分配策略能使合法者最多，因此，这样没啥问题。
晁端马：
CODE
#include <bits/stdc++.h>
typedef long long ll;
// #pragma GCC optimize(2)
using namespace std;
const int N = 1e6 + 100;
const int INF = 1e9;
namespace IO {
#ifdef linux
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
inline ll read() {
ll x = 0; char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x;
}
template <typename T> void write(T x) {
if (x / 10) write(x / 10);
putchar(x % 10 + '0');
}
} using namespace IO;
int n, w[N], c[N];
int Belong[N], Position[N];
struct SegMentTree {
#define lson (id << 1)
#define rson (id << 1 | 1)
#define mid ((l + r) >> 1)
int t[N << 2];
void build(int id, int l, int r) {
if (l == r) return t[id] = c[l], void();
build(lson, l, mid), build(rson, mid + 1, r);
t[id] = min(t[lson], t[rson]);
}
void updata(int id, int l, int r, int x, int c) {
if (l == r) return t[id] = c, void();
return ((x <= mid) ? updata(lson, l, mid, x, c) : updata(rson, mid + 1, r, x, c)), t[id] = min(t[lson], t[rson]), void();
}
int Precursor(int id, int l, int r, int x) {
if (l == r) return t[id] < x ? l : n + 1;
return (t[lson] < x ? Precursor(lson, l, mid, x) : Precursor(rson, mid + 1, r, x));
}
int Subsequent(int id, int l, int r, int x) {
if (l == r) return t[id] < x ? l : n + 1;
return (t[rson] < x ? Subsequent(rson, mid + 1, r, x) : Subsequent(lson, l, mid, x));
}
#undef mid
} t1, t2;
signed main() {
auto Ret1 = freopen("uphill.in", "r", stdin);
auto Ret2 = freopen("uphill.out", "w", stdout);
n = read();
for (int i = 1; i <= n; ++ i) c[i] = read();
for (int i = 1; i <= n; ++ i) w[i] = read();
stable_sort(w + 1, w + n + 1);
t1.build(1, 1, n), t2.build(1, 1, n);
for (int i = 1; i <= n; ++ i) {
int pos = t1.Subsequent(1, 1, n, w[i]);
if (pos != n + 1) {
Belong[pos] = i, Position[i] = pos;
t1.updata(1, 1, n, pos, INF);
}
}
for (int i = n; i >= 1; -- i) {
int pos;
if (!Position[i]) {
pos = t2.Precursor(1, 1, n, INF);
Position[Belong[pos]] = 0;
Belong[pos] = i, Position[i] = pos;
} else {
t1.updata(1, 1, n, Position[i], c[Position[i]]); Belong[Position[i]] = 0;
pos = t1.Precursor(1, 1, n, w[i]);
Belong[pos] = i, Position[i] = pos;
}
t1.updata(1, 1, n, pos, INF), t2.updata(1, 1, n, pos, INF);
}
for (int i = 1; i <= n; ++ i) {
write(w[Belong[i]]); putchar(' ');
}
}
后记
连续打唐好几场了，没啥可说的吧。
一场没有任何区分度的模拟赛能把你区分出来确实挺难评的。
大概好几场了吧，总是卡在一个题的代码上调不出来。我也很无奈。
可能是做题少或者码力差，还是少颓多补补吧。
感觉也有一些问题导致心情不好，单纯的不开心。
我放在桌子上的日记本，前两天也丢失了，就是一个黄色的本， pu 磁扣的，谁看见了也请告诉我，谢谢了。
标签：int,11.22,ll,pos,ans,sum,模拟,mod From： https://www.cnblogs.com/hangry/p/18563406