2016 ACM / ICPC Asia Regional Dalian Online
1002 Different GCD Subarray Query
问长为n的序列，m个询问，问区间[L,R]所有子段的不同gcd值个数
考虑固定左端点，随着右端点的移动，gcd至多衰减log次（每次至少折半）
|
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 |
#include<map> #include<set> #include<ctime> #include<queue> #include<stack> #include<cmath> #include<vector> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define lb long double #define mod 1000000007 #define inf 1000000000 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,q; int t[1000005],now[1000005],a[100005]; ll ans[100005]; int f[100005][17]; int bin[20],Log[100005]; vector<int>qr[100005],id[100005]; int gcd(int x,int y) { return y==0?x:gcd(y,x%y); } void pre() { for(int i=1;i<=n;i++)f[i][0]=a[i]; for(int i=1;i<=16;i++) for(int x=1;x<=n;x++) if(x+bin[i]-1<=n) f[x][i]=gcd(f[x][i-1],f[x+bin[i-1]][i-1]); else break; } int query(int l,int r) { int t=Log[r-l+1]; return gcd(f[l][t],f[r-bin[t]+1][t]); } void add(int x,int val) { for(int i=x;i<=1000000;i+=i&(-i)) t[i]+=val; } ll query(int x) { ll tot=0; for(int i=x;i;i-=i&(-i)) tot+=t[i]; return tot; } int find(int x,int l,int L) { int r=n,ans=n+1; while(l<=r) { int mid=(l+r)>>1; if(query(L,mid)!=x)ans=mid,r=mid-1; else l=mid+1; } return ans; } int main() { bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1; while(scanf("%d%d",&n,&q)!=EOF) { for(int i=0;i<=1000000;i++)now[i]=inf; memset(t,0,sizeof(t)); Log[0]=-1;for(int i=1;i<=n;i++)Log[i]=Log[i>>1]+1; for(int i=1;i<=n;i++) qr[i].clear(),id[i].clear(); for(int i=1;i<=n;i++) a[i]=read(); pre(); for(int i=1;i<=q;i++) { int x=read(),y=read(); qr[x].push_back(y); id[x].push_back(i); } for(int i=n;i;i--) { int R=i,tmp=a[i]; if(now[tmp]!=inf)add(now[tmp],-1); now[tmp]=i; add(now[tmp],1); while(1) { R=find(tmp,R,i); if(R==n+1)break; tmp=query(i,R); if(R<now[tmp]) { if(now[tmp]!=inf)add(now[tmp],-1); now[tmp]=R; add(now[tmp],1); } } for(int j=0;j<qr[i].size();j++) ans[id[i][j]]=query(qr[i][j]); } for(int i=1;i<=q;i++) printf("%I64d\n",ans[i]); } return 0; } |
n个人，每个人可以用m种颜色中的一部分染色自己的项链
两个人是朋友当且仅当他们拥有相同的颜色
敌人不拥有任何相同的颜色
问对于任意一种关系情况，m种颜色是否足够
用连边表现朋友关系，n/2个点中每个点a向其余的n/2个点连边
可以证明，至少需要n*n/4种颜色，而且这是最差的情况
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; typedef long long LL; LL n,m; int main() { while(cin>>n>>m) { if(m>=(n*n)/4LL) puts("T"); else puts("F"); } return 0; } |
1008 Function
问长为n的序列，m个询问，问的值
一个数a取模小于等于其的数b，其值才会变化
从l开始，每次用二分+ST表寻找最近的小于当前模数的下一个数
|
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 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> 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,q; int bin[20],Log[100005]; int a[100005],f[100005][17]; void pre() { for(int i=1;i<=n;i++)f[i][0]=a[i]; for(int i=1;i<=16;i++) for(int x=1;x<=n;x++) if(x+bin[i]-1<=n) f[x][i]=min(f[x][i-1],f[x+bin[i-1]][i-1]); else break; } int query(int l,int r) { int t=Log[r-l+1]; return min(f[l][t],f[r-bin[t]+1][t]); } int find(int l,int val) { int L=l,R=n,ans=n+1; while(L<=R) { int mid=(L+R)>>1; if(query(L,mid)>val)L=mid+1; else ans=mid,R=mid-1; } return ans; } int main() { bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1; T=read(); while(T--) { n=read(); Log[0]=-1;for(int i=1;i<=n;i++)Log[i]=Log[i>>1]+1; for(int i=1;i<=n;i++) a[i]=read(); pre(); q=read(); for(int i=1;i<=q;i++) { int l=read(),r=read(); int tmp=a[l],now=l; while(1) { now=find(now+1,tmp); if(now>r)break; tmp=tmp%a[now]; } printf("%d\n",tmp); } } return 0; } |
容易证明，从S能到达的点，最远点的距离不会超过 \(T=\sqrt{2m}\) 次
循环T次，第i次标记距离为i的结点，即每次查看原图上未标记的点是否与所有已标记的点连边
复杂度\(m\sqrt{2m}\)
|
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 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> using namespace std; int T,n,m,x[200005],y[200005],S,dis[200010],vis[200010],size; int v[200005],top; inline int getint() { int res=0; char c=getchar(); while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') res=res*10+c-'0',c=getchar(); return res; } int main() { T=getint(); while(T--) { size=1; n=getint(),m=getint(); top=0; for(int i=1;i<=m;i++) x[i]=getint(),y[i]=getint(),v[++top]=x[i],v[++top]=y[i]; sort(v+1,v+top+1); int len=unique(v+1,v+top+1)-v-1; scanf("%d",&S); for(int i=1;i<=n;i++) dis[i]=-1; dis[S]=0; for(int t=1;t<=300;t++) { for(int i=1;i<=m;i++) { if(dis[x[i]]!=-1&&dis[y[i]]==-1) vis[y[i]]++; if(dis[y[i]]!=-1&&dis[x[i]]==-1) vis[x[i]]++; } int d=0; if(t==1) { for(int i=1;i<=n;i++) if(vis[i]!=size&&dis[i]==-1) dis[i]=t,d++; } else { for(int i=1;i<=len;i++) if(vis[v[i]]!=size&&dis[v[i]]==-1) dis[v[i]]=t,d++; } size+=d; for(int i=1;i<=m;i++) vis[x[i]]=0,vis[y[i]]=0; } int tot=0; for(int i=1;i<=n;i++) { if(i==S) continue; printf("%d",dis[i]); ++tot; if(tot==n-1) puts(""); else putchar(' '); } } return 0; } |
Subscribe
计数器 9325530
OI 课件=>
OI 课件=>