PKUSC 2014 #4
A:Magical GCD
枚举每个起点
gcd变化不超过log次，二分+rmq求分界点
|
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 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long #define pa pair<ll,int> using namespace std; ll read() { ll 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; } ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); } int bin[20],Log[100005]; int T,n; ll a[100005],f[17][100005]; ll ans; void pre() { for(int i=1;i<=n;i++)f[0][i]=a[i]; for(int i=1;i<=16;i++) for(int j=1;j<=n;j++) if(j+bin[i]-1<=n) f[i][j]=gcd(f[i-1][j],f[i-1][j+bin[i-1]]); } ll query(int a,int b) { int t=Log[b-a+1]; return gcd(f[t][a],f[t][b-bin[t]+1]); } void solve(int x) { for(ll t=a[x],now=x;now<=n;t=query(x,now)) { int l=now,r=n; while(l<=r) { int mid=(l+r)>>1; if(query(x,mid)<t)r=mid-1; else now=mid,l=mid+1; } ans=max((ll)(now-x+1)*query(x,now),ans); now++; } } int main() { Log[0]=-1;for(int i=1;i<=100000;i++)Log[i]=Log[i/2]+1; bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1; T=read(); while(T--) { n=read(); for(int i=1;i<=n;i++)a[i]=read(); pre();ans=0; for(int i=1;i<=n;i++)solve(i); printf("%lld\n",ans); } return 0; } |
B:Data Packing
不知道是不是这样做QAQ
|
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 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long #define pa pair<ll,int> using namespace std; ll read() { ll 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 n,x; int a[100005]; int main() { while(scanf("%d%d",&n,&x)!=EOF) { for(int i=1;i<=n;i++)a[i]=read(); sort(a+1,a+n+1); int now=1,ans=0; for(int i=n;i>=now;i--) { ans++; if(a[now]<=x-a[i])now++; } printf("%d\n",ans); } return 0; } |
C:Radar Installation
得出覆盖每个点的区间贪心即可
|
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 119 120 121 122 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long #define pa pair<ll,int> using namespace std; ll read() { ll 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 n,m,cnt,sum,rt; int last[10005],size[10005],d[10005],f[10005],q[105]; bool vis[10005],mark[105]; struct edge{ int to,next,v; }e[20005]; vector<int>tmp; set<int>st; void insert(int u,int v,int w) { e[++cnt]=(edge){v,last[u],w};last[u]=cnt; e[++cnt]=(edge){u,last[v],w};last[v]=cnt; } void getrt(int x,int fa) { size[x]=1;f[x]=0; for(int i=last[x];i;i=e[i].next) if(!vis[e[i].to]&&e[i].to!=fa) { getrt(e[i].to,x); size[x]+=size[e[i].to]; f[x]=max(f[x],size[e[i].to]); } f[x]=max(f[x],sum-size[x]); if(f[x]<f[rt])rt=x; } void getdp(int x,int fa) { tmp.push_back(d[x]); for(int i=last[x];i;i=e[i].next) if(!vis[e[i].to]&&e[i].to!=fa) { d[e[i].to]=d[x]+e[i].v; getdp(e[i].to,x); } } void solve(int x) { vis[x]=1; st.clear(); for(int i=last[x];i;i=e[i].next) if(!vis[e[i].to]) { tmp.clear(); d[e[i].to]=e[i].v; getdp(e[i].to,x); for(int j=0;j<tmp.size();j++) for(int k=1;k<=m;k++) if(!mark[k]&&q[k]>=tmp[j]) { if(q[k]==tmp[j])mark[k]=1; else mark[k]=st.find(q[k]-tmp[j])!=st.end(); } for(int j=0;j<tmp.size();j++) st.insert(tmp[j]); } for(int i=last[x];i;i=e[i].next) if(!vis[e[i].to]) { sum=size[e[i].to];rt=0; getrt(e[i].to,x); solve(rt); } } int main() { while(1) { n=read(); if(n==0)return 0; cnt=0;memset(last,0,sizeof(last)); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) { int x=read(),v; while(x!=0) { v=read(); insert(i,x,v); x=read(); } } m=0; int x=read(); while(x!=0) { q[++m]=x; x=read(); } memset(mark,0,sizeof(mark)); rt=0;sum=n;f[0]=inf; getrt(1,0); solve(rt); for(int i=1;i<=m;i++) if(mark[i])puts("AYE"); else puts("NAY"); puts("."); } return 0; } |
E:Egyptian 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 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 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } struct data{ int a,b; friend data operator+(data x,data y){ int t=gcd(x.b,y.b); return (data){(x.a*y.b+x.b*y.a)/t,x.b*y.b/t}; } friend bool operator<(data x,data y){ return x.a*y.b<x.b*y.a; } friend data operator-(data x,data y){ y.a=-y.a; return x+y; } friend data operator*(data x,int y){ x.a*=y; int t=gcd(x.a,x.b); return (data){x.a/t,x.b/t}; } }; void print(data a) { printf("%d/%d",a.a,a.b); } bool flag; int a,b,dep,mn=20000; int ans[305],c[305]; data n; void dfs(data n,int now,int k) { if(now>mn||n.b>500000)return; if(n.a==0&&now<mn) { flag=1;mn=now; for(int i=1;i<=dep;i++)ans[i]=c[i]; return; } if(n.a<=0)return; data p=(data){1,now}; if(p*(dep-k+1)<n)return; c[k]=now;dfs(n-p,now+1,k+1); dfs(n,now+1,k); } int main() { scanf("%d%d",&a,&b); n=(data){a,b}; for(dep=1;dep<=10;dep++) { dfs(n,1,1); if(flag)break; } printf("%d/%d=",a,b); for(int i=1;i<=dep;i++) { printf("1/%d",ans[i]); if(i!=dep)printf("+"); } return 0; } |
Subscribe
计数器 9774804
OI 课件=>
OI 课件=>