| 长途旅行 |
| 难度级别：A； 运行时间限制：3000ms； 运行空间限制：262144KB； 代码长度限制：2000000B |
|
试题描述
|
|
JY 是一个爱旅游的探险家，也是一名强迫症患者。现在JY 想要在C 国进行一次长途 旅行，C 国拥有n 个城市(编号为0,1,2...,n - 1)，城市之间有m 条道路，可能某个城市到自己 有一条道路，也有可能两个城市之间有多条道路，通过每条道路都要花费一些时间。JY 从 0 号城市开始出发，目的地为n – 1 号城市。由于JY 想要好好参观一下C 国，所以JY 想要旅行恰好T 小时。为了让自己的旅行更有意思，JY 决定不在任何一个时刻停留(走一条到城市自己的路并不算停留)。JY 想知道是否能够花恰好T 小时到达n – 1 号城市（每个城市可经过多次）。现在这个问题交给了你。 若可以恰好到达输出“Possible”否则输出“Impossible”。(不含引号)。 |
|
输入
|
|
第一行一个正整数Case，表示数据组数。
每组数据第一行3 个整数，分别为n, m, T。 接下来m 行，每行3 个整数x, y, z,代表城市x 和城市y 之间有一条耗时为z 的双向边。 |
|
输出
|
|
对于每组数据输出”Possible”或者”Impossible”.
|
|
输入示例
|
|
2
3 3 11 0 2 7 0 1 6 1 2 5 2 1 10000 1 0 1 |
|
输出示例
|
|
Possible
Impossible |
|
其他说明
|
|
【样例解释】
第一组：0 -> 1 -> 2 :11 第二组：显然偶数时间都是不可能的。 【数据范围】 30%: T <= 10000 另有30%: n <= 5 , m <= 10. 100%: 2 <= n <= 50 , 1 <= m <= 100 , 1 <= z <= 10000 , 1 <= T <= 10^18 , Case <= 5. |
我还不懂哒。。。
hzwer的题解：http://hzwer.com/5006.html（然而我还不知道这个结论为什么是对的）
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } typedef long long ll; const int maxn=55; const int maxm=210; const int maxk=20010; struct HeapNode { int x,u,d; bool operator < (const HeapNode& ths) const {return d>ths.d;} }; int done[maxn][maxk],first[maxn],next[maxm],to[maxm],dist[maxm],n,m,mod,e; ll d[maxn][maxk],T; void AddEdge(int u,int v,int w) { to[++e]=v;dist[e]=w;next[e]=first[u];first[u]=e; to[++e]=u;dist[e]=w;next[e]=first[v];first[v]=e; } priority_queue<HeapNode> Q; int dijkstra() { rep(i,1,n) rep(j,0,mod) done[i][j]=0,d[i][j]=1ll<<60; d[1][0]=0;Q.push((HeapNode){1,0,0}); while(!Q.empty()) { int x=Q.top().x,u=Q.top().u;Q.pop(); if(done[x][u]) continue;done[x][u]=1; ren { int u2=(u+dist[i])%mod; if(d[x][u]+dist[i]<d[to[i]][u2]) { d[to[i]][u2]=d[x][u]+dist[i]; Q.push((HeapNode){to[i],u2,d[to[i]][u2]}); } } } return d[n][T%mod]<=T; } int main() { dwn(Case,read(),1) { n=read();m=read();scanf("%lld",&T);mod=e=0; memset(first,0,sizeof(first)); rep(i,1,m) { int u=read()+1,v=read()+1,w=read(); AddEdge(u,v,w);if(u==1||v==1) mod=w<<1; } if(!mod) puts("Impossible"); else if(dijkstra()) puts("Possible"); else puts("Impossible"); } return 0; }
| 数列 |
| 难度级别：A； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
Czy 手上有一个长度为n 的数列，第i 个数为xi。 他现在想知道，对于给定的a,b,c，他要找到一个i，使得 a*(i+1)*xi2+(b+1)*i*xi+(c+i)=0 成立。 如果有多个i 满足，Czy 想要最小的那个i。 Czy 有很多很多组询问需要你回答，多到他自己也不确定有多少组。所以在输入数据中a=b=c=0 标志着Czy 的提问的结束。 更加糟糕的是，Czy 为了加大难度，决定对数据进行加密以防止离线算法的出现。 假设你在输入文件中读到的三个数为a0,b0,c0，那么Czy 真正要询问的a=a0+LastAns,b=b0+LastAns,c=c0+LastAns. LastAns 的值是你对Czy 的前一个询问的回答。如果这是第一个询问，那么LastAns=0。 所有的询问都将会按上述方式进行加密，包括标志着询问的结束的那个询问也是这样。 |
|
输入
|
|
输入文件为 seq.in
输入文件第一行包含一个整数n，表示数列的长度。 输入文件第二行包含n 个整数，第i 个数表示xi 的值。 接下来若干行，每行三个数，表示加密后的a,b,c 值（也就是上文所述的a0,b0,c0） |
|
输出
|
|
输出文件为 seq.out
包含若干行，第i 行的值是输入文件中第i 个询问的答案。注意，你不需要对标志着询问结束的那个询问作答。 同时，标志着询问结束的询问一定是输入文件的最后一行。也就是，输入文件不会有多余的内容。 |
|
输入示例
|
|
5
-2 3 1 -5 2 -5 -4 145 -1 -6 -509 -9 -14 40 -3 -13 21 -3 -3 -3 |
|
输出示例
|
|
5
4 3 3 |
|
其他说明
|
|
【数据范围】
对于40%的数据，满足N<=1000，需要作出回答的询问个数不超过1000. 对于100%的数据，满足N<=50000，需要作出回答的询问个数不超过500000，xi 的绝对值不 超过30000，解密后的a 的绝对值不超过50000，解密后的b 的绝对值不超过10^8，解密后的c 的绝对值不超过10^18. |
好逗的一道题。。。
注意结尾肯定是0 0 0，那么倒数第二个问题的答案可以推出来，然后倒数第三个问题的答案可以推出来。。。。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; typedef long long ll; inline ll read() { ll x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=500010; int n,m=1,v[maxn]; ll A[maxn],B[maxn],C[maxn],res[maxn],ans; int main() { n=read(); rep(i,1,n) v[i]=read(); while(scanf("%lld%lld%lld",&A[m],&B[m],&C[m])==3) m++;m--; res[m]=ans=-A[m]; dwn(k,m-1,1) { ll xi=v[ans],i=ans; ll t1=A[k]*(i+1)*xi*xi+(B[k]+1)*i*xi+(C[k]+i); ll t2=(i+1)*xi*xi+i*xi+1; res[k]=ans=-t1/t2; } rep(i,2,m) printf("%lld ",res[i]); return 0; }
| 刷漆 |
| 难度级别：A； 运行时间限制：1000ms； 运行空间限制：262144KB； 代码长度限制：2000000B |
|
试题描述
|
|
Czy 做完了所有的回答出了所有的询问，结果是，他因为脑力消耗过大而变得更虚了:)。帮助Czy 恢复身材的艰巨任务落到了你的肩上。 正巧，你的花园里有一个由N 块排成一条直线的木板组成的栅栏，木板从左到右依次标号1到N。这N 块木板中，有M 块木板前面放着一桶油漆。油漆有不同的颜色，每种颜色可以由一个大写字母表示(A 到Z)。而你要求Czy 用他的油漆刷子给栅栏刷上油漆。 已知Czy 会选择一个前方放有油漆桶的木板开始他的任务。刷子蘸上油漆后，他开始随机地沿着栅栏走，他不会走出栅栏的范围。随机地走表示Czy 会沿着他选择的方向一直走，然后随机在任何时候改变方向。沿着栅栏走只有两个方向，向前和向后。 你发现Czy 刷油漆的过程总是符合下列规则: • 每个油漆桶里装着无限多的油漆； • 刷子上每次只有一种颜色的油漆，每次蘸油漆都会完全替换刷子上的油漆颜色； • 当Czy 走到一个油漆桶前，他会首先用刷子蘸这个油漆桶里的油漆； • Czy 每走过一个木板都会将这个木板刷成当前刷子上的油漆颜色。 已知木板可以被多次刷上油漆，每次都会完全覆盖之前的颜色。当所有木板都被刷上了油漆的时候，Czy 才能停下来(当然他也可以继续刷到他想停下来为止)。你看着Czy 在栅栏前来回舞动，突然想知道Czy 停下来的时候栅栏有多少种可能的不同油漆方案。定义当至少有一块木板颜色不同时，两种油漆方案被视为是不同的。 请你输出不同的油漆方案数对10^9+9 取模的值。
|
|
输入
|
|
输入的第一行包含两个整数N 和M。
接下来M 行，每行两个整数x 和y，表示第y 块木板前面有一个装着颜色为x 的油漆的油漆桶。 |
|
输出
|
|
输出一行，包含一个整数，表示不同的油漆方案数对10^9 + 9 取模的结果。
|
|
输入示例
|
|
6 2
A 2 B 6 |
|
输出示例
|
|
4
|
|
其他说明
|
|
【数据范围】
对于30% 的数据，1 ≤ M ≤ N ≤ 100。 对于100% 的数据， 1 ≤ M ≤ N ≤ 100000。 x 是A 到Z 之间的大写字母；1 ≤ y ≤ N。 |
可以将整个线段分成若干段，若i、j均是油漆桶，且Ai!=Aj，则这区间共有j-i种方案，乘起来就行了。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=100010; const int mod=1000000009; long long ans=1; int A[maxn]; int main() { int n=read(),m=read(); rep(i,1,m) { char c[2];scanf("%s",c); int p=read(); A[p]=c[0]-'A'+1; } rep(i,1,n) if(A[i]) {A[0]=A[i];break;} dwn(i,n,1) if(A[i]) {A[n+1]=A[i];break;} rep(i,0,n) { int j=i+1; while(j<=n+1&&!A[j]) j++; if(A[i]!=A[j]) (ans*=(j-i))%=mod; i=j-1; } printf("%lld ",ans); return 0; }
| 排队 |
| 难度级别：A； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
Czy 喜欢将他的妹子们排成一队。假设他拥有N 只妹纸，编号为1 至N。Czy 让他们站成一行，等待自己来派送营养餐。这些妹纸按照编号大小排列，并且由于它们都很想早点吃饭，于是就很可能出现多只妹纸挤在同一位置的情况(也就是说，如果我们认为妹纸位于数轴上，那么多只妹纸的位置坐标可能相同)。 因为众所周知的原因，某些妹纸之间互相喜欢，他们希望互相之间的距离至多为一个定值。 但某些妹纸之间互相厌恶，他们希望互相之间的距离至少为一个定值。现在给定ML 个互相喜爱的妹纸对以及他们之间距离的最大值，MD 个互相厌恶的妹纸对以及他们之间距离的最小值。 你的任务是计算在满足以上条件的前提下，帮助Czy 计算出编号为1 和编号为N 的妹纸之间距离的最大可能值。 |
|
输入
|
|
输入文件为 layout.in。
第一行有 3 个整数，每两个整数之间用一个空格隔开，依次表示 n,ML 和DL ； 此后ML 行，每行包含三个用空格分开的整数A,B 和D，其中A,B 满足1<=A<=B<=N。表示编号为A 和B 的妹纸之间的距离至多为D。 此后MD 行，每行包含三个用空格分开的整数A,B 和D，其中A,B 满足1<=A<=B<=N。表示编号为A 和B 的妹纸之间的距离至少为D。 |
|
输出
|
|
输出文件名为 layout.out。
输出文件仅包含一个整数。如果不存在任何合法的排队方式，就输出‐1。如果编号1 和编号N 的妹纸间距离可以任意，就输出‐2 。否则输出他们之间的最大可能距离。 |
|
输入示例
|
|
4 2 1
1 3 10 2 4 20 2 3 3 |
|
输出示例
|
|
27
|
|
其他说明
|
|
【数据范围】
对于40%的数据，N<=100； 对于100%的数据，N<=1000；ML,MN<=10000；D<=1000000。 |
又是查分约束系统
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } typedef long long ll; const int maxn=1010; const int maxm=20010; const ll INF=1e16; int n,first[maxn],to[maxm],dist[maxm],next[maxm],e; void AddEdge(int u,int v,int w) { to[++e]=v;dist[e]=w;next[e]=first[u];first[u]=e; } int inq[maxn],q[maxn],cnt[maxn]; ll d[maxn]; int spfa() { rep(i,2,n) d[i]=INF; int l=0,r=1;q[0]=1; while(l!=r) { int x=q[l++];if(l==1005) l=0;inq[x]=0; ren if(d[to[i]]>d[x]+dist[i]) { d[to[i]]=d[x]+dist[i]; if(++cnt[to[i]]>n) return -1; if(!inq[to[i]]) { inq[to[i]]=1; q[r++]=to[i];if(r==1005) r=0; } } } return d[n]==INF?-2:d[n]; } int main() { n=read();int m1=read(),m2=read(); rep(i,1,m1) { int a=read(),b=read(),c=abs(read()); AddEdge(a,b,c); } rep(i,1,m2) { int a=read(),b=read(),c=abs(read()); AddEdge(b,a,-c); } printf("%d ",spfa()); return 0; }
| 感冒病毒 |
| 难度级别：A； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
一种感冒病毒正在学校里传播，这所学校有n个学生，m个学生社团，每个学生可能参加了多个社团，因为同一个社团的学生交流较多，所以如果一个学生感染上感冒病毒，那么他所在的社团里的所有学生都会感染上感冒病毒，现在已知0号学生感染上感冒病毒，问现在有多少人会感染上感冒病毒。
|
|
输入
|
|
输入文件：suspects.in
输入的第一行是两个整数n和m，表示学生的数目和社团的数目,学生的编号为0到n-1。 接下来m行，每行首先是一个数ki，表示这个社团有ki个人，接下来ki个整数，表示这个社团里每个学生的编号aij。 |
|
输出
|
|
输出文件：suspects.out
输出为一行，包含一个整数。表示感染感冒病毒的人数。 |
|
输入示例
|
|
100 4
2 1 10 5 10 13 11 12 14 2 0 1 2 9 2 |
|
输出示例
|
|
7
|
|
其他说明
|
|
【数据范围】
对于100%的数据，3<=n<=30000 对于100%的数据，3<=m<=500 对于100%的数据，1<=ki<=n 对于100%的数据，0<=aij<n。 |
。。。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=30010; int n,m,pa[maxn]; int findset(int x) {return x==pa[x]?x:pa[x]=findset(pa[x]);} int main() { n=read();m=read(); rep(i,1,n) pa[i]=i; rep(i,1,m) { int k=read(),x=read()+1; while(--k) pa[findset(x)]=findset(read()+1); } int ans=0; rep(i,1,n) if(findset(i)==findset(1)) ans++; printf("%d ",ans); return 0; }
| 弱点 |
| 难度级别：A； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
一队勇士正在向你进攻，每名勇士都有一个战斗值ai。但是这队勇士却有一个致命弱点，如果存在i<j<k使得ai>aj>ak，则会影响他们整体的战斗力。我们将这样的一组(i,j,k)称为这队勇士的一个弱点。请求出这队勇士的弱点数目。
|
|
输入
|
|
输入文件：weakness.in
输入的第一行是一个整数n，表示勇士的数目。 接下来一行包括n个整数，表示每个勇士的战斗值ai。 |
|
输出
|
|
输入文件：weakness.out
输出为一行，包含一个整数。表示这队勇士的弱点数目。 |
|
输入示例
|
|
4
10 8 3 1 |
|
输出示例
|
|
4
|
|
其他说明
|
|
【数据范围】
对于30%的数据，3<=n<=100 对于100%的数据，3<=n<=1000000 对于100%的数据，1<=ai<=1000000，每个ai均不相同 |
对于每个位置，求出有多少在其左边的数<Ai，有多少在其右边的数>Ai。用个Fenwich就行了。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } typedef long long ll; const int maxn=1000010; ll ans; int n,A[maxn],f[maxn],c[maxn]; int query(int x) { int res=0; for(;x;x-=x&-x) res+=c[x]; return res; } void add(int x,int v) { for(;x<=1000000;x+=x&-x) c[x]+=v; } int main() { n=read();rep(i,1,n) A[i]=read(); rep(i,1,n) { add(A[i],1); f[i]=i-query(A[i]); } memset(c,0,sizeof(c)); dwn(i,n,1) { add(A[i],1); ans+=(ll)query(A[i]-1)*f[i]; } printf("%lld ",ans); return 0; }
| 改造二叉树 |
| 难度级别：A； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
小Y在学树论时看到了有关二叉树的介绍：在计算机科学中，二叉树是每个结点最多有两个子结点的有序树。通常子结点被称作“左孩子”和“右孩子”。二叉树被用作二叉搜索树和二叉堆。随后他又和他人讨论起了二叉搜索树。 什么是二叉搜索树呢？二叉搜索树首先是一棵二叉树。设key[p]表示结点p上的数值。对于其中的每个结点p，若其存在左孩子lch，则key[p]>key[lch]；若其存在右孩子rch，则key[p]<key[rch]；注意，本题中的二叉搜索树应满足对于所有结点，其左子树中的key小于当前结点的key，其右子树中的key大于当前结点的key。 小Y与他人讨论的内容则是，现在给定一棵二叉树，可以任意修改结点的数值。修改一个结点的数值算作一次修改，且这个结点不能再被修改。若要将其变成一棵二叉搜索树，且任意时刻结点的数值必须是整数（可以是负整数或0），所要的最少修改次数。 相信这一定难不倒你！请帮助小Y解决这个问题吧。 |
|
输入
|
|
第一行一个正整数n表示二叉树结点数。结点从1~n进行编号。
第二行n个正整数用空格分隔开，第i个数ai表示结点i的原始数值。 此后n - 1行每行两个非负整数fa, ch，第i + 2行描述结点i + 1的父亲编号fa，以及父子关系ch，(ch = 0 表示i + 1为左儿子，ch = 1表示i + 1为右儿子)。 结点1一定是二叉树的根。 |
|
输出
|
|
仅一行包含一个整数，表示最少的修改次数。
|
|
输入示例
|
|
3
2 2 2 1 0 1 1 |
|
输出示例
|
|
2
|
|
其他说明
|
|
【数据范围】
20 % ：n <= 10 , ai <= 100. 40 % ：n <= 100 , ai <= 200 60 % ：n <= 2000 . 100 % ：n <= 10 ^ 5 , ai < 2 ^ 31. |
先将二叉树中序遍历，然后参见"Incr"。
#include<cstdio> #include<cctype> #include<queue> #include<stack> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=100010; int n,ans,cnt,vis[maxn],A[maxn],g[maxn],val[maxn],ls[maxn],rs[maxn]; int S[maxn],top; void dfs(int x) { S[++top]=x; while(top) { x=S[top]; if(!vis[x]) { vis[x]=1; if(ls[x]) S[++top]=ls[x]; } else { A[++cnt]=val[x];top--; if(rs[x]) S[++top]=rs[x]; } } } int main() { n=read();rep(i,1,n) val[i]=read(); rep(i,2,n) { int f=read(),t=read(); if(!t) ls[f]=i; else rs[f]=i; } dfs(1); rep(i,1,n) A[i]-=i,g[i]=2e9; rep(i,1,n) { int k=upper_bound(g+1,g+n+1,A[i])-g; ans=max(ans,k);g[k]=A[i]; } printf("%d ",n-ans); return 0; }
| 数字对 |
| 难度级别：A； 运行时间限制：3000ms； 运行空间限制：262144KB； 代码长度限制：2000000B |
|
试题描述
|
|
小H是个善于思考的学生，现在她又在思考一个有关序列的问题。 她的面前浮现出一个长度为n的序列{ai}，她想找出一段区间[L, R](1 <= L <= R <= n)。 这个特殊区间满足，存在一个k(L <= k <= R)，并且对于任意的i(L <= i <= R)，ai都能被ak整除。这样的一个特殊区间 [L, R]价值为R - L。 小H想知道序列中所有特殊区间的最大价值是多少，而有多少个这样的区间呢？这些区间又分别是哪些呢？你能帮助她吧。 |
|
输入
|
|
第一行，一个整数n.
第二行，n个整数，代表ai. |
|
输出
|
|
第一行两个整数，num和val,表示价值最大的特殊区间的个数以及最大价值。
第二行num个整数，按升序输出每个价值最大的特殊区间的L. |
|
输入示例
|
|
【样例输入1】
5 4 6 9 3 6 【样例输入2】 5 2 3 5 7 11 |
|
输出示例
|
|
【样例输出1】
1 3 2 【样例输出2】 5 0 1 2 3 4 5 |
|
其他说明
|
|
【数据范围】
30%: 1 <= n <= 30 , 1 <= ai <= 32. 60%: 1 <= n <= 3000 , 1 <= ai <= 1024. 80%: 1 <= n <= 300000 , 1 <= ai <= 1048576. 100%: 1 <= n <= 500000 , 1 <= ai < 2 ^ 31. |
枚举k，则问题转化成找最大的区间[l,r]满足对于任意的i(L <= i <= R)，ai都能被ak整除。
如果我们能实现一个快速计算区间gcd的数据结构，就可以用二分答案的方法O(logn)得出答案。
直接上ST表就行了。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } int gcd(int a,int b) {return !b?a:gcd(b,a%b);} const int maxn=500010; int n,first,A[maxn],f[maxn],yes[maxn],g[maxn],Log[maxn],res[maxn][20]; void init() { Log[0]=-1; rep(i,1,n) Log[i]=Log[i>>1]+1; rep(i,1,n) res[i][0]=A[i]; for(int j=1;(1<<j)<=n;j++) for(int i=1;i+(1<<j)-1<=n;i++) res[i][j]=gcd(res[i][j-1],res[i+(1<<j-1)][j-1]); } int query(int l,int r) { int k=Log[r-l+1]; return gcd(res[l][k],res[r-(1<<k)+1][k]); } int main() { n=read();rep(i,1,n) A[i]=read(); init(); rep(i,1,n) { int l=1,r=i; while(l<r) { int mid=l+r>>1; if(query(mid,i)%A[i]==0) r=mid; else l=mid+1; } f[i]=l; } dwn(i,n,1) { int l=i,r=n+1; while(l+1<r) { int mid=l+r>>1; if(query(i,mid)%A[i]==0) l=mid; else r=mid; } g[i]=l; } int ans=0,cnt=0; rep(i,1,n) ans=max(ans,g[i]-f[i]); rep(i,1,n) if(ans==g[i]-f[i]) yes[f[i]]=1; rep(i,1,n) if(yes[i]) cnt++; printf("%d %d ",cnt,ans); rep(i,1,n) if(yes[i]) { if(!first) first=1; else putchar(' '); printf("%d",i); } return 0; }
| 篮球比赛1 |
| 难度级别：A； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
Czhou为了提高机房里各种神牛的身体素质，决定在每次训练后举行篮球比赛。为了保持比赛公平，Czhou要将神牛们分成两队。首先神牛们赛前都要排成固定的队伍；然后Czhou将队伍分成一半（前一半和后一半队伍人数可以不等），再分别从两个队伍中选出一些人进行篮球比赛。为了保持公平性，Czhou要求第一个队伍参加比赛的神牛能力的XOR值等于第二个队伍参加比赛的神牛能力的and值。为了增加比赛趣味，每次比赛的参加神牛们不能一样，Czhou现在想知道可以举办多少天的比赛。(很明显参加比赛的人数不能为0) Xor即为亦或, 0 xor 0 = 0, 0 xor 1 = 1, 1 xor 0 = 1 , 1 xor 1 = 0。 And即为与, 0 and 0 = 0, 0 and 1 = 0, 1 and 0 = 0, 1 and 1 = 1。 举个例子10 and 2 = 10，10 xor 2 = 8， 10 = (1010)2 2 = (10)2 8 =(1000)2 |
|
输入
|
|
第一行n，表示机房有n个神牛。
第二行有n个数a_i，表示各个神牛的能力值，并且这是赛前各个神牛的排队方式。 |
|
输出
|
|
就一个数字，表示可以举办多少天比赛。由于天数会比较多，输出结果模1000000007。
|
|
输入示例
|
|
Sample1.input:
3 1 2 3 Sample2.input 4 1 2 3 3 |
|
输出示例
|
|
Sample1.output
1 Sample2.output 4 |
|
其他说明
|
|
样例1说明：1 xor 2 = 3
样例2说明：可以举办四天比赛，参加比赛的双方队伍分别是（1,2）（3）；（1,2）（3）；(1,2)(3,3)；（3）（3）这里虽然能力值相同，但是指的是不同的牛。 对于(1,2)(3,3)来说，队伍分为两个队伍：(1,2)(3,3)，再从各自队伍选出全部选手参加比赛 对于（3）（3）来说，队列分为两个队伍：（1,2,3）(3)，再从各自队伍中选出3进行比赛 数据范围： 0<=n<=10^3 0 <= a_i <1024 |
重复了。。。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } typedef long long ll; const int maxn=1010; const int maxk=1050; const int mod=1000000007; ll f[maxn][maxk][2],g[maxn][maxk][2]; int n,A[maxn]; int main() { n=read();rep(i,1,n) A[i]=read(); rep(i,1,n) { f[i][A[i]][0]++; rep(j,0,1023) { (f[i][j][1]+=f[i-1][j][0]+f[i-1][j][1])%=mod; (f[i][j^A[i]][0]+=f[i-1][j][1]+f[i-1][j][0])%=mod; } } dwn(i,n,1) { g[i][A[i]][0]++; rep(j,0,1023) { (g[i][j][1]+=g[i+1][j][0]+g[i+1][j][1])%=mod; (g[i][j&A[i]][0]+=g[i+1][j][0]+g[i+1][j][1])%=mod; } } ll ans=0; rep(i,1,n-1) rep(j,0,1023) (ans+=(f[i][j][0]*(g[i+1][j][1]+g[i+1][j][0]))%mod)%=mod; printf("%lld ",ans); return 0; }
| 篮球比赛2 |
| 难度级别：A； 运行时间限制：1000ms； 运行空间限制：262144KB； 代码长度限制：2000000B |
|
试题描述
|
|
由于Czhou举行了众多noip模拟赛，也导致放学后篮球比赛次数急剧增加。神牛们身体素质突飞猛进，并且球技不断精进。这引起了体育老师彩哥的注意，为了给校篮球队找到势均力敌的对手，彩哥找到了Czhou神，想要和机房篮球队进行多场友谊赛。Czhou为了顾全校篮球队面子，决定派出配合默契又不至于吊打校篮球队的阵容。 而机房神牛的能力值受到游戏时长，训练时长，个人基础值得影响，可能会不断变化。所以Czhou想根据神牛当天状态从中选出若干名选手，使他们的能力值和等于k。 |
|
输入
|
|
一行三个数n,k,l。表示机房有n个神牛，选出队员能力值和为k，每个神牛的能力最大值<=L且>=0。
|
|
输出
|
|
输出一个数，表示方案数，方案满足选出若干选手使能力和为k。因为答案比较大，最后模10^9+7。
|
|
输入示例
|
|
2 2 2
|
|
输出示例
|
|
6
|
|
其他说明
|
|
样例说明：神牛的能力值可能为(0,2)(1,2)(1,1)(2,0)(2,1)(2,2)，这样都可以选出一些数字使他们的能力值和为2。
对于（0,2）表示第一只牛能力值为0，第二只牛能力为2 类似的 对于（1,2）选出2即满足要求。 对于（1,1）选出全部选手即满足要求。 所以（0,2）（1，1）都是满足要求的方案。 数据范围： n,k<=20 0<=L<=10^9. |
状压DP，设f[i][S]表示前i个神牛，目前选出的队员能够合成能力在S集合中的方案数。
转移就很简单了。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } typedef long long ll; const int mod=1000000007; ll f[2][1<<21]; int n,k,l; int main() { n=read();k=read()+1;l=read(); int cur=0,all=(1<<k)-1;f[0][0]=1; rep(i,1,n) { cur^=1; rep(S,0,all) f[cur][S]=0; rep(S,0,all) if(f[cur^1][S]) { rep(j,0,min(k-1,l)) (f[cur][(S|(S<<j)|(1<<j))&all]+=f[cur^1][S])%=mod; if(l>=k) (f[cur][S]+=f[cur^1][S]*(l-k+1))%=mod; } } ll ans=0; rep(S,0,all) if(S>>k-1&1) (ans+=f[cur][S])%=mod; printf("%lld ",ans); return 0; }