JZOJ

admin 管理员组

文章数量: 1086019

JZOJ

T1

题面

“封印大典启动，请出Nescafe魂珠！”随着圣主applepi一声令下，圣剑护法rainbow和魔杖护法freda将Nescafe魂珠放置于封印台上。封印台是一个树形的结构，魂珠放置的位置就是根节点(编号为0)。还有n个其他节点(编号1-n)上放置着封印石，编号为i的封印石需要从魂珠上获取Ei的能量。能量只能沿着树边从魂珠传向封印石，每条边有一个能够传递的能量上限Wi，魂珠的能量是无穷大的。作为封印开始前的准备工作，请你求出最多能满足多少颗封印台的能量需求？

注意：能量可以经过一个节点，不满足它的需求而传向下一个节点。每条边仅能传递一次能量。

解法

考虑直接贪心的选点，每次选取权值最小的点，如果他可以被选，将他到根经过的所有边减去其权值

正确性

考虑若最小点P没有被选，设当前选取的权值最大的点为M，若P,M不在同一条链上，则P也会被扫描，所以只需考虑P,M在同一条链上的情况

那么若M在P下方，则不选M更佳，若M在P上方，只需考虑在M下方P上方的点，由P的最小性可得若选M可选这些点，选P也可以选

证毕！

；贪心方法不能直接对整条链贪心

代码

#pragma optimize("-O2")#include<algorithm> 
#include<iostream> 
#include<cstring>
#include<cstdio> 
using namespace std; 
#define _ 1005 
pair<int, int> nodeval[_], fa[_], dvt[_]; 
int tot, n, awsl=0; 
int vis[_], dep[_];
int cmp(pair<int, int> a, pair<int,int> b){if(a.first!=b.first) return a.first<b.first; else return a.second>b.second ;
}void dfs(int i){ while(i!=0){ vis[i]=1 ;dvt[++tot]=make_pair(nodeval[i].first, i); i=fa[i].first ;vis[i]=1 ;} 
}
int check(int node, int iv){while(node){if(fa[node].second < iv) return false ;node = fa[node].first ;}return true ;
}
void minu(int node, int iv){while(node){fa[node].second-=iv ;node = fa[node].first; }
}
int main(){ scanf("%d", &n); for(int i=1;i<=n;++i){ int x,y,z; scanf("%d%d%d", &x, &y, &z); nodeval[i]=make_pair(y, i); fa[i]=make_pair(x, z);}sort(nodeval+1, nodeval+n+1, cmp);//puts(":Start") ;for(int i=1;i<=n;++i){if(check(nodeval[i].second, nodeval[i].first)) minu(nodeval[i].second, nodeval[i].first), ++awsl;}//puts(":end") ;cout<<awsl<<endl ;
}

知识点小结

贪心

T2

题面

“圣主applepi于公元2011年9月创造了Nescafe，它在散发了16吃光辉之后与公元2011年11月12日被封印为一颗魂珠，贮藏于Nescafe神塔之中。公元2012年9月，圣主带领四大护法重启了Nescafe，如今已经是Nescafe之魂的第30吃传播了。不久，它就要被第二次封印，而变成一座神杯。。。”applepi思索着Nescafe的历史，准备着第二次封印。

Nescafe由n种元素组成(编号为1~n)，第i种元素有一个封印区[ai,bi]。当封印力度E小于ai时，该元素获得ai的封印能量；当封印力度E在ai到bi之间时，该元素将获得E的封印能量；而当封印力度E大于bi时，该元素将被破坏从而不能获得任何封印能量。现在圣主applepi想选择恰当的E，使得封印获得的总能量尽可能高。为了封印的最后一击尽量完美，就请你写个程序帮他计算一下吧！

解法

发现答案只有可能是左端点或右端点，暴力即可

正确性

若不在端点上，提到最近的端点不会更差；没有考虑左端点，代码、方法不熟练

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std ;
#define int long long
#define _ 300005
int ans=0, n, p, sa, sp ;
int a[_], b[_];
struct rec{int x,y;}c[_];
bool operator <(rec a,rec b){ return a.x<b.x||a.x==b.x&&a.y>b.y; }
signed main(){scanf("%d", &n) ;for(int i=1;i<=n;i++){scanf("%d%d",&a[i],&b[i]);sa+=a[i];c[i].x=a[i],c[i].y=1;c[n+i].x=b[i],c[n+i].y=-1; }sort(c+1,c+2*n+1);for(int i=1;i<=2*n;i++)if(c[i].y==1) {sp++,sa-=c[i].x;if(ans<sa+sp*c[i].x) ans=sa+sp*c[i].x,p=c[i].x;}else{if(ans<sa+sp*c[i].x) ans=sa+sp*c[i].x,p=c[i].x;sp--;}cout<<p<<" "<<ans<<endl;
}

知识点小结

思维

T3

题面

解法

看见循环同构串就先复制一下接在末尾

扫描每一个以i开头串，动态维护其中可匹配串的开头位置，然后每次二分一遍即可，比标算简单

正确性

显然；vector二分没有值会RE，字符串匹配要看清能否重用一个字符，注意调试

代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std ;char str1[105], str2[300005] ;
int len1, len2;
int tot, lst, qwq, ans=0; 
char strs[105][105] ;
int leng[105] ;
unsigned long long hsv[105] ;
vector<int> rgh[51] ;
vector<int> H[100], E[100];
unsigned long long hsh[200005] ;
#define put(X) for(int awsl=0;awsl<X.size();++awsl) cout<<#X<<"["<<awsl<<"]="<<X[awsl]-minusvalnow<<endl ;
unsigned long long power(int a, int b){unsigned long long res=1, car=a;while(b){if(b&1) res*=car ;car*=car ;b>>=1 ;}return res ;
}
int minusvalnow = 0 ;
void minu() {++minusvalnow ;
}
void add(int i, int k){rgh[i].push_back(minusvalnow+k) ;
}
int get(int arrn, int pos){return rgh[arrn][pos]-minusvalnow ;
}
// qwq: 结束位置 
void Judge(int qwq){// Judge the positions// the start position is qwq-len2/2+1 int nowpos = qwq-len2/2+1, f=1;//cout<<"St: "<<nowpos<<endl ;//for(int i=1;i<=tot;++i) { put(rgh[i]); }for(int i=1;i<=tot;++i){// find the first val that bigger than nowval ;int r = -0x3f3f3f3f, wtrl ; if(lower_bound(rgh[i].begin(), rgh[i].end(), nowpos)!=rgh[i].end())r = *lower_bound(rgh[i].begin(), rgh[i].end(), nowpos) ;if(i == 1){//cout<<"spFir: "<<minusvalnow+qwq-len2/2<<endl; wtrl = binary_search(rgh[i].begin(), rgh[i].end(),qwq-len2/2+1) ;}if(i == 1 && str1[0]!='*' && !wtrl){f=0; break ;}if(i == tot){//cout<<"Go: "<<leng[i]<<endl ;//cout<<"Req: "<<qwq-leng[i]+1<<endl ;wtrl = binary_search(rgh[i].begin(), rgh[i].end(),qwq-leng[i]+1) ;}if(i == tot && str1[len1-1]!='*' && !wtrl){//cout<<"Err! Not same!"<<endl;f=0; break ;}//cout<<"R="<<r<<endl ;//cout<<"R is "<<r<<", Leng[i] is "<<leng[i]<<endl ;if(r >= nowpos) nowpos = r+leng[i] ;else { /*cout<<"Break at "<<i<<", and the pos is "<<nowpos<<endl ;*/f=0 ; break; }//cout<<"Nowpos: "<<nowpos<<endl ;}ans+=f ;//puts(f?"Added":"Unadded.qwq") ;
}
unsigned long long gt(int l, int r){if(l == 0) return hsh[r];//if(l == r) return str1[l]-'a'+1 ;return hsh[r]-hsh[l-1]*power(131, r-l+1) ;
}
int main(){scanf("%s\n%s",str1,str2) ;len1=strlen(str1); len2=strlen(str2);for(int i=len2; i<len2*2; ++i) str2[i]=str2[i%len2];for(int i=0;i<len2*2;++i) {if(i!=0) hsh[i] = hsh[i-1]*131+str2[i]-'a'+1 ;else hsh[i] = str2[i]-'a'+1;} len2*=2 ;for(tot=1;;++tot){for(qwq=lst;qwq<len1;++qwq){if(str1[qwq]!='*') strs[tot][leng[tot]]=str1[qwq], ++lst, ++leng[tot];else{while(str1[qwq] == '*')++qwq; lst=qwq; if(leng[tot]==0) --tot;break ;}}if(qwq == len1) break ;}while(leng[tot]==0) --tot ;//cout<<"Tot= "<<tot<<endl ;//for(int i=1;i<=tot;++i){//  cout<<"No."<<i<<" :"<<strs[i]<<endl ;//}char qwq[1]; gets(qwq);// 先断成节// 再找匹配for(int num=1;num<=tot;++num){unsigned long long hshval = 0 ;leng[num]=strlen(strs[num]);//puts("Hashing:") ;rgh[num].push_back(-0x3f3f3f3f) ;for(int i=0;i<leng[num];++i) hshval = hshval*131+strs[num][i]-'a'+1 ;hsv[num] = hshval ; for(int i=0;i<len2/2;++i){//cout<<gt(i, i+leng[num]-1)<<" "<<hshval<<endl ;if((gt(i, i+leng[num]-1) == hshval)) rgh[num].push_back(i) ;}//put(rgh[num]);//char awsl[1] ;//gets(awsl); }Judge(len2/2-1) ;// 然后跑二分for(int i=0;i<len2/2-1;++i){//cout<<"Start pos:"<<i+1<<endl ; // while working the string str2[i~i+len2]// Firstly change the right places//cout<<i<<"\nAt "<<minusvalnow<<endl ;//cout<<"At "<<i+len2/2<<endl ;for(int j=1;j<=tot;++j){//cout<<"Go: ("<<i+len2/2-leng[j]+1<<", "<<i+len2/2<<")"<<endl ;//cout<<gt(i+len2/2-leng[j]+1, i+len2/2)<<endl<<hsv[j]<<endl ;if(gt(i+len2/2-leng[j]+1, i+len2/2) == hsv[j]) add(j, i+len2/2-leng[j]+1) ;}//minu();int pans = ans ;Judge(i+len2/2) ; //if(pans != ans) cout<<"Get ans at "<<i+1<<endl; //char awsl[1] ;//gets(awsl); } cout<<ans<<endl ;
}

知识点小结

Hash

转载于:.html

本文标签： JZOJ