A.OO’s Sequence
计算每个数的贡献
找出第(i)个数左边最靠右的因子位置(lp)和右边最靠左的因子位置(rp)
对答案的贡献就是((rp-i)*(i-lp))
最后答案就是(sum_{i=1}^{n}(rp_i-i)*(i-lp_i))
预处理出来所有的因子，复杂度(O(nsqrt{10000}))
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
typedef long long int LL;
const int MAXN = 1e5+7;
const LL MOD = 1e9+7;
int n,A[MAXN],pos[MAXN],rp[MAXN],lp[MAXN];
vector<int> vec[MAXN];
void preprocess(){
for(int i = 1; i <= 10000; i++){
for(int j = i; j <= 10000; j += i){
vec[j].push_back(i);
}
}
}
void solve(){
for(int i = 1; i <= n; i++) scanf("%d",&A[i]);
memset(pos,0,sizeof(pos));
for(int i = 1; i <= n; i++){
lp[i] = 0;
for(int x : vec[A[i]]) lp[i] = max(lp[i],pos[x]);
pos[A[i]] = i;
}
memset(pos,0x3f,sizeof(pos));
for(int i = n; i >= 1; i--){
rp[i] = n + 1;
for(int x : vec[A[i]]) rp[i] = min(rp[i],pos[x]);
pos[A[i]] = i;
}
LL ret = 0;
for(int i = 1; i <= n; i++) ret = (ret + (i-lp[i]) * (rp[i]-i)) % MOD;
printf("%I64d
",ret);
}
int main(){
preprocess();
while(scanf("%d",&n)!=EOF) solve();
return 0;
}
B.Assignment
把每个位置作为右端点固定之后找长度最长的可行序列
ST表配合二分来找
复杂度(O(nlog n))
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 1e5+7;
typedef long long int LL;
int n,k,ST[2][MAXN][20];
int qmin(int L, int R){
int d = log2(R-L+1);
return min(ST[0][L][d],ST[0][R-(1<<d)+1][d]);
}
int qmax(int L, int R){
int d = log2(R-L+1);
return max(ST[1][L][d],ST[1][R-(1<<d)+1][d]);
}
void solve(){
scanf("%d %d",&n,&k);
for(int i = 1; i <= n; i++){
scanf("%d",&ST[0][i][0]);
ST[1][i][0] = ST[0][i][0];
}
for(int j = 1; (1<<j) <= n; j++){
for(int i = 1; i + (1<<j) - 1 <= n; i++){
ST[0][i][j] = min(ST[0][i][j-1],ST[0][i+(1<<(j-1))][j-1]);
ST[1][i][j] = max(ST[1][i][j-1],ST[1][i+(1<<(j-1))][j-1]);
}
}
LL ret = 0;
for(int i = 1; i <= n; i++){
int l = 1, r = i;
while(l<=r){
int mid = (l+r) >> 1;
if(qmax(mid,i)<qmin(mid,i)+k) r = mid - 1;
else l = mid + 1;
}
ret += i - l + 1;
}
printf("%I64d
",ret);
}
int main(){
int T;
for(scanf("%d",&T); T; T--) solve();
return 0;
}
C.Bombing plan
树形DP
难点在于当前点的选择会影响祖先节点的其他子树
可以先不考虑祖先节点的其他子树，只考虑它还能向上延申最远距离
(f[i][j])表示节点(i)能再向上至少控制(j)个节点的最小消耗
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 1e5+7;
const int MAXM = 2e2+7;
const int D = 1e2;
const int INF = 0x3f3f3f3f;
typedef long long int LL;
int n,dist[MAXN],f[MAXN][MAXM],depth[MAXN],sum[MAXN][MAXM];
vector<int> G[MAXN];
int dfs(int u, int par){
depth[u] = depth[par] + 1;
int maxd = depth[u];
memset(sum[u],0,sizeof(sum[u]));
fill(begin(f[u]),end(f[u]),n);
for(int v : G[u]) if(v!=par){
maxd = max(maxd,dfs(v,u));
for(int i = -100; i <= 100; i++) sum[u][i+D] += f[v][i+D];
}
for(int i = -100; i < 0; i++) f[u][i+D] = min(f[u][i+D],sum[u][i+D+1]);
for(int i = 0; i <= 100; i++){
for(int v : G[u]){
if(v==par) continue;
f[u][D+i] = min(f[u][D+i],f[v][D+i+1]+sum[u][D-i]-f[v][D-i]);
}
}
for(int i = -100; i <= depth[u] - maxd - 1; i++) f[u][i+D] = 0;
f[u][dist[u]+D] = min(f[u][dist[u]+D],1+sum[u][D-dist[u]]);
for(int i = 99; i >= -100; i--) f[u][i+D] = min(f[u][i+D],f[u][i+1+D]);
return maxd;
}
void solve(){
for(int i = 1; i <= n; i++) scanf("%d",&dist[i]);
for(int i = 1; i <= n; i++) G[i].clear();
for(int i = 1; i < n; i++){
int u, v;
scanf("%d %d",&u,&v);
G[u].push_back(v); G[v].push_back(u);
}
dfs(1,0);
printf("%d
",f[1][D]);
}
int main(){
while(scanf("%d",&n)!=EOF) solve();
return 0;
}
D.Candy Distribution
E.Pocket Cube
F.Tree chain problem
评测机出问题了 测不了不知道对不对
按链的LCA深度排序
然后DP
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 1e5+7;
int n,m,dfn[MAXN],son[MAXN],sz[MAXN],tp[MAXN],depth[MAXN],par[MAXN][20],num,sum[MAXN],f[MAXN];
vector<pair<pair<int,int>,int> > chain[MAXN];
vector<int> G[MAXN];
void dfs1(int u, int fa){
sz[u] = 1; son[u] = 0;
depth[u] = depth[par[u][0] = fa] + 1;
for(int i = 1; par[u][i-1]; i++) par[u][i] = par[par[u][i-1]][i-1];
for(int v : G[u]){
if(v==fa) continue;
dfs1(v,u);
sz[u] += sz[v];
if(sz[son[u]]<sz[v]) son[u] = v;
}
}
void dfs2(int u, int top){
tp[u] = top;
dfn[u] = ++num;
if(son[u]) dfs2(son[u],top);
for(int v : G[u]){
if(v==son[u] or v==par[u][0]) continue;
dfs2(v,v);
}
}
int LCA(int u, int v){
while(tp[u]!=tp[v]){
if(depth[tp[u]]<depth[tp[v]]) swap(u,v);
u = par[tp[u]][0];
}
if(depth[u]<depth[v]) return u;
else return v;
}
void dfs(int u){
sum[u] = 0;
for(int v : G[u]){
if(v==par[u][0]) continue;
dfs(v);
sum[u] += f[v];
}
f[u] = sum[u];
for(auto ch : chain[u]){
int x = ch.first.first, y = ch.first.second, w = ch.second;
int maxx = sum[u] + w;
if(x!=u){
if(sz[x]!=1) maxx += sum[x];
int z = x;
for(int i = 0; depth[z]-depth[u]-1; i++) if((depth[z]-depth[u]-1)&(1<<i)) z = par[z][i];
if(sz[z]!=1) maxx -= f[z];
}
if(y!=u){
if(sz[y]!=1) maxx += sum[y];
int z = y;
for(int i = 0; depth[z]-depth[u]-1; i++) if((depth[z]-depth[u]-1)&(1<<i)) z = par[z][i];
if(sz[z]!=1) maxx -= f[z];
}
f[u] = max(f[u],maxx);
}
}
void solve(){
scanf("%d %d",&n,&m);
for(int i = 1; i <= n; i++) G[i].clear();
for(int i = 1; i <= n; i++) chain[i].clear();
num = 0;
for(int i = 1; i < n; i++){
int u, v; scanf("%d %d",&u,&v);
G[u].push_back(v); G[v].push_back(u);
}
dfs1(1,0); dfs2(1,1);
for(int i = 0; i < m; i++){
int u, v, w;
scanf("%d %d %d",&u,&v,&w);
chain[LCA(u,v)].push_back(make_pair(make_pair(u,v),w));
}
dfs(1);
printf("%d
",*max_element(f+1,f+1+n));
}
int main(){
int T;
for(scanf("%d",&T); T; T--) solve();
return 0;
}
G. Tricks Device
保留最短路上的边
然后对于第一问跑最小割
第二问删去最短的一条路径即可
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 2222;
const int INF = 0x3f3f3f3f;
#define S 1
#define T n
struct EDGE{
int to,cap,rev;
EDGE(){};
EDGE(int to, int cap, int rev):to(to),cap(cap),rev(rev){};
};
vector<EDGE> G[MAXN];
int n,m,iter[MAXN],rk[MAXN];
void ADDEDGE(int u, int v, int cap){
G[u].push_back(EDGE(v,cap,(int)G[v].size()));
G[v].push_back(EDGE(u,0,(int)G[u].size()-1));
}
bool bfs(){
memset(rk,0,sizeof(rk));
memset(iter,0,sizeof(iter));
rk[S] = 1;
queue<int> que;
que.push(S);
while(!que.empty()){
int u = que.front();
que.pop();
for(auto e : G[u]){
if(!e.cap or rk[e.to]) continue;
rk[e.to] = rk[u] + 1;
que.push(e.to);
}
}
return rk[T]!=0;
}
int dfs(int u, int flow){
if(u==T) return flow;
for(int &i = iter[u]; i < (int)G[u].size(); i++){
auto &e = G[u][i];
if(!e.cap or rk[e.to]!=rk[u]+1) continue;
int d = dfs(e.to,min(e.cap,flow));
if(d){
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
return 0;
}
int Dinic(){
int flow = 0;
while(bfs()){
int d = dfs(S,INF);
while(d){
flow += d;
d = dfs(S,INF);
}
}
return flow;
}
int dist[MAXN];
vector<pair<int,int> > GG[MAXN];
void Dijkstra(){
memset(dist,0x3f,sizeof(dist));
dist[1] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>,greater<pair<int,int>>> que;
que.push(make_pair(dist[1],1));
while(!que.empty()){
auto p = que.top();
que.pop();
if(dist[p.second]!=p.first) continue;
int u = p.second;
for(auto &e : GG[u]){
int v = e.first, w = e.second;
if(dist[v]<=dist[u]+w) continue;
dist[v] = dist[u] + w;
que.push(make_pair(dist[v],v));
}
}
for(int i = 1; i <= n; i++){
for(auto &e : GG[i]){
int v = e.first, w = e.second;
if(dist[i]+w==dist[v]){
ADDEDGE(i,v,1);
}
}
}
}
int BFS(){
memset(dist,INF,sizeof(dist));
dist[S] = 0;
queue<int> que;
que.push(S);
while(!que.empty()){
int u = que.front();
que.pop();
for(auto e : G[u]){
int v = e.to;
if(dist[v]!=INF) continue;
dist[v] = dist[u] + 1;
que.push(v);
}
}
return dist[T]==INF?m:dist[T];
}
void solve(){
for(int i = 1; i <= n; i++) G[i].clear(), GG[i].clear();
for(int i = 1; i <= m; i++){
int u, v, w;
scanf("%d %d %d",&u,&v,&w);
GG[u].push_back(make_pair(v,w));
GG[v].push_back(make_pair(u,w));
}
Dijkstra();
cout << Dinic() << ' ' << m - BFS() << endl;
}
int main(){
while(scanf("%d %d",&n,&m)!=EOF) solve();
return 0;
}
H. Unstable
I.Annoying problem
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 1e5+7;
int n,q,dfn[MAXN],idx,dist[MAXN],par[MAXN][20],depth[MAXN],ret,rdfn[MAXN];
vector<pair<int,int> > G[MAXN];
void dfs(int u, int f){
dfn[u] = ++idx;
rdfn[idx] = u;
depth[u] = depth[par[u][0] = f] + 1;
for(int i = 1; par[u][i-1]; i++) par[u][i] = par[par[u][i-1]][i-1];
for(auto &e : G[u]){
if(e.first==f) continue;
dist[e.first] = dist[u] + e.second;
dfs(e.first,u);
}
}
int LCA(int u, int v){
if(depth[u]<depth[v]) swap(u,v);
for(int i = 0; depth[u] - depth[v]; i++) if((depth[u]-depth[v])&(1<<i)) u = par[u][i];
if(u==v) return u;
for(int i = 19; i >= 0; i--) if(par[u][i]!=par[v][i]){
u = par[u][i];
v = par[v][i];
}
return par[u][0];
}
set<int> S1,S2;
int cal(int u){
int x,y;
if(S1.lower_bound(dfn[u]+1)!=S1.end() and S2.lower_bound(-dfn[u]+1)!=S2.end()){
x = -*S2.lower_bound(-dfn[u]+1);
y = *S1.lower_bound(dfn[u]+1);
}
else{
x = *S1.begin();
y = *S1.rbegin();
}
x = rdfn[x]; y = rdfn[y];
return dist[u] + dist[LCA(x,y)] - dist[LCA(x,u)] - dist[LCA(y,u)];
}
void rua(){
int op, x;
scanf("%d %d",&op,&x);
if(op==1){
if(!S1.count(dfn[x])){
if(!S1.empty()) ret += cal(x);
S1.insert(dfn[x]);
S2.insert(-dfn[x]);
}
}
else{
if(S1.count(dfn[x])){
S1.erase(dfn[x]);
S2.erase(-dfn[x]);
if(!S1.empty()) ret -= cal(x);
}
}
printf("%d
",ret);
}
void solve(int kase){
scanf("%d %d",&n,&q);
for(int i = 1; i <= n; i++) G[i].clear();
memset(par,0,sizeof(par));
idx = 0; S1.clear(); S2.clear(); ret = 0;
for(int i = 1; i < n; i++){
int u, v, w;
scanf("%d %d %d",&u,&v,&w);
G[u].push_back(make_pair(v,w));
G[v].push_back(make_pair(u,w));
}
dfs(1,0);
printf("Case #%d:
",kase);
while(q--) rua();
}
int main(){
int T, kase = 0;
for(scanf("%d",&T); T; T--) solve(++kase);
return 0;
}
J. Y sequence
容斥+迭代
迭代枚举答案(m)，然后计算删掉的个数，对于每个指数(pw)计算一遍，删掉的数量是(pow(m,frac{1}{pw}))，发现是个关于因子的容斥，所以容斥系数是莫比乌斯函数
二分会T，所以用迭代来做，复杂度很玄学
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
typedef long long int LL;
const int MAXN = 111;
int npm[MAXN],mu[MAXN];
LL n,r;
vector<int> prime;
void sieve(){
mu[1] = 1;
for(int i = 2; i < MAXN; i++){
if(!npm[i]){
prime.push_back(i);
mu[i] = -1;
}
for(int j = 0; j < (int)prime.size(); j++){
if(i*prime[j]>=MAXN) break;
npm[i*prime[j]] = true;
mu[i*prime[j]] = -mu[i];
if(i%prime[j]==0){
mu[i*prime[j]] = 0;
break;
}
}
}
}
vector<int> pw;
void prep(){
pw.clear();
for(int i = 0; prime[i]<=r; i++){
int sz = pw.size();
for(int j = 0; j < sz; j++){
int np = pw[j] * prime[i];
if(np>63) continue;
pw.push_back(np);
}
pw.push_back(prime[i]);
}
}
LL f(LL m){
LL tot = 0;
for(auto p : pw) tot += mu[p] * ((LL)pow(m+.5,1./p) - 1);
return m-1+tot;
}
void solve(){
scanf("%I64d %I64d",&n,&r);
prep();
LL tmp = f(n), ret = n;
while(tmp<n){
ret += n - tmp;
tmp = f(ret);
}
printf("%I64d
",ret);
}
int main(){
sieve();
int T;
for(scanf("%d",&T); T; T--) solve();
return 0;
}
K. Solid Geometry Homework
L. Circles Game
只会口胡
圆扫描线+树上删边游戏