抛硬币coin
#include<bits/stdc++.h>
#define ll long long
using namespace std;const ll mod = 998244353;
inline ll M(ll a){
return a%mod;}
inline ll add(ll a, ll b){
return M(a+b);}
inline ll mul(ll a, ll b){
return M(a*b);}
inline ll sub(ll a, ll b){
return M(a-b+mod);}
ll P(ll a, ll b){
ll c=1;while(b){
if(b&1)c=M(c*a);b>>=1;a=M(a*a);}return c;}
ll n, ans;int main() {
scanf("%lld", &n);if(n&1) ans = add(3, P(P(3, mod-2), n-1));else ans = sub(3, P(P(3, mod-2), n-1));printf("%lld", mul(ans, P(6, mod-2)));return 0;
}
摧毁树状图 sabotage
qt大佬的题解
#include<bits/stdc++.h>
#define ll long long
using namespace std;const int N = 1e5;
const ll mod = 998244353;ll size[N], f[N][210][2], g[510][2], lin[N], len, n, m;
inline void C(){
memset(g, 0, sizeof g);}
struct psx{
int next, y;} e[N<<1];inline ll M(ll a){
return a%mod;}
inline ll add(ll a, ll b){
return M(a+b);}
inline ll mul(ll a, ll b){
return M(a*b);}
inline ll sub(ll a, ll b){
return M(a-b+mod);}
ll P(ll a, ll b){
ll c=1;while(b){
if(b&1)c=M(c*a);b>>=1;a=M(a*a);}return c;}
//取模套餐inline void insert(int xx, int yy) {
e[++len].next = lin[xx];lin[xx] = len;e[len].y = yy;
}inline void dfs(int x, int fa) {
size[x] = f[x][0][0] = 1;for(int i = lin[x]; i; i = e[i].next) {
int y = e[i].y;if(y == fa) continue;dfs(y, x); C();for(int j = 0; j <= size[x]; j++)for(int k = 0; k <= size[y]; k++) {
g[j+k][0] = add(g[j+k][0], mul(f[x][j][0], f[y][k][0]));g[j+k][0] = add(g[j+k][0], mul(2, mul(f[x][j][0], f[y][k][1])));g[j+k][1] = add(g[j+k][1], mul(2, mul(add(f[y][k][0], f[y][k][1]), f[x][j][1])));g[j+k+1][1] = add(g[j+k+1][1], mul(f[x][j][0], f[y][k][0]));}//子树转移for(int j = 0; j < m; j++) {
f[x][j][0] = add(g[j][0], g[j+m][0]);f[x][j][1] = add(g[j][1], g[j+m][1]);}//合并转移size[x] = min(add(size[x], size[y]), 1LL*m);//时间优化}
}int main() {
scanf("%lld%lld", &n, &m);for(int i = 1, u, v; i < n; i++) {
scanf("%d%d", &u, &v);insert(u, v);insert(v, u); }dfs(1, 0);printf("%lld\n", M(f[1][0][0] + f[1][0][1]));return 0;
}
逃出生天escape
考场50分代码 策略不完全 但意外RP高
#include<bits/stdc++.h>
#define ll long long
using namespace std;const int N = 2e6;
const int M = 1e3+10;
char ch[M];
int n, m, end1, end2, head=1, tail=0;
int f[N], q[N], p[N], e[N][10], a[M][M];
int dx[4] = {
-1, 1, 0, 0}, dy[4] = {
0, 0, -1, 1};inline int C(int i, int j) {
return i*(m+2)+j;}
inline int Si(int i){
return i/(m+2);}
inline int Sj(int i){
return i%(m+2);}
inline bool Pn(int i){
return 0<=i&&i<=n+1 ? 1 : 0;}
inline bool Pm(int i){
return 0<=i&&i<=m+1 ? 1 : 0;}
inline bool check(int i, int j){
return (i==end1 && j==end2) ? 1 : 0;}inline int bfs() {
while(head <= tail) {
int k = q[head], val = p[head++], x = Si(k), y = Sj(k);if(Pn(x) && Pm(y+1) && !f[C(x, y+1)] && a[x][y+1]) {
f[C(x, y+1)] = val+1;if(check(x, y+1)) return val+1;else q[++tail] = C(x, y+1), p[tail] = val+1;}//右边 if(Pn(x) && Pm(y-1) && !f[C(x, y-1)] && a[x][y-1]) {
f[C(x, y-1)] = val+1;if(check(x, y-1)) return val+1;else q[++tail] = C(x, y-1), p[tail] = val+1;}//左边 if(Pn(x-1) && Pm(y) && !f[C(x-1, y)] && a[x-1][y]) {
f[C(x-1, y)] = val+1;if(check(x-1, y)) return val+1;else q[++tail] = C(x-1, y), p[tail] = val+1;}//上边 if(Pn(x+1) && Pm(y) && !f[C(x+1, y)] && a[x+1][y]) {
f[C(x+1, y)] = val+1;if(check(x+1, y)) return val+1;else q[++tail] = C(x+1, y), p[tail] = val+1;}//下边for(int i = 1; i <= 4; i++) {
int x = Si(e[k][i]), y = Sj(e[k][i]);if(Pn(x) && Pm(y) && !f[C(x, y)] && a[x][y]) {
f[C(x, y)] = val+1; if(check(x, y)) return val+1;else q[++tail] = C(x, y), p[tail] = val+1;}} if(head == 2) f[k] = M;}
}int main() {
scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) {
scanf("%s", ch+1);for(int j = 1; j <= m; j++) {
if(ch[j] == '#') a[i][j] = 0;else a[i][j] = -1;if(ch[j] == 'C') end1 = i, end2 = j;if(ch[j] == 'S') q[++tail] = C(i, j); }}for(int i = 0; i <= n+1; i++) for(int j = 0; j <= m+1; j++) if(!a[i][j]) for(int k = 0; k < 4; k++) {
int x = i+(dx[k]<<1), y = j+(dy[k]<<1);while(Pn(x) && Pm(y) && a[x][y] && a[i+dx[k]][j+dy[k]]) {
e[C(x, y)][k+1] = C(i+dx[k], j+dy[k]);x += dx[k], y += dy[k];}}printf("%d", bfs());return 0;
}正解 迪杰斯特拉
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e3+10;
int n, m, len, st, ed;
int l[N][N], r[N][N], u[N][N], d[N][N], lin[N * N], a[N][N];
int v[N*N], dis[N*N];
char ch[N];
struct psx{
int next, y, v; }e[N*N<<3];inline void add(int xx, int yy, int vv) {
e[++len].next = lin[xx];e[len].y = yy;e[len].v = vv;lin[xx] = len;
}inline int C(int i, int j) {
return (i-1)*m+j;}
inline int Min(int i, int j){
return i<j ? i : j;}inline void prep() {
for (int i = 1; i <= n; i++) {
l[i][0] = 0;for (int j = 1; j <= m; j++)l[i][j] = !a[i][j] ? j : l[i][j-1];r[i][m+1] = m+1;for (int j = m; j >= 1; j--)r[i][j] = !a[i][j] ? j : r[i][j+1];}for (int j = 1; j <= m; j++) {
u[0][j] = 0;for (int i = 1; i <= n; i++)u[i][j] = !a[i][j] ? i : u[i-1][j];d[n+1][j] = n+1;for (int i = n; i >= 1; i--)d[i][j] = !a[i][j] ? i : d[i+1][j];}
}
inline void edge() {
for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) {
if (!a[i][j]) continue;if (i+1<=n && a[i+1][j]) {
add(C(i, j), C(i+1, j), 1);add(C(i+1, j), C(i, j), 1);}if (j+1<=m && a[i][j+1]) {
add(C(i, j), C(i, j+1), 1);add(C(i, j+1), C(i, j), 1);}}for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) {
if (!a[i][j]) continue;int dl = j - l[i][j];int dr = r[i][j] - j;int du = i - u[i][j];int dd = d[i][j] - i;int dis = Min(Min(dl, dr), Min(du, dd));if (l[i][j] != j-1) add(C(i, j), C(i, l[i][j]+1), dis);if (r[i][j] != j+1) add(C(i, j), C(i, r[i][j]-1), dis);if (u[i][j] != i-1) add(C(i, j), C(u[i][j]+1,j), dis);if (d[i][j] != i+1) add(C(i, j), C(d[i][j]-1,j), dis);}
}
inline int dijkstra() {
memset(dis, 0x3f, sizeof dis);priority_queue < pair <int, int> > q;q.push(make_pair(0, st));dis[st] = 0;while (q.size()) {
int x = q.top().second; q.pop();if (v[x]) continue; v[x] = 1;if (x == ed) return dis[x];for (int i = lin[x], y=e[i].y; i; i = e[i].next, y = e[i].y)if (dis[x] + e[i].v < dis[y]) {
dis[y] = dis[x] + e[i].v;q.push(make_pair(-dis[y], y));}}return -1;
}int main() {
scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) {
scanf("%s", ch + 1);for (int j = 1; j <= m; j++) {
if(ch[j] == '#') a[i][j] = 0;else a[i][j] = 1;if (ch[j] == 'S') st = C(i, j);if (ch[j] == 'C') ed = C(i, j);}} prep();edge();printf("%d\n", dijkstra());return 0;
}
走步 travel
我对不起我的数学老师……余弦定理的经典应用，哎！
设 B B B点为原点，那么第一次操作后第一点必然在圆 B B B上，设为点 A A A
同理第二次操作，必然在圆 A A A上，设为点 C C C，设角度为 θ \theta θ
那么利用余弦定理， B C BC BC 2 ^{2} 2 = A C AC AC 2 ^{2} 2 + A B AB AB 2 ^{2} 2 - 2 2 2 ? * ? A B AB AB ? * ? A C AC AC ? * ? c o s cos cos θ \theta θ
——> B C BC BC 2 ^{2} 2 = 2 2 2 - 2 2 2 ? * ? c o s cos cos θ \theta θ
已知余弦函数如上图，显然可得平均值为0，所以式子答案为 2 2 2
同理可做 3 3 3、 4 4 4、……
#include<bits/stdc++.h>
#define ll long long
using namespace std;int main(){
int n;scanf("%d", &n);printf("%d\n", n);return 0;
}
遥不可及far
考场60分超时代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;const int N = 1e5+10;
struct psx{
int l, r, i, ans;} Q[N];
inline bool mycmp1(psx a, psx b){
return a.r==b.r ? a.l>b.l : a.r>b.r;}
inline bool mycmp2(psx a, psx b){
return a.i<b.i;}
vector<int> b[N];
int n, m, Qi, a[N];
bool c[N];inline int Max(int a, int b){
return a<b ? b : a;}inline void init() {
scanf("%d%d%d", &n, &m, &Qi);for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);b[a[i]].push_back(i);c[a[i]] = 1;}for(int i = 1; i <= Qi; i++) {
scanf("%d%d", &Q[i].l, &Q[i].r);Q[i].i = i;}sort(Q+1, Q+1+Qi, mycmp1);
}inline void work() {
int len, num1, num2;for(int i = 1; i <= Qi; i++) for(int j = 1; j <= m; j++) if(c[j]) {
len = b[j].size(), num1=0, num2=0;for(int k = len-1; k >= 0 && c[j]; k--) {
while(b[j][k] > Q[i].r) {
b[j].pop_back();len--; if(!len) c[j] = 0;k--;}if(Q[i].l <= b[j][k] && b[j][k] <= Q[i].r) {
if(!num1) num1 = b[j][k];else num2 = b[j][k];}if(Q[i].l > b[j][k]) break;}if(num1 && num2) Q[i].ans = Max(Q[i].ans, num1-num2);}
}inline void outo() {
sort(Q+1, Q+1+Qi, mycmp2);for(int i = 1; i <= Qi; i++)printf("%d\n", Q[i].ans);
}
int main() {
init();work();outo();return 0;
}
神奇暴力做法（还有莫队回滚的AC，就不写啦）
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+10;
int n, m, q, l, r, a[N], ans;
int main() {
scanf("%d%d%d", &n, &m, &q);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);while (q--) {
scanf("%d%d", &l, &r);ans = 0;for (int j = r - l; j; j--) {
for (int k = l; k + j <= r; k++)if (a[k + j] == a[k]) {
ans = j; break; } if (ans) break;}printf("%d\n", ans);}return 0;
}
颠倒黑白rev
