鉛導(dǎo)體
問(wèn)題描述 何老板要求第三題要很簡(jiǎn)單，最好是鉛導(dǎo)體的難度。 于是，nodgd把N個(gè)鉛塊用N?1根導(dǎo)線相連，就形成了一個(gè)鉛導(dǎo)體。只要是在這個(gè)基礎(chǔ)上出題，就符合何老板的要求。nodgd為了方便，就把其中的一個(gè)鉛塊固定在了墻上，其他鉛塊在導(dǎo)線的作用下自然下垂。每個(gè)鉛塊有個(gè)固定的純度，若干個(gè)相同純度的鉛塊可以聚變發(fā)電，發(fā)電的電壓與鉛塊的數(shù)量成正比。每當(dāng)nodgd需要電療的時(shí)候，就在鉛導(dǎo)體上選一個(gè)鉛塊，把它和掛在它下面的所有鉛塊都取下來(lái)，在這當(dāng)中選一些純度相同的鉛塊發(fā)電，發(fā)電之后將這些鉛塊掛回原來(lái)的位置。nodgd希望電療的電壓越高越好，在電壓相同的情況下，nodgd又希望使用純度更低的鉛塊。 但是ciocio經(jīng)常來(lái)?yè)v亂，他時(shí)不時(shí)的把整個(gè)鉛導(dǎo)體取下來(lái)，重新選一個(gè)鉛塊固定到墻上，其他的鉛塊繼續(xù)自然下垂。那么問(wèn)題來(lái)了，nodgd每次都想享受最高電壓的電療，需要你大聲喊出應(yīng)該使用多少個(gè)純度是多 少的鉛塊。
輸入格式 輸入文件C.in。 第一行四個(gè)整數(shù)N, A, Q, I，表示鉛塊的數(shù)量、鉛塊純度的范圍、操作的總次數(shù)、測(cè)試點(diǎn)編號(hào)。 鉛塊按1 ～ N編號(hào)，一開(kāi)始nodgd把編號(hào)為1的鉛塊固定在墻上。鉛塊的純度是1 ～ A之間的一個(gè)整 數(shù)。 接下來(lái)N ? 1行，每行兩個(gè)整數(shù)u, v，表示有一條導(dǎo)線連接。 接下來(lái)一行，N個(gè)整數(shù)，表示每個(gè)鉛塊的純度。 接下來(lái)Q行，每行輸入兩個(gè)整數(shù)op, u。 若op = 1，表示ciocio把整個(gè)鉛導(dǎo)體取下來(lái)，再把編號(hào)為u的鉛塊重新固定在墻上。 若op = 2，表示nodgd把編號(hào)為u的鉛塊以及掛在他下面的所有鉛塊暫時(shí)取下來(lái)，選出其中一些鉛塊進(jìn)行聚變發(fā)電。如果要求該組測(cè)試點(diǎn)要求強(qiáng)制在線，設(shè)上一次輸出的答案兩個(gè)數(shù)分別為lasta和lastb，則u′ = (u+lasta×23 + lastb×233)%N + 1才是真正的節(jié)點(diǎn)編號(hào)。
輸出格式 輸出文件C.out。 每次op = 2的時(shí)候輸出一行，兩個(gè)整數(shù)，分別是使用鉛塊的純度和數(shù)量。
樣例輸入 5 3 8 0 1 2 1 3 3 4 3 5 1 1 2 2 3 2 3 2 1 2 5 1 3 2 4 2 2 2 1 2 3
樣例輸出 2 2 1 2 3 1 2 1 1 1 1 2 1 2
數(shù)據(jù)范圍 
dfs序+分塊求眾數(shù)，很機(jī)智的一個(gè)做法將新編號(hào)對(duì)應(yīng)的純度數(shù)組復(fù)制一遍，處理根在子樹(shù)內(nèi)就會(huì)方便很多。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstdlib>#include<cstring>#include<cmath>#define ll long longusing namespace std;const int base=500;template <typename T>inline void _read(T& x){ char t=getchar();bool sign=true; while(t<'0'||t>'9'){if(t=='-')sign=false;t=getchar();} for(x=0;t>='0'&&t<='9';t=getchar())x=x*10+t-'0'; if(!sign)x=-x;}int n,m,q,I,N,S;int tot,e,root;int lasta,lastb;int vistime;struct line{ int from,to; line(){} line(int x,int y){from=x;to=y;}};line edge[200005];int last[100005],_next[200005];void add_edge(int x,int y){ edge[++e]=line(x,y); _next[e]=last[x]; last[x]=e;}int father[100005],dep[100005],p[100005][35],id[100005],R[100005],purity[100005],a[100005];void dfs(int x,int fa){ int i,j,k,v; id[x]=++vistime; dep[x]=dep[fa]+1; father[x]=fa; k=ceil(log(dep[x])/log(2)); p[x][0]=fa; for(i=1;i<=k;i++)p[x][i]=p[p[x][i-1]][i-1]; for(i=last[x];i;i=_next[i]){ v=edge[i].to; if(v==fa)continue; dfs(v,x); } R[x]=vistime;}struct node{ int Purity,sum; node(){} node(int x,int y){Purity=x;sum=y;}};node block[605][1005];int cnt[100005];int all[605][100005];void divide(){ int i,j,k,t1,t2; N=(n<<1); tot=(N-1)/base+1; for(i=1;i<=tot;i++){ int pure=0,sum=0; for(j=i;j<=tot;j++){ int lim=j*base; lim=min(lim,N); for(k=(j-1)*base+1;k<=lim;k++){ t1=a[k]; t2=++cnt[a[k]]; if(t2>sum||(t2==sum&&a[k]<pure)){ sum=cnt[a[k]]; pure=a[k]; } } block[i][j]=node(pure,sum); if(i==1){ for(k=1;k<=m;k++){ all[j][k]=cnt[k]; } } } for(j=1;j<=m;j++)cnt[j]=0; }}int go_up(int x,int step){ int i; for(i=S;i>=0;i--){ if(step&(1<<i))x=p[x][i]; } return x;}void solve(int x){ //cout<<"solve:"<<x<<endl; int l,r,i,j,k; if(x==root){ l=1; r=n; } else if(id[x]<=id[root]&&id[root]<=R[x]){ //cout<<"case1"<<endl; int temp=go_up(root,dep[root]-dep[x]-1); l=R[temp]+1; r=id[temp]-1+n; } else { //cout<<"case2"<<endl; l=id[x];r=R[x]; } int bl,br,tl,tr; bl=(l-2+base)/base+1; br=r/base; tl=(bl-1)*base+1; tr=br*base; //cout<<"l:"<<l<<" r:"<<r<<endl; //cout<<"block("<<bl<<","<<br<<")"<<endl; //cout<<"work["<<l<<","<<r<<"]"<<endl; int pure,sum,t1,t2; if(bl>br){ //cout<<"fuck"<<endl; pure=0;sum=0; for(i=l;i<=r;i++){ t1=++cnt[a[i]]; t2=a[i]; if(t1>sum||(t1==sum&&t2<pure)){ sum=t1;pure=t2; } } //cout<<"cnt[105]:"<<cnt[105]<<endl; for(i=l;i<=r;i++)cnt[a[i]]=0; } else { pure=block[bl][br].Purity; sum=block[bl][br].sum; for(i=l;i<tl;i++){ t1=++cnt[a[i]]+all[br][a[i]]-all[bl-1][a[i]]; t2=a[i]; if(t1>sum||(t1==sum&&t2<pure)){ sum=t1;pure=t2; } } for(i=tr+1;i<=r;i++){ t1=++cnt[a[i]]+all[br][a[i]]-all[bl-1][a[i]]; t2=a[i]; if(t1>sum||(t1==sum&&t2<pure)){ sum=t1;pure=t2; } } for(i=l;i<tl;i++)cnt[a[i]]=0; for(i=tr+1;i<=r;i++)cnt[a[i]]=0; }新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
