CF1580 div1
A:
傻逼题，一开始没想出来，冷静了一会发现可以枚举两行，中间记录个前缀后缀最小值就行了
B:
考虑dp，设f[n][m][k]为答案，发现枚举最大数的位置可以做，于是就做了
N^5tm能过
C:
想了一会，然后5ab说可以根号分治，我想了想好像真可以，于是就写了。
x+y大于sqrtn的直接开大桶算贡献，反正不会T
x+y小于sqrtn的，因为只有sqrt种x+y，直接对于每种开一个余数的小桶记录，修改的时候暴力修改，反正不会T
D:
只要会dicker树的人一般都会，可惜我不会
建出dicker树，考虑把答案转成这样:
$ \sum_{i=1}{n}\sum_{j=1} a_i+a_j-2\times a_{lca(i,j)}$
这东西很像距离，于是w(i,j)=ai-aj,这东西就是距离了
于是变成要求树上选m个点，两两距离和最大
这东西转成贡献，上树形dp就行了
f[i][j]表示考虑了i子树内选出j个点，边的贡献和最大是多少
$f[u][j]=\max(f[v][k]+f[u][j-k]+Wv×j×(M-j))$
O(N^2)
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=4005;
int a[N],ls[N],rs[N],sz[N];
int st[N],tot;
typedef long long ll;
ll lw[N],rw[N],f[N][N];
void dfs(int u){
int i,j;sz[u]=1;
if(ls[u]){
dfs(ls[u]);
for(i=min(sz[u],m);i>=0;i--)
for(j=min(sz[ls[u]],m);j>=0;j--)
f[u][i+j]=max(f[u][i+j],f[ls[u]][j]+lw[u]*j*(m-j));
sz[u]+=sz[ls[u]];
}
if(rs[u]){
dfs(rs[u]);
for(i=min(sz[u],m);i>=0;i--)
for(j=min(sz[rs[u]],m);j>=0;j--)
f[u][i+j]=max(f[u][i+j],f[u][i]+f[rs[u]][j]+rw[u]*j*(m-j));
sz[u]+=sz[rs[u]];
}
}
int main(){
int i;
cin>>n>>m;
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
while(tot>0&&a[st[tot]]>a[i])ls[i]=st[tot],lw[i]=a[st[tot]]-a[i],tot--;
if(tot)rs[st[tot]]=i,rw[st[tot]]=a[i]-a[st[tot]];
st[++tot]=i;
}
dfs(st[1]);
cout<<f[st[1]][m];
return 0;
}
接下来是更重要的反思:
这场比赛前4题都是力所能及的，zky90分钟就全过了
然而由于状态原因（累、太不激动），脑子不是很活跃。
排列的问题大多可以通过枚举最大值解决，但我忘了。
根号分治没想到可以把<sqrtn的直接暴力开桶
。。。
以后一定要早睡，给第二天一个好状态！
不要思维定势！！！
UOJ Round #22
估计是AFO前第一场也是最后一场UOJ了
A是个傻逼题，卡2log，煞笔煞笔煞笔
B、C完全不会
反思:过了大样例也要思考如何卡常！！！
LG 10月月赛I
C 构造题，一如既往地不会！！！
D 根本没来得及仔细想，也没透彻理解算本质不同子序列的性质！！！
反思:多刷构造题，数学构造都是解方程！
每道题都是可做的！要迎难而上！
LG 10月月赛II
C是个傻逼，但可惜我没发现单调性，于是只会90
D是个傻逼，经过CXY提醒后过了
反思:像C这种细节巨大的ds题，考场上直接交暴力！
CF 1592div2
ABC没看，是5ab写的
D也没想到dfs序的做法，搞了个子树大小，但既然数据水就算了。。。
E嘛，反正我只会每一位拆开算，懒得写。具体说就是枚举到一个位，区间长度是偶数并且与起来全是1，然后前面几位只能全是0（如果都是1那长度就是奇数了不符）所以，与起来为0且有偶数个1（前缀异或值相同）
F1，一直以为是DP，没想到贪心做法这么巧妙，给出题人点赞！Orz 9999！%%%
F2，巧妙的建二分图，Orz 9999！%%%
反思:树上二分考虑dfs序，这是好的
时间来不及了就不要写ds题！(和9999一样)
其实不需要啥事都往dp想，百、千级别的数据范围还可以是二分图！
实在不会做了或者太难写了就跳题罢！
NC 赛前训练营 4 T3
从小到大考虑选取第j个可以被贿赂的人，F[i][j]表示已经考虑了前i个人并且树上从根到i的路径上被取人的状态是j的方案数。组合数转移！
考虑n很小，爆搜出可能的序列，也很少，于是直接暴力带入序列进行DP就行了！！！
多做做鼠穴DP题
从小到大考虑dp，可以方便很多
CF EDU div2 115
E是个傻逼题，我不到10分钟就想到了，但因为没有选择比较好的实现方式，考试结束都没调完。
F也是个傻逼题，n很小，可以考虑状压dp，把括号序列转成1,-1的序列，再记录每个串的和，和前缀最小值的位置。直接在vector里面二分即可。
最近怎么看到DP就不会啊，还是要多做做DP
最近喜欢做一些似是而非的神必ds题
首先观察到答案就是按Bi排序的逆序对数
答案可以这么计算：
$\sum_{i=1}^k \sum_{j=i+1}^k f(S[b[i]],S[b[j]])$
$ 其中 S[i] 表示权值为i的位置集合，f(A,B)代表B中每个数在A中贡献逆序对数之和（类似归并）$
因为交换的是相邻的b[i],所以对答案的影响就是$2f(S[b[i]],S[b[i+1]])-c[b[i]]\times c[b[i+1]]$
考虑n是1e5级别的，同时这柿子也没啥性质，于是考虑根号分治。
考虑询问(b[x],b[x+1])时,分成两种情况：
- $\max(cnt[b[x]],cnt[b[x+1]]) \le \sqrt n$
:此时直接暴力双指针O(sqrt N)算贡献 - $\max(cnt[b[x]],cnt[b[x+1]]) > \sqrt n$ 这样的b[x]不超过$\sqrt n $个（称为关键点），所以离线在每个关键点上O(n)处理每个包含此关键点的询问的答案
#include<bits/stdc++.h>
using namespace std;
int n,k,m;
const int N=100005,M=1000005;
int a[M],b[M];
#define lim 100
int Q[M][2];
vector<int> g[M];
#define P pair<int,int>
#define fi first
#define se second
vector<P > q[M];
typedef long long ll;
ll c[M],s[M],w[M],u[M];
#define lowbit(x) x&-x
void add(int x){
while(x<=k){
u[x]++;
x+=lowbit(x);
}
}
ll sum(int x){
ll res=0;
while(x){
res+=1ll*u[x];
x-=lowbit(x);
}
return res;
}
inline ll solve(int x,int y){
register int i;int p=1;
ll ans=0;
for(i=1;i<=g[x].size();++i){
while(p<=c[y]&&g[y][p-1]<g[x][i-1])p++;
ans+=1ll*(p-1);
}
return ans;
}
inline void sol(int x){
int tot=0;register int i;
memset(w,0,sizeof(w));
for(i=n;i>=1;--i){
if(a[i]==x)tot++;
else w[a[i]]+=1ll*tot;
}
for(i=0;i<q[x].size();++i){
int to=q[x][i].fi,id=q[x][i].se;
s[id]=w[to];
}
}
inline int read(){
char c=getchar();int O=0;
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')O=(O<<1)+(O<<3)+(c^48),c=getchar();
return O;
}
int main(){
register int i;
n=read(),k=read(),m=read();
for(i=1;i<=n;++i)a[i]=read(),g[a[i]].push_back(i),c[a[i]]++;
for(i=n;i>=1;--i)s[0]+=sum(a[i]-1),add(a[i]);
for(i=1;i<=k;++i)b[i]=i;
for(i=1;i<=m;++i){
int p=read();swap(b[p],b[p+1]);
if(max(c[b[p]],c[b[p+1]])<=lim)s[i]=solve(b[p+1],b[p]);
else{
if(c[b[p+1]]>c[b[p]])q[b[p+1]].push_back(make_pair(b[p],i));
else q[b[p]].push_back(make_pair(b[p+1],i));
}
Q[i][0]=b[p+1],Q[i][1]=b[p];
}
for(i=1;i<=k;++i)if(c[i]>lim)sol(i);
for(i=1;i<=m;++i){//求XI[x,y] when c[x],c[y]>sqrt(n)
int x=Q[i][0],y=Q[i][1];
if(max(c[x],c[y])<=lim)s[i]=s[i-1]-s[i]*2+c[x]*c[y];
else{
if(c[x]<=c[y])s[i]=s[i-1]+s[i]*2-c[x]*c[y];
else s[i]=s[i-1]-s[i]*2+c[x]*c[y];
}
printf("%lld\n",s[i]);
}
return 0;
}
[CCO2021]SWAP SWAP SORT
一开始写的是错解却过了
看到最小化极差想到双指针，毕竟已经被ZJOI搞过一次了。
每次枚举选进的点，看只选这些点和最短路上的边，能不能从1走到n，BFS就行了。
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m;
typedef long long ll;
int cnt,h[N],nxt[N],to[N];
ll val[N],a[N];
void add(int x,int y,ll z){
nxt[++cnt]=h[x];
h[x]=cnt;
to[cnt]=y,val[cnt]=z;
}
queue<int> q;
struct node{
int id;ll v;
bool operator < (const node &w)const{
return v>w.v;
}
};
priority_queue<node> Q;
int vis[N];
ll dis[N];
int ok[N],bl[N];
int cmp(int x,int y){
return a[x]<a[y];
}
void dij(){
for(int i=2;i<=n;i++)dis[i]=1e18;
Q.push((node){1,0});
while(!Q.empty()){
node u=Q.top();Q.pop();
for(int i=h[u.id];i;i=nxt[i]){
int v=to[i];ll w=val[i];
if(dis[v]>dis[u.id]+w){
dis[v]=dis[u.id]+w;
Q.push((node){v,dis[v]});
}
}
}
}
int bfs(){
while(!q.empty())q.pop();
memset(vis,0,sizeof(vis));
if(!ok[1]||!ok[n]){return 0;}
q.push(1),vis[1]=1;
while(!q.empty()){
int x=q.front();q.pop();
if(n==x){return 1;}
for(int i=h[x];i;i=nxt[i]){
int v=to[i];ll w=val[i];
if(ok[v]&&dis[v]==dis[x]+w&&!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
return 0;
}
int main(){
int i;
cin>>n>>m;
for(i=1;i<=n;i++)scanf("%lld",&a[i]),bl[i]=i;
sort(bl+1,bl+n+1,cmp);
for(i=1;i<=m;i++){
int x,y;ll z;
scanf("%d%d%lld",&x,&y,&z);
add(x,y,z),add(y,x,z);
}
dij();
cout<<dis[n]<<endl;
int r=0;
ll ans=2e18;
for(i=1;i<=n;i++){
r=max(r,i-1);
int flag=0;
while(r<=n){
if(bfs()){
flag=1;
break;
}
ok[bl[++r]]=1;
}
if(flag)ans=min(ans,a[bl[r]]-a[bl[i]]);
ok[bl[i]]=0;
}
cout<<ans<<endl;
return 0;
}
题目叫不想爬坡
rnm，终于过了，不开O2荣登最劣解
建立因数trie
显然每次贪心往自己最小的因数走，不超过log步
用set维护一下子树的不同质因子个数(每个数最多8个)和儿子的倍数就行了
O(8nlogn^2),还用了一堆set,比cxy劣了128倍
#include<bits/stdc++.h>
using namespace std;
#define ri register int
const int N=1e5+5;
int n;
struct st{int x,id;}p[N];
int cmp(const st &a,const st &b){return a.x < b.x;}
int ok=1,fa[N];
namespace GTR {
const int bufl=1<<15;char buf[bufl],*s=buf,*t=buf;
inline int fetch(){if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}return *s++;}
inline int read(){int a=0,b=1,c=fetch();while(!isdigit(c))b^=c=='-',c=fetch();while(isdigit(c))a=(a<<1)+(a<<3)+(c^48),c=fetch();return b?a:-a;}
inline void write(int x){if(x>9)write(x/10);putchar(x%10+48);}}
using GTR::read;using GTR::write;
multiset<int> g[N],G[N];
const int M=1000000;
int tot,pr[M+5],vis[M+5],mn[M+5],f[N];
int cnt,h[M],nxt[M*3],to[M*3];
inline void add(int x,int y){
nxt[++cnt]=h[x];
h[x]=cnt;
to[cnt]=y;
}
void xs(int mx){
ri i,j;
for(i=2;i<=mx;++i){
if(!vis[i]){
pr[++tot]=i;
mn[i]=i;
}
for(j=1;pr[j]<=mx/i&&j<=tot;++j){
mn[i*pr[j]]=min(mn[i],pr[j]);
vis[i*pr[j]]=1;
if(i%pr[j]==0)break;
}
}
}
void pan(int cur,int ban,int x){
for(ri j=h[x];j;j=nxt[j])
if(g[cur].count(to[j])>G[ban].count(to[j])){
ok=0;
return ;
}
}
int mx;
#define P pair<int,int>
set<P > s[N];
void upd(int cur,int tar){
while(ok){
int fl=0;P w=make_pair(p[tar].x,0),x;
if(p[cur].x==p[tar].x){
fa[p[tar].id]=p[cur].id;
return ;
}
if(s[cur].lower_bound(w)!=s[cur].end()){
x=*s[cur].lower_bound(w);
if(x.first==p[tar].x)pan(cur,x.second,p[tar].x/p[cur].x),fl=1,cur=x.second;
}
if (!fl){
pan(cur,0,p[tar].x/p[cur].x);
fa[p[tar].id]=p[cur].id;
f[tar]=cur;
for(ri i=p[tar].x;i<=mx;i+=p[tar].x)s[cur].insert(make_pair(i,tar));
int pos=tar;
while(pos){
for(ri i=h[p[tar].x/p[pos].x];i;i=nxt[i])g[pos].insert(to[i]);
if(f[pos])for(ri i=h[p[tar].x/p[f[pos]].x];i;i=nxt[i])G[pos].insert(to[i]);
pos=f[pos];
}
return;
}
}
}
int main(){
ri i,j;
n=read();
for(i=1;i<=n;++i)p[i]=(st){read(),i},mx=max(mx,p[i].x);
sort(p+1,p+n+1,cmp);
xs(mx);
for(i=2;i<=mx;++i){
int w=i,ls=0;
while(w>1){
if(mn[w]!=ls){
add(i,mn[w]);
ls=mn[w];
}
w/=mn[w];
}
}
for(i=2;i<=n&&ok;++i){
if(p[i].x%p[1].x){puts("-1");return 0;}
upd(1,i);
}
if(ok==0)puts("-1");
else for(i=1;i<=n;++i)write(fa[i]),putchar(' ');
return 0;
}
这题叫GCD TREE
NC周赛TG28题解
T1 傻逼期望题，不用想复杂，考虑相邻边对自己的贡献即可
T2 好题：
考虑把指数拆开，$A^p= (Ap-A)+(A{p-1}-A)+...+(A-1)+(1-0)$ 因为柿子中每一项都比后一项大，所以如果把每项的价值定为1，重量定位自己的话，肯定是从小往大取到某一项，等价于在所有次幂中选择一个，价值是幂。
因为wi很大，所以我们考虑用答案去拼出wi，因为要求最大，所以相当于处理刚好x个能拼出的最小数（容易发现x是$\sqrt n$ 级别的），所以考虑取前x个最小的就行了。于是就从小到大枚举$d$,看d能被加入几次，不断减掉就行了。
T3 cxy的神题
我想了一年都不会啊。
首先找到 [l1, r1] 中的最大值，设其为 x，然后在 [l2, r2] 中找有没有合法的配对，如果有，直接
return，否则说明 [l2, r2] 中没有值在 [x/2, x − 1] 中的数。
然后去找到 [l2, r2] 中小于x/2的最大值，设其为 y，然后在 [l1, r1] 里找有没有合法的配对，如果
有，return，否则说明 [l1, r1] 中没有值在 [y + 1, 2 × y − 1] 内的数。
然后再在 [l1, r1] 中找到小于 y + 1 的最大数，如此这样循环往复，仍然是 log v 次枚举后排除所有
值域。
在 [l, r] 中找值域在 [L, R] 的数中的最大值可以用主席树求解。