1.random
Description
　　給定4個參數A0,N,c,p,你需要按下式構造A1~AN：
　　　　A[i]=(A[i-1]2+c)mod p
　　之后，你需要求出A1~AN中，第K大的數值。
Input
　　一行五個正整數A0,N,c,p,K。
Output
　　一行一個整數,描述答案。
Sample Input
　　123 10 435 3451 5
Sample Output
　　2936
Range
測試點 ? ? ? 范圍
1~3 ? ? ? ? ?K<=N<=105
4~10 ? ? ? ? K<=N<=5*106

直接stl

1 #include<algorithm> 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 9 typedef long long LL; 10 11 #define N 5000010 12 13 LL n,c,p,k; 14 15 LL a[N]; 16 17 bool cmp(const int & a,const int & b) 18 { 19 　　return a>b; 20 } 21 22 int main() 23 { 24 　　freopen("random.in","r",stdin);freopen("random.out","w",stdout); 25 　　scanf("%lld%lld%lld%lld%lld",&a[0],&n,&c,&p,&k); 26 　　for (LL i=1;i<=n;i++) 27 　　　　a[i]=((a[i-1]*a[i-1])%p+c%p)%p; 28 　　nth_element(a+1,a+k,a+n+1,cmp); 29 　　printf("%I64d",a[k]); 30 　　return 0; 31 }

?

?

?

2.sequence

Description

　　給一個長度為n的序列a，以及q個詢問。每次詢問給出兩個參數l,r,你需要輸出子 序列al~ar的最大連續字段和。

Input?

　　第一行兩個正整數n,q。

`　?接下來一行n個整數，描述序列a。

　　接下來q行，每行兩個參數l,r，描述一個詢問。

Output

? ??對于每個詢問，輸出一行一個整數,描述答案。

Sample Input

　　4 3

　　1 -2 3 2

?　?1 4

　　1 2

　　2 2

Sample Output

　　5

　　1

　　0

Range

　　測試點 ? ? ?范圍

　　1~3 　　　　N,Q<=1000

　　4~7 　　　　N,Q<=10⁵

　　8~10 　　　?N<=10⁵,Q<=10⁶

?

線段樹維護。

1 #include<algorithm> 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 9 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout); 10 #define maxn 100010 11 #define IN inline 12 #define RE register 13 14 typedef long long llg; 15 16 int n,m,zhi[maxn*3],now=maxn*3-2,ll,rr,D; 17 int sumv[maxn*3],le[maxn*3],ri[maxn*3]; 18 19 20 IN int getint() 21 { 22 int w=0,q=0; 23 char c=getchar(); 24 while((c<'0'||c>'9')&&c!='-') c=getchar(); 25 if(c=='-') q=1,c=getchar(); 26 while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); 27 return q?-w:w; 28 } 29 30 IN void update(int u,int lc,int lv) 31 { 32 sumv[u]=sumv[lc]+sumv[lv]; 33 le[u]=max(le[lc],sumv[lc]+le[lv]); 34 ri[u]=max(ri[lv],sumv[lv]+ri[lc]); 35 zhi[u]=max(zhi[lc],zhi[lv]); 36 zhi[u]=max(zhi[u],ri[lc]+le[lv]); 37 } 38 39 IN void build(int u,int l,int r) 40 { 41 int lc=u<<1,lv=u<<1|1,mid=l+r>>1; 42 if (l==r) 43 { 44 sumv[u]=getint(); 45 if (sumv[u]>0) 46 zhi[u]=le[u]=ri[u]=sumv[u]; 47 return; 48 } 49 build(lc,l,mid); 50 build(lv,mid+1,r); 51 update(u,lc,lv); 52 } 53 54 IN void query(int u,int l,int r) 55 { 56 int lc=u<<1,lv=u<<1|1,mid=l+r>>1; 57 if (l>=ll && r<=rr) 58 { 59 if (!D) 60 { 61 zhi[now]=zhi[u];sumv[now]=sumv[u]; 62 le[now]=le[u];ri[now]=ri[u];D++; 63 } 64 else 65 { 66 now^=1; 67 update(now,now^1,u); 68 } 69 return; 70 } 71 if (ll<=mid) 72 query(lc,l,mid); 73 if (rr>mid) 74 query(lv,mid+1,r); 75 } 76 77 78 79 int main(){ 80 File("sequence"); 81 n=getint();m=getint(); 82 build(1,1,n); 83 while(m--) 84 { 85 ll=getint();rr=getint(); 86 D=0;query(1,1,n); 87 printf("%d\n",zhi[now]); 88 } 89 }

?

3.tree

Description

　　給一棵n個節點的無根樹，求路徑長度=K的簡單路徑數。

Input

　　第一行兩個正整數n,K。

　　接下來n-1行，每行兩個正整數x,y，描述一條邊(x,y)。

Output

　　一行一個整數,描述答案。

Sample Input

　　4 2

　　1 2

　　2 3

　　2 4

Sample Output

　　3

Range

　　測試點 ? ? ? ?范圍

　　1~3 ? ? ? ? ? 2<=K<=N<=1000

　　4~10 　　　　?2<=K<=N<=10⁵

?

1 #include<algorithm> 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 9 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout); 10 #define maxn 100010 11 12 typedef long long llg; 13 14 int head[maxn],next[maxn<<1],to[maxn<<1],tt,n,ans,D; 15 int a[maxn],c1[maxn],c2[maxn],siz[maxn],val[maxn]; 16 bool w[maxn]; 17 18 void link() 19 { 20 int x,y; 21 scanf("%d%d",&x,&y); 22 to[++tt]=y;next[tt]=head[x];head[x]=tt; 23 to[++tt]=x;next[tt]=head[y];head[y]=tt; 24 } 25 26 void dfs1(int u,int fa) 27 { 28 siz[u]=1;a[++tt]=u;val[u]=0; 29 for (int i=head[u],v;v=to[i],i;i=next[i]) 30 if (v!=fa && !w[v]) 31 { 32 dfs1(v,u);siz[u]+=siz[v]; 33 val[u]=max(val[u],siz[v]); 34 } 35 } 36 37 void dfs2(int u,int fa,int now){ 38 c1[now]++; 39 if (now>=D) 40 return; 41 for (int i=head[u],v;v=to[i],i;i=next[i]) 42 if (v!=fa && !w[v]) 43 dfs2(v,u,now+1); 44 } 45 46 void solve(int u) 47 { 48 int x=u;tt=0; 49 dfs1(u,0); 50 for (int i=2;i<=tt;i++) 51 { 52 val[a[i]]=max(val[a[i]],siz[u]-siz[a[i]]); 53 if (val[a[i]]<val[x]) 54 x=a[i]; 55 } 56 w[x]=1; 57 for (int i=head[x],v;v=to[i],i;i=next[i]) 58 if (!w[v]) 59 { 60 dfs2(v,0,1); 61 ans+=c1[D]; 62 for (int j=1;c1[j];j++) 63 ans+=c2[D-j]*c1[j]; 64 for (int j=1;c1[j];j++) 65 c2[j]+=c1[j],c1[j]=0; 66 } 67 for (int i=1;c2[i];i++) 68 c2[i]=0; 69 for (int i=head[x],v;v=to[i],i;i=next[i]) 70 if (!w[v]) 71 solve(v); 72 } 73 74 int main() 75 { 76 File("tree"); 77 scanf("%d%d",&n,&D); 78 for(int i=1;i<n;i++) 79 link(); 80 solve(1); 81 printf("%d",ans); 82 }

?

轉載于:https://www.cnblogs.com/yangjiyuan/p/5361462.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的【Noip模拟By yxj】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。