A.
乱搞
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<cctype>
#include<cmath>
using namespace std;
int T;
string S;
int len;
int u[2][30];
int mx_u[2];
int main()
{
cin >> T;
while (T--)
{
mx_u[0] = mx_u[1] = 0;
memset(u, 0, sizeof(u));
cin >> S;
len = S.length();
for (int i = 0; i < len; ++i)
{
++u[i & 1][S[i] - 'a'];
if (u[i & 1][S[i] - 'a'] > mx_u[i & 1])
{
mx_u[i & 1] = u[i & 1][S[i] - 'a'];
}
}
cout << (len - mx_u[0] - mx_u[1]) << endl;
}
return 0;
}
B.
数论乱搞
从 (O(2^m)) 变成 (O(m)) 需要稍加思考
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<cctype>
#include<cmath>
using namespace std;
const int MOD = 998244353;
int T, m;
long long q, p;
long long qp(long long bs, int pw)
{
long long ret = 1;
while (pw)
{
if (pw & 1)
{
ret *= bs;
ret %= MOD;
}
bs *= bs;
bs %= MOD;
pw >>= 1;
}
return ret;
}
long long inv(int x)
{
return qp(x, MOD - 2);
}
long long ans;
long long n;
int main()
{
ios::sync_with_stdio(false);
cin >> T;
while (T--)
{
ans = 1;
n = 1;
cin >> m;
for (int i = 1; i <= m; ++i) {
cin >> p >> q;
n *= qp(p, q);
n %= MOD;
ans *= 1ll + q - q * inv(p) % MOD + MOD;
ans %= MOD;
}
cout << n * ans % MOD << endl;
}
// system("pause");
return 0;
}
C.
博弈论，反正也是可以乱搞的
不乱搞也不难
暂时不想写
D.
摸一下规律就可以乱搞了
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<cctype>
#include<cmath>
using namespace std;
const int maxn = 1e5 + 10;
int T;
long long fact[maxn];
int n;
long long a;
const int MOD = 998244353;
long long qp(long long bs, long long pw)
{
long long ret = 1;
while (pw)
{
if (pw & 1)
{
ret *= bs;
ret %= MOD;
}
bs *= bs;
bs %= MOD;
pw >>= 1;
}
return ret;
}
void pre(int n)
{
fact[0] = fact[1] = 1;
for (int i = 2; i <= n; ++i)
{
fact[i] = fact[i - 1] * i % MOD;
}
}
long long ginv(long long x)
{
if (!x)
return 1;
else
return qp(x, MOD - 2);
}
long long gp;
int main()
{
ios::sync_with_stdio(false);
cin >> T;
pre(100000);
while (T--)
{
cin >> n;
long long sm = 0;
sm = gp = 0;
for (int i = 1; i <= n; ++i)
{
cin >> a;
gp = (gp + fact[n - 1] * ginv(i - 1) % MOD) % MOD;
sm += gp * a % MOD;
if (sm >= MOD) sm -= MOD;
}
sm *= ginv(fact[n]);
cout << sm % MOD << endl;
}
// system("pause");
return 0;
}
E.
感觉是树形 DP
不想写
J.
什么简单差分
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<cctype>
#include<cmath>
using namespace std;
int T;
int n, m;
const int MOD = 998244353;
const int maxn = 1e5 + 10;
int dv[2][maxn];
int mn[2];
long long pw[2];
long long qp(long long bs, int pw)
{
long long ret = 1;
while (pw)
{
if (pw & 1)
{
ret *= bs;
ret %= MOD;
}
bs *= bs;
bs %= MOD;
pw >>= 1;
}
return ret;
}
int main()
{
ios::sync_with_stdio(false);
cin >> T;
while (T--)
{
cin >> n >> m;
for (int i = n + 1; i >= 0; --i)
dv[0][i] = dv[1][i] = 0;
for (int l, r, x, i = 1; i <= m; ++i)
{
cin >> l >> r >> x;
++dv[x - 2][l];
--dv[x - 2][r + 1];
}
mn[0] = mn[1] = 2147483644;
int st[2] = {0, 0};
for (int i = 1; i <= n; ++i)
{
st[0] += dv[0][i];
st[1] += dv[1][i];
mn[0] = min(mn[0], st[0]);
mn[1] = min(mn[1], st[1]);
}
pw[0] = qp(2, mn[0]);
pw[1] = qp(3, mn[1]);
cout << pw[0] * pw[1] % MOD << endl;
}
// system("pause");
return 0;
}
K.
二分
不会
L.
很好搞。
(10^{12}) 印象里貌似就可以
枚举一下所有因数，这大概是可以承受的
然后异或的前缀和其实很好推，这个是 (log)
（为什么是异或前缀和嘛，你考虑一个 (n) 有 (2) 和 (3) 这两个因数
你首先考虑一下模比 (n/2) 大的那些数，再考虑模比 (n/3) 大的那些数）
虽然可能不太能过
当然这个也不一定正确
好像是类欧，我跑了
FGHI
有缘再见吧