暂时咕着，慢慢补...赛时几题先放上来
A
打个表即可
#include<bits/stdc++.h>
using namespace std;
int main() {
long long n;
scanf("%lld",&n);
if(n & 1) puts("1"); else puts("-1");
}B
枚举端点，hash判断即可。
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
#define N 10100
#define base 13131
char s[N];
ull h1[N], p[N], h2[N];
int n, ans = 0;
ull gh1(int l, int r) { return h1[r] - h1[l - 1] * p[r - l + 1]; }
ull gh2(int l, int r) { return h2[l] - h2[r + 1] * p[r - l + 1]; }
int main() {
scanf("%s", s + 1); p[0] = 1;
n = strlen(s + 1);
for(int i = 1; i <= n; ++i) s[i + n] = s[i];
n *= 2;
for(int i = 1; i <= n; ++i) {
h1[i] = h1[i - 1] * base + s[i];
p[i] = p[i - 1] * base;
}
for(int i = n; i; i--) h2[i] = h2[i + 1] * base + s[i];
for(int i = 1; i <= n; ++i) {
for(int j = i; j - i + 1 <= n / 2 && j <= n; ++j) {
int mid = (i + j) >> 1;
if((j - i + 1) & 1 && gh1(i, mid - 1) == gh2(mid + 1, j)) ans = max(ans, j - i + 1);
if(!((j - i + 1) & 1) && gh1(i, mid) == gh2(mid + 1, j)) ans = max(ans, j - i + 1);
}
}
printf("%d\n", ans);
}C
考虑答案长什么样子
\[ \frac{钱数大于3*n的方案数}{总方案数} \]
这个方案数dp一下就可以了。类似背包。
然后总方案数是什么呢？考虑每次一共有4种选择，相乘即\(4^n\)。
用个gcd约分即可。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll f[40][130];
int n;
int main() {
cin >> n;
f[0][0] = 1;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= 4 * n; ++j)
for(int v = 1; v <= 4; ++v)
if(j - v >= 0) f[i][j] += f[i - 1][j - v];
}
ll m1 = 0;
for(int i = 3 * n; i <= 4 * n; ++i) m1 += f[n][i];
ll m2 = pow(4, n), g = __gcd(m1, m2);
printf("%lld/%lld\n", m1 / g, m2 / g);
}D
维护前后缀和，枚举不选点
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 5000010
ll a[N], l[N], r[N];
int main() {
int n; cin >> n;
for(int i = 1; i <= n; ++i) scanf("%lld", &a[i]), l[i] = l[i - 1] | a[i];
for(int i = n; i; --i) r[i] = r[i + 1] | a[i];
ll ans = 0;
for(int i = 1; i <= n; ++i) {
ans = max(ans, l[i - 1] | r[i + 1]);
}
printf("%lld\n", ans);
}E
倍增floyd，转移的时候相乘即可。注意细节。
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
#define inf 0x3f3f3f3f
#define il inline
namespace io {
#define in(a) a = read()
#define out(a) write(a)
#define outn(a) out(a), putchar('\n')
#define I_int ll
inline I_int read() {
I_int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
char F[200];
inline void write(I_int x) {
if (x == 0) return (void) (putchar('0'));
I_int 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]);
}
#undef I_int
}
using namespace io;
using namespace std;
#define N 110
const ll mod = 1000000007;
ll K,m,s,n;
struct mat {
int m[N][N];
mat operator * (const mat x) const {
mat c; memset(c.m, 0, sizeof(c.m));
for(int k = 1; k <= n; ++k) {
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
c.m[i][j] += m[i][k] * x.m[k][j] % mod;
c.m[i][j] %= mod;
}
}
}
return c;
}
}d[32];
int main() {
in(n);in(m);in(K);in(s); int tot = 0;
for(int i = 1; i <= m; ++i) {
int x, y; in(x), in(y);
d[0].m[x][y]++;
}
for(int i = 1; (1 << i) <= K; ++i) d[i] = d[i - 1] * d[i - 1];
mat ans;
--K; ans = d[0];
for(int i = 0; (1 << i) <= K; ++i) if((K>>i)&1) ans = ans * d[i];
ll sum = 0;
for(int i = 1; i <= n; ++i) {
if(i == s) continue;
if(ans.m[s][i]!=-1) sum += ans.m[s][i] % mod;
sum %= mod;
}
outn(sum);
}H
单调栈板子。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1000100
int a[N], n, k, h[N], w[N], s[N];
ll ans = 0;
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for(int i = 1; i <= n; ++i) scanf("%d", &h[i]), ans = max(ans, (ll)h[i] * a[i]);
int top = 0;
for(int i = 1; i <= n; ++i) {
if(a[i] > h[s[top]]) {
s[++top] = i, w[top] = 1;
} else {
ll W = 0;
while(top && h[s[top]] > h[i]) {
W += w[top];
ans = max(ans, (ll)W * h[s[top]]);
--top;
}
s[++top] = i; w[top] = W + a[i];
}
}
printf("%lld\n", ans);
}I
做一下nim，如果必败就枚举要取哪个，如果都不行那就还是必败
#include <bits/stdc++.h>
using namespace std;
#define N 100010
int a[N], s, n, k;
int main() {
cin >> n >> k;
for(int i = 1; i <= n; ++i) {
cin >> a[i]; s ^= a[i];
}
if(s) return puts("YES"), 0;
for(int i = 1; i <= n; ++i) {
int now = s ^ a[i];
if(a[i] >= k && now ^ (a[i] - k)) return puts("YES"), 0;
}
puts("NO");
}J
套路莫反。这里放上推导。复杂度\(O(\sqrt{n})\)
\[ \begin{aligned} &\sum \sum (i,j)^2\\ &=\sum^n d^2\sum \sum[(i,j)=d]\\ &=\sum^n d^2 \sum_{i=1}^{n/d}\sum_{j=1}^{m/d}[(i,j)=1]\\ &=\sum^n d^2 \sum_{k=1}^{n/d}\mu(k)\frac{n}{kd}\frac{m}{kd}\\ &T = kd\\ &=\sum_{T=1}^n\frac{n}{T}\frac{m}{T}\sum_{k|T}\mu(k)(\frac{T}{k})^2\\ &id^2*\mu\\ &=F(1)=1, F(p)=p^2-1, F(p^2)=F(p)*p^2 \end{aligned} \]
\[ \begin{aligned} &\sum_{k|T}\mu(k)(\frac{T}{k})^2\\ &\mu*id^2\\ &F(1)=1\\ &F(p)=1*(p/1)^2+(-1)*(p/p)^2=p^2-1\\ &F(p^2)=1*(p^2/1)^2+(-1)*p^2+0=(p^2)^2-p^2=(p^2-1)*p^2 \end{aligned} \]
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1000100
#define M 1000000
const ll mod = 1000000007;
ll n, m;
int p[N], cnt, vis[N];
ll F[N];
void init() {
F[1] = 1;
for(int i = 2; i <= M; ++i) {
if(!vis[i]) p[++cnt] = i, F[i] = ((ll)i * i - 1ll) % mod;
for(int j = 1; i * p[j] <= M && j <= cnt; ++j) {
vis[i * p[j]] = 1;
if(i % p[j] == 0) {
F[i * p[j]] = F[i] * (p[j] * p[j] % mod) % mod;
break;
}
F[i * p[j]] = (ll)F[i] * F[p[j]] % mod;
}
}
for(int i = 1; i <= M; ++i) F[i] += F[i - 1], F[i] %= mod;
}
int main() {
init();
scanf("%lld%lld", &n, &m);
if(n > m) swap(n, m);
ll ans = 0;
for(ll l = 1, r; l <= n; l = r + 1) {
r = min(n / (n / l), m / (m / l));
ans = (ans + (ll)(n / l) * (m / l) % mod * ((F[r] - F[l - 1] + mod) % mod) % mod) % mod;
}
printf("%lld\n", (ans % mod + mod) % mod);
}
京公网安备 11010502036488号