2016 CCPC Changchun Onsite
hdu5912.Fraction
计算连分数的答案，直接模拟即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; typedef long long LL; int T,n; LL a[10],b[10],u,d; LL gcd(LL a,LL b) { if(b==0) return a; return gcd(b,a%b); } int main() { cin>>T; for(int cas=1;cas<=T;cas++) { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) cin>>b[i]; u=b[n],d=a[n]; for(int i=n-1;i>=1;i--) { u+=a[i]*d; swap(d,u); u*=b[i]; } LL g=gcd(u,d); u/=g,d/=g; cout<<"Case #"<<cas<<": "<<u<<" "<<d<<endl; } return 0; } |
hdu5914.Triangle
问长度1到n的线段，至少要去掉多少，使得剩下的线段无法构成三角形
\(1\leq n\leq 20\)
斐波那契数列，手算完打表
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int T,n; int ans[21]={0,0,0,0,1,1,2,3,3,4,5,6,7,7,8,9,10,11,12,13,14}; int main() { scanf("%d",&T); for(int cas=1;cas<=T;cas++) { scanf("%d",&n); cout<<"Case #"<<cas<<": "<<ans[n]<<endl; } return 0; } |
hdu5916.Harmonic Value Description
定义全排列的权值为相邻两个数的gcd，求1到n的所有全排列中第K小的排列
\(1\leq 2k \leq n\leq 10000\)
容易发现，第k大的全排列的权值为n-2+k
构造方式是将偶数从小到大的k个偶数依次放在数列最前面
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int T,n,k,a[10010],tot; int main() { scanf("%d",&T); for(int cas=1;cas<=T;cas++) { tot=0; scanf("%d%d",&n,&k); for(int i=1;i<=k;i++) a[++tot]=2*i; for(int i=1;i<=n;i++) if(i%2!=0||i/2>k) a[++tot]=i; printf("Case #%d: ",cas); for(int i=1;i<n;i++) printf("%d ",a[i]); printf("%d\n",a[n]); } return 0; } |
hdu5917.Instability
给一个n,m的无向图，求稳定子图的个数。稳定子图定义为包含三元环或三个点的独立集为子图的图。
\(1\leq n\leq 50\)
根据ramsey定理，6个点以上的子图都是稳定子图
所以搜索5个点以下的情况即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> using namespace std; typedef long long LL; const LL MOD=1000000007; const int SIZEN=60; LL quickpow(LL a,LL n){ LL ans=1; while(n){ if(n&1) ans=(ans*a)%MOD; a=(a*a)%MOD; n>>=1; } return ans; } int N,M; bool c[SIZEN][SIZEN]; bool check(int i,int j,int k){ return c[i][j]==c[i][k]&&c[i][k]==c[j][k]; } vector<int> now; LL stable=0; bool able(int x){ for(int i=0;i<now.size();i++){ for(int j=0;j<i;j++){ if(check(x,now[i],now[j])) return false; } } return true; } void DFS(int x){ if(x>N||now.size()>=5) return; if(able(x)){ stable++; now.push_back(x); DFS(x+1); now.pop_back(); } DFS(x+1); } int kase=0; void work(void){ scanf("%d%d",&N,&M); memset(c,0,sizeof(c)); int a,b; for(int i=1;i<=M;i++){ scanf("%d%d",&a,&b); c[a][b]=c[b][a]=1; } stable=1; now.clear(); DFS(1); LL all=quickpow(2,N); LL ans=(all-stable)%MOD; if(ans<0) ans+=MOD; printf("Case #%d: ",++kase); cout<<ans<<endl; } int main(){ int T;scanf("%d",&T); while(T--) work(); return 0; } |
hdu5918.Sequence I
分别给出长度为n,m的正整数序列a,b,问a中有多少个起点q,满足从q开始,间隔为p，长度为m的子序列能和b匹配
\(1\leq n,m,p\leq 100000\)
将a拆成p个子序列，每一个和b做一次kmp
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T,n,m,P,ans; int a[1000005],b[1000005],p[1000005]; void solve(int x) { for(int i=x,j=0;i<=n;i+=P) { while(b[j+1]!=a[i]&&j!=0)j=p[j]; if(b[j+1]==a[i])j++; if(j==m)j=p[j],ans++; } } int main() { T=read(); for(int test=1;test<=T;test++) { n=read();m=read();P=read();ans=0; for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=m;i++)b[i]=read(); for(int j=0,i=2;i<=m;i++) { while(b[j+1]!=b[i]&&j!=0)j=p[j]; if(b[j+1]==b[i])j++; p[i]=j; } for(int i=1;i<=P;i++) solve(i); cout<<"Case #"<<test<<": "<<ans<<endl; } return 0; } |
HDU 5919.Sequence II
给一个长为n的数列，m次查询，每次查询一个区间中每一种数在区间中第一次出现的位置的中位数
强制在线 \(1\leq n,m\leq 2*10^5\)
设区间内有K个不同数字，二分一个mid，使得l到mid中恰好有K个不同数字
查询\([l,r]\)中不相同的数字个数可以记录一下每个数字下一次出现的位置\(nxt_i\)，问题转化成该区间有多少个nxt大于r
用主席树实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T,n,m,ans; int cnt,a[200005],nxt[200005],last[200005]; int rt[200005],ls[10000005],rs[10000005],v[10000005]; void insert(int x,int &y,int l,int r,int val) { int mid=(l+r)>>1; y=++cnt;v[y]=v[x]+1; if(l==r)return; ls[y]=ls[x];rs[y]=rs[x]; if(val<=mid) insert(ls[x],ls[y],l,mid,val); else insert(rs[x],rs[y],mid+1,r,val); } int query(int x,int y,int l,int r,int K) { if(l==r)return 0; int mid=(l+r)>>1; if(K<=mid)return v[rs[y]]-v[rs[x]]+query(ls[x],ls[y],l,mid,K); else return query(rs[x],rs[y],mid+1,r,K); } int solve(int l,int r) { int ans=query(rt[l-1],rt[r],1,n+1,r); return ans; } int main() { T=read(); for(int test=1;test<=T;test++) { n=read();m=read();cnt=ans=0; for(int i=1;i<=n;i++) a[i]=read(); for(int i=0;i<=200000;i++)last[i]=n+1; for(int i=n;i>=1;i--) { nxt[i]=last[a[i]]; last[a[i]]=i; } for(int i=1;i<=n;i++) insert(rt[i-1],rt[i],1,n+1,nxt[i]); cout<<"Case #"<<test<<":"; for(int i=1;i<=m;i++) { int l=read(),r=read(); l=(l+ans)%n+1,r=(r+ans)%n+1; if(l>r)swap(l,r); int t=solve(l,r); t=(t+1)/2; int L=l,R=r; while(L<=R) { int mid=(L+R)>>1; if(solve(l,mid)>=t)ans=mid,R=mid-1; else L=mid+1; } cout<<' '<<ans; } cout<<endl; } return 0; } |
HDU 5920.Ugly Problem
给一个数字s，要求构造n个回文数的和等于s，n不超过50
\(1\leq s\leq 10^{1000}\)
每次构造一个不超过S的最大回文数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<cassert> using namespace std; const int SIZEN=1010; void print(int *a,int &n){ for(int i=n-1;i>=0;i--) cout<<a[i]; } void sub_at(int *a,int &n1,int *b,int &n2){ assert(n2<=n1); for(int i=0;i<n2;i++){ a[i]-=b[i]; } for(int i=0;i<n1;i++){ if(a[i]<0){ a[i]+=10; a[i+1]--; } } while(n1>1&&!a[n1-1]){ n1--; } } bool is_zero(int *a,int &n1){ return n1==1&&a[0]==0; } void half_at(int *a,int &n1,int *b,int &n2){ n2=(n1+1)/2; int *p=b; for(int i=n1-n2;i<n1;i++) *(p++)=a[i]; } bool lessequ(const int *a,const int &n1,const int *b,const int &n2){ if(n1<n2) return true; if(n1>n2) return false; for(int i=n1-1;i>=0;i--){ if(a[i]<b[i]) return true; if(a[i]>b[i]) return false; } return true; } bool tenpow(const int *a,const int &n){ if(a[n-1]!=1) return false; for(int i=0;i<n-1;i++){ if(a[i]!=0) return false; } return true; } int one[]={1,0},onel=1; void get_half(int *a,int &n1,int *b,int &n2){ if(n1==1){ n2=1; b[0]=a[0]; } else if(n1==2&&a[1]==1){ n2=1; b[0]=9; } else{ int h=(n1+1)/2; int ofs=n1-h; memcpy(b,a,n1*sizeof(int)); for(int i=0;i<ofs;i++) b[i]=b[n1-1-i]; if(lessequ(b,n1,a,n1)){ n2=n1; return; } if(tenpow(b+ofs,h)){ n2=n1-1; for(int i=0;i<n2;i++) b[i]=9; return; } sub_at(b+ofs,h,one,onel); for(int i=0;i<ofs;i++){ b[i]=b[n1-1-i]; } n2=h+ofs; } } string extract(int *a,int &n){ string ans=""; for(int i=0;i<n;i++){ ans=char(a[i]+'0')+ans; } return ans; } void read_at(int *a,int &n){ static char s[SIZEN]; scanf("%s",s); n=strlen(s); for(int i=0;i<n;i++){ a[n-1-i]=s[i]-'0'; } } int A[SIZEN],N1,B[SIZEN],N2; vector<string> ans; int kase=0; void work(void){ ans.clear(); read_at(A,N1); while(!is_zero(A,N1)){ get_half(A,N1,B,N2); ans.push_back(extract(B,N2)); sub_at(A,N1,B,N2); } printf("Case #%d:\n",++kase); cout<<ans.size()<<endl; for(int i=0;i<ans.size();i++){ cout<<ans[i]<<endl; } } int main(){ int T;scanf("%d",&T); while(T--) work(); return 0; } |
hdu5921.Binary Indexed Tree
求[0,n]中的数组成的所有有序二元组(x,y)的cost的和，cost(x,y)定义为，把x不断减去二进制下的末尾的1，把出现过的数放到集合\(S_x\)，y做相同操作得到集合\(S_y\)，cost是两集合的并减去交
\(1\leq T\leq 10000,1\leq n\leq 10^{18}\)
令f(x)为x二进制下1的个数
\(ans=\sum\sum\{[f(i)+f(j)]-2f(lcp(i,j))\}\)
分别在二进制下计算两部分对答案的贡献
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; typedef long long LL; const int MOD=1000000007; int T; LL n,ans,inv2=(MOD+1)/2,f[100],pow2[200],sum; int main() { cin>>T; pow2[0]=1; for(int i=1;i<=150;i++) pow2[i]=(pow2[i-1]+pow2[i-1])%MOD; f[1]=0; for(int i=2;i<=62;i++) f[i]=(f[i-1]+f[i-1]+(pow2[i-1]*(pow2[i-1]-1+MOD)%MOD*inv2))%MOD; for(int cas=1;cas<=T;cas++) { cin>>n; n++; LL nn=n,nnn=(n-1)%MOD; ans=0,sum=0; for(int i=62;i>=0;i--) if(nn>=(1LL<<i)) { sum=(sum+i*pow2[i-1])%MOD; nn-=(1LL<<i); sum=(sum+nn)%MOD; } for(int i=62;i>=0;i--) if(n>=(1LL<<i)) { ans=(ans+f[i])%MOD; n-=(1LL<<i); LL o=n%MOD; ans=(ans+o*(o-1+MOD)%MOD*inv2)%MOD; } sum=(sum*nnn)%MOD; cout<<"Case #"<<cas<<": "; cout<<(sum-ans-ans+MOD+MOD)%MOD<<endl; } return 0; } |
Subscribe
计数器 9322841
OI 课件=>
OI 课件=>