@01010101
2018-11-05T21:37:12.000000Z
字数 4318
阅读 977
noip
DAY1T1Vigenère 密码
一个简单模拟
DAY1T2国王游戏
贪心,不太好想。关键是涉及高精度的除法
DAY1T3开车旅行
好题。考虑在暴力往前走的基础上如何优化,由于走的是一条链:倍增 把a走一次,b走一次看成一个整体进行倍增。
如何找最大次大也值得思考:双向链表(我不熟),set(不怎么会用迭代器)。。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>
#define ll long long
using namespace std;
const int N=100005;
const int D=20;
int n,x0,m,k,x1,na[N],nb[N],ans;
ll ansa=1e5,ansb=0LL,fa[N][D+2],fb[N][D+2],f[N][D+2];
struct city{
int id,h;
bool operator < (const city &b) const{
return h<b.h;
}
}c[N];
struct node{
int id,delta;
bool operator < (const node &b) const{
if(delta!=b.delta) return delta<b.delta;
return c[id].h<c[b.id].h;
}
}tmp[5];
set <city> s;
void init(int i){
set<city>::iterator it=s.find(c[i]);
int j=0;
if(it!=s.begin()){
--it;
tmp[++j]=(node){it->id,abs(it->h-c[i].h)};
if(it!=s.begin()){
--it;
tmp[++j]=(node){it->id,abs(it->h-c[i].h)};
++it;
}
++it;
}
if((++it)!=s.end()){
tmp[++j]=(node){it->id,abs(it->h-c[i].h)};
if((++it)!=s.end())
tmp[++j]=(node){it->id,abs(it->h-c[i].h)};
}
sort(tmp+1,tmp+j+1);
nb[i]=tmp[1].id;
if(j==1) return;
na[i]=tmp[2].id;
}
void query(int st,int x,ll &ta,ll &tb){
for(int i=D;i>=0;--i)
if(f[st][i]&&fa[st][i]+fb[st][i]<=x){
ta+=fa[st][i];
tb+=fb[st][i];
x-=fa[st][i]+fb[st][i];
st=f[st][i];
}
if(!na[st]) return;
int tmpans=abs(c[na[st]].h-c[st].h);
if(tmpans<=x) ta+=tmpans;
}
int main(){
// freopen("a.txt","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&c[i].h);
c[i].id=i;
}
for(int i=n;i>=1;--i){
s.insert(c[i]);
if(i!=n)
init(i);
}
for(int i=1;i<=n;++i){//把a和b合在一起走2^j步。
int p1=na[i],p2=nb[na[i]];
fa[i][0]=p1?abs(c[p1].h-c[i].h):0;
fb[i][0]=p2?abs(c[p2].h-c[p1].h):0;
f[i][0]=p2;
}
for(int j=1;j<=D;++j){
for(int i=1;i<=n;++i){
f[i][j]=f[f[i][j-1]][j-1];
fa[i][j]=fa[i][j-1]+fa[f[i][j-1]][j-1];
fb[i][j]=fb[i][j-1]+fb[f[i][j-1]][j-1];
}
}
scanf("%d",&x0);
ans=0;
for(int i=1;i<=n;++i){
ll ta=0LL,tb=0LL;
query(i,x0,ta,tb);
if(tb&&(!ans||ansa*tb>ansb*ta)){
ansa=ta;
ansb=tb;
ans=i;
}
}
printf("%d\n",ans);
scanf("%d",&m);
while(m--){
scanf("%d%d",&k,&x1);
ll ta=0LL,tb=0LL;
query(k,x1,ta,tb);
printf("%lld %lld\n",ta,tb);
}
return 0;
}
DAY2T1同余方程
数论模板题
DAY2T2借教室
第一想法线段树,第二想法区间修改+区间查询(最值)线段树,最后发现题解是二分+差分。
DAY2T3疫情控制
好题,从某节点往上走用倍增!!贪心+二分倍增实现。漏了一个情况。
一个节点不是先守好自己。而是在能守别人的时候尽可能守住别人。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
int read(){
char ch;int op=1;
while((ch=getchar())<'0'||ch>'9') if(ch=='-') op=-1;
int ret=ch-'0';
while((ch=getchar())>='0'&&ch<='9') ret=ret*10+ch-'0';
return ret*op;
}
const int D=18;
const int N=50000+10;
const int inf=0x3f3f3f3f;
int n,m,kk,cnt;
int head[N],f[N][D+2],vis[N],ar[N],leaf[N];
ll l,r,mid,ans;
ll g[N][D+2];
struct edge{
int v,w,nxt;
}e[N<<1];
void adde(int u,int v,int w){
e[kk].v=v;
e[kk].w=w;
e[kk].nxt=head[u];
head[u]=kk++;
}
void dfs(int u,int fa,int w){
f[u][0]=fa;g[u][0]=w;
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].v;
if(v!=fa){
dfs(v,u,e[i].w);
}
}
}
struct army{int ct;ll t;}rst[N];
struct pat{int ct;ll nd;}p[N];
bool cmp1(army a,army b){
if(a.ct!=b.ct) return a.ct<b.ct;
return a.t<b.t;
}
bool cmp3(army a,army b){return a.t>b.t;}
bool cmp2(pat a,pat b){ return a.ct<b.ct;}
bool cmp4(pat a,pat b){ return a.nd>b.nd;}
void dfs2(int u,int fa){
if(vis[u]) return;
int flg=-1;
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].v;
if(v!=fa){
if(flg==-1) flg=0;
dfs2(v,u);
leaf[u]+=leaf[v];
}
}
if(flg==-1) leaf[u]=1;
}
bool Check(ll X){
for(int i=1;i<=n;++i) {
vis[i]=0;
p[i].nd=0;
p[i].ct=0;
rst[i].t=0;
rst[i].ct=0;
leaf[i]=0;
}
cnt=0;
for(int i=1;i<=m;++i){
int pos=ar[i];ll R=X;
for(int j=D;j>=0;--j)
if(g[pos][j]<=R&&f[pos][j]!=1) {
R-=g[pos][j];//!!
pos=f[pos][j];
}
if(f[pos][0]==1&&g[pos][0]<=R){
rst[i].t=R-g[pos][0];
rst[i].ct=pos;
}
else vis[pos]=1;
}
dfs2(1,1);
for(int i=head[1];i!=-1;i=e[i].nxt){
int v=e[i].v;
if(leaf[v]){
p[++cnt].nd=e[i].w;
p[cnt].ct=v;
}
}
sort(rst+1,rst+m+1,cmp1);
sort(p+1,p+cnt+1,cmp2);
int tmp=1;
for(int i=1;i<=cnt;++i){
while(rst[tmp].ct<p[i].ct&&tmp<=m) tmp++;
if(rst[tmp].ct==p[i].ct&&rst[tmp].t<p[i].nd) {
p[i].nd=0;
rst[tmp++].t=0;
}
}
sort(rst+1,rst+m+1,cmp3);
sort(p+1,p+cnt+1,cmp4);
for(int i=1;i<=cnt;++i)
if(rst[i].t<p[i].nd) return false;
return true;
}
int main(){
int a,b,c;
// freopen("a.txt","r",stdin);
// freopen("a.out","w",stdout);
memset(head,-1,sizeof(head));
n=read();
for(int i=1;i<n;++i){
a=read();b=read();c=read();
adde(a,b,c);adde(b,a,c);
r+=c;
}
dfs(1,1,0);
for(int i=1;i<=D;++i)
for(int j=1;j<=n;++j){
f[j][i]=f[f[j][i-1]][i-1];
g[j][i]=g[f[j][i-1]][i-1]+g[j][i-1];
}
m=read();
for(int i=1;i<=m;++i) {
ar[i]=read();
}
while(l<=r){
mid=(l+r)>>1;
if(Check(mid)) {ans=mid;r=mid-1;}
else l=mid+1;
}
printf("%lld\n",ans);
return 0;
}
模拟
贪心+高精度除法
倍增
数论同余方程
二分+差分
二分+倍增