A .DZY Loves Physics
题意：给定带点权和边权的无向图，现在让你选一些点，使得 点权和/被选点对间的边权和 最大。
思路：不难证明，选择边和对应的两点是最优的。
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
double a[maxn],ans;
int main()
{
int N,M,u,v; double x;
scanf("%d%d",&N,&M);
rep(i,,N) scanf("%lf",&a[i]);
rep(i,,M){
scanf("%d%d%lf",&u,&v,&x);
ans=max(ans,(a[u]+a[v])/x);
}
printf("%.10lf\n",ans);
return ;
}
B .DZY Loves FFT
题意：给定a数组，范围是1到N；b数组，是0或者1 。a数组和b数组都是随机的。 然后给定规则，ci=max(aj*bk)；满足i=j+k。现在让你求c数组。
思路： 如果b的1的个数比较少，比如num=少于100，我们可以直接暴力，复杂度O(num*N)； 如果1的个数比较多，那么我们可以大胆猜测，排名在前面的S个可以去更新很多地方的答案，假设S=40。 那么只剩下很少的没有被更新，对于这些，我们去暴力更新即可。 复杂度O(40*N+...)
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
int N,D,a[maxn],b[maxn],c[maxn],tot;
int pos[maxn],ans[maxn],X;
int getNextX(){
X=(37LL*X+)%;
return X;
}
int initAB() {
rep(i,,N-) a[i]=i+;
rep(i,,N-) swap(a[i],a[getNextX()%(i+)]);
rep(i,,N-){
if(i<D) b[i]=;
else b[i]=;
}
rep(i,,N-) swap(b[i],b[getNextX()%(i+)]);
}
void get(int p)
{
rep(j,,tot){
if(c[j]>p) break;
ans[p]=max(ans[p],a[p-c[j]]);
}
}
int main()
{
scanf("%d%d%d",&N,&D,&X);
initAB();
rep(i,,N-) pos[a[i]]=i;
rep(i,,N-) if(b[i]) c[++tot]=i;
if(D<){
rep(i,,N-)
rep(j,,tot)
ans[i+c[j]]=max(ans[i+c[j]],a[i]);
}
else {
int B=min(N-,);
rep(i,N-B,N){
int p=pos[i];
rep(j,,tot) {
if(c[j]>N-p) break;
ans[p+c[j]]=max(ans[p+c[j]],a[p]);
}
}
rep(i,,N-) if(!ans[i]) get(i);
}
rep(i,,N-) printf("%d\n",ans[i]);
return ;
}
C .DZY Loves Colors
题意：有一排物体，一开始颜色分别是1到N。假如一个物体颜色是col，修改为x，那么他增加的炫丽度=abs(col-x)；现在进行Q次操作，1操作是区间修改颜色； 2操作是询问区间炫丽度之和。(N<1e5）；
思路：由于要查询区间炫丽度，所以还没法用老司机树，毕竟odt没有历史记录。 所以我们还是用线段树，依然是利用其相同线段的势能关系来解决这个问题。
我们对于颜色相同的区间，可以对其进行lazy操作。 lazy维护一个颜色，和一个加的值。 这样的话，有些中间的变化量就可以不用去考虑了。
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
int col[maxn]; ll add[maxn],sum[maxn];
void build(int Now,int L,int R)
{
if(L==R){ col[Now]=L;return;}
int Mid=(L+R)>>;
build(Now<<,L,Mid);
build(Now<<|,Mid+,R);
}
void pushdown(int Now,int L,int R)
{
if(col[Now]){
col[Now<<]=col[Now<<|]=col[Now];
}
if(add[Now]) {
int Mid=(L+R)>>;
sum[Now<<]+=1LL*(Mid-L+)*add[Now];
sum[Now<<|]+=1LL*(R-Mid)*add[Now];
add[Now<<]+=add[Now]; add[Now<<|]+=add[Now];
add[Now]=;
}
}
void pushup(int Now)
{
sum[Now]=sum[Now<<]+sum[Now<<|];
if(col[Now<<]==col[Now<<|]) col[Now]=col[Now<<];
else col[Now]=;
}
void update(int Now,int L,int R,int l,int r,int x)
{
if(l<=L&&r>=R&&col[Now]){
add[Now]+=abs(x-col[Now]);
sum[Now]+=1LL*abs(x-col[Now])*(R-L+);
col[Now]=x; return ;
}
pushdown(Now,L,R); int Mid=(L+R)>>;
if(l<=Mid) update(Now<<,L,Mid,l,r,x);
if(r>Mid) update(Now<<|,Mid+,R,l,r,x);
pushup(Now);
}
ll query(int Now,int L,int R,int l,int r)
{
if(l<=L&&r>=R) return sum[Now];
pushdown(Now,L,R); int Mid=(L+R)>>; ll res=;
if(l<=Mid) res+=query(Now<<,L,Mid,l,r);
if(r>Mid) res+=query(Now<<|,Mid+,R,l,r);
pushup(Now); return res;
}
int main()
{
int N,M,opt,L,R,x;
scanf("%d%d",&N,&M);
build(,,N);
rep(i,,M){
scanf("%d%d%d",&opt,&L,&R);
if(opt==){
scanf("%d",&x);
update(,,N,L,R,x);
}
else printf("%lld\n",query(,,N,L,R));
}
return ;
}
D .DZY Loves Strings
题意：给定一个字符串S，然后Q次询问，每次询问给出s和t，|s|,|t|<=4；问包含s和t的最短区间是多长。 |S|<5e4。
思路：我们可以把S的所有长度为1到4的子串都提出来，（由于不长感觉不会出现碰撞，单hash就够了）。
然后对于每次询问，我们可以对含s的部分，和含t的部分找最近的地方。即两个集合，在属于不同集合的最近的点对，这里可以用双指针做到线性，单次的复杂度和较小的集合大小有关。 同时，用map记录一下，避免多次出现极端数据。
#include<bits/stdc++.h>
#define pii pair<int,int>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
map<pii,int>mp;
vector<int>G[maxn];
char c[maxn],a[maxn],b[maxn];
int main()
{
int N,Q;
scanf("%s",c+);
N=strlen(c+);
rep(i,,)
rep(j,,N-i+){
int t=;
rep(k,j,j+i-) t=t*+c[k]-'';
G[t].push_back(j);
}
scanf("%d",&Q);
while(Q--){
scanf("%s%s",a+,b+);
int ta=,tb=,L1,L2,ans=maxn;
L1=strlen(a+); rep(i,,L1) ta=ta*+a[i]-'';
L2=strlen(b+); rep(i,,L2) tb=tb*+b[i]-'';
if(mp.find(pii(ta,tb))!=mp.end()){
printf("%d\n",mp[pii(ta,tb)]);
continue;
}
int sz1=G[ta].size(),sz2=G[tb].size();
int p1=,p2=;
while(p1<sz1&&p2<sz2){
while(G[tb][p2]<G[ta][p1]){
p2++; if(p2>=sz2) break;
}
if(p2<sz2)ans=min(ans,max(G[tb][p2]+L2,G[ta][p1]+L1)-G[ta][p1]);
p1++;
}
p1=p2=;
while(p1<sz1&&p2<sz2){
while(G[ta][p1]<G[tb][p2]){
p1++; if(p1>=sz1) break;
}
if(p1<sz1)ans=min(ans,max(G[ta][p1]+L1,G[tb][p2]+L2)-G[tb][p2]);
p2++;
}
if(ans==maxn) ans=-;
mp[pii(ta,tb)]=ans;
printf("%d\n",ans);
}
return ;
}