题意：
给出一个\(n*n\)的矩阵，并满足\(n\)为奇数，矩阵中的数从右上角开始往下，类似于蛇形填数那样来填充。
之后会给出\(m\)个有效数字的坐标，坐标左下角为\((1,1)\)，右上角为\((n,n)\)，其余数字都为\(0\)。
之后会有多个询问，每个询问给出一个子矩阵，问子矩阵中元素和为多少。
思路：
代码写得有点凌乱，很多冗余...
Code
#include <bits/stdc++.h>
#define y1 skljalkd
#define MP make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int N = 1e6 + 5, M = 1e5 + 5;
int T;
struct node{
int x, y, v, id;
bool operator < (const node &A) const {
if(A.y == y && A.x == x) return id < A.id;
if(A.y == y) return x < A.x;
return y < A.y;
}
}a[M], b[N], d[N];
int n, m, p;
int X[N], Y[N];
inline int getv(int x,int y) {
ll k=min(min(x,y),min(n-x+1,n-y+1));
ll ans=(ll)n*n-(ll)(n-2*(k-1))*(n-2*(k-1));
if(x==n-k+1) {
ans+=(n-k+1 -y+1);
} else if(y==n-k+1) {
ans+=n-2*k+2 + n-2*k+1 +n-2*k +(x-k+1);
} else if(x==y) {
ans+=n-2*k+2 + n-2*k+1;
} else if(x>y) {
ans+=n-2*k+2 + (n-k-x+1);
} else if(x<y) {
ans+=n-2*k+2 + n-2*k + y-k+1;
}
int res = 0;
while(ans) {
res += ans % 10;
ans /= 10;
}
return res;
}
void Hash() {
X[0] = Y[0] = 0;
for(int i = 1; i <= m; i++) X[++X[0]] = a[i].x, Y[++Y[0]] = a[i].y;
for(int i = 1; i <= 4 * p; i++) X[++X[0]] = b[i].x, Y[++Y[0]] = b[i].y;
sort(X + 1, X + X[0] + 1);
sort(Y + 1, Y + Y[0] + 1);
X[0] = unique(X + 1, X + X[0] + 1) - X - 1;
Y[0] = unique(Y + 1, Y + Y[0] + 1) - Y - 1;
for(int i = 1; i <= m; i++) a[i].x = lower_bound(X + 1, X + X[0] + 1, a[i].x) - X;
for(int i = 1; i <= m; i++) a[i].y = lower_bound(Y + 1, Y + Y[0] + 1, a[i].y) - Y;
for(int i = 1; i <= 4 * p; i++) b[i].x = lower_bound(X + 1, X + X[0] + 1, b[i].x) - X;
for(int i = 1; i <= 4 * p; i++) b[i].y = lower_bound(Y + 1, Y + Y[0] + 1, b[i].y) - Y;
}
vector <pair<int, int> > col[N];
int c[N];
ll ans[N];
int lowbit(int x) {return x & (-x);}
void upd(int x, int v) {
for(; x < N; x += lowbit(x)) c[x] += v;
}
ll query(int x) {
ll res = 0;
for(; x; x -= lowbit(x)) res += c[x];
return res;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> T;
while(T--) {
memset(c, 0, sizeof(c));
cin >> n >> m >> p;
for(int i = 1; i <= m; i++) {
cin >> a[i].x >> a[i].y;
a[i].v = getv(a[i].x, a[i].y);
a[i].id = 0;
}
for(int i = 1; i <= p; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
--x1, --y1;
int x3 = x1, y3 = y2;
int x4 = x2, y4 = y1;
int v1 = getv(x1, y1), v2 = getv(x2, y2), v3 = getv(x3, y3), v4 = getv(x4, y4);
b[4 * i - 1] = {x1, y1, v1, 4 * i};
b[4 * i] = {x2, y2, v2, 4 * i - 2};
b[4 * i - 2] = {x3, y3, v3, 4 * i - 1};
b[4 * i - 3] = {x4, y4, v4, 4 * i - 3};
}
Hash();
for(int i = 1; i <= Y[0]; i++) col[i].clear();
for(int i = 1; i <= m; i++) d[i] = a[i];
for(int i = 1; i <= 4 * p; i++) d[i + m] = b[i];
int tot = m + 4 * p;
sort(d + 1, d + tot + 1);
for(int i = 1; i <= tot; i++) {
col[d[i].y].push_back(MP(i, d[i].id == 0));
}
for(int i = 1; i <= Y[0]; i++) {
for(auto it : col[i]) {
if(it.se == 1) {
upd(d[it.fi].x, d[it.fi].v);
}
if(it.se == 0) {
int now = it.fi;
ans[d[now].id] = query(d[now].x);
}
}
}
for(int i = 1; i <= p; i++) {
ll res = ans[4 * i - 2] + ans[4 * i] - ans[4 * i - 1] - ans[4 * i - 3];
cout << res << '\n';
}
}
return 0;
}题意：
定义一下式子：
\[
log_a^*(x)=\left\{
\begin{aligned}
&-1,&x<1\&1+log_a^*(log_ax),&x\geq 1
\end{aligned}
\right.
\]
求最小的\(x\)，满足\(log_a^*(x)\geq b\)。
思路：
稍微推一下式子，会变成这样：
\[
log_a^*(x)=b+log_a^*(log_a{log_a{\cdots log_ax}})
\]
那么就有\(x=a^{a^{\cdots ^{a}}}\)，这里共\(b\)个\(a\)。
之后利用广义欧拉降幂搞一下即可。
注意取模函数，这是一个技巧，有了它我们就可以不用管广义欧拉降幂中的条件了。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000005;
bool vis[N];
int prime[N], phi[N], tot;
void pre() {
phi[1] = 1;
for(int i = 2; i < N; i++) {
if(!vis[i]) {
vis[i] = 1; prime[++tot] = i;
phi[i] = i - 1;
}
for(int j = 1; j <= tot && prime[j] * i < N; j++) {
vis[i * prime[j]] = 1;
if(i % prime[j] == 0) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
}
ll Mod(ll a, ll b) {
return a < b ? a : a % b + b;
}
int qp(ll a, ll b, ll p) {
int ans = 1;
while(b) {
if(b & 1) ans = Mod(ans * a, p);
a = Mod(a * a, p);
b >>= 1;
}
return ans;
}
int calc(ll a, ll b, ll m) {
if(m == 1 || !b) return 1;
int p = phi[m];
int x = calc(a, b - 1, p);
return qp(a, x, m);
}
int T;
int a, b, m;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
pre();
cin >> T;
while(T--) {
cin >> a >> b >> m;
ll ans = calc(a, b, m) % m;
cout << ans << '\n';
}
return 0;
}
题意：
给出一张有向无环图。
现在有一个机器人在上面走，每一天可以行动一步，这一步可以选择停留原地或者沿着某一条边走。
定义每一天的消耗为已经经过天数的消耗。
求最终到达\(n\)点时的期望消耗值。
思路：
这个题怎么这么难读，感觉读不懂QAQ。
假设\(dp2[u]\)为从\(u\)出发，到达\(n\)的期望消耗值。那么就有：
\[
dp2[u]=\frac{dp2[u]+dp[u]+1}{out[u]+1}+\sum_{(u,v)\in Edge}\frac{dp2[v]+dp[v]+1}{out[u]+1}
\]
分别表示停留在原地的期望消耗以及走向下一个点的期望消耗，加起来就是目前点的期望消耗。
那这里的\(dp[u]\)指的是什么？
指的就是从\(u\)到\(n\)的期望天数，有了它就相当于求出当前这天的期望消耗。
求\(dp[u]\)类似推一遍就行。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n, m;
vector <int > g[N];
double dp[N][2];
bool vis[N];
double dfs1(int u) {
if(u >= n) return dp[n][0] = 0;
if(vis[u]) return dp[u][0];
vis[u] = 1;
double res = 0;
for(auto it : g[u]) res += dfs1(it);
int x = g[u].size();
res /= (double)(x + 1);
res = 1.0 * (x + 1) / x * (res + 1);
return dp[u][0] = res;
}
double dfs2(int u) {
if(u >= n) return dp[n][1] = 0;
if(vis[u]) return dp[u][1];
vis[u] = 1;
double res = 0;
for(auto it : g[u]) res += dfs2(it) + dp[it][0];
res += dp[u][0];
int x = g[u].size();
res /= (double)(x + 1);
res = 1.0 * (x + 1) / x * (res + 1);
return dp[u][1] = res;
}
int main() {
// ios::sync_with_stdio(false); cin.tie(0);
int T; cin >> T;
while(T--) {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) g[i].clear();
for(int i = 1; i <= m; i++) {
int u, v; cin >> u >> v;
g[u].push_back(v);
}
fill(vis + 1, vis + n + 1, false);
dfs1(1);
fill(vis + 1, vis + n + 1, false);
dfs2(1);
printf("%.2f\n", dp[1][1]);
}
return 0;
}
很容易分析，对一个数求答案的话，就是找相应区间内小于他的最大的数，所以就有很多种做法。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int T, n, k;
int maxv[N << 2];
void push_up(int o) {
maxv[o] = max(maxv[o << 1], maxv[o << 1|1]);
}
void build(int o, int l, int r) {
maxv[o] = 0;
if(l == r) return;
int mid = (l + r) >> 1;
build(o << 1, l, mid); build(o << 1|1, mid + 1,r);
}
void update(int o, int l, int r, int p, int v) {
if(l == r) {
maxv[o] = v; return;
}
int mid = (l + r) >> 1;
if(p <= mid) update(o << 1, l, mid, p, v);
else update(o << 1|1, mid + 1, r, p, v);
push_up(o);
}
int query(int o, int l, int r, int L, int R) {
if(L > R) return 0;
if(L <= l && r <= R) return maxv[o];
int mid = (l + r) >> 1;
int res = 0;
if(L <= mid) res = max(res, query(o << 1, l, mid, L, R));
if(R > mid) res = max(res, query(o << 1|1, mid + 1, r, L, R));
return res;
}
int a[N], ans[N], pos[N];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> T;
while(T--) {
cin >> n >> k;
build(1, 1, n);
for(int i = 1; i <= n; i++) cin >> a[i], pos[a[i]] = i;
for(int i = 1; i <= n; i++) {
int mx = query(1, 1, n, max(1, pos[i] - k), pos[i] - 1);
mx = max(mx, query(1, 1, n, pos[i] + 1, min(n, pos[i] + k)));
ans[i] = ans[mx] + 1;
update(1, 1, n, pos[i], i);
}
for(int i = 1; i <= n; i++) cout << ans[i] << " \n"[i == n];
}
return 0;
}签到题，跑六次最短路即可。
Code
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int MAXN = 3e2+5,MAXM = 5e2+5,MOD = 20130427,INF = 0x3f3f3f3f,N=100050;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
const db eps = 1e-9;
#define lson o<<1,l,m
#define rson o<<1|1,m+1,r
#define mid l + ((r-l)>>1)
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define vii vector<pair<int,int>>
#define vi vector<int>
using namespace std;
struct Edge{
int u,v;
ll w;
}e[MAXM];
int t,n,m,start[10],target[10];
ll d[MAXN];
int main(){
ios::sync_with_stdio(false);cin.tie(0);
//freopen("../A.in","r",stdin);
//freopen("../A.out","w",stdout);
cin>>t;
while(t--){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>e[i].u>>e[i].v>>e[i].w;
}
for(int i=1;i<=6;i++)cin>>start[i]>>target[i];
for(int s=1;s<=6;s++){
for(int i=0;i<n;i++)d[i]=INF;
d[target[s]]=0;
for(int i=1;i<n;i++){
for(int j=1;j<=m;j++){
d[e[j].v]=min(d[e[j].v],d[e[j].u]+e[j].w);
}
}
cout << -d[start[s]]<<'\n';
e[++m]={start[s],target[s],-d[start[s]]};
}
}
return 0;
}The Preliminary Contest for ICPC Asia Nanjing 2019
原文：https://www.cnblogs.com/heyuhhh/p/11445496.html