szzq学长出的题，先orz一下。
day1
倾斜的线
做过差不多的题，写在我自己的博客里，我却忘得一干二净，反而李巨记得清清楚楚我写了的。
题目就是要最小化这个东西
$|\frac{y_i-y_j}{x_i-x_j}- \frac{P}{Q}|$
通分
$\frac{Q*(y_i-y_j)-P*(x_i-x_j)}{Q*(x_i-x_j)}$
把$Q*x$作为新的$x$,$Q*y-P*x$作为新的$y$,题面转换为求两点斜率绝对值的最小值。
按y排序后可发现答案一定出现在相邻的两点间(画图可得)。
//Achen
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
#define Formylove return 0
#define inf 1e18
const int N=2e5+;
using namespace std;
typedef long long LL;
typedef double db;
int n,ok;
db ans,bs;
LL P,Q; template<typename T>void read(T &x) {
T f=; x=; char ch=getchar();
while(ch!='-'&&(ch<''||ch>'')) ch=getchar();
if(ch=='-') f=-,ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;
} struct pt {
LL x,y,nx,ny;
friend bool operator <(const pt&A,const pt&B) {
return A.ny<B.ny;
}
}p[N],ap,bp; #define eps 1e-15
int dcmp(db x) { return fabs(x)<eps?:(x>?:-); }
db xl(pt A,pt B) { return ((db)A.y-B.y)/(1.0*((db)A.x-B.x)); }
LL gcd(LL a,LL b) {
return !b?a:gcd(b,a%b) ;
} #define ANS
int main() {
#ifdef ANS
freopen("slope.in","r",stdin);
freopen("slope.out","w",stdout);
#endif
read(n); read(P); read(Q);
For(i,,n) {
read(p[i].x);
read(p[i].y);
p[i].nx=Q*p[i].x;
p[i].ny=Q*p[i].y-P*p[i].x;
}
sort(p+,p+n+);
bs=((db)P)/(1.0*Q);
For(i,,n) {
int j=i-;
db t=xl(p[i],p[j]);
if(t<) continue;
if(!ok||dcmp(fabs(ans-bs)-fabs(t-bs))>||(dcmp(fabs(ans-bs)-fabs(t-bs))==&&dcmp(ans-t)>)) {
ok=; ans=t; ap=p[i]; bp=p[j];
}
}
if(ap.y<bp.y) swap(ap,bp);
LL up=ap.y-bp.y,dn=ap.x-bp.x;
LL d=gcd(up,dn);
printf("%lld/%lld\n",up/d,dn/d);
//cerr<<clock()<<endl;
Formylove;
}
扭动的树
并不难的dp,太久没做dp脑子秀逗了吧。
直接上题解了
二叉查找树按照键值排序的本质是中序遍历,每次我们可以在当前区间中提取出
一个根,然后划分为两个子区间做区间 DP。记 dp[i][j][k]表示区间[i, j]建子树,子树
根节点的父亲是第 k 个数的最大 sum 值之和。由于 k 只能为 i-1 或 j+1,故状态数只
有 O(n^2 ),总复杂度 O(n^3 )。
//Achen
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
#define Formylove return 0
const int N=;
using namespace std;
typedef long long LL;
typedef double db;
int n;
LL ans=-,f[N][N][],sum[N][N],gcd[N][N]; template<typename T>void read(T &x) {
T f=; x=; char ch=getchar();
while(ch!='-'&&(ch<''||ch>'')) ch=getchar();
if(ch=='-') f=-,ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;
} struct node {
LL k,v;
friend bool operator <(const node&A,const node&B) {
return A.k<B.k;
}
}p[N]; LL GCD(LL a,LL b) { return !b?a:GCD(b,a%b); } void MX(LL &x,LL y) { if(x<y) x=y; } #define ANS
int main() {
#ifdef ANS
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
#endif
read(n);
For(i,,n) {
read(p[i].k);
read(p[i].v);
}
sort(p+,p+n+);
For(i,,n) For(j,,n) gcd[i][j]=GCD(p[i].k,p[j].k);
For(i,,n) For(j,i,n) {
sum[i][j]=sum[i][j-]+p[j].v;
}
memset(f,,sizeof(f));
For(i,,n) {
if(i!=&&gcd[i][i-]!=) f[i][i][]=p[i].v;
if(i!=n&&gcd[i][i+]!=) f[i][i][]=p[i].v;
}
For(len,,n) {
For(i,,n-len+) {
int j=i+len-;
if(f[i+][j][]>) {
if(i!=&&gcd[i-][i]!=)
MX(f[i][j][],f[i+][j][]+sum[i][j]);
if(j!=n&&gcd[j+][i]!=)
MX(f[i][j][],f[i+][j][]+sum[i][j]);
}
if(f[i][j-][]>) {
if(i!=&&gcd[i-][j]!=)
MX(f[i][j][],f[i][j-][]+sum[i][j]);
if(j!=n&&gcd[j+][j]!=)
MX(f[i][j][],f[i][j-][]+sum[i][j]);
}
For(k,i+,j-)
if(f[i][k-][]>&&f[k+][j][]>) {
if(i!=&&gcd[i-][k]!=)
MX(f[i][j][],f[i][k-][]+f[k+][j][]+sum[i][j]);
if(j!=n&&gcd[j+][k]!=)
MX(f[i][j][],f[i][k-][]+f[k+][j][]+sum[i][j]);
}
}
}
if(f[][n][]>) MX(ans,f[][n][]+sum[][n]);
if(f[][n-][]>) MX(ans,f[][n-][]+sum[][n]);
For(i,,n-) if(f[][i-][]>&&f[i+][n][]>)
MX(ans,f[][i-][]+f[i+][n][]+sum[][n]);
printf("%lld\n",ans);
//cerr<<clock()<<endl;
Formylove;
}
打铁的匠
题目有歧义啊，我以为是每个点到父亲的边权值大于那么多，结果是到指定点的权值大于那么多，，，那么就是线段树合并的裸题了。题解给的treap启发式合并，一个意思。
//Achen
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
#define Formylove return 0
const int N=1e5+;
using namespace std;
typedef long long LL;
typedef double db;
int n,m,UP,fa[N],w[N];
LL ans[N]; template<typename T>void read(T &x) {
T f=; x=; char ch=getchar();
while(ch!='-'&&(ch<''||ch>'')) ch=getchar();
if(ch=='-') f=-,ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;
} struct node {
int w,id;
node(int w,int id):w(w),id(id){}
};
vector<node>vc[N]; LL sg[N*];
int sg2[N*];
int ch[N*][];
int tot;
#define lc ch[x][0]
#define rc ch[x][1]
#define mid ((l+r)>>1)
int merge(int x,int y,int l,int r) {
if(!(x*y)) return (x^y);
if(l==r) {
sg2[x]+=sg2[y];
sg[x]+=sg[y]; return x;
}
lc=merge(lc,ch[y][],l,mid);
rc=merge(rc,ch[y][],mid+,r);
sg[x]=sg[lc]+sg[rc];
sg2[x]=sg2[lc]+sg2[rc];
return x;
} void update(int &x,int l,int r,int pos) {
if(!x) x=++tot;
if(l==r) {
sg[x]+=pos;
sg2[x]++;
return;
}
if(pos<=mid) update(lc,l,mid,pos);
else update(rc,mid+,r,pos);
sg[x]=sg[lc]+sg[rc];
sg2[x]=sg2[lc]+sg2[rc];
} #define pr pair<int,LL>
pr operator +(const pr&A,const pr&B) {
return make_pair(A.first+B.first,A.second+B.second);
}
pr qry(int x,int l,int r,int ql,int qr) {
if(!x) return make_pair(,);
if(l>=ql&&r<=qr) return make_pair(sg2[x],sg[x]);
if(qr<=mid) return qry(lc,l,mid,ql,qr);
if(ql>mid) return qry(rc,mid+,r,ql,qr);
return qry(lc,l,mid,ql,qr)+qry(rc,mid+,r,ql,qr);
} int ecnt,fir[N],nxt[N<<],to[N<<];
void add(int u,int v) {
nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v;
} int rt[N],R[N],sz[N];
int val[N];
void dfs(int x) {
sz[x]=;
R[x]=R[fa[x]]+;
for(int i=fir[x];i;i=nxt[i]) {
val[to[i]]=val[x]+w[to[i]];
dfs(to[i]);
sz[x]+=sz[to[i]];
}
} void DFS(int x) {
for(int i=fir[x];i;i=nxt[i]) {
DFS(to[i]);
rt[x]=merge(rt[x],rt[to[i]],,UP);
}
update(rt[x],,UP,val[x]);
int up=vc[x].size();
For(i,,up-) {
int w=vc[x][i].w,id=vc[x][i].id;
pr tt=qry(rt[x],,UP,val[x]+w,UP);
ans[id]=tt.second-(LL)tt.first*val[x];
}
} #define ANS
int main() {
#ifdef ANS
freopen("forging.in","r",stdin);
freopen("forging.out","w",stdout);
#endif
read(n);
For(i,,n) {
read(fa[i]);
read(w[i]);
add(fa[i],i);
}
read(m);
For(i,,m) {
int u,w;
read(u); read(w);
vc[u].push_back(node(w,i));
}
UP=(n+)*;
dfs();
DFS();
For(i,,m) printf("%lld\n",ans[i]);
//cerr<<clock()<<endl;
Formylove;
}
/*
10
1 6
2 2
3 5
2 3
5 5
6 2
5 4
10 3
1 2
4
2 3
2 2
2 5
1 3
*/
day2
古代龙人的谜题
全机房集体猜题意半小时，终于被辉神凑过了样例。
题目转化求除l,r之外还有1存在，且1的总个数为奇数的区间个数。1的个数为奇数的区间很好找，特判一下只有l,r上有1的区间即可。
//Achen
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
#define Formylove return 0
const int N=1e6+;
using namespace std;
typedef long long LL;
typedef double db;
int n,idx;
char s[N]; template<typename T>void read(T &x) {
T f=; x=; char ch=getchar();
while(ch!='-'&&(ch<''||ch>'')) ch=getchar();
if(ch=='-') f=-,ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;
} #define ANS
int main() {
#ifdef ANS
freopen("puzzle.in","r",stdin);
freopen("puzzle.out","w",stdout);
#endif
read(idx);
read(n);
scanf("%s",s+);
LL ans=,c1=,c0=;
if(s[]=='') c0=; else c1=;
For(i,,n) {
if(s[i]=='') {
ans+=c0;
swap(c0,c1);
c1++;
}
else {
ans+=c1;
c0++;
}
}
int cc=;
For(i,,n) {
if(s[i]=='') cc++;
else {
ans-=cc; cc=;
}
}
cc=;
Rep(i,n,) {
if(s[i]=='') cc++;
else {
ans-=cc; cc=;
}
}
printf("%lld\n",ans);
//cerr<<clock()<<endl;
Formylove;
}
交错的字符串
这个就是传说中的折半搜索？
把字符串拆成{S1,S2},即n个字符属于S1,n个属于S2，那么根据前n个字符哪些属于S1哪些属于S2就可以得出S1，S2是什么串了。
暴力枚举前n个哪些属于S1，用mp存下这种情况对应的串，再暴力枚举后n个位置能对应的串计算答案即可。
//Achen
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
#define Formylove return 0
const int N=;
using namespace std;
typedef long long LL;
typedef double db;
int n;
LL ans;
char s[N],a[N]; template<typename T>void read(T &x) {
T f=; x=; char ch=getchar();
while(ch!='-'&&(ch<''||ch>'')) ch=getchar();
if(ch=='-') f=-,ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;
} #define pr pair<LL,LL>
#define MP make_pair
#define fi first
#define se second
map<pr,int>mp[]; pr hash() {
pr rs=MP(,);
For(i,,n/)
rs.fi=rs.fi*+a[i]-'a';
For(i,n/+,n)
rs.se=rs.se*+a[i]-'a';
return rs;
} #define ANS
int main() {
#ifdef ANS
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
#endif
read(n);
scanf("%s",s+);
int up=(<<n)-;
For(S,,up) {
int cc=,l=,r=n;
For(i,,n) {
if(S&(<<(i-))) { cc++; a[l++]=s[i]; }
else a[r--]=s[i];
}
pr H=hash();
mp[cc][H]++;
}
For(S,,up) {
int cc=,l=,r=n;
For(i,,n) {
if(S&(<<(i-))) { cc++; a[l++]=s[*n-i+]; }
else a[r--]=s[*n-i+];
}
pr H=hash();
if(mp[cc][H])
ans+=mp[cc][H];
}
printf("%lld\n",ans/);
//cerr<<clock()<<endl;
Formylove;
}
世界第一的猛汉王
以为能AK结果把曼哈顿距离误当成切比雪夫距离然后爆0了。
把x,y改成x+y,x-y就A了？？？
亏死了。
题解：
先把曼哈顿距离转换成切比雪夫距离，然后距离一个点距离不超过d的范围变成了一个框框，非常优美。
题目转换为给定一张竞赛图，有些边未定向，给这些边定向使得猛汉三角最多和最少。
点分为黑白两色，根据题目要求，猛汉三角只能是黑白黑或者白黑白，考虑一种情况，另一种是对称的。
猛汉三角只能长这样
对于一个黑点，一个在它框内的白点a和不在它框内的白点b，如果a,b之间的边是b指向a的，贡献就为1。
也就是对于两个白点a,b，如果边是b指向a的，那么贡献就是在a的框内不在b的框内的黑点个数，反之亦然。
那么最大的答案就是，考虑每一对同色点，在其中一个的框内不在另一个框内的点的个数较多的个数之和，最小反之。
发现比较每一对同色的点的这个（”在其中一个的框内不在另一个框内的点的个数“）个数，公共的部分没有影响，也就是比较这对点的框内的异色点的个数。那么按框内异色点的个数排序，答案最大的时候我和我前面的点都选我，我和我后面的点都选我后面的，最小反之。
求每个点框内异色点的个数，扫描线即可，闲的蛋疼的话估计啥子树套树也不是不能做。
//Achen
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
#define Formylove return 0
const int N=1e5+;
using namespace std;
typedef long long LL;
typedef double db;
int n,m,d;
LL UP=3e9+;
LL ans1,ans2; template<typename T>void read(T &x) {
T f=; x=; char ch=getchar();
while(ch!='-'&&(ch<''||ch>'')) ch=getchar();
if(ch=='-') f=-,ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;
} int rt,tot,sg[N*],ch[N*][];
#define lc ch[x][0]
#define rc ch[x][1]
#define mid ((l+r)>>1)
void update(int &x,LL l,LL r,LL pos) {
if(!x) {
x=++tot; sg[x]=lc=rc=;
}
if(l==r) {
sg[x]++; return;
}
if(pos<=mid) update(lc,l,mid,pos);
else update(rc,mid+,r,pos);
sg[x]=sg[lc]+sg[rc];
} int qry(int x,LL l,LL r,LL ql,LL qr) {
if(!x) return ;
if(l>=ql&&r<=qr) return sg[x];
if(qr<=mid) return qry(lc,l,mid,ql,qr);
if(ql>mid) return qry(rc,mid+,r,ql,qr);
return qry(lc,l,mid,ql,qr)+qry(rc,mid+,r,ql,qr);
} struct node {
LL x,y,k;
friend bool operator <(const node&A,const node&B) {
return A.k<B.k;
}
}b[N],w[N]; struct Q{
LL x,l,r; int f,id;
Q(){}
Q(LL x,LL l,LL r,int f,int id):x(x),l(l),r(r),f(f),id(id){}
friend bool operator<(const Q&A,const Q&B) {
return A.x<B.x||(A.x==B.x&&A.f<B.f);
}
}q[N*];
int cnt; void solve(node b[],node w[],int n,int m) {
rt=tot=; cnt=;
For(i,,n)
q[++cnt]=Q(b[i].x,b[i].y,b[i].y,,i);
For(i,,m) {
if(w[i].x-d>) q[++cnt]=Q(w[i].x-d-,max(w[i].y-d,1LL),min(w[i].y+d,UP),,i);
q[++cnt]=Q(min(w[i].x+d,UP),max(w[i].y-d,1LL),min(w[i].y+d,UP),,i);
}
sort(q+,q+cnt+);
For(i,,cnt) {
if(q[i].f==) update(rt,,UP,q[i].l);
else {
int tp=qry(rt,,UP,q[i].l,q[i].r);
if(q[i].f==) w[q[i].id].k-=tp;
else w[q[i].id].k+=tp;
}
}
} #define ANS
int main() {
#ifdef ANS
freopen("mhw.in","r",stdin);
freopen("mhw.out","w",stdout);
#endif
read(n); read(m); read(d);
For(i,,n) {
LL x,y;
read(x); read(y);
b[i].x=x+y+1e9+;
b[i].y=x-y+1e9+;
}
For(i,,m) {
LL x,y;
read(x); read(y);
w[i].x=x+y+1e9+;
w[i].y=x-y+1e9+;
}
solve(b,w,n,m);
solve(w,b,m,n);
For(i,,n) {
LL tp=b[i].k;
ans1-=tp*(tp-)/;
ans2-=tp*(tp-)/;
}
For(i,,m) {
LL tp=w[i].k;
ans1-=tp*(tp-)/;
ans2-=tp*(tp-)/;
}
sort(b+,b+n+);
sort(w+,w+m+);
For(i,,n) {
ans1+=b[i].k*(n-i);
ans2+=b[i].k*(i-);
}
For(i,,m) {
ans1+=w[i].k*(m-i);
ans2+=w[i].k*(i-);
}
printf("%lld %lld\n",ans1,ans2);
//cerr<<clock()<<endl;
Formylove;
}